聚类算法-基础篇

聚类算法-基础篇

1. 聚类定义

“聚类是把相似的对象通过静态分类的方法分成不同的组别或者更多的子集（subset）,这样让在同一个子集中的成员对象都有相似的一些属

性。” ——wikipedia

“聚类分析指将物理或抽象对象的集合分组成为由类似的对象组成的

多个类的分析过程。它是一种重要的人类行为。聚类是将数据分类到不同的类或者簇这样的一个过程，所以同一个簇中的对象有很大的相似性，而不同簇间的对象有很大的相异性。” ——百度百科

说白了，聚类（clustering）是完全可以按字面意思来理解的——将相同、相似、相近、相关的对象实例聚成一类的过程。简单理解，如果一个数据集合包含N个实例，根据某种准则可以将这N个实例划分为m个类别，每个类别中的实例都是相关的，而不同类别之间是区别的也就是不相关的，这个过程就叫聚类了。

形式化一点，令，其中的x都是向量，一个X的m聚类R将X分割为m个集合C1, C2, ,Cm，使其满足下面三个条件：

（1）

（2）

（3）

满足上述条件的同时，在聚类Ci中的向量彼此相似，而与其他类中的向量不相似。

但是这种定义也只是定义了确定性的聚类，也叫做硬聚类(hard clustering)，每个实例x都确定的属于某个聚类。而不确定性聚类，也需要定义，这就引出了模糊聚类(fuzzy clustering)的概念了。模糊聚类中，每个实例向量x以一定的隶属度属于某个聚类。同上面的设置，X的模糊聚类是将X分成m个类，由m个函数uj表示，其中满足：

（1）

聚类算法-基础篇

（2）

（3）

其中这个隶属度函数越接近1，说明xi越可能属于Ci，反之如果越接近0，则说明越不可能属于Ci。

2. 聚类过程

当我们知道聚类是什么时，我们下一步想知道的应该是怎么进行聚类。这一点，教材上做了详细介绍，补充一点自己理解：

1）特征选择(feature selection)：就像其他分类任务一样，特征往往是一切活动的基础，如何选取特征来尽可能的表达需要分类的信息是一个重要问题。表达性强的特征将很影响聚类效果。

2）近邻测度(proximity measure)：当选定了实例向量的特征表达后，

这个问题是非常关键的一个问题，在聚类过程中也有着决定性的意义，因为聚类本质在区分相似与不相似，而近邻测度就是对这种相似性的一种定义。

3）聚类准则(clustering criterion)：定义了相似性还不够，结合近邻测度，如何判断相似才是关键。直观理解聚类准则这个概念就是何时聚类，何时不聚类的聚类条件。当我们使用聚类算法进行计算时，如何聚类是算法关心的，而聚与否需要一个标准，聚类准则就是这个标准。

4）聚类算法(clustering algorithm)：这个东西不用细说了吧，整个学习的重中之重，核心的东西这里不讲，以后会细说，简单开个头——利用近邻测度和聚类准则开始聚类的过程。

5）结果验证(validation of the results)：其实对于PR的作者提出这个过程也放到聚类任务流程中，我觉得有点冗余，因为对于验证算法的正确性这事应该放到算法层面吧，可以把4）和5）结合至一层。因为算法正确和有穷的验证本身就是算法的特性。

6）(interpretation of the results)：中文版的PR上翻译为结果判定，而我感觉字面意思就是结果解释。做事前要有原则，做事后要有解释，这个就是解释了。

聚类算法-基础篇

整个聚类任务详细的东西会在以后详细介绍，这里先细说一下聚类准则。举例吧，比如，有这样一个数据集X，包含了四名同学的基本信息和数学成绩。

聚类准则就是一个分类标准，对于示例中这样一个数据集合，如何聚类呢。当然聚类的可能情况有很多。比如，如果我们按照年级是否为大于1来分类，那么数据集X分为两类：{张三}，{李四，张飞，赵云}；如果按照班级不同来分，分为两类：{张三，李四}，{张飞，赵云}；如果按照成绩是否及格来分（假设及格为60分），分两类：{张三，李四，赵云}，{张飞}。当然聚类准则的设计往往是复杂的，就看你想怎么划分了。按照对分类思想的几何理解，数据集相当于样本空间，数据实例的特征数（本例共有4个特征[姓名，年级，班级，数学成绩]）相当于空间维度，而实例向量对应到空间中的一个点。那么聚类准则就应该是那些神奇的超平面（对应有数学函数表达式，我个人认为这些函数就等同于聚类准则），这些超平面将数据“完美的”分离开了。

3. 聚类特征类型

聚类时用到的特征如何区分呢，有什么类型要求？聚类的特征按照域划分，可以分为连续的特征和离散特征。其中连续特征对应的定义域是数据空间R的连续子空间，而离散特征对应的是离散子集，另外如果离散特征只包含两个特征值，那么这个离散特征又叫二值特征。

根据特征取值的相对意义又可以将特征分为以下四种：标量的(Nominal)，顺序的(Ordinal)，区间尺度的(Interval-scaled)以及比率尺度的(Ratio-scaled)。其中，标量特征用于编码一类特征的可能状态，比如人的性别，编码为男和女；天气状况编码为阴、晴和雨等。顺序特征同标量特征类似，同样是一系列状态的编码，只是对这些编码稍加约束，即编码顺序是有意义的，比如对一道菜，它的特征有{很难吃，难吃，一般，好吃，美味}几个值来定义状态，但是这些状态是有顺序意义的。这类特征我认为就是标量特征的一个特定子集，或者是一个加约束的标量特征。区间尺度特征表示该特征数值之间的区间有意义而数值的比率无意义，经典例子就是温度，A地的温度（20℃）比B地（15℃）高5度，这里的区间差值是有意义的，但你不能说A地比B地热1/3，这是无意义的。比率特征与此相反，其比率是有意义的，经典例子是重量，C重100g，D重50g，那么C比D重2倍，这是有意义的。（当然说C比D重50g也是可以的，因此可以认为区间尺度是比率尺度的一个真子集）。

聚类算法-基础篇

在常见应用中，包括我们平日关心的编程实现中，一般只定义nominal特征和numeric特征，其中nominal可以用string来表示，而numeric可以用number来表示。（weka中的attribute的特征类型就是这么定义的）

4. 聚类分析的应用

说了这么多基本概念，最实际的话题莫过于应用了。就像为聚类做广告一 样，到底我们可以在哪里应用它呢。就像引言里我提到的传说一样，分类作为人类识别对象的一个基本活动大概与人类的意识共同存在着，也可以说人类智能认识的 本质活动之一就是分类。而研究者对分类的研究又将分类划分为有监督与无监督，其中聚类就是无监督分类的最常用方法也是绝对代表性方法。设想一下，对于一组 数据，或者一堆信息，计算机可以自动地将其分为若干类，那这对于辅助人类智能来说绝对是必要的也是有意义的。所以聚类的一个核心应用就是数据挖掘与模式识 别。另外各个科学领域只要涉及到分类的任务，大家无不联想到聚类。而学者比较权威的分类将聚类的应用分为四个基本的方向：

1）数据去冗，即将海量数据中的冗余信息去除。

2）假说生成，为了推导出数据的某些性质，我们可以对数据进行聚类分析。

3）假说检验，其实就是通过聚类分析来验证某个决策的风险程度。

4）基于分组的预测，同所有预测任务一样，将已有的数据都聚类分类后，新的未来数据可以用同样的规则进行识别预测其所属分类。

Eg. 假设你的工作是在一 …… 此处隐藏：3395字，全部文档内容请下载后查看。喜欢就下载吧 ……