K-modes(补充） K-模，对k-平均方法的改进，k-原型的简化 处理分类属性 A Fast Clustering Algorithm to Cluster Very Large Categorical Data Sets in Data Mining,Zhexue Huang,1997 K-模，对k-平均方法的改进，k-原型的简化 处理分类属性 分类属性：A1,A2,…,Am为空间的m个属性， DOM(Ai)为属性的值域，如果DOM(Ai) 是确定和无序的，即对任何a，b A,只有a=b或者ab,则称Ai为分类属性 如果A1,A2,…,Am都为分类属性，则属性为分类空间

相异度度量 设X，Y为m个分类属性的分类对象，它们之间的相异度定义为： nxj为数据集中属性j上的值为xj的对象数 d(x,y)对一个属性上的每个类赋予了相同的权重 考虑属性出现的频率 对出现频率较低的类给予了更大的权重 nxj为数据集中属性j上的值为xj的对象数

数据集的模（mode） X={X1,X2,…Xn}的模: 向量Q=[q1,q2,…,qm],使得 最小 设X为一组分类对象，分类属性包括A1,A2,…,AM X={X1,X2,…Xn}的模: 向量Q=[q1,q2,…,qm],使得 最小 定理：函数D(Q,X)为最小，当且仅当 对所有的j=1,…,m有 Nck,j是在属性上Ai值为ck,j的对象数

K模算法 1.为每个簇选择初始模，共k个 2.根据d，把对象分配给最近的簇。根据定理重新计算簇的模 3.计算每个对象对当前模的相异度，重新分配对象到簇 4.重复上述2，3过程，直到簇中的对象不再发生变化

聚类分析 什么是聚类分析 聚类分析中的数据类型 主要聚类方法的分类 划分方法 层次方法 基于密度的方法 基于网格的方法 基于模型的方法 孤立点分析 小结

Chapter 8. Cluster Analysis 基于密度的方法 DBSCAN OPTICS DENCLUE 基于网格的方法 STING WaveCluster CLIQUE 基于模型的方法 统计学方法 神经网络方法 孤立点分析 小结

DBSCAN(基于高密度连接区域的密度聚类方法） Density-Based Spatial Clustering of Applications with Noise A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise Martin Ester,KDD-96

定义  = 1 cm 给定半径和MinPts ，每个聚类中的对象的-邻域中至少包含MinPts个对象 给定对象集合D  邻域N(q): 给定对象半径内的区域，即{q  D | dist(p,q) <= } 核心对象：q  D，|N(q)|MinPts 对象p从对象q出发是直接密度可达：pN(q)且|N(q)|  MinPts p q MinPts = 5  = 1 cm

定义（续） 对象p从对象q关于和MinPts密度可达：存在对象链p1，p2，…，pn，p1=q，pn=p，piD，pi+1是从pi关于和MinPts直接密度可达的（非对称） 对象p和q关于和MinPts密度相连：存在对象o D，使得对象p和q 从o关于和MinPts密度可达（对称） p q o p q p1

DBSCAN基本思想  = 1cm 簇：基于密度可达性的最大的密度相连对象的集合 噪音：不在任何簇中的对象 边界对象：不是核心对象，但在簇中，即至少从一个核心对象直接可达 核心对象 边界点 噪音  = 1cm MinPts = 5

DBSCAN算法 1）任意选择没有加簇标签的点 p 2）找到从p关于 and MinPts 密度可达的所有点 3）如果|N(q)|MinPts ，则p是核心对象,形成一个新的簇，给簇内所有的对象点加簇标签 4）如果p 是边界点, 则处理数据库的下一点 5）重复上述过程，直到所有的点处理完毕  = 1cm MinPts = 5

不足和改进 只能发现密度相仿的簇 对用户定义的参数（  and MinPts ）敏感 计算复杂度为O(n2) 采用R-树等空间索引技术，计算复杂度为o(nlogn)

图示 A 和 B被认为是噪音 C1和C2两个簇合并了

OPTICS OPTICS:Ordering Points To Identify the Clustering Structure（通过对象排序识别聚类结构） Mihael Ankerst .ACM SIGMOD’99 Int.Conf,1999 对DBSCAN的改进 对输入参数不敏感 可以发现不同密度的簇 用图表等可视化的方式来表示 按可达距离排序 可自动开采，也可与用户交互

引入两个新概念 P 为对象，数据集D，为距离值，N(q)为邻域，MinPts P 的核心距离：使得P成为核心对象的最小 P 关于对象q的可达距离：p的核心距离和p,q的欧几里得距离之间的较大值 若|N(q)| MinPts，即P不是核心对象，则无定义 否则，定义为Max（核心距离，|（p,q）|）

图示 核心距离 可达距离

OPTICS算法 1.计算数据点p的核心距离和可达距离 2.如果p为核心对象，找到所有它的关于 和MinPts的直接密度可达点，按可达距离排序并插入队列。 3.处理下一个数据点

寻找簇 Reachability-distance undefined ‘ Cluster-order of the objects

不同密度、形状、大小的簇

参数的影响 减小，则可达距离为无穷大的点增多； MinPts减小，核心对象增多，图象更尖锐

确定参数  MinPts 经验值：10-20

DENCLUE DENsity-based CLUstering An Efficient Application to Clustering in Large Multimedia Databases with Noise（在带噪音的大型多维数据库上的高效的聚类方法） Alexander Hinnebug,1998

数学基础 1.影响函数描述了一个数据点在邻域的影响 2.数据空间的整体密度函数为所有数据点的影响函数之和 3.聚类可以通过确定密度吸引点来得到，密度吸引点为密度函数的局部最大

影响函数 假设x 和y是特征空间中的对象。数据对象y对x的影响函数为 原则上影响函数可以是任意的函数，它由邻域内的两个对象之间的距离决定 方波影响函数 高斯函数 一个点x是被一个密度吸引点y密度吸引的:如果存在一组点x0,…,xk,x0=x,xk=y,对0<i<k,xi-1的梯度是在xi的方向上的 一个梯度指导的爬山算法可用来计算一组数据点的密度吸引点

梯度和密度吸引点

爬山算法 1.在收缩空间随机选择一点. 2.考虑当前状态的所有邻域 3.选择最佳的邻域，当前状态转向它 4.重复过程2，3，直到当前状态为邻域中最佳 5.返回当前状态作为结果

对一个2维数据集的可能的密度函数

簇 密度吸引点x的中心定义的簇是一个被x密度吸引的子集C，在x的密度函数不小于阈值；否则它被认为是孤立点 一个任意形状的簇是子集C的集合，每一个都是密度吸引的，有不小于阈值的密度函数值；并从每个区域到另一个都存在一条路径p，路径上的每个点的密度函数值都不小于

Chapter 8. Cluster Analysis 基于密度的方法 DBSCAN OPTICS DENCLUE 基于网格的方法 STING WaveCluster CLIQUE 基于模型的方法 统计学方法 神经网络方法 孤立点分析 小结

STING STatistical Information Grid (统计信息网格方法） STING: A Statistical Information Grid Approach to Spatial Data Mining Wei Wang,Los Angeles,1997

主要思想 数据空间区域被划分为矩形单元 对应于不同级别的分辨率，存在着不同级别的矩形单元：高层的每个单元被分为多个低一层的单元。 每个网格单元的统计信息被预先计算和存储，以供处理查询之用

统计信息（1） n（网格中的对象数）， m（平均值），s（标准偏差），min（最小值），max（最大值）

统计信息（2） 分布类型（type of distribution) 假设dist为大多数数据点的分布类型，confl为分布类型不同的数据点的个数 1.distidist，mim，sis，则conflconfl+ni 3. distidist，mim，sis，则confl  confl 4. mim，sis中有某个不成立，则confl n 如果 ,（t为一个指定域值），则dist为NONE. 否则，dist不变.

统计信息（3） n=220 dist4dist m=20.27 confl=10 s=2.37 confl/n=0.045<0.05 min=3.8 max=40 dist=normal

自顶向下地回答查询 1.从层次中选定一层（包含较少的单元）作为查询处理的开始。 2.对当前层次的每个单元，计算置信度区间，用以反映该网格单元与给定查询的关联程度 3.当前层次处理完毕，转低一层，直至底层

优缺点 独立于查询 有利于并行处理和增量更新 计算统计信息的复杂度为o(n),n为对象数，查询处理事件的复杂度为o(g),g为最低层的网格数，g<<n 聚类的质量取决于网格最低层的粒度 所有聚类边界为水平或垂直的 降低了簇的质量和精确性

Wavecluster(小波变换） Wavecluster：基于大型空间数据库的多分辨率的聚类方法（the 24th VLDB Conference,NewYork,USA,1998) 基于网格和密度的 多维空间数据对象可以用多维特征空间来表示。从信号处理的角度来看，n 维特征空间的对象就是n维的信号。 信号的高频率区：对象分布情况变化剧烈的区域，即孤立点 信号的低频率高振幅区：对象分布密集区，即簇 n维信号的变换用多次 的一维小波变换来实现

小波变换的原理 通过过滤，可以给出信号的瞬间频率值 一维信号S与过滤系数Ck卷积 M:过滤系数的个数 Ck：过滤系数 S：输入信号

Wavecluster 分类算法 输入：多维数据对象的特征向量 输出：聚类的对象 1.量化特征空间，把对象分配到各个单元 2.对各个单元做小波变换 3.按照不同的分辨率，在变换后的子波带中找到簇 4.给簇加类标签 5.生成查找表 6.给对象加类标签

量化 有d维的特征空间，每一维分成m个间隔，设每一维的m是相等的，且mi=m，则共有单元md个。 Fk=（f1，f2，…，fd）是对象o的原始特征向量，Mj=（v1，v2，…，vd）是一个在原始特征空间的单元，1vimi，1id，是单元Mi在向量轴上的位置 若 i（vi-1）*sifivi*si，1id，则对象ok在单元Mj中

图示 A0为输入信号， 为低通过滤器， 为高通过滤器 Dj为详细信号（detail signal），反映孤立点信息 Ai为平均信号（average signal），反映簇的信息 Ai的分辨率比Ai+1要高

加类标签，查找表 c Tk，Tkc  lTk=cn，ccr lTk为经小波变换后的单元Tk的类标签 簇的标签不能直接用于原始空间 c Mj，oiMj，loi=cn，ccr，1iN loi是对象oi的类标签

特性 时间复杂度（NK） 1）扫描数据库，分配空间： O（N） 2）设K=md，做小波变换：O（K） 3）标签：O（K），LT表：O（K） 4）加类标签：O（N）

多分辨率 强调平均领域 强调水平边 强调转角 强调垂直边

任意形状的簇的发现

小波变换的优点 无监督分类：hat-shape过滤，没有事先假定的聚类形状，边界的弱信息不会屏蔽 剔除孤立点：采用低通过滤，对信号中的高低频分量通低不通高 多分辨率：不同的变换次数产生不同的分辨率 高效率：本身运算开销不大，并可以采用并行处理 处理高维数据，多达20维

CLIQUE CLIQUE:Clustering In QUEst,1998 给定多维数据集合，数据点在数据空间中不是均衡分布的。 如果一个单元中的包含数据点超过了某个输入模型参数，则该单元是密集的。 簇：相连的密集单元的最大集合

主要步骤 1.将数据空间划分为互不相交的长方形单元，记录每个单元里的对象数 2.用先验性质识别包含簇的子空间 3.识别簇： 在符合兴趣度的子空间中找出密集单元 在符合兴趣度的子空间中找出相连的密集单元 4.为每个簇生成最小化的描述 先验性质：如果一个K维单元是密集的，那么它在k-1空间上的投影也是密集的。即给定一个k维的侯选密集单元，如果检查它的k-1维投影空间，发现任何一个不是密集的，那么知道第k维的单元也不可能是密集的。

关于age对salary和vocation维的密集单元，这些密集单元相交形成更高维度密集单元的一个侯选搜索空间 20 30 40 50 60 age 5 4 3 1 2 6 7 Vacation Salary  = 3 Vacation(week) 关于age对salary和vocation维的密集单元，这些密集单元相交形成更高维度密集单元的一个侯选搜索空间

有效性和缺点 自动地发现最高维的子空间，高密度聚类存在于这些子空间中。 对元组的输入顺序不敏感，无需假设任何规范的数据分布 随输入数据的大小线形地扩展，当数据的维数增加时具有良好的可伸缩性 聚类结果的精确度降低

Chapter 8. Cluster Analysis 基于密度的方法 DBSCAN OPTICS DENCLUE 基于网格的方法 STING WaveCluster CLIQUE 基于模型的方法 统计学方法 神经网络方法 孤立点分析 小结

基于模型的聚类方法 试图优化给定的数据和某些数学模型之间的适应性 假设：数据是根据潜在的概率分布生成的 统计学方法 神经网络方法

统计学方法 概念聚类 COBWEB 机器学习中的一种聚类方法，给出一组未标记的对象。 产生对象的一个分类模式 为每组对象发现了特征描述（分类） COBWEB 简单增量概念聚类算法 以分类树的形式创建层次聚类 每个节点代表一个概念，包含对概念的概率描述

分类效用(Category Utility) 概率表示 类内相似性。该值越大，共享该属性-值对的类成员比例就更大。 概率表示 类间相异性。该值越大，在对照类中共享该属性-值对的类成员比例就更大。 分类效用： N是在树的某个层次上形成的一个划分{C1,C2,…,Ck}的节点、概念或“种类”的数目。 在给定的划分中能够正确猜测期望的属性值的数目中，分类效用是随没有此种知识时期望的正确猜测的树木而增加的。

COBWEB：分类树

分类树的节点插入 将对象临时置于每个节点，并计算结果划分的分类效用。产生最高分类效用的位置是对象节点的好的选择 计算为给定对象创建一个新的节点所产生的分类效用，与基于现存节点的计算相比较。 根据产生最高效用的划分，对象被置于一个已存在的类，或者为它创建一个新类。

优缺点 假设每个属性上的概率分布是彼此独立的。 聚类的概率分布表示使得更新和存储聚类相当昂贵 时间和空间复杂度取决于属性的数目、每个属性的值的数目 对偏斜的数据输入不是高度平衡的，可能导致空间和时间复杂性的剧烈变化 不适合大数据库

神经网络方法 将每个簇描述为一个标本（examplar），作为聚类的原型 根据某些距离度量，新的对象被分配给标本与其最相似的簇 竞争学习(competitive learning) 自组织特征映射

竞争学习 采用了若干个单元的层次结构（神经元） 神经元以一种“胜者全取”的方式对系统当前处理的对象进行竞争 1.激发式的连接（excitatory）：在某个给定层次中的单元可以接收来自低一层次所有单元的输入。 2.每一层中活动单元的布局代表了高一层的输入模式 3.一个层次内的联系是抑制式（inhibitory）的，在某个给定的层次中，一个簇中的单元彼此竞争，对低一层的输入模式做出反应 4.获胜的单元修正它与簇中其他单元连接上的权重，以便它能够对与当前对象相似或一样的对象做出较强的反应 每个簇可被看成一个新的低层特征向高层特征的映射

输入模式 层3抑制簇 层2抑制簇 层1输入单元 激发联接

自组织特征映射 Self-Organizing feature Map(SOM) 通过若干个单元竞争当前对象来进行聚类 权重向量最接近当前对象的单元为获胜或活跃的单元 对获胜单元及其最近的邻居的权重进行调整 类似大脑的处理过程 用于可视化高维数据

神经元网络的结构 竞争层 Competitive layer 输出层 Output layer

输入层： 竞争层： 输出层： 接受多维输入模式，每个输入模式即一个向量 输入层的每个神经元代表输入模式的一个维 输入层的神经元把它得到的输入向量传给竞争层 竞争层： 竞争层的神经元接受来自输入层向量的加权和 每个神经元有它的邻域，包括一组其它的神经元 给定一个输入，某些神经元可被激活，这些神经元可抑制或激发它的邻域内的神经元 生物上的“on-center,off-surround”结构，lateral feedback/inhibition 输出层： 输出层的组织依赖于具体的应用程序

数学模型 输入向量为v=(v1,v2,…,vn) 竞争层的每个单元i都有一个相关的权重向量：w=(w1,w2,…,wn) 则每个神经元的输入为 可见，输入为标量，即权重向量与输入向量的点乘

数学模型（续） 计算角度angle(v,w)以决定“胜出”的神经元

初始化 训练集的选择： 神经元权重初始化： 神经元网络构建的很重要的环节 反映输入数据的概率分部 将训练集里的数据随机化 对训练集中至少一个输入有“获胜”的机会，或在获胜单元的邻域中

性能 无监督学习 复杂度大大降低 系统是个黑盒 需要很大的训练集 结果有时不易理解 多维的竞争层不一定收敛

Chapter 8. Cluster Analysis 基于密度的方法 DBSCAN OPTICS DENCLUE 基于网格的方法 STING WaveCluster CLIQUE 基于模型的方法 统计学方法 神经网络方法 孤立点分析 小结

孤立点分析 孤立点：与数据的其他部分不同的数据对象 一个人的噪音是另一个人的信号 信用卡欺诈探测、收入极高或极低的客户分区、医疗分析 孤立点挖掘 在给定的数据集合中定义什么样的数据为不一致的 找到一个有效的方法来挖掘孤立点 统计学方法 基于距离的方法 基于偏移的方法

基于统计的孤立点检测 工作假设（working hypothesis) N个数据对象的整个数据集合来自一个初始的分布模型F 不一致检测 缺点 数据分布 分布参数（平均值、变量等） 孤立点数目的期望值 缺点 只能在单属性上作检测 大部分情况下，数据分布未知

基于距离的孤立点检测 解决了统计方法的主要缺陷 基于距离的DB（p,d）孤立点：数据集合T中至少有p部分与对象o的距离大于d 主要算法 在未知数据分布状态下做多维数据分析 基于距离的DB（p,d）孤立点：数据集合T中至少有p部分与对象o的距离大于d 主要算法 基于索引的算法 嵌套－循环算法 基于单元的算法

基于偏离的孤立点检测 检查组中对象的主要特征 偏离主要特征的对象被认为是孤立点 序列异常技术（sequential exception technique ） 模仿了人类从一系列推测类似的对象中识别异常对象的方式 OLAP数据立方体方法（ OLAP data cube technique） 在大型多维数据中使用数据立方体来确定反常区域

Chapter 8. Cluster Analysis 基于密度的方法 DBSCAN OPTICS DENCLUE 基于网格的方法 STING WaveCluster CLIQUE 基于模型的方法 统计学方法 神经网络方法 孤立点分析 小结

小结 什么是聚类分析 聚类分析中的数据类型 主要聚类方法的分类 划分方法:k-means 层次方法: 基于密度的方法:DBSCAN,OPTICS,DENCLUE 基于网格的方法:STING,WAVECLUSTER,CLIQUE 基于模型的方法:SOM 孤立点分析