什么是聚类（clustering）
个人理解：聚类就是将大量无标签的记录，根据它们的特点把它们分成簇，最后结果应当是相同簇之间相似性要尽可能大，不同簇之间相似性要尽可能小。
聚类方法的分类如下图所示：
一、如何计算样本之间的距离？
样本属性可能有的类型有：数值型，命名型，布尔型……在计算样本之间的距离时，需要将不同类型属性分开计算，最后统一相加，得到两个样本之间的距离。下面将介绍不同类型的属性的数据计算方法。
对于全部都是连续的数值型的样本来说，首先，对于值相差较大的属性来说，应该进行归一化，变换数据，使其落入较小的共同区间。
标准化的方法：
1.最大-最小规范化
其中Vi 表示在第i条记录在A这个属性上的取值，MINA表示A这个属性上的最小值，new_maxA表示我们希望映射到的区间的右边界，其他同理。
2. Z-score 规范化
其中两个参数分别表示均值和方差。
3. 小数定标规范化
通过移动属性A的小数点位置进行规范化。小数点移动位数依赖于A的最大绝对值。
在进行规范化之后，就可以计算两个样本之间的距离了，计算公式如下：
如果每个属性有不同的权重，公式修改如下：
对于全是布尔型的样本来说，计算方式如下：
上表表示对与不同的样本i,j，统计它们布尔型同时为1的属性个数，同时为0的属性个数，分别为1和0的属性个数，它们的距离计算方式如下所示：
这个公式的含义其实就是两个样本之间，取值不同的属性的数量与所有属性的数量的比值。
对于命名型（nominal variable）来说，其一种简单的距离计算公式为：
如果样本集的属性类型是混合的，那么有以下公式可以计算距离：
其中分母是属性的权重。
Partitional Clustering
主要思想：首先人为决定将要将数据集分为k个簇，然后根据簇内部相似性要尽可能大，簇之间相似性要尽可能小的思想，将样本分到不同的簇当中去。
1. K-means Clustering
算法过程：首先给k个簇随机分配中心点，然后计算样本集中的每一条数据与k个中心点之间的距离，将这条数据归为距离最小的那个簇。扫描完一轮之后，再重新根据每个簇中的样本，重新计算簇的中心点，然后再扫描样本集，根据新的中心点，计算样本与中心点之间的距离，从而k个簇里的样本更新。迭代几次之后，若重新计算出来的中心点与原来的中心点一样，那么停止迭代。
原理：
其中l表示l个簇，w(i,l)取值为0,1表示第i个样本是否属于第l个簇，d表示计算i样本与l中心点之间的距离。
我们的目的就是要找到w(i,l)使得这个p函数的值最小。很明显，穷举法时间复杂度太高而不可行。
我们采用梯度下降法来解决这个问题，沿着梯度方向下降，从而得到局部最优解。
K-means 算法的缺陷：
1. 受离群点影响
2. 受初始质心影响
3. 它分出来的cluster是球形的
4. 数据类型收到限制
2.K-medoids Method
算法过程：
1. 随机选择样本集中的k个样本作为中心点。
2. 计算剩下的样本到这k个中心点之间的距离，把样本全部分配到不同的cluster中。
3. 对于每一个中心点，每次用一个非中心点代替当前中心点，并重新分配cluster，计算代价函数。如果代替之后的代价比之前代价小，那么就用这个非中心点代替当前中心点。
4.重复2-3，直到中心点不再变化。
K-medoid method 相对k-means 来说比较不受离群点的干扰。
Hierarchical methods
cluster之间距离计算的方法：
Single linkage:
自底向上，首先把所有的样本都分别看作是单独的cluster，然后计算两两之间的距离，选择两两距离最小的合并成一个cluster，然后再更新其他cluster到这个cluster的距离。重复这个过程，直到所有的都合并成一个cluster。
BIRCH
http://blog.csdn.net/qll125596718/article/details/6895291
http://www.cs.sfu.ca/CourseCentral/459/han/papers/zhang96.pdf
Density-Based Clustering Methods
两个参数：
1. Eps: Maximum radius of the neighborhood 半径长度，在这个半径之内的点q都算作为p的邻居。
2. MinPts: Minimum number of points in an Eps-neighborhood of that point p作为中心点的最小邻居数。
几个概念：
1. 直接密度可达：q对p直接密度可达：p是q的邻居，q是中心点
2. 密度可达： q对p密度可达：存在一条链（p1,p2,...pi） p1=q,pi = p,pj 到pj+1是直接密度可达的。（1<=j<=i）
3. 密度连接：q对p密度连接：如果存在一个o，o到p密度可达并且o到q也密度可达，那么p,q是密度连接的。
聚类：由一个核心对象和其所有密度连接的对象构成一个cluster.