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ả[.]
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 kết nghiên cứu luận văn trung thực chưa sử dụng để bảo vệ luận văn học vị Tôi xin cam đoan giúp đỡ cho việc thực luận văn cảm ơn thơng tin trích dẫn luận văn 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 Để hồn thành luận văn, tơi nhận giúp đỡ tận tình, đóng góp q báu nhiều cá nhân tập thể Trước hết, 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 việc hồn thành luận văn Tơi xin trân trọng cảm ơn góp ý chân thành 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 truyền thông - Đại học Thái Nguyên, tạo điều kiện thuận lợi cho thực hồn thành đề tài Tơi xin cảm ơn đến gia đình, người thân, đồng nghiệp bạn bè động viên, giúp đỡ, tạo điều kiện thuận lợi cho tơi q trình thực đề tài Một lần xin trân trọng cảm ơn ! Hà Nội, tháng 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 Sự cần thiết lựa chọn đề tài 1.2 Mục tiêu nghiên cứu đề tài Đối tượng phạm vi nghiên cứu 2.1 Đối tượng 2.2 Phạm vi nghiên cứu 3 Hướng nghiên cứu đề tài Cấu trúc luận văn Chương TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ĐỒ THỊ 1.1 Tổng quan khai phá liệu đồ thị 1.1.1 Tại cần khai phá liệu: 1.1.2 Các khái niệm khai phá liệu 1.1.3 Các chức khai phá liệu 1.1.4 Các công cụ khai phá liệu 1.2 Quy trình khai phá liệu đồ thị 1.2.1 Hình thành định nghĩa tốn 1.2.2 Thu thập tiền xử lý liệu 1.2.3 Khai phá liệu rút tri thức 1.2.4 Phân tích kiểm định kết v 1.2.5 Sử dụng tri thức phát 1.3 Các toán khai phá liệu đồ thị 1.3.1 Khai phá luật kết hợp 1.3.2 Phân lớp 1.3.3 Phân cụm 10 1.3.4 Dự báo 11 1.3.5 Các mẫu 11 1.3.6 Các định 12 1.4 Các ứng dụng khai phá liệu đồ thị 13 1.4.1 Các lĩnh vực liên quan đến phát tri thức khai phá liệu 13 1.4.2 Ứng dụng khai phá liệu 13 Chương CÁC PHƯƠNG PHÁP KHAI PHÁ ĐỒ THỊ CON 15 PHỔ BIẾN 15 2.1 Các định nghĩa đồ thị phổ biến 15 2.1.1 Giới thiệu lý thuyết đồ thị 15 2.1.2 Khai phá liệu 19 2.1.3 Một số phương pháp khai phá liệu 21 2.1.4 Khai phá đồ thị phổ biến 26 2.2 Các phương pháp khai phá đồ thị phổ biến 27 2.2.1 Thuật tốn Apriori để tìm tập phổ biến 27 2.2.2 Thuật toán FSG (Frequency SubGraph Mining) để phát cộng đồng mạng xã hội 34 2.3 Ứng dụng khai phá đồ thị phổ biến phát cộng đồng 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 cộng đồng mạng xã hội 45 Chương 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ả tốn 50 3.2 Mơ hình giải toán 50 3.2.1 Mơ hình đồ thị thơng tin 50 3.2.2 Hướng cạnh 50 3.2.3 Trọng số cạnh 51 3.2.4 Lựa chọn mơ hình cho toán 51 3.3 Thử nghiệm, đánh giá mơ hình (thu thập liệu từ mạng xã hội, biểu diễn liệu, cài đặt, thử nghiệm đá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 liệu từ nhóm Facebook 53 3.3.3 Thử nghiệm toán 54 3.3.4 Thuật tốn 55 3.3.5 Demo toán 56 3.3.6 Đánh giá 62 KẾT LUẬN VÀ KHUYẾN NGHỊ 64 Kết luận 64 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ở liệu CNTT Công nghệ thong tin OLAP On Line Analytical Processing FSG Frequency SubGraph Mining CONGA FNCA Cluster Overlap Newman-Girvan Algorithm 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 cuối 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 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 khai phá liệu KDD Hình 1.2 Quá trình khai phá liêu (khám phá tri thức) Hình 1.3 Phân cụm 11 Hình 1.4 Cây đị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 cộng đồng 40 Hình 2.10 Phương pháp phân vùng đồ thị 41 Hình 2.11 Ví dụ phép phân chia đỉnh đồ thị 44 Hình 2.12 Một số ví dụ cộng đồng mạng xã hội 45 Hình 2.13 Mơ hình mạng lưới cộng tác nhà khoa học 46 Hình 3.1 Liên kết hai đỉnh (người) mạng xã hội 50 Hình 3.2 Quan hệ hai người mạng xã hội với trọng số 51 Hình 3.3 Hình ảnh nhóm Facebook 52 Hình 3.5 Ví dụ định dạng worksheet: bạn bè, thích, bình luận 59 Hình 3.6 Đồ thị sau xử lý 59 Hình 3.7 Bộ liệu sau 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 ĐẶT VẤN ĐỀ 1.1 Sự cần thiết lựa chọn đề tài Trong năm gần đây, khai phá liệu liệu đồ thị chủ đề thu hút quan tâm cộng đồng nghiên cứu khai phá liệu học máy ứng dụng rộng rãi nhiều lĩnh vực như: phân tích 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 tác giả, nghiên cứu liên quan đến khai phá liệu đồ thị thường tập trung vào toán như: liệt kê đế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 hướng nghiên cứu sôi động năm gần lĩnh vực khai phá liệu đồ thị Dựa tảng toán khai phá luật kết hợp, khai phá đồ thị phổ biến nhằm tìm kiếm đồ thị phổ biến (tương ứng với tập mục phổ biến) Các đồ thị phổ biến tảng để giải toán dự báo không gian liệu đồ thị có ứng rộng rãi nhiều lĩnh vực khác đời sống Một số thuật tốn điển hình khai phá đồ thị phổ biến CMTMiner [7], HSIGRAM, VSIGRAM [8], Thuật toán CMTMiner thực việc duyệt cạnh phổ biến xây dựng DFS để tìm đồ thị phổ biến.Trong đó, HSIGRAM, VSIGRAM hai thuật toán xác định đồ thị phổ biến đồ thị lớn Như trình bày trên, lĩnh vực khai phá liệu đồ thị thu kết quan trọng lý thuyết có ứng dụng hiệu việc giải số toán thực tiễn.Một toán ứng dụng khai phá đồ thị phổ biến phát cộng đồng mạng xã hội 2 Mạng xã hội cấu trúc mang tính xã hội cấu tạo từ nút cung, nút liên kết với nhiều cung, thể kiểu mối quan hệ cụ thể [9] Mỗi nút, gọi tác nhân (actor), biểu diễn cho đối tượng xã hội, người, tài liệu, tổ chức, quốc gia,…Mối liên hệ nút biểu diễn liên kết nút Liên kết mối quan hệ bạn bè, họ hàng, đồng nghiệp,…, trao đổi tài chính, giao dịch, số liệu,…Các liên kết liên kết vơ hướng (hay cịn gọi liên kết đối xứng liên kết có hướng Mặt khác, liên kết cịn đánh trọng số, trọng số biểu diễn độ mạnh liên kết hai nút.Về mặt tốn học, mạng xã hội biểu diễn dạng đồ thị có hướng, sở áp dụng phương pháp khai phá liệu đồ thị để giải toán mạng xã hội Phát cộng đồng mạng xã hội toán thu hút quan tâm nhiều nhóm nghiên cứu Theo Simmel (1955) cộng đồng nhóm cá nhân mạng, tập thực thể có tính chất tương tự đóng vai trị mạng xã hội Bài toán phát cộng đồng từ mạng xã hội cho trước, phát cấu trúc cộng đồng nằm tìm hiểu mối liên hệ bên cộng đồng cộng đồng với nhau, mối liên hệ có ảnh hưởng đến cấu trúc toàn mạng xã hội Theo Santo Fortunato [10], phương pháp phát cộng đồng mạng xã hội điển hình là: phương pháp truyền thống; thuật toán phân chia; phương pháp dựa mơ đun hóa; thuật toán động; phương pháp phát cộng đồng chồng chéo Các thuật tốn phát cộng đồng điển hình Girvan- Newman [11], Conga [12]… Định hướng nghiên cứu đề tài nghiên cứu phương pháp khai phá đồ thị phổ biến ứng dụng giải toán phát cộng đồng mạng xã hội 1.2 Mục tiêu nghiên cứu đề tài Nghiên cứu lý thuyết phương pháp khai phá đồ thị phổ biến thử nghiệm giải toán phát cộng đồng mạng xã hội Đối tượng phạm vi nghiên cứu 2.1 Đối tượng Đối tượng nghiên cứu phương pháp, công cụ khai phá đồ thị phổ biến liệu thử nghiệm 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 toán khai phá đồ thị phổ biến thử nghiệm với toán phát cộng đồng mạng xã hội Hướng nghiên cứu đề tài - Khai phá liệu đồ thị lĩnh vực khai phá liệu học máy Cấu trúc 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 tài liệu tham khảo cụ thể: Chương TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ĐỒ THỊ 1.1 Tổng quan khai phá liệu đồ thị 1.1.1 Tại cần khai phá liệu: Khoảng thập kỷ trở lại lượng thông tin lưu trữ thiết bị điện tử không ngừng tăng lên Theo chuyên gia ngành CNTT sau khoảng năm lượng thơng tin lưu trữ tồn giới tăng gấp đôi, thông tin lưu trữ có số lượng kích cỡ CSDL ngày lớn tăng cách nhanh chóng Để giải vấn đề khai phá liệu đời cách hữu hiệu giải vấn đề vừa nêu Hiện khai phá liệu có nhiều định nghĩa nhiên hiểu đơn giản khai phá liệu công nghệ tri thức giúp khai thác thơng tin hữu ích từ kho liệu tích trữ suốt trình hoạt động tổ chức, đơn vị 1.1.2 Các khái niệm khai phá liệu Thuật ngữ khai phá liệu nói đến việc tìm kiếm tập hợp nhỏ có giá trị từ số lượng lớn liệu thô Hiện có nhiều thuật ngữ dùng có nghĩa tương tự với khai phá 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 liệu/mẫu (Data/patern), … Định nghĩa : Khai phá liệu tập hợp kỹ thuật đươc sử dụng để tự động để khai thác tìm mối quan hệ lẫn liệu tập hợp liệu khổng lồ phức tạp, đồng thời tìm ta mẫu tiềm ẩn tập liệu Khai phá liệu bảy bước trình KDD (Knowleadge Discovery in Database) KDD xem trình khác theo thứ tự: - Làm liệu (data cleaning & preprocessing): Loại bỏ nhiễu liệu khơng cần thiết - Tích hợp liệu (Data integration): Quá trình hợp liệu thành kho liệu sau làm liệu tiền xử lý - Trích chọn liệu (data selection): Trích chọn liệu từ kho liệu sau chuyển đổi dạng thích hợp cho q trình khai thác tri thức - Chuyển đổi liệu: Các liệu chuyển sang dạng phù hợp cho trình xử lý - Khai phá liệu: Đây bước quan trọng nhất, sử dụng phương pháp thông minh để chắt lọc mẫu liệu - Ước lượng mẫu (Knowledge evulation): Đây trình đánh giá kết tìm thơng qua độ đo - Biểu diễn tri thức (knowledge pesentation): Quá trình sử dụng kỹ thuật để biểu diễn thể trực quan cho người dùng Hình 1.1 Các bước khai phá liệu KDD 1.1.3 Các chức khai phá liệu Khai phá liệu đươc chia thành nhánh nhỏ bao gồm: - Mô tả khái niệm: Thiên mơ tả, tổng hợp tóm tắt khai niệm 6 Ví dụ cụ thể minh hoa cho nhánh q trình tóm tắt văn bản, báo, luận… - Luật kết hợp: Là dạng luật biểu diễn tri thức dạng đơn giản VD: “ 70% nam giới mua bia số 85% mua thêm đồ nhắm” Luật kết hợp ứng dụng nhiều lĩnh vực như: y học, kinh doanh, tài thị trường chứng khoán… - Phân lớp dự đoán: Xếp đối tượng vào lớp biết trước Hướng tiếp cận thường sử dụng số kỹ thuật học máy(machine learning) định, mạng noron nhân tạo, …đây hiểu theo nghĩa khác 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 đối tượng theo cụm, số lượng tên cụm chưa biết trước Phân cụm hay gọi tên khác học không giám sát - Khai phá chuỗi: Khai phá chuỗi tương tự khai phá luật kết hợp có thêm tính thứ tự tính thời gian Hướng tiếp cận ứng dụng nhiều lĩnh vực tài thị trường chứng khốn có tính dự báo cao 1.1.4 Các công cụ khai phá liệu Khai phá liệu tất công cụ hay phần mềm sở liệu sử dụng Có thể thực việc khai phá liệu hệ thống sở liệu bình thường cơng cụ đơn giản, bao gồm việc tạo viết phần mềm riêng sử dụng gói phần mềm thương mại Khai phá liệu phức tạp hưởng lợi từ kinh nghiệm khứ thuật toán định nghĩa với phần mềm gói phần mềm có với cơng cụ định để thu mối quan hệ uy tín lớn kỹ thuật khác Hiện tập hợp liệu lớn việc xử lý liệu theo cụm quy mơ lớn cho phép khai phá liệu để xếp lập báo cáo nhóm mối tương quan liệu phức tạp Bây có sẵn nhiều cơng cụ hệ thống hồn toàn gồm hệ thống lưu trữ xử lý kiệu kết hợp 1.2 Quy trình khai phá liệu đồ thị Quá trình khai phá liệu đồ thị (khám phá tri thức) tiến hành qua bước sau Hình thành định nghĩa tốn Thu thập Tiền xử lý liệu Khai thác liệu Rút tri thức Phân tích kiểm định kết Sử dụng tri thức phát Hình 1.2 Quá trình khai phá liêu (khám phá tri thức) 1.2.1 Hình thành định nghĩa tốn Đây bước tìm hiểu lĩnh vực ứng dụng hình thành tốn, bước định cho việc rút tri thức hữu ích, đồng thời lựa chọn phương pháp khai phá liệu thích hợp với mục đích ứng dụng chất liệu 8 1.2.2 Thu thập tiền xử lý liệu Trong bước liệu thu thập dạng thô (nguồn liệu thu thập từ kho liệu hay nguồn thông tin internet) Trong giai đoạn liệu tiền xử lý để biến đổi cải thiện chất lượng liệu cho phù hợp với phương pháp khai phá liệu chọn lựa bước Bước thường chiếm nhiều thời gian trình khám phá tri thức Các giải thuật tiền xử lý liệu bao gồm : Xử lý liệu bị mất/ thiếu: Các dạng liệu bị thiếu thay giá trị thích hợp Khử trùng lắp: đối tượng liệu trùng lắp bị loại bỏ Kỹ thuật không sử dụng cho tác vụ có quan tâm đến phân bố liệu Giảm nhiễu: nhiễu đối tượng tách rời khỏi phân bố chung bị loại khỏi liệu Chuẩn hoá: miền giá trị liệu chuẩn hoá Rời rạc hoá: dạng liệu số biến đổi giá trị rời rạc Rút trích xây dựng đặc trưng từ thuộc tính có Giảm chiều: thuộc tính chứa thơng tin loại bỏ bớt 1.2.3 Khai phá liệu rút tri thức Đây bước quan trọng tiến trình khám phá tri thức Kết bước trích mẫu và/hoặc mơ hình ẩn liệu Một mơ hình biểu diễn cấu trúc tổng thể thành phần hệ thống hay hệ thống sở liệu, hay miêu tả cách liệu nảy sinh Còn mẫu cấu trúc cục có liên quan đến vài biến vài trường hợp sở liệu 9 1.2.4 Phân tích kiểm định kết Bước thứ tư hiểu tri thức tìm được, đặc biệt làm sáng tỏ mơ tả dự đốn Trong bước này, kết tìm biến đổi sang dạng phù hợp với lĩnh vực ứng dụng dễ hiểu cho người dùng 1.2.5 Sử dụng tri thức phát Trong bước này, tri thức khám phá củng cố, kết hợp lại thành hệ thống, đồng thời giải xung đột tiềm tri thức Các mơ hình rút đưa vào hệ thống thông tin thực tế dạng môdun hỗ trợ việc đưa định Các giai đoạn q trình khám phá tri thức có mối quan hệ chặt chẽ với bối cảnh chung hệ thống Các kỹ thuật sử dụng giai đoạn trước ảnh hưởng đến hiệu giải thuật sử dụng giai đoạn Các bước trình khám phá tri thức lặp lặp lại số lần, kết thu được lấy trung bình tất lần thực 1.3 Các toán khai phá liệu đồ thị Một số kỹ thuật cốt lõi sử dụng tốn khai phá liệu, mơ tả kiểu hoạt động khai phá liệu hoạt động phục hồi liệu 1.3.1 Khai phá luật kết hợp Khai phá luật kết hợp kỹ thuật khai phá liêu biết đến nhiều tính quen thuộc đơn giản Ở thực tương quan đơn giản hai nhiều mục, thường kiểu để nhận biết mẫu Việc xây dựng công cụ khai phá liệu dựa kết hợp hay mối quan hệ thực đơn giản công cụ khác 1.3.2 Phân lớp Kỹ thuật phân lớp dùng để xây dựng ý tưởng kiểu khách hàng, kiểu mặt hàng kiểu đối tượng cách mơ tả nhiều thuộc tính để nhận 10 biết lớp cụ thể Kỹ thuật phân lớp dùng để xây dựng ý tưởng kiểu khách hàng, kiểu mặt hàng kiểu đối tượng Hơn sử dụng việc phân lớp dạng nguồn thứ cấp, kết kỹ thuật khác 1.3.3 Phân cụm Bằng cách xem xét hay nhiều thuộc tính lớp, nhóm phần liệu riêng lẻ với để tạo thành quan điểm cấu trúc Ở mức đơn giản, việc phân cụm sử dụng nhiều thuộc tính làm sở cho bạn để nhận nhóm kết tương quan Việc phân cụm giúp để nhận biết thông tin khác tương quan với ví dụ khác, nên thấy đâu có điểm tương đồng phạm vi phù hợp Việc phân cụm làm theo hai cách Có thể giả sử có cụm điểm định sau sử dụng tiêu chí nhận dạng để xem liệu có khơng Đồ thị Hình 1.2 ví dụ Một ví dụ mẫu liệu kinh doanh so sánh tuổi khách hàng với quy mô bán hàng Hợp lý thấy người độ tuổi hai mươi (trước kết hôn nhỏ), độ tuổi năm mươi sáu mươi (khi khơng cịn nhà), có nhiều tiền tiêu Với đồ thị phân cụm đơn giản mà ta tạo cách sử dụng phần mềm đồ họa thích hợp để có nhìn nhanh chóng Các định phức tạp cần phải có gói phần mềm phân tích đầy đủ, đặc biệt định dựa vào thông tin lân cận Việc vẽ đồ thị theo phân cụm cách đơn giản để nhận lân cận Có thể nhận đối tượng riêng lẻ gần gũi theo nghĩa đen đối tượng đồ thị 11 Hình 1.3 Phân cụm 1.3.4 Dự báo Dự báo chủ đề rộng từ dự báo lỗi thành phần hay máy móc đến việc nhận gian lận chí dự báo lợi nhuận công ty Được sử dụng kết hợp với kỹ thuật khai phá liệu khác, dự báo gồm có việc phân tích xu hướng, phân loại, so khớp mẫu mối quan hệ Bằng cách phân tích kiện cá thể khứ, bạn đưa dự báo kiện Khi sử dụng quyền hạn thẻ tín dụng, chẳng hạn, bạn kết hợp phân tích định giao dịch riêng lẻ khứ với việc phân loại so khớp mẫu lịch sử để nhận biết liệu giao dịch có gian lận hay khơng Rất việc thực so khớp việc mua vé chuyến bay đến Mỹ giao dịch Mỹ cho thấy giao dịch hợp lệ 1.3.5 Các mẫu Thường sử dụng liệu dài hạn, mẫu phương pháp có ích để nhận biết xu hướng hay xuất thường xuyên kiện tương tự Ví dụ, với liệu khách hàng, nhận khách hàng mua sưu tập riêng lẻ sản phẩm nhiều thời điểm khác năm Trong ứng dụng giỏ hàng, sử dụng thông tin để tự động đề xuất số mặt hàng ... tắt đồ thị (graph summarization), khai phá đồ thị phổ biến (frequent graph mining)… Khai phá đồ thị phổ biến hướng nghiên cứu sôi động năm gần lĩnh vực khai phá liệu đồ thị Dựa tảng toán khai phá. .. phá luật kết hợp, khai phá đồ thị phổ biến nhằm tìm kiếm đồ thị phổ biến (tương ứng với tập mục phổ biến) Các đồ thị phổ biến tảng để giải tốn dự báo khơng gian liệu đồ thị có ứng rộng rãi nhiều... định đồ thị phổ biến đồ thị lớn Như trình bày trên, lĩnh vực khai phá liệu đồ thị thu kết quan trọng lý thuyết có ứng dụng hiệu việc giải số toán thực tiễn.Một toán ứng dụng khai phá đồ thị phổ biến