CHƯƠNG 2: PHÂN CỤM CÓ THỨ BẬC CÁC ĐỒ THỊ DỮ LIỆU
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ả 5. return; // Thoát khỏi thủ tục đệ quy
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:
𝐷 = ∑2𝑙𝑖 − 𝑙𝑜 𝑛𝑖
|𝐶|
𝑖=1