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

ĐẠ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

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

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

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

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

Knowleadge Discovery in Database KDD

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

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

ĐẶ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.

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]…

Đị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ể:

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ự:

- 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.

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

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

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ả

5 bước sau

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.

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.

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

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ị.

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

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.3.6. Cá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.3 cho 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.

Error triggered

Yes

Water lever > 15ft

Yes

Are pumps Working?

Send warning

Yes

Send alert

Send warning

Hình 1.4. Cây quyết định

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.4. Các ứng dụng của khai phá dữ liệu đồ thị

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

Phát hiện tri thức và khai phá dữ liệu được ứng dụng trong nhiều ngành

và lĩnh vực khác nhau như: tài chính ngân hàng, thương mại, y tế, giáo dục,

thống kê, máy học, trí tuệ nhân tạo, csdl, thuật toán toán học, tính toán song

song với tốc độ cao, thu thập cơ sở tri thức cho hệ chuyên gia,…

1.4.2.Ứng dụng của khai phá dữ liệu

Khai phá dữ liệu được vận dụng để giải quyết các vấn đề thuộc nhiều

lĩnh vực khác nhau. Chẳng hạn như giải quyết các bài toán phức tạp trong các

ngành đòi hỏi kỹ thuật cao, như tìm kiếm mỏ dầu, từ ảnh viễn thám, cảnh báo

hỏng hóc trong các hệ thống sản xuất; Được ứng dụng cho việc quy hoạch và

phát triển các hệ thống quản lý và sản xuất trong thực tế như dự đoán tải sử

dụng điện, mức độ tiêu thụ sản phẩm, phân nhóm khách hàng; Áp dụng cho các

vấn đề xã hội như phát hiện tội phạm, tăng cường an ninh…

Một số ứng dụng cụ thể như sau :

Khai phá dữ liệu được sử dụng để phân tích dữ liệu, hỗ trợ ra quyết định.

Trong sinh học: nó dùng để tìm kiếm , so sánh các hệ gen và thông tin di

chuyền, tìm mối liên hệ giữa các hệ gen và chuẩn đoán một số bệnh di chuyền

Trong y học: khai phá dữ liệu giúp tìm ra mối liên hệ giữa các triệu

chứng, chuẩn đoán bệnh.

Tài chính và thị trường chứng khoán: Khai phá dữ liệu để phân tích tình

hình tài chính, phân tích đầu tư, phân tích cổ phiếu

Khai thác dữ liệu web.

Trong thông tin kỹ thuật: khai phá dữ liệu dùng để phân tích các sai hỏng,

điều khiển và lập lịch trình…

Trong thông tin thương mại: dùng để phân tích dữ liệu người dùng, phân

tích dữ liệu marketing, phân tích đầu tư, phát hiện các gian lận.

Chương 2. CÁC PHƯƠNG PHÁP KHAI PHÁ ĐỒ THỊ CON

PHỔ BIẾN

2.1. Các định nghĩa về đồ thị con phổ biến

2.1.1. Giới thiệu về lý thuyết đồ thị

2.1.1.1. Định nghĩa cơ bản về đồ thị

Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh

này. Chúng ta phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nối

hai đỉnh nào đó của đồ thị. Để có thể hình dung được tại sao lại cần đến các loại

đồ thị khác nhau, chúng ta sẽ nêu ví dụ sử dụng chúng để mô tả một mạng máy

tính. Giả sử ta có một mạng gồm các máy tính và các kênh điện thoại (gọi tắt là

kênh thoại) nối các máy tính này. Chúng ta có thể biểu diễn các vị trí đặt náy tính

bởi các điểm và các kênh thoại nối chúng bởi các đoạn nối

Hình 2.1. Mô tả mô hình đồ thị

2.1.1.2. Các loại đồ thị

Hình 2.2. Các loại đồ thị

+ Đơn đồ thị vô huớng

Đồ thị G=(V, E) được gọi là đơn đồ thị vô hướng:

- V: Là tập các đỉnh

- E: là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V

V= {1, 2, 3, 4, 5}

E= {(1, 2), (1, 3), (1, 5), (2, 5), (3, 4), (3, 5), (4, 5)}

Hình 2.3. Đơn đồ thị vô hướng

+ Đa đồ thị vô huớng

Đồ thị G=(V, E) được gọi là đa đồ thị vô hướng:

- V: Là tập các đỉnh

- E: Là họ các cặp không có thứ tự gồm hai phần tử khác nhau của V.

Hai cạnh e1, e2 gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh

V= {1, 2, 3, 4, 5}

E= {(1, 2), (1, 3), (1, 5), (2, 5), (3, 4), (3, 5), (4, 5), (1, 2), (2, 1), (5, 2), (3,5)}

Hình 2.4. Đa đồ thị vô hướng

+ Giả đồ thị vô huớng

Đồ thị G=(V, E) được gọi là giả đồ thị vô hướng:

- V: Là tập các đỉnh

- E: Là họ các cặp không có thứ tự gồm hai phần tử không nhất thiết khác

nhau của V.

Cạnh e được gọi là khuyên nếu nó có dạng: e=(u, u)

V= {1, 2, 3, 4, 5}

E= {(1, 2), (1, 3), (1, 5), (2, 5), (3, 4), (3, 5), (4, 5), (1, 2), (2, 1), (5, 2), (3,5),

(2, 2), 3, 3)}

Hình 2.5. Giả đồ thị vô hướng

+ Đơn đồ thị có hướng

Đồ thị G=(V, E) được gọi là đơn đồ thị có hướng:

- V: Là tập cácđỉnh

- E: Là tập các cặp có thứ tự gồm hai phần tử khác nha ucủa V.(tập các

cung)

V= {1, 2, 3, 4, 5}

E= {(2, 1), (1, 3), (5, 1), (4, 2), (3, 4), (3, 5), (5, 4)}

Hình 2.6. Đơn đồ thị có hướng

+ Đa đồ thị có hướng

Đồ thị G=(V, E) được gọi là đơn đồ thị có hướng:

- V: Là tập các đỉnh

- E: Là họ các cặp có thứ tự gồm hai phần tử khác nhau của V.(tập các cung)

Hai cung e1, e2 được gọi là cung lặp nếu chúng cùng tương ứng với một

cặp đỉnh.

V= {1, 2, 3, 4, 5}

E= {(2, 1), (1, 3), (6, 2), (3, 4), (6, 3), (4, 6), (5, 4), (5, 6), (3, 1), (6, 2)}

Hình 2.7. Đa đồ thị có hướng

2.1.2. Khai phá dữ liệu

2.1.2.1. Khai phá dữ liệu

Khai phá dữ liệu được dùng để mô tả quá trình phát hiện ra tri thức trong

CSDL. Quá trình này kết xuất ra các tri thức tiềm ẩn từ dữ liệu giúp cho việc

dự báo trong kinh doanh, các hoạt động sản xuất, ... Khai phá dữ liệu làm giảm

chi phí về thời gian so với phương pháp truyền thống trước kia (ví dụ như

phương pháp thống kê).

Sau đây là một số định nghiã mang tính mô tả của nhiều tác giả về khai

phá dữ liệu.

 Định nghĩa của Ferruzza: “Khai phá dữ liệu là tập hợp các phương

pháp được dùng trong tiến trình khám phá tri thức để chỉ ra sự khác biệt các

mối quan hệ và các mẫu chưa biết bên trong dữ liệu”

 Định nghĩa của Parsaye: “Khai phá dữ liệu là quá trình trợ giúp quyết

định, trong đó chúng ta tìm kiếm các mẫu thông tin chưa biết và bất ngờ trong

CSDL lớn”

 Định nghĩa của Fayyad: “Khai phá tri thức là một quá trình không tầm

thường nhận ra những mẫu dữ liệu có giá trị, mới, hữu ích, tiềm năng và có thể

hiểu được”.

2.1.2.2. Các ứng dụng của khai phá dữ liệu

Phát hiện tri thức và khai phá dữ liệu liênquan đến nhiều ngành, nhiều lĩnh

vực: thống kê,trí tuệ nhân tạo, cơ sở dữ liệu, thu thập tính toán, tính toán song

song và tốc độ cao, thu thập tri thức cho các hệ chuyên gia, quan sát dữ liệu...

Đặc biệt phát hiện tri thức và khai phá dữ liệu rất gần gũi với lĩnh vực thống

kê, sử dụng các phương pháp thống kê để mô hình dữ liệu và phát hiện các

mẫu, luật ... Ngân hàng dữ liệu (Data Warehousing) và các công cụ phân tích

trực tuyến (OLAP- On Line Analytical Processing) cũng liên quan rất chặt chẽ

với phát hiện tri thức và khai phá dữ liệu.

Khai phá dữ liệu có nhiều ứng dụng trong thực tế, ví dụ như:

 Bảo hiểm, tài chính và thị trường chứng khoán: phân tích tình hình tài

chính và dự báo giá của các loại cổ phiếu trong thị trường chứng khoán. Danh

mục vốn và giá, lãi suất, dữ liệu thẻ tín dụng, phát hiện gian lận, ...

 Thống kê, phân tích dữ liệu và hỗ trợ ra quyết định.

 Điều trị y học và chăm sóc y tế: một số thông tin về chuẩn đoán bệnh

lưu trong các hệ thống quản lý bệnh viện. Phân tích mối liên hệ giữa các triệu chứng

bệnh, chuẩn đoán và phương pháp điều trị (chế độ dinh dưỡng, thuốc, ...)

 Sản xuất và chế biến: Quy trình, phương pháp chế biến và xử lý sự cố

 Text mining và Web mining: Phân lớp văn bản và các trang web, tóm

tắt văn bản,...

 Lĩnh vực khoa học: Quan sát thiên văn, dữ liệu gene, dữ liệu sinh vật

học, tìm kiếm, so sánh các hệ gene và thông tin di truyền, mối liên hệ gene và

một số bệnh di truyền, ...

 Mạng viễn thông: Phân tích các cuộc gọi điện thoại và hệ thống giám

sát lỗi, sự cố, chất lượng dịch vụ, ...

 Áp dụng trên một số lớp đồ thị như vô hướng, có hướng, có trọng số

hay gán nhãn. Cuối cùng là việc áp dụng của thuật toán so khớp đồ thị vào việc

phát hiện trang web giả mạo dựa vào cấu trúc DOM của chúng…

 Hệ thống phát hiện xâm nhập trái phép phát hiện sự truy cập và khai

thác hệ thống máy tính bất hợp pháp thông qua việc giám sát các hoạt động bất

thường của người sử dụng, dựa trên việc ứng dụng mạng nơ- ron, một kỹ thuật

học máy trong các hệ thống phát hiện xâm nhập.

2.1.3. Một số phương pháp khai phá dữ liệu

Khai phá dữ liệu là lĩnh vực mà con người luôn tìm cách đạt được mực

đích sử dụng thông tin của mình. Quá trình khai phá dữ liệu là quá trình phát

hiện mẫu, trong đó phương pháp khai phá dữ liệu để tìm kiếm các mẫu đáng

quan tâm theo dạng xác định. Có thể kể ra đây một vài phương pháp như: sử

dụng công cụ truy vấn, xây dựng cây quyết định, dựa theo khoảng cách (K-láng

giềng gần), giá trị trung bình, phát hiện luật kết hợp, … Các phương pháp trên

có thể được phỏng theo và được tích hợp vào các hệ thống lai để khai phá dữ

liệu theo thống kê trong nhiều năm nghiên cứu.

Tuy nhiên, với dữ liệu rất lớn trong kho dữ liệu thì các phương pháp này

cũng đối diện với thách thức về mặt hiệu quả và quy mô.

2.1.3.1. Các thành phần của giải thuật khai phá dữ liệu

Giải thuật khai phá dữ liệu bao gồm 3 thành phần chính như sau: biểu diễn

mô hình, kiểm định mô hình và phương pháp tìm kiếm.

Biểu diễn mô hình: Mô hình được biểu diễn theo một ngôn ngữ L nào đó

để miêu tả các mẫu có thể khai thác được. Mô tả mô hình rõ ràng thì học máy

sẽ tạo ra mẫu có mô hình chính xác cho dữ liệu. Tuy nhiên, nếu mô hình quá

lớn thì khả năng dự đoán của học máy sẽ bị hạn chế. Như thế sẽ làm cho việc

tìm kiếm phức tạp hơn cũng như hiểu được mô hình là không đơn giản hoặc sẽ

không thể có các mẫu tạo ra được một mô hình chính xác cho dữ liệu. Ví dụ

mô tả cây quyết định sử dụng phân chia các nút theo 1 trường dữ liệu, chia

không gian đầu vào thành các siêu phẳng song song với trục các thuộc tính.

Phương pháp cây quyết định như vậy không thể khai phá được dữ liệu dạng

công thức X = Y dù cho tập học có quy mô lớn thế nào đi nữa. Vì vậy, việc

quan trọng là người phân tích dữ liệu cần phải hiểu đầy đủ các giả thiết miêu

tả. Một điều cũng khá quan trọng là người thiết kế giải thuật cũng phải diễn tả

được các giả thiết mô tả nào được tạo ra bởi giải thuật nào. Khả năng miêu tả

mô hình càng lớn thì càng làm tăng mức độ nguy hiểm do bị học quá và làm

giảm đi khả năng dự đoán các dữ liệu chưa biết. Hơn nữa, việc tìm kiếm sẽ

càng trở lên phức tạp hơn và việc giải thích mô hình cũng khó khăn hơn.

Mô hình ban đầu được xác định bằng cách kết hợp biến đầu ra (phụ thuộc)

với các biến độc lập mà biến đầu ra phụ thuộc vào. Sau đó phải tìm những tham

số mà bài toán cần tập trung giải quyết. Việc tìm kiếm mô hình sẽ đưa ra được

một mô hình phù hợp với tham số được xác định dựa trên dữ liệu (trong một số

trường hợp khác thì mô hình và các tham số lại thay đổi để phù hợp với dữ

liệu). Trong một số trường hợp, tập các dữ liệu được chia thành tập dữ liệu học

và tập dữ liệu thử. Tập dữ liệu học được dùng để làm cho tham số của mô hình

phù hợp với dữ liệu. Mô hình sau đó sẽ được đánh giá bằng cách đưa các dữ

liệu thử vào mô hình và thay đổi các tham số cho phù hợp nếu cần. Mô hình

lựa chọn có thể là phương pháp thống kê như SASS, … một số giải thuật học

máy (ví dụ như cây quyết định và các quyết định học có thầy khác), mạng

neuron, suy diễn hướng tình huống (case based reasoning), các kỹ thuật phân

lớp.

Kiểm định mô hình (model evaluation): Là việc đánh giá, ước lượng các

mô hình chi tiết, chuẩn trong quá trình xử lý và phát hiện tri thức với sự ước

lượng có dự báo chính xác hay không và có thoả mãn cơ sở logic hay không?

Ước lượng phải được đánh giá chéo (cross validation) với việc mô tả đặc điểm

bao gồm dự báo chính xác, tính mới lạ, tính hữu ích, tính hiểu được phù hợp

với các mô hình. Hai phương pháp logic và thống kê chuẩn có thể sử dụng trong

mô hình kiểm định.

Phương pháp tìm kiếm: Phương pháp này bao gồm hai thành phần: tìm

kiếm tham số và tìm kiếm mô hình. Trong tìm kiếm tham số, giải thuật cần tìm

kiếm các tham số để tối ưu hóa các tiêu 19 chuẩn đánh giá mô hình với các dữ

liệu quan sát được và với một mô tả mô hình đã định. Việc tìm kiếm không cần

thiết đối với một số bài toán khá đơn giản: các đánh giá tham số tối ưu có thể

đạt được bằng các cách đơn giản hơn. Đối với các mô hình chung thì không có

các cách này, khi đó giải thuật “tham lam” thường được sử dụng lặp đi lặp lại.

Ví dụ như phương pháp giảm gradient trong giải thuật lan truyền ngược

(backpropagation) cho các mạng neuron. Tìm kiếm mô hình xảy ra giống như

một vòng lặp qua phương pháp tìm kiếm tham số: mô tả mô hình bị thay đổi

tạo nên một họ các mô hình. Với mỗi một mô tả mô hình, phương pháp tìm

kiếm tham số được áp dụng để đánh giá chất lượng mô hình. Các phương pháp

tìm kiếm mô hình thường sử dụng các kỹ thuật tìm kiếm heuristic vì kích thước

của không gian các mô hình có thể thường ngăn cản các tìm kiếm tổng thể, hơn

nữa các giải pháp đơn giản (closed form) không dễ đạt được.

2.1.3.2. Phương pháp suy diễn/quy nạp

Một cơ sở dữ liệu là một kho thông tin nhưng các thông tin quan trọng

hơn cũng có thể được suy diễn từ kho thông tin đó. Có hai kỹ thuật chính để

thực hiện việc này là suy diễn và quy nạp.

Phương pháp suy diễn: Nhằm rút ra thông tin là kết quả logic của các

thông tin trong cơ sở dữ liệu. Ví dụ như toán tử liên kết áp dụng cho bảng quan

hệ, bảng đầu chứa thông tin về các nhân viên và phòng ban, bảng thứ hai chứa

các thông tin về các phòng ban và các trưởng phòng. Như vậy sẽ suy ra được

mối quan hệ giữa các nhân viên và các trưởng phòng. Phương pháp suy diễn

dựa trên các sự kiện chính xác để suy ra các tri thức mới từ các thông tin cũ.

Mẫu chiết xuất được bằng cách sử dụng phương pháp này thường là các luật

suy diễn.

Phương pháp quy nạp: phương pháp quy nạp suy ra các thông tin được

sinh ra từ cơ sở dữ liệu. Có nghĩa là nó tự tìm kiếm, tạo mẫu và sinh ra tri thức

chứ không phải bắt đầu với các tri thức đã biết trước. Các thông tin mà phương

pháp này đem lại là các thông tin hay các tri thức cấp cao diễn tả về các đối

tượng trong cơ sở dữ liệu. Phương pháp này liên quan đến việc tìm kiếm các

mẫu trong CSDL. Trong khai phá dữ liệu, quy nạp được sử dụng trong cây

quyết định và tạo luật.

2.1.3.3. Phương pháp phát hiện luật kết hợp

Phương pháp này nhằm phát hiện ra các luật kết hợp giữa các thành phần

dữ liệu trong cơ sở dữ liệu. Mẫu đầu ra của giải thuật khai phá dữ liệu là tập

luật kết hợp tìm được. Ta có thể lấy một ví dụ đơn giản về luật kết hợp như sau:

sự kết hợp giữa hai thành phần A và B có nghĩa là sự xuất hiện của A trong bản

ghi kéo theo sự xuất hiện của B trong cùng bản ghi đó: A => B.

Cho một lược đồ R={A1, …, Ap} các thuộc tính với miền giá trị {0,1},

và một quan hệ r trên R.

Một luật kết hợp trên r được mô tả dưới dạng X=>B với X  R và B 

R\X. Về mặt trực giác, ta có thể phát biểu ý nghĩa của luật như sau: nếu một

bản ghi của bảng r có giá trị 1 tại mỗi thuộc tính thuộc X thì giá trị của thuộc

tính B cũng là 1 trong cùng bản ghi đó. Ví dụ như ta có tập cơ sở dữ liệu về các

mặt hàng bán trong siêu thị, các dòng tương ứng với các ngày bán hàng, các

cột tương ứng với các mặt hàng thì giá trị 1 tại ô (20/10, bánh mì) xác định rằng

bánh mì đã bán ngày hôm đó cũng kéo theo sự xuất hiện giá trị 1 tại ô (20/10,

bơ).

Cho W  R, đặt s(W,r) là tần số xuất hiện của W trong r được tính bằng

tỷ lệ của các hàng trong r có giá trị 1 tại mỗi cột thuộc W. Tần số xuất hiện

của luật X=>B trong r được định nghĩa là s(X  {B}, r) còn gọi là độ hỗ trợ

của luật, độ tin cậy của luật là s(X  {B}, r)/s(X, r). Ở đây X có thể gồm nhiều

thuộc tính, B là giá trị không cố định. Nhờ vậy mà không xảy ra việc tạo ra các

luật không mong muốn trước khi quá trình tìm kiếm bắt đầu. Điều đó cũng cho

thấy không gian tìm kiếm có kích thước tăng theo hàm mũ của số lượng các

thuộc tính ở đầu vào. Do vậy cần phải chú ý khi thiết kế dữ liệu cho việc tìm

kiếm các luật kết hợp.

Nhiệm vụ của việc phát hiện các luật kết hợp là phải tìm tất cả các luật

X=>B sao cho tần số của luật không nhỏ hơn ngưỡng σ cho trước và độ tin cậy

của luật không nhỏ hơn ngưỡng θ cho trước. Từ một cơ sở dữ liệu ta có thể tìm

được hàng nghìn và thậm chí hàng trăm nghìn các luật kết hợp.

Ta gọi một tập con X  R là thường xuyên trong r nếu thỏa mãn điều kiện

s(X, r)≥σ. Nếu biết tất cả các tập thường xuyên trong r thì việc tìm kiếm các

luật rất dễ dàng. Vì vậy, giải thuật tìm kiếm các luật kết hợp trước tiên đi tìm

tất cả các tập thường xuyên này, sau đó tạo dựng dần các luật kết hợp bằng cách

ghép dần các tập thuộc tính dựa trên mức độ thường xuyên.

Các luật kết hợp có thể là một cách hình thức hóa đơn giản. Chúng rất

thích hợp cho việc tạo ra các kết quả có dữ liệu dạng nhị phân. Giới hạn cơ bản

của phương pháp này là ở chỗ các quan hệ cần phải thưa theo nghĩa không có

tập thường xuyên nào chứa nhiều hơn 15 thuộc tính. Giải thuật tìm kiếm các

luật kết hợp tạo ra số luật ít nhất phải bằng với số các tập phổ biến và nếu như

một tập phổ biến có kích thước K thì phải có ít nhất là 2K tập phổ biến. Thông

tin về các tập phổ biến được sử dụng để ước lượng độ tin cậy của các tập luật

kết hợp.

2.1.4. Khai phá đồ thị con phổ biến

Định nghĩa 1: Cho D là một tập dữ liệu đồ thị, D ={G0, G1, G2, ... Gn},

ngưỡng hỗ trợ tối thiểu minFreq 0,1. Ký hiệu δ(g, G), với g là một đồ thị,

GD, được xác định như sau:

δ(g, G) = { 1Nếu g đẳng cấu với một đồ thị con trong G 0 Nếu g không đẳng cấu với bất kỳ đồ thị con nào trong G

Ký hiệu σ(g, D) được gọi là độ phổ biến của đồ thị g trong tập dữ liệu đồ

thị D và được xác định như sau:

σ(g, D) = ∑ δ(g, Gi ) GiD

Bài toán tìm đồ thị con phổ biến g là bài toán tìm các đồ thị con g trong

tập dữ liệu đồ thị D sao cho độ phổ biến của đồ thị g trong tập dữ liệu đồ thị D

không nhỏ hơn ngưỡng hỗ trợ tối thiểu minFreq,

σ(g, D)  minFreq

Định nghĩa 2: Ta định nghĩa cây phổ biến t là cực đại nếu không có một

cây trên thực sự nào của t là phổ biến và là cây phổ biến đóng (closed) nếu

không có một cây trên thực sự nào của t lại có độ hỗ trợ như t.

Tập các cây con phổ biến, tập các cây con phổ biến đóng và tập các cây

con phổ biến cực đại thỏa mãn tính chất sau:

Bổ đề 2. Đối CSDL D và minsup cho trước, giả sử F là tập các cây con

phổ biến, C là tập các cây con phổ biến đóng và M là tập các cây con phổ biến

cực đại, ta có M  C  F.

Bổ đề 3. Chúng ta có thể nhận được tất cả các cây con phổ biến từ các cây

con phổ biến cực đại hoặc từ các cây con phổ biến đóng cùng với các giá đỡ

(supports) của chúng.

2.2. Các phương pháp khai phá đồ thị con phổ biến

2.2.1 . Thuật toán Apriori để tìm tập con phổ biến

2.2.1.1. Giới thiệu

Apriori là thuật toán khả sinh được đề xuất bởi R. Agrawal và R. Srikant

vào năm 1993 để khai thác các tập item đối với các luật kết hợp kiểu bool. Tên của

thuật toán dựa trên việc thuật toán sử dụng tri thức trước (prior knowledge) của các

thuộc tính tập item phổ biến, chúng ta sẽ thấy sau đây. Apriori dùng cách tiếp cận

lặp được biết đến như tìm kiếm level-wise, với các tập k item được dùng để thăm

dò các tập (k+1) item. Đầu tiên, tập các tập 1 item phổ biến được tìm thấy bằng cách

quét cơ sở dữ liệu để đếm số lượng từng item, và thu thập những item thỏa mãn độ

hỗ trợ tối thiểu. Tập kết quả đặt là L1. Tiếp theo, L1 được dùng để tìm L2, tập các tập

2 item phổ biến, nó được dùng để tìm L3, và cứ thế tiếp tục, cho tới khi tập k item

phổ biến không thể tìm thấy. Việc tìm kiếm cho mỗi Lk đòi hỏi một lần quét toàn bộ

cơ sở dữ liệu.

Trước khi đi vào chi tiết của thuật toán Apriori đầu tiên chúng ta sẽ tìm

 Itemset- Itemset là tập hợp của những item trong cơ sở dữ liệu mà nó

hiểu xác định một vài thuật ngữ phổ biến được sử dụng trong thuật toán.

 Transaction- Transaction là một thành phần cơ sở dữ liệu mà nó bao

được xác định bởi I={i1, i2,…. in}, trong đó n là số lượng item.

gồm tập hợp các item. Transaction được ký hiệu là T và T I. Một Transaction

chứa tâp hợp các item T={i1, i2,…. in}.

 Minimum support – Minimum support là điều kiện cần được đáp ứng

bởi các item đề ra để có thể tiến hành xử lý item kế tiếp có thể. Minimum

support có thể được xem như là một điều kiện giúp loại bỏ các tâp không phổ

biến trong bất kỳ cơ sở dữ liệu. Thường sử dụng Minimum support cho mô

 Frequent itemset (tập phổ biến) - các Itemset đáp ứng các tiêu chí điều

hình tỷ lệ phần trăm.

kiện minimum support thì được gọi là tập phổ biến. Nó được ký hiệu là Li trong

 Candidate itemset (ứng viên tập phổ biến) - ứng viên tập phổ biến là

đó i chỉ i-itemset.

các item chỉ được xem xét xử lý. Ứng viên tập phổ biến là tất cả các kết hợp có thể

 Support – Độ hữu dụng của một luật có thể được đo với sự giúp đỡ

có của tập phổ biến. Nó thường được ký hiệu Ci trong đó I chỉ i-itemset.

của ngưỡng hỗ trợ. Support giúp chúng ta đo như thế nào các giao tác có tập

phổ biến mà nó phù hợp với ý nghĩa cả hai phía cạnh trong luật kết hợp.

Xem xét hai item A và b. Để tính toán support của A->B theo công thức

(𝑠ố 𝑙ượ𝑛𝑔 𝑔𝑖𝑎𝑜 𝑑ị𝑐ℎ 𝑔ồ𝑚 𝑐ả 𝐴 𝑣à 𝐵)

như sau:

𝑇ổ𝑛𝑔 𝑠ố 𝑙ượ𝑛𝑔 𝑔𝑖𝑎𝑜 𝑑ị𝑐ℎ

Supp(A->B) =

Confidence – Confidence chỉ sự chắc chắn của các luật. Thông số

này cho phép chúng ta đếm mức độ thường xuyên một giao tác của tập phổ

biến phù hợp với ý nghĩa cả phía cạnh bên trái với phía cạnh bên phải. các tập

phổ biến không đáp ứng các điều kiện trên có thể được loại bỏ.

Xem xét hai item A và B. Để tính toán confidence của A->B theo công

𝑠ố 𝑙ượ𝑛𝑔 𝑔𝑖𝑎𝑜 𝑑ị𝑐ℎ 𝑔ồ𝑚 𝑐ả 𝐴 𝑣à 𝐵

thức sau:

𝐺𝑖𝑎𝑜 𝑑ị𝑐ℎ 𝑏𝑎𝑜 𝑔ồ𝑚 𝑐ℎỉ 𝐴

Conf(A->B) =

Chú ý: Conf(A->B) có thể không bằng conf(B->A)

Để tăng hiệu quả của việc phát sinh level-wise của tập item phổ biến,

một tính chất quan trọng gọi là tính chất Apriori (Apriori property), được

giới thiệu dưới đây, dùng để giảm không gian tìm kiếm. Chúng ta sẽ mô tả tính

chất này trước, rồi mới xem một ví dụ minh họa cách sử dụng nó.

Tính chất Apriori : Tất cả các tập con không rỗng của một tập item phổ biến

cũng phải là phổ biến.

Tính chất Apriori này dựa theo nhận xét sau. Theo định nghĩa, nếu một

tập item I không thỏa ngưỡng độ hỗ trợ tối thiểu, min_sup, thì I không là phổ

biến, do đó, P(I)< min_sup. Nếu một item A được thêm vào tập item I, thì tập

item được tạo thành (vd, I A) không thể xuất hiện thường xuyên hơn I. Do

đó, I A cũng không phổ biến; do đó, P(I A) < min_sup.

Tính chất này thuộc về loại đặc biệt của các thuộc tính gọi là chống đơn

điệu (antimonotone) trong nghĩa rằng nếu một tập không thể qua một cuộc

kiểm tra, tất cả các tập cha (superset) của nó cũng sẽ thất bại với một cuộc

kiểm tra tương tự. Đó gọi là chống đơn điệu là vì thuộc tính này là đơn điệu

(monotonic) trong ngữ cảnh của việc thất bại một cuộc kiểm tra.

2.2.1.2. Thuật toán Apriori

Apriori dùng cách tiếp cận lặp được biết đến như tìm kiếm level-wise, với

các tập k item được dùng để thăm dò các tập (k+1) item.

1. Đầu tiên, tập (frequent 1- itemsets) phổ biến 1 được tìm thấy ký hiệu là C1

2. Bước tiếp theo là tính support có nghĩa là sự xuất hiện của các item

trong cơ sở dữ liệu. Điều này đòi hỏi phải duyệt qua toàn bộ cơ sở dữ liệu.

3. Sau đó, bước cắt tỉa được thực hiện trên C1 trong đó những item được

so sánh với thông số minimum support. Những item thỏa điều kiện minimum

support mới được xem xét cho tiến trình tiếp theo ký hiệu là L1.

4. Sau đó, bước phát sinh các bộ ứng viên được thực hiện trong đó tập

phổ biến 2 được tạo ra ký hiệu là C2.

5. Một lần nữa, cở sở dữ liệu được duyệt để tính toán support của 2 tập

phổ biến. Theo minimum support, các bộ ứng viên tạo ra được kiểm tra và chỉ

những tập phổ biến nào thỏa điều kiện minimum support thì tiếp tục được sử

dụng tạo ra bô ứng viên tập phổ biến 3.

Bước trên tiếp tục cho đến khi không có tập phổ biến hoặc bộ ứng viên có

thể được tạo ra.

2.2.1.3. Ví dụ thuật toán Apriori

Bảng 2.1 biểu diễn một giao dịch cơ sở dữ liệu có 4 giao dịch.

TID là một nhận dạng duy nhất cho mỗi giao dịch.

Bảng 3.1 Biểu diễn giao dịch

Bảng 2.1. Biểu diễn giao dịch

TID Items

T001 {A,C,D}

T002 {B,C,E}

T003 {A,B,C,E}

T004 {B,E}

Thực hiện bước đầu tiên là chức năng duyệt cơ sở dữ liệu để xác định số

lượng sự xuất hiện cho một item cụ thể. Sau bước đầu tiên chúng ta sẽ có C1

được thể hiện trong Bảng 2.2.

Bảng 2.2. Biểu diễn giao dịch

Itemset Support

{A} 2

{B} 3

{C} 3

{D} 1

{E} 3

Bước tiếp theo là bước cắt tỉa, trong đó support tập phổ biến được so sánh

với minimum support. Các tập phổ biến thỏa măn minimum support sẽ được

xử lý tiếp tục. Giả sử rằng minimum support là 2. Chúng ta sẽ có được L1 từ

bước này. Bảng 2.3 cho thấy kết quả cắt tỉa.

Bảng 2.3. Biểu diễn giao dịch

Itemset Support

{A} 2

{B} 3

{C} 3

{E} 3

Bây giờ bước tiếp theo phát sinh ứng viên được thực hiện trong đó tất cả ứng

viên có thể có 2 tập phổ biến ứng viên được tạo. Bảng này được ký hiệu là C2. Bảng

2.4 cho thấy tất cả khả năng kết hợp mà có thể tạo ra từ tập phổ biến.

Bảng 2.4. Biểu diễn giao dịch

Itemset Support

{A,B} 1

{A,C} 2

{A,E} 1

{B,C} 2

{B,E} 3

{C,E} 2

Bây giờ cắt tỉa phải được thực hiện trên cơ sở các điều kiện minimum

support. Từ Bảng 2.4 hai tập phổ biến sẽ được loại bỏ. Sau khi cắt tỉa chúng ta

nhận được kết quả như sau:

Bảng 2.5. Biểu diễn giao dịch

Itemset Support

{A,C} 2

{B,C} 2

{B,E} 3

{C,E} 2

Các quá trình tương tự được tiếp tục cho đến khi không có tập phổ biến hoặc

bộ ứng viên có thể tạo ra. Tiến trình được mô tả trong Bảng 2.6 và Bảng 2.7

Bảng 2.6. Biểu diễn giao dịch

Itemset Support

{A,B,C} 1

{A,B,E} 1

{B,C,E} 2

Bảng 2.7. Kết quả cuối cùng

Itemset Support

{B,C,E} 2

Mã giả thuật toán:

Apriori_Algorithm()

{

Ck: Candidate itemset of size k

Lk : frequent itemset of size k

L1 = {frequent items};

for (k = 1; Lk!=0; k++)

{

Ck+1 = candidates generated from Lk;

foreach transaction t in database do

increment the count of all candidates in Ck+1

that are contained in t

Lk+1 = candidates in Ck+1 with min_support

}

return CkLk;

}

 Số lượng lớn tập phổ biến được tạo ra làm gia tăng sự phức tạp không

Hạn chế của thuật toán Apriori:

 Quá nhiều lần duyệt cơ sở dữ liệu được yêu cầu vì số lượng lớn tập

gian.

 Khi số lần duyệt cơ sở dữ liệu nhiều làm gia tăng sự phức tạp thời gian

phổ biến được tạo. Với I = i1, i2,…,i100 thì số lầ duyệt CSDL sẽ là 100 lần.

 Thực hiện việc tính độ phổ biến nhiều, đơn điệu.

khi cơ sở dữ liệu gia tăng. Số lượng tập ứng viên rất lớn: 2100-1

Do những hạn chế đó, một điều cần thiết phải đưa ra một số thay đổi

trong thuật toán Apriori mà chúng ta sẽ thấy thêm trong phần sau để cải tiến

 Giảm số lần duyệt CSDL

 Giảm số lượng tập ứng viên

 Qui trình tính độ phổ biến thuận tiện hơn

Apriori : ý tưởng chung

2.2.2. Thuật toán FSG (Frequency SubGraph Mining) để phát hiện cộng

đồng mạng xã hội

2.2.2.1. Giới thiệu

Thuật toán FSG (Frequency SubGraph Mining) là thuật toán mở rộng dựa

trên thuật toán thuật toán Apriori. Thuật toán FSG được sử dụng trong các bài

toán về đồ thị, dựa trên việc kết hợp các đồ thị con (subgraph), thường áp dụng

cho việc tìm kiếm tất cả các đồ thị con kết nối xuất hiện thường xuyên trong

một cơ sở dữ liệu đồ thị lớn. Thuật toán FSG tìm các đồ thị con thường xuyên

sử dụng cùng cấp được thông qua bởi thuật toán Apriori mở rộng. Các tính

năng chính của FSG như sau:

- Nó sử dụng một đồ thị rời rạc được tối ưu hóa về cả lưu trữ và tính toán,

- Nó làm tăng kích thước của subgraphs thường xuyên bằng cách thêm

một cạnh tại một thời điểm, cho phép tạo ra các ứng cử viên hiệu quả

- Nó sử dụng các thuật toán đơn giản để ghi nhãn kinh điển và tính đẳng

cấu của đồ thị mà nó thấy hiệu quả đối với các đồ thị nhỏ,

- Nó kết hợp tối ưu hóa khác nhau cho đồ thị con và cho phép nó để mở

rộng cơ sở dữ liệu đồ thị lớn.

Vấn đề phát hiện subgraph thường xuyên có nguồn gốc trong những năm

chín mươi đầu với việc xây dựng thuật toán cho thị trường giỏ phân tích. Công

việc này đã được theo sau bởi sự phát triển của nhiều khái niệm mới và bây giờ

chúng ta có nhiều thuật toán cho việc phát hiện đồ thị con, khai thác các thuật

toán khác nhau.

2.2.2.2. Cách tiếp cận của thuật toán FSG

Cách tiếp cận của Thuật toán FSG tương tự như thuật toán Apriori. Quá

trình phát hiện subgraph thường xuyên có thể được chia thành hai bước chính.

+ Bước đầu tiên là tìm subgraph dựa trên dữ liệu đã có chiến lược tìm kiếm.

+ Bước tiếp theo là kết hợp chúng trong các đồ thị / đồ thị được sử dụng

subgraph

Nhìn chung, thuật toán FSG bị ảnh hưởng bởi bốn khía cạnh sau bị ảnh

hưởng của việc thực hiện các thuật toán và cũng một phần do dữ liệu đầu vào

của chúng:

+ Biểu diễn đồ thị;

+ Tạo Subgraph;

+ Phương pháp tiếp cận thuật toán;

+ Đánh giá tần suất.

2.2.2.3. Minh họa thuật toán FSG (Frequent Subgraph Mining)

Hình 2.8. Minh họa thuật toán FSG

Tương tự như thuật toán Apriori, nhưng áp dụng trong đồ thị, ta thực hiện

như sau:

Cho giá trị minimum support

Bước 1: hình thành các subgraph của cùng 1 đỉnh trong ma trận

Bước 2: Join các subgraph của 2 đỉnh với nhau để hình thành các subgraph con

thỏa điều kiện minimum support.

Khi thực hiện FSG sẽ có các trường hợp:

-Trường hợp 1: hình thành các subgraph của các đỉnh là khác nhau

- Trường hợp 2: các subgraph có nhiều dạng thể hiện

- Trường hợp 3: ngoài việc kết hợp 2 đồ thị khác nhau, FSG có thể kết

hợp chính nó

Thuật toán FSG:

- Ký hiệu: k-đồ thị con là một đồ thị con với k cạnh.

- Khởi động: Quét các giao dịch để tìm F1, tập hợp tất cả thường xuyên 1

đồ thị con và 2 đồ thị con cùng số đếm với nhau;

For (k = 3; F k-1  ; k ++)

1. Thế hệ ứng viên (Candidate Generation): Ck, tập các ứng cử viên k -

subgraphs, từ Fk-1, bộ thường xuyên -subgraphs (k-1);

2. Các ứng viên dán nhãn (Candidates labeling): Một điều kiện cần thiết

của ứng cử viên thường xuyên là mỗi bước (k-1) của nó là thường xuyên.

3. Đếm tần số: Quét các giao dịch để đếm số lần xuất hiện của đồ thị con

trong Ck;

4. F k = {c  CK | c có số lượng không ít hơn #minSup}

5. Return F1  F2  ......  Fk (= F)

Trong đó:

Thế hệ ứng viên: Để xác định hai ứng viên tham gia, chúng ta cần phải

kiểm tra tính đẳng số của đồ thị. Bước này tạo ra ứng viên mới dựa trên số item

mà mình đang kiểm và những ứng viên cũ của mình mà đã duyệt rồi.

Ứng viên dán nhãn: Để kiểm tra thuộc tính đóng của đồ thị, chúng ta cần

tính đẳng số của đồ thị. Bước này dùng để tạo ra một cái ID key cho một

subgraph.

Đếm tần số: Quét các giao dịch để đếm các lần xuất hiện của subgraph

trong đó. Dùng canonical labeling để kiểm tra các subgraph có nằm trong

Candidate Generation đó hay không.

2.2.2.4. Các trường hợp/vấn đề khi thực hiện thuật toán này trong thực tế

- Đối với một số tương đối lớn các loại khác nhau của các đối tượng và

các mối quan hệ tồn tại thì FSG đã có thể đạt được tốt hiệu suất và quy mô

tuyến tính với kích thước cơ sở dữ liệu. Trong thực tế, FSG tìm thấy tất cả các

kết nối thường xuyên đồ thị con trong vòng chưa đầy 500 giây từ bộ dữ liệu

tổng hợp bao gồm 80000 đồ thị với sự hỗ trợ ngưỡng 2%.

- Đối với những vấn đề mà số nhãn cạnh và đỉnh nhỏ, hiệu suất của FSG

thì lại không tốt, như mức độ phức tạp hàm mũ của phép đẳng cấu đồ thị chiếm

lợi thế trong hiệu suất tổng thể.

- Thuật toán FSG khi thực hiện duyệt các đồ thị con thì thường thường tìm

và so khớp toàn bộ đối với tất cả các đồ thị con trong dữ liệu. Việc này gây khó

khăn, mất thời gian và có rất ít đồ thị con đáp ứng dẫn đến không giải được bài

toán đặt ra và quá phức tạp.

2.2.3. Thuật toán Light-FSG

Thuật toán FSG có một số vấn đề như sau. Thứ nhất, trong lý thuyết đồ

thị và phức tạp, vấn đề clique là một vấn đề NP-Complete, có nghĩa là "dễ

dàng" để xác minh một giải pháp nhất định trong một cách dưới mức Thời gian

(ví dụ: "đồ thị con này thuộc đồ thị" hay "là biểu đồ này Clique "), nhưng nó

là" khó "để tìm ra một giải pháp một cách hiệu quả. FSG có thể thực hiện tốt

đối với một vài nút hoặc với đồ thị mật độ thấp, nhưng thời gian thực hiện có

xu hướng phát triển thực sự nhanh với số nút quá nhiều. Độ phức tạp tính toán

của nó là trên O(n3).

Vì vậy, khi xử lý mạng xã hội với thuật toán FSG thì hoàn toàn không khả

thi và hiệu quả với quy mô của bài toán đặt ra. Do đó tôi áp dụng thuật toán

mới, có tên là Light-FSG vẫn là một sự lựa chọn tối ưu trong trường hợp này

vì một số lý do sau:

- Thời gian duyệt các đồ thị con trong FSG mất khá nhiều thời gian do

thuật toán phải tìm duyệt tất cả các đồ thị con phải giống (tương tự).

- Để thực hiện thuật toán FSG thì phải có một hệ thống máy chủ mạnh để

có thể tính toán/tìm duyệt các đồ thị con trong thời gian ngắn.

Thuật toán Light-FSG:

- Ký hiệu: k-đồ thị con là một đồ thị con với k cạnh.

- Khởi động: Quét các giao dịch để tìm F1, tập hợp tất cả thường xuyên 1

đồ thị con và 2 đồ thị con cùng số đếm với nhau;

For (k = 3; F k-1  ; k ++)

1. Thế hệ ứng viên (Candidate Generation): Ck, tập các ứng cử viên k -

subgraphs, từ Fk-1, bộ thường xuyên -subgraphs (k-1);

2. Đếm tần số: Quét các giao dịch để đếm số lần xuất hiện của đồ thị con

trong Ck;

F k = {c  CK | c có số lượng không ít hơn #minSup}

Return F1  F2  ......  Fk (= F)

Trong đó:

Thế hệ ứng viên: Để xác định hai ứng viên tham gia, chúng ta cần phải

kiểm tra xem ứng viên có phù hợp với yêu cầu về minsup hay không.

Đếm tần số: Tính đẳng số Subgraph để kiểm tra việc ngăn chặn một đồ thị

con thường xuyên.

Như vậy so với giải thuật FSG gốc, giải thuật Light-FSG bỏ qua bước cắt

tỉa, tức là bước đếm lại đồ thị gốc để xác định số lần xuất hiện của đồ thị con

ứng viên. Đồ thị con ứng viên sẽ được kết nối với các đồ thị con thoả yêu cầu

minsup đã tìm thấy trước đó để tạo thành đồ thị con mới. Các đồ thị con cuối

cùng tìm thấy được theo cách này sẽ là các cộng đồng được tìm thấy.

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

2.3.1. Cộng đồng mạng xã hội

Khi xem xét về khái niệm cộng đồng, một thuộc tính quan trọng là tính

kết nối. Như vậy trong một cộng đồng, phải có đường đi giữa mỗi cặp đỉnh

của nó. Ở đây, chúng ta xem xét phân biệt ba lớp định nghĩa: cục bộ, toàn cục

và dựa trên độ tương đồng đỉnh.

Định nghĩa cục bộ: là một phần của đồ thị có ít gắn kết với phần còn lại

của đồ thị. Như vậy cộng đồng sẽ có tính độc lập tương đối so với phần còn lại và

bên cạnh đó có một vài tính chất giữa các đỉnh: có tính kết nối giữa bất kỳ các cặp

đỉnh nào, khả năng tiếp cận, sự phân biệt về tính gắn kết trong và ngoài.

Về góc độ toàn cục: các cộng đồng nhìn chung vẫn là một phần của mạng

toàn thể, chúng không thể tách ra khỏi mạng xã hội toàn thể mà không làm ảnh

hưởng đến mạng.

Về góc độ đỉnh, cộng đồng là các nhóm có đỉnh tương đối giống nhau, sự

giống nhau này được đo đạc dựa trên các độ đo, so sánh truyền thống.

Nhìn chung, cộng đồng là một nhóm các cá nhân, tập các thực thể trên

mạng 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. Trên thực tế, các cộng đồng được đề cập đến trong một bối cảnh xã hội

xác định, con người có xu hướng kết hợp lại với nhau, hình thành các nhóm

trong cùng một khu vực, môi trường làm việc, gia đình, bạn bè…

Hình 2.9. Cộng đồng mạng xã hội đơn giản với 3 cộng đồng

Trong hình trên, là một ví dụ đơn giản về một cách phân chia mạng xã

hội thành 3 cộng đồng con. Sự chia tách mạng là sự phân chia đồ thị thành các

cộng đồng, mỗi nút sẽ thuộc về một cộng đồng. Trong thực tế, thì nút có thể

thuộc nhiều cộng đồng. Số cộng đồng có thể k khi phân chia một mạng n đỉnh

là một số tính theo hàm mũ. Như vậy, giá trị tăng nhanh theo hàm số mũ và

việc tính ra các cách phân chia đồ thị là không thể, vì khối lượng tính toán quá

lớn nếu n lớn.

Trong một đồ thị ngẫu nhiên sự phân bố các cạnh giữa các đỉnh là rất

đồng nhất, vì nó tuân theo phân phối Poissonian, vì vậy hầu hết các nút có bậc

(degree) tương đương. Thế giới mạng thực không phải đồ thị ngẫu nhiên,

chúng thể hiện sự không đồng nhất lớn, có mức độ trật tự và tổ chức cao. Sự

phân bố bậc theo chiều rộng và không phụ thuộc vào quy mô, nhiều nút với

bậc thấp cùng tồn tại với các nút có bậc lớn.

Hơn nữa, sự phân bố của các cạnh là không toàn bộ, nhưng cũng không

đồng nhất tại địa phương, với mật độ cao của các cạnh trong các nhóm đặc biệt

của các nút, và mật độ thấp giữa các nhóm này. Tính năng này của các mạng

thế giới thực được gọi là cấu trúc cộng đồng. Vấn đề hiểu được cấu trúc cộng

đồng của mạng chính là sự phát hiện, khai phá cộng đồng.

Theo Santo Fortunato trong báo cáo năm 2010 đã tổng hợp các phương

pháp phát hiện cộng đồng trong mạng xã hội. Trong đó, các nhóm phương

pháp đ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 phương pháp phát hiện cộng đồng động

2.3.2. Các phương pháp truyền thống

Gồm 4 phương pháp, đó là phân vùng đồ thị, phân cụm phân cấp, phân

cụm theo vùng và phân cụm theo phổ. Nội dung tóm lược của từng phương

pháp như sau:

+ Phương pháp phân vùng đồ thị có mục tiêu là tìm được một phép

chia đồ thị thành g nhóm với kích thước xác định trước, sao cho số lượng

các cạnh nằm giữa các nhóm là tối thiểu. Trong phương pháp này, việc xác

định số cụm được phân chia thành, cũng như kích thước của mỗi cụm đó

là cần thiết. Phương pháp phân vùng đồ thị được áp dụng chủ yếu trong tính

toán song song, phân vùng mạch và một số các giải thuật nối tiếp

Hình 2.10. Phương pháp phân vùng đồ thị

+ Phương pháp phân cụm phân cấp thường được sử dụng khi mạng xã

hội có cấu trúc phân cấp (tức một mạng chia làm nhiều cộng đồng con, mỗi

cộng đồng con chia ra làm nhiều cộng đồng con khác và cứ như vậy). Ý

tưởng cơ bản của thuật toán phân cụm phân cấp là xác định được sự tương

tự của các đỉnh trong đồ thị mạng bằng một độ đo tương tự, sau đó các đỉnh

có độ tương tự cao được xếp vào cùng một nhóm. Phương pháp phân cụm

phân cấp được áp dụng phổ biến trong phân tích mạng xã hội, sinh học, kỹ

thuật, tiếp thị,…

+ Phương pháp phân cụm theo vùng định nghĩa trước một số k là số

lượng các cụm, rồi từ đó ta biểu diễn đồ thị trong một không gian metric sao

cho mỗi đỉnh của đồ thị được biểu diễn bằng một điểm trong không gian đó.

Sau đó người ta tính toán khoảng cách giữa các điểm trong không gian và lấy

đó làm độ đo sự khác nhau giữa các đỉnh trong đồ thị. Mục tiêu của phương

pháp là phân tách không gian trên thành k cụm các điểm sao cho một hàm

chi phí dựa trên khoảng cách của các điểm trong cụm đến tâm của cụm là

lớn nhất / nhỏ nhất. Phương pháp phân cụm theo vùng được áp dụng để xác

định các cụm trong các tập điểm dữ liệu.

+ Phương pháp phân cụm theo phổ bao gồm tất cả các phương pháp và

kỹ thuật chia tập đối tượng thành các cụm sử dụng vector riêng của ma trận

được định nghĩa từ tập đối tượng đó. Đối tượng ở đây có thể được hiểu là

các đỉnh của đồ thị, hoặc có thể là các điểm của không gian metric nào đó.

Phương pháp phân cụm bao gồm việc chuyển hóa các tập đối tượng thành

các điểm trong một không gian, mà các điểm này là các thành phần của

vector đặc trưng, sau đó các điểm được phân cụm dựa trên các phương pháp

chuẩn, ví dụ phương pháp phân cụm k-mean

2.3.3. Các phương pháp áp dụng thuật toán phân chia:

Các phương pháp áp dụng thuật toán phân chia đều dựa trên mục đích

cơ bản là tìm ra được các cạnh nối giữa các đỉnh của các cộng đồng khác

nhau, sau đó loại bỏ chúng khỏi đồ thị. Như vậy các cụm trong đồ thị sẽ bị

ngắt kết nối với nhau, từ đó ta có thể phân đồ thị thành các cộng đồng. Điểm

mấu chốt của phương pháp này là xác định được tính chất nào đó của các

cạnh nối các cộng đồng trong đồ thị, từ đó có thế phát hiện và loại bỏ chúng

ra khỏi đồ thị. Phương pháp áp dụng thuật toán chia có thể coi là một kiểu

thuật toán phân cụm phân cấp, chỉ khác là thay vì tìm các cạnh có độ tương

đồng cao để ghép các đỉnh của các cạnh đó thành cộng đồng, thì ở đây

người ta tìm cách loại bỏ các cạnh nối giữa các cộng đồng để thu được

từng cộng đồng riêng biệt. Vì vậy kết quả của các thuật toán chia có thể

biểu diễn dưới dạng các mô hình phân cấp dưới dạng cây.

Các thuật toán điển hình nhất trong các thuật toán chia này là thuật

toán Girvan- Newman và thuật toán Conga. Trong đó Conga đưa ra khái niệm

độ trung gian phân chia của một đỉnh v, đó là số đường đi ngắn nhất có thể sẽ

vượt qua giữa hai phần của v nếu nó được phân chia. Ví dụ v được phân chia

thành v1, v2 thì độ trung gian này chính là độ trung gian của cạnh v1v2. Từ

đó, thay vì việc loại bỏ các cạnh thì ta có thể phân chia các đỉnh, từ đó sẽ có

thêm các đỉnh mới và cạnh mới. Có rất nhiều cách để chia một đỉnh thành hai,

một cách phân chia tốt nhất là cách phân chia trong đó tối đa hóa độ trung

gian phân chia. Các thuật toán này mang tính phổ biến cao, vì nó có ý nghĩa

về mặt lịch sử (đánh dấu bước khởi đầu của một thời kỳ mới trong sự phát

triển của phát hiện cộng đồng) cũng như về mặt phương pháp. Trong thực tế,

do tính ứng dụng cao, thuật toán Girvan-Newman và Conga được sử dụng

rộng rãi và phát triển thành nhiều thuật toán cải tiến sau này, tạo thành họ

thuật toán Girvan-Newman.

Thuật toán CONGA (Cluster Overlap Newman-Girvan Algorithm) được

Gregory cải tiến từ thuật toán Girvan-Newman nhằm mục đích giải quyết vấn

đề về chồng chéo cộng đồng. Dựa trên ý tưởng thuật toán Girvan-Newman,

tác giả đề xuất thêm một ý tưởng mới đó là phép chia các đỉnh thành nhiều

phần khác nhau, để một phần của đỉnh được chia đó có thể xuất hiện trong

các cộng đồng con. Phép chia các đỉnh này là phù hợp với ý tưởng của thuật

toán GirvanNewman bởi lẽ, cũng như việc loại bỏ các cạnh, việc phân chia

các đỉnh cũng có thể làm cho một cộng đồng lớn chia thành các cộng đồng

con.

Hình 2.11. Ví dụ về phép phân chia một đỉnh trong đồ thị

Thuật toán này có ưu điểm là giải quyết được vấn đề chồng chéo cộng

đồng bằng cách đặt ra phép phân chia đỉnh, ngoài ra nội dung thuật toán tương

đối dễ hiểu và xác định được phép phân chia tối ưu nhất trong các trường hợp,

một điều mà thuật toán Girvan-Newman nguyên thủy không làm được.Tuy

nhiên nhược điểm của thuật toán vẫn là thời gian tính toán, với độ phức tạp

tính toán lên tới O(m3) với m là số cạnh.

2.3.4. Phát hiện cộng đồng trong mạng xã hội

+ Mô tả

Mục tiêu của bài toán 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.

Một tập hợp các đỉnh trên đồ thị được coi là một cộng đồng nếu mật độ cạnh

bên trong nó cao hơn so với mật độ của các cạnh giữa đỉnh của nó và những cạnh

bên ngoài. Dưới đây là một vài ví dụ khá điển hình về mạng xã hội:

Hình 2.12. Một số ví dụ về cộng đồng trên mạng xã hội

Chúng ta có thể thấy trong biểu đồ, mỗi trong sáu trang web chính có tiểu

sử riêng của họ backlink - các trang web chỉ liên kết với chính nó. Một số liên

kết được chia sẻ giữa các trang web khác nhau, và chúng nằm ở giữa của biểu

đồ. Điều nhấn mạnh trong đồ thị mạng này là các trang web liên kết với ít nhất

2 trang web chính. Các trang web này là mục tiêu liên kết chính. Khi chúng

liên kết với ít nhất hai trang webchinh, điều đó chứng minh rằng nó có mối

quan tâm trong ngành công nghiệp đó và chắc chắn sẽ có quan tâm đến trang

web của mà cần phân tích. Phân tích mạng có thể được áp dụng rộng rãi cho

lĩnh vực SEO trong việc phân tích các trang web liên kết với nhau như thế nào,

và trong việc tiến hành phân tích cạnh tranh. Lĩnh vực này cũng có ứng dụng

rõ ràng cho truyền thông xã hội để hiểu cách thức người dùng kết nối với nhau

trong mạng lưới trực tuyến. Bất kỳ mạng xã hội trực tuyến nào - dù là trên

Twitter, Facebook, Youtube, Flickr, v.v. - có thể dễ dàng mô hình hoá bằng

cách sử dụng biểu đồ mạng. Một biểu đồ có thể tập trung vào cách một người

dùng được liên kết với người dùng khác, được gọi là mạng ego. Hoặc một biểu

đồ mạng xã hội có thể tập trung vào một chủ đề cụ thể - nhận xét về một video

trên Youtube, một thẻ bắt đầu bằng Twitter hoặc một nhóm Facebook - và xem

nhóm người dùng được kết nối với nhau như thế nào. Các công cụ tìm kiếm

đã tuyên bố rằng các trang web xã hội có một ảnh hưởng nhỏ đến thứ hạng vì

vậy cũng có một ý nghĩa SEO cho loại phân tích này.

Hình 2.13. Mô hình mạng lưới cộng tác của các nhà khoa học

Hình trên hiển thị các thành phần kết nối lớn nhất trong mạng lưới các

cộng tác của các nhà khoa học làm việc tại Viện Santa Fe (SFI). Đồ thị bao

gồm 118 đỉnh đại diện cho các nhà khoa học cư trú tại SFI và các cộng tác viên

của họ. Hai đỉnh sẽ có cạnh kết nối nếu hai nhà khoa học đã công bố cùng với

nhau ít nhất một bài báo. Mạng này có rất nhiều cộng đồng, mỗi cộng đồng

thường thiên về một vấn đề nghiên cứu. Trên hình, các đỉnh cùng màu là kết

quả phân tích và phát hiện cộng đồng sử dụng thuật toán Girvan và Newman,

kết quả này cũng gần tương tự so với sự phân chia theo các lĩnh vực nghiên

cứu của Viện.

Như vậy tồn tại các nhóm (cộng đồng) có mật độ kết nối mạnh của các

đỉnh trong nhóm và các kết nối yếu giữa các nhóm. Từ đó, việc xác định cộng

đồng có thể được xem như là việc tìm kiếm các cụm nút phân nhóm và việc

này liên quan đến việc phân nhóm trong dữ liệu, mặc dù phương tiện và thuật

toán sử dụng có thể khác nhau. Xác định các kết nối và tìm ra các cộng đồng

khác nhau là mục tiêu chính của nghiên cứu khai phá cộng đồng.

+ Phát hiện cộng đồng trong mạng xã hội

Việc phát hiện các cấu trúc cộng đồng trong một mạng lớn là một vấn đề

phức tạp về tính toán. Các thuật toán phát hiện cộng đồng ban đầu xây dựng

bởi Girvan và Newman được biết đến rộng rãi, nhưng không phải là giải pháp

khả thi vì không tìm ra được cộng đồng chồng chéo và chi phí quá đắt. Một số

thuật toán tối ưu hóa đã được đề xuất trong đó đáng chú ý là CONGA (Cluster

Overlap Newman-Girvan Algorithm), LPA (Label Propagation Algorithm),

và FNCA (Fast Network Community Algorithm).

CONGA: Gregory năm 2007 đề xuất một hướng tiếp cận tương tự thuật

toán Girvan và Newman, đặt tên là CONGA (Cluster Overlap Newman-

Girvan Algorithm), trong đó các đỉnh được phân chia thành nhiều bản sao

nếu như độ trung gian của nó vượt quá độ trung gian cạnh lớn nhất. Thuật

toán CONGA được Gregory cải tiến từ thuật toán Girvan-Newman nhằm mục

đích giải quyết vấn đề về chồng chéo cộng đồng. Do đó, một phần của đỉnh

được chia đó có thể xuất hiện trong các cộng đồng con. Phép chia các đỉnh

này là phù hợp với ý tưởng của thuật toán Girvan- Newman.

LPA: là một thuật toán thơi gian tuyến tính để phát hiện cộng đồng. LPA

chỉ sử dụng cấu trúc mạng nguyên thủy đưa ra, được tối ưu hóa cho các mạng

quy mô lớn, không theo bất kỳ một hàm mục tiêu nào và không đòi hỏi bất kỳ

thông tin trước về các cộng đồng. Chi tiết về thuật toán có mô tả trong phần

sau.

FNCA: ưu điểm là nó không yêu cầu định nghĩa trước số của cộng đồng

trong mạng, hoặc kích thước của chúng. Đặc điểm này làm cho nó thích hợp

cho việc điều tra của các cấu trúc cộng đồng chưa biết, chẳng hạn như trong

trường hợp của Facebook.

FNCA là một thuật toán tối ưu hóa nhằm tối đa hóa giá trị của hàm mô

đun mạng, nhằm phát hiện các cấu trúc cộng đồng của một mạng nào đó. Các

hàm mô đun đã được giới thiệu bởi trong những năm qua và đã được phần lớn

cộng đồng khoa học thông qua.

Cho một mạng vô hướng, không trọng số G = (V, E), giả sử i  V là một

đỉnh thuộc cộng đồng r (i) biểu thị bằng cr (i) hàm số mô đun mạng có thể được

viết như sau:

Trong đó Aij là phần tử của ma trận kề A = (Aij)nxn đại diện cho mạng, và

giá trị Aij = 1 nếu i và j được gắn bởi một cạnh, aij = 0 nếu ngược lại.

Với những giả định, các tác giả đã phát minh ra một thuật toán phát hiện

cộng đồng nhanh chóng, tối ưu hóa cho mạng lưới phức tạp. FNCA dựa trên

việc xem xét rằng, trong các mạng với một cấu trúc cộng đồng xuất hiện, mỗi

nút phải được dán nhãn như một trong những láng giềng của nó, nếu không nó

là một cụm riêng.

Ngoài ra thuật toán này, giống như LPA, có thể không hội tụ. Thời gian

phức tạp của FNCA là O (T.n.k.c), trong đó T là số lần lặp lại tối đa, n số lượng

tổng số các nút, k bậc trung bình của tất cả các nút, và c là kích thước cộng

đồng trung bình ở cuối quá trình thực hiện thuật toán. Thực tế, với các mạng

quy mô lớn, FNCA là một thuật toán tuyến tính.

2.3.5. Thuật toán phát hiện cộng đồng

Mục tiêu: Nhằm phát hiện ra các cộng đồng trong mạng xã hội và đưa ra

danh sách những nút mạng thuộc mỗi cộng đồng.

Đầu vào: Đồ thị mạng xã hội G = (V, E) gồm tập V có đỉnh: v1, v2,…, vn

và tập E các liên kết E = {(vi, vj)}.

Đầu ra: Tập các cộng đồng Ci và tập hợp các đỉnh thuộc các cộng

đồng đó: {C1, C2,...,Cn}; trong đó Ci có thể bao gồm tập các đỉnh: {vi1, vi2,

…,vik}

Việc xác đinh cộng đồng trong đồ thị cũng là một chủ đề phổ biến trong

khoa học máy tính. Ví dụ trong tính toán song song, việc xác định phương

pháp giao các công việc cho các bộ xử lý sao cho giảm thiểu tối đa sự liên

lạc giữa chúng và tối đa hóa hiệu suất tính toán là rất quan trọng. Điều này

có thể thực hiện được bằng cách chia các cụm máy tính thành các nhóm có số

lượng bộ xử lý gần tương tự nhau, như vậy số lượng kết nối vật lý giữa các

vi xử lý của các nhóm khác nhau là tối thiểu.

Riêng trong lĩnh vực khai phá dữ liệu, bài toán khai phá cộng đồng trong

mạng xã hội cũng có một ứng dụng tương đối rộng rãi. Khai phá cộng đồng

ứng dụng trực tiếp vào các bài toán chính của khai phá dữ liệu như nhận

dạng thực thể, phân cụm, xếp hạng thực thể hay phân lớp thực thể, dự đoán

các liên kết hay phát hiện các đồ thị con…

Tóm lại, cộng đồng trong các mạng xã hội có một vai trò quan trọng

trong nhiều lĩnh vực của đời sống xã hội, như khoa học máy tính, sinh học,

kinh tế, chính trị,…Điều này dẫn đến nhu cầu bức thiết của bài toán phát hiện

cộng đồng trong mạng xã hội vì các lý do đã được nêu ở trên.

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

3.1. Mô tả bài toán

Bài toán nhằm xác định những cộng đồng (nhóm) người dùng có quan hệ

với nhau của một mạng xã hội. Để làm được điều này bài tóan cần giải quyết:

- Xây dựng mô hình cho bài toán: mô hình cần mô tả được các thông tin

thể hiện được mối quan hệ của nhóm người dùng mạng xã hội.

- Xây dựng công thức và giải thuật xác định những nhóm cộng đồng người

có mối quan hệ với nhau trên một cộng đồng mạng xã hội. Chọn lựa công thức,

giải thuật, cải tiến để áp dụng phù hợp với mô hình đề xuất.

- Áp dụng mô hình vào cộng đồng ảo chuyên biệt, cụ thể là nhóm

Facebook của 1 công ty, nhằm phát hiện cộng đồng mạng trên mạng xã hội.

3.2. Mô hình giải quyết bài toán

3.2.1. Mô hình đồ thị thông tin

Theo những yêu cầu của bài toán, chúng ta sẽ mô hình hóa mạng xã hội

bởi một đồ thị có hướng G=(V, E), với V là tập đỉnh, mỗi đỉnh trong V sẽ đại

diện cho một thành viên trong nhóm, và E là tập cạnh có hướng, có trọng số,

mỗi cạnh trong E sẽ biểu diễn cho sức ảnh hưởng giữa hai đỉnh. Ta gọi là đồ

thị thông tin.

3.2.2. Hướng của cạnh

Hai thành viên có quan hệ với nhau hay giữa hai thành viên có tồn tại liên

kết khi và chỉ khi một trong hai có phản ứng với nhau. Liên kết (cạnh) giữa hai

người dùng sẽ là một cạnh có hướng:

Hình 3.1. Liên kết giữa hai đỉnh (người) trên mạng xã hội

3.2.3. Trọng số của cạnh

Trọng số của cạnh trong mô hình đã thể hiện được mối quan hệ/hành độ

của một người tới một người khác. Nếu một đỉnh A có quan hệ bạn

bè/thích/chia sẻ/bình luận tới đỉnh B có nghĩa là đỉnh A có quan hệ cộng đồng

với đỉnh B với xác suất là cạnh AB, hay là nếu đỉnh A chấp nhận ý tưởng nào

đó và truyền đến đỉnh B thì đỉnh B sẽ chấp nhận với xác suất là cạnh AB.

Hình 3.2. Quan hệ giữa hai người trên mạng xã hội với trọng số

3.2.4. Lựa chọn mô hình cho bài toán

Theo những giả định về mô hình mạng xã hội được mô tả ở trên, chúng ta

có 2 mô hình được áp dụng trong đề tài đó là mô hình sử dụng thuật toán Apriori

và mô hình thuật toán FSG (Frequency SubGraph Mining). Như vậy mô hình

đồ thị cho bài toán là mô hình đồ thị có hướng, có trọng số, sức ảnh hưởng giữa hai

đỉnh trong đồ thị thể hiện mối quan hệ từ đỉnh này đến đỉnh kia.

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ả)

3.3.1. Giới thiệu nhóm Facebook, phân tích nhóm Facebook

Facebook group page là một diễn đàn Facebook bao gồm những thành

viên có chung một nội dung quan tâm, các bài viết của các thành viên trong

nhóm sẽ tập trung chủ yếu vào một lĩnh vực, chủ đề cụ thể nào đó. Các thành

viên của nhóm có thể đăng bài viết, liên kết, hình ảnh, video… những người

khác là thành viên của nhóm có thể thấy được nội dung đăng của thành viên

trong nhóm và cũng có thể có phản ứng (like, comment, share) với nội dung

đó. Ví dụ: diễn đàn Facebook về điện thoại di động; diễn đàn về các kỹ thuật

lập trình C, C++; hoặc diễn đàn Facebook mua sắm quần áo, giày dép,…

Hình 3.3. Hình ảnh một nhóm Facebook

Phân tích một Facebook group là sử dụng các API có sẵn trên Facebook

để thu thập thông tin trên nhóm đó. Thông tin được thu thập gồm có: thông tin

của người dùng (thành viên của nhóm), tổng số bài viết mà người dùng đã đăng,

với mỗi bài viết thu thập còn kèm theo phản ứng với bài viết. Phản ứng với bài

viết được thu thập sẽ là trạng thái “like”/ “share”/“comment” đối với bài viết.

Trạng thái like của bài viết sẽ cho ta thấy được phản ứng khách quan nhất

của người đọc với bài viết. Một người đọc khi tiếp cận với bài viết thì họ sẽ

biết được những thông tin được truyền tải trên bài viết đó, những thông tin này

nếu họ đang cần hoặc họ cũng có suy nghĩ giống như vậy, thì người đọc này sẽ

like bài viết mặc dù họ có thể không hề biết người viết bài viết đó là ai. Nhóm

trên Facebook có rất nhiều thành viên cùng quan tâm đến một vấn đề cụ thể

nào đó, họ chỉ tương tác với nhau qua thông tin từ các bài viết được đăng trên

nhóm.

Qua phân tích trên, mô hình cho cộng đồng ảo sẽ trừu tượng hóa các thông

tin về các thành viên của cộng đồng, những bài viết của các thành viên và phản

ứng với bài viết.

3.3.2. Phương pháp thu thập dữ liệu từ nhóm Facebook

+ Sử dụng Facebook API để thực hiện gọi hàm truy xuất dữ liệu:

Phương pháp Facebook API thì có những ưu điểm như: tương thích hoàn

toàn với cấu trúc dữ liệu của Facebook, kết quả trả về là định dạng JSON tương

thích với hầu hết ngôn ngữ lập trình phổ biến. Bộ SDK của Facebook API cũng

hỗ trợ rất nhiều ngôn ngữ lập trình như Java, C#, PHP… Vì đây là sản phẩm từ

Facebook phát triển nên việc thu thập dữ liệu không gặp vấn đề với ajax.

Sử dụng XML-RPC: một cài đặt RPC (Remote Procedure Call) trên nền

giao thức HTTP, sử dụng XML để mã hoá và trao đổi dữ liệu.

+ Về mặt dữ liệu:

Sử dụng bất kỳ định dạng dữ liệu đơn giản: excel (xlsx, csv), json, nó có

một số ưu điểm:

- Đơn giản, gọn.

- Linh động, không cần phải định nghĩa cấu trúc dữ liệu trước khi tiến

hành lưu trữ điều này thể hiện tính tương thích khi làm việc với các dạng dữ

liệu không có cấu trúc như của Facebook.

- Khả năng mở rộng tốt, khả năng cân bằng tải cao, tích hợp các công nghệ

quản lý dữ liệu vẫn tốt khi kích thước và thông lượng trao đổi dữ liệu tăng.

- Xây dựng ma trận quan hệ dựa trên các tiêu chí sau:

+ Bạn bè (friend)

+ Thích (like): bài viết

+ Bình luận (comment)

+ Chia sẻ (share)

Công cụ đang làm việc trên bộ dữ liệu CSV thu thập trong tệp Excel phải

tuân theo điều này định dạng sau

Bảng 3.1. Một dạng format (Ma trận thích (Like))

ID User1 User2 UserN …

23 … 11 User1 0

0 … 34 User2 1

… … … … …

0 … 0 UserN 28

- Hộp đầu tiên phải là "ID".

- ID của các yếu tố có thể là chuỗi hoặc số, nhưng sẽ được phân tích cú

pháp như chuỗi, nhưng dù sao mọi dữ liệu trên đường chéo phải là 0.

- Trong ví dụ này, dữ liệu có thể được hiểu là "User1 thích các bài viết

của User2 23 lần "...

- Bảng tính phải chứa ít nhất 3 worksheet. Đầu tiên là về:

+ Quan hệ nhị phân giữa hai người dùng (Bạn bè hay không). Hộp phải là

1 hoặc 0. Bất cứ thứ gì trừ 0 sẽ được coi là "1".

+ Hai worksheet tiếp theo, có chứa ví dụ "Thích" và "Bình luận" phải theo

cùng một định dạng như đã đề cập ở trên..

Lưu ý: các tập dữ liệu sẽ chỉ được đọc. Không có dữ liệu nào sẽ được sửa

đổi.

3.3.3. Thử nghiệm bài toán

- Tìm kiếm các cộng đồng trong một bộ dữ liệu là một vấn đề của đồ thị

con thường xuyên, việc sử dụng thuật toán phát triển Pattern, cụ thể là Apriori

hoặc FSG, là một trong những đề xuất tốt nhất trong trường hợp này cho đến

ngày nay. Tuy nhiên, có một số khác biệt nhỏ khi áp dụng cho bài toán này:

- Trước hết, chỉ được coi là "cộng đồng" (tức là hoàn chỉnh đồ thị con)

khi có một nhóm hai hoặc nhiều nút kết nối. Bằng cách này, các nút riêng lẻ

không được bao gồm trong thuật toán, giảm thời gian thực hiện của thuật toán,

và các cặp của các nút là bao gồm trong C2.

- Trước tiên xem xét sử dụng các cạnh như các cá nhân, vì nó phù hợp

với bài toám. Tuy nhiên, đồ thị hoàn chỉnh không có hướng chỉ có hai cạnh là

không thể; số các cạnh là n (n-1)/2, với n số lượng các nút.

- Do đó, tôi thực hiện bằng cách gắn trọng lượng của cạnh, giữa 0 và 1

(1 là có mối quan hệ "hoàn hảo" giữa hai cá thể, 0 có nghĩa là không có mối

quan hệ và không đại diện trên biểu đồ). Sau khi nhập ngưỡng và nhận L2, C3

thu được bằng cách tìm ra 3 tập con. Các ứng cử viên mới được lựa chọn trong

số các nút kết nối của một cộng đồng, tránh để đọc toàn bộ cơ sở dữ liệu ở mỗi

bước lặp lại.

3.3.4. Thuật toán chính

function subgraph(n){

var eles = cy.nodes();

var C = [];

var C1 = [];

var C2 = [];

for (var i = 0; i < eles.size(); i++) {

var a = eles[i];

// nodes neighbourgs of a

for (var j = i+1; j < eles.size(); j++) {

if(edge(a.id(),eles[j].id()))

if(cn(a).intersection(cn(eles[j])).size() >= n-

C1.push(cy.collection([a,eles[j]]));

}

// at this point, C1 contains all couples that belong to a (n+)-graph

while(C1.length > 0){

C.push(C1);

// foreach communities in C1

for (var i = 0; i < C1.length; i++) {

// the current community

var com = C1[i]

// the "new" nodes to the community

var set = cn(com)

for (var j = 0; j < set.size(); j++) {

if(inCommunity(com,set[j]) &&

!C2.contains(com.union(set[j])) ){

C2.push(com.union(set[j]));

}

// at this point, C2 contains all k+2-communities

C1 = C2;

C2 = [];

}

console.log(C);

return C;

}

3.3.5. Demo bài toán

Yêu cầu chung

- Demo bài toán này là một ứng dụng web, được viết hoàn toàn bằng

HTML5, CSS3 và JavaScript, với 3 thư viện:

+ JQuery, để cải tiến tổng thể và giảm mã.

+Cytoscape.js (js.cytoscape.org), để chuyển đổi một đối tượng JavaScript

thành một biểu đồ, hiển thị và thao tác đồ thị.

+ Sheet.js và Xslx.js (sheetjs.com), để đọc và chuyển đổi và phân tích cú

pháp nhị phân các tệp Excel vào đối tượng JavaScript.

- Tập tin test.js: chứa các chức năng chính, khởi tạo đồ thị và các trình

nghe hành động cho các giao diện.

- Ứng dụng được tối ưu hóa cho Google Chrome, và đã được kiểm tra

đầy đủ trên trình duyệt IE 9 và Firefox trên Windows và Linux. Nó hỗ trợ

Chrome, Edge, Firefox, Opera và Safari. Một số chức năng không có sẵn trên

Internet Explorer và các phiên bản cũ của Safari.

- Công cụ này không cần một máy chủ. Bạn có thể chạy nó ở bất cứ đâu

miễn là bạn sở hữu tất cả các tệp.

Thử nghiệm bài toán:

+ Xử lý dữ liệu:

- Tệp sẽ được giải mã và chuyển đổi từ nhị phân (.xls) sang chuỗi, sau đó

chuyển đổi thành một chuỗi các chuỗi. Mỗi chỉ mục có chứa một bảng tính,

được phân cách bởi dấu phẩy và giá trị. Nếu dữ liệu theo định dạng đã nêu ở

trên, các chuỗi sẽ được chia nhỏ và được chuyển đổi thành một mảng duy nhất

theo cùng một định dạng:

Bảng 3.2. Bảng người dùng sau khi đã giải mã

ID User1 User2 UserN …

User1 0 0.24 … 0.11

User2 0.24 0 … 0.34

… … … … …

UserN 0.11 0.34 … 0

- `Nếu hai người dùng không phải là bạn, số lượt thích và nhận xét của

họ sẽ bị bỏ qua (0). Điểm số hiện tại của mảng này thể hiện trọng số của một mối

quan hệ, do đó đối xứng (trọng lượng chỉ được tính một lần, sau đó sao chép vào

hộp đối xứng). Mỗi cặp người sử dụng, công thức tính toán là như sau:

+ 𝑙𝑖𝑘𝑒𝑠. 𝛼 max 𝐿𝑖𝑘𝑒𝑠 𝑐𝑜𝑚. (1 − 𝛼) max 𝐶𝑜𝑚𝑠

Công thức tính mối quan hệ “Like”, “Coms”

Với maxLikes: Số cao nhất thích trong "thích" của mảng,

maxComs: Số cao nhất của bình luận

α: là một hệ số giữa 0 và 1 (bạn có thể nhập khi gửi một tệp Excel, để

tăng hoặc giảm giá trị thích so với bình luận)

- Cuối cùng, kết quả sẽ được chuyển đổi thành một mảng giống Apriori

Bảng 3.3. Mảng chuyển đổi

User1 User2 0.24

User1 UserN 0.11

User2 UserN 0.34

… … …

Và đã sẵn sàng để nhập vào đồ thị và tạo thành những "đồ thị con"

Đây là một định dạng dữ liệu đầu vào đại hiện cho bảng: bạn bè, thích,

bình luận:

Hình 3.5. Ví dụ 3 định dạng worksheet: bạn bè, thích, bình luận

Sau khi xử lý sơ bộ dữ liệu như trang trước với tỷ lệ 0,7 thì thu được đồ

thị như thế này

Hình 3.6. Đồ thị sau khi xử lý

Và cuối cùng, áp dụng thuật toán Light-FSG thông qua chức năng đồ thị

con, chúng ta có được bộ dữ liệu sau đây (hai cộng đồng cuối cùng):

Hình 3.7. Bộ dữ liệu sau khi xử lý

Lưu ý: một số đang được viết tắt trong Excel, nhưng mỗi ID là duy nhất.

So sánh thuật toán Light-FSG với thuật toán khác:

Hình 3.8. So sánh thuật toán Light-FSG với thuật toán khác

Giao diện chương trình:

Hình 3.9. Giao diện chương trình

Hình 3.10. Biểu diễn Mạng đồ thị 2D

Hình 3.11. Biểu diễn Mạng đồ thị 3D

3.3.6. Đánh giá

- Thứ nhất, trong lý thuyết đồ thị và phức tạp, vấn đề clique là một NP-

Complete vấn đề, có nghĩa là "dễ dàng" để xác minh một giải pháp nhất định

trong một cách dưới mức Thời gian (ví dụ: "đồ thị con này thuộc đồ thị" hay

"là biểu đồ này Clique "), nhưng nó là" khó "để tìm ra một giải pháp một cách

hiệu quả.

- Với ý nghĩ đó, tôi đã cố gắng để thực hiện một giải pháp cạn kiệt, mà

sẽ đánh giá từng đồ thị con có thể và xác minh hoặc nó là một quan hệ hay

không, và lưu nó nếu nó Hỗ trợ là đủ cao. Giải pháp này là hoàn toàn không tối

ưu, hiểu biết hơn Số kết hợp tăng lên theo cấp số nhân với số nút.

- Sau đó, tôi áp dụng một thuật toán tham lam, mà lựa chọn các giải pháp

tối ưu tại địa phương ở mỗi lần lặp để tìm ra sự tối ưu toàn cầu. Trước mỗi thế

hệ, chúng tôi Đảm bảo rằng mỗi kết hợp thực sự là trong biểu đồ. Bằng cách

này, đồ thị con chứa các bản đồ con không tồn tại sẽ không được đánh giá. Giải

pháp này là tối ưu với một vài nút hoặc với đồ thị mật độ thấp, nhưng thời gian

thực hiện có xu hướng phát triển thực sự nhanh với số nút quá nhiều. Độ phức

tạp tính toán của nó là khá trên O(n3). Vì vậy, khi thực hiện bài toán này với

thuật toán FSG hoàn toàn không khả thi và hiệu quả với quy mô của bài toán

đặt ra. Do đó, tôi chuyển sang chọn thuật toán Light-FSG vẫn là một sự lựa

chọn tối ưu trong trường hợp này vì một số lý do sau:

+ Thời gian duyệt các đồ thị con trong FSG mất khá nhiều thời gian do

thuật toán phải tìm duyệt tất cả các đồ thị con phải giống (tương tự).

+ Để thực hiện thuật toán FSG thì phải có một hệ thống máy chủ mạnh để

có thể tính toán/tìm duyệt các đồ thị con trong thời gian ngắn.

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN

1. Kết luận

Mạng xã hội và bài toán phát hiện cộng đồng trong mạng xã hội là những

vấn đề được nhiều nhà nghiên cứu quan tâm trong thời đại hiện nay. Các bài

toán phát hiện cộng đồng được ứng dụng rộng rãi trong nhiều lĩnh vực của đời

sống như kinh tế, chính trị, xã hội, khoa học công nghệ,...

Luận văn đã đưa ra tổng quan về mạng xã hội và bài toán phát hiện cộng

đồng trong mạng xã hội, cũng như những hướng tiếp cận điển hình cho bài toán

phát hiện cộng đồng. Luận văn chú trọng trình bày chi tiết về thuật toán Light

- FSG (Frequency SubGraph Mining).

2. Hướng phát triển

Hướng phát triển nghiên cứu tiếp theo của luận văn là mở rộng mô hình

mạng xã hội, tính toán trọng số cũng như bổ sung hướng cho đồ thị cho phù

hợp như:

- Đánh giá mức độ quan tâm của cộng đồng mạng xã hội đối với một vấn

đề đang được quan tâm nhất. Nhằm có định hướng và phát triển 1 chính sách,

1 chiến lược, 1 kế hoạch kinh doanh phù hợp…

- Đánh giá mức độ quan tâm cộng đồng mạng xã hội đối với 1 bộ phim,

sản phẩm, 1 dịch vụ mới. Từ đó có chiến lược quảng cáo phù hợp.

- Đánh giá mức độ ảnh hưởng của 1 cá nhân, tổ chức, công ty.

TÀI LIỆU THAM KHẢO

Tài liệu tiếng việt

1. Giang Thành Trung, “Một thuật toán khai phá đồ thị con phổ biến trong dữ

liệu đồ thị”.

2. Hà Quang Thụy, Phan Xuân Hiếu, Đoàn Sơn, Nguyễn Trí Thành,

Nguyễn Thu Trang, Nguyễn Cẩm Tú (2009), Giáo trình khai phá dữ liệu,

Nhà xuất bản Giáo dục.

3. GS.TS Trần Hữu Luyến, ThS. Đặng Hoàng Ngân (7/2014), “Mạng xã hội:

Khái niệm, đặc điểm, tính năng, áp lực và ý nghĩa trong thực tiễn và nghiên

cứu”, Tạp chí Tâm lý học - Số 7 (184).

Tài liệu tiếng anh

4. A.Ben-Dor, R. Shamir, and Z. Yakhini. Clustering gene expression

patterns.J. Comput. Biol., 6(3/4):281–292, 1999.

5. V. Satuluri, S. Parthasarathy. Scalable Graph Clustering Using Stochastic

Flows: Applications to Community Discovery, ACM KDD Conference,

2009.

6. Viet Anh Nguyen, Learning from graph data by putting graph on the lattice,

Viện Công nghệ thông tin.

7. Y. Chi, Y. Yang, Y. Xia, and R.R. Muntz, CMTreeMiner: Mining Both

Closed and Maximal Frequent Subtrees, Proc. Eighth Pacific Asia Conf.

Knowledge Discovery and Data Mining (PAKDD ’04), May 2004.

8. M. Kuramochi, G. Karypis,Finding frequent patterns in a large

sparsegraph. Data Mining and Knowledge Discovery, 11(3): pp. 243–

271, 2005.

9. Jiyang Chen, Community Mining-Discovery Communities in Social

Network, Thesis, University of Alberta, 2010.

10. Santo Fortunato (2010), Community detection in graphs, Technical Report,

Complex Networks and Systems Lagrange Laboratory, ISI Foundation,

Torino, ITALY, arXiv:0906.0612v2 (2010).

11. M. Girvan, M. E. J. Newman (2002). Community structure in social and

biological networks, Proc. Natl. Acad. Sci., 99(12), 7821 (2002).

12. Steve Gregory: An Algorithm to Find Overlapping Community Structure

in a Networks.PKDD 2007.

Website

13. http://www.mediative.com/network-analysis-seo/

14. https://www.facebook.com/

15. http://tailieudientu.lrc.tnu.edu.vn/chi-tiet/mang-xa-hoi-khai-niem-dac-

diem-tinh-nang-ap-luc-va-y-nghia-trong-thuc-tien-va-nghien-cuu-

44022.html

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

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

Error triggered

Yes

Water lever > 15ft

Are pumps Working?

Send warning

Send alert

Send warning

Có thể bạn quan tâm

Luận văn Thạc sĩ: Quản lý hoạt động phát triển nhận thức cho trẻ mẫu giáo ở các trường mầm non, huyện Hoàng Su Phì, tỉnh Hà Giang

Luận văn Thạc sĩ tóm tắt: Pháp luật về điều kiện đầu tư kinh doanh trong lĩnh vực giáo dục, đào tạo ở Việt Nam

Luận văn Thạc sĩ: Sự nghiệp nghiên cứu phê bình văn học của Hoài Thanh

Luận văn Thạc sĩ: Tiểu thuyết của Đỗ Phấn từ góc nhìn sinh thái

Luận văn Thạc sĩ: Giải pháp ứng phó với nhập cư ở Liên minh Châu Âu

Luận văn Thạc sĩ: Diễn ngôn về giới nữ trong văn xuôi nữ Việt Nam đương đại (khảo sát sáng tác của Dạ Ngân, Y Ban, Lý Lan, Nguyễn Thị Thu Huệ)

Luận văn Thạc sĩ: Xây dựng mức phát thải tham chiếu rừng khu vực huyện Bảo Lâm tỉnh Lâm Đồng

Luận văn Thạc sĩ: Đặc điểm nhân vật chính trong ba tác phẩm của Franz Kafka: Lâu đài, Vụ án, Hóa thân

Kháo luận tốt nghiệp: Vận dụng lí thuyết học tập trải nghiệm vào dạy học Thống kê - Xác suất ở lớp Hai

Luận văn Thạc sĩ: Xây dựng hệ thống điều khiển và thu nhận dữ liệu cho Robot dịch vụ

Luận văn Thạc sĩ: Thế giới nhân vật trong truyện ngắn Lê Minh Khuê sau năm 1975

Luận văn Thạc sĩ: Tác động của cấu trúc vốn đến hiệu quả hoạt động của các ngân hàng thương mại cổ phần niêm yết trên thị trường chứng khoán Việt Nam

Luận văn Thạc sĩ: Kiểm soát rủi ro tín dụng bán lẻ tại Ngân hàng Thương mại Cổ phần Đầu tư và Phát triển Việt Nam chi nhánh Thủ Thiêm

Luận văn Thạc sĩ: Các yếu tố ảnh hưởng đến hiệu quả kinh doanh của ngân hàng thương mại cổ phần niêm yết trên thị trường chứng khoán Việt Nam

Luận văn Thạc sĩ: Các nhân tố ảnh hưởng đến hành vi sử dụng dịch vụ ngân hàng điện tử tại Ngân hàng Thương mại Cổ phần Ngoại thương Việt Nam – Chi nhánh Thủ Đức

Luận văn Thạc sĩ: Các yếu tố tác đồng đến nợ xấu tại Ngân hàng Nông nghiệp và Phát triển Nông thôn - Chi nhánh Tiền Giang

Luận văn Thạc sĩ: Yếu tố ảnh hưởng đến quyết định sử dụng dịch vụ thanh toán không dùng tiền mặt tại Ngân hàng TMCP Công thương Việt Nam (Vietinbank)

Luận văn Thạc sĩ tóm tắt: Pháp luật về du lịch biển, thực tiễn tại tỉnh Bình Định

Luận văn Thạc sĩ: Ảnh hưởng của các yếu tố thương hiệu với vai trò trung gian của Marketing truyền miệng đến quyết định chọn việc làm của nhân viên GenZ tại chuỗi nhà hàng gà rán Popeyes khu vực Thành Phố Hồ Chí Minh

Luận văn Thạc sĩ: Ảnh hưởng của Marketing mix đến ý định học cao học của sinh viên khối ngành kinh tế thuộc Trường Đại học Công nghệ Thành phố Hồ Chí Minh

Tài liêu mới

Luận án Tiến sĩ: Nghiên cứu xây dựng thuật toán thích nghi và học tăng cường cấu trúc Actor - Critic điều khiển bám quỹ đạo cho robot di động đa hướng mecanum

Luận án Tiến sĩ: Cơ cấu bệnh tim mạch và chất lượng cuộc sống của người cao tuổi mắc suy tim, rung nhĩ điều trị tại Bệnh viện Thống Nhất, thành phố Hồ Chí Minh

Tóm tắt Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

Tóm tắt Luận án Tiến sĩ: Nghiên cứu xây dựng giải pháp đảm bảo an toàn thông tin cho quá trình học liên kết dựa trên mật mã

Tóm tắt Luận án Tiến sĩ: Phát triển năng lực đánh giá công nghệ cho học sinh trong dạy học môn Công nghệ 11 ở trường trung học phổ thông

Tóm tắt Luận án Tiến sĩ: Nghiên cứu phân loại chi cầu diệp – Bulbophyllum Thouars (Orchidaceae) ở vùng Tây Nguyên bằng phương pháp hình thái và phân tử

Tóm tắt Luận án Tiến sĩ: Nghiên cứu đặc điểm phân bố và dinh dưỡng của các loài lưỡng cư ở Vườn Quốc gia Bến En và Khu bảo tồn thiên nhiên Pù Luông, tỉnh Thanh Hóa

Luận án Tiến sĩ: Tổng hợp luật dẫn và điều khiển cho một lớp tên lửa đối hải trên cơ sở ứng dụng mạng nơ ron và hệ mờ

Luận án Tiến sĩ: Nghiên cứu tổng hợp hệ điều khiển góc Pitch tua bin gió trong điều kiện có nhiễu tác động

Luận án Tiến sĩ: Nghiên cứu hóa học lipid của hai loài san hô thủy tức Millepora dichotoma và Millepora platyphylla ở Việt Nam

Luận án Tiến sĩ: Nghiên cứu kiểm soát phân phối công suất kéo trên cầu chủ động của ô tô con bằng ABS

Luận án Tiến sĩ: Ứng dụng phản ứng Domino vào tổng hợp các dẫn xuất Podophyllotoxin, Pyrimidine và đánh giá hoạt tính sinh học của các chất tổng hợp được

Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và một số hoạt tính sinh học của cây chùm ngây (Moringa oleifera)

Tóm tắt Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và ứng dụng ức chế ăn mòn cho thép của cao chiết xuất từ cây Lộc vừng thuộc họ Lecythidaceae

Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok