聚类分析被称之为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都没怎么看,也许以后再写一篇“再访聚类分析”。下一篇会关于决策树。