Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu mô hình phân cụm có thứ bậc các đồ thị dữ liệu

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CNTT & TT THÁI NGUYÊN

NGUYỄN THẾ ĐẠT

NGHIÊN CỨU MÔ HÌNH

PHÂN CỤM CÓ THỨ BẬC CÁC ĐỒ THỊ DỮ LIỆU

LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH

Thái Nguyên – 2017

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CNTT & TT THÁI NGUYÊN

NGUYỄN THẾ ĐẠT

NGHIÊN CỨU MÔ HÌNH PHÂN CỤM CÓ THỨ BẬC

CÁC ĐỒ THỊ DỮ LIỆU

Chuyên ngành: Khoa học máy tính

Mã số: 60 48 0101

LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS ĐOÀN VĂN BAN

Thái Nguyên – 2017

LỜI CAM ĐOAN

Tên tôi là: Nguyễn Thế Đạt

Sinh ngày: 09/01/1979

Học viên lớp cao học CK14 - Trường Đại học Công nghệ thông tin và Truyền

thông - Đại học Thái Nguyên.

Hiện đang công tác tại: Trường THCS Hạp Lĩnh – TP Bắc Ninh – Bắc Ninh

Xin cam đoan: Đề tài “Nghiên cứu mô hình phân cụm có thứ bậc các đồ thị

dữ liệu” do Thầy giáo PGS.TS Đoàn Văn Ban hướng dẫn là công trình nghiên cứu

của riêng tôi. Tất cả tài liệu tham khảo đều có nguồn gốc, xuất xứ rõ ràng.

Tác giả xin cam đoan tất cả những nội dung trong luận văn đúng như nội dung

trong đề cương và yêu cầu của thầy giáo hướng dẫn. Nếu sai tôi hoàn toàn chịu trách

nhiệm trước hội đồng khoa học và trước pháp luật.

Thái Nguyên, ngày 15 tháng 5 năm 2017

Tác giả luận văn

Nguyễn Thế Đạt

LỜI CẢM ƠN

Sau một thời gian nghiên cứu và làm việc nghiêm túc, được sự động viên, giúp

đỡ và hướng dẫn tận tình của Thầy giáo hướng dẫn PGS.TS Đoàn Văn Ban, luận văn

với đề tài “Nghiên cứu mô hình phân cụm có thứ bậc các đồ thị dữ liệu”đã hoàn

thành.

Tôi xin bày tỏ lòng biết ơn sâu sắc đến:

Thầy giáo hướng dẫn PGS.TS Đoàn Văn Ban đã tận tình chỉ dẫn, giúp đỡ tôi

hoàn thành luận văn này.

Khoa sau Đại học Trường Đại học công nghệ thông tin và truyền thông đã

giúp đỡ tôi trong quá trình học tập cũng như thực hiện luận văn.

Tôi xin chân thành cảm ơn bạn bè, đồng nghiệp và gia đình đã động viên,

khích lệ, tạo điều kiện giúp đỡ tôi trong suốt quá trình học tập, thực hiện và hoàn

thành luận văn này.

Thái Nguyên, ngày 15 tháng 5 năm 2017

Tác giả luận văn

Nguyễn Thế Đạt

iii

MỤC LỤC

LỜI CAM ĐOAN ....................................................................................................... i

LỜI CẢM ƠN ............................................................................................................ ii

MỤC LỤC ................................................................................................................ iii

DANH MỤC BẢNG .................................................................................................. v

DANH MỤC CÁC TỪ VIẾT TẮT ......................................................................... vi

DANH MỤC CÁC HÌNH VẼ................................................................................. vii

MỞ ĐẦU .................................................................................................................... 1

CHƯƠNG 1: PHÂN CỤM DỮ LIỆU VÀ PHÂN CỤM ĐỒ THỊ DỮ LIỆU ...... 4

1.1. Phân cụm dữ liệu ................................................................................................ 4

1.1.1. Khái niệm và mục tiêu của phân cụm dữ liệu ............................................ 4

1.1.2. Một số khái niệm cần thiết khi tiếp cận phân cụm dữ liệu......................... 7

1.1.3. Một số kỹ thuật trong phân cụm dữ liệu .................................................. 10

1.1.4. Các ứng dụng của phân cụm dữ liệu ........................................................ 16

1.2. Phân cụm đồ thị dữ liệu ................................................................................... 17

1.2.1. Mô hình đồ thị dữ liệu .............................................................................. 17

1.2.2. Các loại độ đo ........................................................................................... 18

1.2.3. Một số kỹ thuật phân cụm đồ thị dữ liệu .................................................. 23

1.3. Kết luận chương 1 ............................................................................................ 28

CHƯƠNG 2: PHÂN CỤM CÓ THỨ BẬC CÁC ĐỒ THỊ DỮ LIỆU ................ 29

2.1. Thuật toán CHAMELEON .............................................................................. 29

2.2. Thuật toán CURE ............................................................................................. 31

2.3. Thuật toán Girvan-Newman ............................................................................ 34

2.3.1. Giới thiệu về độ đo modularity ................................................................ 34

2.3.2. Độ đo trung gian ....................................................................................... 35

2.3.3. Thuật toán phân cụm Girvan-Newman .................................................... 36

2.4. Thuật toán CNM (Clauset-Newman-Moore) ................................................... 39

2.5. Thuật toán Rosvall-Bergstrom ......................................................................... 42

2.6. Thuật toán INC (Incre-Comm-Extraction). ..................................................... 47

2.6.1. Nội dung thuật toán .................................................................................. 47

2.6.2. Độ phức tạp của thuật toán ....................................................................... 49

2.6.3. Độ đo chất lượng phân cụm của thuật toán .............................................. 50

2.7. Kết luận chương 2 ............................................................................................ 51

CHƯƠNG 3: ỨNG DỤNG THUẬT TOÁN PHÂN CỤM CÓ THỨ BẬC

TRONG PHÂN CỤM ĐỒ THỊ DỮ LIỆU CÁC MẠNG XÃ HỘI ..................... 52

3.1. Bài toán phân cụm mạng xã hội ....................................................................... 52

3.2. Xây dựng chương trình ứng dụng phân cụm đồ thị các mạng xã hội .............. 53

3.2.1. Giai đoạn 1: Thu thập dữ liệu ................................................................... 53

3.2.2. Giai đoạn 2: Xử lý dữ liệu ........................................................................ 54

3.2.3. Giai đoạn 3: Xây dựng ứng dụng phân cụm có thứ bậc đồ thị các mạng xã .................................................................................................................. 55 hội

3.3. Các kết quả thực nghiệm và đánh giá .............................................................. 56

3.3.1. Thời gian thực thi thuật toán .................................................................... 57

3.3.2. Số cụm được phân chia ............................................................................ 58

3.3.3. Chất lượng phân cụm ............................................................................... 58

3.4. Phân cụm đồ thị mạng xã hội dựa trên mối quan tâm của người dùng ........... 58

3.4.1. Giới thiệu .................................................................................................. 58

3.4.2. Mô hình hóa dữ liệu ................................................................................. 60

3.4.3. Xây dựng dữ liệu ...................................................................................... 62

3.4.4. Xây dựng ứng dụng .................................................................................. 66

3.4.5. Thực nghiệm và đánh giá INC ................................................................. 69

3.5. Kết luận chương 3 ............................................................................................ 74

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ............................................................. 75

TÀI LIỆU THAM KHẢO ...................................................................................... 76

DANH MỤC BẢNG

Bảng 3.1: Kết quả thực thi các thuật toán…………………………………………57

Bảng 3.2: Kết quả thực thi 2 thuật toán INC và CNM…………………………….69

DANH MỤC CÁC TỪ VIẾT TẮT

Từ hoặc Từ tiếng Anh Từ tiếng Việt cụm từ

CNM Clauset-Newman-Moore Phân cụm có thứ bậc tích tụ

CSDL Cơ sở dữ liệu

Clustering Using CURE Phân cụm dữ liệu sử dụng điểm đại diện Representatives

GN Girvan-Newman Phân cụm phân chia

INC Incre-Comm-Extraction

MCL Markov Clustering Phân cụm theo mô hình Markov

RB Rosvall-Bergstrom

vii

DANH MỤC CÁC HÌNH VẼ

Hình 1.1: Ví dụ về phân cụm dữ liệu ......................................................................... 4

Hình 1.2: Ví dụ phân cụm các ngôi nhà dựa trên khoảng cách ................................. 5

Hình 1.3: Ví dụ phân cụm các ngôi nhà dựa trên kích cỡ .......................................... 6

Hình 1.4: Các chiến lược phân cụm có thứ bậc ....................................................... 11

Hình 1.5: Ví dụ về phân cụm dựa theo mật độ ........................................................ 12

Hình 1.6: Cấu trúc phân cụm dựa trên lưới .............................................................. 13

Hình 1.7: Ví dụ về phân cụm dựa trên mô hình ....................................................... 14

Hình 1.8: Các cách mà các cụm có thể đưa ra .......................................................... 16

Hình 1.9: (a) Tối ưu đường kính cực tiểu hoặc tổng cực tiểu tạo ra cụm B nhưng A

lại tốt hơn trên thực tế. (b) Tối ưu K-means tạo ra cụm B nhưng A lại tốt hơn . ..... 20

Hình 1.10: Minh họa mô hình đồ thị cho bước đi ngẫu nhiên …………………….25

Hình 2.1: Phân cụm Chameleon ............................................................................... 31

Hình 2.2: Sự di chuyển về trung tâm cụm ............................................................... 32

Hình 2.3: Sự sáp nhập của các cụm ......................................................................... 32

Hình 2.4: Cụm dữ liệu khai phá bởi thuật toán CURE ............................................ 33

Hình 2.5: Ví dụ phát hiện cụm sử dụng thuật toán Girvan - Newman . ................... 38

Hình 2.6: Khung làm việc cơ sở để phân cụm đồ thị như quá trình truyền thông…42

Hình 2.7: Ví dụ về mã Huffman ............................................................................... 43

Hình 2.8: Phân hoạch vào một lượng tối ưu các modul . .......................................... 45

Hình 3.1: Các bước thực hiện chương trình ............................................................. 53

Hình 3.2: Ví dụ về tập dữ liệu Dolphins.gml ........................................................... 54

Hình 3.3: Tập dữ liệu Dolphins.txt .......................................................................... 54

Hình 3.4: Nạp file dữ liệu đầu vào ............................................................................ 55

Hình 3.5: Kết quả chạy thuật toán phân cụm CNM cho bộ dữ liệu dolphins.txt ...... 56

Hình 3.6: Kết quả chạy thuật toán Girvan-Newman cho bộ dữ liệu dolphins.txt ..... 56

Hình 3.7: Biểu đồ so sánh thời gian thực thi thuật toán ............................................ 57

Hình 3.8: Biểu đồ so sánh số lượng cụm ................................................................. 58

viii

Hình 3.9: Biểu đồ so sánh chất lượng phân cụm ....................................................... 58

Hình 3.10: Đăng tin và bình luận trên Facebook ...................................................... 60

Hình 3.11: Một phần danh sách tài khoản Facebook ................................................ 62

Hình 3.12: Giao diện đăng ký một ứng dụng trên Facebook API ........................... 63

Hình 3.13: Thu thập dữ liệu thủ công với Graph API Explorer ................................ 63

Hình 3.14: Thu thập dữ liệu tự động với Facebook API ........................................... 64

Hình 3.15: Một phần dữ liệu thu thập được cập nhật trên SQL Server .................... 64

Hình 3.16: Một phần dữ liệu về danh sách và số lượng ID người dùng đã bình luận

trên các tường Facebook tương ứng. ......................................................................... 65

Hình 3.17: Một phần dữ liệu mạng xã hội dựa trên mối quan tâm của người dùng . 66

Hình 3.18: Giao diện tự động thu thập bộ dữ liệu .................................................... 67

Hình 3.19: Kết quả chạy chương trình phân cụm với INC và CNM. ....................... 68

Hình 3.20: Một phần biểu đồ dendrogram kết quả phân cụm với INC .................... 68

Hình 3.21: Đồ thị so sánh thời gian thực thi INC và CNM ...................................... 69

Hình 3.22: Đồ thị so sánh số lượng cụm theo INC và CNM .................................... 70

Hình 3.23: Đồ thị tương quan số lượng cụm với giá trị s ......................................... 70

Hình 3.24: Đồ thị so sánh chất lượng phân cụm theo INC và CNM ........................ 70

Hình 3.25: Đồ thị tương quan chất lượng cụm với giá trị s ...................................... 71

Hình 3.2.6: Kết quả phân chia cụm lớn thành các cụm con (bất động sản, chứng

khoán, ô tô, xe máy...). .............................................................................................. 72

Hình 3.27: Kết quả phân chia cụm lớn yêu thích đồ nội thất, lưu niệm, thời trang

thành các cụm con (giày dép, đồng hồ,hoa tươi, quà lưu niệm, ngân hàng...). ........ 72

Hình 3.28: Kết quả phân cộng động quan tâm tới Phật giáo .................................... 73

Hình 3.29: Kết quả phân cộng động quan tâm tới mỹ phẩm, thẩm mỹ, bệnh viện thẩm

mỹ đã được phân chia theo INC. ............................................................................... 73

MỞ ĐẦU

1. Lý do chọn đề tài

Trong những năm gần đây, cùng với sự phát triển vượt bậc của công nghệ

thông tin, khả năng thu thập và lưu trữ thông tin của các hệ thống thông tin không

ngừng được nâng cao. Theo đó, lượng thông tin được lưu trữ trên các thiết bị nhớ

không ngừng tăng lên.

Khai phá dữ liệu là quá trình khám phá các tri thức mới có ích ở dạng tiềm

năng trong nguồn dữ liệu đã có. Quá trình khám phá tri thức là một chuỗi lặp gồm

các bước: làm sạch dữ liệu, tích hợp dữ liệu, chọn lựa dữ liệu, đánh giá mẫu, biểu

diễn tri thức. Khai phá dữ liệu liên quan đến nhiều lĩnh vực khác nhau như: công nghệ

cơ sở dữ liệu, lý thuyết thống kê, học máy, khoa học thông tin, trực quan hóa, ...

Những đồ thị lớn và mạng (networks) là những mô hình toán học tự nhiên cho

những đối tượng tương tác với nhau như mối quan hệ giữa con người trong mạng xã

hội, các cấu trúc phân tử trong mạng sinh học, mạng biểu diễn gene, ... Trong thực

tế, cỡ của các mạng như thế khá lớn mà khả năng phân tích, khai thác các tính chất

của chúng lại rất hạn chế.

Hiện nay, các mạng xã hội ngày càng phát triển và trở nên vô cùng phổ biến.

Trên thế giới hiện có hàng trăm trang mạng xã hội trực tuyến khác nhau, tiêu biểu

như Facebook, Google+, Twitter, MySpace, YouTube, Instagram ...hay ở Việt Nam

như Zing Me, Tamtay kết nối hàng trăm triệu người trên toàn thế giới. Các mạng xã

hội này được người dùng sử dụng để giải trí, kinh doanh, chia sẻ thông tin, bày tỏ các

quan điểm, mối quan tâm đến các lĩnh vực khác nhau cũng như để giao lưu, kết bạn,

mở rộng các mối quan hệ... Việc phân cụm người dùng trong mạng có ý nghĩa vô

cùng to lớn trong thực tế như: giúp cho việc truyền tải thông tin, tiếp thị bán hàng

cũng như các hoạt động kinh doanh ... nhắm đến một lượng đông đảo các đối tượng

quan tâm (thuộc cùng một cộng đồng) một cách dễ dàng hơn, ...[12].

Đã có nhiều thuật toán phân cụm khác nhau được đề xuất để phân cụm các đồ

thị dữ liệu nói chung và đồ thị mạng xã hội nói riêng, trong đó các thuật toán phân

cụm có thứ bậc tỏ ra rất hiệu quả với lớp bài toán này. Chính vì vậy, tôi đã chọn đề

tài "Nghiên cứu mô hình phân cụm có thứ bậc các đồ thị dữ liệu" với mục đích

tìm hiểu sâu hơn về phương pháp phân cụm có thứ bậc áp dụng cho các đồ thị dữ

liệu, mà cụ thể trong luận văn là đồ thị dữ liệu các mạng xã hội.

2. Mục tiêu của đề tài

• Tìm hiểu sâu về các thuật toán phân cụm có thứ bậc các đồ thị dữ liệu.

• Cài đặt các thuật toán phân cụm có thứ bậc đã nghiên cứu, tiến hành thực

nghiệm trên các bộ dữ liệu chuẩn (các mạng xã hội) nhằm đánh giá kết quả

của từng thuật toán, qua đó lựa chọn thuật toán phù hợp cho việc phân cụm

các mạng xã hội.

3. Đối tượng và phạm vi nghiên cứu

▪ Đối tượng nghiên cứu:

 Tập đồ thị dữ liệu.

 Các cụm trên đồ thị.

 Các mạng xã hội.

▪ Phạm vi nghiên cứu

 Phân cụm có thứ bậc trên đồ thị dữ liệu.

 Nắm bắt và vận dụng lý thuyết đồ thị để biểu diễn mạng xã hội.

 Tìm hiểu các độ đo trên đồ thị.

 Nghiên cứu một số kỹ thuật phân cụm có thứ bậc trong khai phá đồ thị dữ

liệu nói chung và đồ thị mạng xã hội nói riêng.

4. Phương pháp luận và phương pháp nghiên cứu

Kết hợp lý thuyết được thu nhận từ nhiều nguồn như các bài báo, tài liệu, các

công trình nghiên cứu liên quan đến các độ đo trong phân cụm, phân cụm có thứ bậc

các đồ thị dữ liệu và các kỹ thuật phân cụm đồ thị dữ liệu, tiến hành xây dựng ứng

dụng thử nghiệm đánh giá hiệu quả của các thuật toán, làm nổi bật kết quả nghiên

cứu của luận văn.

5. Ý nghĩa khoa học của đề tài

Phân cụm có thứ bậc đồ thị dữ liệu nhằm tìm kiếm, phát hiện các cụm, các mẫu

dữ liệu tự nhiên tiềm ẩn và quan trọng trong tập đồ thị dữ liệu lớn để từ đó cung cấp

thông tin, tri thức cho việc ra quyết định.

Ngoài ra, phân cụm có thứ bậc đồ thị dữ liệu còn có thể được sử dụng như một

bước tiền xử lí cho các thuật toán khai phá dữ liệu đồ thị khác như là phân loại và mô

tả đặc điểm, có tác dụng trong việc phát hiện ra các cụm, các mẫu theo yêu cầu.

Luận văn gồm có phần mở đầu, kết luận và 03 chương, cụ thể như sau:

Chương I. Phân cụm dữ liệu và phân cụm đồ thị dữ liệu

Nghiên cứu tổng quan về các kỹ thuật phân cụm dữ liệu nói chung, ứng dụng

của phân cụm dữ liệu. Qua đó làm tiền đề để nghiên cứu sâu hơn về phân cụm đồ thị

dữ liệu: khái niệm đồ thị dữ liệu, các độ đo trong phân cụm dữ liệu nói chung và đồ

thị dữ liệu nói riêng, các kỹ thuật phân cụm đồ thị.

Chương II: Phân cụm có thứ bậc các đồ thị dữ liệu

Nghiên cứu, trình bày một số thuật toán phổ biến sử dụng kỹ thuật phân cụm

có thứ bậc trong phân cụm đồ thị dữ liệu như: thuật toán Chameleon, CURE, Girvan-

Newman, CNM (Clauset Newmen Moore), Rosvall Bergtrom và INC (Incre-Comm-

Extraction), đánh giá sơ bộ các ưu, nhược điểm của từng thuật toán.

Chương III. Ứng dụng thuật toán phân cụm có thứ bậc trong phân cụm đồ thị

dữ liệu các mạng xã hội

Giới thiệu tổng quan về bài toán phân cụm mạng xã hội, các bộ dữ liệu mạng

xã hội được sử dụng trong thực nghiệm. Tiến hành cài đặt các thuật toán đã nghiên

cứu ở chương 2 và thực nghiệm trên các bộ dữ liệu chuẩn để đánh giá các kết quả đạt

được, so sánh các thuật toán về thời gian thực thi, chất lượng phân cụm.

CHƯƠNG 1: PHÂN CỤM DỮ LIỆU VÀ PHÂN CỤM ĐỒ THỊ DỮ LIỆU

1.1. Phân cụm dữ liệu

1.1.1. Khái niệm và mục tiêu của phân cụm dữ liệu

1.1.1.1. Khái niệm phân cụm dữ liệu

Phân cụm dữ liệu là một kỹ thuật trong Data mining nhằm tìm kiếm, phát hiện

các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn và quan trọng trong tập dữ liệu lớn để từ

đó cung cấp thông tin, tri thức cho việc ra quyết định.

Phân cụm dữ liệu là sự phân chia một cơ sở dữ liệu lớn thành các nhóm dữ

liệu với trong đó các đối tượng tương tự như nhau. Trong mỗi nhóm, một số chi tiết

có thể không quan tâm đến để đổi lấy dữ liệu đơn giản hóa. Hay ta có thể hiểu “Phân

cụm dữ liệu là quá trình tổ chức các đối tượng thành từng nhóm mà các đối tượng ở

mỗi nhóm đều tương tự nhau theo một tính chất nào đó, những đối tượng không tương

tự tính chất sẽ ở nhóm khác” [3].

Phân cụm dữ liệu là một ví dụ của phương pháp học không có thầy. Không

giống như phân lớp dữ liệu, phân cụm dữ liệu không đòi hỏi phải định nghĩa trước

các mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân cụm dữ liệu là một cách học bằng

quan sát, trong khi phân lớp dữ liệu là học bằng ví dụ, ... Ngoài ra phân cụm dữ liệu

còn có thể được sử dụng như một bước tiền xử lí cho các thuật toán khai phá dữ liệu

khác như là phân loại và mô tả đặc điểm, có tác dụng trong việc phát hiện ra các cụm.

Chúng ta có thể thấy điều này với một ví dụ đơn giản như sau:

Hình 1.1: Ví dụ về phân cụm dữ liệu [3].

Trong trường hợp này, chúng ta dễ dàng xác định được 4 cụm dựa vào các dữ

liệu đã cho; các tiêu chí “tương tự” để phân cụm trong trường hợp này là khoảng

cách: hai hoặc nhiều đối tượng thuộc nhóm của chúng được “đóng gói” theo một

khoảng cách nhất định. Điều này được gọi là phân cụm dựa trên khoảng cách.

Một kiểu khác của phân cụm dữ liệu là phân cụm dữ liệu dựa vào khái niệm:

hai hay nhiều đối tượng thuộc cùng nhóm nếu có một định nghĩa khái niệm chung

cho tất cả các đối tượng trong đó. Nói cách khác, đối tượng của nhóm phải phù hợp

với nhau theo miêu tả các khái niệm đã được định nghĩa, không phải theo những biện

pháp đơn giản tương tự.

1.1.1.2. Mục tiêu của phân cụm dữ liệu

Mục tiêu của phân cụm dữ liệu là để xác định các nhóm nội tại bên trong một

bộ dữ liệu không có nhãn. Nhưng để có thể quyết định được cái gì tạo thành một cụm

tốt. Nhưng làm thế nào để quyết định cái gì đã tạo nên một phân cụm dữ liệu tốt ? Nó

có thể được hiển thị rằng không có tiêu chuẩn tuyệt đối “tốt nhất” mà sẽ là độc lập

với mục đích cuối cùng của phân cụm dữ liệu. Do đó, mà người sử dụng phải cung

cấp tiêu chuẩn, theo cách như vậy mà kết quả của phân cụm dữ liệu sẽ phù hợp với

nhu cầu của họ cần.

Ví dụ, chúng ta có thể quan tâm đến việc tìm kiếm đối tượng đại diện cho các

nhóm đồng nhất trong “các cụm tự nhiên” và mô tả thuộc tính không biết của chúng

trong việc tìm kiếm các nhóm hữu ích và phù hợp hoặc trong việc tìm kiếm các đối

tượng bất thường trong dữ liệu (cá biệt, ngoại lệ, nhiễu).

Hình 1.2: Ví dụ phân cụm các ngôi nhà dựa trên khoảng cách [3].

Một vấn đề thường gặp trong phân cụm là hầu hết các dữ liệu cần cho phân

cụm đều có chứa dữ liệu nhiễu do quá trình thu thập thiếu chính xác hoặc thiếu đầy

đủ, vì vậy cần phải xây dựng chiến lược cho bước tiền xử lí dữ liệu nhằm khắc phục

hoặc loại bỏ nhiễu trước khi chuyển sang giai đoạn phân tích cụm dữ liệu. Nhiễu ở

đây được hiểu là các đối tượng dữ liệu không chính xác, không tường minh hoặc là

các đối tượng dữ liệu khuyết thiếu thông tin về một số thuộc tính, ... Một trong các

kỹ thuật xử lí nhiễu phổ biến là việc thay thế giá trị các thuộc tính của đối tượng nhiễu

bằng giá trị thuộc tính tương ứng. Ngoài ra, dò tìm đối tượng ngoại lai cũng là một

trong những hướng nghiên cứu quan trọng trong phân cụm, chức năng của nó là xác

định một nhóm nhỏ các đối tượng dữ liệu khác thường so với các dữ liệu trong cơ sở

dữ liệu, tức là các đối tượng dữ liệu không tuân theo các hành vi hoặc mô hình dữ

liệu nhằm tránh sự ảnh hưởng của chúng tới quá trình và kết quả của phân cụm.

Hình 1.3: Ví dụ phân cụm các ngôi nhà dựa trên kích cỡ [3].

Theo các nghiên cứu đến thời điểm hiện nay thì chưa có một phương pháp

phân cụm tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc cơ sở

dữ liệu. Hơn nữa, đối với các phương pháp phân cụm cần có cách thức biểu diễn cấu

trúc của cơ sở dữ liệu, với mỗi cách thức biểu diễn khác nhau sẽ có tương ứng một

thuật toán phân cụm phù hợp. Vì vậy phân cụm dữ liệu vẫn đang là một vấn đề khó

và mở, vì phải giải quyết nhiều vấn đề cơ bản một cách trọn vẹn và phù hợp với nhiều

dạng dữ liệu khác nhau, đặc biệt là đối với dữ liệu hỗn hợp đang ngày càng tăng trong

các hệ quản trị dữ liệu và đây cũng là một trong những thách thức lớn trong lĩnh vực

khai phá dữ liệu.

1.1.2. Một số khái niệm cần thiết khi tiếp cận phân cụm dữ liệu

1.1.2.1. Phân loại các kiểu dữ liệu

Cho một CSDL D chứa n đối tượng trong không gian k chiều trong đó x, y, z

là các đối tượng thuộc D : x = (x1,x2,..,xk ); y = (y1,y2,..,yk); z = (z1,z2,..,zk), trong đó

xi, yi, zi với i = 1…k là các đặc trưng hoặc thuộc tính tương ứng của các đối tượng x,

y, z.

Sau đây là các kiểu dữ liệu:

a. Phân loại các kiểu dữ liệu dựa trên kích thước miền

- Thuộc tính liên tục (Continuous Attribute) : nếu miền giá trị của nó là vô hạn

không đếm được

- Thuộc tính rời rạc (DiscretteAttribute): Nếu miền giá trị của nó là tập hữu

hạn, đếm được

- Lớp các thuộc tính nhị phân: là trường hợp đặc biệt của thuộc tính rời rạc mà

miền giá trị của nó chỉ có 2 phần tử được diễn tả như : Yes/No hoặc Nam/Nữ,

False/true,…

b. Phân loại các kiểu dữ liệu dựa trên hệ đo

Giả sử rằng chúng ta có hai đối tượng x, y và các thuộc tính xi, yi tương ứng

với thuộc tính thứ i của chúng. Chúng ta có các lớp kiểu dữ liệu như sau :

- Thuộc tính định danh (Nominal Scale): đây là dạng thuộc tính khái quát hoá

của thuộc tính nhị phân, trong đó miền giá trị là rời rạc không phân biệt thứ tự và có

nhiều hơn hai phần tử -nghĩa là nếu x và y là hai đối tượng thuộc tính thì chỉ có thể

xác định là x ≠ y hoặc x = y.

- Thuộc tính có thứ tự (Ordinal Scale): là thuộc tính định danh có thêm tính

thứ tự, nhưng chúng không được định lượng. Nếu x và y là hai thuộc tính thứ tự thì

ta có thể xác định là x ≠ y hoặc x = y hoặc x > y hoặc x < y.

- Thuộc tính khoảng (Interval Scale): Với thuộc tính khoảng, chúng ta có thể

xác định một thuộc tính là đứng trước hoặc đứng sau thuộc tính khác với một khoảng

là bao nhiêu. Nếu xi > yi thì ta nói x cách y một khoảng xi - yi tương ứng với thuộc

tính thứ i.

- Thuộc tính tỉ lệ (Ratio Scale): là thuộc tính khoảng nhưng được xác định một

cách tương đối so với điểm mốc, thí dụ như thuộc tính chiều cao hoặc cân nặng lấy

điểm 0 làm mốc. Trong các thuộc tính dữ liệu trình bày ở trên, thuộc tính định danh

và thuộc tính có thứ tự gọi chung là thuộc tính hạng mục (Categorical), thuộc tính

khoảng và thuộc tính tỉ lệ được gọi là thuộc tính số (Numeric).

1.1.2.2. Độ đo tương tự và phi tương tự

Để phân cụm, người ta phải đi tìm cách thích hợp để xác định “khoảng cách”

giữa các đối tượng, hay là phép đo tương tự dữ liệu. Đây là các hàm để đo sự giống

nhau giữa các cặp đối tượng dữ liệu, thông thường các hàm này hoặc là để tính độ

tương tự (Similar) hoặc là tính độ phi tương tự (Dissimilar) giữa các đối tượng dữ

liệu.

1. Không gian metric

Tất cả các độ đo dưới đây được xác định trong không gian độ đo metric. Một

không gian metric là một tập trong đó có xác định các “khoảng cách” giữa từng cặp

phần tử, với những tính chất thông thường của khoảng cách hình học. Nghĩa là, một

tập X (các phần tử của nó có thể là những đối tượng bất kỳ) các đối tượng dữ liệu

trong CSDL D như đã đề cập ở trên được gọi là một không gian metric nếu:

- Với mỗi cặp phần tử x, y thuộc X đều xác định, theo một quy tắc nào đó, một

số thực δ(x,y), được gọi là khoảng cách giữa x và y.

- Quy tắc nói trên thoả mãn hệ tính chất sau : δ(x,y) > 0 nếu x ≠ y ; (ii) δ(x, y)

= 0 nếu x = y; (iii) δ(x,y) = δ(y,x) với mọi x,y; (iv) δ(x,y) ≤ δ(x,z) + δ(z,y).

Hàm δ(x,y) được gọi là một metric của không gian. Các phần tử của X được

gọi là các điểm của không gian này.

2. Thuộc tính khoảng cách:

Sau khi chuẩn hoá, độ đo phi tương tự của hai đối tượng dữ liệu x,y được xác

định bằng các metric khoảng cách như sau [6]:

- Khoảng cách Minskowski: trong đó q là số tự nhiên dương.

(1.1)

- Khoảng cách Euclide: Đây là trường hợp đặc biệt của khoảng cách

Minskowski trong trường hợp q = 2.

(1.2)

- Khoảng cách Manhattan: Đây là trường hợp đặc biệt của khoảng cách

Minskowski trong trường hợp q = 1.

(1.3)

- Khoảng cách cực đại: là trường hợp của khoảng cách Minskowski trong

trường hợp q = ∞.

(1.4)

3. Thuộc tính có thứ tự:

Giả sử i là thuộc tính thứ tự có Mi giá trị (Mi kích thước miền giá trị):

Các trạng thái Mi được sắp thứ tự như sau : [1…Mi], chúng ta có thể thay thế mỗi giá

trị của thuộc tính bằng giá trị cùng loại ri, với ri ∈{1…Mi}.

Mỗi một thuộc tính có thứ tự có các miền giá trị khác nhau, vì vậy chúng ta

chuyển đổi chúng về cùng miền giá trị [0,1] bằng cách thực hiện phép biến đổi sau

cho mỗi thuộc tính:

(𝑗) = 𝑍𝑖

(𝑗) − 1 𝑟𝑖 𝑀𝑖 − 1

(1.5) )

(𝒋), đây cũng chính là độ phi tương tự của thuộc tính có thứ tự.

Sử dụng công thức tính độ phi tương tự của thuộc tính khoảng đối với các giá

trị 𝒁𝒊 4. Thuộc tính tỉ lệ:

Có nhiều cách khác nhau để tính độ tương tự giữa các thuộc tính tỉ lệ. Một

trong những số đó là sử dụng công thức tính logarit cho mỗi thuộc tính. Hoặc loại bỏ

đơn vị đo của các thuộc tính dữ liệu bằng cách chuẩn hoá chúng, hoặc gán trọng số

cho mỗi thuộc tính giá trị trung bình, độ lệch chuẩn. Với mỗi thuộc tính dữ liệu đã

được gán trọng số tương ứng wi (1 <= i <= k), độ tương đồng dữ liệu được xác định

như sau:

𝑛 𝑑(𝑥, 𝑦) = √∑ 𝑤𝑖(𝑥𝑖 − 𝑦𝑖)2 𝑖=1

(1.6)

1.1.3. Một số kỹ thuật trong phân cụm dữ liệu

Các kỹ thuật phân cụm có rất nhiều cách tiếp cận và các ứng dụng trong thực

tế, nó đều hướng tới hai mục tiêu chung đó là chất lượng của các cụm khám phá được

và tốc độ thực hiện của thuật toán. Hiện nay, các kỹ thuật phân cụm có thể phân loại

theo các phương pháp tiếp cận chính như sau: phân cụm phân họach (Partitioning

Methods); phân cụm có thứ bậc (Hierarchical Methods); phân cụm dựa trên mật độ

(Density-Based Methods); phân cụm dựa trên lưới (Grid-Based Methods); phân cụm

dựa trên mô hình phân cụm (Model-Based Clustering Methods) và phân cụm có dữ

liệu ràng buộc (Binding data Clustering Methods) [5].

1.1.3.1. Phương pháp phân cụm phân hoạch

Kỹ thuật này phân hoạch một tập hợp dữ liệu có n phần tử thành k nhóm cho

đến khi xác định số các cụm được thiết lập. Số các cụm được thiết lập là các đặc trưng

được lựa chọn trước. Phương pháp này là tốt cho việc tìm các cụm hình cầu trong

không gian Euclidean. Ngoài ra, phương pháp này cũng phụ thuộc vào khoảng cách

cơ bản giữa các điểm để lựa chọn các điểm dữ liệu nào có quan hệ là gần nhau với

mỗi điểm khác và các điểm dữ liệu nào không có quan hệ hoặc có quan hệ là xa nhau

so với mỗi điểm khác. Tuy nhiên, phương pháp này không thể xử lí các cụm có hình

dạng kỳ quặc hoặc các cụm có mật độ các điểm dầy đặc. Các thuật toán phân hoạch

dữ liệu có độ phức tạp rất lớn khi xác định nghiệm tối ưu toàn cục cho vấn đề phân

cụm dữ liệu, do nó phải tìm kiếm tất cả các cách phân hoạch có thể được. Chính vì

vậy, trên thực tế thường đi tìm giải pháp tối ưu cục bộ cho vấn đề này bằng cách sử

dụng một hàm tiêu chuẩn để đánh giá chất lượng của cụm cũng như để hướng dẫn

cho quá trình tìm kiếm phân hoạch dữ liệu. Như vậy, ý tưởng chính của thuật toán

phân cụm phân hoạch tối ưu cục bộ là sử dụng chiến lược ăn tham (Greedy) để tìm

kiếm nghiệm.

Điển hình trong phương pháp tiếp cận theo phân cụm phân hoạch là các thuật

toán như: K_means, K - medoids, CLARA (Clustering Large Applications),

CLARANS (Clustering Large Applications based on RAndomized Search), ...[3]

1.1.3.2. Phương pháp phân cụm có thứ bậc

Phương pháp này xây dựng một có thứ bậc trên cơ sở các đối tượng dữ liệu

đang xem xét. Nghĩa là sắp xếp một tập dữ liệu đã cho thành một cấu trúc có dạng

hình cây, cây có thứ bậc này được xây dựng theo kỹ thuật đệ quy. Có hai cách tiếp

cận phổ biến của kỹ thuật này đó là: hòa nhập nhóm, thường được gọi là tiếp cận

(Bottom-Up); phân chia nhóm, thường được gọi là tiếp cận (Top-Down):

- Phương pháp “dưới lên” (Bottom up): Phương pháp này bắt đầu với mỗi đối

tượng được khởi tạo tương ứng với các cụm riêng biệt, sau đó tiến hành nhóm các

đối tượng theo một độ đo tương tự (như khoảng cách giữa hai trung tâm của hai

nhóm), quá trình này được thực hiện cho đến khi tất cả các nhóm được hòa nhập vào

một nhóm (mức cao nhất của cây có thứ bậc) hoặc cho đến khi các điều kiện kết thúc

thỏa mãn. Như vậy, cách tiếp cận này sử dụng chiến lược ăn tham trong quá trình

phân cụm.

Hình 1.4: Các chiến lược phân cụm phân cấp [3].

- Phương pháp “trên xuống” (Top Down): Bắt đầu với trạng thái là tất cả các

đối tượng được xếp trong cùng một cụm. Mỗi vòng lặp thành công, một cụm được

tách thành các cụm nhỏ hơn theo giá trị của một phép đo độ tương tự nào đó cho đến

khi mỗi đối tượng là một cụm, hoặc cho đến khi điều kiện dừng thỏa mãn. Cách tiếp

cận này sử dụng chiến lược chia để trị trong quá trình phân cụm.

Điển hình trong phương pháp tiếp cận theo phân cụm phân cấp là các thuật

toán như: AGNES (Agglomerative Nesting), DIANA (Divisive Analysis), BIRCH

(1996), CURE (1998), CHAMELEON (1999), ...[3].

Thực tế áp dụng, có nhiều trường hợp kết hợp cả hai phương pháp phân cụm

phân hoạch và phân cụm phân cấp, nghĩa là kết quả thu được của phương pháp phân

cấp có thể cải tiến thông qua bước phân cụm phân hoạch. Phân cụm phân hoạch và

phân cụm phân cấp là hai phương pháp phân cụm dữ liệu cổ điển, hiện đã có rất nhiều

thuật toán cải tiến dựa trên hai phương pháp này đã được áp dụng phổ biến trong khai

phá dữ liệu.

1.1.3.3. Phương pháp phân cụm dựa trên mật độ

Kỹ thuật này nhóm các đối tượng dữ liệu dựa trên hàm mật độ xác định, mật

độ là số các đối tượng lân cận của một đối tượng dữ liệu theo một nghĩa nào đó. Trong

cách tiếp cận này, khi một dữ liệu đã xác định thì nó tiếp tục được phát triển thêm các

đối tượng dữ liệu mới miễn là số các đối tượng lân cận này phải lớn hơn một ngưỡng

đã được xác định trước. Phương pháp phân cụm dựa trên mật độ của các đối tượng

để xác định các cụm dữ liệu có thể phát hiện ra các cụm dữliệu với hình thù bất kỳ.

Kỹ thuật này có thể khắc phục được các phần tử ngoại lai hoặc giá trị nhiễu rất tốt,

tuy nhiên việc xác định các tham số mật độ của thuật toán là rất khó khăn, trong khi

các tham số này lại có tác động rất lớn đến kết quả phân cụm.

Hình 1.5: Ví dụ về phân cụm dựa theo mật độ [3].

Điển hình trong phương pháp tiếp cận theo phân cụm dựa trên mật độ là các

thuật toán như: DBSCAN(KDD’96), DENCLUE (KDD’98), CLIQUE

(SIGMOD’98)), OPTICS (SIGMOD’99), ...[3].

1.1.3.4. Phương pháp phân cụm dựa trên lưới

Kỹ thuật phân cụm dựa trên lưới thích hợp với dữ liệu nhiều chiều, dựa trên

cấu trúc dữ liệu lưới để phân cụm, phương pháp này chủ yếu tập trung áp dụng cho

lớp dữ liệu không gian. Mục tiêu của phương pháp này là lượng hóa dữ liệu thành

các ô tạo thành cấu trúc dữ liệu lưới. Sau đó, các thao tác phân cụm chỉ cần làm việc

với các đối tượng trong từng ô trên lưới chứ không phải các đối tượng dữ liệu. Cách

tiếp cận dựa trên lưới này không di chuyển các đối tượng trong các ô mà xây dựng

nhiều mức phân cấp của nhóm các đối tượng trong một ô. Phương pháp này gần giống

với phương pháp phân cụm phân cấp nhưng chúng không trộn các ô, đồng thời giải

quyết khắc phục yêu cầu đối với dữ liệu nhiều chiều mà phương pháp phân phân cụm

dựa trên mật độ không giải quyết được. ưu điểm của phương pháp phân cụm dựa trên

lưới là thời gian xử lí nhanh và độc lập với số đối tượng dữ liệu trong tập dữ liệu ban

đầu, thay vào đó là chúng phụ thuộc vào số ô trong mỗi chiều của không gian lưới.

Hình 1.6: Cấu trúc phân cụm dựa trên lưới

Điển hình trong phương pháp tiếp cận theo phân cụm dựa trên lưới là các thuật

toán như: STING (a STatistical INformation Grid approach) bởi Wang, Yang và

Muntz (1997), WAVECLUSTER bởi Sheikholeslami, Chatterjee và Zhang (1998),

CLIQUE (Clustering In QUEst) bởi Agrawal, Gehrke, Gunopulos, Raghavan (1998),

...[3].

1.1.3.5. Phương pháp phân cụm dựa trên mô hình

Phương pháp này cố gắng khám phá các phép xấp xỉ tốt của các tham số mô

hình sao cho khớp với dữ liệu một cách tốt nhất. Chúng có thể sử dụng chiến lược

phân cụm phân hoạch hoặc phân cụm phân cấp, dựa trên cấu trúc hoặc mô hình mà

chúng giả định về tập dữ liệu và cách chúng hiệu chỉnh các mô hình này để nhận dạng

ra các phân hoạch.

Hình 1.7: Ví dụ về phân cụm dựa trên mô hình [3]

Phương pháp phân cụm dựa trên mô hình cố gắng khớp giữa các dữ liệu với

mô hình toán học, nó dựa trên giả định rằng dữ liệu được tạo ra bằng hỗn hợp phân

phối xác suất cơ bản. Các thuật toán phân cụm dựa trên mô hình có hai cách tiếp cận

chính: mô hình thống kê và mạng nơron. Phương pháp này gần giống với phương

pháp phân cụm dựa trên mật độ, vì chúng phát triển các cụm riêng biệt nhằm cải tiến

các mô hình đã được xác định trước đó, nhưng đôi khi nó không bắt đầu với một số

cụm cố định và không sử dụng cùng một khái niệm mật độ cho các cụm.

Điển hình trong phương pháp tiếp cận theo phân cụm dựa trên mô hình là các

thuật toán như: EM, COBWEB, CLASSIT, AutoClass (Cheeseman and Stutz, 1996),

...[3].

1.1.3.6. Phương pháp phân cụm có dữ liệu ràng buộc

Sự phát triển của phân cụm dữ liệu không gian trên cơ sở dữ liệu lớn đã cung

cấp nhiều công cụ tiện lợi cho việc phân tích thông tin địa lí, tuy nhiên hầu hết các

thuật toán này cung cấp rất ít cách thức cho người dùng để xác định các ràng buộc

trong thế giới thực cần phải được thỏa mãn trong quá trình phân cụm. Để phân cụm

dữ liệu không gian hiệu quả hơn, các nghiên cứu bổ sung cần được thực hiện để cung

cấp cho người dùng khả năng kết hợp các ràng buộc trong thuật toán phân cụm.

Hiện nay, các phương pháp phân cụm trên đã và đang được phát triển và áp

dụng nhiều trong các lĩnh vực khác nhau và đã có một số nhánh nghiên cứu được phát

triển trên cơ sở của các phương pháp đó như:

• Phân cụm thống kê: Dựa trên các khái niệm phân tích hệ thống, nhánh nghiên

cứu này sử dụng các độ đo tương tự để phân hoạch các đối tượng, nhưng chúng

chỉ áp dụng cho các dữ liệu có thuộc tính số.

• Phân cụm khái niệm: Kỹ thuật này được phát triển áp dụng cho dữ liệu hạng

mục, chúng phân cụm các đối tượng theo các khái niệm mà chúng xử lí.

• Phân cụm mờ: Sử đụng kỹ thuật mờ để phân cụm dữ liệu. Các thuật toán thuộc

loại này chỉ ra lược đồ phân cụm thích hợp với tất cả các hoạt động đời sống

hàng ngày, chúng chỉ xử lí các dữ liệu thực không chắc chắn.

• Phân cụm mạng Kohonen: Loại phân cụm này dựa trên khái niệm của các

mạng nơron. Mạng Kohonen có tầng nơron vào và các tầng nơron ra. Mỗi

nơron của tầng vào tương ứng với mỗi thuộc tính của bản ghi, mỗi một nơron

vào kết nối với tất cả các nơron của tầng ra. Mỗi liên kết được gắn liền với

một trọng số nhằm xác định vị trí của nơron ra tương ứng.

Hình 1.8: Các cách mà các cụm có thể đưa ra [3]

1.1.4. Các ứng dụng của phân cụm dữ liệu

Phân cụm dữ liệu có thể ứng dụng trong nhiều lĩnh vực như [3]:

- Thương mại: tìm kiếm nhóm các khách hàng quan trọng dựa vào các thuộc

tính đặc trưng tương đồng và những đặc tả của họ trong các bản ghi mua bán của cơ

sở dữ liệu;

- Sinh học: phân loại động, thực vật qua các chức năng gen tương đồng của

chúng;

- Thư viện: phân loại các cụm sách có nội dung và ý nghĩa tương đồng nhau

để cung cấp cho độc giả, cũng như đặt hàng với nhà cung cấp;

- Bảo hiểm: nhận dạng nhóm tham gia bảo hiểm có chi phí yêu cầu bồi thường

trung bình cao, xác định gian lận trong bảo hiểm thông qua các mẫu cá biệt;

- Quy hoạch đô thị: nhận dạng các nhóm nhà theo kiểu, vị trí địa lí, giá trị...

nhằm cung cấp thông tin cho quy hoạch đô thị;

- Nghiên cứu địa chấn : phân cụm để theo dõi các tâm động đất nhằm cung

cấp thông tin cho việc nhận dạng các vùng nguy hiểm;

- WWW: tài liệu phân loại, phân nhóm dữ liệu weblog để khám phá các nhóm

về các hình thức tiếp cận tương tự trợ giúp cho việc khai phá thông tin từ dữ liệu.

1.2. Phân cụm đồ thị dữ liệu

Phân cụm đồ thị là phân chia đồ thị lớn thành các đồ thị con. Mỗi đồ thị con

là một cụm. Các đối tượng trong cụm là các đỉnh biểu diễn cho các phần tử dữ liệu

tương đồng về tính chất và trọng số trên các cạnh biểu diễn cho độ tương tự (khoảng

cách) giữa các cặp dữ liệu.

1.2.1. Mô hình đồ thị dữ liệu

Đồ thị có trọng số được ký hiệu là G = (V, E, W), với V là tập đỉnh, E  V 

V là tập cạnh và W= (wij)i,j = 1, …N là tập các trọng số trên các cạnh của đồ thị, chính

là ma trận trọng số (ma trận liền kề) với N = |V|. Giữa hai đỉnh vi và vj ∈ V có cạnh

nối với nhau với trọng số wij > 0 nếu (vi, vj) ∈ E, ngược lại wij = 0, nghĩa là vi và vj ∈

V không có cạnh nối với nhau. Nếu W là ma trận đối xứng, nghĩa là wij = wji thì G là

đồ thị vô hướng, ngược lại, G là có hướng. Khi wij = 1 với mọi (vi, vj) ∈ E thì đồ thị

G được gọi là đồ thị không có trọng số.

Ma trận liền kề chứa các thông tin về trọng số của sự liên kết giữa các đỉnh

trong đồ thị. Những thông tin khác có thể nhận được thông qua bậc của các đỉnh. Bậc

của đỉnh vi được ký hiệu là deg(vi) là tổng trọng số của các đỉnh có cạnh nối với vi.

deg(vi) =

(1.7)

Ma trận bậc của đồ thị là ma trận D có đường chéo chính là các bậc của các

đỉnh.

(1.8)

𝐷(𝑖, 𝑗) = { deg(𝑣𝑖) 𝑖𝑓 𝑖 = 𝑗, ∀𝑖, 𝑗 = 1, … 𝑁 0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

Giả sử C = {C1, C2, …, CK} là một phân hoặch của tập đỉnh V của đồ thị G sao cho:

▪ Ci  Ø với mọi i = 1, 2, …, K, K  N

▪ Ci  Cj = Ø với mọi i  j

▪ C1  C2  …  Ck = V

Ta gọi C là phân cụm của đồ thị G. C là phân cụm tầm thường (Trivial) nếu K

= 1 hoặc mỗi cụm chỉ có 1 phần tử, K = N.

Mỗi cụm Ci xác định một đồ thị con Gi = (Ci, Ei, Wi), trong đó

▪ Ei = {(vm, vn)  E | vm, vn  Ci}

▪ Wi là ma trận con của W bằng cách chọn các hàng, cột theo chỉ số m mà vm

Ci.

Đồ thị thường được sử dụng để mô hình cho tập dữ liệu, trong đó các đỉnh

biểu diễn cho các phần tử dữ liệu và trọng số trên các cạnh biểu diễn cho độ tương tự

(khoảng cách) giữa các cặp dữ liệu.

Bên cạnh việc xác định ngữ nghĩa của việc sử dụng các đỉnh, cạnh của đồ thị

thì một vấn đề quan trọng nữa là việc tính độ tương tự (similarity) hoặc khoảng cách

(distance) giữa các đỉnh để xây dựng đồ thị. Cách tính độ tương tự cũng có thể thay

đổi và phụ thuộc vào các ứng dụng. Nhưng về nguyên tắc phải đảm bảo rằng, nếu hai

đỉnh có độ tương tự cao thì trong thực tế ứng dụng chúng phải gần nhau theo một

nghĩa nào đó.

Một số phương pháp mô hình đồ thị dữ liệu phổ biến [11]:

▪ 𝜺–đồ thị láng giềng (𝜺 -neighborhood graph): đồ thị được xây dựng bằng cách

kết nối những đỉnh mà khoảng cách từng cặp nhỏ hơn ε. Tương tự, δ- đồ thị

láng giềng (δ- neighborhood graph) là đồ thị được xây dựng bằng cách kết nối

những đỉnh mà khoảng cách từng cặp lớn hơn δ.

▪ 𝒌-đồ thị láng giềng gần nhất (k-nearest neighbor graph): đồ thị được xây dựng

bằng cách kết nối đỉnh vi với vj nếu vi là một trong số 𝑘 - láng giềng gần nhất

của vj hoặc vj là một trong số 𝑘 - láng giềng gần nhất của vi. Nói một cách

khác, để kết nối vi với vj nếu cả hai vi và vj là 𝑘 - láng giềng gần nhất của nhau.

Đồ thị liên thông mạnh: đồ thị được xây dựng bằng cách kết nối tất cả các đỉnh

với các đỉnh khác với độ tương tự dương.

1.2.2. Các loại độ đo

Một câu hỏi đặt ra là một kỹ thuật (thuật toán) phân cụm như thế nào được gọi

là tốt, tối ưu? Để có câu trả lời chúng ta phải xác định được các tiêu chí, hay độ đo

(measure) để đánh giá được một thuật toán phân cụm là tối ưu.

1.2.2.1. Độ đo cho phân cụm dữ liệu tổng quát

Một số độ đo độ tương tự phổ biến của phân cụm dữ liệu nói chung [23]:

(1) Đường kính cực tiểu (Minimum diameter - Charikar et al., 1997). Đường kính

của cụm được định nghĩa là khoảng cách cực đại giữa các cặp phần tử dữ liệu

trong cụm. Mục tiêu của phân cụm là cực tiểu hóa các đường kính của cụm,

nghĩa là

(1.9)

𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑚𝑎𝑥1≤𝑖≤𝑘𝑑𝑖𝑎𝑚𝑒𝑡𝑒𝑟(𝐶𝑖)

(1.10)

𝑑𝑖𝑎𝑚𝑒𝑡𝑒𝑟(𝐶𝑖) = 𝑚𝑎𝑥{|𝑥𝑗𝑥𝑖||𝑥𝑗, 𝑥𝑖𝜖𝑐𝑖}

(2) K-means (K-median - Charikar et al., 1999). Độ đo này được xác định thông

qua việc chọn nhiều nhất K phần tử dữ liệu như là các tâm của các cụm và

gán dữ liệu j vào tâm i với trọng số (phí tổn) wij. Mục đích của phân cụm dữ

liệu là cực tiểu hóa tổng của các phí tổn, nghĩa là:

𝑖,𝑗𝜖𝑁

𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 ∑ 𝑤𝑖𝑗𝑥𝑖𝑗 (1.11)

với xij  yi, với mọi i, j  N

Theo các điều kiện:

(1.12)

xij  {0, 1}, với mọi i, j  N, yi  {0, 1}, với mọi i  N (1.13)

Điều kiện ràng buộc (1.15) đảm bảo rằng mọi phần tử dữ liệu j ∈ 𝑁 đều được

gán cho một phần tử tâm 𝑖 ∈ 𝑁, (1.16) đảm bảo không có phần tử j ∈ 𝑁 mà lại được

gán vào cụm không có tâm 𝑖 ∈ 𝑁, và (1.17) đảm bảo rằng có nhiều nhất K phần tử dữ

liệu được chọn làm tâm của cụm.

(3) Tổng cực tiểu (Minimum Sum – Indyk 1999). Mục tiêu là cực tiểu hóa khoảng

𝑘

cách giữa các điểm trong tất cả các cụm.

𝑖=1

𝑥𝑖𝜖𝑐𝑖,𝑥𝑗𝑐𝑖

) 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 ∑ ∑ 𝑑(𝑥𝑖, 𝑥𝑗 (1.14)

Mặc dù các độ đo ở trên được xây dựng trên nền tảng toán học hợp lý và đơn

giản, tuy nhiên chúng lại dễ gây ra các lỗi. Hình 1.10 dưới đây minh chứng rằng việc

tối ưu các độ đo ở trên có thể tạo ra các cụm tồi trên thực tế. Hình 1.10 (a): mặc dù

việc phân cụm A tuân theo đường kính cực đại lớn hơn, nó vẫn tốt hơn so với B. Điều

này cũng xảy ra khi sử dụng độ đo tổng cực tiểu với hình 1.10 (a) và độ đo K-means

cho hình 1.10 (b).

Hình 1.9: (a) Tối ưu đường kính cực tiểu hoặc tổng cực tiểu tạo ra cụm B nhưng A

lại tốt hơn trên thực tế. (b) Tối ưu K-means tạo ra cụm B nhưng A lại tốt hơn [1].

1.2.2.2. Độ đo cho phân cụm đồ thị

Phân cụm đồ thị là tìm cách xác định các đồ thị con liên thông mạnh (cụm)

trong các đồ thị cho trước và mục tiêu cần đạt được là tối ưu hóa hàm đo chất lượng

của kỹ thuật phân cụm đồ thị. Một số độ đo phổ biến được sử dụng để phân cụm như

(i) Mật độ của cụm (intra-cluster density): Mật độ của cụm Ci được xác định

bằng tỷ số giữa tổng các trọng số của cạnh bên trong của Ci trên tổng các

trọng số của đồ thị.

(1.15) 𝑖𝑛𝑡𝑟𝑎𝑑𝑒𝑛𝑠𝑖𝑡𝑦(𝐶𝑖) = ∑ uϵci, 𝑣ϵ Ci𝑊𝑢𝑣 ∑(𝑢, 𝑣)ϵE 𝑊𝑢𝑣

𝐾

Mục tiêu là cực đại hóa tổng của các mật độ của tất cả các cụm:

𝑖=1

(1.16) 𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑒 ∑ 𝑖𝑛𝑡𝑟𝑎_𝑑𝑒𝑛𝑠𝑖𝑡𝑦(𝐶𝑖)

(ii) Mật độ giữa các cụm (inter-cluster density): Mật độ của cụm Ci và Cj được

xác định bằng tỷ số giữa tổng các trọng số của cạnh nối giữa Ci và Cj trên

tổng các trọng số của đồ thị.

(1.17) 𝑖𝑛𝑡𝑒𝑟_𝑑𝑒𝑛𝑠𝑖𝑡𝑦(𝐶𝑖, 𝐶𝑗) = ∑ 𝑢𝜖𝐶𝑖, 𝑣𝜖𝐶𝑗𝑊𝑢𝑣 ∑(𝑢, 𝑣)𝜖𝐸𝑊𝑢𝑣

𝐾−1

𝐾

Mục tiêu là cực tiểu hóa tổng của các mật độ giữa các cụm:

𝑖=1

𝑗=𝑖+1

(1.18) 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 ∑ ∑ 𝑖𝑛𝑡𝑒𝑟𝑑𝑒𝑛𝑠𝑖𝑡𝑦(𝐶𝑖,𝐶𝑗)

Nếu G được phân hoạch thành 2 cụm thì phân cụm C = (S, V\S) được gọi là

lát cắt (cut) của đồ thị G với S  V. Giá trị của lát cắt bằng tổng các trọng số của các

cạnh nối giữa hai cụm.

𝑢𝜖𝑆,𝑣𝜖𝑉\𝑆

(1.19) 𝑐𝑢𝑡(𝑆, 𝑉\𝑆) = ∑ 𝑊𝑢𝑣

Một lát cắt thỏa mãn điều kiện (1.18) được gọi là lát cắt cực tiểu.

(iii) Lát cắt tỷ lệ (ratio cut- Hagan and Kahng, 1992): được xác định như sau:

(1.20) 𝑟𝑎𝑡𝑖𝑜𝑐𝑢𝑡(𝐶𝑖, 𝑉\𝐶𝑖) = 𝑐𝑢𝑡(𝐶𝑖, 𝑉\𝐶𝑖 |𝐸𝐶𝑖|

trong đó |𝐸𝐶𝑖| là số lượng cạnh của cụm Ci.

𝐾

Mục tiêu là cực tiểu hóa tổng ratiocut cho tất cả các cụm:

(1.21)

𝑖=1

𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 ∑ 𝑟𝑎𝑡𝑖𝑜𝑐𝑢𝑡(𝐶𝑖, 𝑉\𝐶𝑖)

Lát cắt tỷ lệ phù hợp cho đồ thị không trọng số, tuy nhiên với các đồ thị có

trọng số, số lượng các đỉnh trong một cụm có thể không tương ứng mật độ bên trong

cụm là cao. Bởi vậy, ta nên thay chúng bằng lát cắt chuẩn bên dưới.

(iv) Lát cắt chuẩn (Normalized cut- Shi and Malik 2000): được xác định như sau:

(1.22)

𝑛𝑐𝑢𝑡(𝐶𝑖, 𝑉\𝐶𝑖) = 𝑐𝑢𝑡(𝐶𝑖, 𝑉\𝐶𝑖 𝑣𝑜𝑙(𝐶𝑖)

𝑢𝜖𝐶𝑖,𝑣𝜖𝑉

. Trong đó, 𝑣𝑜𝑙(𝐶𝑖) = ∑ 𝑊𝑢𝑣

𝐾

Mục tiêu là cực tiểu hóa tổng ncut() của tất cả cụm:

𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 ∑ 𝑛𝑐𝑢𝑡(𝐶𝑖, 𝑉\𝐶𝑖)

(1.23)

𝑖=1

(v) Độ đo tiêu chuẩn hai chiều (Bicriteria- Kannan et al, 2000) được xác định

như sau:

Bài toán cực đại hóa tiêu chuẩn hai chiều đòi hỏi: 1) các cụm phải có một số

độ dẫn cực tiểu α; 2) Tổng trọng số các cạnh giữa các cụm tối đa là ε phần của tổng

trọng số cạnh.

Mục tiêu là với giá trị α cho trước, tìm một cách phân cụm làm cực tiểu hóa

giá trị ε hoặc với giá trị ε cho trước, tìm một cách phân cụm mà làm cực đại hóa giá

trị α.

(vi) Độ đo đơn thể (modularity- Girvan và Newman, 2002) được xác định như

𝒎𝒐𝒅𝒖𝒍𝒂𝒓𝒊𝒕𝒚(𝑪𝒊) = 𝒆𝒊𝒊 – 𝒂𝒊𝟐, 𝒗ớ𝒊 𝒂𝒊 =

(1.24)

Trong đó, eii là phân số của các cạnh trong cụm Ci, eij (i  j) là phân số của các

cạnh nối đỉnh của cụm i sang cụm j.

Độ đo đơn thể được thể hiện như sau: mật độ của cạnh hiện thời trong cụm 𝐶𝑖

trừ đi giá trị kỳ vọng bên trong cụm Ci khi tất cả các đỉnh của đồ thị được kết nối theo

các bậc đã được xác định. Độ đo đơn thể của phân cụm là tổng của độ đo đơn thể của

𝐾

các cụm.

𝑗=1

(1.25) 𝑄 = ∑ 𝑚𝑜𝑑𝑢𝑙𝑎𝑟𝑖𝑡𝑦(𝐶𝑖)

Mục tiêu là cực đại hóa độ đo đơn thể của phân cụm Q.

Hiện nay độ đo đơn thể của phân cụm được sử dụng khá hiệu quả trong nhiều

ứng dụng khác nhau.

1.2.3. Một số kỹ thuật phân cụm đồ thị dữ liệu

1.2.3.1. Thuật toán phân cụm quang phổ

Thuật toán phân cụm quang phổ (Spectral Clustering Algorithm) [6] là thuật

toán phân cụm đồ thị dữ liệu quan trọng bởi lẽ, nó dựa vào cơ sở đại số tuyến tính và

dễ cài đặt để giải rất hiệu quả, giống như đối với các thuật toán phân cụm dữ liệu

truyền thống, như thuật toán K-means. Công cụ được sử dụng chính trong thuật toán

phân cụm quang phổ là ma trận Laplacian.

Dựa vào các ma trận trên để định nghĩa độ tương tự hoặc khoảng cách giữa

các đồ thị. Ma trận đồ thị Laplacian phi chuẩn [6] được ký hiệu là L, là ma trận biểu

diễn cho đồ thị thông qua ma trận liền kề W và ma trận D, được định nghĩa như sau:

L = D – W

(1.26)

Các ma trận đồ thị Laplacian chuẩn được định nghĩa như sau:

Lsym = D-1/2LD-1/2

(1.27)

Lrw = D-1L

(1.28)

D là ma trận có đường chéo chính là các số dương, do vậy D-1/2 chính là ma

trận có các phần tử trên đường chéo chính là căn bậc hai của các phần tử tương ứng

của D. Tương tự, D-1 là ma trận nghịch đảo của D.

Lý thuyết đồ thị quang phổ (spectral graph theory) dựa vào ma trận Laplacian

đã chỉ ra rằng một số cấu trúc cơ bản có thể có cùng tính chất Laplacian. Ma trận và

các giá trị véc tơ đặc trưng (eigenvectors) có thể được sử dụng để mô tả nhiều tính

chất của đồ thị [6].

Dựa vào lý thuyết đồ thị quang phổ, chúng ta chọn k (k < N) giá trị đặc trưng

nhỏ nhất X = e1, …, ek (∀i = [1, .., k], ei ∈ RN ) của ma trận Laplacian. Thay vì xét

trong không gian N × N chiều, chúng ta chỉ cần xét N đối tượng trong không gian con

k × k chiều. Hàng xi ∈ X sẽ biểu diễn cho vi ∈ V. Bằng cách đó chúng ta rút gọn được

ánh xạ đồ thị G vào X, trong đó độ tương tự của hai đỉnh vi và vj được xác định là

khoảng cách giữa hai giá trị đặc trưng tương ứng của chúng. Do vậy, chúng ta có thể

đồng nhất ba ký hiệu: đối tượng i, vector xi và đỉnh vi là tương đương với nhau theo

nghĩa biểu diễn cho cùng một thực thể dữ liệu.

Thuật toán phân cụm quang phổ phi chuẩn

Input: + Ma trận liền kề W ∈ Rn×n của đồ thị G = (V, E)

+ Ma trận D của đồ thị G

+ Số cụm K

Output: Các cụm C1, …, CK

1. Tính ma trận Laplacian L = D – W

2. Tính K vector giá trị đặc trưng u1, …, uK của L ứng với K giá trị đặc trưng

nhỏ nhất

3. Đặt U ∈ Rn×K là ma trận có các cột là các vector giá trị đặc trưng u1, …, uK

4. for i = 1 to n do

5. yi ∈ RK là vector ứng với hàng thứ i của U

6. Gọi thuật toán K-means đối với các tâm cụm y1, …, yK để phân V thành K

cụm.

Thuật toán phân cụm quang phổ chuẩn hóa

Input: + Ma trận liền kề W ∈ Rn×n của đồ thị G = (V, E)

+ Ma trận D của đồ thị G

+ Số cụm K

Output: Các cụm C1, …, CK

1. Tính ma trận Laplacian chuẩn hóa Lsym = D-1/2LD-1/2

2. Tính K vector giá trị đặc trưng đầu u1, …, uK của Lsym

3. Đặt U∈ Rn×K là ma trận có các cột là các vector giá trị đặc trưng u1, …, uK

4. Tạo ra ma trận T ∈ Rn×K từ U bằng cách chuẩn hóa các hàng theo chuẩn 1

𝑡𝑖𝑗 =

(1.29)

2 𝑢𝑖𝑘

√∑ 𝑢𝑖𝑗 𝑛 𝑘=1

5. for i = 1 to n do

6. yi ∈ RK là vector ứng với hàng thứ i của T

7. Gọi thuật toán K-means đối với các tâm cụm y1, …, yK để phân V thành K

cụm.

Cả hai thuật toán trên đều có độ phức tạp tính toán là (nK).

1.2.3.2. Thuật toán phân cụm Markov

Một họ thuật toán khác cho phân cụm đồ thị là dựa trên các bước đi ngẫu nhiên

trên đồ thị. Ý tưởng của phương pháp “bước đi ngẫu nhiên” được sử dụng ở đây là

nếu chúng ta bắt đầu xuất phát tại một đỉnh bất kỳ của đồ thị và thực hiện “bước đi

ngẫu nhiên” - chọn ngẫu nhiên tới một đỉnh khác thông qua cạnh liên kết giữa chúng

thì dường như chúng ta đi qua chủ yếu các cạnh giữa các đỉnh cùng thuộc một nhóm

nhiều hơn là đi qua các cạnh nối giữa các nhóm với nhau. Từ đặc điểm này có thể

tiến hành gom cụm dữ liệu với độ chính xác cao. Ví dụ từ hình 1.11: cạnh nối đỉnh 2

và đỉnh 5, có mật độ di chuyển qua lại ít hơn các cạnh khác, do nó là cạnh nối liền 2

nhóm đỉnh.

Hình 1.10: Minh họa mô hình đồ thị cho bước đi ngẫu nhiên [1]

Thuật toán thành công nhất trong họ thuật toán này chính là thuật toán phân

cụm Markov (MCL) được đề xuất bởi Dongen (2000).

Tương tự như ma trận Laplacian trong thuật toán phân cụm quang phổ, MCL

định nghĩa ma trận riêng của nó với tên gọi là ma trận Markov. Ma trận Markov 𝒯𝐺

nhận được bằng việc chuẩn hóa cột thứ q của ma trận trọng số W (gọi là ℳ𝐺) và nhân

-1. MCL đưa ra hai phép toán mở rộng

với nghịch đảo bậc của ma trận có giá trị các đường chéo là tổng của các trọng số cột

-1), tức là 𝒯𝐺 = ℳ𝐺𝒟𝐺

của ma trận W (gọi là 𝒟𝐺

và thổi phồng, trong đó phép toán mở rộng là việc lấy hàm mũ của một ma trận ngẫu

nhiên, còn phép thổi phồng là việc lấy hàm mũ Hadamard của một ma trận.

Phép toán mở rộng tương ứng với việc tính các bước đi ngẫu nhiên của chiều

dài lớn hơn, tức là các bước đi ngẫu nhiên với nhiều bước. Do các đường đi với chiều

dài lớn hơn là phổ biến hơn bên trong các cụm so với giữa các cụm khác nhau, tức là

có nhiều cách để đi từ một nút tới các nút khác.

Phép toán thổi phồng sau đó sẽ giúp tăng xác suất của các bước đi bên trong

cụm và giảm bước đi giữa các cụm.

Kết quả của việc lặp lại phép mở rộng và thổi phồng là một phân hoạch của

đồ thị. Thuật toán được thể hiện dưới đây:

Input: một đồ thị có cấu trúc G = (V,E) với ma trận Markov ℳ𝐺 và bậc ma

trận 𝒟𝐺 , tham số mở rộng e và tham số thổi phồng r.

-1.

Output: Kết quả phân cụm đồ thị

1. Tính ma trận Markov 𝒯𝐺 = ℳ𝐺𝒟𝐺

e // phép toán mở rộng

2. Khi 𝒯𝐺 chưa phải là điểm cố định:

𝒯𝐺 = 𝒯𝐺

𝑟 for all 𝑣 ∈ 𝑉 do 𝒯𝑢𝑣 = 𝒯𝑢𝑣

𝒯𝑢𝑣

for all 𝑢 ∈ 𝑉 do // phép toán thổi phồng

∑

𝑤∈𝑉

𝒯𝑢𝑤

for all 𝑣 ∈ 𝑉 do 𝒯𝑢𝑣 =

3. H: đồ thị tạo ra bởi các giá trị khác không của 𝒯𝐺

4. C: phép phân cụm tạo ra bởi các thành phần liên thông của H.

Thuật toán MCL có một số đặc điểm hấp dẫn như sau:

- Nó thực hiện đơn giản với hai phép toán mở rộng và thổi phồng.

- Nó có tính thích nghi. Với việc điều chỉnh tham số mở rộng và thổi phồng,

các phép phân cụm trên các tỷ lệ khác nhau có thể được tìm thấy.

MCL đã được áp dụng trong một số các lĩnh vực khác nhau với các thành công

vang dội, đặc biệt là trong lĩnh vực tin sinh và tin hóa.

1.2.3.3. Thuật toán pha tạp khác

a. Một trong số các thuật toán phân cụm đồ thị sớm nhất đó là thuật toán

Kerninghan-Lin (1970). Mục đích là để phân hoạch đồ thị thành hai phần với kích

thước bằng nhau với số lượng các cạnh bị cắt là nhỏ nhất. Thuật toán hoạt động với

việc lặp cải tiến, bắt đầu từ việc chia làm hai phần tùy ý và đổi chỗ các cặp nút để cải

thiện giá trị của việc phân hoạch. Độ phức tạp của thuật toán là O(n3) với n là số đỉnh

của đồ thị. Độ phức tạp cao khiến thuật toán không được áp dụng nhiều trong thực

tế. Tuy nhiên thuật toán này được nghiên cứu, mở rộng bởi các nhà nghiên cứu khác.

b. Karypis và Kumar (1999) đề xuất một tiếp cận đa mức cho việc phân chia

đồ thị thành hai cụm. Ý tưởng cơ bản đó là rút gọn đồ thị bằng cách giảm bớt các

đỉnh và cạnh (pha thô), phân hoạch đồ thị nhỏ hơn (pha phân hoạch) và sau đó là tinh

chỉnh để cấu trúc một phân hoạch cho đồ thị gốc (pha tinh chỉnh). Thuật toán được

mô tả như sau:

Input: một đồ thị có cấu trúc G0 = (V0,E0).

Output: Kết quả phân cụm đồ thị G0.

Pha thô:

Đồ thị G0 được biến đổi thành một chuỗi các đồ thị nhỏ hơn G1, G2, ..., Gm sao

cho |V0| > |V1| > ...> |Vm|.

Pha phân hoạch:

Một phân hoạch 2 chiều Pm của đồ thị Gm = (Vm, Em) được tính bằng cách phân

hoạch Vm thành hai phần, mỗi phần chứa một nửa số đỉnh của đồ thị G0.

Pha tinh chỉnh:

Phân hoạch Pm của Gm được chiếu trở lại G0 bằng việc đi qua các phân hoạch

trung gian Pm-1, ..., P0.

Thuật toán này có tên gọi là METIS. Mặc dù các tác giả không đưa ra độ phức

tạp chính xác của thuật toán, họ tuyên bố rằng thời gian chạy của thuật toán là rất

nhanh. Ngoài ra, các phân hoạch được tạo ra bởi METIS là tốt hơn từ 10% đến 50%

so với các thuật toán phân hoạch quang phổ, dựa trên việc thực nghiệm trên một lượng

lớn các đồ thị dữ liệu. Vấn đề của METIS đó là nó chỉ tạo ra được hai cụm và Dhilon

et al (2005) đã mở rộng thuật toán cho K cụm.

c. Aksoy và Haralick (1999) đề xuất một thuật toán phân cụm bắt đầu với việc

tìm kiếm các vùng dày trong đồ thị và sau đó trộn các vùng dày này theo một số tiêu

chí. Bởi thế, điểm mấu chốt trong thuật toán này là cách tìm các vùng dày của đồ thị.

Thuật toán được miêu tả như sau:

Input: Đồ thị G = (V, E) với ma trận kề 𝑊 ∈ ℝ𝑛×𝑛.

Output: Kết quả phân cụm đồ thị G.

Bước 1: Tìm tất cả các vùng dày của đồ thị.

Bước 2: Trộn các vùng dày nếu thỏa mãn một số tiêu chí.

Mặc dù các tác giả không đề cập đến độ phức tạp khi thực hiện thuật toán, một

phân tích đơn giản chỉ ra rằng độ phức tạp phụ thuộc chủ yếu vào việc tìm kiếm các

vùng dày trên một đồ thị thưa với độ phức tạp O(nm2) trong trường hợp xấu nhất.

Một vấn đề khác đó là thuật toán chỉ làm việc trên các đồ thị không có trọng số, tuy

nhiên nó có thể được mở rộng để làm việc trên các đồ thị có trọng số.

d) Newman (2004) đề xuất thuật toán phân cụm phân cấp tích tụ để nhận được

giá trị độ đo đơn thể tối ưu theo phương pháp tham lam. Bắt đầu với mỗi đỉnh như là

các cụm, thuật toán lặp lại việc hòa các cặp cụm, việc lựa chọn ở mỗi bước để hòa

nhập các cụm phải làm cho giá trị độ đo đơn thể tăng lên giá trị lớn nhất có thể. Tiến

trình của thuật toán sẽ tạo ra một "dendrogram" và số lượng các cụm thay đổi từ lớn

nhất thành nhỏ nhất. Ta có thể lựa chọn một phép phân cụm tốt nhất bởi việc tìm

kiếm giá trị đơn thể tối ưu. Dưới đây là miêu tả của thuật toán:

Input: Đồ thị G = (V, E) với ma trận kề 𝑊 ∈ ℝ𝑛×𝑛.

Output: Kết quả phân cụm đồ thị G.

Bước 1. Khởi tạo phân cụm bằng cách gán mỗi đỉnh là một cụm.

Bước 2. Hòa nhập cặp cụm làm tăng giá trị độ đo đơn thể lên lớn nhất (hoặc

làm giảm ít nhất).

Bước 3. Lặp lại bước 2 cho tới khi phép phân cụm chỉ còn lại một cụm.

Bước 4. Tìm phép phân cụm cho độ đo đơn thể lớn nhất.

Thành công của thuật toán này đó là độ phức tạp của thuật toán chỉ là

O(n(m+n)) trong trường hợp xấu nhất và là O(n2) trên đồ thị thưa [12].

1.3. Kết luận chương 1

Chương này đã trình bày tổng quan về các kỹ thuật phân cụm dữ liệu nói chung,

ứng dụng của phân cụm dữ liệu. Qua đó làm tiền đề để nghiên cứu sâu hơn về phân

cụm đồ thị dữ liệu: khái niệm dữ liệu đồ thị, các độ đo trong phân cụm dữ liệu nói

chung và dữ liệu đồ thị nói riêng, các kỹ thuật phân cụm dữ liệu đồ thị. Với các kiến

thức đã nghiên cứu về phân cụm dữ liệu đồ thị tổng quát, trong chương tiếp theo sẽ

tập trung trình bày kỹ hơn về các kỹ thuật phân cụm có thứ bậc dữ liệu đồ thị.

CHƯƠNG 2: PHÂN CỤM CÓ THỨ BẬC CÁC ĐỒ THỊ DỮ LIỆU

Trong phân cụm có thứ bậc, đồ thị được tổ chức thành các mức, từ mức cao

(mức tổng quát) và đồ thị được chi tiết dần theo các mức từ trên xuống (top down) để

giảm độ phân cấp [3, 7]. Các phương pháp phân cụm có thứ bậc đều dựa trên một

nguyên lý chung là dựa vào độ tương tự giữa các cặp đối tượng, những đối tượng có

quan hệ nhiều hơn với nhau sẽ gần nhau hơn những đối tượng có ít mối quan hệ hơn.

Hiện nay có nhiều phương pháp phân cụm có thứ bậc đã được phát triển và

chúng có những ưu, nhược điểm riêng, song trong luận văn này chỉ tập trung vào

một số thuật toán chính:

2.1. Thuật toán CHAMELEON

Thuật toán phân cụm CHAMELEON sử dụng mô hình động trong phân cụm

có thứ bậc, được phát triển bởi Karypis, Han và Kumar (1999). Khi xử lý phân cụm,

hai cụm được hoà nhập nếu liên kết nối và độ chặt (độ gần) giữa hai cụm được liên

kết cao với liên kết nối và độ chặt nội tại của các đối tượng nằm trong phạm vi các

cụm. Xử lý hoà nhập dựa trên mô hình động tạo điều kiện thuận lợi cho sự khám phá

ra các cụm tự nhiên và đồng nhất, nó áp dụng cho tất cả các kiểu dữ liệu miễn là hàm

tương đồng được chỉ định [1, 3].

CHAMELEON có được dựa trên quan sát các yếu điểm của hai thuật toán

phân cụm có thứ bậc: CURE và ROCK. CURE và các lược đồ quan hệ bỏ qua thông

tin về liên kết nối tổng thể của các đối tượng trong hai cụm ; ngược lại, ở ROCK, các

lược đồ quan hệ lờ đi thông tin về độ chặt của hai cụm trong khi nhấn mạnh liên kết

nối của chúng.

Input: Cơ sở dữ liệu với n bộ, số lượng cụm con K

Output: Các cụm dữ liệu Ci (0 < i

CHAMELEON trước tiên sử dụng một thuật toán phân chia đồ thị để phân

cụm các mục dữ liệu vào trong một số lượng lớn các cụm con tương đối nhỏ. Sau đó

dùng giải thuật phân cụm có thứ bậc tập hợp để tìm ra các cụm xác thực bằng cách

lặp lại việc kết hợp các cụm này với nhau. Để xác định các cặp cụm con giống nhau

nhất, cần đánh giá cả liên kết nối cũng như độ chặt của các cụm, đặc biệt là các đặc

tính nội tại của bản thân các cụm. Do vậy nó không tuỳ thuộc vào một mô hình tĩnh

được cung cấp bởi người dùng và có thể tự động thích ứng với các đặc tính nội tại

của các cụm đang được hoà nhập.

Chameleon miêu tả các đối tượng dựa trên tiếp cận đồ thị được dùng phổ biến:

k-láng giềng gần nhất. Mỗi đỉnh của đồ thị k-láng giềng gần nhất đại diện cho một

đối tượng dữ liệu, tại đó tồn tại một cạnh giữa hai đỉnh (đối tượng), nếu một đối tượng

là giữa k đối tượng giống nhau so với các đối tượng khác. Đồ thị k-láng giềng gần

nhất Gk có được khái niệm láng giềng động: Bán kính láng giềng của một điểm dữ

liệu được xác định bởi mật độ của miền mà trong đó các đối tượng cư trú. Trong một

miền dày đặc, láng giềng được định nghĩa hẹp, và trong một miền thưa thớt, láng

giềng được định rộng hơn. Chameleon chỉ rõ sự tương đồng giữa mỗi cặp các cụm Ci

và Cj theo liên kết nối tương đối RI (Ci ,Cj) và độ chặt tương đối RC(Ci ,Cj) của chúng.

Liên kết nối tương đối RI(Ci,Cj) giữa hai cụm Ci và Cj được định nghĩa như

liên kết nối tuyệt đối giữa Ci và Cj đã tiêu chuẩn hoá đối với liên kết nối nội tại của

hai cụm Ci và Cj. Đó là:

|𝐸𝐶𝐶𝑖,𝐶𝑗|

(2.1)

𝑅𝐼(𝐶𝑖, 𝐶𝑗) =

|𝐸𝐶𝐶𝑖| + |𝐸𝐶𝐶𝑗| 1 2

với 𝐸𝐶{𝐶𝑖,𝐶𝑗} là cạnh cắt của cụm chứa cả Ci và Cj để cụm này được rơi vào trong Ci

và Cj, và tương tự như vậy, 𝐸𝐶𝐶𝑖 (hay 𝐸𝐶𝐶𝑖) là kích thước của min-cut bisector (tức

là trọng số của các cạnh mà chia đồ thị thành hai phần thô bằng nhau).

Độ chặt tương đối giữa một cặp các cụm Ci và Cj là RC(Ci,Cj) được định nghĩa

như là độ chặt tuyệt đối giữa Ci và Cj được tiêu chuẩn hóa đối với liên kết nối nội tại

của hai cụm Ci và Cj. Đó là:

𝑆̅𝐸𝐶{𝐶𝑖,𝐶𝑗}

(2.2)

𝑅𝐶(𝐶𝑖, 𝐶𝑗) =

+ 𝑆̅𝐸𝐶𝐶𝑖 𝑆̅𝐸𝐶𝐶𝑗 |𝐶𝑖| |𝐶𝑖| + |𝐶𝑗| |𝐶𝑗| |𝐶𝑖| + |𝐶𝑗|

Với 𝑆̅𝐸𝐶{𝐶𝑖,𝐶𝑗} là trọng số trung bình của các cạnh kết nối các đỉnh trong Ci tới tương ứng là trọng số trung bình của các cạnh thuộc về min-cut

, 𝑆̅𝐸𝐶𝐶𝑗 Cj và 𝑆̅𝐸𝐶𝐶𝑖 bisector của cụm Ci và Cj.

Hình 2.1: Phân cụm Chameleon [1]

Giải thuật Chameleon có nhiều khả năng khám phá ra các cụm có hình dạng

tùy úy với chất lượng cao hơn so với CURE. Tuy nhiên, thời gian chi phí cho xử lý

dữ liệu có số chiều lớn có thể là O(n2) cho n đối tượng.

2.2. Thuật toán CURE

CURE (Clustering Using Representatives – Phân cụm dữ liệu sử dụng điểm

đại diện) là thuật toán sử dụng chiến lược dưới lên (Bottom-Up) của kĩ thuật phân

cụm có thứ bậc. Trong hầu hết các thuật toán thực hiện phân cụm với các cụm hình

cầu và kích thước tương tự, như vậy là không hiệu quả khi xuất hiện các phần tử

ngoại lai. [10] Thuật toán này định nghĩa một số cố định các điểm đại diện nằm rải

rác trong toàn bộ không gian dữ liệu và được chọn để mô tả các cụm được hình thành.

Các điểm này được tạo ra bởi trước hết lựa chọn các đối tượng nằm rải rác trong cụm

và sau đó “co lại” hoặc di chuyển chúng về trung tâm cụm bằng nhân tố co cụm. Quá

trình này được lặp lại và như vậy trong quá trình này có thể đo tỷ lệ gia tăng của cụm.

Tại mỗi bước của thuật toán, hai cụm có cặp các điểm đại diện gần nhau (mỗi điểm

trong cặp thuộc về mỗi cụm khác nhau) được hòa nhập. Như vậy, có nhiều hơn một

điểm đại diện mỗi cụm cho phép CURE khám phá được các cụm có hình dạng không

phải hình cầu. Việc co lại các cụm có tác dụng làm giảm tác động của các phần tử

ngoại lai. Như vậy, thuật toán này có khả năng xử lý tốt trong trường hợp có các phần

tử ngoại lai và làm cho hiệu quả với hình dạng không phải hình cầu và kích thước độ

rộng biến đổi. Hơn nữa, nó tỷ lệ tốt với CSDL lớn mà không làm giảm chất lượng

phân cụm.

Đặt c là điểm đại diện cho mỗi cụm, chọn c rải rác sao cho có thể nắm bắt

được hình dạng vật lý và hình học của cụm. Các điểm này sau đó được “co lại” hoặc

di chuyển chúng về trung tâm cụm bằng nhân tố co cụm α trong đó 0 <α <1.

Hình 2.2: Sự di chuyển về trung tâm cụm [1]

Những điểm này được sử dụng như là đại diện và ở mỗi bước của thuật toán,

hai cụm với cặp gần gũi nhất của các đại diện được sáp nhập. Sau mỗi lần sáp nhập,

một điểm c được lựa chọn từ các đại diện ban đầu của cụm trước đó để đại diện cho

cụm mới. Cụm sáp nhập dừng cho đến khi mục tiêu k cụm được tìm thấy.

Hình 2.3: Sự sáp nhập của các cụm [1]

Với cách thức sử dụng nhiều hơn một phần tử đại diện cho các cụm, CURE có

thể khám phá được các cụm có các hình thù và kích thước khác nhau trong cơ sở dữ

liệu lớn. Việc co các đối tượng đại diện lại có tác dụng làm giảm tác động của các

phần tử ngoại lai, vì vậy, CURE có khả năng xử lý đối với các phần tử ngoại lai.

Hình dưới đây là ví dụ về các dạng và kích thước cụm dữ liệu được khám phá bởi

CURE.

Hình 2.4: Cụm dữ liệu khai phá bởi thuật toán CURE [1]

Để xử lý được các CSDL lớn, CURE sử dụng ngẫu nhiên và phân hoạch, một

mẫu là được xác định ngẫu nhiên trước khi được phân hoạch, và sau đó được tiến

hành phân cụm trên mỗi phân hoạch, như vậy mỗi phân hoạch là từng phần đã được

phân cụm, các cụm thu hoạch được lại được phân cụm lần thứ hai để thu được các

cụm con mong muốn, nhưng mẫu ngẫu nhiên không nhất thiết đưa ra một mô tả tốt

cho toàn bộ tập dữ liệu.

Thuật toán CURE được thực hiện qua các bước cơ bản sau:

Input: Cơ sở dữ liệu với n đối tượng

Output: K cụm dữ liệu

Bước 1: Chọn một mẫu ngẫu nhiên từ tập dữ liệu ban đầu.

Bước 2: Phân hoạch mẫu này thành nhiều nhóm dữ liệu có kích thước bằng

nhau: ý tưởng ở đây là phân hoạch mẫu thành p nhóm dữ liệu bằng nhau, kích thước

của mỗi phân hoạch là n’/p (n’ là kích thước mẫu).

Bước 3: Phân cụm các điểm của mỗi nhóm : Thực hiện PCDL cho các nhóm

cho đến khi mỗi nhóm được phân thành n’/pq (với q>1).

Bước 4: Loại bỏ các phần tử ngoại lai: Trước hết, khi các cụm được hình thành

cho đến khi số các cụm giảm xuống một phần so với số các cụm ban đầu. Sau đó,

trong trường hợp các phần tử ngoại lai được lấy mẫu cùng với quá trình pha khởi tạo

mẫu dữ liệu, thuật toán sẽ tự động loại bỏ các nhóm nhỏ.

Bước 5: Phân cụm các cụm không gian: các đối tượng đại diện cho các cụm

di chuyển về hướng trung tâm cụm, nghĩa là chúng được thay thế bởi các đối tượng

gần trung tâm hơn.

Bước 6: Đánh dấu dữ liệu với các nhãn tương ứng.

Độ phức tạp tính toán của thuật toán CURE là O(n2log(n)). CURE là thuật

toán tin cậy trong việc khám phá ra các cụm với hình thù bất kỳ và có thể áp dụng tốt

đối với dữ liệu có phần tử ngoại lai và trên các tập dữ liệu hai chiều. Tuy nhiên, nó

lại rất nhạy cảm với các tham số như số các đối tượng đại diện, tỉ lệ co của các phần

tử đại diện.

Đánh giá thuật toán CURE

Ưu điểm:

Bằng cách sử dụng trên một đại diện cho một cụm, CURE có khả năng khám

phá được các cụm có hình thù và kích thước bất kỳ trong tập dữ liệu lớn. Việc co các

đối tượng đại diện có tác dụng làm giảm tác động của các đối tượng ngoại lai. Do đó

CURE có thể xử lý tốt các đối tượng ngoại lai.

Nhược điểm:

CURE là dễ bị ảnh hưởng bởi các tham số cho bởi người dùng như cỡ mẫu, số

cụm mong muốn.

2.3. Thuật toán Girvan-Newman

2.3.1. Giới thiệu về độ đo modularity

Có nhiều thuật toán để phân cụm đồ thị dữ liệu. Hầu hết các thuật toán này đều

hoạt động tốt trên các bộ dữ liệu nhân tạo hoặc các bộ dữ liệu thực tế mà các cụm đã

biết trước. Tuy nhiên, có một câu hỏi đặt ra đó là làm sao để đánh giá chất lượng của

các cấu trúc cụm đã được phân chia bởi các thuật toán này khi chúng ta làm việc trên

các bộ dữ liệu thực tế mà chưa biết trước các cụm đó. Một khái niệm mà chúng ta đã

biết đó một cụm tốt khi các cạnh bên trong cụm đó là dày đặc hơn. Một nút được kết

nối tới nhiều nút khác trong cụm hơn là kết nối tới các nút khác cụm. Một độ đo được

định nghĩa bởi Girvan và Newman [9, 13, 16] đó là độ đo đơn thể Q được sử dụng

cho việc đánh giá chất lượng của các cụm . Đặt Avw là phần tử của ma trận kề biểu

diễn đồ thị dữ liệu:

(2.3) Avw = { 1 𝑛ế𝑢 𝑐ó 𝑐ạ𝑛ℎ 𝑛ố𝑖 𝑔𝑖ữ𝑎 𝑐á𝑐 đỉ𝑛ℎ 𝑣 𝑣à 𝑤 0 𝑛ế𝑢 𝑘ℎô𝑛𝑔 𝑐ó 𝑐ạ𝑛ℎ 𝑛ố𝑖 𝑔𝑖ữ𝑎 𝑣 𝑣à 𝑤

và giả sử các đỉnh được chia vào trong các cụm với đỉnh v sẽ thuộc cụm cv. Theo đó,

số phép phân chia các cạnh vào trong các cụm, tức là kết nối các đỉnh nằm cùng cụm

𝑣𝑤

là:

(2.4) = 1 2𝑚 ∑ 𝐴𝑣𝑤𝛿(𝑐𝑣, 𝑐𝑤) ∑ 𝐴𝑣𝑤 𝑣𝑤 ∑ 𝐴𝑣𝑤𝛿(𝑐𝑣, 𝑐𝑤) 𝑣𝑤

với hàm 𝛿 nhận giá trị như sau: 𝛿(𝑖, 𝑗) = 1 nếu i=j và 𝛿(𝑖, 𝑗) =0 trong trường hợp còn

lại.

(2.5) m = là số cạnh của đồ thị. ∑ 𝐴𝑣𝑤 𝑣𝑤

Bậc kv của đỉnh v được đỉnh nghĩa là số cạnh gắn với v:

(2.6) kv = ∑ 𝐴𝑣𝑤 𝑤

Nếu các kết nối giữa các đỉnh được tạo ra ngẫu nhiên thì xác suất tồn tại một

cạnh kết nối hai đỉnh v và w liên quan đến bậc của đỉnh sẽ là: kvkw/2m.

Khi đó giá trị modularity Q được tính như sau:

(2.7) ] 𝑄 = 𝛿(𝑐𝑣, 𝑐𝑤) 1 2𝑚 𝑘𝑣𝑘𝑤 2𝑚 ∑ [𝐴𝑣𝑤 − 𝑣𝑤

Một giá trị Q cao tức là thể hiện một phép phân hoạch cụm tốt. Do đó nhiệm

vụ của bài toán là đi tìm giá trị Q cao nhất có thể. Tuy nhiên, với một không gian tìm

kiếm vô cùng lớn (độ phức tạp NP-khó) khiến cho việc tìm phương án tối ưu của Q

là không khả thi.

2.3.2. Độ đo trung gian

 Độ đo trung gian của một đỉnh được tính bằng tổng số các đường đi ngắn nhất

• Khái niệm:

ngang qua đỉnh đang xét chia cho tổng số các đường đi ngắn nhất của toàn mạng.

Nói cách khác, độ đo trung gian dùng để xác định vị trí của tác nhân trong mạng

mà nó có khả năng kết nối đến những cặp tác nhân hay những nhóm tác nhân khác.

• Công thức tính:

- Cho đồ thị G = (V, E) có n đỉnh.

- Công thức tính Độ đo trung gian của đỉnh v :

(2.8)

Trong đó:

: Tổng số đường đi ngắn nhất từ đỉnh s đến t và có qua đỉnh v (s ≠ v ≠ t).

- Công thức tính độ đo trung gian của đỉnh v theo dạng chuẩn:

: Tổng số các đường đi ngắn nhất từ đỉnh s đến t (s ≠ v ≠ t).

(2.9)

′ (𝑣) =

𝐶𝐵

𝜎𝐵(𝑣) (𝑛−1)(𝑛− 2) / 2

• Miền giá trị:

Độ đo này có miền giá trị nằm trong khoảng [0..1], node có giá trị càng lớn thì

node đó sẽ có sự ảnh hưởng tới việc phân bổ cấu trúc của các cụm hay nhóm trong

mạng càng lớn. Một tác nhân có vai trò trung tâm càng lớn trong mạng thì sẽ có tầm

ảnh hưởng lớn trong việc kiểm soát mọi thông tin trao đổi giữa các tác nhân khác

trong mạng.

2.3.3. Thuật toán phân cụm Girvan-Newman

Thay vì việc tìm kiếm những nút mạng trong đồ thị có độ gắn kết cao với nhau,

phương pháp phân cụm bằng thuật toán phân chia được đưa ra như một cách giải

quyết hữu hiệu. Để tránh các khuyết điểm của phương pháp phân nhóm có thứ bậc,

thay vì cố gắng để xây dựng một biện pháp tìm cạnh trung tâm của cụm, chúng ta đi

tìm những cạnh ít trung tâm nhất, cạnh đó được gọi tên là cạnh giữa cụm. Thuật toán

này dựa trên quan niệm cho rằng khi các cụm được gắn kết với nhau thì đường đi

giữa cụm này đến cụm khác sẽ đi qua các cạnh nối giữa các cụm với tần suất cao.

Mục đích chính của thuật toán là tìm những cạnh nối đó. Thay vì việc xây dựng cụm

bằng cách thêm vào các cạnh mạnh mẽ nhất, chúng ta sẽ xây dựng bằng cách loại bỏ

dần dần các cạnh nối từ đồ thị ban đầu. Khi đó, các cụm trong mạng sẽ bị ngắt kết

nối với nhau, ta có thể xác định được cách phân vùng đồ thị thành các phần nhỏ riêng

rẽ. Để làm được việc này, điều quan trọng nhất của thuật toán là việc tính toán như

thế nào, sử dụng tính chất nào để phát hiện ra những cạnh nối này, từ đó loại bỏ chúng

ra khỏi đồ thị. Thuật toán lần đầu tiên được đề xuất bởi Freeman. Theo Freeman, các

cạnh được coi là cạnh có số lượng con đường ngắn nhất giữa các cặp đỉnh khác nhau

chạy qua nó. Cạnh nối có ảnh hưởng rất lớn đến dòng chảy của thông tin giữa các nút

khác, đặc biệt là trong trường hợp thông tin lưu truyền trong mạng chủ yếu theo con

đường ngắn nhất. 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 [9, 13, 16].

Để tìm các cạnh trong mạng nối hai đỉnh thuộc hai cụm khác nhau, khái quát

đây là cạnh có độ trung gian cao, và xác định độ đo trung gian này bằng cách tính số

đường đi ngắn nhất giữa các cặp đỉnh mà có qua nó. Với một đồ thị m cạnh và n đỉnh

thì thời gian tính toán cho giai đoạn này là O(mn) .Với đồ thị có trọng số, độ đo trung

gian của cạnh có trọng số đơn giản được tính bằng độ đo trung gian của cạnh không

có trọng số chia cho trọng số của cạnh đó.

Nếu một mạng lưới bao gồm các cụm hoặc nhóm chúng chỉ được liên kết nối

yếu bằng một nhóm cạnh, thì tất cả các đường đi ngắn nhất giữa các cụm khác nhau

sẽ phải đi dọc theo một trong số ít các cạnh thuộc nhóm cạnh đó. Vì vậy, các cạnh

kết nối các cụm sẽ là cạnh có độ đô trung gian cao. Bằng cách loại bỏ các cạnh, thuật

toán Girvan-Newman tách được thành các nhóm riêng biệt. Thuật toán được thực

hiện theo các bước sau:

1. Tính độ đo trung gian cho tất cả các cạnh trong mạng.

2. Hủy bỏ các cạnh có độ trung gian cao nhất.

3. Tính lại độ trung gian cho tất cả các cạnh bị ảnh hưởng theo các cạnh đã

loại bỏ.

4. Lặp lại từ bước 2 cho đến khi không còn các cạnh trung gian.

Hình 2.5: Ví dụ phát hiện cụm sử dụng thuật toán Girvan - Newman [7].

Thuật toán Girvan-Newman khá đơn giản và dễ hiểu. Toàn bộ thuật toán có

thể được biểu diễn trong một dendrogram, ở đây ta có thể hiểu là thuật toán đi từ gốc

đến các lá. Các nhánh của cây biểu diễn cho các phép loại bỏ cạnh để chia đồ thị

thành các cụm riêng rẽ. Thuật toán Girvan-Newman đưa lại kết quả tương đối tốt

trong nhiều trường hợp, mặc dù vậy nó vẫn gặp phải một số nhược điểm:

1. Thuật toán Girvan-Newman sử dụng phương pháp loại trừ đến khi không

có cạnh nào vượt qua ngưỡng của độ trung gian cao nhất, vì vậy nên số lượng cụm

hoàn toàn không kiểm soát trước được. Bên cạnh đó, thuật toán sử dụng nhiều phép

phân vùng, khó có thể xác định được phép phân vùng nào mang lại hiệu quả tốt nhất.

2. Do tại mỗi lượt thực hiện, thuật toán tính lại độ trung gian của mỗi cạnh liên

quan sau khi xóa đi cạnh có độ trung gian lớn nhất nên độ phức tạp thời gian là khá

cao. Giả sử với đồ thị n đỉnh, số cạnh phải xóa đi khỏi đồ thị là m cạnh thì ta cần

lượng thời gian tính toán O(mn) cho mỗi lần lặp. Tổng thời gian chạy thuật toán

O(m2n). Trong trường hợp xấu nhất, mỗi đỉnh được chia ra thành một cụm riêng rẽ

thì độ phức tạp thời gian của thuật toán sẽ lên đến O(n3).

3. Trên thực tế, mỗi đơn vị nút mạng có thể thuộc vào rất nhiều cụm khác

nhau. Ví dụ với một cá nhân A, đóng góp vai trò là một nút trên mạng xã hội có thể

thuộc vào nhiều nhóm: Bạn cùng lớp, đồng nghiệp cùng công ty, anh em họ hàng

trong gia đình, … Nhưng với cách phân chia của Girvan-Newman không giải quyết

được hiện tượng chồng chéo cụm trên.

2.4. Thuật toán CNM (Clauset-Newman-Moore)

Thuật toán CNM được đề xuất bởi Clauset, Newman và Moore [5] là một

phương pháp phân cụm phân cấp tích tụ. Thuật toán này sử dụng độ đo đơn thể Q

được đề xuất bởi Girvan và Newman như đã giới thiệu ở chương 1 để làm độ đo cho

việc tối ưu hóa kết quả phân cụm.

Một giá trị cao của Q thể hiện phép phân cụm tốt cho đồ thị hiện tại, do đó

nhiệm vụ của CNM là đi tìm giá trị Q cao nhất trong tập ứng cử của nó. Việc tìm giá

trị Q cực đại toàn cục trên tập các phương án có thể là rất khó hay nói cách khác là

tốn rất nhiều thời gian (không khả thi với thời gian thực), do đó trong CNM, các tác

giả đề xuất kỹ thuật tối ưu hóa xấp xỉ hay còn gọi là phương pháp tối ưu tham lam.

Tương tự như thuật toán của Girvan-Newman, CNM cũng bắt đầu với việc

phân hoạch mỗi đỉnh vào một cụm đơn lẻ, sau đó sẽ lặp lại việc kết hợp hai cụm với

nhau sao cho phép hợp nhất này sẽ làm tăng Q lên một giá trị lớn nhất. Với mạng có

n đỉnh thì sau n-1 phép kết hợp như vậy sẽ phân hoạch toàn bộ các đỉnh vào trong

một cụm đơn và thuật toán kết thúc. Toàn bộ tiến trình này sẽ được tạo thành một cây

kết quả trong đó các lá của cây là các đỉnh của mạng gốc và các nút bên trong tương

ứng với phép kết hợp. Cây này biểu diễn dưới dạng cấu trúc "dendrogram" và nó thể

hiện việc phân cụm có thứ bậc mạng trên thành các cụm ở tất cả các mức khác nhau.

Cách thực thi trực tiếp của ý tưởng này mà Girvan-Newman áp dụng là lưu

ma trận kề của đồ thị như một mảng các số nguyên và lặp lại việc trộn các cặp hàng

- cột tương ứng với việc trộn các cụm với nhau. Đối với trường hợp đồ thị thưa, cách

thực hiện này gây lãng phí bộ nhớ và thời gian thực thi đối với các phần tử có giá trị

0 trong ma trận này, mà với đồ thị thưa số phần tử 0 rất nhiều. Bởi vậy, CNM đề xuất

thuật toán mới nhằm tăng tốc độ công việc trên bằng cách loại bỏ những phép toán

không cần thiết.

Trước tiên, CNM định nghĩa 2 đại lượng sau:

(2.10) 𝑒𝑖𝑗 = 1 2 ∑ 𝐴𝑣𝑤𝛿(𝑐𝑣, 𝑖)𝛿(𝑐𝑤, 𝑗) 𝑣𝑤

là số phép phân hoạch để kết hợp các đỉnh trong cụm i và đỉnh trong cụm j.

(2.11) 𝑎𝑖 = 1 2𝑚 ∑ 𝑘𝑣𝛿(𝑐𝑣, 𝑖) 𝑣

là phép phân hoạch các cạnh gắn các đỉnh trong cụm i.

𝑖

ta sẽ được (2.12).

𝑖

= ∑ [

−

]

1 2𝑚

∑ 𝐴𝑣𝑤𝛿(𝑐𝑣, 𝑖)𝛿(𝑐𝑤, 𝑖) 𝑣𝑤

∑ 𝑘𝑣𝛿(𝑐𝑣, 𝑖) 𝑣

∑ 𝑘𝑤𝛿(𝑐𝑤, 𝑖) 𝑤

𝑖

𝑄 = ] ∑ 𝛿(𝑐𝑣, 𝑖)𝛿(𝑐𝑤, 𝑖) Tiếp đến, ký hiệu 𝛿(𝑐𝑣, 𝑐𝑤) = ∑ 𝛿(𝑐𝑣, 𝑖)𝛿(𝑐𝑣, 𝑖) 𝑘𝑣𝑘𝑤 2𝑚 1 2𝑚 ∑ [𝐴𝑣𝑤 − 𝑣𝑤

2 = ∑(𝑒𝑖𝑖 − 𝑎𝑖

𝑖

) (2.12)

Công việc của thuật toán CNM liên quan đến việc tìm sự thay đổi của giá trị

Q được tạo ra do sự hợp nhất các cặp cụm và chọn giá trị lớn nhất trong số chúng. Ta

đặt ∆𝑄𝑖𝑗 là sự thay đổi của Q khi hợp nhất hai cụm i và j. Trên thực tế, việc tìm cặp

i, j cho ∆𝑄𝑖𝑗 lớn nhất tốn rất nhiều thời gian. Vì thế CNM thay bằng việc lưu trữ ma

trận kề của mạng và tính toán giá trị ∆𝑄𝑖𝑗, nó thay bằng việc lưu trữ và cập nhật một

ma trận các giá trị của ∆𝑄𝑖𝑗. Do việc kết hợp hai cụm mà không có cạnh nối chúng sẽ

không làm tăng Q nên CNM chỉ lưu các ∆𝑄𝑖𝑗 với các cặp i, j mà việc hợp nhất khi

chúng có một hay nhiều cạnh nối. Do ma trận này có cùng độ hỗ trợ như ma trận kề,

nó cũng sẽ thưa như ma trận kề gốc và có thể biểu diễn chúng với các cấu trúc dữ liệu

hữu hiệu. Tiếp nữa, CNM xây dựng một cấu trúc dữ liệu hữu hiệu khác để lưu trữ các

giá trị ∆𝑄𝑖𝑗 lớn nhất tại các bước. Hai sự cải tiến này sẽ giúp cho việc tiết kiệm về bộ

nhớ và thời gian thực thi của CNM.

CNM tổ chức 03 cấu trúc dữ liệu như sau:

1. Một ma trận thưa chứa các ∆𝑄𝑖𝑗 cho mỗi cặp cụm i, j với tối thiểu 1 cạnh

nối giữa chúng. CNM lưu trữ mỗi hàng của ma trận vừa giống cây nhị phân cân bằng

(các phần tử có thể tìm kiếm hay chèn mới với độ phức tạp O(logn)) và như cấu trúc

max-heap (phần tử lớn nhất có thể tìm được trong thời gian hằng số).

2. Một cấu trúc max-heap H lưu trữ phần tử lớn nhất của mỗi hàng trong ma

trận ∆𝑄𝑖𝑗 cùng với các nhãn i, j tương ứng với cặp cụm được hợp nhất.

3. Một mảng vector thông thường cho việc lưu trữ các phần tử ai. Như đã nói

ở trên, CNM bắt đầu với việc mỗi đỉnh sẽ nằm trong 1 cụm đơn lẻ, với trường hợp

này thì eij = 1/2m nếu i và j được kết nối và =0 trong trường hợp còn lại. ai = ki/2m.

Do đó, CNM sẽ khởi tạo ma trận ∆𝑄𝑖𝑗 như sau:

(2.13) ∆𝑄𝑖𝑗 = { 1/2𝑚 − 𝑘𝑖𝑘𝑗/(2𝑚)2 𝑛ế𝑢 𝑐ó 𝑐ạ𝑛ℎ 𝑛ố𝑖 𝑖, 𝑗 0 𝑛ế𝑢 𝑖 𝑘ℎô𝑛𝑔 𝑛ố𝑖 𝑣ớ𝑖 𝑗

Và

𝑣ớ𝑖 𝑚ọ𝑖 𝑖 𝑎𝑖 = (2.14) 𝑘𝑖 2𝑚

Các bước của thuật toán:

1. Tính toán các giá trị khởi tạo của ∆𝑄𝑖𝑗 và ai tương ứng với công thức (2.13),

(2.14) và tạo cấu trúc max-heap với các phần tử lớn nhất cho mỗi hàng của ma trận

∆𝑄.

2. Chọn giá trị ∆𝑄𝑖𝑗 lớn nhất trong cấu trúc max-heap H, hợp nhất hai cụm i, j

tương ứng, cập nhật ma trận ∆𝑄, heap H và ai, đồng thời tăng giá trị modularity Q lên

một lượng ∆𝑄𝑖𝑗.

3. Lặp lại bước 2 cho tới khi chỉ còn lại 1 cụm.

Cấu trúc dữ liệu mà CNM xây dựng giúp việc cập nhật các giá trị trong bước

2 rất nhanh chóng. Nếu hợp nhất hai cụm i, j và đánh lại nhãn là j cho cả hai cụm này,

CNM chỉ cần cập nhật hàng và cột thứ j, đồng thời xóa bỏ hàng và cột thứ i. Luật cập

nhật sẽ như sau:

Nếu cụm k đã từng kết nối với cả cụm i và j thì:

′ = ∆𝑄𝑖𝑘 + ∆𝑄𝑗𝑘

(2.15a) ∆𝑄𝑗𝑘

Nếu k chỉ kết nối với i mà không kết nối với j thì:

′ = ∆𝑄𝑖𝑘 − 2𝑎𝑗𝑎𝑘

(2.15b) ∆𝑄𝑗𝑘

Nếu k chỉ kết nối với j mà không nối với i thì:

′ = ∆𝑄𝑗𝑘 − 2𝑎𝑖𝑎𝑘

(2.15c) ∆𝑄𝑗𝑘

Với các sự điều chỉnh ở trên, thuật toán CNM có độ phức tạp về thời gian là

O(mdlogn) với một mạng n đỉnh, m cạnh và d là độ sâu của cây dendrogam, tức là

CNM có hiệu năng rất cao. Trong bài báo giới thiệu về CNM, các tác giả đã thực thi

thuật toán với một mạng gồm 400.000 đỉnh và 2 triệu cạnh với thời gian thực thi rất

nhanh.

2.5. Thuật toán Rosvall-Bergstrom

Để hiểu được cấu trúc của các mạng xã hội, mạng tin sinh cỡ lớn, sẽ rất thuận

tiện nếu phân tích chúng thành các đơn vị con hay các modul nhỏ hơn. Trong [14],

Rosvall - Bergstrom phát triển một nền tảng lý thuyết thông tin cho khái niệm về độ

đo modularity trong các mạng. Các tác giả xác định các modul trong mạng bằng cách

tìm một phép nén tối ưu cho topology của mạng đó dựa trên cấu trúc của nó. Hình

2.6 dưới đây minh họa một nền tảng cơ bản cho việc phân cụm (xác định các cộng

đồng) trong mạng. Chúng ta hình dung quá trình mô tả một mạng phức tạp bằng một

bản tóm tắt đơn giản về cấu trúc modul của nó như một quá trình truyền thông. Cấu

trúc liên kết của một mạng phức tạp là một biến ngẫu nhiên X, một tín hiệu biết được

dạng đầy đủ của mạng X và nhằm mục đích chuyển tải nhiều thông tin hơn tới bộ tiếp

nhận tín hiệu trong thời gian ngắn hơn. Để làm được điều này, tín hiệu mã hóa thông

tin về X như một mô tả đơn giản Y và gửi đi thông điệp đã được mã hóa này thông

qua một kênh truyền thông ít nhiễu. Bộ nhận tín hiệu quan sát thông điệp Y và sau

đó sẽ "giải mã" thông điệp này, sử dụng nó để tạo ra các dự đoán Z về cấu trúc của

mạng gốc X.

Hình 2.6: Khung làm việc cơ sở để phân cụm đồ thị như quá trình truyền thông

Có nhiều cách khác nhau để mô tả một mạng X bằng một mô tả đơn giản hơn

Y. Cách nào trong số này là tốt nhất? Câu trả lời cho câu hỏi này tất nhiên phụ thuộc

vào những gì ta muốn làm với mô tả. Tuy nhiên, lý thuyết thông tin cung cấp một câu

trả lời chung hấp dẫn cho câu hỏi này. Cho một số tập hợp các mô tả ứng viên Yi, mô

tả Y tốt nhất của một biến ngẫu nhiên X là một trong những mô tả nhiều thông tin

nhất về X, nghĩa là tối đa hóa thông tin chung I(X;Y) giữa mô tả và mạng.

Do chúng ta quan tâm đến việc xác định cấu trúc các cụm (cộng đồng), chúng

ta sẽ khám phá các mô tả Y tổng hợp cấu trúc của mạng X bằng cách liệt kê các cụm

hoặc các phân hệ trong X và mô tả các mối quan hệ giữa chúng. Trong [14], các tác

giả xem xét một phương pháp cụ thể để mã hóa cấu trúc các cụm của X. Để tổng quát

hơn, có thể và nên xem xét các bộ mã hóa khác, để lựa chọn một trong những giải

pháp phù hợp nhất cho bài toán.

Một cách trực tiếp để đặt tên cho các nút là sử dụng mã Huffman. Mã Huffman

tiết kiệm không gian bằng cách gán từ mã ngắn tới các sự kiện hoặc các đối tượng

phổ biến và các từ mã dài cho các đối tượng ít xuất hiện, giống như các ngôn ngữ trên

thực tế. Hình 2.7(a) chỉ ra một ví dụ về mã Huffman tiền tố tự do.

(a) Mã Huffman (b): Miêu tả 2 mức

Hình 2.7. Ví dụ về mã Huffman [14]

Mỗi từ mã xác định một nút và chiều dài của từ mã nhận được từ tần xuất ghé

thăm nút của một bước đi ngẫu nhiên hữu hạn. Với mã Huffman trong hình 2.7(a), ta

có thể miêu tả 71 bước đi ngẫu nhiên bằng 314 bit. Nếu chúng ta thay thế bằng việc

chọn một mã đồng nhất, trong đó tất cả các từ mã có cùng chiều dài, mỗi từ mã sẽ có

log25 = 5 bit chiều dài và 71x5 = 355 bit để miêu tả bước đi này.

Ta xét một mạng X là đồ thị vô hướng không có trọng số, với kích thước n

đỉnh, l liên kết, được biểu diễn bởi ma trận kề như (2.9).

𝑎1...

Ta lựa chọn miêu tả:

𝑎𝑛

𝑌 = {𝒂 = ( ) , 𝑴 = ( )} (2.16)

𝑙11 ⋯ 𝑙1𝑚 ⋮ ⋮ ⋱ 𝑙𝑚1 ⋯ 𝑙𝑚𝑚

với m modul, trong đó a là véc tơ chỉ định modul, ai∈{1, 2, ...,m}, và M là ma trận

modul. Ma trận modul M = M(X, a) miêu tả cách mà m modul được tạo bởi véc tơ

chỉ định modul được kết nối trong mạng thực. Modul i có ni node và kết nối với modul

j với lij liên kết (hình 2.6).

Để tìm được chỉ định modul tốt nhất a*, ta cần cực đại hóa thông tin chung

trên toàn bộ các chỉ định có thể của các nút trong m modul:

𝑎

𝑎∗ = arg max 𝐼(𝑋; 𝑌) (2.17)

Theo định nghĩa, thông tin chung I(X; Y) = H(X) - H(X|Y) = H(X) - H(Z),

trong đó H(X) là thông tin cần thiết để miêu tả X, và thông tin điều kiện H(X|Y) =

H(Z) là thông tin cần thiết để miêu tả X theo Y. Do đó, ta sẽ chuyển bài toán (2.2)

sang việc cực tiểu hóa H(Z). Điều này tương đương với việc cấu trúc một véc tơ chỉ

định sao cho Z là nhỏ nhất có thể.

𝑖>𝑗

𝑚 𝑖=1

𝑛𝑖(𝑛𝑖−1) 2 𝑙𝑖𝑖

) ) 𝐻(𝑍) = 𝑙𝑜𝑔 [∏ ( ] (2.18) ∏ (𝑛𝑖𝑛𝑗 𝑙𝑖𝑗

Trong đó, các đấu ngoặc đơn biểu thị các tổ hợp chập và logarit tính ở cơ số

2. Mỗi tổ hợp chập trong m tích đầu tiên cho biết số lượng các modul khác nhau có

thể được xây dựng với các nút ni và liên kết lii. Mỗi tổ hợp chập trong m(m-1)/2 tích

thứ 2 cho biết số cách khác nhau mà modul i và j có thể được kết nối với nhau.

Tiếp theo, các tác giả đi giải quyết các thách thức trong việc lựa chọn một mô

hình. Trong một số trường hợp đặc biệt, chúng ta sẽ biết được có bao nhiêu modul

tạo thành mạng mẫu, nhưng nói chung, việc xác định các cụm là mô hình hai bước.

Đầu tiên ta cần phải xác định số lượng modul trong mạng, và sau đó chúng ta cần

phải phân hoạch các nút vào trong các modul đó. Cả hai việc này đều phải thực hiện

đồng thời. Các tác giả đưa ra một giải pháp dựa trên thuật toán lý thuyết thông tin.

Xem lại hình 2.6, bộ mã hóa tìm kiếm một kết quả nén của mạng để bộ giải

mã có thể tạo ra ước lượng tốt nhất cho mạng thực tế. Một cách tiếp cận đó là phân

vùng mã hóa mạng thành các mudul, mỗi modul cho một nút. Điều này đảm bảo rằng

bộ giải mã có thể tái tạo lại mạng một cách đầy đủ, nhưng theo tiếp cận này thì không

đạt được lợi ích gì trong việc nén thông tin hay xác định modul. Do đó, bộ mã hóa

phải cân bằng lượng thông tin cần thiết để mô tả mạng ở dạng modul, như được cho

bởi tín hiệu Y trong hình 2.6. Đây là một bài toán mã hóa tối ưu và có thể giải quyết

theo nguyên tắc độ dài mô tả tối thiểu (MDL). Ý tưởng là để khai thác tính chính xác

trong cấu trúc của mạng X thực tế để tóm tắt nó ở dạng cô đặc, mà không cần

"overfitting" nó.

Hình 2.8: Phân hoạch vào một lượng tối ưu các modul. (A): mạng được cấu thành

bởi 40 tạp chí như các nút từ 4 lĩnh vực khác nhau (vật lý, hóa học, sinh học và kinh

tế). 189 liên kết kết nối các nút nếu tối thiểu có một bài báo từ tạp chí này trích dẫn

một bài báo từ tạp chí khác. (B): độ dài mô tả tối thiểu cho mạng A đã được phân

hoạch vào từ 1 đến 5 modul khác nhau.

Để giảm thiểu độ dài mô tả của mạng X ban đầu, tác giả tìm kiếm số modul

giảm thiểu độ dài của mô tả modul cộng với độ dài mô tả điều kiện, trong đó độ dài

mô tả có điều kiện là số lượng thông tin bổ sung có thể cần phải xác định chính xác

X đến người nhận đã giải mã mô tả Y. Tức là, tìm cách cực tiểu hóa tổng:

L(Y) + L(X|Y) (2.19)

trong đó L(Y) là chiều dài tính theo bit của tín hiệu, và L(X|Y) là số lượng bit cần

thiết để xác định mạng bởi tín hiệu Y một cách đáng tin cậy. Chiều dài mô tả dễ dàng

tính toán trong trường hợp rời rạc như sau:

L(Y) + L(X|Y) = 𝑛𝑙𝑜𝑔𝑚 + 𝑚(𝑚 + 1)𝑙𝑜𝑔𝑙 + 𝐻(𝑍) (2.20)

trong đó số hạng thứ nhất và thứ hai đưa ra kích thước cần thiết để mã hóa véc tơ

chuyển đổi a và ma trận modul M(X, a), và H(Z) được xác định theo công thức (2.18).

Trong hình 2.8 B chỉ ra chiều dài mô tả với mạng tạp chí được phân hoạch vào từ 1

tới 5 modul. Với phân hoạch 4 modul cho ta chiều dài mô tả tối thiểu, và tương ứng

với phân hoạch chỉ ra trong hình 2.8 A.

Vậy có thể tóm tắt các bước của thuật toán như sau:

𝑎1...

Bước 1: Với mạng đầu vào X biểu diễn bởi ma trận kề, có l liên kết, ta lựa

𝑎𝑛

)}. chọn một miêu tả: 𝑌 = {𝒂 = ( ) , 𝑴 = (

𝑙11 ⋯ 𝑙1𝑚 ⋮ ⋮ ⋱ 𝑙𝑚1 ⋯ 𝑙𝑚𝑚

𝑚

Bước 2: Tính toán thông tin cần thiết để miêu tả X theo Y:

𝑖=1

𝑖>𝑗

) ∏ ( ) ] 𝐻(𝑍) = 𝑙𝑜𝑔 [∏ ( 𝑛𝑖𝑛𝑗 𝑙𝑖𝑗 𝑛𝑖(𝑛𝑖 − 1) 2 𝑙𝑖𝑖

Bước 3: Tính chiều dài mô tả X:

L(Y) + L(X|Y) = 𝑛𝑙𝑜𝑔𝑚 + 𝑚(𝑚 + 1)𝑙𝑜𝑔𝑙 + 𝐻(𝑍)

Bước 4: Lặp lại từ bước 1 đến 3 cho đến khi nào L(Y) + L(X|Y) không thể

giảm thêm được nữa (L(Y) + L(X|Y) là cực tiểu).

Kết quả: ta thu được số cụm là số modul m, xác định mỗi nút thuộc vào cụm

nào thông qua véc tơ chỉ định modul a, chất lượng phân cụm là chiều dài tối thiểu

của từ mã biểu diễn X.

2.6. Thuật toán INC (Incre-Comm-Extraction).

Theo nhiều phân tích trực quan trên các cụm của các mạng xã hội dựa trên mối

quan tâm của người dùng, các nhà nghiên cứu nhận thấy hầu như các cụm thường có

kích thước nhỏ ngay cả với các mạng lớn như Facebook, Twitter... Cũng có trường

hợp mật độ các cạnh giữa các cụm khá lớn dẫn tới việc các thuật toán sẽ coi các cụm

này chỉ là một cụm lớn. Để tìm được các cụm phân biệt này, chúng ta cần phải tìm

kiếm trong cụm lớn đó. Ví dụ, khi tìm kiếm trong một cụm lớn sử dụng thuật toán

CNM đối với tập dữ liệu Facebook, chúng ta có thể tìm ra nhiều cụm nhỏ hơn liên

quan tới thể thao, chính trị, tin tức...

Thuật toán cải tiến được đề xuất để phân chia các cụm lớn thành nhiều cụm

con với sự quan tâm giống nhau hơn. Thuật toán chỉ xét các đồ thị con chứa các đỉnh

nằm trong một cụm lớn chứ không xét mối quan hệ với cụm lớn khác, do công việc

này đã xét ở bước phân cụm với CNM. Do thuật toán sẽ làm gia tăng việc trích xuất

ra nhiều cụm có ý nghĩa ở mỗi vòng lặp nên ta ký hiệu thuật toán là INC (INCRE-

COMM-EXTRACTION) [30].

2.6.1. Nội dung thuật toán

Thuật toán được xây dựng dưới dạng đệ quy. Ở đầu mỗi vòng lặp, thuật toán

sẽ gọi thủ tục phân cụm theo thuật toán CNM và với mỗi cụm kết quả do CNM tìm

ra, thuật toán INC sẽ xác định xem cụm này là cụm cuối cùng (không phân chia thêm

được nữa) hay là gọi lại thủ tục đệ quy cho cụm đó để phân chia tiếp cụm lớn này.

Theo cách này, chúng ta có thể chia nhỏ cụm với thuật toán CNM chừng nào có thể.

Khi thuật toán CNM không thể chia nhỏ được cụm này nữa thì thuật toán INC sẽ xác

định đồ thị đầu vào này là cụm kết quả. Chúng ta cũng có thể dừng việc phân chia

cụm khi kích thước cụm đạt tới giá trị cận trên s (s: tham số đâu vào thể hiện kích

thước cận trên của một cụm). Đây là một đặc trưng thêm vào của thuật toán để những

người dùng không muốn các cụm tìm được quá nhỏ. Điều này không đồng nghĩa với

việc tất cả các cụm tìm được đều phải có kích thước tối đa là s, vì có những cụm có

kích thước lớn hơn s nhưng thuật toán CNM không thể phân chia được nữa do tính

kết nối cao của các cụm thành viên. Trong luận văn, sử dụng CNM làm thuật toán

nền cho INC vì CNM cho hiệu năng tốt nhất tính đến thời điểm hiện tại. Chúng ta

cũng có thể sử dụng các thuật toán khác như Girvan-Newman, CONGA... thay cho

CNM.

Thuật toán INC như sau:

Đầu vào: Đồ thị G =(V, E), tham số s: cận trên kích thước của cộng đồng

kết quả.

Đầu ra: Tập các cụm C = {c1, c2, ..., ck}, với |C| = k: số cộng đồng tìm được

và ci, i =1...k là các cụm tìm được.

function INC (Gr, s) // Thủ tục đệ quy của thuật toán

1. C' ← CNM(G); // Phân cụm với thuật toán CNM

2. If |C'| = 1 then

3. Đặt c1 là cụm duy nhất trong C';

4. C ← C ∪ c1; // Thêm cụm c1 vào tập kết quả

return; // Thoát khỏi thủ tục đệ quy 5.

6. c' ← ∅;

7. for each cụm ci ∈ C' do

8. if |ci| = 1 then

9. c' ← c' ∪ ci; // đưa ci vào cụm chứa cụm đơn

10. else if |ci| ≤ s then

11. C ← C ∪ ci; // Thêm cụm ci vào tập kết quả

12. else

13. Gi ← G(V(ci), E(ci)); // Xây dựng đồ thị mới từ ci

14. INC(Gi, s); // Gọi đệ quy thuật toán

15. if |c'| ≠ 0 then

C ← C ∪ c';

Giải thích thuật toán:

Thuật toán bắt đầu với đồ thị đầu vào G và khởi tạo tập cụm kết quả C = ∅. Ở

mỗi vòng lặp đệ quy của thuật toán, đồ thị đầu vào được ký hiệu là Gr. Thuật toán gọi

thủ tục tìm cụm cho đồ thị Gr với thuật toán CNM - CNM(Gr) và nhận được tập cụm

kết quả C'. Nếu C' chỉ chứa một cụm tức là CNM không thể phân chia đồ thị Gr thành

các cụm con được nữa. Gọi c1 là cụm duy nhất đó ở trong C', khi đó c1 sẽ chứa toàn

bộ các đỉnh của Gr. Khi đó c1 là một cụm kết quả và ta thêm c1 vào tập cụm kết quả

C, kết thúc vòng lặp hiện tại.

Nếu C' nhiều hơn một cụm, thuật toán sẽ duyệt qua tất cả các cụm ci nằm trong

C' và kiểm tra xem một trong ba điều kiện sau đây có thỏa mãn hay không:

1. Nếu ci chỉ chứa một đỉnh, khi đó không thể nói ci là một cụm, vì cụm mà

chỉ có một cá thể thì không hợp lý. Do đó, thuật toán sẽ thêm đỉnh ci này vào c' (với

c' được sử dụng để lập thành một cụm chứa tất cả các đỉnh đơn như ci). Ban đầu c'

được khởi tạo rỗng. Khi duyệt qua toàn bộ các cụm trong C', c' sẽ chứa toàn bộ các

đỉnh đơn và sẽ đưa c' vào tập cụm kết quả C khi c' chứa tối thiểu một đỉnh. Theo cách

này, tất cả các cụm đơn ở mỗi vòng lặp đệ quy sẽ được đưa vào một cụm chung (chưa

xác định tính chất).

2. Khi người dùng đưa vào tham số s, thuật toán kiểm tra xem kích thước cụm

ci có nhỏ hơn hoặc bằng s hay không. Nếu thỏa mãn thì thêm ci vào tập cụm kết quả

C và tiếp tục với các cụm khác trong C'. Nếu không thì chuyển sang kiểm tra điều

kiện 3.

3. Nếu điều kiện 1 và 2 ở trên không thỏa mãn thì ở điều kiện 3 này, chúng ta

có thể phân chia tiếp đồ thị Gi thành các cụm con, trong đó Gi được tạo từ các đỉnh

của cụm ci này, V(ci) và tập các cạnh của ci, E(ci). Khi đó chúng ta gọi thủ tục đệ quy

của thuật toán cho đồ thị đầu vào Gi vừa xây dựng từ ci.

Kết thúc thuật toán, chúng ta sẽ nhận được tập các cụm kết quả C. Luồng thực

hiện thuật toán được biểu diễn dưới dạng một biểu đồ dendrogram, trong đó mỗi nút

bên trong biểu diễn một đồ thị con Gr ở mỗi bước đệ quy và mỗi nút lá chính là các

cụm ci.

2.6.2. Độ phức tạp của thuật toán

Ta tiến hành phân tích độ phức tạp của thuật toán INC. Theo các nghiên cứu

đã trình bày ở chương 2, thuật toán CNM có độ phức tạp là O(mdlogn) cho một đồ

thị tổng quát (m là số cạnh, n là số đỉnh và d là độ sâu của dendrogram). Với các đồ

thị thưa, thời gian thực thi là O(nlog2n). Ta đặt độ phức tạp của thuật toán INC là

T(n).

Trong trường hợp xấu nhất, các cụm được tìm thấy ở mỗi vòng đệ quy có thể

không cân bằng. Với các đồ thị thưa, thời gian thực thi CNM là nlog2n, ta có công

thức quy nạp cho T(n) như sau:

T(n) = nlog2n + T(n-1) = nlog2n + nlog2n + T(n-2) = ...= n2log2n + T(1).

Do đó, độ phức tạp của thuật toán INC là O(n2log2n) trong trường hợp đồ thị

thưa. Tương tự như vậy cho trường hợp tổng quát, độ phức tạp của INC sẽ là T(n) =

O(mndlogn), khi ta sử dụng CNM làm thuật toán nền ở mỗi vòng đệ quy. Trong

trường hợp xấu nhất, thủ tục đệ quy INC sẽ gọi CNM n lần. Tuy nhiên qua thực

nghiệm chỉ ra rằng con số này nhỏ hơn rất nhiều so với n, do đó thuật toán chạy rất

nhanh.

Trong trường hợp các cụm khá cân bằng (đa số các trường hợp), tức là tối đa

p cụm được tìm thấy bởi thuật toán ở mỗi vòng đệ quy và mỗi cụm này có n/p thành

viên. Khi đó, với đồ thị thưa, thuật toán có độ phức tạp (logn/logp) * n * log2n với đồ

thị thưa. Với p ≥2 thì ta có T(n) = O(nlog3n).

2.6.3. Độ đo chất lượng phân cụm của thuật toán

Như đã trình bày ở trên, độ đo mođun hóa Q nhiều khi không phản ánh đúng

cấu trúc cụm, do đó trong luận văn này sử dụng độ đo tính mật độ được giới thiệu

trong Zhang et al (2009) [25] để tiến hành đánh giá chất lượng phân cụm trong thực

nghiệm ở 3.4.5.

Với một đồ thị con Gi(Vi, Ei), đặt li và lo là số cạnh bên trong và bên ngoài của

Gi. Cạnh bên trong là cạnh có hai đỉnh đều nằm trong đồ thị Gi. Cạnh bên ngoài là

cạnh có một đỉnh nằm trong và một đỉnh nằm ngoài Gi. Giả sử ni = |Vi|, bậc trung

bình bên trong của đồ thị Gi là 2li/ni và bậc trung bình bên ngoài của Gi là lo/ni. Khi

đó, độ đo mô đun hóa mật độ D của phép phân chia đồ thị G thành tập cụm C = {c1,

c2, ..., ck} được tính bằng tổng bậc trung bình bên trong trừ đi bậc trung bình bên

ngoài:

|𝐶|

𝑖=1

(2.21) 𝐷 = ∑ 2𝑙𝑖 − 𝑙𝑜 𝑛𝑖

2.7. Kết luận chương 2

Trong chương 2 này đã trình bày một số thuật toán phân cụm có thứ bậc được

sử dụng phổ biến cho bài toán phân cụm đồ thị dữ liệu, bao gồm các thuật toán

Chameleon, CURE, SoT, Girvan-Newman, CNM, Rosvall-Bergstrom và INC. Mỗi

thuật toán có những ưu và nhược điểm riêng đã được đánh giá chi tiết. Những đánh

giá sơ bộ trên cũng là cơ sở để lựa chọn một số thuật toán này để tiến hành cài đặt và

thực nghiệm trong chương 3 của luận văn trên các bộ dữ liệu chuẩn, qua đó một lần

nữa đánh giá lại được một cách chính xác các thuật toán trên và khả năng ứng dụng

của các thuật toán trong việc giải quyết các bài toán thực tế.

CHƯƠNG 3: ỨNG DỤNG THUẬT TOÁN PHÂN CỤM CÓ THỨ BẬC

TRONG PHÂN CỤM ĐỒ THỊ DỮ LIỆU CÁC MẠNG XÃ HỘI

3.1. Bài toán phân cụm mạng xã hội

Bài toán: Phân cụm các nút dữ liệu trong đồ thị mạng xã hội và đưa ra danh

sách những nút mạng thuộc từng cụm đó.

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

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

Output: Tập các cụm C = {C1, C2, ...,Cm} và tập hợp các đỉnh thuộc cụm đó:

Ci = {vi1, vi2, ..., vik} với i =1, 2, ...,m.

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ụm nằm trong phù hợp với nhu cầu của ngươi sử dụng và tìm hiểu về mối liên

hệ bên trong các cụm cũng như giữa các cụm 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.

Việc phân cụm có rất nhiều ứng dụng cụ thể:

 Phân cụm các Web client có sở thích tương tự nhau và gần nhau về mặt địa lý có

thể cải thiện hiệu suất của việc cung cấp dịch vụ trên World Wide Web, trong đó mỗi

cụm khách hàng được phục vụ bởi một server chuyên dụng.

 Xác định các cụm khách hàng có chung sở thích trong một mạng thể hiện quan

hệ giữa người mua và sản phẩm trên một trang web bán hàng trực tuyến có thể giúp

xây dựng hệ thống tư vấn mua bán một cách hiệu quả.

 Nhóm thành cụm các nút trong mạng lưới giao thông có thể giúp ích trong việc

xây dựng các bảng định tuyến nhỏ gọn giúp ích trong việc tham gia giao thông thuận

tiện.

Tóm lại, cụm 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ân cụm trong mạng xã hội vì các lý do

đã được nêu ở trên.

Hệ thống được thiết kế gồm 3 giai đoạn:

3.2. Xây dựng chương trình ứng dụng phân cụm đồ thị các mạng xã hội

Thu thập dữ liệu

Xử lý dữ liệu

Phân cụm đồ thị

Hình 3.1: Các bước thực hiện chương trình

3.2.1. Giai đoạn 1: Thu thập dữ liệu

Để tiến hành thực nghiệm, em đã thu thập 05 bộ dữ liệu được công bố phổ biến trên

[16], [21], [30], đây là các bộ dữ liệu chuẩn, chuyên sử dụng cho việc đánh giá, thực

nghiệm các thuật toán phân cụm, phân cụm trong các mạng xã hội:

1. Zachary's karate club: Đồ thị vô hướng gồm 34 đỉnh, 78 cạnh, thể hiện mối

quan hệ bạn bè giữa các thành viên của một câu lạc bộ karate tại một trường

đại học tại Mỹ những năm 1970.

2. Dolphin social network: đồ thị vô hướng gồm 62 đỉnh, 159 cạnh, thể hiện mối

quan hệ giữa các con cá heo sống tại vùng Doubtful Sound, New Zealand.

3. Word adjacencies: Đồ thị vô hướng gồm 112 đỉnh, 425 cạnh, thể hiện mối liên

hệ của các tính từ phổ biến và danh từ trong tiểu thuyết David Copperfield của

Charles Dickens.

4. Neural network: Đồ thị vô hướng gồm 297 đỉnh, 2148 cạnh, thể hiện mạng

lưới trọng số, đại diện cho mạng nơ-ron của C. elegans.

5. Coauthorships in network science: Đồ thị vô hướng gồm 1461 đỉnh, 2742

cạnh, thể hiện mạng lưới đồng tác giả của các nhà khoa học làm việc về lý

Tất cả ban đầu có kiểu file *.gml.

thuyết mạng và thử nghiệm, do M. Newman biên soạn vào tháng 5 năm 2006.

3.2.2. Giai đoạn 2: Xử lý dữ liệu

Các tập dữ liệu thu thập được cần phải qua giai đoạn xử lý và làm sạch để phù

hợp với việc tổ chức cấu trúc dữ liệu cho bài toán được cài đặt trong giai đoạn 3.

Tập dữ liệu ban đầu có dạng *.gml.

Sử dụng phần mềm để chuyển tập dữ liệu này sang file văn bản .txt. Phải làm

sạch bằng cách loại bỏ bớt các cột dư thừa và thu được file .txt.

Ví dụ: Tập dữ liệu Dolphins.gml: được thực hiện trích lọc và làm sạch dữ

liệu lại thành tệp Dolphins.txt như sau:

Hình 3.2: Ví dụ tập dữ liệu dolphins.gml

Tập dữ liệu Dolphins.xls bao gồm 62 đỉnh (nodes) và 318 cạnh (links)

Hình 3.3: Tập dữ liệu dolphins.txt

Định dạng file dữ liệu: danh sách các cạnh của đồ thị, gồm ký hiệu của 2 đỉnh tạo nên

cạnh đó.

3.2.3. Giai đoạn 3: Xây dựng ứng dụng phân cụm có thứ bậc đồ thị các mạng

xã hội

Dựa trên các nghiên cứu ở các chương trước, em tiến hành cài đặt ứng dụng

để đánh giá kết quả đạt được trên bộ dữ liệu thực nghiệm với ba thuật toán đã nghiên

cứu là Girvan-Newman, CNM (Clauset-Newman-Moore) và Rosvall-Bergstrom. Sở

dĩ em chỉ cài đặt ba thuật toán trên bởi các thuật toán còn lại không thực sự phù hợp

cho phân cụm đồ thị mạng xã hội (biểu diễn sự liên quan giữa các phần tử trong mạng

xã hội thông qua các mối liên kết - cạnh nối) vì các thuật toán đó thường sử dụng để

phân cụm các đồ thị có dữ liệu biểu diễn dưới dạng các điểm dữ liệu (tọa độ trong

không gian n chiều).

Các chức năng chính của ứng dụng demo như sau:

- Cho phép người dùng nạp vào file đầu vào. File đầu vào có định dạng là danh

sách các cạnh của đồ thị cần phâm cụm:

Hình 3.4: Nạp file dữ liệu đầu vào

- Phân cụm phân hoạch đồ thị dữ liệu đầu vào theo các thuật toán được lựa

chọn (kết quả cho ra số cộng đồng, độ đo chất lượng phân cụm Modularity, thời gian

thực thi thuật toán và chi tiết danh sách các đỉnh nào thuộc cộng đồng nào):

Hình 3.5: Kết quả chạy thuật toán phân cụm CNM cho bộ dữ liệu dolphins.txt

Hình 3.6: Kết quả chạy thuật toán Girvan-Newman cho bộ dữ liệu dolphins.txt

3.3. Các kết quả thực nghiệm và đánh giá

Để đánh giá kết quả của các thuật toán đã nghiên cứu, em tiến hành thực nghiệm

trên 05 bộ dữ liệu đã giới thiệu ở 3.2.1.

Cấu hình máy tính sử dụng để tiến hành thực nghiệm như sau:

- Hệ điều hành: Windows 8.1 64bit

- Processor: Intel(R) Celeron(R) CPU G1840 @2.80GHz

- RAM: 8GB.

- Ngôn ngữ lập trình sử dụng để thực nghiệm: Visual C++ trong bộ Visual

Studio 2012

Kết quả thực thi thuật toán sau khi chạy demo được cho bởi bảng 3.1 dưới đây:

Số cụm

Chất lượng phân cụm (Modularity)

STT

Bộ dữ liệu

CNM

Thời gian thực thi (giây) GN

CNM

Karate

0.374

0.392

21.85

0.02

0.5

0.13

Dolphins

0.512

0.517

39.3

0.01

2.66

0.55

3 Word adjacencies

0.295

0.073

175.513

0.11

43.25 1.37

Neural network

0.372

0.28

204.570

2409

102

0.3

276

277

402

0.96

0.956

699.82

4742

0.2

Coauthorships in network science

Bảng 3.1: Kết quả thực thi các thuật toán

Trong đó: CNM: thuật toán Clauset - Newman - Moore; GN: thuật toán Girvan-

Newman; RB: thuật toán Rosvall-Bergstrom.

5000

4500

Clauset- Newman- Moore

4000

3.3.1. Thời gian thực thi thuật toán

) y â i g ( i

3500

3000

2500

Girvan- Newman

2000

1500

1000

h t c ự h t n a i g i ờ h T

500

Rosvall- Bergstrom

Bộ dữ liệu

Hình 3.7: Biểu đồ so sánh thời gian thực thi thuật toán

3.3.2. Số cụm được phân chia

i

Clauset- Newman- Moore

) y â i g (

Girvan- Newman

h t c ự h t n a i g i ờ h T

Rosvall- Bergstrom

450 400 350 300 250 200 150 100 50 0

Bộ dữ liệu

Hình 3.8: Biểu đồ so sánh số lượng cụm

3.3.3. Chất lượng phân cụm

Do độ đo chất lượng phân cụm của thuật toán Rosvall-Bergstrom là chiều dài

trung bình của mã miêu tả, khác với độ đo chất lượng modularity của hai thuật toán

CNM và Girvan-Newman nên hình bên dưới em chỉ so sánh hai thuật toán sau:

i

Clauset- Newman- Moore

) y â i g (

Girvan- Newman

1.2 1 0.8 0.6 0.4 0.2 0

h t c ự h t n a i g i ờ h T

Bộ dữ liệu

Hình 3.9: Biểu đồ so sánh chất lượng phân cụm

3.4. Phân cụm đồ thị mạng xã hội dựa trên mối quan tâm của người dùng

3.4.1. Giới thiệu

Tại Việt Nam, trang mạng xã hội Facebook được sử dụng rộng rãi nhất. Thông

qua trang mạng xã hội này, một lượng rất lớn các nội dung đã được người dùng tạo

ra và trao đổi hàng ngày. Trước đây đã có một số công trình nghiên cứu liên quan đến

việc phân cụm trong mạng xã hội Facebook dựa trên các mối quan hệ bạn bè (friend)

và theo dõi (follow). Tuy nhiên, việc thiết lập một mạng xã hội dựa trên mối quan hệ

bạn bè hay theo dõi như vậy mang tính động không cao do số lượng bạn bè cũng như

số người theo dõi trang facebook của một người thường khá ít biến động. Ngoài ra,

với nhiều trang được thiết lập dưới dạng các nhóm, fanpage ... thì lại không quan tâm

tới các mối quan hệ bạn bè. Các người dùng facebook có thể tự do bày tỏ quan điểm

của mình trên tường (wall) của các trang facebook đó bằng cách bình luận

(comments), thích (likes) hay viết hoặc chia sẻ lên tường facebook đó (post, share).

Các hành động đó được gọi là mối quan tâm của người dùng.

Theo thống kê trên internet, trung bình một người dùng Facebook viết 25 bình

luận và bấm nút thích 9 lần trong một tháng. Chính những hành động thể hiện mối

quan tâm của người dùng sẽ tạo ra các kết nối mạng mà ở đó, số người cùng quan

tâm (cùng comments, like, share, post) sẽ xác định độ mạnh của các kết nối này. Sử

dụng mô hình dựa trên mối quan tâm của người dùng sẽ tạo ra các mạng với mức độ

động cao vì gần như các hoạt động này diễn ra hàng ngày trên Facebook.

Theo một số báo cáo, các trang mạng xã hội có ảnh hưởng tới người tiêu dùng

còn lớn hơn cả truyền hình và báo chí. Thêm nữa, các mạng xã hội được xây dựng

giữa những người có sở thích tương tự nhau hoặc ngang hàng nhau. Bởi vậy, một

trong những ứng dụng của việc phân cụm trong mạng xã hội dựa trên mối quan tâm

của người dùng đó là trong lĩnh vực kinh doanh, tiếp thị, nó giúp cho các nhân viên

tiếp thị tiếp cận đến đúng các đối tượng khách hàng cần quan tâm.

Theo nội dung nghiên cứu ở chương 2, có nhiều thuật toán được sử dụng cho

việc phân cụm trong mạng xã hội, tiêu biểu có thuật toán CNM. Tuy nhiên, việc cực

đại hóa giá trị mô đun hóa Q chưa hẳn đã phản ánh đúng việc một mạng có cấu trúc

cụm. Trên thực tế, điều này chỉ đúng khi các cụm là các clique (giữa các đỉnh trong

cụm đều phải có cạnh nối). Để nhận được giá trị Q cực đại, các thuật toán này kết

thúc thường sinh ra nhiều cụm với kích thước rất lớn và chỉ một số cụm nhỏ.

Bởi vậy, cần đề xuất một cách tiếp cận lặp để trích xuất ra các cụm cần quan

tâm. Trong cách tiếp cận này, thuật toán bắt đầu với toàn bộ mạng lớn và cho ra một

số cụm con ở mỗi vòng lặp. Sau đó, ta sẽ loại bỏ các cụm này ra khỏi mạng và thực

hiện thuật toán đệ quy cho các cụm lớn. Thuật toán thực hiện cho tới khi nào không

thể chia nhỏ các cụm được nữa hoặc khi kích thước các cụm này thỏa mãn kích thước

cận trên mong muốn của người dùng. Kỹ thuật này sẽ được tác giả áp dụng cho bộ

dữ liệu thực tế được thu thập trên mạng xã hội Facebook.

3.4.2. Mô hình hóa dữ liệu

Để xây dựng mạng xã hội dựa trên mối quan tâm của người dùng, ta tiến hành

thu thập dữ liệu từ mạng xã hội Facebook. Các tường Facebook là phương tiện để các

cá nhân, các nhóm hay các tổ chức, công ty đưa các nội dung như các thông điệp, các

chiến dịch hoặc các quảng cáo, xúc tiến thương mại,... Các trang này được cung cấp

để các người dùng khác tương tác và giao dịch bằng cách cho phép họ phản hồi hoặc

bình luận trên các nội dung đã được đưa lên. Để thu được mối quan tâm của người

dùng trên Facebook, em xem xét các bình luận của người dùng trên các nội dung

được đăng lên các tường Facebook và sử dụng chúng để xây dựng mạng xã hội sẽ

dùng cho việc thực nghiệm ở mục 3.4.5. Trong hình 3.10 là một ví dụ về một nội

dung được đăng bởi "Vinamilk - Bí quyết ngon khỏe từ thiên nhiên" trên tường

Facebook của công ty này và các bình luận được tạo ra bởi các người dùng quan tâm.

Các bình luận và thông tin của người dùng (tên, facebook id...) tham gia bình luận

trên tường của một Facebook cụ thể là công khai và có thể thu thập sử dụng Facebook

API. Chi tiết cách thu thập dữ liệu được trình bày trong phần sau của luận văn.

Hình 3.10: Đăng tin và bình luận trên Facebook

Để xây dựng mạng xã hội dựa trên mối quan tâm của người dùng, ta thực hiện

như sau:

- Từ dữ liệu thu thập được liên quan đến các bình luận của người dùng, tiến

hành tách ra các người dùng phân biệt đơn nhất bằng cách trích rút theo tên và ID

facebook của người dùng đó.

- Xác định các người dùng chung giữa hai tường Facebook bất kỳ là người có

tham gia bình luận trên cả hai tường Facebook đó.

- Biểu diễn dữ liệu dưới dạng ma trận vuông đối xứng M, kích thước bằng với

số lượng các tường Facebook cần xét. Mỗi đường chéo của M là các phần tử M[i,i]

biểu diễn số lượng các người dùng đơn nhất bình luận trên tường i và các phần tử

M[i,j] với i khác j biểu diễn số người dùng bình luận chung trên hai tường i và j. Nếu

giá trị M[i,i] lớn thể hiện số lượng người tham gia bình luận trên tường i rất đông đảo.

Giá trị M[i,j] lớn thể hiện nhiều người dùng quan tâm tới cả hai tường i và j. Ở đây

ta cần phân biệt rõ: người dùng không phải là tường mà chỉ là người tham gia bình

luận các tin, bài viết đăng trên tường đó.

- Tiến hành chuyển đổi dữ liệu này sang dạng đồ thị vô hướng G = (V, E),

trong đó V biểu diễn các tường Facebook và E biểu diễn các cạnh nối giữa hai tường

Facebook. Giữa hai tường Facebook có cạnh nối khi chúng có số người quan tâm

chung lớn hơn 0. Do chúng ta cần tìm ra các cụm có cùng mối quan tâm nên các cạnh

này sẽ được đánh trọng số để chỉ độ mạnh của kết nối. Trọng số giữa hai đỉnh i và j,

được ký hiệu là w[i,j] và được tính theo chỉ số Jaccard như phương trình dưới đây:

(3.5) 𝑤[𝑖, 𝑗] = 𝑀[𝑖, 𝑗] 𝑀[𝑖, 𝑖] + 𝑀[𝑗, 𝑗] − 𝑀[𝑖, 𝑗]

Trong đó: M[i,j] là số người dùng cùng quan tâm tới tường i và j, M[i,i] là số

người dùng đơn nhất tham gia bình luận tường i, M[j,j] là số người dùng đơn nhất

tham gia bình luận tường j. Giá trị trọng số w[i,j] nằm trong khoảng 0 và 1, trong đó

w[i,j] càng gần với 1 càng chứng tỏ hai tường này càng tương tự nhau tính theo mối

quan tâm của người dùng.

3.4.3. Xây dựng dữ liệu

Để tiến hành thực nghiệm, ta đã thu thập dữ liệu từ 1500 tài khoản (tường)

Facebook khác nhau, chủ yếu là Facebook của các nhóm, các fanpage và các

Facebook thiết lập ở chế độ công cộng của các công ty, tổ chức, tập đoàn ... Các tài

khoản này được thu thập theo cách thủ công (bao gồm tên và facebook id). Cơ sở dữ

liệu sử dụng để lưu trữ tập dữ liệu này là MS SQL Server 2008.

Hình 3.11: Một phần danh sách tài khoản Facebook

Sau khi thu thập xong danh sách tài khoản Facebook, ta tiến hành thu thập

danh sách các người dùng tham gia bình luận trên Facebook đó, tách ra từng ID người

dùng đơn nhất. Cách thức thực hiện được trình bày ở mục dưới.

3.4.3.1. Thu thập dữ liệu mạng xã hội với Facebook API

Để xây dựng chương trình tự động thu thập các bình luận trên tường của một

tài khoản Facebook, ta sử dụng công cụ Facebook API [26]. Trước tiên cần đăng ký

một tài khoản facebook. Sau đó, truy cập vào liên kết

https://developers.facebook.com để tạo một ứng dụng với Facebook API.

Sau khi đăng ký thành công, giao diện sẽ như sau:

Hình 3.12: Giao diện đăng ký một ứng dụng trên Facebook API

Lúc này, ta đã có thể sử dụng các ngôn ngữ lập trình, cụ thể ở đây ta sử dụng

Visual Studio 2012 (C#) để xây dựng ứng dụng sử dụng Facebook API để thu thập

dữ liệu thông qua công cụ Graph API Explorer.

Một ví dụ thu thập thông tin các bình luận của người dùng trên tường của một

Facebook khi dùng Graph API Explorer thủ công như sau:

Hình 3.13: Thu thập dữ liệu thủ công với Graph API Explorer

Để thu thập tự động, ta sử dụng thư viện Facebook.dll với các tham số AppId,

Access token của ứng dụng đã đăng ký. Riêng giá trị Access token phải truy cập vào

ứng dụng để lấy lại mã vì mỗi giá trị này chỉ có giới hạn phiên làm việc là 2 giờ. Dữ

liệu có thể thu thập theo năm, theo số bình luận tối đa trên một trang dữ liệu trả về.

Vì thời gian thu thập dữ liệu rất lâu do số lượng bình luận trên các trang này là rất lớn

nên ta thu thập dữ liệu theo từng khoảng khác nhau với nhiều ứng dụng cùng thực thi

tại một thời điểm. Trong khuôn khổ luận văn này chỉ thu thập các dữ liệu bình luận

tính từ năm 2016 trở đi. Bộ dữ liệu thu thập được lưu trữ trên SQL Server 2008 với

dung lượng lên tới hơn 4.5 GB.

Hình 3.14: Thu thập dữ liệu tự động với Facebook API

Hình 3.15: Một phần dữ liệu thu thập được cập nhật trên SQL Server

Như ở hình 3.14, 3.15, dữ liệu trả về ở định dạng Json, tiến hành đọc định dạng

này và tách ra danh sách ID và đếm số lượng của các người dùng đơn nhất đã bình

luận trên các tường Facebook tương ứng.

Hình 3.16: Một phần dữ liệu về danh sách và số lượng ID người dùng đã bình luận

trên các tường Facebook tương ứng.

3.4.3.2. Tiền xử lý dữ liệu, xây dựng cấu trúc mạng xã hội dựa trên mối quan

tâm của người dùng

Với dữ liệu đã thu thập được, có một số tường Facebook không thu thập được

dữ liệu do các tài khoản này đã thiết lập quyền không cho phép thu thập tự động thông

qua Facebook API. Ta tiến hành loại bỏ các bản ghi này và một số bản ghi có ít người

tham gia bình luận (dưới 100 người) để bộ dữ liệu có ý nghĩa.

Sau đó ta tiến hành xây dựng dữ liệu đồ thị mạng xã hội thu thập được theo

mô hình đã giới thiệu ở 3.4.2, và tiến hành xuất ra file FacebookGraphWeight.txt để

làm đầu vào cho thuật toán INC phân cụm.

Định dạng file FacebookGraphWeight.text gồm có các dòng là các cạnh của

đồ thị với các thông số: đỉnh đầu, đỉnh cuối, số người bình luận chung, số người bình

luận trên tường facebook đỉnh đầu, số người bình luận trên tường facebook đỉnh cuối.

Dựa trên các giá trị này, trong chương trình sẽ tính ra được trọng số của các cạnh của

đồ thị theo công thức trong 3.4.2.

Sau khi tiền xử lý dữ liệu, bộ dữ liệu thu thập được gồm 1500 đỉnh

(FacebookID), 109445 cạnh và 2.604.079 người dùng Facebook đơn nhất tham gia

bình luận trên các tường này.

Hình 3.17: Một phần dữ liệu mạng xã hội dựa trên mối quan tâm của người dùng

3.4.4. Xây dựng ứng dụng

Dựa trên các nghiên cứu ở các chương trước, ta tiến hành cài đặt các ứng dụng

để đánh giá kết quả đạt được trên bộ dữ liệu thực nghiệm. Các chức năng chính của

ứng dụng demo như sau:

3.4.4.1. Tự động thu thập và xây dựng dữ liệu

Được phát triển trên ngôn ngữ C#.NET với bộ Visual Studio 2012 và hệ quản

trị CSDL Microsoft SQL Server 2008, kết hợp với thư viện hỗ trợ lập trình Facbook

API.

Người dùng nhập vào chuỗi Access Token của ứng dụng theo phiên làm việc

của Facebook, nhập vào các tham số thời gian thu thập tính từ năm nào, số bình luận

tối đa thu được trên một trang (nếu dữ liệu lớn Facebook sẽ phân trang kết quả trả

về), thu thập cho các ID facebook nằm trong khoảng nào (áp dụng cho việc chạy

nhiều tiến trình đồng thời - vì chạy một ứng dụng thu thập sẽ rất mất thời gian). Bấm

nút "Thu thập comments" để tự động thu thập các bình luận và ghi vào cơ sở dữ liệu:

Hình 3.18: Giao diện tự động thu thập bộ dữ liệu

Sau khi thu thập xong các bình luận, bấm nút "Tách Facebook ID" để tách

riêng các ID của người dùng đã bình luận tương ứng với các tường Facebook được

lựa chọn. Sau khi tách xong, bấm nút "Xây dựng mạng cụm" để tạo ra file dữ liệu đầu

vào cho việc phân cụm.

3.4.4.2. Phân cụm đồ thị mạng xã hội với CNM và INC

Ứng dụng được kế thừa từ bộ thư viện mã nguồn mở SNAP [23] viết trên

Visual C++ Console phục vụ cho mục đích nghiên cứu các thuật toán phân cụm.

Trong bộ thư viện này có cài đặt thuật toán CNM nhưng chỉ áp dụng cho đồ thị vô

hướng không có trọng số. Tiến hành phát triển CNM cho đồ thị vô hướng có trọng số

theo yêu cầu của thuật toán INC đã trình bày ở 2.6

Sau đó tiến hành cài đặt thuật toán INC dựa trên thuật toán CNM với tham số

đầu vào là đồ thị mạng xã hội đã thu thập được và chỉ số s (cận trên của kích thước

các cụm) nếu có. Kết quả xuất ra số lượng cụm, thời gian thực hiện thuật toán và độ

đo chất lượng phân cụm của với các thuật toán INC và CNM để tiện theo dõi, so sánh

kết quả.

Hình 3.19: Kết quả chạy chương trình phân cụm với INC và CNM.

Ngoài việc xuất ra kết quả chung trên màn hình, chương trình còn xuất ra file

kết quả chi tiết (danh sách các cụm và các thành viên trong cụm) dưới định dạng file

Json phục vụ cho việc biểu diễn trực quan biểu đồ dendrogram phân chia cụm.

3.4.4.3. Biểu diễn trực quan kết quả phân cụm với CNM cải tiến

Để biểu diễn trực quan kết quả phân cụm, em xây dựng ứng dụng ASP.NET

với C# để vẽ biểu đồ dendrogram của file kết quả dưới định dạng Json, sử dụng phần

mềm mã nguồn mở D3 [27]. Để việc biểu diễn được chính xác, định dạng file Json

được nghiên cứu kỹ lưỡng và được xuất ra tương ứng ở từng vòng lặp đệ quy của

thuật toán INC.

Hình 3.20: Một phần biểu đồ dendrogram kết quả phân cụm với INC

3.4.5. Thực nghiệm và đánh giá INC

Để đánh giá kết quả của thuật toán INC, tác giả tiến hành thực nghiệm trên bộ

dữ liệu thu thập được ở 3.4.3. Cấu hình máy tính sử dụng để tiến hành thực nghiệm

như sau:

- Hệ điều hành: Windows 8.1 64bit

- Processor: Intel(R) Celeron(R) CPU G1840 @2.80GHz

- RAM: 8GB.

Kết quả thực thi 2 thuật toán INC và CNM được cho bởi bảng 3.2 dưới đây:

Số cụm

Thời gian thực thi (giây)

Chất lượng phân cụm (Modularity)

Bộ dữ liệu

s

INC

CNM

INC

CNM

INC

CNM

321

2480.094

8.25

7.35

1212.408

284

2651.66

224

2730.1

188

2785.667

168

2754.92

Facebook Dataset (1500)

140

2713.86

137

2721.756

135

50 2719.86 Bảng 3.2: Kết quả thực thi thuật toán INC và CNM

3.4.5.1. Thời gian thực thi thuật toán

Với bộ dữ liệu đầu vào thu thập được: đồ thị 1500 đỉnh và 109445 cạnh, thuật

toán INC cho thời gian chạy là 6.60(s), CNM là 5.99(s). Như vậy có thể thấy tốc độ

8.25

7.35

INC

của INC không chênh lệch nhiều so với CNM.

) y â i g ( n a i g i

CNM

ờ h T

Facebook Dataset (1500) Bộ dữ liệu (số đỉnh mạng xã hội)

Hình 3.21: Đồ thị so sánh thời gian thực thi INC và CNM

3.4.5.2. Số lượng cụm tìm được

Kết quả thực nghiệm tên bộ dữ liệu thu thập được cho thấy số lượng cụm tìm

400

321

300

200

INC

100

CNM

được bởi thuật toán INC là 321 cụm, vượt trội so với thuật toán CNM (92 cụm).

g n ồ đ g n ộ c ố S

Facebook Dataset (1500) Bộ dữ liệu (số đỉnh mạng xã hội)

Hình 3.22: Đồ thị so sánh số lượng cụm theo INC và CNM

Khi người dùng đưa vào tham số s (cận trên của kích thước cụm), thì số lượng

321

400

284

224

188

168

140

137

135

200

INC

cụm thu được tỷ lệ nghịch với giá trị của s.

g n ồ đ g n ộ c ố S

10 30 Giá trị tham số s

Hình 3.23: Đồ thị tương quan số lượng cụm với giá trị s

3.4.5.3. Chất lượng phân chia cụm

Kết quả thực nghiệm tên bộ dữ liệu thu thập được cho thấy chất lượng phân

3000

2480.094196

2500

2000

INC

1212.407817

1500

cụm bởi thuật toán INC là 2480,094, vượt trội so với thuật toán CNM (1212,408).

a ó h n u d o m

CNM

) ộ đ t ậ m

1000

(

500

i

ị r t á G

Facebook Dataset (1500) Bộ dữ liệu (số đỉnh mạng xã hội)

Hình 3.24: Đồ thị so sánh chất lượng phân cụm theo INC và CNM

Khi người dùng đưa vào tham số s (cận trên của kích thước cụm), thì chất

lượng cụm cũng thay đổi. Chất lượng cụm biến thiên tăng dần và đạt giá trị cao nhất

khi s=15 (D = 2785.667), sau đó giảm dần khi s tăng lên. Khi s càng tăng thì giá trị

2850

2785.667

2800

2754.92

2730.1

2713.86 2721.756 2719.86

2750

2700

2651.66

2650

2600

INC

2550

2480.094196

2500

2450

D sẽ tiến tới giá trị phân chia cụm của CNM là 1212.408.

c ặ đ y à d n u đ ô m o đ ộ Đ

2400

2350

2300

Giá trị tham số s

Hình 3.25: Đồ thị tương quan chất lượng cụm với giá trị s

3.4.5.4. Đánh giá trực quan trên biểu đồ kết quả

Căn cứ trên biểu đồ dendrogram biểu diễn kết quả phân các cụm trong mạng

xã hội với bộ dữ liệu thu thập được cho thấy chất lượng phân chia cụm khá tốt. Các

nút bên trong biểu diễn một cụm ở các mức khác nhau, các nút lá là các tường

Facebook. Các cụm ở mức cuối chính là kết quả phân chia theo INC, ở mức thứ hai

là kết quả phân chia theo thuật toán CNM.

Hình 3.26 dưới đây là một ví dụ phân chia cụm lớn từ CNM (cụm quan tâm

tới ô tô, xe máy, bất động sản, chứng khoán) thành các cụm con với thuật toán INC.

Đối với cụm con quan tâm tới ô tô, thuật toán còn có thể chia nhỏ thành các cụm quan

tâm tới các dòng xe khác nhau (Lamborghini, Renault, Lexus, Kia, Honda, Toyota...)

và phân khúc khác nhau (xe bình dân, xe sang...).

Hình 3.26: Kết quả phân chia cụm lớn thành các cụm con (bất động sản, chứng

khoán, ô tô, xe máy...).

Hình 3.27 dưới đây là một ví dụ phân chia cụm lớn từ CNM (yêu thích đồ nội thất,

lưu niệm, thời trang, ngân hàng) thành các cụm con với thuật toán INC. Đối với cụm

con quan tâm tới thời trang, thuật toán còn có thể chia nhỏ thành các cụm quan tâm

tới các loại khác nhau như giày dép, đồng hồ, mũ, quần áo, ...

Hình 3.27: Kết quả phân chia cụm lớn yêu thích đồ nội thất, lưu niệm, thời trang

thành các cụm con (giày dép, đồng hồ,hoa tươi, quà lưu niệm, ngân hàng...).

Hình 3.28: Kết quả phân cộng động quan tâm tới Phật giáo

Hình 3.29: Kết quả phân cộng động quan tâm tới mỹ phẩm, thẩm mỹ, bệnh viện

thẩm mỹ đã được phân chia theo INC.

* Đánh giá chung:

 Thuật toán INC cho thời gian thực thi nhanh, không lâu hơn so với CNM là mấy.

 Thuật toán cho số lượng cụm tìm thấy nhiều hơn rất nhiều so với thuật toán CNM.

 Khi giá trị s tăng dần thì số cụm tìm được giảm dần và chất lượng cụm cũng giảm

dần.

 Chất lượng phân chia cụm của INC tốt hơn nhiều so với CNM xét trên độ đo mô

đun hóa mật độ.

 Phân tích trực quan kết quả cho thấy việc phân chia cụm của INC khá chính xác.

3.5. Kết luận chương 3

Trong chương 3, em đã giới thiệu các kiến thức liên quan đến mạng xã hội và

bài toán phân cụm đồ thị dữ liệu mạng xã hội. Để áp dụng các thuật toán phân cụm

phân cấp đã nghiên cứu để phân cụm dữ liệu đồ thị mạng xã hội, em đã tiến hành thu

thập 05 bộ dữ liệu mạng xã hội và cài đặt, thực nghiệm 03 thuật toán đã nghiên cứu

trên 05 bộ dữ liệu này và tiến hành đánh giá kết quả đạt được. Qua kết quả thực

nghiệm cho thấy, thuật toán Clauset-Newman-Moore đang là thuật toán cho kết quả

tốt nhất trong phân cụm đồ thị dữ liệu mạng xã hội, cả về thời gian thực thi thuật toán,

số lượng cụm tìm được cũng như chất lượng phân cụm.

Do thuật toán CNM cho ra số cụm rất ít, và nhiều cụm có kích thước lớn. Trên

thực tế, với bài toán phân cụm đồ thị mạng xã hội cần phân cụm thành các cụm có

kích thước nhỏ nhằm phản ánh rõ nét tính chất của các phần tử trong cụm (cụ thể ở

đây là mối quan tâm của các người dùng mạng xã hội tới các lĩnh vực, chủ đề cụ thể)

nên thuật toán INC cải tiến từ thuật toán CNM được xây dựng để đáp ứng mục tiêu

đó, qua đó hỗ trợ các hoạt động như truyền thông, quảng cáo, marketing online hướng

tới đúng những cụm đối tượng người dùng cụ thể.

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ân cụm người dù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 dựa trên thuật toán phân cụm đượ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ệ,...

Những kết quả chính của luận văn:

 Trình bày các kiến thức tổng quan về đồ thị dữ liệu, các phương pháp phân cụm

đồ thị dữ liệu, trong đó tập trung vào các phương pháp phân cụm phân cấp đồ thị

dữ liệu. Trên cơ sở các thuật toán đã nghiên cứu.

 Cài đặt các thuật toán và thử nghiệm trên 05 bộ dữ liệu mạng xã hội thực tế (các

bộ dữ liệu chuẩn sử dụng trong đánh giá các thuật toán phân cụm đồ thị mạng xã

hội).

 Kết quả thực nghiệm cho thấy thuật toán CNM (Clauset-Newman-Moore) là thuật

toán tốt nhất hiện nay cho phân cụm để phát hiện cộng đồng trong các mạng xã

hội với tốc độ tính toán nhanh nhất, chất lượng phân cụm tốt ít nhất tương đương

với thuật toán Girvan-Newman theo tiêu chí đánh giá độ đo Modularity.

 Chất lượng phân chia cụm của INC tốt hơn nhiều so với CNM xét trên độ đo mô

đun hóa mật độ.

 Phân tích trực quan kết quả cho thấy việc phân chia cụm của INC khá chính xác.

2. Hướng phát triển của đề tài

Mặc dù đã rất cố gắng nhưng với thời gian thực hiện luận văn không nhiều,

khối lượng kiến thức cần nghiên cứu nhiều nên luận văn vẫn còn tồn tại những hạn

chế cần khắc phục trong thời gian tới, cụ thể như:

- Việc đánh giá kết quả cần tiến hành trên nhiều bộ dữ liệu hơn, kích thước dữ

liệu lớn hơn .

- Cài đặt và đánh giá kết quả trên nhiều thuật toán hơn để thấy được đầy đủ

hơn về những điểm mạnh, yếu của từng thuật toán.

- Hiển thị kết quả phân cụm trực quan hơn, có thể làm việc với các loại dữ liệu

đầu vào khác nhau như file .gml...

TÀI LIỆU THAM KHẢO

Tiếng Việt

1. 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, NXBGD.

2. Lê Minh Tiến (2006), “Tổng quan phương pháp phân tích mạng xã hội trong

nghiên cứu xã hội”. Tạp chí khoa học xã hội. Số 9.

3. Nguyễn Hoàng Tú Anh (2009), Giáo trình "Khai thác dữ liệu và ứng dụng", Đại

học Khoa học Tự nhiên TP. HCM.

Tiếng Anh

4. B. W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning

graphs. Bell System Technical Journal 49, 291-307 (1970).

5. Clauset A, Newman MEJ, Moore C (2004), Finding community structure in very

large networks. Phys Rev E 70(6):066,111.

6. Doan Nhat Quang (2013), New models for hierarchical and topological clustering,

Ph D Thesis PARIS 13 UNIVERSITY - SORBONNE PARIS CITÉ.

7. Girvan M, Newman MEJ (2002), Community structure in social and

biological networks. PNAS 99(12):7821–7826.

8. Girvan, M. & Newman, M.E.J. (2004). Finding and evaluating community

structure in networks. Physical review. E, Statistical, nonlinear, and soft matter

physics, 69.

9. Hanene Azzag, Gilles Venturini, Antoine Oliver et Christiane Guinot (2007), A

hierarchical ant based clustering algorithm and its use in three real-world applications,

European Journal of Operational Research, vol. 179, no. 3, June 2007.

10. H. Azzag, N. Monmarch´e, M. Slimane, G. Venturini, C. Guinot (2012), AntTree:

a New Model for Clustering with Artiﬁcial Ants.

11. Istvan Jonyer, Diane J. Cook, Lawrence B. Holder (2002), Graph-Based

Hierarchical Conceptual Clustering, Journal of Machine Learning Research.

12. M. Girvan, M. E. J. Newman (2002), Community structure in social and

biological networks, Proc. Natl. Acad. Sci., 99(12), 7821.

13. M. E. J. Newman (2004), Fast algorithm for detecting community structure in

networks. Phys. Rev. E 69, 066133.

14. Martin Rosvall, Carl T. Bergstrom (2007), "Maps of random walks on complex

networks reveal community structure", Department of Biology, University of

Washington, Seattle.

15. Newman, M.E.J. (2006). Modularity and community structure in networks.

Proceedings of the National Academy of Sciences, 103, 8577-8582.

16. Newman, M.E.J. (2004). Detecting community structure in networks. The European

Physical Journal B - Condensed Matter and Complex Systems, 38, 321-330.

17. Network data sets (truy cập ngày 10/2/2017)

http://www-personal.umich.edu/~mejn/netdata/

18. P. Eades and Q.W. Feng (1996), Multilevel visualization of clustered graphs, In

Proceedings of the Symposium on Graph Drawing, GD ’96, pages 101–112,

Berkeley, California, USA, September 1996.

19. Pinney J,Westhead D (2007), Betweenness-based decomposition methods for

social and biological networks. Interdiscipl StatBioinf pp 87–90.

20. Reinhard Diestel (2005), Graph Theory, Springer-Verlag Heidelberg, NY, 2005.

21. Santo Fortunato (2010), Community detection in graphs.

22. Social Networks Datasets (truy cập ngày 10/2/2017)

https://snap.stanford.edu/data/#socnets

23. Teuvo Kohonen (2001), Self-Organizing Maps, Third Edition, Springer,

Heidelberg.

24. Zhang S, Ning X, Ding C (2009), Maximizing modularity density for exploring

modular organization of protein interaction networks. In: Third international

symposium on optimization and systems biology, pp361–370

25. Zheng Chen (2009), Graph-based Clustering and its Application in Coreference

Resolution, The Graduate Center, The City University of New York.

26. http://mbostock.github.com/d3/

27. http://snap-graph.sourceforge.net

28. http://developers.facebook.com/

29. http://julianhopkins.net

30. https://link.springer.com/article/10.1007/s13278-014-0170-z

31. http://www-personal.umich.edu/~mejn/netdata/

Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu mô hình phân cụm có thứ bậc các đồ thị dữ liệu

NGUYỄN THẾ ĐẠT

NGHIÊN CỨU MÔ HÌNH

PHÂN CỤM CÓ THỨ BẬC CÁC ĐỒ THỊ DỮ LIỆU

LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH

Thái Nguyên – 2017

NGUYỄN THẾ ĐẠT

NGHIÊN CỨU MÔ HÌNH PHÂN CỤM CÓ THỨ BẬC

CÁC ĐỒ THỊ DỮ LIỆU

Chuyên ngành: Khoa học máy tính

Mã số: 60 48 0101

LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS ĐOÀN VĂN BAN

Thái Nguyên – 2017

LỜI CẢM ƠN

(1.7)

(1.8)

(1.9)

(1.10)

(1.21)

(1.22)

(1.23)

(1.24)

(1.26)

(1.27)

(1.28)

(1.29)

(2.1)

(2.2)

(2.9)

𝐶𝐵

3.2.1. Giai đoạn 1: Thu thập dữ liệu

3.2.2. Giai đoạn 2: Xử lý dữ liệu

Số cụm

Chất lượng phân cụm (Modularity)

STT

Bộ dữ liệu

Thời gian thực thi (giây) GN

) y â i g ( i

h t c ự h t n a i g i ờ h T

Bộ dữ liệu

i

) y â i g (

h t c ự h t n a i g i ờ h T

Bộ dữ liệu

i

) y â i g (

h t c ự h t n a i g i ờ h T

Bộ dữ liệu

Số cụm

Thời gian thực thi (giây)

Chất lượng phân cụm (Modularity)

Bộ dữ liệu

s

) y â i g ( n a i g i

ờ h T

Facebook Dataset (1500) Bộ dữ liệu (số đỉnh mạng xã hội)

g n ồ đ g n ộ c ố S

Facebook Dataset (1500) Bộ dữ liệu (số đỉnh mạng xã hội)

g n ồ đ g n ộ c ố S

10 30 Giá trị tham số s

a ó h n u d o m

) ộ đ t ậ m

(

i

ị r t á G

Facebook Dataset (1500) Bộ dữ liệu (số đỉnh mạng xã hội)

c ặ đ y à d n u đ ô m o đ ộ Đ

Giá trị tham số s

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ụ