Luận văn Thạc sĩ: Khai phá đồ thị con phổ biến và ứng dụng

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:75

Thêm vào BST

Báo xấu

27
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu của đề tài là nghiên cứu lý thuyết về các phương pháp khai phá đồ thị con phổ biến và thử nghiệm giải quyết bài toán phát hiện cộng đồng trên mạng xã hội. Định hướng nghiên cứu của đề tài là nghiên cứu các phương pháp khai phá đồ thị con phổ biến là ứng dụng giải quyết bài toán phát hiện cộng đồng trên mạng xã hội. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ: Khai phá đồ thị con phổ biến và ứng dụng

i ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG ----------------------------- HOÀNG VIỆT DŨNG KHAI PHÁ ĐỒ THỊ CON PHỔ BIẾN VÀ ỨNG DỤNG Thái Nguyên, 2018
ii LỜI CAM ĐOAN Tôi xin cam đoan số liệu và kết quả nghiên cứu trong luận văn này là trung thực và chưa sử dụng để bảo vệ luận văn của một học vị nào. Tôi xin cam đoan mọi sự giúp đỡ cho việc thực hiện luận văn này đã được cảm ơn và các thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn gốc. Hà Nội, tháng 05 năm 2018 Tác giả Hoàng Việt Dũng
iii LỜI CẢM ƠN Để hoàn thành luận văn, tôi đã nhận được sự giúp đỡ rất tận tình, sự đóng góp quý báu của nhiều cá nhân và tập thể. Trước hết, tôi xin trân trọng cảm ơn Thầy giáo PGS.TS. Nguyễn Long Giang người đã nhiệt tình hướng dẫn, giúp đỡ tôi trong việc hoàn thành luận văn này. Tôi xin trân trọng cảm ơn sự góp ý chân thành của các Thầy, Cô giáo Viện Công nghệ thông tin, Các thầy giáo, cô giáo Trường Đại học Công nghệ thông tin và truyền thông - Đại học Thái Nguyên, đã tạo điều kiện thuận lợi cho tôi thực hiện và hoàn thành đề tài. Tôi xin cảm ơn đến gia đình, người thân, các đồng nghiệp và bạn bè đã động viên, giúp đỡ, tạo điều kiện thuận lợi cho tôi trong quá trình thực hiện đề tài này. Một lần nữa tôi xin trân trọng cảm ơn ! Hà Nội, tháng 5 năm 2018 Tác giả Hoàng Việt Dũng
iv MỤC LỤC Trang phụ bìa LỜI CAM ĐOAN .............................................................................................. i LỜI CẢM ƠN .................................................................................................. iii MỤC LỤC ........................................................................................................ iv DANH MỤC CÁC TỪ VIẾT TẮT …..……………………………………. vi DANH MỤC BẢNG ....................................................................................... vii DANH MỤC HÌNH ..................................................................................... ixvii ĐẶT VẤN ĐỀ ................................................................................................... 1 1.1. Sự cần thiết lựa chọn đề tài ........................................................................ 1 1.2. Mục tiêu nghiên cứu của đề tài .................................................................. 3 2. Đối tượng và phạm vi nghiên cứu ................................................................. 3 2.1. Đối tượng ................................................................................................... 3 2.2. Phạm vi nghiên cứu .................................................................................... 3 3. Hướng nghiên cứu của đề tài ........................................................................ 3 4. Cấu trúc của luận văn .................................................................................... 3 Chương 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ĐỒ THỊ ....................... 4 1.1. Tổng quan về khai phá dữ liệu đồ thị......................................................... 4 1.1.1. Tại sao cần khai phá dữ liệu:.................................................................. 4 1.1.2. Các khái niệm khai phá dữ liệu .............................................................. 4 1.1.3. Các chức năng chính của khai phá dữ liệu ............................................. 5 1.1.4. Các công cụ khai phá dữ liệu .................................................................. 6 1.2. Quy trình khai phá dữ liệu đồ thị ............................................................... 7 1.2.1. Hình thành và định nghĩa bài toán ......................................................... 7 1.2.2. Thu thập và tiền xử lý dữ liệu.................................................................. 8 1.2.3. Khai phá dữ liệu và rút ra các tri thức ................................................... 8 1.2.4. Phân tích và kiểm định kết quả ............................................................... 9
v 1.2.5. Sử dụng các tri thức phát hiện được ....................................................... 9 1.3. Các bài toán trong khai phá dữ liệu đồ thị ................................................. 9 1.3.1. Khai phá luật kết hợp .............................................................................. 9 1.3.2. Phân lớp .................................................................................................. 9 1.3.3. Phân cụm ............................................................................................... 10 1.3.4. Dự báo ................................................................................................... 11 1.3.5. Các mẫu tuần tự .................................................................................... 11 1.3.6. Các cây quyết định ................................................................................ 12 1.4. Các ứng dụng của khai phá dữ liệu đồ thị ................................................ 13 1.4.1. Các lĩnh vực liên quan đến phát hiện tri thức và khai phá dữ liệu ...... 13 1.4.2. Ứng dụng của khai phá dữ liệu ............................................................. 13 Chương 2. CÁC PHƯƠNG PHÁP KHAI PHÁ ĐỒ THỊ CON .................... 15 PHỔ BIẾN....................................................................................................... 15 2.1. Các định nghĩa về đồ thị con phổ biến ..................................................... 15 2.1.1. Giới thiệu về lý thuyết đồ thị ................................................................. 15 2.1.2. Khai phá dữ liệu .................................................................................... 19 2.1.3. Một số phương pháp khai phá dữ liệu ................................................. 21 2.1.4. Khai phá đồ thị con phổ biến ................................................................ 26 2.2. Các phương pháp khai phá đồ thị con phổ biến ....................................... 27 2.2.1 . Thuật toán Apriori để tìm tập con phổ biến ......................................... 27 2.2.2. Thuật toán FSG (Frequency SubGraph Mining) để phát hiện cộng đồng mạng xã hội ..................................................................................................... 34 2.3. Ứng dụng khai phá đồ thị con phổ biến phát hiện cộng đồng trên mạng xã hội .................................................................................................................... 39 2.3.1. Cộng đồng mạng xã hội ........................................................................ 39 2.3.2. Các phương pháp truyền thống ........................................................... 41 2.3.3. Các phương pháp áp dụng thuật toán phân chia: ................................ 43
vi 2.3.4. Phát hiện cộng đồng trong mạng xã hội ............................................... 45 Chương 3. THỬ NGHIỆM, ĐÁNH GIÁ KẾT QUẢ VỚI BÀI TOÁN PHÁT HIỆN CỘNG ĐỒNG MẠNG XÃ HỘI .......................................................... 50 3.1. Mô tả bài toán........................................................................................... 50 3.2. Mô hình giải quyết bài toán ..................................................................... 50 3.2.1. Mô hình đồ thị thông tin ........................................................................ 50 3.2.2. Hướng của cạnh .................................................................................... 50 3.2.3. Trọng số của cạnh ................................................................................. 51 3.2.4. Lựa chọn mô hình cho bài toán ............................................................ 51 3.3. Thử nghiệm, đánh giá mô hình (thu thập dữ liệu từ mạng xã hội, biểu diễn dữ liệu, cài đặt, thử nghiệm và đánh giá kết quả) ........................................... 51 3.3.1. Giới thiệu nhóm Facebook, phân tích nhóm Facebook ........................ 51 3.3.2. Phương pháp thu thập dữ liệu từ nhóm Facebook ............................... 53 3.3.3. Thử nghiệm bài toán ............................................................................. 54 3.3.4. Thuật toán chính ................................................................................... 55 3.3.5. Demo bài toán ....................................................................................... 56 3.3.6. Đánh giá ................................................................................................ 62 KẾT LUẬN VÀ KHUYẾN NGHỊ ................................................................. 64 1. Kết luận ....................................................................................................... 64 2. Khuyến nghị ................................................................................................ 64 TÀI LIỆU THAM KHẢO
vii DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt Ý nghĩa KDD Knowleadge Discovery in Database CSDL Cơ sở dữ liệu CNTT Công nghệ thong tin OLAP On Line Analytical Processing FSG Frequency SubGraph Mining CONGA Cluster Overlap Newman-Girvan Algorithm FNCA Fast Network Community Algorithm
viii DANH MỤC BẢNG Bảng 2.1. Biểu diễn giao dịch ......................................................................... 30 Bảng 2.2. Biểu diễn giao dịch ......................................................................... 30 Bảng 2.3. Biểu diễn giao dịch ......................................................................... 31 Bảng 2.4. Biểu diễn giao dịch ......................................................................... 31 Bảng 2.5. Biểu diễn giao dịch ......................................................................... 31 Bảng 2.6. Biểu diễn giao dịch ......................................................................... 32 Bảng 2.7. Kết quả cuối cùng .......................................................................... 32 Bảng 3.1. Một dạng format (Ma trận thích (Like)) ........................................ 54 Bảng 3.2. Bảng người dùng sau khi đã giải mã .............................................. 57 Bảng 3.3. Mảng chuyển đổi ............................................................................ 58
ix DANH MỤC HÌNH Hình 1.1. Các bước trong khai phá dữ liệu và KDD......................................... 5 Hình 1.2. Quá trình khai phá dữ liêu (khám phá tri thức)................................. 7 Hình 1.3. Phân cụm ......................................................................................... 11 Hình 1.4. Cây quyết định ................................................................................ 12 Hình 2.1. Mô tả mô hình đồ thị ....................................................................... 15 Hình 2.2. Các loại đồ thị ................................................................................. 16 Hình 2.3. Đơn đồ thị vô hướng ....................................................................... 16 Hình 2.4. Đa đồ thị vô hướng.......................................................................... 17 Hình 2.5. Giả đồ thị vô hướng ........................................................................ 18 Hình 2.6. Đơn đồ thị có hướng ....................................................................... 18 Hình 2.7. Đa đồ thị có hướng ......................................................................... 19 Hình 2.8. Minh họa thuật toán FSG ............................................................... 35 Hình 2.9. Cộng đồng mạng xã hội đơn giản với 3 cộng đồng ....................... 40 Hình 2.10. Phương pháp phân vùng đồ thị ..................................................... 41 Hình 2.11. Ví dụ về phép phân chia một đỉnh trong đồ thị ............................ 44 Hình 2.12. Một số ví dụ về cộng đồng trên mạng xã hội .............................. 45 Hình 2.13. Mô hình mạng lưới cộng tác của các nhà khoa học ..................... 46 Hình 3.1. Liên kết giữa hai đỉnh (người) trên mạng xã hội ............................ 50 Hình 3.2. Quan hệ giữa hai người trên mạng xã hội với trọng số .................. 51 Hình 3.3. Hình ảnh một nhóm Facebook ........................................................ 52 Hình 3.5. Ví dụ 3 định dạng worksheet: bạn bè, thích, bình luận .................. 59 Hình 3.6. Đồ thị sau khi xử lý ......................................................................... 59 Hình 3.7. Bộ dữ liệu sau khi xử lý .................................................................. 60 Hình 3.8. So sánh thuật toán Light-FSG với thuật toán khác ......................... 60 Hình 3.9. Giao diện chương trình .................................................................. 61 Hình 3.10. Biểu diễn Mạng đồ thị 2D ............................................................. 61 Hình 3.11. Biểu diễn Mạng đồ thị 3D ............................................................. 62
1 ĐẶT VẤN ĐỀ 1.1. Sự cần thiết lựa chọn đề tài Trong những năm gần đây, khai phá dữ liệu dữ liệu đồ thị là chủ đề thu hút sự quan tâm của cộng đồng nghiên cứu về khai phá dữ liệu và học máy và được ứng dụng rộng rãi trong nhiều lĩnh vực như: phân tích dữ liệu hóa học, sinh học, phân tích mạng máy tính, phân tích mạng xã hội..[4, 5, 6]. Theo tìm hiểu của tác giả, các nghiên cứu liên quan đến khai phá dữ liệu đồ thị thường tập trung vào các bài toán như: liệt kê và đếm (Enumeration and Counting), phân lớp đồ thị (graph classification), phân cụm đồ thị (graph clustering), học bán giám sát (semi-supervisedlearning), tóm tắt đồ thị (graph summarization), khai phá đồ thị phổ biến (frequent graph mining)… Khai phá đồ thị phổ biến là hướng nghiên cứu sôi động trong mấy năm gần đây trong lĩnh vực khai phá dữ liệu đồ thị. Dựa trên nền tảng của bài toán khai phá luật kết hợp, khai phá đồ thị phổ biến nhằm tìm kiếm các đồ thị con phổ biến (tương ứng với tập mục phổ biến). Các đồ thị con phổ biến là nền tảng để giải quyết bài toán dự báo trên không gian dữ liệu đồ thị và có ứng rộng rãi trong nhiều lĩnh vực khác nhau của đời sống. Một số thuật toán điển hình khai phá đồ thị phổ biến là CMTMiner [7], HSIGRAM, VSIGRAM [8],. Thuật toán CMTMiner thực hiện việc duyệt các cạnh phổ biến và xây dựng cây DFS để tìm các đồ thị con phổ biến.Trong khi đó, HSIGRAM, VSIGRAM là hai thuật toán xác định các đồ thị con phổ biến trong một đồ thị lớn. Như đã trình bày ở trên, lĩnh vực khai phá dữ liệu đồ thị đã thu được các kết quả quan trọng về lý thuyết và đã có ứng dụng hiệu quả trong việc giải quyết một số bài toán trong thực tiễn.Một trong những bài toán ứng dụng của khai phá đồ thị con phổ biến là phát hiện cộng đồng mạng xã hội.
2 Mạng xã hội là một cấu trúc mang tính xã hội được cấu tạo từ các nút và các cung, trong đó các nút được liên kết với nhau bởi một hoặc nhiều cung, thể hiện kiểu mối quan hệ cụ thể [9]. Mỗi nút, còn được gọi là tác nhân (actor), biểu diễn cho một đối tượng trong xã hội, có thể là một người, một tài liệu, một tổ chức, một quốc gia,…Mối liên hệ giữa các nút được biểu diễn bởi một liên kết giữa các nút đó. Liên kết này có thể là mối quan hệ bạn bè, họ hàng, đồng nghiệp,…, cũng có thể là các trao đổi tài chính, các giao dịch, số liệu,…Các liên kết này có thể là liên kết vô hướng (hay còn gọi là liên kết đối xứng hoặc liên kết có hướng. Mặt khác, các liên kết còn có thể được đánh trọng số, trọng số này biểu diễn độ mạnh của liên kết đó giữa hai nút.Về mặt toán học, mạng xã hội có thể được biểu diễn dưới dạng đồ thị có hướng, trên cơ sở đó có thể áp dụng các phương pháp khai phá dữ liệu đồ thị để giải quyết các bài toán trên mạng xã hội. Phát hiện cộng đồng mạng xã hội là bài toán thu hút sự quan tâm của nhiều nhóm nghiên cứu. Theo Simmel (1955) thì cộng đồng là một nhóm các cá nhân trên mạng, tập các thực thể có những tính chất tương tự nhau và cùng đóng một vai trò trong mạng xã hội. Bài toán phát hiện cộng đồng là từ các mạng xã hội cho trước, phát hiện được các cấu trúc cộng đồng nằm trong đó và tìm hiểu về mối liên hệ bên trong các cộng đồng cũng như giữa các cộng đồng với nhau, mối liên hệ đó có ảnh hưởng thế nào đến cấu trúc của toàn mạng xã hội. Theo Santo Fortunato [10], các phương pháp phát hiện cộng đồng trong mạng xã hội điển hình là: các phương pháp truyền thống; các thuật toán phân chia; các phương pháp dựa trên mô đun hóa; các thuật toán động; các phương pháp phát hiện cộng đồng chồng chéo. Các thuật toán phát hiện cộng đồng điển hình là Girvan- Newman [11], Conga [12]…
3 Định hướng nghiên cứu của đề tài là nghiên cứu các phương pháp khai phá đồ thị con phổ biến là ứng dụng giải quyết bài toán phát hiện cộng đồng trên mạng xã hội. 1.2. Mục tiêu nghiên cứu của đề tài Nghiên cứu lý thuyết về các phương pháp khai phá đồ thị con phổ biến và thử nghiệm giải quyết bài toán phát hiện cộng đồng trên mạng xã hội. 2. Đối tượng và phạm vi nghiên cứu 2.1. Đối tượng Đối tượng nghiên cứu là các phương pháp, công cụ khai phá đồ thị con phổ biến và dữ liệu thử nghiệm được thu thập từ mạng xã hội 2.2. Phạm vi nghiên cứu Phạm vi nghiên cứu là bài toán khai phá đồ thị con phổ biến và thử nghiệm với bài toán phát hiện cộng đồng mạng xã hội. 3. Hướng nghiên cứu của đề tài - Khai phá dữ liệu đồ thị trong lĩnh vực khai phá dữ liệu và học máy 4. Cấu trúc của luận văn Dự kiến luận văn gồm: Phần mở đầu, ba chương nội dung, kết luận và tài liệu tham khảo cụ thể:
4 Chương 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ĐỒ THỊ 1.1. Tổng quan về khai phá dữ liệu đồ thị 1.1.1. Tại sao cần khai phá dữ liệu: Khoảng 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ử không ngừng tăng lên. Theo các chuyên gia trong ngành CNTT sau cứ khoảng 2 năm thì lượng thông tin lưu trữ trên toàn thế giới tăng gấp đôi, không những vậy các thông tin lưu trữ này có số lượng và kích cỡ CSDL ngày càng lớn và tăng một cách nhanh chóng. Để giải quyết vấn đề này khai phá dữ liệu ra đời như một cách hữu hiệu giải quyết vấn đề vừa nêu ở trên. Hiện nay khai phá dữ liệu có rất nhiều định nghĩa tuy nhiên chúng ta có thể hiểu đơn giản khai phá dữ liệu như là một công nghệ tri thức giú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 tổ chức, đơn vị nào đó. 1.1.2. Các khái niệm khai phá dữ liệu Thuật ngữ khai phá dữ liệu là nói đến 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ô. Hiện nay có rất nhiều thuật ngữ được dùng có nghĩa tương tự với khai 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), …. Định nghĩa : Khai phá dữ liệu là 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 các dữ liệu khổng lồ và phức tạp, đồng thời cũng tìm ta các mẫu tiềm ẩn trong tập dữ liệu. Khai phá dữ liệu là một 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ự:
5 - Làm sạch dữ liệu (data cleaning & preprocessing): Loại bỏ nhiễu các dữ liệu không cần thiết. - Tích hợp dữ liệu (Data integration): Quá trình hợp nhất dữ liệu thành kho dữ liệu sau khi đã làm sạch dữ liệu và tiền xử lý. - 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 - Chuyển đổi dữ liệu: Các dữ liệu được chuyển sang dạng phù hợp cho quá trình xử lý - Khai phá dữ liệu: Đây là một trong những 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. - Ước lượng mẫu (Knowledge evulation): Đây là quá trình đánh giá các kết quả tìm được thông qua các độ đo nào đó. - Biểu diễn tri thức (knowledge pesentation): Quá trình sử dụng các kỹ thuật để biểu diễn và thể hiện trực quan cho người dùng. Hình 1.1. Các bước trong khai phá dữ liệu và KDD 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 thành các nhánh nhỏ bao gồm: - Mô tả khái niệm: Thiên về mô tả, tổng hợp và tóm tắt khai niệm.
6 Ví dụ cụ thể minh hoa cho nhánh này chính là quá trình tóm tắt văn bản, bài báo, bài luận…. - Luật kết hợp: Là dạng luật biểu diễn tri thức ở dạng khá đơn giản VD: “ 70% nam giới đi mua bia thì trong số đó 85% sẽ mua thêm đồ nhắm” Luật kết hợp được ứng dụng trong nhiều lĩnh vực như: y học, kinh doanh, tài chính và thị trường chứng khoán… - Phân lớp và dự đoán: Xếp một đối tượng vào trong một lớp đã biết trước. Hướng tiếp cận này thường sử dụng một số kỹ thuật của học máy(machine learning) như cây quyết định, mạng noron nhân tạo, …đây còn được hiểu theo nghĩa khác là học có giám sát. VD: Phân lớp vùng địa lý theo dự báo thời tiết - Phân cụm: Xếp các đối tượng theo từng cụm, số lượng cũng như tên cụm chưa được biết trước. Phân cụm hay còn gọi tên khác là học không giám sát. - Khai phá chuỗi: Khai phá chuỗi tương tự như khai phá luật kết hợp nhưng ở đây 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ả 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 việc 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ối quan hệ hoặc uy tín lớn hơn bằng các kỹ thuật khác nhau. Hiện nay 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
7 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ữ kiệu kết hợp. 1.2. Quy trình khai phá dữ liệu đồ thị Quá trình khai phá dữ liệu đồ thị (khám phá tri thức) được tiến hành qua 5 bước sau Hình thành và định nghĩa bài toán Thu thập và Tiền xử lý dữ liệu Khai thác dữ liệu Rút ra các tri thức Phân tích và kiểm định kết quả Sử dụng các tri thức phát hiện được Hình 1.2. Quá trình khai phá dữ liêu (khám phá tri thức) 1.2.1. Hình thành và định nghĩa bài toán Đây là bước tìm hiểu lĩnh vực ứng dụng và hình thành bài toán, bước này sẽ quyết định cho việc rút ra những tri thức hữu ích, đồng thời lựa chọn các phương pháp khai phá dữ liệu thích hợp với mục đích của ứng dụng và bản chất của dữ liệu.
8 1.2.2. Thu thập và tiền xử lý dữ liệu Trong bước này dữ liệu được thu thập ở dạng thô (nguồn dữ liệu thu thập có thể là từ các kho dữ liệu hay nguồn thông tin internet). Trong giai đoạn này dữ liệu cũng được tiền xử lý để biến đổi và cải thiện chất lượng dữ liệu cho phù hợp với phương pháp khai phá dữ liệu được chọn lựa trong bước trên. Bước này thường chiếm nhiều thời gian nhất trong quá trình khám phá tri thức. Các giải thuật tiền xử lý dữ liệu bao gồm : Xử lý dữ liệu bị mất/ thiếu: Các dạng dữ liệu bị thiếu sẽ được thay thế bởi các giá trị thích hợp Khử sự trùng lắp: các đối tượng dữ liệu trùng lắp sẽ bị loại bỏ đi. Kỹ thuật này không được sử dụng cho các tác vụ có quan tâm đến phân bố dữ liệu. Giảm nhiễu: nhiễu và các đối tượng tách rời khỏi phân bố chung sẽ bị loại đi khỏi dữ liệu. Chuẩn hoá: miền giá trị của dữ liệu sẽ được chuẩn hoá. Rời rạc hoá: các dạng dữ liệu số sẽ được biến đổi ra các giá trị rời rạc. Rút trích và xây dựng đặc trưng mới từ các thuộc tính đã có. Giảm chiều: các thuộc tính chứa ít thông tin sẽ được loại bỏ bớt. 1.2.3. Khai phá dữ liệu và rút ra các tri thức Đây là bước quan trọng nhất trong tiến trình khám phá tri thức. Kết quả của bước này là trích ra được các mẫu và/hoặc các mô hình ẩn dưới các dữ liệu. Một mô hình có thể là một biểu diễn cấu trúc tổng thể một thành phần của hệ thống hay cả hệ thống trong cơ sở dữ liệu, hay miêu tả cách dữ liệu được nảy sinh. Còn một mẫu là một cấu trúc cục bộ có liên quan đến vài biến và vài trường hợp trong cơ sở dữ liệu.
9 1.2.4. Phân tích và kiểm định kết quả Bước thứ tư là hiểu các tri thức đã tìm được, đặc biệt là làm sáng tỏ các mô tả và dự đoán. Trong bước này, kết quả tìm được sẽ được biến đổi sang dạng phù hợp với lĩnh vực ứng dụng và dễ hiểu hơn cho người dùng. 1.2.5. Sử dụng các tri thức phát hiện được Trong bước này, các tri thức khám phá được sẽ được củng cố, kết hợp lại thành một hệ thống, đồng thời giải quyết các xung đột tiềm năng trong các tri thức đó. Các mô hình rút ra được đưa vào những hệ thống thông tin thực tế dưới dạng các môdun hỗ trợ việc đưa ra quyết định. Các giai đoạn của quá trình khám phá tri thức có mối quan hệ chặt chẽ với nhau trong bối cảnh chung của hệ thống. Các kỹ thuật được sử dụng trong giai đoạn trước có thể ảnh hưởng đến hiệu quả của các giải thuật được sử dụng trong các giai đoạn tiếp theo. Các bước của quá trình khám phá tri thức có thể được lặp đi lặp lại một số lần, kết quả thu được có thể được lấy trung bình trên tất cả các lần thực hiện. 1.3. Các bài toán trong khai phá dữ liệu đồ thị Một số kỹ thuật cốt lõi được sử dụng trong các bài toán khai phá dữ liệu, mô tả kiểu hoạt động khai phá dữ liệu và hoạt động phục hồi dữ liệu. 1.3.1. Khai phá luật kết hợp Khai phá luật kết hợp 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. 1.3.2. Phân lớp Kỹ thuật phân lớp dù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
10 biết một lớp cụ thể. Kỹ thuật phân lớp dù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. Hơn nữa chúng ta có thể sử dụng việc phân lớp như một dạng nguồn thứ cấp, hoặc như là kết quả của các kỹ thuật khác. 1.3.3. Phâ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.2 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. Với một đồ thị phân cụm đơ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à các quyết định dựa vào thông tin lân cận nhất. Việc vẽ đồ thị theo phân cụm là cách đơn giản nhất để nhận ra sự lân cận nhất. Có thể nhận ra các đối tượng riêng lẻ bằng sự gần gũi theo nghĩa đen của các đối tượng trên đồ thị.
11 Hình 1.3. Phân cụm 1.3.4. Dự 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ệ. 1.3.5. Cá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