介绍

聚类技术在当今有着广泛的应用和重要性。随着数据量的增长和计算机处理能力的提升，这种重要性也日益增加。聚类应用广泛应用于人工智能、模式识别、经济学、生态学、精神病学和营销等各个领域。

聚类技术的核心目的是将一组实体划分为不同的组，称为聚类。这些组在成员的相似性方面可能是一致的。顾名思义，基于代表的聚类技术使用某种形式的表示来表示每个聚类。因此，每个组都有一个成员来代表它。使用这种聚类技术背后的动机是，除了降低算法的成本之外，使用代表使过程更容易理解。为了使用基于代表的聚类策略，必须做出许多决定。例如，在聚类的数量和聚类的内部凝聚力之间存在明显的权衡。如果聚类很少，内部凝聚力往往很小。否则，大量的聚类使它们非常接近，因此相邻组之间几乎没有差异。另一个决定是聚类应该是相互排斥的还是不排斥的，也就是说，一个实体是否可以同时存在于多个聚类中。

要讨论的技术

在这项工作中，我们重点关注 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 月。