1

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
NGUYỄN XUÂN TRƢỜNG NGHIÊN CỨU CÁC PHẦN TỬ NGOẠI LAI
TRONG CSDL & ỨNG DỤNG
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

THÁI NGUYÊN – 2014
2

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN XUÂN TRƢỜNG NGHIÊN CỨU CÁC PHẦN TỬ NGOẠI LAI

Nguyễn Xuân Trƣờng

4

LỜI CẢM ƠN

Trƣớc hết, tôi vô cùng biết ơn sâu sắc đến Thầy giáo GS.TS Vũ Đức
Thi, 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.
Sau cùng tôi xin bày tỏ lòng biết ơn đến ngƣời thân, cùng bạn bè, đồng
nghiệp cơ quan, những ngƣời luôn cổ vũ động viên tôi hoàn thành bản luận
văn tốt nghiệp này. Thái Nguyên, ngày 18 tháng 04 năm 2014
Học viên

Nguyễn Xuân Trƣờng

7

DANH MỤC THUẬT NGỮ

Từ viết tắt
Nghĩa của từ
Box_Cox
Tên phép biến đổi thành dạng xấp xỉ chuẩn
DB (Distance Based)
Dựa theo khoảng cách
DSE (Donoho Stahel)
Tên bộ ƣớc lƣợng mạnh đa biến
KDD (Know ledgement
Discovery in Database )
Khám phá tri thức trong cơ sở dữ liệu
LOF ( Local Outlier Factor)
Yếu tố ngoại lai cục bộ
MAD (Median Absolute
Deviation)
Là tên một bộ ƣớc lƣợng mạnh đơn biến
NL ( Nested Loop)
Tên một thuật toán phát hiện phần tử ngoại
lai
Shorth ( Shortest half)
Là tên một bộ ƣớc lƣợng mạnh đơn biến
thƣờng nhằm mục đích tìm kiếm, khám phá, các dạng mẫu thƣờng gặp. Chủ
yếu tập trung vào các hƣớng: Tìm kiếm các luật kết hợp, nhận dạng và phân
lớp mẫu…Còn lĩnh vực khám phá phần tử ngoại lai mới bƣớc đầu đƣợc sự
quan tâm nghiên cứu.
Mặc dù nó đƣợc ứng dụng trong nhiều lĩnh vực trong cuộc sống: nhƣ
phát hiện những thẻ bất thƣờng trong hệ thống ngân hàng, những tuyến đƣờng
bất ổn không hợp lý trong giao thong, ứng dụng trong hệ thống an ninh, dự
báo thời tiết, trong thị trƣờng chứng khoán, trong lĩnh vực thể thao Tuy
nhiên, với số lƣợng dữ liệu đƣợc 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 ngoại lệ hoặc các phần tử ngoại lai trở nên cấp
thiết hơn nhiều.
10

CHƢƠNG I: KHÁM PHÁ TRI THỨC TRONG CƠ SỞ DỮ LIỆU VÀ
PHẦN TỬ NGOẠI LAI
Nội dung của chƣơng này giới thiệu quá trình khám phá tri thức, khai
thác dữ liệu và các ứng dụng thực tế có sự hỗ trợ của các kỹ thuật khai thác
dữ liệu. Đồng thời trình bày khái niệm về phần tử ngoại lai và mối quan hệ
giữa các lĩnh vực khám phá phần tử ngoại lai và lĩnh vực khai thác dữ liệu.
1.1 Khám phá 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

của dữ liệu.
 Dự báo: Xác định các hàm hồi quy.
 Nhận dạng và phân lớp mẫu :Tìm kiếm, xác định
các mẫu theo yêu cầu, phân chia các mẫu thành các lớp nhằm
phục vụ cho mục đích sử dụng.
 Phát hiện phần tử ngoại lệ : Tìm kiếm và xác định
các các đối tƣợng dữ liệu lỗi, bất thƣờng và các phần tử ngoại lai.
Môi trƣờng khám phá tri thức nhằm mục đích hỗ trợ quá
trình khai thác dữ liệu .Do đó, hai thuật ngữ “ khai thác dữ liệu”(
Data Mining) và “ khám phá tri thức”(Knowledge Discovery)
thƣờng đƣợc sử dụng để thay thế cho nhau.
- Đánh giá : Bƣớc đánh giá bao gồm đánh giá mẫu và biểu
diễn tri thức. Đánh giá mẫu là tìm ra những mẫu quan tâm từ các mẫu đã
có trong bƣớc khai thác dữ liệu. Có thể sử dụng các ngƣỡng cần thiết để
lọc ra các mẫu cần khai thác.Biểu diễn tri thức là quá trình cho phép
12

ngƣời sử dụng tƣơng tác với hệ thống bằng các nhiệm vụ hoặc các truy
vấn tìm kiếm dữ liệu cụ thể. Cung cấp thông tin nhằm mục đích trợ giúp
việc tìm kiếm và thực hiện khai thác dữ liệu chi tiết dựa trên dữ liệu đã
đƣợc khai thác.
Ngoài ra, biểu diễn tri thức cho phép ngƣời sử dụng trình duyệt các
lƣợc đồ cơ sở dữ liệu và kho dữ liệu hoặc các cấu trúc dữ liệu.
Hình 1.1 trình bày tổng thể qui trình KDD, không chỉ bao gồm khai
thác dữ liệu mà còn có các bƣớc khác để có đƣợc kết quả. Các bƣớc khai thác
dữ liệu thƣờng tiêu tốn thời gian và phức tạp nhất của qui trình, tuy nhiên các
bƣớc tiền xử lý và hậu xử lý cũng không đơn giản và có thể tiêu tốn nhiều
thời gian hơn so với các thuật toán khai thác dữ liệu.
Chúng tôi thực hiện hầu hết các bƣớc trên hình 1.1 trong việc tìm kiếm
các phần tử ngoại lai DB.Một số bƣớc tiền xử lý liên quan đến việc tìm các


Hình 1.1 Qui trình KDD Knowledgement Discovery in Database –
Khám phá tri thức trong Cơ sở dữ liệu.
KNOWLEDGE
Đánh Giá và Biểu Diễn
Các Mẫu Trích Chọn
Khai thác Dữ Liệu
Trích Chọn và Biến Đổi
Dữ Liệu
Làm Sạch và Tích Hợp
Dữ Liệu
Các Cơ Sở Dữ Liệu
Các File Bằng
14

1.2 Các ứng dụng sử dụng kỹ thuật khai thác dữ liệu.
Có rất nhiều ứng dụng trong các lĩnh vực khác nhau sử dụng các kỹ
thuật khai thác dữ liệu nhằm hỗ trợ cho mục đích sử dụng. Ví dụ: Trong
thƣơng mại, một công ty hay một tổ chức sử dụng các kỹ thuật khai thác dữ
liệu để tặng khuyến mãi cho các khách hàng dựa vào tần suất truy cập
website, kiểu khách hàng, số lƣợng hàng đã mua ở các lần trƣớc. Trong ngân

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 .”[20]. Nói khác đi, 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à các phần tử ngoại lai.
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:
Nằm trong một phân bố khác với phân bố của tập dữ liệu
còn lại.
Là một đối tƣợng có giá trị hợp lệ nhƣng không phải là đối
tƣợng mong muốn.
Là đối tƣợng dữ liệu đƣợc tạo sinh có sai sót.
Đối với trƣờng hợp các phần tử ngoại lai có thể là các đối tƣợng hợp lệ
nhƣng chúng có giá trị không mong muốn, ta không cần thiết phải loại bỏ
chúng khỏi tập dữ liệu nhƣng các đối tƣợng này phải đƣợc xác định hay nhận
dạng .Draper và Smith nhận xét rằng một phần tử ngoại lai có thể “ cung cấp
thông tin mà đối tƣợng khác không thể bởi vì nó xuất hiện từ sự kết hợp bất
bình thƣờng của một số trƣờng hợp rất có ý nghĩa”[13].
Nếu một phần tử ngoại lai không phải là một đối tƣợng hợp lệ ( có thể
là do nó đƣợc đánh giá và đƣa vào không đúng ) thì nó có thể đƣợc phát hiện,
16

khắc phục và đánh giá bởi các chuyên gia. Do đó, phụ thuộc vào từng ngữ
cảnh các phần tử ngoại lai có thể đƣợc loại bỏ từ tập dữ liệu để làm tăng tính
thuần nhất của dữ liệu còn lại.
Nói tóm lại, các phần tử ngoại lai là những đối tƣợng đủ khác với hầu
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 là các
điểm không thỏa mãn mô hình dữ liệu đang xét. Việc phần tử ngoại lai có bị
loại bỏ hay không còn tùy thuộc vào từng chƣơng trình ứng dụng và quyết
định bởi chuyên gia.
Một cách hình thức ngƣời ta có thể định nghĩa phần tử ngoại lai của

cho hƣớng tiếp cận này là các tác giả Barnett, Lewis.
- Xác định theo độ khác biệt (Deviation-Based):
18

Hƣớng nghiên cứu này dựa trên việc xác định 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, Raghavan.
Các phƣơng pháp nghiên cứu trên hiệu quả khi áp dụng trong lĩnh vực
Data mining ( nghiên cứu phát hiện các tri thức, các luật trong một tập các
phần tử dữ liệu). Tuy nhiên chúng khó áp dụng, hoặc không hiệu quả trong
các trƣờng hợp đối với các dữ liệu của cơ sở dữ liệu dạng quan hệ trong đó có
nhiều thuộc tính vừa là số vừa là định danh, hoặc trong trƣờng hợp khi chúng
ta quan tâm nhiều đến sự vi phạm của các phần tử dữ liệu đối với một tập các
ràng buộc, quy tắc (luật) đƣợc cho trƣớc. Ở đây chúng tôi đề xuất việc phát
hiện các phần tử ngoại lai trong CSDL quan hệ dựa theo các luật (Rule-Base).
Hƣớng tiếp cận này giúp khắc phục đƣợc những hạn chế của các hƣớng
nghiên cứu trƣớc đồng thời có thể mang lại hiệu quả hơn trong việc phát hiện
những phần tử ngoại lai trong CSDL quan hệ.
1.4 Mối quan hệ giữa các phần tử ngoại lai và khai thác dữ liệu.
Trƣớc khi các kỹ thuật khai thác dữ liệu ra đời, thông tin hữu ích chỉ
đƣợc khai thác hiệu quả trên các tập dữ liệu với cỡ và số chiều dữ liệu là nhỏ.
Do đó, để có thể khai thác dữ liệu một cách hiệu quả với khối lƣợng thông tin
lớn thì cần thiết phải có các công cụ khai thác dữ liệu tốt, các thuật toán khai
thác dữ liệu tự động, thời gian thực hiện nhanh. Trong thực tế các chƣơng
trình ứng dụng khai thác dữ liệu thƣờng phải khai thác dữ liệu trên các tập lớn
dữ liệu rất lớn không phù hợp với bộ nhớ chính.
Dữ liệu đó đƣợc gọi là dữ liệu nằm trong bộ nhớ ngoài(Disk-resident
Data ).
19

hình theo đăng nhập, sử dụng CPU và truy xuất dữ liệu ).
Đối với các hệ thống thanh toán điện tử bao gồm các ứng dụng thẻ tín
dụng, thẻ điện thoại và thẻ thông minh, chúng ta quan tâm tới việc phát hiện
thẻ giả.
Một ứng dụng nữa của việc phát hiện phần tử ngoại lai là nghiên cứu cổ
phiếu. Các công ty và các cá nhân đã từng thử dự đoán giá trị các cổ phiếu
đƣợc niêm yết. Giả sử phần lớn giá các cổ phiếu ở một ngành.
21

CHƢƠNG II: CÁC ĐỊNH NGHĨA, THUẬT TOÁN TÌM KIẾM CÁC
PHẦN TỬ NGOẠI LAI.
Trong chƣơng này sẽ trình bầy các định nghĩa, khái niệm và thuật ngữ
các phần tử ngoại lai trong cơ sở dữ liệu theo cách nhìn toàn cục. Đồng thời
giới thiệu các thuật toán, độ phức tạp của các thuật toán, trình bày thực
nghiệm của Knorr[24] để đánh giá và so sánh thời gian thực hiện của các
thuật toán.
2.1 Các định nghĩa và thuật ngữ các phần tử ngoại lai.
Định nghĩa các phần tử ngoại lai dựa trên khoảng cách.
Cho N là số lƣợng các đối tƣợng trong tập dữ liệu T. Gọi d là
hàm khoảng cách giữa một cặp đối tƣợng bất kỳ trong tập dữ liệu. Với
một đối tƣợng O, gọi S(o) là tập các lân cận của O bao gồm tất cả các

2
là phần tử ngoại lai -3, thì
t
1
mạnh hơn t
2
. Chúng ta chỉ cần xét 2 thuộc tính trƣớc khi quan sát
xem t
1
có đủ xa so với các điểm khác trong tập dữ liệu, ngƣợc lại chúng
ta xét 3 thuộc tính để kết luận tƣơng tự về t
2
. Một đồ thị 2-D của tất cả
các điểm trong tập dữ liệu T đã chỉ ra t
1
đủ xa hơn t
2
từ vùng dữ liệu.
Đặc biệt, nó sử dụng ít thuộc tính hơn để giải thích tại sao t
1
là phần tử
ngoại lai.
Nhƣợc điểm của khái niệm này là ở 3-D, t
2
có thể thực sự xa hơn
t
1
từ vùng dữ liệu, vì thế, ở 3-D t
2
là phần tử ngoại lai mạnh hơn.

có thể chỉ lớn hơn khoảng cách D đối với tất cả a tổ hợp của nó. Biện pháp
khắc phục nhƣợc điểm này là ngƣời dùng lấy một giá trị D lớn hơn của nó sẽ
loại trừ t
1
không còn là phần tử ngoại lai.
(3) Giả sử t
1
và t
2
đều là phần tử ngoại lai –j. Và giả sử ít nhất tỉ lệ p1
của các đối tƣợng trong T lớn hơn khoảng cách D từ t
1
và ít nhất tỉ lệ p
2
của
các đối tƣợng trong T phải lớn hơn khoảng cách D từ t
2
, với p
1
> p
2
p. Thì
chúng ta nói rằng t
1
là phần tử ngoại lai mạnh hơn t
2
.
Khái niệm này đã nhấn mạnh đến số đối tƣợng trong lân cận D. Các
phần tử ngoại lai có ít số đối tƣợng hơn trong các lân cận D của chúng đƣợc
xem là các phần tử ngoại lai mạnh hơn. Tất nhiên, nếu ngƣời dùng tăng đủ giá

Khái niệm này đã sắp xếp thứ tự một nhóm các phần tử ngoại lai dựa
trên khoảng cách của từng phần tử ngoại lai đến một số điểm trong T. Tất
nhiên, nếu ngƣời dùng tăng đủ giá trị của D, thì t
2
sẽ không còn là một phần
tử ngoại lai nữa
( nhƣng t
1
sẽ vẫn là phần tử ngoại lai).
24

Cho một đối tƣợng P đã đƣợc xác định là ngoại lai trong không gian
thuộc tính Ap, 2 thành phần của tri thức sẽ đƣợc quan tâm là:
1. Tập các thuộc tính nhỏ nhất là gì để giải thích tại sao P là ngoại
lai ?
2. P có “nổi trội” hơn các phần tử ngoại lai khác không ?
Câu hỏi (1) chỉ tập trung vào P. Không gian đã cho Ap, chúng tôi tìm
tất cả các tập con các thuộc tính tối thiểu mà ở đó P là ngoại lai. Câu hỏi (2)
quan tâm đến việc đánh giá P đối với các phần tử ngoại lai khác. Cụ thể
chúng tôi tìm các tập thuộc tính tối thiểu ở đó có một phần tử ngoại lai – phần
tử bất kỳ, là P, Q,…
Định nghĩa 3: Một không gian –j là một trong bất kỳ tổ hợp của j
thuộc tính ở k chiều.
Định nghĩa 4: Không gian –As là kí hiệu một không gian cho tập As
duy nhất của ít nhất một thuộc tính trong k thuộc tính. Hạng hoặc số chiều của
không gian – As là .
Có 2
k
-1 không gian con không rỗng có thể của k thuộc tính. Vì thế nếu
k=3 thì có 7 không gian con duy nhất: 3 trong 1-D, 3 trong 2-D, 3 trong 3-D.

với A
Si
đƣợc hiểu
là duy nhất. Nhớ rằng mỗi không gian – A
Si
là một không gian . P là một
phần tử ngoại lai –j nếu P là phần tử ngoại lai trong không gian A
p
với =
j.
25

Ta quan tâm đến giá trị j nhỏ nhất để P là phần tử ngoại lai. Trừ khi
trong ngữ cảnh yêu cầu, nếu không chúng ta coi đó là giá trị tối thiểu của j để
P là phần tử ngoại lai, khi sử dụng thuật ngữ phần tử ngoại lai –j. Lý do duy
nhất là j thuộc tính dùng để chỉ ra rằng P là phần tử ngoại lai. Nói cách khác
đây là cách đơn giản nhất để giải thích tại sao P đƣợc phân loại là phần tử
ngoại lai DB. Chúng tôi sử dụng thuật ngữ A
p
, bởi vì A
p
tham chiếu tới một
tập j thuộc tính đang sử dụng. Chú ý rằng P có thể là phần tử ngoại lai –j với
hơn một không gian –j.
Chúng ta phân biệt phần tử ngoại lai phổ biến và các phần tử ngoại lai
có cấu trúc. Các phần tử ngoại lai phổ biến là các phần tử ngoại lai -1, các
phần tử ngoại lai có cấu trúc là các phần tử ngoại lai –j (j 2).
Chúng ta phân biệt giữa các không gian thông thƣờng và không thông
thƣờng.
Với không gian không thông thƣờng: Phân biệt giữa các không gian