i
MỤC LỤC
DANH MỤC CÁC HÌNH ẢNH ............................................................................ iii
DANH MỤC BẢNG BIỂU ..................................................................................... v
DANH MỤC CÁC TỪ VIẾT TẮT......................................................................... vi
MỞ ĐẦU ................................................................................................................ 1
CHƯƠNG 1
1.1
KHAI PHÁ DỮ LIỆU VÀ CẤU TRÚC CÂY DỮ LIỆU ............... 5
Khai phá dữ liệu ........................................................................................ 5
1.1.1
Tại sao lại cần khai phá dữ liệu .......................................................... 5
1.1.2
Khai phá dữ liệu là gì? ....................................................................... 5
1.1.3
Các chức năng chính của khai phá dữ liệu .......................................... 7
1.1.4
Các công cụ khai phá dữ liệu ............................................................. 8
1.1.5
Các kỹ thuật khai phá dữ liệu ............................................................. 8
1.1.6
Ứng dụng của khai phá dữ liệu ......................................................... 13
1.2
Cấu trúc cây dữ liệu ................................................................................ 13
1.2.1
Các loại cây ..................................................................................... 13
1.2.2
Các cách biểu diễn cây cấu trúc dữ liệu ............................................ 18
1.3
Dạng chuẩn của cây dữ liệu ..................................................................... 19
1.3.1
Dạng chuẩn chính tắc theo chiều rộng (BFCF) ................................. 19
1.3.2
Dạng chính tắc theo chiều sâu DFCF ............................................... 24
1.3.3
Cây liệt kê ........................................................................................ 29
1.4
Kết luận chương 1 ................................................................................... 33
CHƯƠNG 2
2.1
PHÁT HIỆN CÁC CÂY CON PHỔ BIẾN ................................... 34
Khai phá cây con phổ biến ...................................................................... 34
2.1.1
Cây con phổ biến ............................................................................. 34
2.1.2
Bài toán khai phá các cây con phổ biến ............................................ 35
ii
2.2
Thuật toán khai phá các cây con phổ biến trong cơ sở dữ liệu cây dữ liệu.... 36
2.2.1
Thuật toán khai phá các cây con phổ biến DTMiner. ........................ 36
2.2.2
Thuật toán khai phá cây con phổ biến đóng và cực đại ..................... 39
2.2.3
Thứ tự tính toán - Heuristic .............................................................. 48
2.2.4
Thuật toán khai phá các cây con phổ biến đóng và cực đại
CMT_Miner(D, minsup) ................................................................................ 50
2.2.5
Thuật toán khai phá các cây conphổ biến đóng và cực
đạiNCMT_Miner(D, minsup) ........................................................................ 52
2.3
Kết luận chương 2 ................................................................................... 55
CHƯƠNG 3
3.1
CHƯƠNG TRÌNH THỬ NGHIỆM .............................................. 56
Ứng dụng phát hiện cấu trúc chức năng của protein trong tin sinh học .... 56
3.1.1
Phân tích trình tự.............................................................................. 57
3.1.2
Dò tìm đột biến và SNP ................................................................... 57
3.1.3
Phân tích chức năng gene ................................................................. 57
3.1.4
Nhận diện protein............................................................................. 58
3.1.5
Dự đoán cấu trúc protein .................................................................. 58
3.2
Chương trình thử nghiệm ........................................................................ 59
3.2.1
Môi trường thử nghiệm .................................................................... 59
3.2.2
Kết quả thực nghiệm ........................................................................ 59
3.2.3
So sánh kết quả thực nghiệm ............................................................ 67
3.3
Kết luận chương 3 ................................................................................... 68
KẾT LUẬN ........................................................................................................... 69
TÀI LIỆU THAM KHẢO ..................................................................................... 70
iii
DANH MỤC CÁC HÌNH ẢNH
Hình 1-1 Các bước trong Khai phá dữ liệu & KDD [6]............................................ 7
Hình 1-2 Luồng thông tin được sử dụng theo cách kết hợp[1] ................................. 9
Hình 1-3 Phân cụm [6] .......................................................................................... 10
Hình 1-4 Cây quyết định [6] .................................................................................. 12
Hình 1-5 Tám cây có thứ tự nhận được từ một cây không có thứ tự ....................... 15
Hình 1-6 Cây tìm kiếm nhị phân với tập khóa là các số nguyên ............................. 16
Hình 1-7 Cây t’ ở dạng chính tắc DFCF ................................................................ 29
Hình 1-8 Cây liệt kê các cây con phổ biến ............................................................. 33
Hình 2-1 Chuẩn hóa và đánh số các cây giao tác ................................................... 36
Hình 2-2 CSDL gồm 3 cây giao tác ....................................................................... 41
Hình 2-3 (a) Đồ thị định hướng phi chu trình liệt kê DAG, (b) Cây liệt kê .............. 42
Hình 2-4 Cây t và các cây t rên a), b), c), d) trong lớp phủ Bt ................................ 43
Hình 2-5 a) Cây trước khi tỉa
b) Cây sau khi tỉa ............................................. 44
Hình 2-6 a) Đường đi phải nhất, b) Lớp phủ trái/phải ............................................ 45
Hình 2-7 Vị trí của đỉnh mới có thể được thêm vào một cây con phổ biến t ........... 46
Hình 3-1 Cây không có thứ tự T1, T2,T3 .................................................................. 59
Hình 3-2 Chính tắc hóa cây T1 ............................................................................... 60
Hình 3-3 Chính tắc hóa cây T2 ............................................................................... 60
Hình 3-4 Chính tắc hóa cây T3 ............................................................................... 60
Hình 3-5 Tập chuỗi mã hóa cây chính tắc T1 ......................................................... 61
Hình 3-6 Tập chuỗi mã hóa cây chính tắc T2 ......................................................... 61
Hình 3-7 Tập chuỗi mã hóa cây chính tắc T3 ......................................................... 61
Hình 3-8 Tập các cây con phổ biến đóng cực đại của tập CSDL T1 ....................... 62
Hình 3-9 Tập các cây con phổ biến đóng cực đại của tập CSDL T1, T2 .................. 62
iv
Hình 3-10 Tập các cây con phổ biến đóng cực đại của tập CSDL T1, T2, T3 ........... 63
Hình 3-11 Chính tắc hóa cây T1 ............................................................................. 63
Hình 3-12 Chính tắc hóa cây T2 ............................................................................. 64
Hình 3-13 Chính tắc hóa cây T3 ............................................................................. 64
Hình 3-14 Tập chuỗi mã hóa cây chính tắc T1 ....................................................... 64
Hình 3-15 Tập chuỗi mã hóa cây chính tắc T2 ....................................................... 65
Hình 3-16 Tập chuỗi mã hóa cây chính tắc T3 ....................................................... 65
Hình 3-17 Tập các cây con phổ biến đóng cực đại của tập CSDL T1...................... 65
Hình 3-18 Tập các cây con phổ biến đóng cực đại của tập CSDL T1, T2 ................ 66
Hình 3-19 Tập các cây con phổ biến đóng cực đại của tập CSDL T1, T2, T3 ........... 66
Hình 3-20 So sánh số lượng cây con phổ biến đóng cực đại của 2 thuật toán ......... 67
v
DANH MỤC BẢNG BIỂU
Bảng 3.1 Cấu hình phần cứng sử dụng trong thực nghiệm ..................................... 59
Bảng 3.2 Công cụ phần mềm sử dụng trong thực nghiệm ...................................... 59
vi
DANH MỤC CÁC TỪ VIẾT TẮT
Thuật ngữ
Viết tắt
Ý nghĩa
Depth-first search
DFS
Tìm kiếm theo chiều sâu
Breadth-first search
BFS
Tìm kiếm theo chiều rộng
Breadth-Frist String Encoding
BFSE
Mã chuỗi theo chiều rộng
Breadth-First Canonical String
BFCS
Chuỗi chuẩn theo chiều rộng
Breadth-First Canonical Form
BFCF
Dạng chuẩn theo chiều rộng
Depth-First String Encoding
DFSE
Mã chuỗi theo chiều sâu
Depth-First Canonical Form
DFCF
Dạng chuẩn theo chiều sâu
Directed Acyclic Graph
DAG
Đồ thị định hướng
phichu trình
Partially Ordered set
POSET
Tập thứ tự bộ phận
Frequent Subgraphs Mining
FSM
Khai phá đồ thị con phổ biến
Inductive Logic Programming
ILP
Chương trình Logic qui nạp
eXtensible Markup Language
XML
Ngôn ngữ đánh dấu Mở rộng
1
MỞ ĐẦU
1. Đặt vấn đề
Cùng với sự phát triển của xã hội, con người đã tạo ra những thiết bị xử lý dữ
liệu thông minh đáp ứng nhu cầu của họ. Thế hệ máy tính đầu tiên xuất hiện vào
những thập kỉ đầu của thế kỉ 20, đó là những cỗ máy với kích thước khổng lồ có khi
bằng cả gian phòng lớn và tiêu thụ rất nhiều điện năng. Tuy nhiên do nhu cầu xử lý
dữ liệu ngày càng lớn, con người đã sáng tạo và cải tiến các thế hệ máy tính trở nên
gọn nhẹ với những chiếc máy tính xách tay chỉ nặng vài kilogam và tiêu thụ rất ít
điện năng đã đáp ứng được hầu hết các yêu cầu của con người trong việc xử lí khối
dữ liệu lớn và phức tạp.
Đồng hành với sự phát triển của thông tin và công nghệ, khai phá dữ liệu ra
đời mở ra một hướng đi mới để giải quyết những yêu cầu về xử lý khối dữ liệu
khổng lồ. Hướng đi này đã được ứng dụng vào rất nhiều lĩnh vực, ví dụ như: tin
sinh học, điều trị y học, phân tích dữ liệu và hỗ trợ ra quyết định, tài chính và thị
trường chứng khoán, bảo hiểm, nhân dạng… Đặc biệt, khi nghiên cứu về tin sinh
học ta thấy công nghệ thông tin cũng là một công cụ quan trọng góp phần hỗ trợ
trong công tác nghiên cứu và phát triển ngành công nghệ sinh học nói chung và sinh
học nói riêng. Điển hình đó là ứng dụng phát hiện cấu trúc chức năng của protein
trong tin sinh. Bên cạnh đó ta thấy được rằng, khai phá dữ liệu đồ thị là một kĩ thuật
được dùng để phát hiện tri thức và đặc biệt thích hợp với dữ liệu có cấu trúc vì có thể
sử dụng đồ thị để mô tả.
Đồ thị được sử dụng rộng rãi trong việc biểu diễn dữ liệu và mối quan hệ
giữa chúng. Trong tất cả các đồ thị, một lớp con đã rất quen thuộc với nhiều người,
đó các cây, cây được ứng dụng trong nhiều lĩnh vực khác nhau, như trong lĩnh vực
CSDL: các tài liệu XML sử dụng cấu trúc cây để các phần tử-phần tử con và các
mối quan hệ giữa thuộc tính - giá trị. Trong khai phá truy cập Web: cây truy cập
được sử dụng để biểu diễn các mẫu truy cập của những khách hàng khác nhau.
2
Trong phân tích sự tiến hóa của các phân tử: cây tiến hóa được sử dụng để mô tả
lịch sử tiến hóa của các loài; trong mạng máy tính, cây được sử dụng để xác định
định tuyến của các gói tin. Trong tin sinh học: cây con phổ biến sử dụng để dự đoán
mối quan hệ tương tác giữa các protein, dự đoán cấu trúc bậc 2 phân tử của protein,
dò tìm đột biến trong cấu trúc protein v.v … Từ những ứng dụng nêu trên, ta thấy
cây trong các ứng dụng thực tế thường là cây được gắn nhãn vào các đỉnh, nhưng
nhãn của các cạnh không cần thiết phải duy nhất – điều này phản ánh đúng thực tế.
Và việc xác định được các cấu trúc con phổ biến của tập dữ liệu sẽ hỗ trợ để hiểu và
giúp nghiên cứu sâu, chi tiết hơn về dữ liệu đó.
Chính vì vậy, để thực hiện khai phá dữ liệu cây, bài toán cơ bản là phát hiện
các cây con thường xuyên và được giải quyết bằng các phương pháp liệt kê vét cạn.
Số các cây liệt kê được sinh ra thường rất lớn, khá tốn kém trong lưu trữ và thời
gian xử lý. Bởi vậy, học viên tiếp cận vấn đề theo hướng chỉ quan tâm đến những
cây con phổ biến, và ở mỗi mức chỉ cần lưu lại những cây con phổ biến thỏa mãn
điều kiện đặt ra để phát triển tiếp các cây con ở mức tiếp theo. Bài toán khai phá các
cây phổ biến là tìm tất cả những cây con liên thông phổ biến trong một cơ sở dữ liệu
các cây. Điều cốt lõi của thuật toán khai thác cây con phổ biến là:
-
Xác định những cây con đẳng cấu: một cây có phải là một cây con của cây
khác hay không?
-
Xây dựng một lược đồ liệt kê hiệu quả tất cả các cây con phổ biến.
Với những lý do trên nên học viên chọn đề tài "Khai phá dữ liệu đồ thị (cây
dữ liệu), phát hiện các cây con phổ biến ".
2. Đối tượng và phạm vi nghiên cứu
Trong phạm vi luận văn, học viên tập trung nghiên cứu các cây con phổ biến
đóng và cực đại, các thuộc tính và mối quan hệ giữa chúng. Trước tiên, để làm tiền
đề cho nghiên cứu, học viên tìm hiểu về cấu trúc cây dữ liệu, các dạng chính tắc
theo chiều sâu DFCF, chiều rộng BFCF cũng như các dạng chuẩn hóa theo chiều
sâu DFSE và chiểu rồng BFSE. Sau đó, trình bày thuật toán khai phá tất cả các cây
con phổ biến đóng và cực đại trong kho các cây dữ liệu đã được gán nhãn không có
3
thứ tự, sử dụng cấu trúc cây liệt kê DAG, lớp phủ và các kỹ thuật cắt tỉa cây. Học
viên đi sâu nghiên cứu thuật toán CMT_Miner xác định cây con phổ biến đóng cực
đại, do số lượng các cây con thường xuyên tăng theo hàm mũ của kích cỡ của cây
con, vì vậy, khai phá tất cả các cây con thường xuyên là không khả thi đối với
những cây dữ liệu cỡ lớn. Thuật toán CMT_Miner rất hiệu quả trong việc phát hiện
những cây con thường xuyên cực đại và đóng trong CSDL các cây con được gắn
nhãn. Thuật toán này tìm các cây con thường xuyên cực đại và đóng theo cách
duyệt cây liệt kê để xác định tất cả cây con thường xuyên. Có một số kỹ thuật được
sử dụng để tỉa những nhánh của cây liệt kê mà nó không phải là cây con thường
xuyên cực đại hoặc đóng, trong đó phương pháp Heuristic được áp dụng để tổ chức
tính toán và xác định cây con thường xuyên hiệu quả nhất có thể. Thông qua kết quả
thực nghiệm trên những tập dữ liệu thực tế cho thấy rằng thuật toán này khá hiệu
quả trong việc giảm thiểu không gian tìm kiếm và nhanh chóng phát hiện các cây
con thường xuyên cực đại và đóng. Bên cạnh đó, học viêncũng đề cập đến thuật
toán NCMT_Miner nhằm mục đích kiểm nghiệm, so sánh, đánh giá lại kết quả thuật
toán CMT_Miner. Ngoài ra, học viên cũng tìm hiểu về lĩnh vực tin sinh học, khả
năng ứng dụng của khai phá cây con phổ biến trong các bài toán của lĩnh vực này.
3. Hướng nghiên cứu
+ Tìm hiểu về khai phá dữ liệu, dữ liệu dạng cây. Nghiên cứu các dạng biểu
diễn chuẩn tắc dữ liệu dạng cây. Nghiên cứu ứng dụng phát hiện cấu trúc chức năng
của protein trong tin sinh.
+ Thuật toán phát hiện cây con phổ biến. Ứng dụng cài đặt thực nghiệm
thuật toán.
4. Phương pháp nghiên cứu
Phương pháp nghiên cứu lý thuyết: Nghiên cứu lý thuyết về khai phá dữ
liệu. Lý thuyết về đồ thị, cấu trúc dữ liệu dạng cây. Thuật toán để phát hiện cây con
phổ biến đóng và cực đại.
Phương pháp nghiên cứu thực nghiệm: Sử dụng ngôn ngữ lập trình để cài
đặt chương trình thực nghiệm.
4
Phương pháp trao đổi khoa học: Trao đổi nội dung, hướng phát triển của đề
tài với giáo viên hướng dẫn để đề xuất và giải quyết các vấn đề mà luận văn đặt ra.
5. Ý nghĩa khoa học của đề tài
+ Đề ra các hướng biểu diễn chuẩn tắc dữ liệu dạng cây.
+ Đề xuất thuật toán phát hiện cây con phổ biến đóng và cực đại.
+ Kết quả nghiên cứu giúp xác định cây con phổ biến đóng và cực đại mà
không cần phải phát triển cây hoàn chỉnh.
5
CHƯƠNG 1
KHAI PHÁ DỮ LIỆU VÀ CẤU TRÚC CÂY
DỮ LIỆU
Nội dung chương sẽ giới thiệu khái niệm về khai phá dữ liệu, tiến trình khai
phá dữ liệu, các kĩ thuật khai phá dữ liệu, các phương pháp khai phá dữ liệu thông
dụng, những thách thức gặp phải trong quá trình khai phá dữ liệu và giới thiệu một
số công cụ hỗ trợ trong khai phá dữ liệu.
1.1 Khai phá dữ liệu
1.1.1 Tại sao lại cần khai phá dữliệu
Theo [1] khoảng hơn một thập kỷtrởlại đây, lượng thông tin được lưu trữtrên
các thiết bị điện tử(đĩa cứng, CD-ROM, băng từ, .v.v.) không ngừng tăng lên.
Người ta ước đoán rằng lượng thông tin trên toàn cầu tăng gấp đôi sau khoảng hai
năm và theo đó sốlượng cũng nhưkích cỡcủa các cơsởdữliệu (CSDL) cũng tăng lên
một cách nhanh chóng.
Khai phá dữ liệu ra đời nhưmột hướng giải quyết hữu hiệu cho câu hỏi vừa
đặt ra ở trên. Khá nhiều định nghĩa vềkhai phá dữ liệu, tuy nhiên có thểhiểu đơn
giản rằng khai phá dữ liệu nhưlà một công nghệtri thứcgiúp khai thác những thông
tin hữu ích từnhững kho dữliệu được tích trữtrong suốt quá trình hoạt động của một
công ty, tổchức nào đó.
1.1.2 Khai phá dữliệu là gì?
Thuật ngữkhai phá dữ liệu ám chỉviệc tìm kiếm một tập hợp nhỏcó giá
trịtừmột sốlượng lớn các dữ liệu thô. Có nhiều thuật ngữhiện được dùng cũng có
nghĩa tương tựvớiKhai phá dữ liệu (Data Mining) nhưKhai phá tri thức (Knowledge
Mining), Chắt lọc tri thức (knowledge extraction), Phân tích dữliệu/mẫu
(data/patern analysis), Khảo cổ dữ liệu (data archaeoloogy), Nạo vét dữ liệu
(datadredging),... [6]
Định nghĩa 1.1Khai phá dữ liệu là một tập hợp các kỹthuật được sửdụng đểtựđộng
khai thác và tìm ra các mối quan hệlẫn nhau của dữ liệu trong một tập hợp dữliệu
6
khổng lồvà phức tạp, đồng thời cũng tìm ra các mẫu tiềm ẩn trong tập dữ liệu
đó.[2]
Khai phá dữ liệu là một bước trong bảy bước của quá trình KDD (Knowleadge
Discovery in Database) và KDD được xem như7 quá trình khác nhau theo thứtự
sau:
1. Làm sạch dữ liệu (data cleaning & preprocessing)s: Loại bỏnhiễu và các
dữliệu không cần thiết.
2. Tích hợp dữ liệu: (data integration): quá trình hợp nhất dữ liệu thành những
kho dữ liệu (data warehouses & data marts) sau khi đã làm sạch và tiền xửlý (data
cleaning & preprocessing).
3. Trích chọn dữ liệu (data selection): trích chọn dữ liệu từnhững kho dữ liệu và
sau đó chuyển đổi vềdạng thích hợp cho quá trình khai thác tri thức.
4. Chuyển đổi dữ liệu: Các dữ liệu được chuyển đổi sang các dạng phù hợp cho
quá trình xửlý
5. Khai phá dữ liệu (khai phá dữ liệu): Là một trong các bước quan trọng nhất,
trong đó sửdụng những phương pháp thông minh đểchắt lọc ra những mẫu dữ liệu.
6. Ước lượng mẫu (knowledge evaluation): Quá trình đánh giá các kết quảtìm
được thông qua các độ đo nào đó.
7. Biểu diễn tri thức (knowledge presentation): Quá trình này sửdụng các kỹthuật
đểbiểu diễn và thểhiện trực quan cho người dùng.
7
Hình 1-1Các bước trong Khai phá dữ liệu& KDD[6]
1.1.3 Các chức năng chính của khai phá dữ liệu
Khai phá dữ liệu được chia nhỏthành một sốhướng chính nhưsau:
Mô tảkhái niệm (concept description): thiên vềmô tả, tổng hợp và tóm tắt khái
niệm. Ví dụ: tóm tắt văn bản.
Luật kết hợp (association rules): là dạng luật biểu diễn tri thứ ởdạng khá đơn
giản. Ví dụ: “60 % nam giới vào siêu thịnếu mua bia thì có tới 80% trong
sốhọsẽmua thêm thịt bò khô”. Luật kết hợp được ứng dụng nhiều trong lĩnh vực
kinh doanh, y học, tin-sinh, tài chính & thịtrường chứng khoán, .v.v.
Phân lớp và dự đoán (classification & prediction): xếp một đối tượng vào một
trong những lớp đã biết trước. Ví dụ: phân lớp vùng địa lý theo dữ liệu thời tiết.
Hướng tiếp cận này thường sử dụng một sốkỹthuật của machine learningnhưcây
quyết định (decision tree), mạng nơron nhân tạo (neural network), .v.v. Người ta
còn gọi phân lớplà học có giám sát (học có thầy).
Phân cụm (clustering): xếp các đối tượng theo từng cụm (sốlượng cũng nhưtên
của cụm chưa được biết trước. Người ta còn gọi phân cụmlà học không giám sát
(học không thầy).
8
Khai phá chuỗi (sequential/temporal patterns): tương tựnhưkhai phá luật kết hợp
nhưng có thêm tính thứtựvà tính thời gian. Hướng tiếp cận này được ứng dụng
nhiều trong lĩnh vực tài chính và thịtrường chứng khoán vì nócó tính dựbáo cao.
1.1.4 Các công cụ khai phá dữ liệu
Khai phá dữ liệu không phải là tất cả về các công cụ hay phần mềm cơ sở dữ
liệu đang sử dụng. Có thể thực hiện khai phá dữ liệu bằng các hệ thống cơ sở dữ
liệu bình thường và các công cụ đơn giản, bao gồm việc tạo và viết phần mềm riêng
hoặc sử dụng các gói phần mềm thương mại. Khai phá dữ liệu phức tạp được hưởng
lợi từ kinh nghiệm trong quá khứ và các thuật toán đã định nghĩa với phần mềm và
các gói phần mềm hiện có, với các công cụ nhất định để thu được một mối quan hệ
hoặc uy tín lớn hơn bằng các kỹ thuật khác nhau. [3]
Gần đây các tập hợp dữ liệu rất lớn và việc xử lý dữ liệu theo cụm và quy mô
lớn có thể cho phép khai phá dữ liệu để sắp xếp và lập báo cáo về các nhóm và các
mối tương quan của dữ liệu phức tạp hơn. Bây giờ đã có sẵn rất nhiều công cụ và hệ
thống hoàn toàn mới, gồm các hệ thống lưu trữ và xử lý dữ liệu kết hợp.
1.1.5 Các kỹ thuật khai phá dữ liệu
Một số kỹ thuật cốt lõi, được sử dụng trong khai phá dữ liệu, mô tả kiểu hoạt động
khai phá và hoạt động phục hồi dữ liệu [6].
1.1.5.1Khai phá luật kết hợp
Khai phá luật kết hợp (mối quan hệ) là kỹ thuật khai phá dữ liệu được biết đến
nhiều hơn vì tính quen thuộc và đơn giản. Ở đây, thực hiện một sự tương quan đơn
giản giữa hai hoặc nhiều mục, thường cùng kiểu để nhận biết các mẫu.Việc xây
dựng các công cụ khai phá dữ liệu dựa trên sự kết hợp hay mối quan hệ có thể thực
hiện đơn giản bằng các công cụ khác nhau.
Ví dụ 1-1: Hình 1-2 cho thấy của cơ sở dữ liệu ví dụ mẫu [9]
9
Hình 1-2 Luồng thông tin được sử dụng theo cách kết hợp[1]
1.1.5.2Phân lớp
Kỹ thuật phân lớpdùng để xây dựng một ý tưởng về kiểu khách hàng, kiểu mặt
hàng hoặc kiểu đối tượng bằng cách mô tả nhiều thuộc tính để nhận biết một lớp cụ
thể. Ví dụ, bạn có thể dễ dàng phân loại các xe ô tô thành các kiểu xe khác nhau (xe
mui kín, 4x4, xe có thể bỏ mui) bằng cách xác định các thuộc tính khác nhau (số
chỗ ngồi, hình dạng xe, các bánh xe điều khiển). Với một chiếc xe mới, bạn có thể
đặt nó vào một lớp cụ thể bằng cách so sánh các thuộc tính với định nghĩa đã biết
của chúng tôi. Bạn có thể áp dụng các nguyên tắc tương tự ấy cho các khách hàng,
ví dụ bằng cách phân loại khách hàng theo độ tuổi và nhóm xã hội.
Hơn nữa, bạn có thể sử dụng việc phân loại như một nguồn cấp, hoặc như là
kết quả của các kỹ thuật khác. Ví dụ, bạn có thể sử dụng các cây quyết định để xác
định một cách phân loại. Việc phân cụm sẽ cho phép bạn sử dụng các thuộc tính
chung theo các cách phân loại khác nhau để nhận biết các cụm. [8]
10
1.1.5.3Phân cụm
Bằng cách xem xét một hay nhiều thuộc tính hoặc các lớp, có thể nhóm các
phần dữ liệu riêng lẻ với nhau để tạo thành một quan điểm cấu trúc. Ở mức đơn
giản, việc phân cụm đang sử dụng một hoặc nhiều thuộc tính làm cơ sở cho bạn để
nhận ra một nhóm các kết quả tương quan. Việc phân cụm giúp để nhận biết các
thông tin khác nhau vì nó tương quan với các ví dụ khác, nên có thể thấy ở đâu có
những điểm tương đồng và các phạm vi phù hợp.
Việc phân cụm có thể làm theo hai cách. Có thể giả sử rằng có một cụm ở một
điểm nhất định và sau đó sử dụng các tiêu chí nhận dạng để xem liệu có đúng
không. Đồ thị trong Hình 1-3 là một ví dụ. Một ví dụ mẫu về dữ liệu kinh doanh so
sánh tuổi của khách hàng với quy mô bán hàng. Hợp lý khi thấy rằng những người
ở độ tuổi hai mươi (trước khi kết hôn và còn nhỏ), ở độ tuổi năm mươi và sáu mươi
(khi không còn con cái ở nhà), có nhiều tiền tiêu hơn.
Hình 1-3Phân cụm [6]
Trong ví dụ này, chúng ta có thể nhận ra hai cụm, một cụm xung quanh nhóm
2.000 Đô la Mỹ/ 20-30 tuổi và một cụm ở nhóm 7.000-8.000 Đô la Mỹ/ 50-65 tuổi.
Trong trường hợp này, giả thuyết hai cụm và đã chứng minh giả thuyết bằng một đồ
11
thị đơn giản mà ta có thể tạo ra bằng cách sử dụng bất kỳ phần mềm đồ họa thích
hợp nào để có được cái nhìn nhanh chóng. Các quyết định phức tạp hơn cần phải có
một gói phần mềm phân tích đầy đủ, đặc biệt là nếu muốn các quyết định tự động
dựa vào thông tin lân cận gần nhất.
Việc vẽ đồ thị phân cụm theo cách này là một ví dụ đơn giản về cái gọi là
nhận ra sự lân cận gần nhất. Có thể nhận ra các khách hàng riêng lẻ bằng sự gần
gũi theo nghĩa đen của họ với nhau trên đồ thị. Có nhiều khả năng là các khách
hàng trong cùng một cụm cũng dùng chung các thuộc tính khác và bạn có thể sử
dụng sự mong đợi đó để giúp hướng dẫn, phân loại và nếu không thì phân tích
những người khác trong tập hợp dữ liệu của bạn.
Cũng có thể áp dụng việc phân cụm theo quan điểm ngược lại; dựa vào một số
thuộc tính đầu vào, có thể nhận ra các tạo phẩm khác nhau. Ví dụ, một nghiên cứu
gần đây về các số PIN 4-chữ số đã tìm ra các cụm giữa các chữ số trong phạm vi 112 và 1-31 cho các cặp đầu tiên và thứ hai. Bằng cách vẽ các cặp này, bạn có thể
nhận ra và xác định các cụm liên quan đến ngày tháng (các ngày sinh nhật, các ngày
kỷ niệm).
1.1.5.4Dự báo
Dự báo là một chủ đề rộng và đi từ dự báo về lỗi của các thành phần hay máy
móc đến việc nhận ra sự gian lận và thậm chí là cả dự báo về lợi nhuận của công ty
nữa. Được sử dụng kết hợp với các kỹ thuật khai phá dữ liệu khác, dự báo gồm có
việc phân tích các xu hướng, phân loại, so khớp mẫu và mối quan hệ. Bằng cách
phân tích các sự kiện hoặc các cá thể trong quá khứ, bạn có thể đưa ra một dự báo
về một sự kiện.
Khi sử dụng quyền hạn thẻ tín dụng, chẳng hạn, bạn có thể kết hợp phân tích
cây quyết định của các giao dịch riêng lẻ trong quá khứ với việc phân loại và các sự
so khớp mẫu lịch sử để nhận biết liệu một giao dịch có gian lận hay không. Rất có
thể là việc thực hiện một sự so khớp giữa việc mua vé các chuyến bay đến Mỹ và
các giao dịch tại Mỹ cho thấy giao dịch này hợp lệ.
12
1.1.5.5Các mẫu tuần tự
Thường được sử dụng trên các dữ liệu dài hạn, các mẫu tuần tự là một phương
pháp có ích để nhận biết các xu hướng hay các sự xuất hiện thường xuyên của các
sự kiện tương tự. Ví dụ, với dữ liệu khách hàng, có thể nhận ra rằng các khách hàng
cùng nhau mua một bộ sưu tập riêng lẻ về các sản phẩm tại nhiều thời điểm khác
nhau trong năm. Trong một ứng dụng giỏ hàng, có thể sử dụng thông tin này để tự
động đề xuất rằng một số mặt hàng nào đó được thêm vào một giỏ hàng dựa trên tần
suất và lịch sử mua hàng trong quá khứ của các khách hàng.
1.1.5.6Các cây quyết định
Liên quan đến hầu hết các kỹ thuật khác (chủ yếu là phân loại và dự báo), cây
quyết định có thể được sử dụng hoặc như là một phần trong các tiêu chí lựa chọn
hoặc để hỗ trợ việc sử dụng và lựa chọn dữ liệu cụ thể bên trong cấu trúc tổng thể.
Trong cây quyết định, bạn bắt đầu bằng một câu hỏi đơn giản có hai câu trả lời
(hoặc đôi khi có nhiều câu trả lời hơn). Mỗi câu trả lời lại dẫn đến thêm một câu hỏi
nữa để giúp phân loại hay nhận biết dữ liệu sao cho có thể phân loại dữ liệu hoặc
sao cho có thể thực hiện dự báo trên cơ sở mỗi câu trả lời. Hình 1-4cho thấy một ví
dụ trong đó bạn có thể phân loại một điều kiện lỗi gửi đến.
Hình 1-4Cây quyết định [6]
13
Các cây quyết định thường được sử dụng cùng với các hệ thống phân loại liên
quan đến thông tin có kiểu thuộc tính và với các hệ thống dự báo, nơi các dự báo
khác nhau có thể dựa trên kinh nghiệm lịch sử trong quá khứ để giúp hướng dẫn cấu
trúc của cây quyết định và kết quả đầu ra.
1.1.6 Ứng dụng của khai phá dữ liệu
Khai phá dữ liệu tuy là một hướng tiếp cận mới nhưng thu hút được rất nhiều
sựquan tâm của các nhà nghiên cứu và phát triển nhờvào những ứng dụng thực tiễn
của nó. Chúng ta có thểliệt kê ra đây một số ứng dụng điển hình:
Phân tích dữ liệu và hỗtrợra quyết định (data analysis & decision support)
Điều trịy học (medical treatment)
Text mining & Web mining
Tin-sinh (bio-informatics)
Tài chính và thịtrường chứng khoán (finance & stock market)
Bảo hiểm (insurance)
Nhận dạng (pattern recognition)
.v.v.
1.2 Cấu trúc câydữ liệu
Đồ thị được gắn nhãn G = (V, E, , L) gồm tập các đỉnh V, tập cạnh E, bảng
chữ cho các nhãn của đỉnh, các cạnh và hàm gắn nhãn L: V E . Đồ thị là có
hướng (hoặc vô hướng) nếu mỗi cạnh nối hai đỉnh là một cặp được sắp (hoặc không
có thứ tự, không được sắp tương ứng). Đồ thị là liên thông nếu giữa hai đỉnh bất kỳ
đều có ít nhất một đường đi nối giữa chúng, ngược lại là đồ thị không liên thông.
Chu trình trong đồ thị là một đường đi mà đỉnh đầu và đỉnh cuối trùng nhau. [4]
1.2.1 Các loại cây
Cây tự do (Free Tree) là một đồ thị vô hướng liên thông và phi chu trình.
Định nghĩa 1.2Cây có gốc (rooted tree), gọi tắt là cây, là cây tự do có một đỉnh đặc
biệt được gọi là gốc và thỏa mãn các tính chất sau:
-
Mỗi đỉnh khác gốc đều có đúng một đỉnh vào
-
Có đúng một đường đi từ gốc tới mỗi đỉnh khác của cây.
14
Trong cấu trúc cây, đỉnh v trên đường đi từ gốc tới w được gọi là tiền bối
(ancestor) của w, còn w được gọi là hậu duệ (descendant) của v. Nếu w liền kề với
v (có cạnh nối v với w) thì v là cha của w, hay ngược lại w là con của v. Kích thước
của cây t được định nghĩa là số đỉnh của cây, ký hiệu là |t| = |V|. Để tiện lợi, ta qui
ước cây có kích thước k sẽ được gọi là k-cây. Trong cây, một đỉnh v được gọi là lá
nếu nó không có đỉnh con. Bậc của mỗi đỉnh v là số đỉnh con của nó, ký hiệu là
deg(v). Hiển nhiên, nếu v là lá thì deg(v) = 0.
Chiều cao của cây t, ký hiệu là high(t), là độ dài của đường đi dài nhất trên cây
(bắt đầu từ gốc). Thông thường, đối với k-cây thì độ dài của cây t luôn thỏa mãn
high(t) < k. Một đỉnh trên cây được gọi là ở mức m nếu đường đi từ gốc tới nó có
độ dài (số cạnh) là m, m h. Đỉnh gốc có mức là 0. Đỉnh không phải là gốc, không
phải là lá được gọi là đỉnh trong của cây.
Cây t và s được gọi là đẳng cấu với nhau (isomorphism) nếu tồn tại một ánh
xạ 1-1 giữa hai tập đỉnh của t, s và bảo toàn được các nhãn của đỉnh và các cạnh.
Một cây con t có đẳng cấu trong cây s nếu tồn tại một đẳng cấu của t với một cây con
của s.
Các cây trong đó mỗi nút có thể có nhiều hơn hai con được gọi là cây tổng quát,
các cây trong đó mỗi nút có không quá hai con được gọi là cây nhị phân.
Các cây có thể phân chia thành hai loại chính: cây có thứ tự và cây không có
thứ tự.
1.2.1.1Cây có thứ tự
Định nghĩa 1.3Một cây có thứ tự (rooted ordered tree) là cây trong đó các đỉnh con
của mỗi đỉnh đều được xếp theo thứ tự từ trái qua phải, ngược lại được gọi là cây
không có thứ tự.
Ví dụ 1-2Các cây có thứ tự, trong đó sử dụng các nhãn để ký hiệu cho các đỉnh của cây.
- Xem thêm -