Nghiên cứu kỹ thuật và ứng dụng về phân cụm trong khai phá dữ liệu

Nghiên cứu kỹ thuật và ứng dụng về phân cụm trong khai phá dữ liệu Nghiên cứu kỹ thuật và ứng dụng về phân cụm trong khai phá dữ liệu Nghiên cứu kỹ thuật và ứng dụng về phân cụm trong khai phá dữ liệu Nghiên cứu kỹ thuật và ứng dụng về phân cụm trong khai phá dữ liệu Nghiên cứu kỹ thuật và ứng dụng về phân cụm trong khai phá dữ liệu

CÁC PHƯƠNG PHÁP PHÂN CỤM DỮ LIỆU

Tổng quan về phân cụm dữ liệu

Khai phá dữ liệu (Data mining) là quá trình trích xuất thông tin giá trị từ tập dữ liệu lớn trong các cơ sở dữ liệu Phân cụm dữ liệu, một kỹ thuật trong Data Mining, giúp phát hiện các cụm và mẫu dữ liệu tự nhiên quan trọng, từ đó cung cấp thông tin hữu ích cho việc ra quyết định.

Phân cụm dữ liệu là quá trình chia tập dữ liệu thành các cụm sao cho các phần tử trong cùng một cụm tương tự nhau, trong khi các phần tử ở các cụm khác nhau thì phi tương tự Số lượng cụm có thể được xác định trước hoặc tự động, và độ tương tự giữa các phần tử được đánh giá dựa trên giá trị thuộc tính mô tả Phép đo khoảng cách thường được sử dụng để xác định mức độ tương tự hay phi tương tự giữa các phần tử.

Trong hình 1.1, quá trình phân cụm dữ liệu cho thấy ba cụm được hình thành, trong đó các phần tử tương tự được nhóm lại với nhau, trong khi các phần tử phi tương tự được phân chia vào các cụm khác nhau Phân cụm dữ liệu trong học máy được coi là một vấn đề học không có giám sát (Unsupervised Learning), vì nó tập trung vào việc tìm kiếm cấu trúc trong tập dữ liệu mà không có thông tin về lớp hay dữ liệu huấn luyện trước đó Ngược lại, phân lớp được xem là một vấn đề học có giám sát (Supervised Learning).

Phân cụm dữ liệu là bước quan trọng trong quá trình phân lớp dữ liệu, giúp khởi tạo các lớp bằng cách xác định nhãn cho các nhóm dữ liệu.

Trong phân cụm dữ liệu, việc xử lý dữ liệu "nhiễu" là rất quan trọng do sự thiếu chính xác trong quá trình thu thập Để cải thiện chất lượng dữ liệu, cần xây dựng chiến lược tiền xử lý nhằm khắc phục hoặc loại bỏ các dữ liệu không chính xác hoặc thiếu thông tin Một kỹ thuật phổ biến là thay thế giá trị của thuộc tính đối tượng "nhiễu" bằng giá trị của đối tượng gần nhất Ngoài ra, việc phát hiện phần tử ngoại lai cũng là một hướng nghiên cứu quan trọng, giúp xác định các đối tượng dữ liệu "khác thường" để giảm thiểu ảnh hưởng của chúng đến quá trình phân cụm Khám phá các phần tử ngoại lai đã được ứng dụng trong nhiều lĩnh vực như viễn thông và phát hiện gian lận thương mại.

1.1.2 Ứng dụng của phân cụm dữ liệu

Phân cụm dữ liệu là một công cụ quan trọng trong khai phá dữ liệu (KPDL), được ứng dụng rộng rãi trong nhiều lĩnh vực như thương mại và khoa học Các kỹ thuật phân cụm đã được áp dụng hiệu quả trong nhiều ứng dụng tiêu biểu trong các lĩnh vực này.

- Thương mại: Giúp các doanh nhân khám phá ra các nhóm khách hàng quan trọng để đưa ra các mục tiêu tiếp thị

- Sinh học: Xác định các loài sinh vật, phân loại các Gen với chức năng tương đồng và thu được cấu trúc trong các mẫu

- Lập quy hoạch đô thị: Nhận dạng các nhóm nhà theo kiểu và vị trí địa lý, nhằm cung cấp thông tin cho quy hoạch đô thị

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

- Bảo hiểm: Nhận dạng nhóm tham gia bảo hiểm có chi phí bồi thường cao, nhận dạng gian lận thương mại

- Nghiên cứu đất đai: Phân cụm để theo dõi các tâm động đất nhằm cung cấp thông tin cho nhận dạng các vùng nguy hiểm

Khai phá Web là quá trình phân cụm nhằm khám phá các nhóm tài liệu quan trọng và có ý nghĩa trong môi trường trực tuyến Những lớp tài liệu này hỗ trợ việc khai thác tri thức từ dữ liệu Web, giúp phát hiện các mẫu truy cập của khách hàng đặc biệt và tìm ra các cộng đồng trên mạng.

1.1.3 Các yêu cầu đối với kỹ thuật phân cụm dữ liệu

Việc lựa chọn thuật toán phân cụm là bước quan trọng trong việc giải quyết vấn đề phân cụm, phụ thuộc vào đặc tính dữ liệu, mục đích ứng dụng thực tế, và ưu tiên giữa chất lượng cụm và tốc độ thực hiện Dưới đây là những yêu cầu cơ bản của phân cụm trong khai phá dữ liệu.

- Có khả năng mở rộng: Một số thuật toán có thể ứng dụng tốt cho tập dữ liệu nhỏ (khoảng

200 bản ghi dữ liệu) nhưng không hiệu quả khi áp dụng cho tập dữ liệu lớn (khoảng 1 triệu bản ghi).

Thuật toán có khả năng thích nghi linh hoạt với nhiều loại dữ liệu khác nhau, bao gồm dữ liệu số, nhị phân, định danh và hạng mục Điều này cho phép thuật toán phân cụm hiệu quả các tập dữ liệu đa dạng và hỗn hợp.

Khám phá các cụm dữ liệu với hình dạng đa dạng là rất quan trọng, bởi vì nhiều cơ sở dữ liệu chứa các cụm có hình dạng khác nhau như hình lõm, hình cầu hay hình que Để nhận diện và phân loại các cụm tự nhiên, các thuật toán phân cụm cần phải có khả năng phát hiện các hình dạng bất kỳ của dữ liệu.

Để xác định các tham số đầu vào trong phân tích phân cụm, người dùng cần có một lượng tri thức tối thiểu, vì nhiều thuật toán yêu cầu nhập các tham số như số lượng cụm mong muốn Kết quả phân cụm thường nhạy cảm với các tham số này, và việc xác định chúng trở nên khó khăn, đặc biệt là với các tập dữ liệu lớn Điều này không chỉ gây khó khăn cho người dùng mà còn ảnh hưởng đến khả năng điều chỉnh chất lượng của phân cụm.

Khả năng thích nghi với dữ liệu nhiễu là yếu tố quan trọng trong việc xử lý cơ sở dữ liệu thực, vì hầu hết các cơ sở dữ liệu đều chứa dữ liệu ngoại lai, lỗi, chưa biết hoặc sai Nhiều thuật toán phân cụm có thể bị ảnh hưởng tiêu cực bởi những dữ liệu này, dẫn đến chất lượng phân cụm kém.

Thuật toán phân cụm có tính ít nhạy cảm với thứ tự dữ liệu đầu vào, nghĩa là khi sử dụng cùng một tập dữ liệu, kết quả phân cụm không bị ảnh hưởng nhiều bởi thứ tự mà các đối tượng dữ liệu được đưa vào xử lý trong các lần thực hiện khác nhau.

Thích nghi với dữ liệu đa chiều là điều quan trọng trong việc phân tích dữ liệu, đặc biệt khi một cơ sở dữ liệu hoặc kho dữ liệu có thể chứa nhiều chiều hoặc thuộc tính khác nhau Nhiều thuật toán phân cụm thường hoạt động hiệu quả với dữ liệu có từ 2 đến 3 chiều Tuy nhiên, việc đánh giá chất lượng phân cụm được xem là tốt khi nó có thể áp dụng cho dữ liệu có từ 3 chiều trở lên.

Kết quả phân cụm cần phải dễ hiểu, dễ giải thích và dễ sử dụng cho người sử dụng Điều này có nghĩa là việc phân cụm không chỉ phải rõ ràng mà còn cần có sự giải thích về ý nghĩa và ứng dụng của nó.

1.1.4 Các kiểu dữ liệu và độ đo tương tự

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

CÁC THUẬT TOÁN CƠ BẢN TRONG PHÂN CỤM DỮ LIỆU

Các thuật toán phân cụm phân hoạch

Phương pháp phân hoạch trong cơ sở dữ liệu với n đối tượng dữ liệu được thiết kế để chia dữ liệu thành k phần (k ≤ n), mỗi phần tương ứng với một cụm Mục tiêu là gom dữ liệu vào k nhóm, đảm bảo các nhóm này đáp ứng các yêu cầu nhất định.

(1) Mỗi nhóm phải chứa ít nhất một đối tượng;

(2) Mỗi đối tượng phải thuộc về chính xác một nhóm

Dưới đây là một số thuật toán phân hoạch điển hình như : K-Means, PAM, CLARA, CLARANS,…

Thuật toán phân cụm K-Means do MacQueen đề xuất trong lĩnh vực thống kê năm

Thuật toán K-Means, được phát triển vào năm 1967, nhằm mục đích phân nhóm n đối tượng trong không gian d chiều thành k cụm dữ liệu {C1, C2,…, Ck} Mỗi đối tượng được biểu diễn dưới dạng vector Xi =(xi1, xi2, …,xid) với i = 1 đến n.

Thuật toán K-Means phân chia n đối tượng thành k cụm, nhằm tối đa hóa độ tương tự trong từng cụm và tối thiểu hóa độ tương tự giữa các cụm Độ tương tự trong cụm được đánh giá dựa trên giá trị trung bình của các đối tượng, được coi là “trọng tâm” của cụm.

Giải thuật xử lý bắt đầu bằng việc chọn ngẫu nhiên k đối tượng, mỗi đối tượng này đại diện cho một trung bình cụm Các đối tượng còn lại sẽ được phân nhóm vào cụm mà chúng tương đồng nhất dựa trên khoảng cách tới trung bình cụm Sau đó, trung bình cụm mới sẽ được tính toán cho từng cụm Quá trình này tiếp tục lặp lại cho đến khi hàm tiêu chuẩn hội tụ, với bình phương sai số là hàm tiêu chuẩn thường được sử dụng để đạt giá trị tối thiểu.

Trong đó: mi là tâm của cụm Ci, D là khoảng cách giữa hai đối tượng

Tâm của một cụm được định nghĩa là một véc tơ, trong đó mỗi phần tử là giá trị trung bình cộng của các thành phần tương ứng từ các đối tượng vectơ dữ liệu trong cụm Để đo khoảng cách D giữa các đối tượng dữ liệu, khoảng cách Euclide thường được sử dụng.

Hàm tiêu chuẩn và độ đo khoảng cách có thể được xác định cụ thể hơn tuỳ vào ứng dụng hoặc các quan điểm của người dùng

Thuật toán K-Means bao gồm các bước sau:

Input: Tập dữ liệu chứa n đối tượng, số cụm k

Output: Tập k cụm dữ liệu được phân hoạch

Chọn k tâm {mj} j=1,k ban đầu trong không gian R d (d là số chiều của dữ liệu) Việc lựa chọn này có thể là ngẫu nhiên hoặc theo kinh nghiệm

Bước 2: Tính toán khoảng cách giữa mỗi điểm xi (1≤i≤n) và các tâm mj (j=1,k) Tiếp theo, xác định tâm gần nhất cho từng điểm.

Bước 3: Cập nhật tâm cụm Đối với mỗi j=1,k, cập nhật tâm cụm mj bằng cách xác định trung bình cộng của các vectơ đối tượng dữ liệu

Lặp các bước 2 và 3 đến khi các tâm của cụm không thay đổi.

Thuật toán K-Means có độ phức tạp tính toán là O(tkn), với t là số lần lặp, k là số cụm và n là số đối tượng trong tập dữ liệu Tuy nhiên, K-Means nhạy cảm với nhiễu và các phần tử ngoại lai, và chất lượng phân cụm phụ thuộc vào các tham số đầu vào như số cụm k và các trọng tâm khởi tạo Nếu các trọng tâm khởi tạo lệch so với các cụm tự nhiên, kết quả phân cụm sẽ không chính xác Hiện tại, chưa có giải pháp tối ưu để chọn tham số đầu vào, do đó, phương pháp phổ biến là thử nghiệm với nhiều giá trị k khác nhau để tìm ra giải pháp tốt nhất.

Trong một hệ trục tọa độ X, Y, giả sử có một tập đối tượng cần được phân chia thành 3 cụm với k=3 Đầu tiên, chúng ta sẽ chọn ngẫu nhiên 3 tâm cụm ban đầu (Hình bước 1) Tiếp theo, mỗi đối tượng sẽ được phân vào cụm gần nhất dựa trên vị trí của tâm cụm đó (Hình bước 2).

Sau khi cập nhật lại các tâm cụm, giá trị trung bình của mỗi cụm được tính toán dựa trên các đối tượng trong cụm Dựa vào các tâm mới này, các đối tượng sẽ được phân bố lại vào các cụm theo tâm cụm gần nhất.

Tính toán lại giá trị trung bình cụm (Hình bước 4b) và di chuyển tâm cụm về vị trí trung bình của cụm mới (Hình bước 5)

Hình 2.1 : Minh họa các bước thuật toán K-Means

Ví dụ: Phân cụm với thuật toán K-Means

Hàm tính khoảng cách Minkowski với r=1 p(a,b) = |x2-x1| +|y2-y1|

Chọn ngẫu nhiên 3 tâm cụm: c1(2,10), c2(5, 8) và c3(1,2)

Lần lượt tính khoảng cách từ mỗi tâm cụm đến các đối tượng dữ liệu còn lại

Chẳng hạn: p(point(2,10), c1(2,10)) = |2-2 | + |10-10| = 0 +0 = 0 p(point(2,10), c2(5,8)) = |5-2 | + |8-10| = 3 +2 = 5 p(point(2,10), c3(1,2)) = |1-2 | + |2-10| = 1 +8 = 9

Ta có bảng kết quả sau: c1(2,10), c2(5,8), c3(1,2)

DataSet Dist_Means1 Dist_Means2 Dist_Means3 Cluster

Điểm dữ liệu được phân loại vào các cụm dựa trên khoảng cách đến tâm cụm nhỏ nhất Ví dụ, điểm X2(2,5) thuộc về cụm 3 vì nó có khoảng cách ngắn nhất đến tâm cụm là 4.

Tính toán lại các tâm cụm mới bẳng trung bình cộng các điểm thuộc cụm:

Tâm Cluster 1: Không thay đổi vì chỉ có X1(2,1) là điểm thuộc cụm trước đó

Các cụm mới sẽ là:

Cluster 1: {X1} ; Cluster 2: {X3, X4, X5, X6,X8} ; Cluster 3: {X2, X7} với các tâm cụm C1=(2,10); C2=(6,6) ; C3=(1.5, 3.5)

Lặp lại tính toán khoảng cách từ các điểm đến các tâm cụm mới như bảng sau: c1(2,10), c2(6,6), c3(1.5,3.5)

DataSet Dist_Means1 Dist_Means2 Dist_Means3 Cluster

Các cụm mới sẽ là:

Cluster 1: {X1, X8} ; Cluster 2: {X3, X4, X5, X6} ; Cluster 3: {X2, X7} với các tâm cụm C1=(3,9.5); C2=(6.5,5.25) ; C3=(1.5, 3.5)

DataSet Dist_Means1 Dist_Means2 Dist_Means3 Cluster

Các cụm mới sẽ là:

Cluster 1: {X1, X4, X8} ; Cluster 2: {X3, X5, X6} ; Cluster 3: {X2, X7} với các tâm cụm C1=(3.66,9); C2=(7, 4.33) ; C3=(1.5, 3.5)

DataSet Dist_Means1 Dist_Means2 Dist_Means3 Cluster

Không có sự thay đổi vị trí các điểm thuộc các cụm Thuật toán dừng

Thuật toán PAM (Partitioning Around Medoids) được đề xuất bởi Kaufman và Rousseeuw vào năm 1987 là một phiên bản mở rộng của thuật toán K-Means, giúp xử lý hiệu quả dữ liệu nhiễu và các phần tử ngoại lai Thay vì sử dụng giá trị trung bình của các đối tượng trong cụm làm điểm đại diện như K-Means, PAM lựa chọn một đối tượng cụ thể trong cụm, gọi là medoid, để làm điểm đại diện cho cụm đó.

PAM (Partitioning Around Medoids) xác định 27 medoid là trung tâm của cụm, giúp giảm thiểu ảnh hưởng từ các đối tượng xa trung tâm Khác với K-Means, nơi mà các tâm cụm dễ bị tác động bởi các điểm ngoài, PAM khởi đầu bằng cách chọn k medoid và phân chia các đối tượng còn lại vào các cụm dựa trên sự tương đồng với medoid tương ứng.

Trong thuật toán PAM, một đối tượng Oj được xác định thuộc về cụm có medoid Om nếu khoảng cách d(Oj, Om) là nhỏ nhất so với khoảng cách giữa Oj và tất cả các đối tượng medoid khác Để tìm các medoid, PAM bắt đầu bằng việc chọn ngẫu nhiên k đối tượng medoid Sau mỗi bước, thuật toán sẽ hoán đổi một đối tượng medoid Om với một đối tượng Op không phải medoid nhằm cải thiện chất lượng phân cụm, và quá trình này sẽ dừng lại khi không còn sự cải thiện nào Chất lượng phân cụm được đánh giá qua hàm mục tiêu, với chất lượng tốt nhất đạt được khi hàm này có giá trị tối thiểu.

- Om: Là đối tượng medoid hiện thời cần được thay thế

- Op: Là đối tượng medoid mới thay thế cho Om;

- Oj : Là đối tượng dữ liệu (không phải là medoid) có thể được di chuyển sang cụm khác

- Oj,2: Là đối tượng medoid hiện thời khác với Om mà gần với đối tượng Oj nhất

Thuật toán PAM tính toán giá trị hoán đổi Cjmp cho tất cả các đối tượng Oj, phục vụ làm căn cứ cho việc hoán đổi giữa Om và Op Cjmp được xác định thông qua 4 trường hợp khác nhau, đảm bảo tính chính xác trong quá trình hoán đổi.

Trong trường hợp Oj thuộc về cụm đại diện Om, nếu khoảng cách giữa Oj và Op lớn hơn hoặc bằng khoảng cách giữa Oj và Oj,2, thì Oj,2 sẽ là đối tượng medoid xếp thứ hai gần nhất.

Các thuật toán phân cụm phân cấp

Trong phân cụm phân cấp, dữ liệu được cấu trúc thành một cây, với mỗi đỉnh đại diện cho một cụm Các lá của cây thể hiện các đối tượng riêng lẻ, trong khi các nút bên trong biểu thị các cụm.

Có hai loại phương pháp tạo kiến trúc cụm (hình 1.1):

- Gộp (Agglomerative) hay từ dưới lên (Bottom-up)

 Đưa từng đối tượng vào cụm riêng của nó

 Tại mỗi bước tiếp theo, trộn hai cụm tương tự nhất cho đến khi chỉ còn một cụm hay thỏa điều kiện kết thúc

- Phân chia (Divisive) hay từ trên xuống (Top-down)

 Bắt đầu bằng một cụm lớn chứa tất cả các đối tượng

 Phân chia cụm phân biệt nhất thành các cụm nhỏ hơn và xử lý cho đến khi có k cụm hay thỏa điều kiện kết thúc

Trong phương pháp phân cụm phân cấp khoảng cách giữa 2 cụm là một trong các loại sau:

- Single-linkage clustering: khoảng cách giữa hai cụm là khoảng cách ngắn nhất giữa hai đối tượng của hai cụm [4][5][6]

- Complete-linkage clustering: khoảng cách giữa hai cụm là khoảng cách lớn nhất giữa hai đối tượng của hai cụm

- Average-linkage clustering: khoảng cách giữa hai cụm là khoảng cách trung bình giữa hai đối tượng của hai cụm

2.2.1 Thuật toán AGNES Ý tưởng: Phương pháp phân cụm AGNES là kỹ thuật kiểu tích tụ AGNES bắt đầu ở ngoài với mỗi đối tượng dữ liệu trong các cụm riêng lẻ Các cụm được hòa nhập theo một số loại của cơ sở luật, cho đến khi chỉ có một cụm ở đỉnh của phân cấp, hoặc gặp điều kiện dừng Hình dạng này của phân cụm phân cấp cũng liên quan đến tiếp cận bottom-up bắt đầu ở dưới với các nút lá trong mỗi cụm riêng lẻ và duyệt lên trên phân cấp tới nút gốc, nơi tìm thấy cụm đơn cuối cùng với tất cả các đối tượng dữ liệu được chứa trong cụm đó

Thuật toán AGNES bao gồm các bước cơ bản sau :

Bước 1: Mỗi đối tượng là một cụm

Bước 2: Hợp nhất các cụm có khoảng cách giữa các nhóm là nhỏ nhất (Single Link)

Bước 3: Nếu thu được nhóm “toàn bộ” thì dừng, ngược lại quay lại bước 2

Hình 2.2: Các bước cơ bản thuật toán AGNES

2.2.2 Thuật toán DIANA Ý tưởng: Thuật toán DIANA thực hiện đối lập với AGNES DIANA bắt đầu với tất cả các đối tượng dữ liệu được chứa trong một cụm lớn và chia tách lặp lại, theo phân loại giống nhau

Cụm phân cấp được xây dựng theo cách tiếp cận top-down, bắt đầu từ nút gốc với tất cả các đối tượng dữ liệu trong cụm Quá trình này tiếp tục cho đến khi mỗi đối tượng dữ liệu được phân tách và chứa trong cụm riêng của nó, đảm bảo sự tổ chức và phân loại hiệu quả.

Thuật toán DIANA bao gồm các bước cơ bản sau :

Bước 1: Tất cả các đối tượng là một cụm

Bước 2: Chia nhỏ cụm có khoảng cách giữa những đối tượng trong cụm là lớn nhất (Complete

Bước 3: Nếu mỗi cụm chỉ chứa một đối tượng thì dừng, ngược lại quay lại quay lại bước 2

Hình 2.3: Các bước cơ bản thuật toán DIANA

BIRCH (Balanced Iterative Reducing and Clustering Using Hierarchies) là thuật toán phân cụm phân cấp được đề xuất bởi Tian Zhang, Amakrishnan và Livny vào năm 1996, sử dụng chiến lược Top-Down Thuật toán này không yêu cầu lưu trữ toàn bộ dữ liệu của các cụm trong bộ nhớ, mà chỉ cần lưu các đại lượng thống kê Đối với mỗi cụm, BIRCH chỉ lưu một bộ ba (n, LS, SS), trong đó n là số đối tượng, LS là tổng các giá trị thuộc tính và SS là tổng bình phương các giá trị thuộc tính Các bộ ba này, gọi là đặc trưng của cụm (CF), được lưu trong một cấu trúc cây được gọi là cây CF, trong đó mọi nút lưu tổng các đặc trưng của cụm.

CF của nút con, trong khi đó các nút lá lưu trữ các đặc trưng của các cụm dữ liệu Hình 2.4 minh họa một CF

Hình 2.4: Ví dụ về xác định đặc trưng cụm CF

Cây CF là một cấu trúc cân bằng dùng để lưu trữ các đặc trưng của cụm, bao gồm các nút trong và nút lá Các nút trong giữ tổng hợp các đặc trưng của các nút con, trong khi cây CF được xác định bởi hai tham số chính.

- Yếu tố nhánh (Branching Factor- B): Nhằm xác định số tối đa các nút con của mỗi nút trong của cây;

Ngưỡng (Threshold - T) là khoảng cách tối đa giữa bất kỳ cặp đối tượng nào trong nút lá của cây, đồng thời được xem như đường kính của các cụm con được lưu trữ tại các nút lá.

Hình 2.5: Cấu trúc cây CF

Thuật toán BIRCH thực hiện qua 2 giai đoạn sau:

Giai đoạn 1 : Duyệt tất cả các đối tượng trong tập dữ liệu và xây dựng một cây CF ban đầu

Các đối tượng được chèn vào nút lá gần nhất của cây CF, với nút lá đóng vai trò là cụm con Sau khi quá trình chèn hoàn tất, thông tin trên mọi nút của cây CF sẽ được cập nhật.

- Nếu đường kính của cụm con sau khi chèn lớn hơn ngưỡng T thì nút lá được tách ra

- Quá trình này được lặp đi lặp lại cho đến khi tất cả các đối tượng đều được chèn vào cây CF.

- Để lưu toàn bộ cây CF trong bộ nhớ thì cần phải điều chỉnh kích thước của cây CF thông qua điều chỉnh ngưỡng T

Giai đoạn 2: BIRCH lựa chọn một thuật toán phân cụm (như thuật toán phân cụm phân hoạch) để thực hiện phân cụm cho các nút lá của cây CF

Thuật toán BIRCH gồm 4 bước cơ bản sau:

Input: CSDL gồm n đối tượng, ngưỡng T

Bước đầu tiên trong quá trình xây dựng cây CF là duyệt qua tất cả các đối tượng trong cơ sở dữ liệu để tạo ra một cây CF khởi tạo Mỗi đối tượng sẽ được chèn vào nút lá gần nhất, hình thành nên các cụm con Nếu đường kính của cụm con vượt quá ngưỡng T, nút lá sẽ bị tách ra Khi một đối tượng phù hợp được chèn vào nút lá, tất cả các nút liên kết với gốc cây sẽ được cập nhật với thông tin cần thiết.

Nếu cây CF hiện tại không đủ bộ nhớ trong, hãy xây dựng một cây CF nhỏ hơn bằng cách điều chỉnh tham số T, vì tăng T sẽ giúp hoà nhập một số cụm con thành một cụm lớn hơn, từ đó giảm kích thước của cây CF Bước này không yêu cầu phải đọc lại dữ liệu từ đầu, nhưng vẫn đảm bảo hiệu chỉnh cho cây dữ liệu nhỏ hơn.

Bước 3 trong quá trình phân cụm là thực hiện phân cụm con, trong đó các nút lá của cây CF lưu giữ các đại lượng thống kê quan trọng Tại bước này, thuật toán BIRCH sử dụng các đại lượng thống kê này để áp dụng các kỹ thuật phân cụm như K-Means, từ đó tạo ra một khởi tạo hiệu quả cho quá trình phân cụm.

Bước 4: Phân phối lại các đối tượng dữ liệu bằng cách sử dụng các trọng tâm cho các cụm đã được khám phá từ bước 3 Đây là bước tùy chọn nhằm duyệt lại tập dữ liệu, gán nhãn lại cho các đối tượng dữ liệu gần nhất với trọng tâm, giúp gán nhãn cho dữ liệu khởi tạo và loại bỏ các đối tượng ngoại lai.

Thực nghiệm thuật toán phân hoạch

2.3.1 Mô tả bài toán phân cụm dữ liệu

Đề tài nghiên cứu này tập trung vào việc phân cụm dữ liệu nhằm phân nhóm khách hàng trên trang Facebook của một thương hiệu mỹ phẩm uy tín tại Thái Lan.

Trong nghiên cứu này, chúng tôi đã phân tích 36 bài đăng trên các nền tảng mạng xã hội, bao gồm video, hình ảnh, trạng thái và liên kết Dựa vào các chỉ số tương tác của người dùng như phản ứng, nhận xét và chia sẻ, chúng tôi đã thống kê và đánh giá theo các khung thời gian khác nhau như hàng giờ, hàng ngày và hàng tháng Qua đó, các hãng mỹ phẩm có thể thực hiện phân tích định tính về chiến lược tiếp cận và hiệu quả hoạt động bán hàng của họ.

Data is organized and stored in a CSV file format, resembling a spreadsheet layout similar to Excel This dataset comprises 12 attributes: status_id, status_type, status_published, num_reactions, num_comments, num_shares, num_likes, num_loves, num_wows, num_hahas, num_sads, and num_angrys.

2.3.2 Tiền xử lý dữ liệu

Trước khi tiến hành phân cụm dữ liệu, bước đầu tiên là xử lý làm sạch dữ liệu, bao gồm việc loại bỏ các mẫu tin dị thường và dữ liệu null Đồng thời, chúng tôi cũng tiến hành chọn lọc các thuộc tính quan trọng để đảm bảo khả năng phân nhóm hiệu quả Dựa trên thực tiễn và phạm vi nghiên cứu, chúng tôi đã chọn bốn thuộc tính chính để làm cơ sở phân cụm, bao gồm num_reactions, num_comments, num_shares và num_likes.

Trong quá trình phân cụm dữ liệu, việc sử dụng các phép đo khoảng cách giữa các điểm dữ liệu là rất quan trọng Giá trị của các phép đo này phụ thuộc vào thang đo được sử dụng, do đó, các biến cần được chia tỷ lệ hoặc chuẩn hóa trước khi đo lường sự khác biệt giữa các quan sát Điều này đặc biệt quan trọng khi các biến được đo bằng các thang đo khác nhau như kilôgam, ki lô mét hay cm, vì nếu không, các biện pháp khác biệt sẽ bị ảnh hưởng nghiêm trọng.

Chuẩn hóa dữ liệu là một phương pháp phổ biến trong phân tích dữ liệu trước khi tiến hành phân cụm Việc chia tỷ lệ dữ liệu trở nên cần thiết khi giá trị trung bình và độ lệch chuẩn của các biến có sự khác biệt lớn Khi thực hiện thay đổi tỷ lệ, dữ liệu có thể được chuyển đổi theo công thức: 𝑥 𝑖 −𝑚𝑒𝑎𝑛(𝑥).

Giá trị trung bình của các giá trị x được ký hiệu là Mean(x), trong khi độ lệch chuẩn được ký hiệu là SD(x), cho biết mức độ phân tán của tập dữ liệu xung quanh giá trị trung bình Công thức tính độ lệch chuẩn (SD) giúp xác định sự biến động của dữ liệu.

Trong một tập dữ liệu, giá trị của điểm dữ liệu thứ i được ký hiệu là x i, trong khi giá trị trung bình của tập dữ liệu là x̄ Tổng số quan sát trong tập dữ liệu được biểu thị bằng n Công thức tính toán sử dụng n - 1 để xác định các yếu tố liên quan đến phân tích dữ liệu.

2.3.3 Cài đặt chương trình thực nghiệm

Chương trình được xây dựng trên phần mềm Visual Studio 15 (C#), và tập dữ liệu dạng CSV [9][11] Bao gồm các lớp:

- Datapoint.cs: Thiết lập các thuộc tính của tập dữ liệu cần phân cụm

Clustering.cs là một tập hợp các hàm chức năng bao gồm kết nối và chuẩn hóa dữ liệu, triển khai hai thuật toán phân cụm K-Means và K-Medoids, và xuất ra dữ liệu đã được phân thành các cụm rõ ràng.

2.3.3.2 Màn hình chính của chương trình

Hình 2.6: Mô hình chương trình demo phân cụm dữ liệu

- Đọc dữ liệu nguồn (tệp CSV)

- Chọn thuật toán phân cụm K-Means hoặc K-Medoids

- Kết quả phân cụm được lưu vào tệp CSV

Dữ liệu được lưu trữ theo từng cụm dựa theo tiêu chí của 3 thuộc tính num_reactions, num_comments và num_shares

Hình 2.7: Kết quả phân cụm dữ liệu trên Facebook

2.3.4 Phân tích đánh giá kết quả thực nghiệm

Kết quả phân cụm theo thuật toán K-Means và K-Medoids với k=3 và số mẫu tin = 200 được thể hiện ở bảng 1 và bảng 2:

Status_Type Cụm dữ liệu

Bảng 2.1: Kết quả phân cụm dữ liệu trên Facebook bằng thuật toán K-Means

Trong bảng 1, cụm 1 và cụm 2 ghi nhận rằng hai trạng thái Video và Photo nhận được nhiều phản ứng (reaction) và bình luận (comment) từ người dùng Facebook hơn so với cụm 3.

Hình 2.8: Biểu đồ phân cụm dữ liệu trên Facebook bằng thuật toán K-Means

Dưới đây là bảng kết quả phân cụm dữ liệu bằng thuật toán K-Medoids

Status_Type Cụm dữ liệu

Bảng 2.2: Kết quả phân cụm dữ liệu trên Facebook bằng thuật toán K-Medoids

Bảng 2 chỉ ra rằng cụm 1 và cụm 3 có số lượng phản ứng (reaction) và bình luận (comment) trên Facebook cao hơn so với cụm 2 ở hai trạng thái Video và Photo.

Hình 2.9: Biểu đồ phân cụm dữ liệu trên Facebook bằng thuật toán K-Medoids

Biểu đồ phân cụm trạng thái trên Facebook

Bảng 3 so sánh tốc độ thực hiện của hai thuật toán K-Means và K-Medoids, với dữ liệu gồm 200 bản ghi và 3 thuộc tính, được thể hiện bằng đơn vị giây.

Bảng 2.3: Thời gian thực hiện phân cụm bằng thuật toán K-Means và K-Medoids

Hình 2.10: Biểu đồ so sánh giữa thuật toán K-Means và K-Medoids

Thuật toán K-Medoids cho thấy hiệu quả vượt trội hơn so với K-Means trong việc thực hiện phân cụm, như được minh họa trong hình 2.10 Hơn nữa, theo hình 2.8, K-Medoids cũng cho kết quả phân cụm chính xác hơn trên hai nhóm dữ liệu Video và Photo, dựa trên ba thuộc tính num_reactions, num_comments và num_shares.

Biểu đồ so sánh tốc độ phân cụm của 2 thuật toán

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

1 Kết luận: Đề tài đã thực hiện được mục tiêu nghiên cứu với các nội dung sau:

Nghiên cứu về phân cụm dữ liệu trong quá trình khai phá dữ liệu đóng vai trò quan trọng trong việc hiểu và phân tích thông tin Phân cụm không chỉ giúp tổ chức dữ liệu một cách hiệu quả mà còn có nhiều ứng dụng thực tiễn trong các lĩnh vực kinh tế - xã hội Việc áp dụng phân cụm giúp phát hiện các mẫu và xu hướng, từ đó hỗ trợ ra quyết định và tối ưu hóa quy trình trong các ngành nghề khác nhau.

Nghiên cứu các kiểu dữ liệu và các phương pháp đo lường độ tương tự hoặc độ phi tương tự giữa các đối tượng dữ liệu là rất quan trọng Điều này tạo nền tảng cho việc tính toán khoảng cách giữa các đối tượng trong quá trình phân cụm dữ liệu.