K-means聚类分析
作者：Pang-Ning Tan，Michael Steinbach，Vipin Kumar
国籍：America
出处：Introduction to Data Mining
中文译文：
8.2 K-means
基于原型的集群技术创建了数据对象的一级分区.有许多这样的技术，但最突出的两个是K-means和K-medoid. K-means用质心来定义原型，质心通常是一组点的平均值，通常用于连续n维空间中的对象.K-medoid用medoid定义了一个原型，medoid是一组点的最具代表性的点，它可以应用于广泛的数据，因为它只需要对一对对象的接近度度量.虽然质心几乎从不对应于实际的数据点，但medoid根据其定义，必须是实际的数据点.在这一节中，我们将只关注K-means，它是最古老和最广泛使用的聚类算法之一.
8.2.1 基本K-means算法
K-means聚类技术很简单，我们首先描述基本算法.我们首先选择K个初始质心，其中K是用户指定的参数，即期望的簇数.然后将每个点分配给最近的质心，每个分配给质心的点集合就是一个聚类.然后根据分配给聚类的点更新每个聚类的质心.我们重复分配和更新步骤，直到没有点改变集群，或者等价地，直到质心保持不变.
算法8.1对K-means进行了形式化描述.图8.3展示了K-means的操作，它展示了如何从三个质心开始，在四个分配-更新步骤中找到最终的集群.在这些和其他显示K-means聚类的图中，每个子图显示(1)迭代开始时的质心和(2)将点分配给这些质心.质心用“ ”符号表示;属于同一簇的所有点具有相同的标记形状.
算法 8.1 基本 K 均值算法.
1：选择 K 个点作为初始质心
2：重复
3： 通过将每个点分配到其最近的质心来形成 K 个集群
4： 重新计算每个簇的质心
5：直到 质心不变.
在第一步中，如图8.3(a)所示，将点分配给初始质心，这些质心都在较大的一组点中.对于这个例子，我们使用平均值作为质心.将点分配给质心后，质心会被更新.同样，每个步骤的图显示了步骤开始时的质心以及为这些质心分配的点.第二步，对更新后的质心分配点，再对质心进行更新.在图8.3 (b)、(c)、(d)所示的步骤2、3、4中，两个质心分别移动到图的底部的两组点.当K-means算法在图8.3(d)中终止时，由于不再发生变化，质心已经确定了点的自然分组.
图8.3 利用K-means算法在样本数据中找到三个聚类。
对于某些接近函数和各种形心的组合，K-均值总是收敛于一个解;也就是说，K-means达到了没有点从一个簇转移到另一个簇的状态，因此，质心没有改变.然而，由于大部分收敛发生在早期步骤，算法8.1第5行条件经常被较弱的条件取代，例如，重复直到只有1%的点改变聚类.
我们更详细地考虑了基本K-means算法中的每一步，然后对算法的空间和时间复杂度进行了分析.
分配点到最近的质心
要为最近的质心指定一个点，我们需要一个接近度量，它可以量化考虑的特定数据的“最近”概念.在欧氏空间中数据点通常使用欧氏距离()，而余弦相似度更适用于文档.但是，可能有几种接近度量适合于给定类型的数据.例如，曼哈顿()距离可以用于欧几里德数据，而Jaccard度量通常用于文档.
通常，由于算法反复计算每个点与每个质心的相似度，K-means的相似度度量相对简单.然而，在某些情况下，比如数据在低维欧氏空间中，可以避免计算许多相似点，从而显著加快K-means算法的速度.平分K-means(见8.2.3节)是另一种通过减少计算的相似点数量来加快K-means的方法.
表8.1 符号表
|
符号 |
描述 |
|
一个对象. 第个集群. 簇的质心. 所有点的质心. 第个集群中的对象数. 数据集中对象的数量. 集群的数量. |
质心和目标函数
K-means算法的第4步通常被称为“重新计算每个聚类的质心”，因为质心可以变化，这取决于数据的接近度和聚类的目标.聚类的目标通常由一个目标函数表示，该目标函数依赖于点与点之间或与聚类质心之间的距离;例如，最小化每个点到其最近的质心的平方距离.我们用两个例子来说明这一点.然而，关键是:一旦我们指定了接近度量和目标函数，我们应该选择的质心往往可以通过数学方法确定.我们在8.2.6节中提供了数学上的细节，并在这里提供了关于这个观察的非数学的讨论.
欧几里德空间中的数据 考虑接近度度量为欧氏斜距的数据.对于我们衡量聚类质量的目标函数，我们使用平方误差(SSE)的和，这也被称为散点.换句话说，我们计算每个数据点的误差，即它到最近质心的欧氏距离，然后计算误差平方和.给定由两个不同的K-means运行产生的两组不同的簇，我们更喜欢具有最小平方误差的一组，因为这意味着该簇的原型(质心)是其簇中点的更好的表示.使用表8.1中的符号，SSE的正式定义如下:
其中为欧几里德空间中两个物体之间的标准欧几里德()距离.
根据这些假设，可以看出(见8.2.6节)，使聚类的SSE最小化的质心是平均值.利用表8.1中的符号，第个簇的质心(均值)由式8.2定义.
例如，包含三个二维点的聚类的质心为.
K-means算法的第3步和第4步直接尝试最小化SSE(或者更普遍地说，目标函数).步骤3通过将点分配给它们最近的质心来形成聚类，这使得给定的质心集的SSE最小化.步骤4重新计算质心，进一步最小化SSE.然而，步骤3和步骤4中的K-means操作只能保证找到关于SSE的局部最小值，因为它们是基于针对质心和集群的特定选择而优化SSE，而不是针对所有可能的选择.稍后我们将看到一个导致次优集群的示例.
文档数据 为了说明K-means并不局限于欧氏空间中的数据，我们考虑了文档数据和余弦相似度度量.这里我们假设文档数据表示为文档术语矩阵，如第31页所述.我们的目标是最大限度地提高聚类中文档与聚类质心的相似性;这个量被称为聚类的内聚力.对于这一目标，可以证明，对于欧几里德数据，聚类质心是均值.与总SSE类似的量是总内聚力，由方程8.3给出.
一般情况下 对于接近函数、质心和目标函数有许多选择，这些选择可以用于基本k均值算法，并且保证收敛.表8.2显示了一些可能的选择，包括我们刚刚讨论的两个.注意，对于曼哈顿()距离和最小化距离之和的目标，合适的质心是聚类中点的中值.
表8.2 K-means:接近度、质心和目标函数的常见选择
|
接近函数 |
质心 |
目标函数 |
|
曼哈顿() |
中位数 |
目标到其聚类质心距离的最小和 |
|
平方欧氏() |
平均数 |
一个物体到其聚类质心的距离的平方的最小和 |
|
余弦 |
平均数 |
一个物体与它的聚类质心的余弦相似度的最大和 |
|
Bregman散度 |
平均数 |
一个物体到其聚类质心的Bregman散度的最小和 |
表中的最后一项，Bregman散度(第2.4.5节)，实际上是一类接近度量，包括平方欧几里得距离、、马氏距离和余弦相似性.Bregman散度函数的重要性在于，任何这样的函数都可以作为以均值为质心的K-均值风格聚类算法的基础.具体地说，如果我们使用Bregman散度作为我们的接近函数，那么结果聚类算法在收敛性、局部极小等方面具有K-means等通常的性质.此外，这种聚类算法的性质可以发展为所有可能的Bregman散度.实际上，使用余弦相似度或平方欧氏距离的K-means算法是基于Bregman散度的一般聚类算法的特殊实例.
对于其余的K-means讨论，我们使用二维数据，因为很容易解释这类数据的K-means及其属性.但是，正如前几段所指出的，K-means是一种非常通用的聚类算法，可以用于各种各样的数据类型，如文档和时间序列.
选择初始质心
当使用质心的随机初始化时，不同的K-means运行通常产生不同的总SSEs.我们用图8.3所示的二维点集来说明这一点，它有三个自然的点簇.图8.4(a)显示了一个集群解决方案，它是三个集群的SSE的全局最小值，而图8.4(b)显示了一个次优集群，它只是一个局部最小值.
图8.4 三个最优和非最优集群
选择合适的初始质心是基本K-means算法的关键步骤.一种常见的方法是随机选择初始质心，但得到的聚类往往很差.
例8.1(初始质心较差) 随机选择的初始中心点可能较差.我们使用与图8.3和8.4中相同的数据集提供了这方面的一个示例.图8.3和8.5显示了由两个特定的初始质心选择产生的集群.(对于这两幅图，在不同迭代中簇质心的位置都用叉表示.)在图8.3中，即使所有的初始质心都来自一个自然集群，仍然可以找到最小的SSE集群.然而，在图8.5中，尽管初始质心似乎分布得更好，我们获得了次优聚类，具有更高的平方误差.
例8.2(随机初始化的限制) 一种通常用于解决选择初始质心问题的技术是执行多次运行，每次运行使用随机选择的不同初始质心集，然后选择SSE最小的群集集.虽然很简单，但这个策略可能不是很有效，这取决于所寻找的数据集和集群的数量.我们使用图8.6(a)所示的样本数据集来说明这一点.数据由两对集群组成，其中每一对(上、下)中的集群彼此之间的距离比另一对中的集群更近.图8.6 (b-d)表明，如果我们从每对集群的两个初始质心开始，那么即使两个质心都在一个集群中，质心也会重新分布自己，从而找到“真正的”集群.然而，图8.7显示，如果一对集群只有一个初始质心，而另一对有三个，那么两个真实的集群将被合并，一个真实的集群将被拆分.
图8.5 K-means的初始质心差
请注意，只要两个初始质心位于一对集群中的任何位置，就会获得最佳的聚类，因为质心会重新分配自己，每个集群一个.不幸的是，随着星团数量的增加，至少有一对星团只有一个初始质心的可能性越来越大.(参见559页练习4)在这种情况下，由于成对的聚类之间的距离比成对内的聚类之间的距离要远，K-means算法不会在成对的聚类之间重新分配质心，因此只会达到局部最小值.
由于使用随机选择的初始质心的问题，这甚至重复运行可能无法克服，其他技术经常被用于初始化.一种有效的方法是采用分层聚类技术对样本点进行聚类.从层次聚类中提取出K个聚类，并将这些聚类的质心作为初始质心.这种方法通常工作得很好，但是只有当(1)样本相对较小，例如几百到几千(层次聚类是昂贵的)，以及(2)K相对于样本规模较小时，这种方法才实用.
下面的步骤是选择初始质心的另一种方法.随机选择第一个点或取所有点的质心.然后，对于每个连续的初始质心，选择离任何已经选择的初始质心最远的点.通过这种方法，我们得到了一组初始质心，它不仅可以随机选择，而且可以很好地分离.不幸的是，这种方法只能选择离群值，而不是密集区域(集群)中的点.此外，计算距离当前初始质心集最远的点是昂贵的.为了克服这些问题，这种方法经常被应用到样点上.由于异常值很少，它们往往不会出现在随机样本中.相反，除非样本容量非常小，否则每个密集区域的点都可能被包括进来.此外，由于样本大小通常比点的数量要小得多，因此寻找初始质心所涉及的计算也大大减少.
图8.6 两对簇，每对簇内有一对初始质心
图8.7 在一对簇中具有多于或少于两个初始质心的两对簇 剩余内容已隐藏，支付完成后下载完整资料
K-means聚类分析
作者：Pang-Ning Tan，Michael Steinbach，Vipin Kumar
国籍：America
出处：Introduction to Data Mining
中文译文：
8.2 K-means
基于原型的集群技术创建了数据对象的一级分区.有许多这样的技术，但最突出的两个是K-means和K-medoid. K-means用质心来定义原型，质心通常是一组点的平均值，通常用于连续n维空间中的对象.K-medoid用medoid定义了一个原型，medoid是一组点的最具代表性的点，它可以应用于广泛的数据，因为它只需要对一对对象的接近度度量.虽然质心几乎从不对应于实际的数据点，但medoid根据其定义，必须是实际的数据点.在这一节中，我们将只关注K-means，它是最古老和最广泛使用的聚类算法之一.
8.2.1 基本K-means算法
K-means聚类技术很简单，我们首先描述基本算法.我们首先选择K个初始质心，其中K是用户指定的参数，即期望的簇数.然后将每个点分配给最近的质心，每个分配给质心的点集合就是一个聚类.然后根据分配给聚类的点更新每个聚类的质心.我们重复分配和更新步骤，直到没有点改变集群，或者等价地，直到质心保持不变.
算法8.1对K-means进行了形式化描述.图8.3展示了K-means的操作，它展示了如何从三个质心开始，在四个分配-更新步骤中找到最终的集群.在这些和其他显示K-means聚类的图中，每个子图显示(1)迭代开始时的质心和(2)将点分配给这些质心.质心用“ ”符号表示;属于同一簇的所有点具有相同的标记形状.
算法 8.1 基本 K 均值算法.
1：选择 K 个点作为初始质心
2：重复
3： 通过将每个点分配到其最近的质心来形成 K 个集群
4： 重新计算每个簇的质心
5：直到 质心不变.
在第一步中，如图8.3(a)所示，将点分配给初始质心，这些质心都在较大的一组点中.对于这个例子，我们使用平均值作为质心.将点分配给质心后，质心会被更新.同样，每个步骤的图显示了步骤开始时的质心以及为这些质心分配的点.第二步，对更新后的质心分配点，再对质心进行更新.在图8.3 (b)、(c)、(d)所示的步骤2、3、4中，两个质心分别移动到图的底部的两组点.当K-means算法在图8.3(d)中终止时，由于不再发生变化，质心已经确定了点的自然分组.
图8.3 利用K-means算法在样本数据中找到三个聚类。
对于某些接近函数和各种形心的组合，K-均值总是收敛于一个解;也就是说，K-means达到了没有点从一个簇转移到另一个簇的状态，因此，质心没有改变.然而，由于大部分收敛发生在早期步骤，算法8.1第5行条件经常被较弱的条件取代，例如，重复直到只有1%的点改变聚类.
我们更详细地考虑了基本K-means算法中的每一步，然后对算法的空间和时间复杂度进行了分析.
分配点到最近的质心
要为最近的质心指定一个点，我们需要一个接近度量，它可以量化考虑的特定数据的“最近”概念.在欧氏空间中数据点通常使用欧氏距离()，而余弦相似度更适用于文档.但是，可能有几种接近度量适合于给定类型的数据.例如，曼哈顿()距离可以用于欧几里德数据，而Jaccard度量通常用于文档.
通常，由于算法反复计算每个点与每个质心的相似度，K-means的相似度度量相对简单.然而，在某些情况下，比如数据在低维欧氏空间中，可以避免计算许多相似点，从而显著加快K-means算法的速度.平分K-means(见8.2.3节)是另一种通过减少计算的相似点数量来加快K-means的方法.
表8.1 符号表
|
符号 |
描述 |
|
一个对象. 第个集群. 簇的质心. 所有点的质心. 第个集群中的对象数. 数据集中对象的数量. 集群的数量. |
质心和目标函数
K-means算法的第4步通常被称为“重新计算每个聚类的质心”，因为质心可以变化，这取决于数据的接近度和聚类的目标.聚类的目标通常由一个目标函数表示，该目标函数依赖于点与点之间或与聚类质心之间的距离;例如，最小化每个点到其最近的质心的平方距离.我们用两个例子来说明这一点.然而，关键是:一旦我们指定了接近度量和目标函数，我们应该选择的质心往往可以通过数学方法确定.我们在8.2.6节中提供了数学上的细节，并在这里提供了关于这个观察的非数学的讨论.
欧几里德空间中的数据 考虑接近度度量为欧氏斜距的数据.对于我们衡量聚类质量的目标函数，我们使用平方误差(SSE)的和，这也被称为散点.换句话说，我们计算每个数据点的误差，即它到最近质心的欧氏距离，然后计算误差平方和.给定由两个不同的K-means运行产生的两组不同的簇，我们更喜欢具有最小平方误差的一组，因为这意味着该簇的原型(质心)是其簇中点的更好的表示.使用表8.1中的符号，SSE的正式定义如下:
其中为欧几里德空间中两个物体之间的标准欧几里德()距离.
根据这些假设，可以看出(见8.2.6节)，使聚类的SSE最小化的质心是平均值.利用表8.1中的符号，第个簇的质心(均值)由式8.2定义.
例如，包含三个二维点的聚类的质心为.
K-means算法的第3步和第4步直接尝试最小化SSE(或者更普遍地说，目标函数).步骤3通过将点分配给它们最近的质心来形成聚类，这使得给定的质心集的SSE最小化.步骤4重新计算质心，进一步最小化SSE.然而，步骤3和步骤4中的K-means操作只能保证找到关于SSE的局部最小值，因为它们是基于针对质心和集群的特定选择而优化SSE，而不是针对所有可能的选择.稍后我们将看到一个导致次优集群的示例.
文档数据 为了说明K-means并不局限于欧氏空间中的数据，我们考虑了文档数据和余弦相似度度量.这里我们假设文档数据表示为文档术语矩阵，如第31页所述.我们的目标是最大限度地提高聚类中文档与聚类质心的相似性;这个量被称为聚类的内聚力.对于这一目标，可以证明，对于欧几里德数据，聚类质心是均值.与总SSE类似的量是总内聚力，由方程8.3给出.
一般情况下 对于接近函数、质心和目标函数有许多选择，这些选择可以用于基本k均值算法，并且保证收敛.表8.2显示了一些可能的选择，包括我们刚刚讨论的两个.注意，对于曼哈顿()距离和最小化距离之和的目标，合适的质心是聚类中点的中值.
表8.2 K-means:接近度、质心和目标函数的常见选择
|
接近函数 |
质心 |
目标函数 |
|
曼哈顿() |
中位数 |
目标到其聚类质心距离的最小和 |
|
平方欧氏() |
平均数 |
一个物体到其聚类质心的距离的平方的最小和 |
|
余弦 |
平均数 |
一个物体与它的聚类质心的余弦相似度的最大和 |
|
Bregman散度 |
平均数 |
一个物体到其聚类质心的Bregman散度的最小和 |
表中的最后一项，Bregman散度(第2.4.5节)，实际上是一类接近度量，包括平方欧几里得距离、、马氏距离和余弦相似性.Bregman散度函数的重要性在于，任何这样的函数都可以作为以均值为质心的K-均值风格聚类算法的基础.具体地说，如果我们使用Bregman散度作为我们的接近函数，那么结果聚类算法在收敛性、局部极小等方面具有K-means等通常的性质.此外，这种聚类算法的性质可以发展为所有可能的Bregman散度.实际上，使用余弦相似度或平方欧氏距离的K-means算法是基于Bregman散度的一般聚类算法的特殊实例.
对于其余的K-means讨论，我们使用二维数据，因为很容易解释这类数据的K-means及其属性.但是，正如前几段所指出的，K-means是一种非常通用的聚类算法，可以用于各种各样的数据类型，如文档和时间序列.
选择初始质心
当使用质心的随机初始化时，不同的K-means运行通常产生不同的总SSEs.我们用图8.3所示的二维点集来说明这一点，它有三个自然的点簇.图8.4(a)显示了一个集群解决方案，它是三个集群的SSE的全局最小值，而图8.4(b)显示了一个次优集群，它只是一个局部最小值.
图8.4 三个最优和非最优集群
选择合适的初始质心是基本K-means算法的关键步骤.一种常见的方法是随机选择初始质心，但得到的聚类往往很差.
例8.1(初始质心较差) 随机选择的初始中心点可能较差.我们使用与图8.3和8.4中相同的数据集提供了这方面的一个示例.图8.3和8.5显示了由两个特定的初始质心选择产生的集群.(对于这两幅图，在不同迭代中簇质心的位置都用叉表示.)在图8.3中，即使所有的初始质心都来自一个自然集群，仍然可以找到最小的SSE集群.然而，在图8.5中，尽管初始质心似乎分布得更好，我们获得了次优聚类，具有更高的平方误差.
例8.2(随机初始化的限制) 一种通常用于解决选择初始质心问题的技术是执行多次运行，每次运行使用随机选择的不同初始质心集，然后选择SSE最小的群集集.虽然很简单，但这个策略可能不是很有效，这取决于所寻找的数据集和集群的数量.我们使用图8.6(a)所示的样本数据集来说明这一点.数据由两对集群组成，其中每一对(上、下)中的集群彼此之间的距离比另一对中的集群更近.图8.6 (b-d)表明，如果我们从每对集群的两个初始质心开始，那么即使两个质心都在一个集群中，质心也会重新分布自己，从而找到“真正的”集群.然而，图8.7显示，如果一对集群只有一个初始质心，而另一对有三个，那么两个真实的集群将被合并，一个真实的集群将被拆分.
图8.5 K-means的初始质心差
请注意，只要两个初始质心位于一对集群中的任何位置，就会获得最佳的聚类，因为质心会重新分配自己，每个集群一个.不幸的是，随着星团数量的增加，至少有一对星团只有一个初始质心的可能性越来越大.(参见559页练习4)在这种情况下，由于成对的聚类之间的距离比成对内的聚类之间的距离要远，K-means算法不会在成对的聚类之间重新分配质心，因此只会达到局部最小值.
由于使用随机选择的初始质心的问题，这甚至重复运行可能无法克服，其他技术经常被用于初始化.一种有效的方法是采用分层聚类技术对样本点进行聚类.从层次聚类中提取出K个聚类，并将这些聚类的质心作为初始质心.这种方法通常工作得很好，但是只有当(1)样本相对较小，例如几百到几千(层次聚类是昂贵的)，以及(2)K相对于样本规模较小时，这种方法才实用.
下面的步骤是选择初始质心的另一种方法.随机选择第一个点或取所有点的质心.然后，对于每个连续的初始质心，选择离任何已经选择的初始质心最远的点.通过这种方法，我们得到了一组初始质心，它不仅可以随机选择，而且可以很好地分离.不幸的是，这种方法只能选择离群值，而不是密集区域(集群)中的点.此外，计算距离当前初始质心集最远的点是昂贵的.为了克服这些问题，这种方法经常被应用到样点上.由于异常值很少，它们往往不会出现在随机样本中.相反，除非样本容量非常小，否则每个密集区域的点都可能被包括进来.此外，由于样本大小通常比点的数量要小得多，因此寻找初始质心所涉及的计算也大大减少.
图8.6 两对簇，每对簇内有一对初始质心
图8.7 在一对簇中具有多于或少于两个初始质心的两对簇 剩余内容已隐藏，支付完成后下载完整资料
资料编号：[595599]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
