CHƯƠNG 3: ỨNG DỤNG THUẬT TOÁN PHÂN CỤM CÓ THỨ BẬC
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.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:
Bộ dữ liệu s Số cụm
Chất lượng phân cụm
(Modularity) Thời gian thực thi (giây)
INC CNM INC CNM INC CNM
Facebook Dataset
(1500)
0 321 92 2480.094 1212.408 8.25 7.35
5 284 2651.66
10 224 2730.1
15 188 2785.667
20 168 2754.92
30 140 2713.86
40 137 2721.756
50 135 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 độ của INC không chênh lệch nhiều so với CNM.
Hình 3.21: Đồ thị so sánh thời gian thực thi INC và CNM
8.25 7.35
0 2 4 6 8 10
Facebook Dataset (1500)
Thời gian (giây)
Bộ dữ liệu (số đỉnh mạng xã hội)
INC 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 đượ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).
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 cụm thu được tỷ lệ nghịch với giá trị của 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 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).
Hình 3.24: Đồ thị so sánh chất lượng phân cụm theo INC và CNM
321
92 0
100 200 300 400
Facebook Dataset (1500)
Số cộng đồng
Bộ dữ liệu (số đỉnh mạng xã hội)
INC CNM
321 284
224 188 168 140 137 135
0 200 400
0 5 10 15 20 30 40 50
Số cộng đồng
Giá trị tham số s
INC
2480.094196
1212.407817
0 500 1000 1500 2000 2500 3000
Facebook Dataset (1500)
Giá trị modun hóa (mật độ)
Bộ dữ liệu (số đỉnh mạng xã hội)
INC 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ị D sẽ tiến tới giá trị phân chia cụm của CNM là 1212.408.
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...).
2480.094196 2651.66
2730.1
2785.667 2754.92
2713.86 2721.756 2719.86
2300 2350 2400 2450 2500 2550 2600 2650 2700 2750 2800 2850
0 5 10 15 20 30 40 50
Độ đo mô đun dày đặc
Giá trị tham số s
INC
+
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.