i

LỜI CAM ĐOAN
Tôi cam đoan những kết quả trong luận văn là của việc tìm hiểu, có
trích dẫn và tham chiếu đến các nguồn tư liệu tin cậy. Nội dung luận văn
không sao chép từ các kết quả của các luận văn, luận án khác.


ii

LỜI CẢM ƠN
Lời đầu tiên, tôi xin được gửi lời cảm ơn sâu sắc nhất tới thầy giáo TS.
Lê Văn Phùng, người thầy đã trực tiếp dành nhiều thời gian tận tình hướng
dẫn, cung cấp những thông tin, tài liệu quý báu giúp đỡ tôi hoàn thành bản
luận văn này.
Tôi cũng xin gửi lời cảm ơn đến các giảng viên trường Đại học công
nghệ thông tin và truyền thông - Đại học Thái Nguyên, các thầy Viện công nghệ
thông tin - Viện hàn lâm khoa học công nghệ Việt Nam đã giảng dạy, truyền đạt
những kiến thức và giúp đỡ tôi trong suốt quá trình học tập của mình.
Tôi cũng xin gửi lời cảm ơn tới Phòng giáo dục và đào tạo huyện Văn
Yên, tỉnh Yên Bái, đã tạo mọi điều kiện thuận lợi cho tôi tham gia khóa học
và trong suốt quá trình hoàn thành luận văn.
Cuối cùng, tôi xin cảm ơn những người thân, bạn bè và gia đình đã luôn
cổ vũ động viên tôi hoàn thành luận văn tốt nghiệp này.
Mặc dù đã hết sức cố gắng hoàn thành luận văn với tất cả sự nỗ lực của
bản thân, nhưng luận văn không tránh khỏi những thiếu sót. Kính mong nhận
được những ý kiến đóng góp của quý thầy cô và bạn bè, đồng nghiệp.
Tôi xin chân thành cảm ơn!
Thái Nguyên, ngày 05 tháng 05 năm 2016
Học viên


THEO TỶ LỆ KHÁC BIỆT DB(PCT,DMIN) .......................................... 21
2.1. Định nghĩa các phần tử ngoại lai theo tỷ lệ khác biệt ............................ 21


iv

2.2 Thuật toán đánh giá theo ô..................................................................... 22
2.2.1 Các khái niệm và tính chất liên quan ................................................... 22
2.2.2 Thuật toán FindAllOutsM cho các tập dữ liệu trong bộ nhớ chính ...... 24
2.2.2.1 Tư tưởng thuật toán .......................................................................... 24
2.2.2.2 Mô tả thuật toán FindAllOutsM (Find All Outliers in Memory) ...... 26
2.2.2.3 Đánh giá độ phức tạp thuật toán trong không gian hai chiều ............ 28
2.2.2.4 Tổng quát cho trường hợp nhiều chiều ............................................. 30
2.2.2.5 Đánh giá độ phức tạp trong không gian nhiều chiều ........................ 31
2.3 Phát hiện các phần tử ngoại lai DB(pct,Dmin) trong các tập dữ liệu lớn, ở
bộ nhớ ngoài................................................................................................. 32
2.3.1 Phân tích tổng quát .............................................................................. 32
2.3.2 Thuật toán FindAllOutsD cho các phần tử ngoại lai nằm trong bộ nhớ
ngoài ............................................................................................................ 36
2.3.2.1 Tư tưởng thuật toán .......................................................................... 36
2.4 Xử lý thực nghiệm .................................................................................. 39
2.4.1 Thiết lập thực nghiệm .......................................................................... 39
2.4.2 Thay đổi cỡ của tập dữ liệu.................................................................. 40
2.4.3 Thay đổi giá trị của pct ........................................................................ 42
2.4.4 Thay đổi chiều dữ liệu và số lượng ô .................................................. 42
2.5. Kết luận chương ................................................................................... 43
CHƯƠNG 3 ................................................................................................ 44
CHƯƠNG TRÌNH THỰC NGHIỆM ....................................................... 44
3.1 Hiện trạng và đặt bài toán ....................................................................... 44
3.1.1 Chỉnh sửa dữ liệu................................................................................. 44


Khám phá tri thức

SQL

Ngôn ngữ hỏi SQL, Structured
Query Language

MySQL

Hệ quản trị cơ sở dữ liệu MySQL

ECG(Electrocardiograms)

Điện tâm đồ

Electroencephalograms

Điện não đồ

ID (Identification)

Nhận biết

FindAllOutsM

Find All Outliers in memory

FindAllOutsD


Hình 1.4. Thí dụ phân tích dữ liệu ngoại lai ............................................. 11
Hình1.5: Minh họa- giá trị ngoại lai trong một bộ dữ
Hình 1.6: Các thành phần chính liên quan đến kỹ thuật phát hiện ngoại
lai ................................................................................................................. 14
Hình 1.7: Biểu đồ nhiệt độ tại các tháng khác nhau trong năm .............. 16
Hình 2.2 a .................................................................................................... 29
Hình 2.2b..................................................................................................... 29
Hình 2.2c ..................................................................................................... 30
Hình 2.2d..................................................................................................... 30
Hình 2.3 Thời gian chạy của CPU+I/O với các tập dữ liệu ba chiều nằm
trong bộ nhớ ngoài. Với pct=0.9999. ......................................................... 40
Hình 2.4 ....................................................................................................... 42
Hình 3.1. Dữ liệu ban đầu, chưa điều chỉnh thủ công .............................. 45
Hình 3.2. Bảng điểm đã điều chỉnh, cho phù hợp với yêu cầu tin học hóa
..................................................................................................................... 47
Hình 3.3. Bản đồ Huyện Văn Yên – Tỉnh Yên Bái ................................... 49
Hình 3.4: Tệp Excel bảng điểm cơ sở dữ liệu đầu vào ............................. 52
Hình 3.5: Các danh mục ............................................................................ 52
Hình 3.6: Ta có thể thêm vào hoặc xóa tên các dân tộc............................ 53
Hình 3.7. Ta có thể sửa thêm vào hoặc xóa tên các trường THCS .......... 53
Hình 3.8. Ta có thể sửa, xóa hoặc thêm môn thi ....................................... 54
Hình 3.9. Kết quả tìm phần tử ngoại lai .................................................... 54


1

MỞ ĐẦU
Trong vài thập niên gần đây, cùng với sự thay đổi và phát triển không
ngừng của ngành công nghệ thông tin dẫn đến sự bùng nổ thông tin và dữ
liệu. Luồng thông tin được chuyển tải mau lẹ rất nhanh chóng.Công nghệ khai



3

CHƯƠNG 1. PHẦN TỬ NGOẠI LAI VÀ ỨNG DỤNG TRONG
KHAI PHÁ DỮ LIỆU
Nội dung của chương này giới thiệu quá trình phát hiện tri thức, khai
phá dữ liệu, trình bày một số khái niệm liên quan đến phần tử ngoại lai và
phát hiện phần tử ngoại lai trong cơ sở dữ liệu. Đồng thời, đi sâu tìm hiểu ứng
dụng thực tế của phần tử ngoại lai trong các lĩnh vực của cuộc sống.
1.1 Khai phá dữ liệu và phát hiện tri thức
1.1.1 Một số khái niệm
Người ta xác định rõ dữ liệu, thông tin, tri thức và vai trò của chúng
trong xã hội tri thức.
Nói chung, dữ liệu bao gồm những mệnh đề phản ánh thực tại. Một
phân loại lớn của các mệnh đề quan trọng trong thực tiễn là các đo
đạc hay quan sát về một đại lượng biến đổi. Các mệnh đề đó có thể bao gồm
các số, từ hoặc hình ảnh.
Tri thức hay kiến thức bao gồm những dữ kiện, thông tin, sự mô tả, hay
kỹ năng có được nhờ trải nghiệm hay thông qua giáo dục. Trong tiếng Việt,
cả "tri" lẫn "thức" đều có nghĩa là biết. Tri thức có thể chỉ sự hiểu biết về một
đối tượng, về mặt lý thuyết hay thực hành. Nó có thể tiềm ẩn, chẳng hạn
những kỹ năng hay năng lực thực hành, hay tường minh, như những hiểu biết
lý thuyết về một đối tượng, nó có thể ít nhiều mang tính hình thức hay có tính
hệ thống. Mặc dù có nhiều lý thuyết về tri thức, nhưng hiện không có một
định nghĩa nào về tri thức được tất cả mọi người chấp nhận.
Thành tựu tri thức liên quan đến những quá trình nhận thức phức
tạp: tri giác, truyền đạt, liên hệ, và suy luận. Trong triết học, ngành nghiên
cứu về tri thức được gọi là tri thức luận.
1.1.2 Khai phá dữ liệu

rất nhiều kiểu dữ liệu khác nhau:
 Cơ sở dữ liệu quan hệ


5

 Kho dữ liệu
 Cơ sở dữ liệu giao dịch
 Dữ liệu không gian và thời gian
 Dữ liệu chuỗi thời gian
 Cơ sở dữ liệu đa phương tiện
1.1.3 Phát hiện tri thức
Với sự tiến bộ của khoa học kỹ thuật và nhu cầu con người ngày càng
tăng đã tạo nên một thời đại bùng nổ thông tin trong mọi lĩnh vực của đời
sống. Với lượng thông tin “khổng lồ” đó thì cần có các kỹ thuật khai phá dữ
liệu hiệu quả để lấy ra những thông tin hữu ích. Một số các ngôn ngữ truy vấn
như SQL được sử dụng 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 dữ liệu theo những
yêu cầu đơn giản. Các kiểu dữ liệu đa phương tiện được một số các hệ thống
cơ sở dữ liệu hỗ trợ như: Dữ liệu âm thanh, hình ảnh…không thể đáp ứng
được khi các yêu cầu của người sử dụng ngày càng cao và phức tạp.

Hình 1.1. Vai trò của tri thức
Do đó, với 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: Phát hiện tri thức trong cơ sở dữ liệu. Phát hiện 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:
1. Chuẩn bị dữ liệu: Dữ liệu được tập trung vào trong các cơ sở dữ liệu, các


6

Phần tử ngoại lai có thể có nhiều nguyên nhân bất thường. Một bộ máy
vật lý cho lấy số đo có thể đã phải chịu đựng một sự cố thoáng qua. Có thể có
một lỗi trong truyền dữ liệu hoặc sao chép. Ngoại lai phát sinh do sự thay đổi
trong hệ thống hành vi, hành vi gian lận, lỗi của con người, lỗi công cụ, hay
chỉ đơn giản là thông qua độ lệch tự nhiên trong quần thể. Một mẫu có thể đã
bị nhiễm các yếu tố từ bên ngoài dân số được kiểm tra. Ngoài ra, một ngoại
lai có thể là kết quả của một lỗ hổng trong lý thuyết giả định, kêu gọi tiếp tục
điều tra bởi các nhà nghiên cứu.
Phần tử ngoại lai là quan sát xa nhất, có thể bao gồm tối đa hoặc tối
thiểu mẫu, hoặc cả hai, tùy thuộc vào việc phần tử đó cao hay thấp. Tuy
nhiên, tối đa và tối thiểu mẫu không phải lúc nào cũng là giá trị ngoại lai bởi
vì có thể không có bất thường xa với quan sát khác. Giải thích của các số liệu
thống kê từ các tập dữ liệu bao gồm các giá trị ngoại lai có thể gây hiểu nhầm.
Ví dụ: Nếu một người tính toán nhiệt độ trung bình của 10 đối tượng
trong một căn phòng, và chín trong số đó là từ 20oC đến 25oC, nhưng một đối
tượng ở 175°C, trung bình của các dữ liệu sẽ được giữa 20oC và 25°C, nhưng
nhiệt độ trung bình sẽ vào khoảng 35,5oC và 40°C. Trong trường hợp này,
trung bình tốt hơn phản ánh nhiệt độ của một đối tượng lấy mẫu ngẫu nhiên
hơn so với trung bình. Tuy nhiên giải thích nghĩa là "một mẫu điển hình",
tương đương với mức trung bình, là không chính xác. Như minh họa trong
trường hợp này, giá trị ngoại lai có thể chỉ ra các điểm dữ liệu mà thuộc về
một dân số khác biệt so với phần còn lại của tập hợp mẫu. Ước lượng khả
năng đối phó với các ngoại lệ được cho là mạnh mẽ.[9]


9

1.2.2. Khái niệm ngoại lai trong cơ sở dữ liệu
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ị

thực hiện với tập dữ liệu còn lại được xem là các phần tử ngoại lai.[7]
Có nhiều cách định nghĩa và hiểu khác nhau về phần tử ngoại lai. Tuy
nhiên chúng có điểm chung là: Một phần tử ngoại lai là những quan trắc mà
có sự khác biệt đáng kể đối với những quan trắc còn lại.
Có nhiều công trình nghiên cứu về phát hiện phần tử ngoại lai. Các
phương pháp chính để phát hiện phần tử ngoại lai bao gồm:
1. Xác định phần tử ngoại lai theo khoảng cách (Distance –
Based):
Theo hướng tiếp cận này cần phải xác định một hàm đo khoảng
cách(metric) giữa các phần tử trong tập dữ liệu. Các phần tử ngoại
lai là những phần tử nằm khá xa với tập các phần tử còn lại. Điển
hình cho hướng tiếp cận này là các tác giả Knorr and Ng.[5]
2. Xác định theo thống kê (Statistical – Based):
Hướng nghiên cứu này dựa trên việc xác định các mô hình phân
phối thống kê mà các phần tử phải tuân theo(phân phối chuẩn,
phân phối X2…). Phần tử ngoại lai là những phần tử không tuân
theo luật này. Điển hình cho hướng tiếp cận này là các tác giả
Barnett and lewis[4]


11

3. Xác định theo độ khác biệt (Deviation – Based):
Hướng nghiên cứu này dựa trên những đặc trưng cơ bản của các
phần tử trong một tập các phần tử. Các phần tử có những đặc
trưng khác biệt quá lớn so với các phần tử còn lại thì là các phần
tử ngoại lai. Điển hình cho hướng tiếp cận này là các tác giả
Arning, Agrawal, Raghaval.[1]
Một phần tử ngoại lai có thể là một đối tượng dữ liệu trong các trường
hợp sau:

hết các điểm khác. Tuy nhiên, không có một định nghĩa về phần tử ngoại lai
nào được chấp nhận rộng rãi. Các phần tử ngoại lai thường được xem xét là
các điểm không thoả mãn dưới mô hình của dữ liệu. Việc phần tử ngoại lai có
bị loại bỏ hay không còn phụ thuộc vào từng chương trình ứng dụng và quyết
định từ chuyên gia.
1.3. Phát hiện các phần tử ngoại lai trong dữ liệu
Phát hiện phần tử ngoại lai là các mẫu trong dữ liệu mà không phù hợp
với một định nghĩa khái niệm về hành vi bình thường . Hình 1.5 minh họa giá
trị ngoại lai trong một bộ dữ liệu hai chiều đơn giản. Những dữ liệu có hai
khu vực bình thường N1 và N2 , vì hầu hết các quan sát nằm ở hai vùng này.
Điểm đó là đủ xa cách xa các khu vực ví dụ: chỉ o1 và o2, và điểm trong khu
vực O3, là giá trị ngoại lai . x y N1 N2 o1 o2 O3


13

Hình1.5: Minh họa- giá trị ngoại lai trong một bộ dữ liệu 2 chiều đơn giản
Những khó khăn trong việc phát hiện phần tử ngoại lai trong cơ sở dữ liệu:
 Bao gồm việc xác định mọi hành vi bất bình thường có thể có
trong khu vực cơ sở dữ liệu.
 Chỉ ra được ranh giới không chính xác giữa bình thường và
ngoại lai.
 Mỗi một lĩnh vực thì khái niệm phần tử ngoại lai có thể khác
nhau. Chính vì vậy lĩnh vực ứng dụng để áp dụng kỹ thuật tìm
kiếm phát hiện phần tử ngoại lai là rất khó khăn.
Do những thách thức trên, vấn đề phát hiện phần tử ngoại lai ở dạng
chung nhất của nó, không phải là dễ dàng để giải quyết. Trong thực tế, hầu
hết các phần tử ngoại lai hiện các kỹ thuật phát hiện giải quyết cụ thể xây
dựng vấn đề được gây ra bởi các yếu tố khác nhau. Chẳng hạn như tính chất
của dữ liệu, sẵn có của dữ liệu được dán nhãn, loại các giá trị ngoại lai được

 Phát hiện xâm nhập
 Lỗi / phát hiện thiệt hại
 Tội phạm/ điều tra / lập kế hoạch khủng bố
 Tin học y tế

Hình 1.6: Các thành phần chính liên quan đến kỹ thuật phát hiện ngoại lai
Nếu một thể hiện dữ liệu cá nhân có thể được coi là bất thường đối
với phần còn lại của dữ liệu, được gọi là một ngoại lai điểm . Đây là đơn giản
nhất ngoại lai và là trọng tâm của phần lớn các nghiên cứu về phát hiện ngoại
lai .[9]


15

Ví dụ: Trong hình 1.1 , các điểm O1 và o2 cũng như các điểm trong khu
vực O3 nằm ngoài ranh giới của khu vực bình thường, và do đó có giá trị
ngoại lai điểm từ họ là khác nhau từ các điểm dữ liệu bình thường.
Ví dụ: Nếu chúng ta phát hiện xem xét gian lận thẻ tín dụng với tập dữ
liệu tương ứng với thẻ tín dụng của một cá nhân giao dịch, giả sử dữ liệu bởi
chỉ có một tính năng là số tiền chi. Một giao dịch mà số tiền bỏ ra là rất cao so
với mức bình thường chi tiêu cho người đó sẽ là một ngoại lai điểm.
Nếu một trường dữ liệu là bất thường trong một văn bản cụ thể (nhưng
không khác), sau đó nó được gọi là một ngoại lai theo ngữ nghĩa. Các khái
niệm về một bối cảnh được gây ra bởi cấu trúc trong thiết lập dữ liệu và có
được quy định như một phần của việc xây dựng vấn đề.
Dữ liệu được định nghĩa sử dụng hai bộ của các thuộc tính, theo ngữ cảnh
và thuộc tính. Các thuộc tính ngữ cảnh được sử dụng để xác định các nội dung.
Ví dụ: Trong bộ dữ liệu không gian, kinh độ và vĩ độ của một vị trí là
các thuộc tính ngữ cảnh. Trong chuỗi thời gian dữ liệu, thời gian là một thuộc
tính ngữ cảnh mà xác định vị trí của một trường hợp trên toàn bộ chuỗi. Các


17

hiện xâm nhập áp dụng các kỹ thuật phát hiện ngoại lai. Các thách thức chính
cho việc phát hiện ngoại lai là:
+ Khối lượng dữ liệu lớn: Điều này đòi các kỹ thuật hiệu quả tính toán.
+ Truyền dữ liệu: Điều này đòi hỏi phân tích trực tuyến.
+ Tỷ lệ báo động sai: Tỷ lệ phần trăm nhỏ nhất của báo động sai trong
số hàng triệu đối tượng dữ liệu có thể làm cho là quá sức đối với một nhà
phân tích.
+ Được gán nhãn dữ liệu thường không có sẵn cho xâm nhập: Đây sẽ
ưu tiên cho ban giám sát và phát hiện ngoại lai không có giám sát kỹ thuật. Hệ
thống phát hiện xâm nhập đã được phân loại vào máy chủ dựa và mạng dựa
trên hệ thống phát hiện xâm nhập.
1.4.2 Phát hiện gian lận
Gian lận liên quan đến hoạt động tội phạm xảy ra trong các tổ chức
thương mại, các tổ chức như ngân hàng, các công ty thẻ tín dụng, cơ quan bảo
hiểm, các công ty điện thoại di động, thị trường chứng khoán , … Người sử
dụng độc hại có thể là khách hàng thực tế của tổ chức hoặc phải dùng đến
hành vi trộm cắp danh tính (giả làm khách hàng). Các hoạt động phát hiện
nhằm mục đích phát hiện tiêu thụ trái phép các nguồn tài nguyên được cung
cấp bởi tổ chức để ngăn chặn thiệt hại kinh tế. Một cách tiếp cận chung để
phát hiện ngoại lai ở đây sẽ liên quan duy trì một cấu hình sử dụng cho từng
khách hàng và theo dõi các cấu hình để phát hiện bất kỳ sai lệch được gọi là
hoạt động giám sát. Một số ứng dụng cụ thể của phát hiện gian lận:
- Phát hiện thẻ tín dụng gian lận: Kỹ thuật phát hiện ngoại lai được áp
dụng để phát hiện gian lận đối với thẻ tín dụng. Điều này cũng tương tự như
việc phát hiện gian lận bảo hiểm. Cách sử dụng gian lận của thẻ tín dụng: Kết
hợp với các vụ trộm cắp thẻ tín dụng. Các hồ sơ dữ liệu được xác định trên
một số phương diện như nhận diện người sử dụng, đã dành số tiền, thời gian

trị ngoại lai do một số lý do như tình trạng bệnh nhân bất thường hoặc thiết bị