模糊聚类_聊聊聚类算法
学模式识别的时候觉得聚类是个很简单很基础的东西，但到了实习工作以及保研面试的时候又发现其实聚类没那么简单，这里从浅入深，结合个人项目以及其他写的不错的博客来聊聊聚类算法，有写的不对的地方欢迎指出~~主要参考了下面这些文章用于数据挖掘的聚类算法有哪些，各有何优势？www.zhihu.com09 聚类算法 - 层次聚类 - CF-Tree、BIRCH、CUREhttp://www.tcse.cn/~
学模式识别的时候觉得聚类是个很简单很基础的东西，但到了实习工作以及保研面试的时候又发现其实聚类没那么简单，这里从浅入深，结合个人项目以及其他写的不错的博客来聊聊聚类算法，有写的不对的地方欢迎指出~~
主要参考了下面这些文章
用于数据挖掘的聚类算法有哪些，各有何优势？www.zhihu.com09 聚类算法 - 层次聚类 - CF-Tree、BIRCH、CURE
http://www.tcse.cn/~wsdou/papers/2020-icdcs-diststream.pdfwww.tcse.cnhttps://zhuanlan.zhihu.com/p/55903495zhuanlan.zhihu.com
1 聚类基础
首先聚类是一个无监督的方法，在没有标签的情况下按“类间差异尽可能大，类内差异尽可能小”的思路去划分成一个一个的类簇。所以首先要做的就是怎么衡量差异？这个问题其实就是similarity measurement，简单来说就可以通过距离：
- 教科书上讲了很多的距离计算方法，简单的说主要有L1 norm即曼哈顿距离，L2 norm欧式距离，L无穷时即切比雪夫距离（取各坐标数值差的最大值）等。余弦距离用于评估向量间差异（注重维度之间的差异，不注重数值上的差异，相对欧式距离来说各个维度数值权重不同），汉明距离简单说就是字符替换最小次数。
- 除了距离外，还有很多比如相似性系数以及核函数等等，我也不是很了解就不说了
聚类可以分为硬聚类和模糊聚类：硬聚类的方法包括划分方法、层次方法、基于密度的方法、基于网格的方法以及基于模型的方法等等，硬聚类强调每一个数据只能被归为一类，即数据集中每一个样本都是被100%确定得分到某一个类别中；而模糊聚类是通过隶属函数来确定每个数据隶属于各个簇的程度，而不是将一个数据对象硬性地归类到某一簇中，可以理解为每个样本是以一定的概率被分到某一个类别中。
https://github.com/scikit-learn/scikit-learn/tree/master/sklearn/clustergithub.com2 常见聚类算法 K-Means
- K-Means是首先要给出类型数目K，然后先随便选取K个中心，再不断重新做划分并重新计算聚类中心，最后得到K个不变的聚类中心为止。
- 与KNN的比较：KNN其实是有监督的简单分类，而KMeans作为聚类方法是无监督的
- K-Means聚类准则与K值选取策略：最终的K个聚类中心应当使得准则函数J的值极小，函数J是每个样本和样本所属的聚类中心的距离平方和；因此K增大，J变小，所以K-J曲线的拐点是最合适的K值，使得J的值极小（不是最小，因为当K等于样本数时J必然为0，这样没有意义）。这种方式可以帮助选取K值，被称为Elbow Method肘部法则，简单来说就是目测拐点，不过大佬表示更推荐根据实际情况人工选取k值。关于K-Means如何确定K值，如何确定最佳聚类数目这样的问题，这篇文章有非常深入的讨论:【机器学习】确定最佳聚类数目的10种方法 - 曹明 - 博客园, 讲解了Gap Statistic等方法，比目测肘部拐点的方式更复杂一些，有兴趣可以看看
- 改进思路1（K-Means++）：改进初始的K个聚类中心的选取方式
- 原始K-means算法最开始随机选取数据集中K个点作为聚类中心，而K-means++按照如下的思想选取K个聚类中心：假设已经选取了n个初始聚类中心(0<n<K)，则在选取第n+1个聚类中心时：距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心。在选取第一个聚类中心(n=1)时同样通过随机的方法。可以说这也符合我们的直觉：聚类中心当然是互相离得越远越好。这个改进虽然直观简单，但是却非常得有效。
- 改进思路2（ ISODATA） ：聚类中心数K在迭代中不断调整
- 在计算聚类中心的过程中，K值通过模式类的合并和分裂来进行不断地修改
- '合并'(当聚类结果某一类中样本数太少, 或两个类间的距离太近时，或类别数过多时)
- '分裂' (当聚类结果中某一类的内方差太大, 将该类进行分裂，或类别数过少时)
- 我理解中ISODATA是需要用户给出一系列的参数，再根据这些参数选取范围内比较合适的K值，这些参数包括每个类的最小样本数目，类内距离（最大方差阈值）/类间距离阈值，预期聚类中心数等等。如果参数不符合则进行相应的合并/分裂操作，从而满足参数并调整K值。
- 具体步骤十几步就不列了，有兴趣可以参考一下这篇博客，最后总结一下：ISODATA算法能够在聚类过程中根据各个类所包含样本的实际情况动态调整聚类中心的数目。如果某个类中样本分散程度较大（通过方差进行衡量）并且样本数量较大，则对其进行分裂操作；如果某两个类别靠得比较近（通过聚类中心的距离衡量），则对它们进行合并操作。
- 改进思路3（Kernel K-means）：核K-均值聚类
- kernel k-means,就是将每个样本进行一个投射到高维空间的处理,然后再将处理后的数据使用普通的k-means算法进行聚类
- 改进思路4（bisecting K-means）：二分K-Means
- 首先将所有点作为一个簇，然后将该簇一分为二。之后选择能最大程度降低聚类代价函数（也就是误差平方和SSE）的簇划分为两个簇（或者选择最大的簇等，选择方法多种）。以此进行下去，直到簇的数目等于用户给定的数目k为止。
- 已经是一种层次聚类的思想了，可能是因为依然是依据代价函数来进行分裂所以依然叫k-means？
- 但是我有个问题，这个Bi-KMeans看起来就是不断地用KMeans(2)来二分分裂，最后得到K个分开的簇，那既然每一步都是KMeans二分类，何不一开始就直接KMeans(K)来分K个类呢？效果不是更好吗？看起来二分K-Means的方法除了解决了K-Means初始聚类中心的随机性这个问题外并没有什么实质性的突破？
- 改进思路5（elkan K-Means） 距离计算优化
- K-Means时间复杂度是O(klmn)，其中k为聚类中心数，I为迭代次数，n为样本数，m为样本的字段数，所以其实性能瓶颈在每轮迭代都需要计算每个样本点到k个聚类中心的距离，如果能优化计算距离这部分，整体算法就会有提升。
- 计算距离本身没法优化，但是elkan K-Means可以通过避免不必要的距离计算来优化整体。那么哪些距离不需要计算呢？
- 这里利用了三角形两边之差小于第三边的性质，举个例子：
- 已知某个样本点A和两个聚类中心M1、M2，假设距离上满足M1M2 > 2 * AM1，根据两边之差小于第三边可以得到：AM2 > M1M2 - AM1，即AM2 > M1M2 - AM1 > AM1，因此可以得到AM2 > AM1，不需要计算AM2的距离，就可以知道AM1更小，所以就避免了AM2这个不必要的距离计算。
- 改进思路6（Mini Batch K-Means） 适合大数据的聚类算法
- 对于样本数多于10000的情况下，就最好要使用Mini Batch K-Means来加速了
- Mini Batch KMeans使用了一个种叫做Mini Batch（分批处理）的方法对数据点之间的距离进行计算。在普通的K-Means的计算过程中，每次更新各聚类中心点时，需要计算所有点和每个聚类中心点的距离，所以代价特别昂贵。而在mini-batch K Means的计算过程中，每次更新各聚类中心点时，先从所有数据中随机地选取一个小集合（也就是这里的mini-batch），根据这个集合中的数据点，来更新各聚类的中心点。下一次更新时，再重新从所有数据点中选取一个随机的小集合，如此重复，直到达到收敛条件。
- 例如batch_size为100时，就是每次拿100个样本做迭代计算新聚类中心，算完再随机拿100个去计算更新，这样减少了计算时间，效果也下降不多。
- 进一步的讨论：K-Means实现mini-batch online learning的原理是什么？-SofaSofa
- 原始论文：http://www.eecs.tufts.edu/~dsculley/papers/fastkmeans.pdf
- scikit learn实现介绍：https://scikit-learn.org/stable/modules/clustering.html#mini-batch-kmeans
Mini-Batch的思想就是用部分数据，而不是全部数据，来更新模型的参数。实际上，这种思路不仅应用于K-Means聚类，还广泛应用于梯度下降、深度网络等机器学习和深度学习算法。
A Phrase-Based Method for Hierarchical Clustering of Web Snippets
document文档可以看成phrase短语的集合，那么如果要对document文档做聚类，用无监督的方式把文档分入不同的簇，我们可以利用phrase短语：具备一定数量的相同phrase分词的文档归入同一类。在snippets短消息这种应用情景下，phrase分词数量
以后有空继续更新～
CSDN联合极客时间，共同打造面向开发者的精品内容学习社区，助力成长！
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)