cluster 聚类分析

聚类分析被称之为unsupervised分析，一个跟它相似的概念是分类(classification)模型，不同的是，分类模型预先知道 一共有几个类别，每个类别的定义是什么，所以叫做supervised。聚类分析预先不知道目标分成哪几类。往往在实际中，先用cluster分成一些 类，然后有了这些类之后，可以再可以做classification分析，就是所谓的two steps analytisis.

聚类分析的算法主要基于“距离”的计算。聚类之后的结果要尽量保证每个segment内部的对象之间距离要短， segment之间的距离要长。这篇博客的内容总结自Han Jiawei的书，这本书可以在这篇博客里找到： 分享读书笔记Data Mining Concepts and Techniques  

关于距离：

如果有n个对象，每个对象有p个属性，那么可以得到这样一个矩阵：

距离通常是用另一个变形后的矩阵来做的：

其中d(2,1)表示第二个对象第一个属性和第一个对象第一个属性之间的距离。

对于连续型变量(interval)的 ，通常要对数据预先做标准化“standardiz”，方式如下：

1. 算mean absolute deviation.

2. 得出标准度量(不知道怎么翻译，standardized measurement)

3.最后结果：

 

对 于二值型(binary)的, 有两种，一种是均衡型的（symmetric），另一种是非均衡型的(asymmetric),均衡指的是yes or no两种状态权重一样。比如如果你没有性别歧视的话，性别是均衡的二值变量。如果通过一系列症状诊断一个人是否生病了，yes比no的权重要大的多。

两种形式都通过下面这个2x2的表来算距离：

对于均衡型的，

对于非均衡型的

 

对于类别型（categorical）的变量，比较简单

where m is the number of matches (i.e., the number of variables for which i and  j are
in the same state), and p is the total number of variables.

 

对于顺序型（ordinal）的变量，要先把顺序map成[0.0，1.0]之间的数，然后按interval的方式来算。直接上截图，因为太多数学符号了

书上对每种计算基本都有例子。

 

关于聚类方法：

有partitioning, hierarchical, density-based, grid-based, model-based, clustering High-Dimensional, Constraint-Based.

Partitioning方法：

代表方法是K-means:

它的大致算法是，选定K值（最后要分成多少组）后，任选K个object作为cluster的中心，然后对每个其他的对象计算离哪个中心最近，就归到哪个cluster里，最后从每个cluster中找到新的中心，然后这样重复计算，直到聚类没有变化为止。

 

Hierarchical方法：

分 agglomerative和Divisive两种，前者是自底向上的，就是一个一个object merge出一个segment,后者相反，自顶向下的。 上面说的K-means方法有时候和hierarchical联在一起用，因为K-means需要k作为参数，这个参数还挺重要的，极大影响了聚类的结 果，可以先用hierarchical看看大致分几类合理，然后再用K-means。

 

Density-based方法：

基于距离的算法segment都是类球形的，density-based克服了这个问题。他的理念基本上是，一个对象为中心画个圆，看看圈近来的对象过没过threshold.

 

Grid-Based:

它是从上往下分层，底层grid粒度更细。它的特点是是scalability比较好。没细看理论，但是看图能感觉个大概。

 

Constraint-Based:

有 的时候用户清楚应用的需求，想要指引聚类的过程，比如每个cluster size的range, 不同对象不用的权重等等。这就用到constraint-based聚类分析。这个也没细看，还有另外的clustering high-dimensional data, model based clustering都没怎么看，也许以后再写一篇“再访聚类分析”。下一篇会关于决策树。