第8讲 聚类的基本概念在线视频

同学们好

欢迎来到

互联网大规模数据分析技术课堂

我是这节课的主讲教师张蕊

来自武汉理工大学

这节课我们一起来了解一下

聚类的基本概念

我们首先来看一下

ArnetMiner对热门话题的展示

这里展示了6个热门话题

同时每个话题下面提供了相关的研究者

支持这样的分析结果涉及多种技术

而聚类就是其中很重要的一种

那什么是聚类呢

物以类聚，人以群分

聚类顾名思义

就是将相似的对象聚集在一起

不相似的对象分区分开来

这就是聚类的本质

对ArnetMiner来说

它将相似的研究聚集在一起

形成一个个的topic

一个一个的话题，这就是聚类

下面我们来了解一下

关于聚类的基本概念

聚类是要聚成一个个的cluster

Cluster是簇，是数据对象的集合

同一个簇的对象相似

不同簇的对象相异

聚类分析，clustering

是根据数据特征发现数据之间的相似性

然后将相似的对象划分成簇

聚类是非监督学习

训练集中并没有预定好的类标签

典型的聚类分析

既可以作为一个单独的数据分析工具

也可以作为其他算法的预处理手段

典型的聚类分析，涉及以下基本步骤

特征选择：选择任务相关信息

并具有最小的信息冗余度

特征工程往往是知识发现工作的基础

相似性度量，对两个特征向量

采取什么方式去计算相似性

聚类标准：往往通过聚类函数

或者是一些规则来表达

聚类算法：选择一个合适的算法

结果的校验：包括验证测试等等

对结果的解释

这确定了如何集成到应用当中

当我们去考察一个

聚类分析方法的时候呢

往往会从以下角度去了解

它的划分准则是什么

究竟是单层的划分方法

还是多层的划分方法

比如类似ArnetMiner的话题聚类

如果每个topic还可以往下发现子话题

比如data mining下面还有

Stream mining、Graph mining等

那就是多层划分方法

否则就是单层划分方法

簇的分离性如何

有的情况下簇之间是互相排斥的

比如一个顾客仅仅划分在这一类当中

由某位员工负责

有时一个数据对象可以属于多个类

比如前面提到的

ArnetMiner的hot topic的例子中

jiawei Han既属于data mining组

也属于database组

那这个聚类中

对研究者的划分不是互相排斥的

它采用的是什么相似性度量

有的采用的是基于距离的方法

比如欧式距离等

比如对某刻路网上的车进行聚类

我们往往会采用各种距离函数

来作为相似性度量的指标

而有的采用基于连接的度量

比如说密度或邻近性定义

例如14年Science上发表的

聚类算法就是基于密度的

它的聚类空间是什么

有的聚类算法

是在整个数据空间中去搜索cluter

有的在子空间中搜索

前者一般针对低维数据

后者在高维数据聚类时很常见

在大数据环境下，高维数据很多

尽管数据量大

但从整个数据空间来看是稀疏的

这时在子空间聚类往往更可行也更有意义

对于聚类分析来说

通常面临的需求和挑战有以下这些

第一点，可伸缩性

那很多聚类算法

在小规模数据集上面运行良好

但对于大规模数据

可能性能就变得无法接受

因此

需要找到具有良好伸缩性的聚类算法

第二点，处理不同类型属性的能力

有的聚类算法只能处理数值型数据

但在大数据流行的今天

很多数据都是数值型数据

分类数据等的混合

也可能出现音频视频数据

数据之间还可能存在复杂的联系

比如图数据等等

那如何设计针对复杂数据的聚类算法

是一个非常挑战的问题

第三点，基于约束的聚类

用户可能会输入一些约束

也可能会用到相关的领域知识

比如对城市的交通情况进行聚类

除了考虑人和车外

还要考虑路网的约束等等

第四点，聚类的结果要可解释和可用

我们曾经有过这样的经验

对铺设在隧道下的传感器数据进行聚类

可是有些聚类结果看指标很好

但无法解释

而能解释的又是大家可以想象到的

比如说繁忙、空闲等模式

另外还有，发现任意形状的cluster

基于欧式距离的聚类算法

倾向于发现球形簇

但有时聚类的结果并不是球形的

其他的包括处理噪声的能力

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

对高维数据进行聚类等等

主要的聚类方法可以划分为以下几种

第一种，划分方法

划分方法，构建不同的划分

然后用一些准则来评估

比如说误差的平方和等等

典型的划分方法包括

k-means、k-mediods等

第二种，层次方法

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

这包括自顶向下或者是自底向上的方法等

第三种，基于密度的方法

基于密度的方法

根据连接性和密度函数来进行评估

典型方法包括DBSCAN、OPTICS等

第四种，基于网格的方法

基于多层的粒度结构

典型方法包括STING、CLIQUE等

第五种,基于模型的方法

这种方法认为模型是一个对簇的假设

然后试图发现最符合这些数据的模型

典型方法包括EM等

第六种，基于频繁模式的方法

这种方法通过发现频繁模式来进行聚类

典型方法包括p-cluster

第七种，用户指导的或者是基于约束的方法

通过考虑用户指定的

或者是特定的约束来进行聚类

典型方法包括COD等

第八种，基于链接的聚类

很多数据对象通过各种方式相互联系

可以考虑这些link来进行聚类

典型方法包括SimRank和LinkClus等

本节课的内容到此结束

感谢同学们的观看