聚类（clustering）

　　无监督学习。
　　我们能用少量的原型，精准地概括数据吗？给我们一堆照片，能把它们分成风景、狗、婴儿、猫、山峰的照片吗？类似的，给定一堆用户浏览记录，我们能把他们分成几类典型的用户吗？这类问题通常被称为聚类（clustering）。
　　聚类本身就形容了问题和方法。聚类方法通常是由建模方式分类的比如基于中心的聚类和层次聚类。所有的聚类方法都是利用数据的内在结构来组织数据，使得每组内的点有最大的共同性。

主要的聚类方法

1）基于层次聚类算法：常见的有由下而上的两步聚类，确定相似函数及相似度的ROCK聚类等
2）基于密度聚类算法：常见的有基于最低信任值及最低n/N阀值的Dbscan
3）基于神经网络的聚类：常见的有把输入变量离散到目标维度上的SOM
4）基于统计学的聚类：常见的有类似于变量迭代的方式，产出如同决策树形式的COBWeb
5）先指定类个数的聚类算法，如k-means

常见的类模型有以下几种

1）连接模型。例如，基于距离连接的层次聚类法(hierarchical clustering)；
2）中心模型。例如，k-means法使用一个类均值代表一个类；
3）分布模型。例如，用概率分布代表一个类，典型的方法有基于EM算法的多元正态分布。 种常见的聚类算法。

按照不同类之间的关系，聚类分为两种类型

1）Hard clustering : 每一个对象确定地属于某一个类
2）Soft clustering : 每一个对象在某种程度上属于某个类，这里的“某种程度”，通常用概率表示。高斯混合模型

不需要指定类个数的聚类算法

　　一般都是将k转化为别的参数。毕竟这是一个如何防止过拟合的情况下得出最优解的问题。
　　如果资源足够丰富，可以考虑对不同的k赋予先验的概率之后使用贝叶斯。

　　在聚类问题上，通常用Dirichlet process（狄利克雷）作为mixture proportions的先验。DP的扩展包括Hierarchical Dirichlet process 和 Pitman-Yor process。
　　1）前者是对joint groups的数据建模，假设这些groups共享一个base distribution，也就是参数的先验。
　　2）PYP在Chinese restaurant process的基础上加了一个参数用于控制类别数目的生成速度，使得PYP能够更好的刻画Power-law这一现象。
　　这两种扩展很大程度推动了DP的应用，比如基于HDP-HMM以及Infinite PCFG，还有Hierarchical-PYP等。

---

K-均值聚类(K-means)

　　传统的K-Means算法的目标函数可以被表达成数据矩阵与其低阶数据矩阵之间差异的Frobenius范数。
　　简要的说，K-Means 聚类其实是一种矩阵分解问题。

具体做法

1）以你想要的簇的数量K作为输入，随机初始化每个簇的中心。
2）现在，在数据点和中心点的欧氏距离，将每个数据点分配给离它最近的簇。
3）将第二步中每个簇数据点的均值作为新的聚类中心。
4）重复步骤2和步骤3直到聚类中心不再发生变化。

如何在第一步中决定K值？

　　一种“肘部法则”（Elbow Method）可以用来确定最佳聚类数。你可以在K值范围内运行K-均值聚类，并在Y轴上绘制“可解释方差的比例”，在X轴上绘制K值。”

---

层次聚类

　　与K-均值聚类不同的是，初始化时，层次聚类中每个数据点都属于一类。顾名思义，它构建层次结构，在下一步中，它将两个最近的数据点合并在一起，并将其合并到一个簇中。

具体做法

1）将每个数据点分配给它自己的簇。
2）使用欧氏距离找到最接近的一组簇，并将它们合并为一个簇中。
3）计算两个最近的簇之间的距离，并结合起来，直到所有簇都聚集在一起。（距离计算可以是全连接，平均，重心，加权平均）

---

AP聚类算法

　　又称，吸引子传播算法；Affinity Propagation算法；A近邻传播聚类
　　

参考资料

https://blog.****.net/u010161379/article/details/51636926”

优点

1）不需要制定最终聚类族的个数
2）已有的数据点作为最终的聚类中心，而不是新生成一个族中心。
3）模型对数据的初始值不敏感。
4）对初始相似度矩阵数据的对称性没有要求。
5）相比与k-centers聚类方法，其结果的平方差误差较小”

缺点

1）虽然AP算法不用提前设置聚类中心的个数，但是需要事先设置参考度，而参考度的大小与聚类中心的个数正相关；
2）由于AP算法每次迭代都需要更新每个数据点的吸引度值和归属度值，算法复杂度较高，在大数据量下运行时间较长。