BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2

TRẦN VIỆT CƯỜNG
NGHIÊN CỨU
CÁC PHẦN TỬ NGOẠI LAI
LUẬN VĂN THẠC SĨ MÁY TÍNH

LUẬN VĂN THẠC SĨ MÁY TÍNH

Người hướng dẫn khoa học: GS.TS. Vũ Đức Thi
HÀ NỘI, 2015

1
LỜI CẢM ƠN Em xin chân thành gửi lời cảm ơn tới GS.TS Vũ Đức Thi, thầy đã nhiệt
tình hướng dẫn và giúp đỡ em trong quá trình hoàn thành luận văn này.
Em xin chân thành gửi lời cảm ơn tới các thầy cô trong Viện CNTT
thuộc Viện Khoa học Hàn lâm Việt Nam đã tận tình giảng dạy, chỉ bảo và
giúp đỡ em trong quá trình học tập tại trường cũng như trong thời gian hoàn
thành luận văn này.
Em xin chân thành gửi lời cảm ơn tới các thầy cô phòng Sau Đại học,
khoa CNTT và thư viện trường ĐHSPHN2 đã tận tình giúp đỡ và truyền đạt


Trần Việt Cường 3
MỤC LỤC

LỜI CẢM ƠN 1

LỜI CAM ĐOAN 2

MỤC LỤC 3

BẢNG KÝ HIỆU CÁC CHỮ VIẾT TẮT 6


2.1 Định nghĩa các phần tử ngoại lai dựa trên khoảng cách 19

2.2 Thuật toán Nested-Loop. 20

2.2.1 Tư tưởng thuật toán. 20

2.2.2 Mô tả thuật toán Nested Loop: 21

2.2.3 Ước lượng tham số p, D sử dụng phương pháp lấy mẫu 22

2.2.4 Đánh giá độ phức tạp của thuật toán Nested Loop. 25

2.3 Thuật toán đánh giá theo ô 25

2.3.1 Các khái niệm và tính chất liên quan 264
2.3.2 Thuật toán FindAllOutsM cho các tập dữ liệu trong bộ nhớ
chính. 28

2.3.2.1 Tư tưởng thuật toán. 28

2.3.2.2 Mô tả thuật toán FindAllOutsM (Find All Outlier in
Memory) 33

2.3.2.3 Đánh giá độ phức tạp thuật toán trong không gian hai
chiều. 36

2.3.2.4 Tổng quát cho trường hợp nhiều chiều 36

3.4. Sự ảnh hưởng của tham số Minpts. 64

3.4.1 Sự phụ thuộc của LOF theo Minpts. 645
3.4.2 Xác định miền của Minpts 65

3.5 Đánh giá độ phức tạp của thuật toán xác định giá trị LOF. 68

CHƯƠNG 4: CÀI ĐẶT VÀ THỬ NGHIỆM 70

4.1 Yêu cầu cài đặt 70

4.1.1 Cấu trúc tệp dữ liệu đầu vào 70

4.1.2 Cấu trúc các lớp chương trình 71

4.2 Thực hiện chương trình và đánh giá kết quả 73

4.2.1 Sơ đồ thuật toán Nested Loop 73

4.2.2 Thực hiện chương trình và kết quả 75

4.2.2.1 Nhập dữ liệu: 75

4.2.2.2 Thực hiện thuật toán: 76

4.2.2.3 Kết quả thực nghiệm: 76


chứng khoán, những tuyến đường bất ổn không hợp lý trong giao thông,
những ứng dụng trong hệ thống an ninh, dự báo thời tiết, trong lĩnh vực thể
thao…vv. Tuy nhiên, với số lượng dữ liệu tập trung và lưu trữ trong cơ sở dữ
liệu ngày càng lớn thì việc tìm kiếm các phần tử ngoại lai trở nên cần thiết
hơn nhiều trong cuộc sống.
Xuất phát từ yêu cầu và ý nghĩa thực tiễn đó, đồng thời mong muốn
được tìm hiểu và nghiên cứu vấn đề này, tôi đã lựa chọn và thực hiện luận văn
này với đề tài “Nghiên cứu các phần tử ngoại lai”. Đây là lĩnh vực tương đối
mới, tôi hy vọng đề tài trên đây với sự hướng dẫn của GS.TS Vũ Đức Thi,
cùng sự góp ý của các chuyên gia sẽ giúp giải quyết một số bài toán thực tế
phục vụ cho xã hội ngày càng phát triển trong công cuộc Công nghiệp hóa và
Hiện đại hóa đất nước.
2. Mục đích nghiên cứu
- Cung cấp một số giải thích hoặc mô tả về không gian dữ liệu mà trong
đó xuất hiện phần tử ngoại lai.
- Cung cấp một số thông tin về mối quan hệ giữa các phần tử ngoại lai.
- Đưa ra những ứng dụng liên quan đến phần tử ngoại lai nhằm giải
quyết những vướng mắc trong thực tế.
3. Nhiệm vụ nghiên cứu
- Tìm hiểu các khái niệm về khám phá tri thức và khai thác dữ liệu.

8
- Tìm hiểu các khái niệm về phần tử ngoại lai theo cách nhìn địa phương
và toàn cục.
- Tìm hiểu các thuật toán tìm kiếm phần tử ngoại lai trên dữ liệu lớn,
nhiều chiều.
- Kiểm tra, đánh giá thuật toán trên cơ sở dữ liệu thực của tập dữ liệu
khách hàng trong Ngân hàng Nông nghiệp và Phát triển Nông thôn
Agribank.
4. Đối tượng và phạm vi nghiên cứu

hội. Với lượng thông tin ngày càng nhiều (có thể nói là “khổng lồ”) và phức
tạp thì cần có các kỹ thuật và phương pháp khai thác dữ liệu hiệu quả để lấy
ra những thông tin cần thiết cho công việc. Việc sử dụng một số các ngôn ngữ
truy vấn nhằm lấy ra những thông tin theo yêu cầu của người sử dụng, nhưng
hầu hết các ngôn ngữ này chỉ lấy ra được những dữ liệu theo những yêu cầu
đơn giản, tầm thường, hay các kiểu dữ liệu đa phương tiện được hệ thống hỗ
trợ như: Dữ liệu âm thanh, hình ảnh,… Nhưng kết quả này không thể đáp ứng
được khi yêu cầu của con người sử dụng ngày càng cao và phức tạp. Do đó,
nhu cầu tìm kiếm tri thức trong cơ sở dữ liệu đã hình thành một lĩnh vực mới
đó là Khám phá tri thức trong cơ sở dữ liệu; Khám phá tri thức là toàn bộ quá
trình tìm kiếm tri thức từ dữ liệu, bao gồm các bước sau:
- Chuẩn bị dữ liệu: Dữ liệu được tập trung vào trong cơ sở dữ liệu, các kho
lưu trữ dữ liệu. Dữ liệu đó có thể là “chưa sạch” tức là có cả dữ liệu không

10
phù hợp, nhiễu, sai xót và các dữ liệu không đầy đủ thông tin. Trong bước
này dữ liệu được làm sạch để loại bỏ các dữ liệu không liên quan, dữ liệu
không phù hợp, công việc này có thể được tiến hành trước hoặc sau khi phát
hiện dữ liệu “chưa sạch” (bị nhiễm bẩn). Sau khi dữ liệu được làm sạch, dữ
liệu sẽ được bổ sung các thông tin cần thiết, sau đó dữ liệu được biến đổi
theo các dạng phù hợp để thực hiện quá trình khai thác dữ liệu.
- Khai thác dữ liệu: Khai thác dữ liệu là một bước quan trọng trong quá trình
khám phá tri thức, bước này sử dụng các kỹ thuật và các phương thức thông
minh để xác định các mẫu dữ liệu theo yêu cầu người dùng. Khai thác dữ liệu
được định nghĩa là quá trình khai thác, khám phá những thông tin hữu ích,
chưa được biết trước, tiềm ẩn và không tầm thường từ những tập dữ liệu lớn.
Khai thác dữ liệu bao gồm:
 Tìm kiếm các luật kết hợp: Sử dụng các luật đơn giản để biểu diễn tri
thức. Tìm kiếm những mối quan hệ có ích của dữ liệu.
 Phát hiện phần tử ngoại lệ: Tìm kiếm và xác định các đối tượng dữ liệu

lý. Bằng cách lựa chọn các giá trị thích hợp cho p và D, quy trình khám phá
tri thức trong cơ sở dữ liệu (KDD) có thể làm cho các phần tử ngoại lai có
nhiều ý nghĩa hơn đối với người sử dụng và giảm thời gian xác định p và D.
12
tìm kiếm Website áp dụng các kỹ thuật thông minh để có thể tìm kiếm được
những thông tin, Website với độ chính xác cao theo yêu cầu của người sử
dụng giúp người dùng thuận tiện trong việc xử lý thông tin. Ngoài ra, kỹ thuật
khai thác dữ liệu còn được áp dụng trong các lĩnh vực khai thác như phân tích
thị trường chứng khoán, dự báo tỷ lệ thay đổi ngoại tệ, tìm kiếm các gene
trong chuỗi DNA, dự báo thời tiết, nhận dạng ảnh và văn bản…
1.3 Phần tử ngoại lai.
1.3.1 Khái niệm phần tử ngoại lai
Trong các tập dữ liệu thường tồn tại các đối tượng dữ liệu không tuân
theo một hình thức hoặc một mô hình dữ liệu chung, các đối tượng dữ liệu mà
giá trị dữ liệu được xem là nằm ngoài phạm vi hoặc không liên quan tới tập
dữ liệu còn lại. Những đối tượng có đặc tính như vậy được gọi là phần tử
ngoại lai.
Có nhiều định nghĩa được đưa ra để định nghĩa phần tử ngoại lai như định
nghĩa của Barnet và Levis: “Một phẩn tử ngoại lai là một đối tượng xuất hiện
không nhất quán với tập dữ liệu còn lại”. Với Hawkins thì mô tả định nghĩa
trực quan về phần tử ngoại lai có thể là “Một đối tượng mà nó lệch hướng rất

14
nhiều với đối tượng khác do đó dẫn đến sự nghi ngờ rằng chúng được tạo ra
bởi một kỹ thuật khác” [10]. Nói cách khác, các đối tượng không cùng một
mô hình tạo sinh với tập dữ liệu còn lại được xem là phần tử ngoại lai.
Các phần tử ngoại lai có thể do lỗi thực hiện hoặc lỗi do phép đo gâp ra.
Ví dụ việc hiển thị một người có tuổi 1000 có thể là do việc thiết lập mặc định
chương trình không giới hạn tuổi dữ liệu. Mặt khác, các phần tử ngoại lai có
thể là kết quả của quá trình tự nhiên.
Có nhiều thuật toán khai thác dữ liệu cố gắng làm cực tiểu hóa sự ảnh
hưởng của các phần tử ngoại lai, loại bỏ chúng cùng một lúc. Tuy nhiên, điều
đó có thể làm mất những thông tin tiềm ẩn quan trọng khi “nhiễu của người
này lại là tín hiệu của người khác”.

dạng tội phạm,…
Sau sự tấn công mạng Internet và các trang web những năm gần đây, đặc
biệt là sự kiện khủng bố tấn công nước Mỹ ngày 11/9/2001 hơn 13 năm về
trước, người ta quan tâm nhiều hơn đến việc bảo mật thông tin máy tính, bao
gồm cả phần cứng, phần mềm và cả hệ thống mạng (như phát hiện ra sự xâm
nhập trái phép vào hệ thống mạng). Bảo mật hệ thống mạng bao gồm tần suất
của các tấn công dịch vụ mà một sự kiện bên ngoài được phát hiện trong gói
dữ liệu hệ thống mạng (như phát hiện ra số lượng lớn, không bình thường các
gói dữ liệu từ một nguồn lạc danh), các công cụ thống kê có thể được dùng để
tìm ra những thói quen là ngoại lệ tương ứng với một lịch sử đã biết (ví dụ:
những thói quen điển hình theo đăng nhập, cách thức truy xuất dữ liệu…).

16
Với các hệ thống thanh toán điện tử bao gồm các ứng dụng như thẻ ngân
hàng, thẻ thông minh, thẻ điện thoại, và thẻ tín dụng, chúng ta quan tâm tới
việc làm sao để phát hiện ra các loại thẻ giả, thẻ không hợp lệ trong hệ thống
thanh toán điện tử.
Thêm một ứng dụng nữa trong việc phát hiện phần tử ngoại lai là ứng
dụng để nghiên cứu cổ phiếu, chứng khoán. Nhiều cá nhân và công ty đã từng
thử dự đoán giá trị các cổ phiếu được niêm yết dựa trên việc tìm kiếm các
phần tử ngoại lai (ví dụ: Giả sử phần lớn giá các cổ phiếu ở một ngành đang
lên cao ở một thị trường ảo và có các thị trường khác (trong cùng một ngành)
mà giá cổ phiếu biến động đột ngột, các phẩn tử ngoại lai như thế nên được
xác định và sau đó các nhà phân tích có thể dựa vào các nguyên nhân để giải
thích sự quá nóng hoặc quá lạnh của thị trường, để xác định khuynh hướng
của cố phiếu có thể mua vào hay bán ra hoặc tích lũy). Sự có mặt của các
phần tử ngoại lai trong các cổ phiếu của các quỹ chung, có thể giúp làm đa
dạng hóa bảng niêm yết cổ phiếu trên sàn chứng khoán trong cùng một loại.
Trên các thị trường chứng khoán thế giới, các giao dịch được thực hiện
mỗi ngày lên đến con số hàng triệu giao dịch, các nhà quản lý bảng niêm yết,

mục đích sau:
 Cung cấp một số thông tin về mối quan hệ giữa các phần tử ngoại lai
 Cung cấp một số giải thích hoặc mô tả về không gian dữ liệu mà trong
đó xuất hiện phần tử ngoại lai.
Và một vấn đề khác chúng tôi cần quan tâm đó là việc liên quan tới ý
nghĩa của các phần tử ngoại lai. Cho đến nay, chưa có một định nghĩa nào có

18
thể định nghĩa một cách đầy đủ và chính xác về phần tử ngoại lai, việc xác
định các phần tử ngoại lai trong mỗi lĩnh vực là khác nhau, bởi vì ý nghĩa
ngoại lai của các phần tử ngoại lai mang tính chất và đặc trưng của từng lĩnh
vực áp dụng (có thể nhiễu của người này nhưng lại là tín hiệu tốt của người
khác), nên rất khó có thể đưa ra được một định nghĩa hoàn chỉnh và chính xác
về phần tử ngoại lai.


ngoại lai có thể có.

20
Theo định nghĩa các phần tử ngoại lai dựa trên khoảng cách DB(p,D) thì
M=(1 - p)*N. Việc tìm kiếm tất cả các phần tử ngoại lai sẽ được bắt đầu từ
việc tìm kiếm các đối tượng thuộc S(o) của tất cả các điểm O trong tập dữ
liệu. Trong quá trình tìm kiếm nếu số lượng của S(o) lớn hơn M thì O được
gọi là không ngoại lai. Ngược lại sau khi kết thúc quá trình tìm kiếm mà lực
lượng của S(o) ≤ M thì thông báo O là phần tử ngoại lai
2.2 Thuật toán Nested-Loop.
2.2.1 Tư tưởng thuật toán.
Để tìm kiếm tất cả các phần tử ngoại lai dựa trên khoảng cách DB(p,D)
trên tập dữ liệu lớn, nằm ở bộ nhớ ngoài, thuật toán Nested Loop chia tập dữ
liệu thành các khối sử dụng các vòng lồng nhau để tìm kiếm. Cụ thể, giả sử có
một bộ nhớ trung gian cỡ b% tập dữ liệu, tư tưởng thuật toán chia bộ nhớ
thành hai phần gọi là mảng A và mảng B, mỗi mảng cỡ b/2% cỡ của tập dữ
liệu, chia tập dữ liệu thành n=[2*100/b] khối để mỗi khối có thể được chứa
trong mỗi mảng của bộ nhớ.
Trước tiên, đọc một khối vào mảng A, với mỗi đối tượng O trong mảng
A, thuật toán lưu lại số lượng các đối tượng thuộc S(o), việc tính toán sẽ kết
thúc cho một đối tượng cụ thể ngay khi số lượng các đối tượng thuộc S(o)
vượt quá M và thông báo O không phải là phần tử ngoại lai. Tiếp theo, đọc
lần lượt các khối còn lại vào trong mảng B, với mỗi đối tượng O thuộc mảng
A chưa được thông báo là không ngoại lai và các đối tượng q thuộc khối nằm
trong mảng B, chúng ta sẽ tiến hành tính toán khoảng cách d(o,q) để xem xét
q có là lân cận thuộc S(o) hay không, khi số lượng của S(o) lớn hơn M thì
thông báo P là không ngoại lai. Ngược lại, sau khi thực hiện tính toán với tất
cả các khối còn lại mà số lượng S(o) ≤ M thì thông báo O là ngoại lai. Bằng

21

j
)≤D) {count
i
++;
If (count
i
>M) {t
i
=không ngoại lai; break;}
}

22
}
3. While (những khối còn chưa được so sánh với mảng A) do
{
a. Lưu một khối vào mảng B (nhưng sẽ giữ lại một khối mà nó
chưa bao giờ được lưu vào mảng A để tính toán cho lần sau)
b. For (mỗi điểm t
i
chưa được đánh dấu trong mảng A) do

{for (mỗi điểm t
j
trong mảng B) do
If (d(t
i
,t
j
) ≤ D) {count
i

việc khởi tạo giá trị p, để dễ dàng ta nên lấy giá trị p sát với 1 và nếu cần thì
giảm giá trị p khi chạy lại, hơn nữa giá trị p gần với 1 sẽ cho thời gian xử lý
nhanh hơn trong các bước khai thác dữ liệu bởi vì giảm được các phép so
sánh trước khi một điểm bị loại trừ từ tập dự tuyển các phần tử ngoại lai và
tốn tại ít bộ nhớ hơn.
Thật vậy, ta xét giải thuật xử lý Nested Loop sau:
1, For(mỗi điểm t
i
trong mảng A) do:
2, Count
i
= 0;
3, If(d(t
i
,t
j
) <= D) do:
4, Count
i
++;
5, If( Count
i
> M) {t
i
= không ngoại lai; Break;}
6, }// End if
7, }// End for
Trong đó, M = (1 - p)*N; Như vậy với p càng gần 1 kéo theo M càng
nhỏ. Khi đó trong dòng lệnh thứ 5 trong giải thuật trên giá trị Count
i