1.基本概念
1.1 分类和聚类
我们首先看一下基本概念里的聚类与分类。我们都知道，有些时候，数据是有标签的，比如，输入数据x(i)如果对应的人脸的特征，而它对应的标签y(i)是相对应的人年龄。有标签的机器学习是有监督学习。但有些时候，数据是没有标签的，对果数据向量没有标签，则表时这种机器学习是无监督的。
有监督学习可以用来判断种类，比如，我们可以把一个人的外貌貌特征作为输入x(i),而以他的职业作为标签，则表明我们在做分类。同样，如果把一个人的外貌作为输入x(i),而使用他的年龄作为标签，由于年龄是一个数值，则表明我们在进行回归，回归是通过类别的或着数值的输入数据来拟合一个数值的输出。这里，我们只说明比较分类和聚类，因此，回归这一块不再详述。
当数据没有标签，但我们却对数据能否自然归类感兴趣时，使用到的便是无监督学习中的聚类算法（clustering algorithm），目的是把这些无标签的数据按照它们的距离远近进行归类。
1.2 聚类算法
简单举个例子来说明一下聚类算法的实用价值。
在商业上，聚类可以帮助市场分析人员从消费者数据库中区分出不同的消费群体来，并且概括出每一类消费者的消费习惯。
它作为数据挖掘中的一个模块，可以作为一个单独的工具来发现数据库中分布的一些深层的信息，并且概括出每一类的特点，或者把注意力放在某一个特定的类上做进一步的分析。
在商业上，聚类可以帮助市场分析人员从杂乱无章的消费者信息中来区分不同的消费的群体，从而总结这个消费群体的行为习惯，而引导消费。
聚类算法一般有五种方法，最主要的是划分方法和层次方法两种。
划分聚类算法通过优化评价函数把数据集分割为K个部分，它需要K作为输人参数。K均值算法便是最广泛使用的划分法。
1.3 划分法
在这儿，我们简单介绍一下划分法的概念。
给定一个有N个元组或者纪录的数据集，划分法将构造K个分组，每一个分组就代表一个聚类，K （1） 每一个分组至少包含一个数据纪录； （2）每一个数据纪录属于且仅属于一个分组（某些模糊聚类算法中该条件可以放宽）； 对于给定的K，算法首先给出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次好，而所谓好的标准就是：同一分组中的记录越近越好，而不同分组中的纪录越远越好。 根据这个原理，我们开始介绍k均值算法。 2.k-means算法 2.1K-means算法 K均值是聚类算法中最简单的一种，其目的是尝试找到数据的自然类别。用户设置了类别个数K,那么K均值 可以迅速找到数据的自然类别。 k-means具体算法是这样的： 1. 给定一个训练集 x(1), x(2)…x(m), x(i) 属于Rn 随机选择K个簇的质心，我们将其设为u(1), u(2)….u(k), u(j)属于Rn （公式表示如下： { x(1), x(2)…x(m)}, x(i) Rn u1, u2….uk Rn ） 2. 重复以下过程直过收敛： { 对于每一个样本i，计算其应该属于的类 对于每一个类j，重新计算该类的质心 } 其中，第一个公式表示，不断的调整参数j,使用每一个点的开销函数 c(i)达到最小值。其实，即是把每一个点都化分到离它最近的一个质心所在的簇中。 第二个公式表示，重新计算簇的质心，通过求簇内各个点的均值，从而得到新的簇的质心。以此迭代，直到簇的质心不再改变为止。 K均值算法的终止条件有三种情况： 第一， 在理想情况下，簇的质心不再发生改变，此时达到终止条件。 但有时候却不会那么理想，那么我们便设定了其它两个终止条件：达到了最大迭代次数或着质心移动的距离的小于用户所要求的精度。 2.2K-means算法图示 现在，我们使用看一个最简单的例子，来理解一下k均值算法。 图 2.2.1 k均值算法图示 如图2.2.1所示，现在有五个点，分别为A,B,C,D,E，现在，要将这五个点分为两个聚类，随机选择两个聚类的质心，经过计算，A,B两点归于一个聚类中，C,D,E三点归于另一个聚类中。经过一次迭代之后，重新计算聚类的质心，再次进行计算，则A,B,C三个点归于一个聚类，C,D两个点归于一个聚类。经过多次迭代之后，最终的结果如最后一幅图像中所示： A,B,C归于一个聚类， C,D归于一个聚类。 下面，我们可以一起看一下k均值在实际运行时产生的效果。 图 2.2.2 k均值算法运行效果（一） 样本点的分布如图2.2.2所示，我们令k=3,随机的选择3个聚类的质心点，图中显示 的是红色，蓝色及灰色3个方框。 我们可以观察出来，在所有的样本点中，左上角是一块稠密的区域，右边中间是一块稠密的区域，而下面的点相对来说可能要松散一些。 图 2.2.3 k均值算法运行效果（二） 首先，第一点步是把各个样本点归类于离它最近的质心点所代表的聚类。如图所示，图中所有的样本点化分为三个聚类。 分别重新计算聚类的质心，经过两次迭代之后，得到的结果如下图所示。 图 2.2.4 k均值算法运行效果（三） 经过多次迭代之后，得到的结果如图所示。它把所有的样本点分成了三个聚类，这个结果应该算是比较理想的，因为它大至符合了我们所期望的那样。 但是从这个图中我们也可以看出k均值的一个最大的缺点，即它最终效果的好坏与k个聚类质心的选定有很大的关系。如果在上图中，我们将三个聚类质心都选在了左侧，那可能不会出现这种较理想的状况。 对应的解决方法是，在k值已经确定的情况下，多做几次运算，选择最优的结果。这里，最优结果的判断，将在下面进行解释。 2.3K-means性能分析 这里对k-means算法的性能分析，主要是讲一下k-means算法的优点和缺点。 主要优点： 是解决聚类问题的一种经典算法，简单、快速。 对处理大数据集，该算法是相对可伸缩和高效率的。因为它的时间复杂度是O(nkt) ，其中，n 是所有对象的数目，k 是簇的数目，t 是迭代的次数。通常k < 主要缺点： 必须事先给出k 值，但很多时候并不知道数据集应该分成多少个类别才最合适。聚类结果对初值敏感，对于不同的初始值，可能会导致不同结果。 初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果。可以多设置一些不同的初值，对比最后的运算结果，一直到结果趋于稳定来解决这一问题，但比较耗时、浪费资源。 算法没有考虑到各数据对象对聚类的影响是不同的，单纯从欧氏距离去决策分类。这对于含有较多“躁声”和孤立点数据聚类时准确度不高。 对于k均值的缺点，主要是三个方面。 第一， k均值方法对k值比较敏感。对于一个庞大的样本集，并不能像我们上面看到的那样，能将各个点显示在一张二维的图片上，通过分析，可大至确定一个k值。 实际中，样本集里的数据可能是三维的，也可能是多维的。 第二， 初始聚类质心的选择对最终结果有较大的影响。对于质心选择的不同，肯定会对结果产生较大的影响。 第三， 算法没有考虑到各数据对象对聚类的影响是不同的，单纯从欧氏距离去决策分类。这对于含有较多“躁声”和孤立点数据聚类时准确度不高。 对于“躁声”和孤立点数据是敏感的，少量的该类数据能够对平均值产生 影响。 极大的 下面的话，将分别对应于这三个缺点，提出相应的处理方法。 2.4K-means算法优化 2.4.1 k值选择 (参考资料： http://wenku.baidu.com/link?url=EP9TXcIswM9C7D77F3Bp9X1gRvJYS62vK3MsibJM7JXSIgDlwpy-k_aaGjpxFkKJ7XjH55Gwa0qzHDxXjDWP_pfHDOdhxcWTRbCGyIr_7aq) 多数情况下，聚类数k事先无法确定，因此，需要对最佳聚类 k进行优化，即寻找最 佳聚类数kopt 前面我们说过一个暂时定义为开销函数的东西，即每个样本点到到聚类质心的距离的平方，我们可以得到总的开销函数，其形式如下： cost(i,j,k) := 但问题是，使用这个总的开销函数无法得到kopt。原因很简单，随着k值的增加，这个函数是逐渐减小的。简单说一下，假设令k=1的时候，总会有一些点离聚类质心比较远。但是当k越来越接近于n的时候，这个函数的值会接近于0。 这个这和有监督学习里面的欠拟合和过拟合差不多的意思。当k接近于n的时候，这种聚类的分法也就没有了意义。 通常而言，k的取值范围为 2<= k <= n , 其中，n为样本的数目。 在这里，其中一个方法便是引入了距离代价函数，并且以距离代价最小准则来求解最佳聚类数k。 首先来看一下这里引入的三个定义： 这儿，需要不断的运行k均值方法，得到使距离代价函数达到最小的k值。 2.4.2 初始聚类中心的选择 初始聚类中心的选择对k均值最终产生的结果有很大的影响，因此，在k值已经确定的情况下，多运行几次k均值，而选择总方差最小的解决方案。 因篇幅问题不能全部显示，请点此查看更多更全内容