一、密度聚类
基于距离的方法
– 适用于发现类球状的簇
– 在交通等领域，非球状簇的挖掘效果较差
– 判断是否“聚”的依据不仅仅有距离
基于密度进行聚类的思想
– 发现“密”的区域
– 判断密的区域的连通性
– DBSCAN（Density-Based Spatial Clustering of Applications with Noise）适应噪声的基于密度的空间聚类应用
对象的ε-临域
– 对象为中心、以ε为半径的空间（一定范围）
核心对象
– 如果一个对象的ε-临域至少包含最小数目MinPts个对象，则称该对象为核心对象（范围内点个数够多）
核心对象附近是比较“密”的
密的区域的连通性
直接密度可达
– 对于对象q和对象p，如果q是核心对象，p在q的ε-临域中，则称p是从q直接密度可达的。
密度可达
– 有对象链p1、p2、…pn，对于pi（1≤i≤ n-1），pi+1是从pi关于ε和MinPts直接密度可达的，则称pn是从p1密度可达的
密度相连
– 对于两个对象p1和p2，如果存在一个对象q，使得p1和p2都是从q关于ε和MinPts密度可达的，则称对象p1和p2是关于ε和MinPts密度相连的。
密度相连的对象闭集作为一个簇
– 对于一个簇C，任意两个对象oi，oj∈C，oi和oj是密度相连的，并且不存在对象om∈C和另一个对象on ∉C，om和on是密度相连的
基本过程（参数ε和MinPts ）
– 初始化，所有对象均被标记为“未处理”– 选择一个未处理的对象，判断其是否是核心对象
• 如果不是，则标记为“已处理”；
• 如果是，则新建一个簇；
• 将其ε-临域中的所有对象加入到该簇中，将该对象标记为“已处理”；
• 依次判断簇内所有“未处理”的对象是否是核心对象，重复前面过程，直到簇内所有对象均为“已处理”，输出该簇。
– 继续选择下一个未处理的对象，重复上述过程直至所有对象均为“已处理”，算法结束
DBSCAN评价：
– 适合发现任意形状的簇
– 易于发现噪声
– 无需预设k值
– 需要输入ε和MinPts
– 多大范围内有多少个点叫“密
优点
– 适合发现任意形状的簇，不受形状影响
– 易于发现簇的边界和噪声
DBSCAN局限
– 密度变化大
– 参数敏感
二、网格聚类
网格聚类
– 数据如果存在空间划分
– 根据空间结构进行聚类
STING统计信息网格
– 输入对象空间单元划分成网格– 支持空间层次结构
STING
– 高一级的每个网格在下一级被划分成若干较小的网格
– 每个网格的统计信息预先计算并存储
– 高阶单元的参数可以由下位单元的参数计算
– 使用自顶向下的方法
– 当前层，分析统计量，去除不满足的网格
– 进入下一层
– 重复上述过程直至到达底层
– 评价指标体系不同可能导致搜索和去除的差异
其他方法：CLIQUE
– 网格聚类与频繁模式挖掘（Apriori）结合
– 投影到低维上不稠密、高维上更不稠密
三、图聚类
图聚类
– 在一个图中，发现关联很密集的区域。比如社交网络发现小团体– 实际上是一个图的切割问题
最小割
– 切割代价最小– 是否最小割就是最优的划分？
切割选择
– 割的代价（切掉的边的代价）
– 切割的效果
– 如何使用数学公式来表示？
基于贪心思路的方法
– 选择最合适的切割
– 循环，直至终止条件
基于结构相似性的判别
– 假设前提：
密集小团体内部互联紧密
节点间相连结构是相似的
节点的邻域
– Γ(ν)
– 图上节点v相连的点和v自身构成的集合
结构相似性
SCAN算法
– 基于结构相似性– 类似密度聚类的思路
– 找出结构相似性高的点
– 然后连接生长
谱聚类Spectral Clustering
– 将样本看作顶点，样本间的相似度看作带权的边，将样本空间变成一个图– 聚类问题转为图分割问题：找到一种图分割的方法使得连接不同组的边的权重尽可能低（这意味着组间相似度要尽可能低），组内的边的权重尽可能高（这意味着组内相似度要尽可能高）
谱聚类过程
– 根据数据构造一个 Graph ，Graph 的每一个节点对应一个数据点，将相似的点连接起来，并且边的权重用于表示数据之间的相似度。把这个 Graph 用邻接矩阵的形式表示出来，记为W 。– 把W的每一列元素加起来得到N个数，把它们放在对角线上（其他地方都是零），组成一个N*N的矩阵，记为D。并令L=D-W。
– 求出L的前k个特征值（按照特征值的大小从小到大的顺序）以及对应的特征向量。
– 把这k个特征（列）向量排列在一起组成一个N*k的矩阵，将其中每一行看作k维空间中的一个向量，并使用 K-means 算法进行聚类。聚类的结果中每一行所属的类别就是原来 Graph 中的节点亦即最初的 个数据点分别所属的类别。
谱聚类原理
谱聚类
– 如何选择K？
– K>=2
– K的个数实际上决定了图被分割成几块
– 第k小的值意味着切分代价，实际上是簇的相似度
– 启发式方式决定k的取值
– 使用K-Means算法聚类，当然它不是唯一选择
五、离群点检测
离群点
– 一个与其他数据有着显著区别的数据对象的集合
离群点产生原因
– 度量或执行错误
– 噪声数据
– 特殊有意义的事件
离群点挖掘
– 给定一个n个数据对象的集合– 设定预期的离群点数目k
– 发现与剩余的数据有着显著差异的头k个数据对象
统计
– 统计的方法对于给定的数据集合假定了一个分布或概率模型（例如正态分布）– 使用依赖于以下参数的不一致性检验（discordancy tests）
• 数据分布
• 分布参数（e.g. 均值或方差）
• 预期的离群点数
– 缺点
• 绝大多数检验是针对单个属性的，而数据挖掘要求在多维空间中发现离群点
• 大部分情况下，数据分布可能是未知的
基于距离的离群点检测
– 为了解决统计学方法带来的一些限制，引入了基于距离的离群点检测• 在不知道数据分布的情况下对数据进行多维分析
– 基于距离的离群点：即DB(p,d)，如果数据集合S中的对象至少有p部分与对象o的距离大于d，则对象o就是DB(p,d)。
– 挖掘基于距离的离群点的高效算法：
• 基于索引的算法
• 嵌套－循环算法
• 基于单元的算法
基于偏离的离群点检测
– 通过检查一组对象的主要特征来确立离群点– 跟主要特征的描述相“偏离”的对象被认为是离群点
– 两种基于偏离的离群点探测技术
• 序列异常技术
– 模仿人类从一系列推测类似的对象中识别异常对象的方式
• OLAP数据立方体技术
– 在大规模的多维数据中采用数据立方体来确定异常区域。如果一个立方体的单元值显著的不同于根据统计模型得到的期望值，则改单元值被认为是一个异常，并用可视化技术表示
五、其他方法
其他聚类方法
– Wavecluster小波变换聚类
– 概念聚类
– CLIQUE维度增长子空间聚类
– PROCLUS维度归约子空间聚类
– 基于约束的聚类
– 双聚类