首先声明，我是一个菜鸟。一下文章中涌现技术误导情况盖不负责
聚类是数据挖掘描述任务的一个主要组成部分。数据挖掘任务包括描述性任务和预测性任务两种。描述性任务包括聚类、关联分析、序列、异常检测等，预测性任务包括回归和分类。
聚类：将数据对象分别为若干类，同一类的对象具有较高的相似度，不同类的对象相似度较低。从这个简略的描述中，可以看出聚类的关键是如何度量对象间的相似性。较为罕见的用于度量对象的相似度的方法有距离、密度等。
1 基于距离度量对象相似性的思惟
凡满足距离定义四个条件（唯一性、非负性、对称性和三角不等式）的函数都可以作为距离公式。经常使用的有欧氏距离（Euclid）、曼哈顿距离（Manhattan）、契比雪夫距离（Chebyshev）、马哈拉诺比斯距离（Mahalanobis）等。
基于距离的两类经典聚类算法：分别方法（Partitioning Method）和层次聚类方法（Hierarchical Method）。
1.1 分别方法
该方法的典范代表有k-Means、k-Medoids。
k-Means算法的核心思惟是把n个数据对象分别为k个类（这k各种事前未知），使得分别后每个类中的数据点到该类中央的距离最小。即使J最小。
k-means算法流程：
输入：分类个数k，包括n个数据对象的数据集输出：k个聚类（1）从n个数据对象中任意选取k个对象作为初始的聚类中央；（2）分别盘算每个对象到各个聚类中央的距离，把对象分配到距离最近的聚类中；（3）全部对象分配完成后，重新盘算k个聚类的中央；（4）与前一次盘算得到的k个聚类中央比较（检测是否收敛），如果聚类中央发生变化（未收敛），转（2），否则聚类结束。
k-means算法本质上是实现了聚类的基本思惟：类内数据点越近越好，类间数据点越远越好。
上述算法大多数情况下会终究求得收敛的最优聚类结果，但也有可能陷入局部最优解。还存在一个问题，上述算法有一个前提，就是指定k的值，即聚类个数。而在事实应用中k值是无法事前给定的，因此k-means算法的另一个重点就是要找出一个适合的k，使平方误差数值达到最小。一般的做法是尝试若干个k，选择使平方误差（距离）最小的k值。
k-Means算法第（3）步中聚类中央是盘算以后每个cluster的均值作为新的聚类中央，这恰是k-Means算法得名的原因。盘算公式为
第（4）步中检测是否收敛的标准并非经常使用标准，因为要达到完全收敛可能并不事实。因此，较为罕见的说法为，直到迭代了最大的步数或者前后的 J 的值相差小于一个阈值为止。
在k-medoids算法中，我们将从以后 cluster 中选取这样一个点——它到其他全部（以后 cluster 中的）点的距离之和最小——作为中央点。也就是说，k-Means算法选择的中央点未必在n个数据点中，而可所以连续空间的任意值；k-Medoids则只能在给样本给定的那些点里头选。也恰是因为这样，k-Means对噪声和孤立点数据非常敏感，而k-Medoids则可以有效地消除这种影响。
当结果簇是密集的，而簇与簇之间区别显著时，k-Means算法的效果较好。对于大规模数据集，该算法是绝对可扩展的，并且效率较高。仅就k-Means和k-Medoids两者而言，在第（3）步中，k-Means具有O(n)的时间复杂度，而k-Medoids的时间复杂度是O(n^2)。
k-Means的不足：首先，k-Means只有在簇数据点的平均值有定义的情况下才能应用，这可能不适用于某些应用，如离散数据。对k-Means改进后的k-模算法用模取代簇的平均值作为相似性度量，用基于频率的方法来修改聚类的模。k-模算法可用于解决离散问题。k-Means和k-模相结合用来处理有数值类型和分类类型属性的数据，这就是k-原型算法。其次，k-Means和k-Medoids不适用于发现非球状的簇。原因是这类算法应用距离来描述数据间的相似性，但是对于非球状数据集，只用距离来描述是不够的。对于这种情况，要采取密度作为相似性度量。（参见2）
1.2 层次聚类方法
层次聚类方法（Hierarchical Method）按数据分层建立簇，形成一棵以簇为节点的树。该方法的典范代表有凝聚法（Agglomerative）和分裂法（Divisive）。若自底向上进行层次聚集，则称为凝聚的层次聚类；若自顶向下进行层次分解，则称为分裂法的层次聚类。
凝聚的层次聚类首先将每个对象作为一个簇，然后逐渐合并这些簇形成较大的簇，直到全部对象都在同一个簇中，或者满足某个终止条件。分裂与之相反，它首先将全部的对象置于一个簇中，然后逐渐分别为越来越小的簇，直到每个对象自成一簇，或者达到了某个终止条件，例如达到了某个希望的簇数目，或两个最近的簇之间的距离超过了必定的阈值。
层次方法可以在不同粒度水平上对数据进行探测，而且容易实现相似度量或距离度量。但是，单纯的层次聚类算法终止条件暧昧，而且执行合并或分裂簇的操作不可修正，这可能致使聚类结果品质很低。另外，由于须要检查和预算大量对象或簇才能决定簇的合并或分裂，所以其可扩展性较差。因此，事实应用中常把层次方法与其他方法结合应用，形成多阶段聚类，改善聚类品质。这类方法包括BIRCH、CURE、ROCK、Chameleon等。
2 基于密度度量对象相似性的思惟
对于非球状的聚类问题可采取基于密度的聚类算法。基于密度的聚类算法（Density-based Method）从数据对象的分布密度触发，把密度足够大的区域连接起来，从而可以发现任意外形的簇，而且此类算法还能有效去除噪声。罕见的基于密度的算法有DBSCAN、OPTICS、DENCLUE等。
3 其他方法
3.1 视觉聚类算法
视觉聚类算法是基于尺度空间理论建立的。其基本思惟是：将数据集看作图像，将数据建模问题看作认知问题，通过模拟认知心理学的格式塔原理与生物视觉原理解决问题。格式塔原理（Gestalt）就是物体的团体是由局部特征组织在一起的认知原则，包括相似率、连续率、闭合率、近邻率、对称率。将这五者作为聚类的基本原则，模拟人的眼睛由近到远视察风物的进程设盘算法进行聚类。随着由近到远，视察尺度由小变大，所看到的风物层次会逐渐变化，这就是一个聚类的进程。
视觉聚类的关键是最好聚类个数的选择。随着尺度σ由小变大，聚类个数逐渐变少，但会涌现尺度σ在很大范围内变化而聚类个数稳定稳定的情况，这意味着这个聚类个数存活周期最长，它就是最好聚类个数。这解决了聚类有效性问题。
参考资料：
[1]谎话数据挖掘
[2]聚类算法研讨．孙吉贵等．Journal of Software
[3]座谈 Clustering (2): k-medoids．http://blog.pluskid.org/?p=40
[4]数据仓库工具箱：维度建模的完全指南
文章结束给大家分享下程序员的一些笑话语录： 腾讯总舵主马化腾，有人曾经戏称如果在Z国选举总统，马化腾一定当选，因为只要QQ来一个弹窗”投马总，送Q币”即可。
--------------------------------- 原创文章 By
聚类和算法---------------------------------