2.4 聚类
聚类就是对物理对象或抽象对象的集合进行分组的过程，所生成的组称为簇（cluster），簇是数据对象的集合。簇内部任意两个对象之间应该具有较高的相似度，而隶属于不同簇的两个对象之间应该具有较高的相异度。相异度一般根据描述对象的属性值进行计算，最常采用的度量指标是对象间的距离。
Weka专门使用Cluster标签页来处理聚类问题，如图2.79所示。
图2.79 Cluster标签页
2.4.1 Cluster标签页的操作
在Cluster标签页中，选择和配置对象的过程与Preprocess和Classify标签页类似，下面对操作方法进行说明。
Cluster标签页的最上部是Clusterer（聚类器）选项组，其中包括Choose按钮和聚类器文本框。按钮用于选择Weka提供的聚类器，文本框用于显示当前选择的聚类器的名称和参数。单击文本框，会弹出一个通用对象编辑器对话框，与过滤器和分类器的对象编辑器对话框的功能一样，可以用来对当前聚类器进行设置。右击（或在按住Alt键和Shift键的同时单击）聚类器文本框，会弹出一个快捷菜单，选择Show Properties菜单项可以打开通用对象编辑器对话框，选择Copy configuration to clipboard菜单项可以将当前的设置字符串复制到剪贴板，选择Edit configuration菜单项可以让用户修改设置，选择Enter configuration菜单项可以直接输入设置字符串，功能与过滤器和分类器的相似。
Cluster标签页的左部是Clusterer mode（聚类器模式）选项组。该选项组用于设置聚类模式及如何评估结果的选项，最终将设置的选项应用到当前选择的聚类器中。聚类模式如下。
（1）Use training set（使用训练集）：直接将训练集实例用于测试。
（2）Supplied test set（提供测试集）：从一个文件中加载一组测试实例。单击Set按钮会弹出一个对话框，允许用户选择测试的实例文件。
（3）Percentage split（按比例分割）：在数据集中，取出特定百分比的数据来作为训练数据，其余数据作为测试数据，评价聚类器的性能。取出的数据量取决于用户在“%”文本框中输入的值，默认取出66%的数据作为训练集。
（4）Classes to clusters evaluation（类别作为簇的评估准则）：比较所选择的簇与预先指定的数据类别的匹配程度。该选项下方有一个下拉列表框，其操作与在Classify标签页中选择类别属性的操作一样。
（5）Store clusters for visualization（为可视化保存簇）：选中此复选框，在训练完成后，保存簇以供可视化使用。当处理很大的数据集遇到内存不足的问题时，取消选中此选项可能会有帮助。默认为选中。
通常情况下，在聚类过程中可以设置忽略一些数据属性。单击Ignore attributes（忽略属性）按钮，会弹出一个小窗口，让用户选择要忽略哪些属性。单击窗口中的属性使其高亮，按住Shift键可选择连续范围内的属性，按住Ctrl键可选择或反选单个属性。要取消选择，可单击Cancel按钮；要激活选择，可单击Select按钮。下一次运行聚类算法时，会忽略选择的属性。
FilteredClusterer元聚类器是一种特殊的聚类器，它为用户提供在聚类器学习之前先应用过滤器的方式。使用这种方法，当不需要在Preprocess标签页中手动应用过滤器时，可以在学习的同时进行数据处理，这在需要使用不同的过滤器设置方式时十分有用。
和Classify标签页类似，Cluster标签页中也有Start按钮和Stop按钮。单击Start按钮开始学习，学习结果会显示在Clusterer output（聚类器输出）区域，并在Result list（结果列表）区域创建一个新条目。右击该条目，也会弹出快捷菜单，不同的是这里只显示两个可视化菜单项——Visualize cluster assignments（可视化簇分配）和Visualize tree（可视化树），后者在不可用时会变灰。另外，Visualize cluster assignments窗口中有一个Save按钮，用于将数据保存为ARFF文件，用户可以查看哪些样本被分配到哪个簇中。
2.4.2 聚类算法介绍
本节介绍三种简单但重要的聚类算法。k均值算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，试图划分k（用户指定个数）个簇。k均值算法不适合处理标称型属性，对于数值型属性的聚类效果较好。EM（Expectation Maximization，期望最大化）算法是k均值算法的一种扩展，它不把对象分配给一个确定的簇，而是根据对象与簇之间的隶属关系发生的概率来分配对象。EM算法是解决数据缺失问题的一种出色算法。DBSCAN算法是一种基于密度的聚类算法，簇的个数由算法自动确定。其将低密度区域中的点视为噪声而忽略，因此DBSCAN不产生完全聚类。
1．k均值算法
k均值算法比较简单，其中k表示用户指定的所期望的簇个数。其基本算法是，首先选择k个初始质心，将每个数据点指派给最近的质心，指派给一个质心的全部点形成一个簇；然后根据指派给簇的点，更新每个簇的质心；重复指派及更新步骤，直到簇不再发生变化，即质心不再发生变化为止。算法的伪代码如算法2.7所示。
算法2.7 基本k均值算法
选择k个点作为初始质心
repeat
将每个点指派给最近的质心，形成k个簇
重新计算每个簇的质心
until 质心不再发生变化
相似度的计算可采用欧氏距离或曼哈顿距离。其中，欧氏距离是指两点之间的欧氏空间直线距离，而曼哈顿距离是在欧氏空间固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。
考虑邻近度为欧氏距离的数据，通常使用误差的平方和（Sum of the Squared Error，SSE）作为度量聚类质量的目标函数。SSE定义如下：
其中，dist表示两个对象之间的标准欧氏距离（L2）；ci为簇i的质心；x为属于簇i的数据点的集合。
Weka提供采用k均值算法进行聚类的SimpleKMeans。簇的数目由参数numClusters指定，用户可以选择欧氏距离或曼哈顿距离等作为距离度量。如果使用曼哈顿距离，该算法实际使用k中位数算法，而非k均值算法，质心基于中位数而不是均值以最小化簇内的距离函数。
2．EM算法
EM算法是在概率模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量。EM算法经常用于机器学习和数据聚类领域。
EM算法使用两个步骤交替进行计算。第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；第二步是最大化（M），最大化在E步上求得的最大似然值来计算参数的值。然后将M步上找到的参数估计值用于下一个E步计算中，这个过程不断交替进行直至收敛。
通过交替使用这两个步骤，EM算法逐步改进模型的参数，使参数和训练样本的似然概率逐渐增大，最后终止于一个极大点。
EM算法的主要目的是提供一个简单的迭代算法计算后验密度函数，它的最大优点是简单和稳定，但容易陷入局部最优。
Weka提供简单的EM聚类算法。EM为每个实例分配一个概率分布，表明它属于每一个簇的概率。EM能用交叉验证确定创建多少个簇，或者指定产生多少个簇的先验。
3．DBSCAN算法
基于密度的聚类寻找由低密度区域分割的高密度区域。DBSCAN是一种简单、有效的基于密度的聚类算法，它诠释了基于密度的聚类算法的很多重要概念。首先定义几个术语。
（1）核心点（core point）：核心点位于基于密度的簇的内部。点的邻域由距离函数和用户指定的距离ε（Weka使用epsilon选项来指定该值）决定。核心点定义是，该点给定邻域内的点的个数超过给定的阈值MinPts，MinPts由用户指定。
（2）边界点（border point）：边界点不是核心点，但落在某个核心点的邻域内。
（3）噪声点（noise point）：既不是核心点又不是边界点的点称为噪声点。
DBSCAN算法的伪代码如算法2.8所示。任意两个足够靠近（相互之间的距离在ε之内）的核心点属于同一个簇。同样，任何与核心点足够靠近的边界点也放到与核心点相同的簇中。如果一个边界点靠近不同簇的核心点，则需要评判是否丢弃噪声点。
算法2.8 DBSCAN算法
将所有点标记为核心点、边界点或噪声点
删除噪声点
为距离在ε之内的所有核心点之间添加一条连接边
每组连通的核心点形成一个簇
将每个边界点指派给一个与之关联的核心点的簇
DBSCAN使用基于密度簇的定义，是相对抗噪声的，并且能够处理任意形状和大小的簇。因此，DBSCAN算法能够发现k均值算法不能发现的簇。但是，DBSCAN在处理簇密度变化太大或高维数据时，会遇到密度定义更加困难的问题。
Weka提供DBSCAN算法，它使用欧氏距离度量以确定哪些实例属于哪个簇。与k均值算法不同，DBSCAN算法可以自动确定簇的数目，发现任意形状的簇，并纳入离群概念。簇定义为至少包含最小数量的点，簇内每对点之间的距离必须落在用户指定的距离（ε）之内，或者由簇中一系列的点连接为链，位于链中的每个点和下一个点的距离必须落在ε内。ε值越小，产生的簇越密集，因为实例之间必须更接近才能同属于一个簇。根据设置的ε值和最小的簇大小，可能有某些实例不属于任何簇，可将这些实例视为离群值。
2.4.3 手把手教你用
1．使用SimpleKMeans算法
k均值算法是一种常用的聚类分析算法。该算法接受输入值k，然后将n个数据对象划分为k个簇，使得获得的簇满足如下条件：同一簇中的对象相似度较高，而不同簇中的对象相似度较小。
SimpleKMeans算法使用k均值算法。簇的数量由一个参数指定，用户可以选择欧氏距离或曼哈顿距离度量。如果使用后者，该算法实际上是使用k-medians替代k-means，并且中心也是基于中位数而不是均值，以尽量使簇内的距离函数最小。
下面对天气数据集使用SimpleKMeans算法。首先在Preprocess标签页中加载weather.numeric.arff文件，然后切换至Cluster标签页，选择SimpleKMeans算法，保持默认参数，即2个簇以及欧氏距离。单击Ignore attributes按钮，选择play属性为忽略属性，单击Select按钮确认选择。单击Start按钮运行聚类算法，结果如下：
=== Run information ===
Scheme: weka.clusterers.SimpleKMeans -init 0 -max-candidates 100 -
periodic-pruning 10000 -min-density 2.0 -t1 -1.25 -t2 -1.0 -N 2 -A
"weka.core.EuclideanDistance -R first-last" -I 500 -num-slots 1 -S 10
Relation: weather
Instances: 14
Attributes: 5
outlook
temperature
humidity
windy
Ignored:
play
Test mode: evaluate on training data
=== Clustering model (full training set) ===
kMeans
======
Number of iterations: 3
Within cluster sum of squared errors: 11.237456311387234
Initial starting points (random):
Cluster 0: rainy,75,80, FALSE
Cluster 1: overcast,64,65, TRUE
Missing values globally replaced with mean/mode
Final cluster centroids:
Cluster#
Attribute Full Data 0 1
(14.0) (9.0) (5.0)
==============================================
outlook sunny sunny overcast
temperature 73.5714 75.8889 69.4
humidity 81.6429 84.1111 77.2
windy FALSE FALSE TRUE
Time taken to build model (full training data) : 0 seconds
=== Model and evaluation on training set ===
Clustered Instances
0 9 ( 64%)
1 5 ( 36%)
可以看到，聚类结果以表格形式显示：行对应属性名，列对应簇中心。在开始的一个额外簇（Full Data）显示整个数据集。每个簇拥有的实例数量显示在所在列的顶部括号内。每一个表项如果是数值型属性，则显示平均值；如果是标称型属性，则显示簇所在列对应的属性标签。用户可以选择显示数值型属性标准差和标称型属性值的频率计数，只要在通用对象编辑器中将displayStdDevs参数设置为true即可。输出结果底部显示应用所学聚类模型的结果。本例中显示了分配给每个簇的训练实例数目及百分比，与表格中每一列顶部括号内的数字相同。使用不同的聚类模式，显示输出会有所不同。
2．使用EM算法
EM算法也是常用的聚类算法。下面使用EM算法对相同的数据集进行聚类分析。
在Cluster标签页中单击Choose按钮选择EM聚类器，单击Choose按钮右边的文本框，将numClusters设置为2，即簇数为2，其他参数保持默认值。确保play属性为忽略属性。单击Start按钮启动聚类训练，得到结果如下：
=== Run information ===
Scheme: weka.clusterers.EM -I 100 -N 2 -X 10 -max -1 -ll-cv 1.0E-6 -ll-
iter 1.0E-6 -M 1.0E-6 -K 10 -num-slots 1 -S 100
Relation: weather
Instances: 14
Attributes: 5
outlook
temperature
humidity
windy
Ignored:
play
Test mode: evaluate on training data
=== Clustering model (full training set) ===
EM
==
Number of clusters: 2
Number of iterations performed: 18
Cluster
Attribute 0 1
(0.28) (0.72)
==============================
outlook
sunny 2.9551 4.0449
overcast 2.9876 3.0124
rainy 1.0009 5.9991
[total] 6.9437 13.0563
temperature
mean 82.2771 70.1574
std. dev. 1.9212 3.6061
humidity
mean 83.9571 80.7353
std. dev. 5.5038 11.043
windy
TRUE 1.9553 6.0447
FALSE 3.9884 6.0116
[total] 5.9437 12.0563
Time taken to build model (full training data) : 0.01 seconds
=== Model and evaluation on training set ===
Clustered Instances
0 4 ( 29%)
1 10 ( 71%)
Log likelihood: -8.36599
可以看到，不同于SimpleKMeans算法的输出，在表头的每个簇的下方并没有显示实例数量，只是在表头括号内显示其先验概率。表中单元格显示数值型属性正态分布的参数或标称型属性值的频率计数，这里，小数数值揭示了由EM算法产生簇的“软”特性，任何实例都可以在若干个簇之间进行分割。输出的最后显示了模型的对数似然值，该值根据训练数据得到。输出还显示了分配给每个簇的实例数量，这是将经过学习后的模型作为分类器应用到数据后所得的结果。
3．使用DBSCAN和OPTICS算法
DBSCAN和OPTICS都是聚类算法。
DBSCAN使用欧氏距离度量，以确定哪些实例属于同一个簇。但是，不同于k均值算法，DBSCAN可以自动确定簇的数量，发现任意形状的簇并引入离群值的概念。它将簇定义为至少包含有最小数目点的集合，其中每个点对彼此之间的距离小于用户指定的最小距离（ε，Weka中为epsilon），或者由簇内的一系列的点连接为链，链中的每个点到下一个点的距离小于ε。ε的值越小，产生的簇越密集，这是因为实例必须靠得更紧密，彼此才能同属于一个簇。根据设定的ε值和簇大小的最小值（Weka中为minPoints），有可能存在某些不属于任何簇的实例，这些实例称为离群值。
OPTICS算法是DBSCAN算法在层次聚类方面的扩展。OPTICS规定了实例的顺序，对这些实例进行二维可视化，可以揭示簇的层次结构。排序过程根据距离度量，对实例排序并放入有序列表中。此外，它会标记每个相邻实例对的“距离可达性”，这是指允许一个相邻实例对属于同一簇的最小ε值。当根据距离可达性顺序绘出散点图后，能明显看出簇的分界。由于簇内实例距离最近邻居的可达性很低，簇可视化为山谷形状。山谷越深，表示簇越密集。
下面演示如何使用DBSCAN和OPTICS算法。
首先，在Preprocess标签页中加载鸢尾花数据集，然后切换至Cluster标签页，单击Choose按钮选择DBSCAN算法。
注意： 如果没有找到DBSCAN算法，那一定是还没有添加该学习方案，需要使用包管理器进行添加。由于DBSCAN和OPTICS算法的关系密切，Weka将这两个算法合为一个包，包名为optics_dbScan，最新版本为1.0.5。
单击Choose按钮右边的文本框，在弹出的通用对象编辑器中将epsilon参数设置为0.2，minPoints参数设置为5。然后，单击Ignore atrributes按钮，在弹出的Select items窗口中选择class属性，忽略该类别属性，单击Select按钮关闭该窗口。单击Start按钮启动聚类算法，在聚类器输出结果中可以看到，DBSCAN只发现两个簇，一个簇有49个实例，另一个簇有98个实例，还有三个实例未能聚类，如图2.80所示。
图2.80 DBSCAN输出结果
右击结果列表中新添加的条目，在弹出的快捷菜单中选择Visualize cluster assignments（可视化簇分配）菜单项，Weka将弹出可视化结果窗口，该可视化界面的操作可以参见2.7节的说明。图2.81所示的是横轴为sepalwidth、纵轴为petalwidth的可视化结果。
图2.81 聚类器结果可视化
从图中可以看到，DBSCAN发现了两个簇，一个显示为蓝色的簇（位于图中右下方）是Iris setosa，另一个簇显示为红色（位于图中左上方），由Iris viginica和Iris versicolor组成，DBSCAN并没有明确区别这两者。三个判定为离群值的实例在散点图中显示为字符M，左下方的一个M实际应该为Iris setosa，右上方的两个M实际应该为Iris versicolor，但在以花萼宽度为横轴，花瓣宽度为纵轴的散点图中，这些离群值的确与两个簇的距离都有些远。
现在，将minPoints参数由5修改为2，保持其他参数不变，重新运行。此时会惊奇地发现DBSCAN已经发现了三个簇，散点图右上方的两个离群值单独形成了第三个簇，因为它们相互间的距离小于设定的ε值，并且也满足簇大小的最小值为2的要求，如图2.82所示。
图2.82 重新运行的结果
现在，对鸢尾花数据集使用OPTICS算法。选择OPTICS聚类器，打开通用对象编辑器，将epsilon参数设置为0.2，minPoints参数设置为5。单击Start按钮运行聚类器，Weka会自动弹出OPTICS Visualizer窗口，窗口中部包括Table和Graph两个标签页，前者以表格形式显示聚类结果，后者以图形形式显示聚类结果，如图2.83所示。
图2.83 OPTICS可视化输出
从图中可以看到，有三个很高的峰值，中间夹着两个山谷，对应OPTICS找到的两个簇。通过设置距离可达性的阈值，获得不同的聚类，也就是说，在图中某个给定的可达性值的位置处绘制一条水平线，该水平线与峰值相交，两侧相交点形成山谷，这就是根据新阈值得到的簇。
注意： Weka提供的是OPTICS聚类算法的简单实现，不要将它作为运行时的参考基准，也不支持对新实例进行聚类分析。