Phân nhóm, hay gọi đầy đủ hơn là phân tích nhóm (clustering analysis), nhằm mục đích tách các thành phần của một đối tượng thành một số nhóm. Các thành phần của một nhóm có sự đồng nhất cao hơn so với toàn bộ dữ liệu ban đầu. Nếu so sánh với phân tích sự khác biệt (discriminant analysis) thì phân nhóm có một số đặc điểm riêng như sau:

• Trong phân tích sự khác biệt, các nhóm đã được hình thành sẵn dựa trên biến phân nhóm; ta đã biết trước các nhóm cũng như phần tử trong các nhóm. Trong phân tích nhóm thì không, số nhóm và các thành phần trong mỗi nhóm là kết quả của phân nhóm.
• Trong phân tích sự khác biệt, có hai loại biến, biến phụ thuộc (biến phân nhóm) và biến độc lập. Trong phân nhóm, các biến tham gia vào quá trình xử lý có vai trò như nhau.
• Đối tượng của phân tích sự khác biệt là các phần tử. Trong phân nhóm, đối tượng có thể là các phần tử, các biến hay cả hai. Tuy vậy trong phần này, chúng ta tập trung vào việc phân nhóm các phần tử.

Để có thể đưa một phần tử vào nhóm này hay chuyển nó sang nhóm khác, ta phải dựa vào sự giống nhau hay khác nhau. Để đánh giá sự giống nhau hay khác nhau, ta sử dụng khái niệm "khoảng cách". Trong phân nhóm, ta có hai loại khoảng cách: khoảng cách giữa các phần tử và khoảng cách giữa các nhóm.

Chúng ta có thể chia các phương pháp phân nhóm thành hai loại chính:

• Loại thứ nhất được gọi là phân nhóm theo cấp (hierarchical clustering). Quá trình phân nhóm được chía làm nhiều bước, sau mỗi bước, số nhóm lại thay đổi. Sự thay đổi này có thể xảy ra theo hai hướng:
  • theo hướng từ dưới lên (bottom-up) hay hướng ghép (agglomorative): sau mỗi bước số nhóm giảm đi bằng cách ghép các nhóm lại thành các nhóm lớn hơn, cho tới khi chỉ còn một nhóm duy nhất
  • theo hướng từ trên xuống (top-down) hay hướng tách (divisive): sau mỗi bước, số nhóm lại tăng lên bằng cách chia một nhóm nào đấy thành các nhóm nhỏ hơn, cho tới khi mỗi nhóm chỉ có một phần tử
• Loại thứ hai được gọi là phân hoạch (partitioning), trong đó các phần tử được chia thành một số `k` nhóm được định trước. Sự phân nhóm được bắt đầu bằng `k` nhóm nhỏ (mỗi nhóm chỉ có một hay một số ít phần tử). Sau đó các phần tử được đưa dần vào các nhóm nhỏ ấy cho đến khi hoàn tất.

Ngoài ra, các loại biểu đồ cũng rất thường được sử dụng phối hợp với các phương pháp phân nhóm.

Về mặt lý thuyết, khoảng cách giữa hai phần tử `mb(y)` và `mb(z)`, được ký hiệu `d(mb(y), mb(z))` phải có các tính chất cơ bản sau:

• `d(mb(y), mb(z))>=0`
• `d(mb(y), mb(y))=0`
• `d(mb(y), mb(z))=d(mb(z), mb(y))`

Xét một dữ liệu gổm `n` biến `(X_1, X_2, . . . , X_i, . . . , X_n`). Để đánh giá sự khác biệt giữa hai phần tử `mb(y)` và `mb(z)`, người ta thường sử dụng các loại khoảng cách sau:

• khoảng cách Euclid, cũng là loại khoảng cách thông dụng nhất, được định nghĩa như sau:

  `d(mb(y), mb(z))=[ (mb(y)-mb(z))^T (mb(y)-mb(z)) ]^(1/2) = [sum_(i=1)^n (x_(iy)-x_(iz))^2 ]^(1/2)`

  (1)

• khoảng cách Manhattan được xác định theo công thức:

  `d(mb(y,z))=sum_(i=1)^n |x_(iy)-x_(iz)|`

  (2)

• khoảng cách Minkowski được định nghĩa như sau:

  `d_m mb(y,z)=[sum_(i=1)^n |x_(iy)-x_(iz)|^m]^(1/m)`

  (3)

  trong đó `m` là cấp của khoảng cách.

Ta có thể xem khoảng cách Minkowski là trường hợp tổng quát vì khi `m=2`, khoảng cách Minkowski trở thành khoảng cách Euclid, còn khi `m=1` thì khoảng cách Minkowski trở thành khoảng cách Manhattan.

Thí dụ

> kc <- dist(tpdd[1:6,])
> kc
            Beef Braised Beef Canned Beef Heart Beef Roast Beef Steak
Beef Canned    161.22410                                             
Beef Heart     181.66147    21.32698                                 
Beef Roast      80.93429   242.05968  262.56658                      
Beef Steak      35.24202   196.42609  216.88451   45.76418           
Beef Tongue    135.75349    27.53979   47.22880  216.46997  170.96494

> as.matrix(kc)
             Beef Braised Beef Canned Beef Heart Beef Roast Beef Steak Beef Tongue
Beef Braised      0.00000   161.22410  181.66147   80.93429   35.24202   135.75349
Beef Canned     161.22410     0.00000   21.32698  242.05968  196.42609    27.53979
Beef Heart      181.66147    21.32698    0.00000  262.56658  216.88451    47.22880
Beef Roast       80.93429   242.05968  262.56658    0.00000   45.76418   216.46997
Beef Steak       35.24202   196.42609  216.88451   45.76418    0.00000   170.96494
Beef Tongue     135.75349    27.53979   47.22880  216.46997  170.96494     0.00000

> dist(tpdd[1:6,], method = "manhattan")
            Beef Braised Beef Canned Beef Heart Beef Roast Beef Steak
Beef Canned        189.1                                             
Beef Heart         217.3        34.2                                 
Beef Roast          98.6       287.7      315.9                      
Beef Steak          40.0       229.1      257.3       58.6           
Beef Tongue        153.1        44.2       72.4      243.5      191.1

Khoảng cách giữa hai nhóm A và B, ký hiệu `D(A, B)`, được xác định dựa theo khoảng cách giữa các phần tử ở hai nhóm. Nếu số phần tử của hai nhóm lần lượt là `p_A` và `p_B` thì ta có tổng cộng `p_Ap_B` khoảng cách giữa hai phần tử. Sau đây là một số phương pháp thông dụng để xác định khoảng cách giữa hai nhóm:

• Chọn khoảng cách nhỏ nhất :

  `D(A,B)=min{ d(mb(y)_u, mb(z)_v)}`(4)

• Chọn khoảng cách lớn nhất :

  `D(A,B)=max{ d(mb(y)_u, mb(z)_v)}`(5)

• Chọn khoảng cách trung bình :

  `D(A,B)=1/(p_Ap_B) sum_(u=1)^(p_A) sum_(v=1)^(p_B) d(mb(y)_u, mb(z)_v)`

  (1)

• Chọn khoảng cách giữa hai tâm (centroid), cũng là trị trung bình, của hai nhóm:

  `D(A,B)=d(bar mb(y)_A, bar mb(z)_B)`(7)

Trong các công thức (4), (5), và (6), `mb(y)_u` là phần tử thuộc nhóm A, `mb(z)_v` là phần tử thuộc nhóm B.

Như phần trên đã trình bày, phân nhóm theo cấp có thể tiến hành theo hai hướng là ghép và tách. Trong thực tế hướng ghép được sử dụng phổ biến hơn nên sẽ được trình bày ở đây.

Phân nhóm theo cấp hướng ghép được tiến hành qua nhiều bước. Đầu tiên mỗi phần tử được xếp vào một nhóm. Trong mỗi bước, ta tính toán khoảng cách giữa tất cả các nhóm rồi ghép hai nhóm gần nhau nhất để tạo nên một nhóm mới. Như vậy sau mỗi bước, số nhóm lại giảm đi. Quá trình tiếp tục cho đến khi chỉ còn một nhóm chứa toàn bộ phần tử của dữ liệu. Quá trình này được trình bày trên một biểu đổ hình cây (dendogram).

Để minh họa, ta sử dụng dữ liệu về thành phần dinh dưỡng ở thí dụ trên và dùng R để phân nhóm.

Trước hết dùng lệnh dist để tính khoảng cách của 27 phần tử trong dữ liệu rồi lưu kết quả vào biến kc:

 kc <- dist(tpdd)

Sau đó dùng lệnh hclust để phân nhóm. Khi sử dụng lệnh này ta lưu ý các điểm sau:

• Dữ liệu để đưa vào là khoảng cách thu được từ lệnh dist,
• Đối số method báo cho R biết phương pháp tính khoảng cách giữa các nhóm mà ta muốn sử dụng. Đối số này có các giá trị như sau: "single" (chọn khoảng cách nhỏ nhất), "complete" (chọn khoảng cách lớn nhất) là giá trị mặc định, "average" (chọn khoảng cách trung bình), "centroid" (chọn khoảng cách hai tâm), "median", "mcquitty", "ward.D", "ward.D2".

Vậy ta có thể sử dụng lệnh sau để phân nhóm:

 nhom <- hclust(kc)

Kết quả phân nhóm được lưu vào biến nhom và ta dùng biến này để vẽ biểu đồ hình cây như lệnh sau:

 plot(nhom, cex = 0.75, main = "Biểu đồ phân nhóm thực phẩm", col.axis = "red")

Và kết quả được thể hiện trên Hình 1.

Hình 1 Biểu đồ phân nhóm thực phẩm

Trục Height ở bên trái biểu đồ giúp ta hình dung được khoảng cách giữa các nhóm.

Biểu đồ vẽ theo kiểu này có thể giúp ta biết được thứ tự của quá trình ghép nhóm (thí dụ bắt đầu bằng ghép Beef Braised và Smoked Ham, kết thúc bằng Sardines Canned), tuy nhiên tên của các phần tử không được sắp xếp ngay ngắn. Nếu ta muốn biểu đồ sắp xếp đẹp hơn và không quan tâm đến thứ tự ghép nhóm, ta đưa vào lệnh plot đối số hang có giá trị âm như thí dụ sau:

 plot(nhom, cex = 0.75, col.axis = "red", hang = -1,
     main = "Biểu đồ phân nhóm thực phẩm")

Thì kết quả được thể hiện trên Hình 2

Hình 2 Biểu đồ phân nhóm thực phẩm

Chuẩn hóa số liệu

Từ bảng số liệu (Bảng 1), ta thấy giá trị các biến chênh lệch rất đáng kể. Do đó, khi ta sử dụng phương pháp Euclid để xác định khoảng cách giữa các phần tử, các biến có giá trị cao như energy sẽ ảnh hưởng mạnh hơn đến giá trị của khoảng cách. Trong trường hợp như vậy, hầu hết các tài liệu đều khuyến cáo chúng ta nên chuẩn hóa số liệu. R cung cấp cho ta lệnh scale để chuẩn hóa số liệu. Ta sẽ lặp lại sự phân nhóm với số liệu chuẩn hóa bằng đoạn lệnh sau:

 tpddch <- scale(tpdd)
 kcch <- dist(tpddch)
 nhomch <- hclust(kcch)
 plot(nhomch, cex = 0.75, main = "Biểu đồ phân nhóm thực phẩm", col.axis = "red")

Và ta có kết quả phân nhóm thể hiện trên Hình 3.

Hình 3 Biểu đồ phân nhóm thực phẩm với số liệu chuẩn hóa

Khi so sánh Hình 1 với Hình 3, ta thấy quá trình phân nhóm của hai dạng số liệu có sự khác biệt đáng kể.

Hình thành nhóm

Nếu ta muốn chia các phần tử của dữ liệu thành một số nhóm thì sử dụng lệnh cutree của R. Đối số thứ nhất của lệnh này là kết quả phân nhóm của lệnh hclust, thí dụ nhomch. Đối số thứ hai k là số nhóm mà ta muốn tạo. Thí dụ:

> cutree(nhomch, k = 4)
       Beef Braised         Beef Canned          Beef Heart          Beef Roast 
                  1                   2                   2                   1 
         Beef Steak         Beef Tongue      Bluefish Baked     Chicken Broiled 
                  1                   2                   2                   2 
     Chicken Canned        Clams Canned           Clams Raw     Crabmeat Canned 
                  2                   3                   3                   2 
      Haddock Fried           Hamburger      Lamb Leg Roast Lamb Shoulder Roast 
                  2                   2                   2                   1 
   Mackerel Broiled     Mackerel Canned         Perch Fried          Pork Roast 
                  2                   2                   2                   1 
      Pork Simmered       Salmon Canned     Sardines Canned       Shrimp Canned 
                  1                   2                   4                   2 
         Smoked Ham         Tuna Canned         Veal Cutlet 
                  1                   2                   2 

Qua đó, ta thấy nhóm 1 có 7 phần tử, nhóm 2 có 17 phần tử, nhóm 3 có 2 phần tử và nhóm 4 chỉ có 1 phần tử.

Nếu ta muốn thể hiện sự phân nhóm này dưới dạng biểu đồ hình cây, ta sử dụng lệnh rect.hclust và lưu ý các đối số sau:

• dữ liệu đưa vào là kết quả của lệnh hclust,
• k là số nhóm muốn chia,
• h là khoảng cách giới hạn để phân nhóm,
• lưu ý là chỉ sử dụng một trong hai đối số k và h,
• border là màu của đường bao các nhóm.

Thí dụ nếu ta dùng dòng lệnh sau :

 rect.hclust(nhomch, k = 4, border = c("red", "blue", "green", "orange"))

Thì ta có kết quả trên Hình 4.

Hình 4 Biểu đồ phân nhóm thực phẩm với 4 nhóm

Trong phân hoạch (partitioning), số nhóm `k` được định trước. Sự phân nhóm được bắt đầu bằng `k` nhóm nhỏ (mỗi nhóm chỉ có một hay một số ít phần tử). Sau đó các phần tử được đưa dần vào các nhóm nhỏ ấy cho đến khi hoàn tất. Phương pháp phân hoạch phổ biến nhất là k-tâm (k-means) nên ta khảo sát phương pháp ấy trong phần này.

Trong bước 1, ta sẽ chọn ra `k` phần tử làm tâm. Có một số phương pháp chọn tâm khác nhau: chọn ngẫu nhiên, chọn `k` phần tử đầu tiên, chọn `k` phần tử cách nhau xa nhất, chọn `k` phần tử sao cho chúng hình thành mạng lưới cho sẵn, ... Cũng có phần mềm, như R, cho phép chọn một số lần, sau đó so sánh những lần ấy và chọn ra phương án tốt nhất.

Trong bước 2, ta sẽ ghép các phần tử vào nhóm có tâm gần nhất dựa theo khoảng cách Euclid. Sau mỗi lần ghép, tâm của nhóm sẽ được tính toán lại. Quá trình ghép này được tiến hành cho tới khi tất cả phần tử được ghép vào các nhóm.

Trong bước 3, ta sẽ so sánh khoảng cách `d` của phần tử `j` đến tâm của nhóm chứa phần tử ấy và khoảng cách `d_k` của phần tử `j` ấy đến các tâm khác. Nếu có một giá trị `d_k` nào đó bé hơn `d`, ta sẽ chuyển phần tử `j` ấy đến nhóm tương ứng. Quá trình này được thực hiện cho toàn bộ các phần tử của dữ liệu.

Ta lặp lại bước 3 một số lần cho đến khi không có phần tử nào được chuyển hay cho đến khi số lần lặp đạt một giá trị định trước.

Trong R, sự phân hoạch theo phương pháp k-tâm được thực hiện bằng lệnh kmeans theo đó việc chọn tâm ở bước 1 được thực hiện một cách ngẫu nhiên. Ta cần lưu ý các đối số sau:

• centers : số tâm `k`, cũng là số nhóm mà ta muốn phân hoạch,
• nstart : số lần chọn tâm ở bước 1, giá trị mặc định là 1,
• iter.max : số lần lặp lại bước 3 cao nhất, giá trị mặc định là 10,
• algorithm : thuật toán sử dụng trong sắp xếp phần tử vào các nhóm với các giá trị "Hartigan-Wong" (mặc định), "MacQueen", "Lloyd", "Forgy" (thực ra hai thuật toán "Lloyd" và "Forgy" giống nhau).

Thí dụ ta sử dụng phương pháp k-tâm để chia 27 loại thực phẩm ở Bảng 1 làm 4 nhóm thì ta có:

> kmeans(tpddch, centers = 4, nstart = 20)
K-means clustering with 4 clusters of sizes 3, 8, 2, 14

Cluster means:
      energy     protein        fat    calcium        iron
1 -0.5507554 -0.15680015 -0.5165495  2.3541419 -0.48916187
2  1.3286287 -0.05880006  1.3674579 -0.4512501  0.03833458
3 -1.4811842 -2.35200232 -1.1087718  0.4361807  2.27092763
4 -0.4295996  0.40320040 -0.5123193 -0.3089133 -0.24150330

Clustering vector:
       Beef Braised         Beef Canned          Beef Heart          Beef Roast 
                  2                   4                   4                   2 
         Beef Steak         Beef Tongue      Bluefish Baked     Chicken Broiled 
                  2                   4                   4                   4 
     Chicken Canned        Clams Canned           Clams Raw     Crabmeat Canned 
                  4                   3                   3                   4 
      Haddock Fried           Hamburger      Lamb Leg Roast Lamb Shoulder Roast 
                  4                   4                   2                   2 
   Mackerel Broiled     Mackerel Canned         Perch Fried          Pork Roast 
                  4                   1                   4                   2 
      Pork Simmered       Salmon Canned     Sardines Canned       Shrimp Canned 
                  2                   1                   1                   4 
         Smoked Ham         Tuna Canned         Veal Cutlet 
                  2                   4                   4 

Within cluster sum of squares by cluster:
[1]  6.9584784  4.3364978  0.5626097 28.9724028
 (between_SS / total_SS =  68.6 %)

Available components:

[1] "cluster"      "centers"      "totss"        "withinss"     "tot.withinss"
[6] "betweenss"    "size"         "iter"         "ifault"

Bảng kết quả trên cho ta biết các chi tiết của bốn nhóm: các phần tử của bốn nhóm, tâm của bốn nhóm, ...

Ta thấy kết quả phân nhóm bằng hai phương pháp ghép và k-tâm không giống nhau. Một trong các lý do là trong phương pháp ghép, các phần từ đã được ghép nhóm thì không thể chuyển sang nhóm khác, nhưng trong phương pháp k-tâm thì điều này có thể xẩy ra (trong bước 3).

Để có thể trình bày kết quả phân nhóm bằng biểu đồ, ta sử dụng lệnh clusplot của phụ kiện cluster. Lệnh này có nhiều đối số, nhưng ta cần quan tâm đến hai đối số sau:

• dữ liệu để vẽ là bảng dữ liệu,
• clus : là thành phần cluster của kết quả xử lý bằng lệnh kmeans.

Thí dụ ta sử dụng đoạn lệnh sau :

 library(cluster) 
 nhkm <- kmeans(tpddch, centers = 4, nstart = 20)
 clusplot(tpddch, clus = nhkm$cluster, color = TRUE, shade = TRUE, labels = 2,
         lines = 0, main = "Biểu đồ phân nhóm thực phẩm", sub = "",  cex = 0.7)

Ta thu được Hình 5.

Hình 5 Biểu đồ phân nhóm thực phẩm với 4 nhóm bằng phương pháp k-tâm

Trên Hình 5, các loại thực phẩm được biểu diễn trên hệ trục gồm hai thành tố chính (Component 1 và Component 2). Mỗi nhóm được bao bọc trong một ellip.