8.1 聚类概述在线视频

聚类过程遵循的基本步骤为

特征选择

尽可能多地包含任务关心的信息

近邻测度

定量测定两特征如何“相似”或“不相似”

准则定义

以蕴含在数据集中类的类型为基础

算法调用

按近邻测度和聚类准则揭示数据集的聚类结构

结果验证

常用逼近检验验证聚类结果的正确性

和结果判定

由专家用其他方法判定结果的正确性

物以类聚 人以群分

聚类是指根据“物以聚类”的原理

将本身没有类别的样本聚集成不同的组

这样的一组数据对象的集合叫做簇

并对每一个这样的簇进行描述的过程

聚类目的是使得属于

同一个簇的样本之间应该彼此相似

而不同簇的样本之间应该足够不相似

与分类规则不同

进行聚类前

并不知道将要划分的组的个数和类型

需要注意的是

在回归、分类等有监督学习任务中

要定义类别标签或者目标值

但聚类过程的输入对象

没有与之关联的目标信息

即类别标签或者目标值

正因为如此

聚类通常归于无监督学习任务

由于无监督算法不需要带标签数据

所以适用于

许多难以获取带标签数据的应用

在进行有监督学习任务之前

经常需要先利用聚类等

无监督学习来探查数据集

并挖掘其特性

由于聚类不使用类别标签

所以相似性的概念

要基于对象的属性进行定义

应用不同

则相似性的定义和聚类算法

都会不同

所以不同的聚类算法使用的数据集类型

和挖掘目的都不一样

因此

“最优”聚类算法实际上

依赖于具体的应用

聚类分析已经

广泛地用于许多应用领域

包括

商务智能

图像模式识别

Web搜索

生物学和安全

理想的聚类效果

对聚类方法研究提出了以下要求

①处理不同属性类型的能力

现有的许多聚类算法

处理的内容通常为数值

然而

随着数据收集技术的多元化发展

聚类应用中

可能需要对其他类型的数据属性

进行处理

如标称属性

二元属性

序数属性

数值属性等多种数据属性

以及包含

多种类型数据属性的混合型数据集

事实上

越来越多的研究开始关注包含

图形

图像

序列

文档等复杂类型数据对象的

数据集的聚类分析

② 可伸缩性

聚类算法不仅要在

小型数据集合上有良好的性能

对于很多并不局限于

成千上万的数据对象的大型数据库

甚至在超过数百万个数据对象的

大型数据库

都要有很好的性能

③对于确定输入参数的

领域知识的要求

许多聚类算法

需要数据挖掘用户

提前指定聚类的簇数目

才能进行聚类分析

然而进行数据挖掘的用户

并不一定是该数据领域的专家

特别是当该参数的设定

对于聚类的结果影响十分显著时

用户无法保证提供的参数一定合适

聚类的质量更是无从保证

对于高维度的大型数据集

不仅需要相当专业的领域知识

还需要深入理解数据

才能确定最佳的簇数目

这在很大程度上

增加了用户聚类分析的成本

④ 发现任意形状的簇

常规的聚类分析算法的相似度的度量方式

是以基于欧几里得距离

或曼哈顿距离为标准

而这些基于

距离的相似度度量方法

对于发现

具有相近尺寸和密度的球状簇

很有效果

对于任意形状簇的效果并不理想

实际生活中的数据往往并不是球状的

因此

对于可以发现

非球状簇的聚类分析算法的需求

已经越来越迫切

⑤ 处理噪声数据的能力

真实世界中多数的数据集

都不可避免地包括离群点

不完整的数据甚至是错误的数据

这些异常的数据称为噪声数据

噪声数据很容易

对某些聚类算法造成干扰

从而影响聚类结果的质量

⑥ 增量聚类和对输入次序不敏感

移动互联网的广泛普及

使得大型数据集随时进行增量更新

一旦数据发生了更新

就需要重新聚类的算法

是缺乏实用意义的

增量聚类应该将增量更新的数据

合并到已存在的簇中

而不必重新进行聚类

此外

由于数据产生先后的不确定性

还应该对数据输入的顺序不敏感

这样的聚类方法

才能保证聚类的稳定性和及时性

⑦ 聚类高维数据的能力

许多聚类算法

在处理低维度的数据时效果很好

可对于高维度的数据

或者含有大量属性值的数据集时

聚类效果很差

例如文本数据库

账务数据库

视频数据库等

很多应用领域的数据都是高维度的

对于这些高维数据

进行聚类分析是一个挑战

⑧基于约束的聚类

现实生活中的聚类

可能要满足一些约束条件

使聚类的结果

在满足良好的聚类特征的基础上

又要满足某些特定的约束条件

在这一过程中

要综合考虑多方面的因素

如何在具有良好的聚类性能的同时

满足特定的聚类要求

是一项极具挑战的任务

⑨可解释性和可用性

用户聚类的目的

更倾向于对聚类结果的理解

也就是说

通过结合特定的领域知识

聚类结果应该可以解释

便于理解以及具备可用性

从聚类的结果中发现可用的信息

也是聚类的最终价值

基本聚类方法概述

1. 基于划分的方法

给定一个 n个对象的集合

划分方法构建数据的k个分区

其中每个分区表示一个簇

并且k ≤ n

也就是说

它把数据划分为 k个组

使得每个组至少包含一个对象

基本上

划分方法都是

基于距离判断数据对象相似度的

通过不断迭代的技术

将含有多个数据对象的数据集

划分成若干个簇

使每个数据对象

都属于且只属于一个簇

同时聚类簇的总数目

小于数据对象的总数目

2. 基于层次的方法

层次方法创建给定数据对象集的层次分解

层次方法分为凝聚的方法或分裂的方法

这是根据聚类层次形成的方向进行划分的

凝聚的方法是

将每个数据对象作为个体

逐渐与相似的对象合并

直到满足聚类的目标

而分裂的方法则恰好相反

将所有数据对象作为一个整体

逐渐划分成簇以满足聚类的条件

层次聚类不局限于基于距离

也可以基于密度

连通性

甚至是基于空间进行聚类

层次聚类的过程是不可逆的

一旦凝聚或分裂了

数据对象就不能再次修正

这样很容易导致质量低的聚类结果

3. 基于密度的方法

大部分划分方法都是基于距离进行聚类的

在聚类非球形的数据集时并不理想

为了发现不规则形状的簇

通常将簇看成是

稀疏区域或稠密区域组成的空间

基于密度的方法

定义邻域的半径范围

邻域内的对象数目

超过某限定值则添加到簇中

这样的方法

可以发现任意形状的簇

此外

基于密度的方法

对于过滤噪声数据也很有效

4. 基于网格的方法

基于网格的聚类方法

使用一种多分辨率的网格数据结构

它将对象空间量化成有限的数目单元

这些单元形成了网格结构

所有的聚类操作都在该结构上进行

这种方法的主要优点是处理速度快

其处理时间独立于数据对象数

仅依赖于量化空间中

每一维上的单元数