介紹

聚類技術在當今有著廣泛的應用和重要性。隨著資料量的增長和計算機處理能力的提升，這種重要性也日益增加。聚類應用廣泛應用於人工智慧、模式識別、經濟學、生態學、精神病學和營銷等各個領域。

聚類技術的核心目的是將一組實體劃分為不同的組，稱為聚類。這些組在成員的相似性方面可能是一致的。顧名思義，基於代表的聚類技術使用某種形式的表示來表示每個聚類。因此，每個組都有一個成員來代表它。使用這種聚類技術背後的動機是，除了降低演算法的成本之外，使用代表使過程更容易理解。為了使用基於代表的聚類策略，必須做出許多決定。例如，在聚類的數量和聚類的內部凝聚力之間存在明顯的權衡。如果聚類很少，內部凝聚力往往很小。否則，大量的聚類使它們非常接近，因此相鄰組之間幾乎沒有差異。另一個決定是聚類應該是相互排斥的還是不排斥的，也就是說，一個實體是否可以同時存在於多個聚類中。

要討論的技術

在這項工作中，我們重點關注 K-Means 演算法，它可能是最流行的基於代表的聚類技術。在第一節中，我們簡要介紹了演算法的工作原理。

演算法

K-Means 是一種用於聚類分析的簡單學習演算法。K-Means 演算法的目標是找到將n個實體劃分為k個組的最佳劃分，以便最小化組成員與其對應質心（組的代表）之間的總距離。形式上，目標是將n個實體劃分為k個集合S_i, i=1, 2, ..., k，以最小化叢集內平方和 (WCSS)，定義為

$\sum _{j=1}^{k}\sum _{i=1}^{n}\parallel x_{i}^{j}-c_{j}\parallel ^{2}$

其中項 $\parallel x_{i}^{j}-c_{j}\parallel$ 提供了一個實體點與聚類質心之間的距離。

下面描述的最常用演算法使用迭代細化方法，遵循以下步驟

定義初始組的質心。這可以透過不同的策略來完成。一種非常常見的方法是為所有組的質心分配隨機值。另一種方法是使用K個不同實體的值作為質心。
將每個實體分配到具有最接近質心的聚類。為了找到具有最相似質心的聚類，演算法必須計算所有實體與每個質心之間的距離。
重新計算質心的值。質心欄位的值會更新，取為屬於該聚類的實體屬性值的平均值。
迭代地重複步驟 2 和 3，直到實體不再能夠更改組。

K-Means 是一種貪婪的、計算效率高的技術，是使用最廣泛的基於代表的聚類演算法。K-Means 演算法的虛擬碼如下所示。

請注意，虛擬碼的最後一行應該是

while $changed=true{\text{ and }}iter\leq MaxIters$ ; 或者
until $changed=false{\text{ or }}iter>MaxIters$ .

實施

為了在 R 中使用 K-Means 演算法，必須安裝stats包。此包包含一個函式，該函式根據不同的演算法執行 K-Mean 過程。這些演算法描述如下

勞埃德

對於任何給定的 k 箇中心集 Z，對於 Z 中的每個中心 z，令 V(z) 表示其鄰域。也就是說，對於哪些資料點 z 是最近鄰。勞埃德演算法的每個階段將每個中心點 z 移動到 V(z) 的質心，然後透過重新計算每個點與其最近中心的距離來更新 V(z)。這些步驟重複，直到收斂。請注意，勞埃德演算法可能會陷入區域性最小解中，而區域性最小解距離最優解很遠。出於這個原因，人們通常會考慮基於區域性搜尋的啟發式方法，其中中心在現有解決方案中被交換進出（通常是隨機的）。這種交換隻有在它降低了平均失真時才會被接受，否則會被忽略。

福吉

福吉演算法是一個簡單的交替最小二乘演算法，包括以下步驟

初始化碼本向量。（假設在處理給定的訓練案例時，N 個案例之前已分配給獲勝的碼本向量。）
重複以下兩個步驟，直到收斂
1. 讀取資料，將每個案例分配到最接近的（使用歐幾里得距離）碼本向量。
2. 用分配給它的案例的均值替換每個碼本向量。

麥克昆

該演算法透過反覆將所有聚類中心移動到其各自的沃羅諾伊集的均值來工作。

哈蒂根和黃

對於 n 個物體，每個物體上有 p 個變數，x(i,j) 為 i = 1,2,...,n; j = 1,2,...,p; K-means 將每個物體分配到 K 個組或聚類中的一個，以最小化叢集內平方和

Sum(k)=\sum _{i=0}^{n}\sum _{j=0}^{p}{(x(i,j)-{\overline {x(k,j)}})^{2}}

其中

{\overline {x(k,j)}}

是第 K 組所有元素的第 j 個變數的平均值。

除了資料矩陣外，還需要一個 K x p 矩陣，用於給出 K 個聚類的初始聚類中心。然後將物件最初分配到具有最接近聚類中心的聚類中。給定初始分配，該過程是透過將點從一個聚類移動到另一個聚類來迭代地搜尋具有區域性最優簇內平方和的 K 分割槽。

stats 包提供的 K-Means 函式可以用如下方式使用：

kmeans(x, centers, iter.max = 10, nstart = 1, algorithm = c("Hartigan-Wong", "Lloyd", "Forgy", "MacQueen"))

其中引數為：

x: 資料的數值矩陣，或者可以強制轉換為這種矩陣的物件（例如數值向量或所有列都是數值的 data frame）。
centers: 聚類數量或一組初始（不同）聚類中心。如果是一個數字，則選擇 x 中隨機的一組（不同）行作為初始中心。
iter.max: 允許的最大迭代次數。
nstart: 如果 centers 是一個數字，nstart 給出了應選擇的隨機集的數量。
algorithm: 要使用的演算法。它應該是 "Hartigan-Wong"、"Lloyd"、"Forgy" 或 "MacQueen" 之一。如果沒有指定演算法，則預設情況下使用 Hartigan 和 Wong 的演算法。

如果一切順利，將返回一個 kmeans 類的物件。該物件具有以下元件：

cluster: 一個整數向量，指示將每個點分配到的聚類。
centers: 一個聚類中心的矩陣。
whithnss: 每個聚類的簇內平方和。
size: 每個聚類中的點數。

檢視

實際上，有兩種方法可以檢視 K-Means 使用的結果。它們都使用函式應用返回的 K-means 類的物件。

第一種方法是繪製該物件，建立一個表示資料的圖表。因此，如果將 N 個物件劃分為 K 個聚類，則圖表必須包含代表物件的 N 個點，並且這些點必須用 K 種不同的顏色著色，每種顏色代表一組聚類。例如，給定物件 km，它是函式 kmeans 應用的結果，為了繪製該物件，只需要：

plot(km)

檢視 K-Means 應用結果的第二種方法是簡單地列印 kmeans 類的物件的元件。例如，給定上一示例中相同的物件 km，可以使用以下方法列印其元件：

print(km)

示例

假設我們有四個物件，每個物件都有兩個屬性（或特徵），如以下表格所示。

表 1: *表示物件的表格*
物件	屬性 X	屬性 Y
A	1	1
B	2	1
C	4	3
D	5	4

我們的目標是根據它們的兩個特徵將這些物件分成 K=2 組。K-Means 函式可以用來定義組，如下所示：

# prepare matrix of data
cells <- c(1, 1, 2, 1, 4, 3, 5, 4)
rnames <- c("A", "B", "C", "D")
cnames <- c("X", "Y")
x <- matrix(cells, nrow=4, ncol=2, byrow=TRUE, dimnames=list(rnames, cnames))

# run K-Means
km <- kmeans(x, 2, 15)

# print components of km
print(km)

# plot clusters
plot(x, col = km$cluster)
# plot centers
points(km$centers, col = 1:2, pch = 8)

列印 km 元件的結果

K-means clustering with 2 clusters of sizes 2, 2

Cluster means:
    X   Y
1 1.5 1.0

2 4.5 3.5

Clustering vector:
A B C D
1 1 2 2

Within cluster sum of squares by cluster:
[1] 0.5 1.0

Available components:
[1] "cluster"  "centers"  "withinss" "size"

繪圖結果

案例研究

在本節中，我們將說明一個使用 K-Means 的案例研究。

場景

國家之間的差異遠遠超出了物質和領土方面。因此，出於分析目的，將國家根據其某些屬性劃分為群體是很常見的。傳統的分類將國家劃分為發達國家、新興國家和欠發達國家。在這個劃分中，可以考慮許多標準，例如人均收入和預期壽命。

k-means 演算法是一種根據實體屬性的相似性對實體進行分組的技術。由於當前問題是將國家劃分為相似的組，因此可以將 K-means 應用於此任務。

讓我們考慮一個需要將國家分類為上述三種類型的場景：發達國家、新興國家和欠發達國家。為了分析它們的相似性並將它們分配到組中，應考慮以下屬性：

人均收入；
識字率；
嬰兒死亡率；
預期壽命；

輸入資料

輸入資料是一個表，包含每個考慮國家的屬性的數值。該表包含 19 行，代表國家，以及 5 列（包括包含國家名稱的第一列），代表屬性。該表可以從電子表格或文字檔案載入。為了保持聚類的語義，本示例中使用的所有值都是國家/地區的真實統計資料。

表 2: *輸入資料*
國家	人均收入	識字率	嬰兒死亡率	預期壽命
巴西	10326	90	23.6	75.4
德國	39650	99	4.08	79.4
莫三比克	830	38.7	95.9	42.1
澳大利亞	43163	99	4.57	81.2
中國	5300	90.9	23	73
阿根廷	13308	97.2	13.4	75.3
英國	34105	99	5.01	79.4
南非	10600	82.4	44.8	49.3
尚比亞	1000	68	92.7	42.4
奈米比亞	5249	85	42.3	52.9
喬治亞	4200	100	17.36	71
巴基斯坦	3320	49.9	67.5	65.5
印度	2972	61	55	64.7
土耳其	12888	88.7	27.5	71.8
瑞典	34735	99	3.2	80.9
立陶宛	19730	99.6	8.5	73
希臘	36983	96	5.34	79.5
義大利	26760	98.5	5.94	80
日本	34099	99	3.2	82.6

執行

"kmeans" 函式可以用來定義國家組，如下所示：

# import data (assume that all data in "data.txt" is stored as comma separated values)
x <- read.csv("data.txt", header=TRUE, row.names=1)

# run K-Means
km <- kmeans(x, 3, 15)
 
# print components of km
print(km)

# plot clusters
plot(x, col = km$cluster)
# plot centers
points(km$centers, col = 1:2, pch = 8)

"kmeans" 的第二個引數的值被傳遞為數字 3，因為我們要得到三個國家組。

輸出

下面顯示了列印函式應用返回的類元件的結果

K-means clustering with 3 clusters of sizes 5, 7, 7

Cluster means:
  Per_capita_income Literacy Infant_mortality Life_expectancy
1         13370.400    91.58        23.560000        68.96000
2          3267.286    70.50        56.251429        58.80000
3         35642.143    98.50         4.477143        80.42857

Clustering vector:
        Brazil        Germany     Mozambique      Australia          China
             1              3              2              3              2
     Argentina United_Kingdom   South_Africa         Zambia        Namibia
             1              3              1              2              2
       Georgia       Pakistan          India        Turkey         Sweden
             2              2              2              1              3
     Lithuania         Greece          Italy          Japan
             1              3              3              3

Within cluster sum of squares by cluster:
[1]  57626083  20109876 158883600

Available components:
[1] "cluster"  "centers"  "withinss" "size"

下面顯示了繪製函式應用返回的類的結果

data= 5.0 3.5 1.3 0.3 -1 5.5 2.6 4.4 1.2 0 6.7 3.1 5.6 2.4 1 5.0 3.3 1.4 0.2 -1 5.9 3.0 5.1 1.8 1 5.8 2.6 4.0 1.2 0

k-means 的實現生成了三個相對同質的聚類，包含 5 個、7 個和 7 個國家。分析聚類中心，我們可以將每個組與三種國家/地區類別中的每一種聯絡起來：

由德國、英國、希臘、澳大利亞、日本、義大利和瑞典組成的聚類具有最高的人均收入、識字率和預期壽命以及最低的嬰兒死亡率。因此，這個聚類代表了發達國家。
由中國、莫三比克、喬治亞、巴基斯坦、印度、尚比亞和奈米比亞組成的聚類在所有屬性方面的值都最低，因此代表了欠發達國家。
由其他國家組成的聚類，巴西、南非、土耳其、阿根廷和立陶宛，代表了新興國家組。

為了提高 K-Means 進行的分類質量，將得到的組劃分與 2009 年 10 月 5 日釋出的聯合國開發計劃署人類發展報告中包含的人類發展指數對所有國家進行的分類進行了比較，該報告是根據 2007 年的資料編制的。人類發展指數 (HDI) 是衡量福祉的比較指標，它考慮了預期壽命、識字率和教育等方面。與 HDI 的劃分相比，只有四個國家被歸類到不同的組：奈米比亞、喬治亞、巴基斯坦和印度。這些國家應該被歸類為“發展中國家”，而不是“欠發達國家”組。

參考文獻

Meira Jr., W.; Zaki, M. 資料探勘演算法基礎。 [1]
Cluster R 包。 [2]
J. B. MacQueen. 1967. 多元觀察分類和分析的一些方法，第五屆伯克利數學統計和機率研討會論文集，伯克利，加州大學出版社。
Hartigan, J.A. (1975)，聚類演算法，紐約：John Wiley & Sons，Inc。
A. K. Jain，M.N. Murthy 和 P.J. Flynn，資料聚類：綜述，ACM 計算機評論，1999 年 11 月。