数据挖掘/机器学习 之 聚类
·
聚类：对点集进行考察并按照某种距离测度将他们聚成多个簇的过程，目标是使得同一个簇内的点之间距离比较短，不同簇中点的距离较大
一般是从给定的数据中发现簇，尤其是大数据量及高维空间或非欧空间
点集是一种适合于聚类的数据集，每个点都是某空间下的对象，能够进行聚类的所有空间都有一个距离测度，即空间下任意两点的距离
聚类策略：
- 层次（hierarchical或者凝聚式agglomerative）算法。这类算法一开始将每个点看成一个簇，簇与簇之间按照接近度来组合，当进一步的组合导致产生非期望结果时，组合过程结束。如：达到预定的簇数目，根据簇的密度判断
- 点分配（point assignment），按照某个顺序依次考虑每个点，并将它分配到最合适的簇中
也可以按照其他方式：是否在欧氏空间下，或者算法对于任意距离测度都有效，需要注意到：欧氏空间下点集可以概括为质心（点的平均），非欧空间没有质心的概念
高维空间下的距离测度：
维数灾难的一个表现：高维空间下几乎所有的点对之间的距离都差不多相等，或者任意的两个向量间是近似正交的
- 距离分布：欧氏距离，几乎所有的点间的距离都接近与平均距离，这样很难聚类（这是在随机情况下），如果数据不随机，即使在高维情况下也存在簇，但是会对发现簇带来困难
- 向量夹角：随机向量正交，当维数增加，随机的两个向量期望夹角接近90度
层次聚类：当不存在质心时使用簇中心点（clustroid）来代表一个簇
欧氏空间下的层次聚类：
1.1：对于层次聚类需要确定：
- 簇如何表示
- 如何选择选择哪两个簇合并： 一个例子，寻找具有最小质心距离的两个簇进行合并
- 簇合并何时结束
一旦确定就可以用如下伪代码：
WHILE stop(Cluster):
pick the best two clusters to merge;
combine those two clusters into one cluster;
END;
如何停止：
- 确信簇的数目
- 如果在某个点，现有簇的最佳合并会产生一个不恰当的簇时停止合并，如何判断是否恰当有多种方法：
- 簇内所有点到质心的平均距离必须小于某个上界，前提是我们相信任何簇都不可能覆盖太多空间区域
- 当最佳合并的簇直径超过了某个阀值时停止，或者半径
- 簇的密度低于某个阀值时停止，密度是单位体积中点的数目，数目除以簇的直径/半径的某个幂（维数，1,2等）
- 簇的合并会产生很糟糕的结果时停止聚类，需要跟踪某个值，比如直径，如果直径大幅增加
3. 聚到只剩一个簇为止，返回一个所有点合并过程的树形表示，这种方式具有实际意义，比如：基因组合并过程反映了同一祖先进化的可能顺序
算法效率：O(n*nlogn), 使用优先队列存放点对和距离，合并A和B两个簇得到C后，在队列删去包含A和B的对，重新计算新簇和剩余簇的距离，不必计算没有发生变化的簇距离
合并规则：
- 定义两个簇的距离为两个簇中所有点的最短距离，这两个点来自不同的簇，选着最小的合并
- 定义簇的距离为所有点对距离的平均值
- 簇的半径，所有点到质心的最大距离，将结果簇具有最小半径的两个簇合并
- 簇的直径，簇内任意两点之间的最大距离，将结果簇具有最小直径的两个簇合并
非欧空间下：
基于点的距离测度，Jaccard距离，余弦距离，编辑距离
选择簇中心点，常见的是选使下列数值最小的：1）该点到簇中其他所有点距离之和，2）该点到簇中另外一点的最大距离，3）该点到簇中其他所有点的距离平方和
我们需要注意到，层次聚类不能视为全局优化目标函数，因为每次合并都是局部地确定的
点分配算法：
K-means，具体的算法就不说了，很多书和网站上有说，我在这里说一些其他的东西：
K-means算法极易受到初始值的影响，很有可能会实现局部最优，所以随机化有很大的缺点，所以在簇的初始化时要进行一些工作量：
K-means算法极易受到初始值的影响，很有可能会实现局部最优，所以随机化有很大的缺点，所以在簇的初始化时要进行一些工作量：
- 选择彼此距离尽可能远的的点
- 对样本数据先进行聚类，比如层次聚类，输出K个簇，在每个簇中选择一个点。
K值的选择：
首先,需要一个能够在不同的k下对聚类结果的质量进行评价的指标，只要我们假设的簇的数目等于或高于真实的簇数目，该指标上升的趋势会很缓慢，一旦少于真实数目的簇时，该指标会急剧上升，所以可以使用指数的增长对K进行考察K=1,2,4,8,...,找到V和2V,使用二分查找的方法找到合适的K
对于欧氏空间下，我们还可以使用误差的平方和（Sum of the Squared Error, SSE）作为度量聚类质量的目标函数，对于预先相似度可以用总凝聚度衡量
K-means算法终止的条件可以是质心不发生变化，也可以是SSE或其他衡量指标变化的量非常小
需要注意到，离群点对聚类的结果影响较大，尤其是在使用SSE作为标准时。
优点和缺点：
简单适用于各种数据结构和有效，但不是所有的数据都可以，不能处理非球形簇，不同尺寸和不同密度的簇（或者可以理解为K-means算法是一种混合模型，假定所有的簇都来自于球形高斯分布，具有不同的均值，但是都具有相同的协方差矩阵），此外它还易受离群点影响.
参考文献：
[1]大数据：互联网大规模数据挖掘与分布式处理
[2]数据挖掘导论
腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)