Đăng ký Đăng nhập
Trang chủ Khai phá dữ liệu đồ thị (cây dữ liệu), phát hiện các cây con phổ biến...

Tài liệu Khai phá dữ liệu đồ thị (cây dữ liệu), phát hiện các cây con phổ biến

.PDF
77
197
59

Mô tả:

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 -

Tài liệu liên quan