非监督学习之聚类算法（1）
一、聚类的概念
聚类是一种无监督学习，根据样本的内在相似性/距离，将大量未知标记的样本集划分为多个类别，使得同一个类别内的样本相似度较大（距离较小），而不同类别间的样本相似度较小（距离较大）。
样本相似度比较见python实现相似性/距离的度量
二、聚类算法分类
基于划分的聚类算法：
| 算法 | 描述 |
|---|---|
| k-Means | 一种典型的划分聚类算法，它用一个聚类的中心来代表一个簇，在迭代过程中选择聚类中心点。只能处理数值型数据 |
| k-Modes | K-Means算法的扩展，用于处理分类型数据 |
| k-Prototypes | 结合了K-Means和K-Modes两种算法，能够处理混合型数据 |
| k-Medoids（中心点） | K-Means算法的改进，对异常值不再敏感。代表为Partitioning Around Medoids (PAM)算法。缺点是计算用时长，只适合处理小规模数据集 |
| Clara | k-Medoids算法的改进，采用了抽样技术，能够处理大规模数据 |
| Clara NS | 对Clara算法的改进，提高了聚类质量，但计算效率较低且对数据输入顺序敏感只能聚类凸状或球型边界 |
基于层次的聚类算法：
| 算法 | 描述 |
|---|---|
| AGNES | 算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并 |
| BIRCH | 基于树模型的数据集扫描，每个叶子节点一个聚类，用中心和半径表示，适合于数据量大，类别数K也比较多的情况。它运行速度很快，只需要单遍扫描数据集就能进行聚类 |
| BUBBLE | 把BIRCH算法的中心和半径概念推广到普通的距离空间 |
| BUBBLE-FM | 通过减少距离的计算次数，提高了BUBBLE算法的效率 |
| CURE | 采用抽样技术先对数据集D随机抽取样本，再采用分区技术对样本进行分区，然后对每个分区局部聚类，最后对局部聚类进行全局聚类 |
| ROCK | 也采用了随机抽样技术，该算法在计算两个对象的相似度时，同时考虑了周围对象的影响 |
基于密度聚类算法：
| 算法 | 描述 |
|---|---|
| DBSCAN | 一种典型的基于密度的聚类算法，该算法采用空间索引技术来搜索对象的邻域，引入了“核心对象”和“密度可达”等概念，从核心对象出发，把所有密度可达的对象组成一个簇 |
| GDBSCAN | 算法通过泛化DBSCAN算法中邻域的概念，以适应空间对象的特点 |
| OPTICS | OPTICS算法结合了聚类的自动性和交互性，先生成聚类的次序，可以对不同的聚类设置不同的参数，来得到用户满意的结果 |
| FDC | FDC算法通过构造k-d tree把整个数据空间划分成若干个矩形空间，当空间维数较少时可以大大提高DBSCAN的效率 |
基于网格的聚类算法：
| 算法 | 描述 |
|---|---|
| STING | 利用网格单元保存数据统计信息，从而实现多分辨率的聚类 |
| WaveCluster | 在聚类分析中引入了小波变换的原理，主要应用于信号处理领域。（备注：小波算法在信号处理，图形图像，加密解密等领域有重要应用，是一种比较高深和牛逼的东西） |
| CLIQUE | 一种结合了网格和密度的聚类算法 |
基于模糊的聚类算法：
| 算法 | 描述 |
|---|---|
| PCM模糊聚类算法 | 模糊集合理论引入聚类分析中的产物 |
基于神经网络的聚类算法：
| 算法 | 描述 |
|---|---|
| 自组织神经网络SOM | 该方法的基本思想是由外界输入不同的样本到人工的自组织映射网络中 一开始时，输入样本引起输出兴奋细胞的位置各不相同，但自组织后会形成一些细胞群，它们分别代表了输入样本，反映了输入样本的特征 |
几种常用的聚类算法从可伸缩性、适合的数据类型、高维性（处理高维数据的能力）、异常数据的抗干扰度、聚类形状和算法效率6个方面进行了综合性能评价，评价结果如下表所示：
| 算法名称 | 可伸缩性 | 适合的数据类型 | 高维性 | 异常数据的抗干扰性 | 聚类形状 | 算法效率 |
|---|---|---|---|---|---|---|
| WaveCluster | 很高 | 数值型 | 很高 | 较高 | 任意形状 | 很高 |
| ROCK | 很高 | 混合型 | 很高 | 很高 | 任意形状 | 一般 |
| BIRCH | 较高 | 数值型 | 较低 | 较低 | 球形 | 很高 |
| CURE | 较高 | 数值型 | 一般 | 很高 | 任意形状 | 较高 |
| K-Prototypes | 一般 | 混合型 | 较低 | 较低 | 任意形状 | 一般 |
| DENCLUE | 较低 | 数值型 | 较高 | 一般 | 任意形状 | 较高 |
| OptiGrid | 一般 | 数值型 | 较高 | 一般 | 任意形状 | 一般 |
| CLIQUE | 较高 | 数值型 | 较高 | 较高 | 任意形状 | 较低 |
| DBSCAN | 一般 | 数值型 | 较低 | 较高 | 任意形状 | 一般 |
| CLARANS | 较低 | 数值型 | 较低 | 较高 | 球形 | 较低 |
三、聚类模型评价的指标
（1） 兰德系数（ARI评价法），需要真实值，最佳值为1，python里的sklearm函数adjust_rand_score
（2）互信息（AMI评价法），需要真实值，最佳值为1，python里的sklearm函数adjust_mutuai_info_score
（3）V-measure评价法， 需要真实值，最佳值为1，python里的sklearm函数completeness_score
（4）FMI评价法，需要真实值，最佳值为1，python里的sklearm函数fowlkes_mallows_score
（5）轮廓系数评价法，不需要真实值，畸变程度最大，python里的sklearm函数silhouette_score
（6）Calinski- Harabasz指数评价法，不需要真实值，相对较大，python里的sklearm函数calinski_harabaz_core
说明：评价的标准是组内的相似性越大，组间相似性越小，前四种方法因为有真实值得参与相对于后两种更具有说服力，那么当有真实值得参与时聚类的评价可以等同于分类算法的评价 ，轮廓系数在不考虑业务情况下得分越高越好，最高得分是1
四、怎么选择聚类算法
对于一个聚类问题，要挑选最适合最高效的算法必须对要解决的聚类问题本身进行剖析，下面我们就从几个侧面分析一下聚类问题的需求。
聚类结果是排他的还是可重叠的
为了很好理解这个问题，我们以一个例子进行分析，假设你的聚类问题需要得到二个簇：“喜欢詹姆斯卡梅隆电影的用户”和“不喜欢詹姆斯卡梅隆的用户”，这其实是一个排他的聚类问题，对于一个用户，他要么属于“喜欢”的簇，要么属于不喜欢的簇。但如果你的聚类问题是“喜欢詹姆斯卡梅隆电影的用户”和“喜欢里奥纳多电影的用户”，那么这个聚类问题就是一个可重叠的问题，一个用户他可以既喜欢詹姆斯卡梅隆又喜欢里奥纳多。
所以这个问题的核心是，对于一个元素，他是否可以属于聚类结果中的多个簇中，如果是，则是一个可重叠的聚类问题，如果否，那么是一个排他的聚类问题。
基于层次还是基于划分
其实大部分人想到的聚类问题都是“划分”问题，就是拿到一组对象，按照一定的原则将它们分成不同的组，这是典型的划分聚类问题。但除了基于划分的聚类，还有一种在日常生活中也很常见的类型，就是基于层次的聚类问题，它的聚类结果是将这些对象分等级，在顶层将对象进行大致的分组，随后每一组再被进一步的细分，也许所有路径最终都要到达一个单独实例，这是一种“自顶向下”的层次聚类解决方法，对应的，也有“自底向上”的。其实可以简单的理解，“自顶向下”就是一步步的细化分组，而“自底向上”就是一步步的归并分组。
簇数目固定的还是无限制的聚类
这个属性很好理解，就是你的聚类问题是在执行聚类算法前已经确定聚类的结果应该得到多少簇，还是根据数据本身的特征，由聚类算法选择合适的簇的数目。
基于距离还是基于概率分布模型
基于距离的聚类问题应该很好理解，就是将距离近的相似的对象聚在一起。相比起来，基于概率分布模型的，可能不太好理解，那么下面给个简单的例子。
一个概率分布模型可以理解是在 N 维空间的一组点的分布，而它们的分布往往符合一定的特征，比如组成一个特定的形状。基于概率分布模型的聚类问题，就是在一组对象中，找到能符合特定分布模型的点的集合，他们不一定是距离最近的或者最相似的，而是能完美的呈现出概率分布模型所描述的模型。
