数据挖掘课件-数据聚类

1 第 8章 数据聚类 2 3.1 引言 3.2 相似性度量 3.3 聚类准则 3.4 基于试探的两种聚类算法 3.5 系统聚类法 3.6 动态聚类 3.7 聚类评价 主要内容 3 3.1 引言 聚类：将数据分组成为多个类别，在同一个类内对 象之间具有较高的相似度，不同类之间的对象差别 较大。 根据各个待分类的模式特征相似程度进行分类， 相 似 的归为一类，不相似的作为另一类。 监督学习： 需要用训练样本进行学习和训练 非监督学习：对于没有类别标签的样本集，根 据该问题本身的目的和样本的特性，把全体 N 个样本划分为若干个子集，同类样本特性相差 小，异类样本特性相差大。 4 聚类应用 花瓣的“物以类聚” 5 聚类应用 早在孩提时代，人就通过不断改进下意识中的聚类 模式来学会如何区分猫和狗，动物和植物 谁经常光顾商店，谁买什么东西，买多少？ 按照卡记录的光临次数、光临时间、性别、年龄、 职业、购物种类、金额等变量分类 这样商店可以 . 识别顾客购买模式（如喜欢一大早来买酸奶和鲜肉， 习惯周末时一次性大采购） 刻画不同的客户群的特征 6 聚类应用 挖掘有价值的客户，并制定相应的促销策略： 如，对经常购买酸奶的客户 对累计消费达到 12个月的老客户 针对潜在客户派发广告，比在大街上乱发传单 命中率更高，成本更低！ 7 聚类应用 谁是银行信用卡的黄金客户？ 利用储蓄额、刷卡消费金额、诚信度等变量对客户分 类，找出 “ 黄金客户 ” ！ 这样银行可以制定更吸引的服务，留住客户！比如： 一定额度和期限的免息透支服务！ 商场的贵宾打折卡！ 在他或她生日的时候送上一个小蛋糕！ 8 聚类应用 经济领域： 帮助市场分析人员从客户数据库中发现不同的客户群， 并且用购买模式来刻画不同的客户群的特征。 谁喜欢打国际长途，在什么时间，打到那里？ 对住宅区进行聚类，确定自动提款机 ATM的安放位置 股票市场板块分析 生物学领域 推导植物和动物的分类； 对基因分类，获得对种群的认识 数据挖掘领域 作为其他数学算法的预处理步骤，获得数据分布状况， 集中对特定的类做进一步的研究 9 聚类分析原理 聚类分析中 “ 类 ” 的特征： 聚类所说的类不是事先给定的，而是根据数据的 相似性和距离来划分 聚类的数目和结构都没有事先假定 10 聚类分析原理 聚类方法的目的是寻找数据中： 潜在的 自然分组结构 感兴趣的 关系 11 聚类分析原理 什么是 自然分组结构 ? 有 16张牌，如何将他们分组呢？ A K Q J 12 聚类分析原理 分成四组：每组里 花色相 同 ，组与组之间花色相异 A K Q J 花色相同的牌为一组 13 聚类分析原理 分成四组， 符号相同 的 牌为一组 A K Q J 符号相同的的牌为一组 14 聚类分析原理 分成两组， 颜色相同 的 牌为一组 A K Q J 颜色相同的牌为一组 15 聚类分析原理 分组的意义在于我们怎么定义并度量 “相似性” 因此衍生出一系列度量相似性的算法 16 聚类分析原理 相似性的度量（统计学角度） 距离 Q型聚类（主要讨论） 主要用于对样本分类 常用的距离有： 明考夫斯基距离 (包括：绝对距离、欧式距离、切比 雪夫距离 ) 兰氏距离 马氏距离 斜交空间距离 此不详述，可参考 应用多元分析 （第二版）王 学民 17 聚类分析原理 相似系数 R型聚类 用于对变量分类，可以用变量之间的相似系数 的变形，如 1 rij定义距离 18 聚类分析原理 变量按测量尺度分类 间隔尺度变量 连续变量，如长度、重量、速度、温度等 有序尺度变量 等级变量，不可加，但可比，如一等、二等、三 等奖学金 名义尺度变量 类别变量，不可加也不可比，如性别、职业等 19 3.2 相似性度量 聚类分析符合“物以类聚，人以群分“的原则，它 把相似性大的样本聚集为一个类型 聚类分析的关键问题：如何在聚类过程中自动地确 定类型数目 20 相似性度量 21 相似性度量 距离相似性度量 角度相似性度量 22 距离相似性度量 模式样本向量与之间的欧氏距离定义为： 若距离阈值 ds选择过大，则全部样本被视作一 个唯一类型；若 ds选取过小，则可能造成每个 样本都单独构成一个类型 d i iie yxyxyxD 1 2|),( 23 距离相似性度量 距离阈值对聚类的影响 24 距离相似性度量 特征选取不当使聚类无效 特征选取不足引起误分类 模式特征坐标单位的选取也会强烈地影响聚类 结果 25 距离相似性度量 特征选取不当使聚类无效 1 2 26 距离相似性度量 特征选取不足引起误分类 1 2 3 27 距离相似性度量 a c b d 28 解决尺度问题 标准化 iiy x m s m i n m a x m i ni i i i iy x x x x m a x m i ni i i iy x x x iiy x a 29 解决尺度问题 为了进行聚类，我们需要一种合适的距离度量尺 度。 这种距离度量尺度依赖于特征标准化方法 为了选择标准化方法我们必须知道聚类的类型 试错法是唯一的避免这种恶性循环的方法。选择 不同的条件进行试验，通过观察、数据解释和效 用分析评价相应的解。平衡各特征值的贡献，并 保持原有的语义信息。 30 角度相似性度量 样本与之间的角度相似性度量定义为它们之间夹角 的余弦 |c o s),( yx yxyxS T 31 3.3 聚类准则 相似性度量 集合与集合的相似性 相似性准则 分类效果好坏的评价准则 聚类准则 : 试探法 定义一种相似性度量的阈值 聚类准则函数法 聚类准则是反映类别间相似性或分离性的函数 误差平方和准则（最常用的） 加权平均平方距离和准则 32 误差平方和准则 假定有混合样本 X=x1, x2, , xn 采用某种相似性度量， X被聚合成 c个分离开的子集 X1, X2, , Xc。每个子集是一个类型，它们分别包含 n1, n2, , nc个样本 为了衡量类的质量，采用误差平方和 Jc聚类准则函数， 定义为： mj为类型 Xj中样本的均值， mj是 c个集合的中心，可 以用来代表 c个类型。 33 误差平方和准则 误差平方和准则适用于各类样本比较密集且样本数 目悬殊不大的样本分布 34 误差平方和准则 例： 35 加权平均平方距离和准则 定义加权平均平方距离和准则： 式中： Sj*是类内样本间平均平方距离 c j jjj SPJ 1 * j jXx Xxjj j xxnnS 2* | )1( 2 Xj中的样本个数 nj， Xj中的样本两两组合共有 nj(nj- 1)/2种 表示所有样本之间距离之和 Pj为 j类的先验概率，可以用样本数目 nj和样本总 数目 n来估计， Pj=nj/n, j=1,2, c 2 j jXx Xx xx 36 加权平均平方距离和准则 例： 37 3.4 基于试探的两种聚类算法 采用最近邻规则的聚类算法 最大最小距离聚类算法 38 采用最近邻规则的聚类算法 选取距离阈值 T，并且任取一个样本作为第一个聚 合中心 Z1，如： Z1=x1 计算样本 x2到 Z1的距离 D21 若 D21T，则 x2 Z1，否则令 x2为第二个聚合中心， Z2=x2 设 Z2=x2，计算 x3到 Z1和 Z2的距离 D31和 D32，若 D31T 和 D32T，则建立第三个聚合中心 Z3。否则把 x3归于 最近邻的聚合中心。依此类推，直到把所有的 n个 样本都进行分类。 按照某种聚类准则考察聚类结果，若不满意，则重 新选取距离阈值 T、第一个聚合中心 Z1，返回 ， 直到满意，算法结束。 39 采用最近邻规则的聚类算法 最近邻规则的聚类算法：计算模式特征矢量到 聚类中心的距离，和门限 T比较，决定归属哪类 或作为新的聚类中心。 该算法的优点是简单，如果有样本分布的先验 知识用于指导阈值和起始点的选取，则可较快 得到合理结果。 算法的结果在很多程度上取决于第一个聚合中 心的选取和距离阈值的大小。 40 阈值对聚类的影响 41 起始点对聚类的影响 Z=x1 Z=x5 Z=x7 42 最大最小距离聚类算法 若 Dk1=maxDi1，则取 xk为第二个聚合中心 Z2，计算所有样 本到 Z1和 Z2的距离 Di1和 Di2。 若 Dl=maxmin(Di1, Di2)， i=1,2, n，并且 DlD12， D12为 Z1和 Z2间距离，则取 xl为第三个聚合中心 Z3。 注意： Di1=|xi-Z1|， Di2 =|xi-Z2|。 如果 Z3存在，则计算 Dj=maxmin(Di1, Di2, Di3), i=1, 2, , n， 若 DjD12，则建立第四个聚合中心。依此类推，直到最大 最小距离不大于 D12时，结束寻找聚合中心的计算。 给定 ， 01，并且任取一个样本作为第一个聚合中心， Z1=x1 寻找新的聚合中心，计算其它所有样本到 Z1的距离 Di1 43 最大最小距离聚类算法 按最近邻原则把所有样本归属于距离最近的聚 合中心 按照某聚类准则考查聚类结果，若不满意，则 重新选择 ，第一个聚合中心，返回到 ，直到 满意，算法结束。 最大最小距离聚类算法：在模式特征矢量集中 以最大距离原则选取新的聚类中心，以最小距 离准则进行模式归类。 独立性能不好，依赖先验知识。 44 最大最小距离聚类算法 例： 45 最大最小距离聚类算法 46 3.5 系统聚类法 (层次化聚类 ) 融合算法 会在每一步减少聚类中心数量，聚类产生的 结果来自于前一步的两个聚类的合并； 分裂算法 在每一步增加聚类中心的数量，每一步聚类 产生的结果，都是将前一步的一个聚类中心 分裂成两个得到。 47 层次聚类 分裂或凝聚 算法运行到某一阶段，类别划分结果达到聚类标准时 即可停止分裂或凝聚 ; 48 融合算法 融合算法基本思想： 给定 n个样本 xi，最初把每个样本看成一类 i=xi，设聚类数 c=n 当 c1时，重复进行以下操作： 利用合适的相似性度量尺度和规则确定最相 近的两个聚类 i 和 j 合并 i和 j： ij=i,j，从而得到一个类别 数为 c-1的聚类解 将 c值递减 注意：在确定最近的两个聚类时，需要同时依 靠相似性度量和用于评价聚类相似性的规则。 49 融合算法 设初始模式样本共有 N个，每个样本自成一类，即建立 N类： G1(0), G2(0), , GN(0)。计算各类之间（在起始时也就是各个 样本之间）的距离，可得一个 N*N维的距离矩阵 D(0) 如在距离运算中心已求得距离矩阵 D(n)，则求 D(n)中的最 小元素。如果它是 Gi(n), Gj(n)两类之间的距离，则将 Gi(n), Gj(n) 两类合并为一类 Gij(n+1)。由此建立新的分类 G1(n+1), G2(n+1), 。 计算合并后的新类别之间的距离，得 D(n+1)。计算 Gij(n+1)与其 他没有发生合并的 G1(n+1), G2(n+1), 之间的距离时，有多种 不同的距离计算准则。 跳到 ，重复计算合并，可一直将全部样本聚集成一类。 50 融合算法 视 N个模式各成为一类，计算类与类之间的距离， 选择距离最小的一对合并成一个新类，计算在新 的类别分划下各类之间的距离，再将距离最近的 两类合并，直至所有模式聚成两类为止。 51 融合算法 例：给出 6个样本待征矢量如下，按最小距离原则进 行聚类。 x1=(0,3,1,2,0)T x2=(1,3,0,1,0)T x3=(3,3,0,0,1)T x4=(1,1,0,2,0)T x5=(3,2,l,2,1)T x6=(4,1,1,1,0)T 52 选择距离函数的形式 选择聚类的方法 输入 N 个模式样本 的特征向量 计算 N * N 维 距离矩阵 D ( 0 ) 设置迭代次数 n = N 按不同的距离函数计 算求距离矩阵中的元 素 ， 将二类合并 。 建 立新的距离矩阵 D ( n + 1 ) n = n - 1 n = 0 输出聚类的分级树 是 否 53 融合算法 系统聚类过程可绘成树状表示，如图所示 54 融合算法 聚类 1 = Aveiro, Setubal, V.Castelo； 财产方面的高犯罪率，超过对人身安全方面的犯罪率； 聚类 2=Beja, Braga, Braganca, Coimbra, Porto, Santarem, Viseu； 财产方面的高犯罪率，低于对人身安全方面的犯罪率。 聚类 3=C.Branco, Evora, Faro, Guarda, Leiria, Lisboa, Portalegre, V.Real；财产和人身安全方面的平均水平的犯罪率。 55 融合算法 w1=I， D w2=A， B， C， E， F， G， H w3=8， 9 w4=1， 2， 3， 4， 5， 6， 7 56 融合算法改进 可将类间距离门限 T作为停止条件，当 D (k)中最小 阵元大于 T时，聚类过程停止； 也可将预定的类别数目作为停止条件，在类别合 并过程中，类数等于预定值时，聚类过程停止。 57 层次化聚类联接规则 联接规则：衡量聚类之间相异程度的方法。 单联接 完全联接规则 类间平均联接规则 类内平均联接规则 Ward方法 , m i n ijij xy d x y , m a x ij ij xyd x y 1, ij ij xyij d x ynn , 1, ,2 ijij xyijd x yC n n 2 , 1, ij ij xij d x mnn 58 最短距离法 理论基础 最短距离法认为，只要两类的最小距离小于阈值，就 将两类合并成一类。定义 DI,J为 wi类中所有样品和 wj 类中所有样品间的最小距离，即 其中 dUV表示 wi类中的样品 U与 wj类中的样品 V之间 的距离。若 wj类是由 wm、 wn两类合并而成的，则 59 递推可得 计算 w1到 w3,4的距离 D1,34，先计算 w1类中各 个样品到 w3类中各个样品的距离，取最小值为 D1,3；然后计算 w1类中各个样品到 w4类中各个 样品的距离，取最小值为 D1,4；取 D1,3、 D1,4 中的最小值为 D1,34。 60 实现步骤 获得所有样品特征。 输入阈值 T（计算所有样品距离的最大值与最小值，输出， 作为阈值的参考）。 将所有样品各分一类，聚类中心数 centerNum=样品总数， m_pattern(i).category=i； m_center(i).feature=m_pattern(i).feature。 对所有样品循环： 找到距离最近的两类 pi、 pj，设距离为 minDis。 若 minDisT，则合并 pi、 pj，将类号大的归入到类号小的 类中，调整其他类保持类号连续。否则 minDisT，两类间的 最小距离大于阈值，则退出循环。 61 最长距离法 理论基础 在该算法中，两类中的所有样品间的距离必须都小 于阈值，才能将两类合并。定义 Di,j为 wi类中所有 样品与 wj中所有样品间的最大距离，则有 Di,j=maxd U v , d U v:wi类中的样品 U与 wj类 中的样品 V之间的距离。 若 wj是由 wm,wn两类合并而成，则 Di,j = maxDi,m , Di,n 62 实现步骤 获得所有样品的特征值。 输入阈值 T 将所有样品各分一类，聚类中心数为 centerNum,样品总数为 patternNum. 对所有样品循环： 计算所有聚类中心的距离，两类间的距离等于两类间样 品的最大距离 maxdis 取所有 maxDis中的最小值，设 pi类和 pj类的距离最小， 为 minDis. 若 minDisT,所有类间距离均大于阈值，则推出循环， 归类完成。 中间距离法 理论基础 最短距离法和最长距离法采用的是分类距离的两个 极端。中间距离法则介于两者之间，若 wj类是由 wm、 wn两类合并而成，则 wi、 wj两类的中间距 离定义为 例如，计算距离 D1,34，先计算 w1类中各个样品 到 w3类中各个样品的距离 D1,3，然后计算 w1类中 各个样品到 w4类中各个样品的距离 D1,4，按照下 式计算 D1,34： 实现步骤 获得所有样品特征。 输入阈值 T（计算所有样品距离的最大值与最小值，输出， 作为阈值的参考）。 将所有样品各分一类，聚类中心数 centerNum=样品总 数， m_pattern(i).category=i； m_center(i).feature=m_pattern(i).feature。 建立距离矩阵 centerDistance，记录各类间的距离，初 始值为各样品间的距离。 对所有样品循环： 找到 centerDistance中的最小值 td=centerDistance(ti, tj)，即 ti类和 tj类距离最小。 若 tdT，则将所有 tj类成员归入 ti类； centerNum=centerNum-1；重新顺序排列类号；根据 上式重新计算距离矩阵 centerDistance，否则（ tdT）终 止循环，分类借宿。 65 3.6 动态聚类算法 动态聚类算法选择若干样品作为聚类中心，再按 照某种聚类准则，如最小距离准则，将其余样品 归入最近的中心，得到初始分类。 然后判断初始分类是否合理，若不合理则按照特 定的规则重新修改不合理的分类，如此反复迭代， 知道分类合理。 66 3.6 动态聚类算法 算法首先选择某种样本相似性度量和适当的聚类准 则函数，使用迭代算法，在初始划分的基础上，逐 步优化聚类结果，使准则函数达到极值。 算法要解决的关键问题： 首先选择有代表性的点作为起始聚合中心。若类 型数目已知，则选择代表点的数目等于类型数目； 若未知，那么聚类过程要形成的类型数目，是一 个问题。 代表点选择好之后，如何把所有样本区分到以代 表点为初始聚合中心的范围内，形成初始划分 67 动态聚类算法 k-均值聚类算法使用的聚类准则函数是误差平方 和准则： c j n k jkc j mxJ 1 1 2| k-均值聚类算法 ISODATA算法 68 K-均值算法：理论基础 K均值算法能够使聚类域中所有样品到聚类中心距 离的平方和最小。 原理： 先取 K个初始距离中心，计算每个样品到这个 K个中 心的距离，找出最小距离把样品归入最近的聚类中心。 修改中心点的值为本类所有样品的均值，再计算各个 样品到 k个中心的距离，重新归类，修改新的中心点。 直到新的距离中心等于上次的中心点结束。 69 k-均值聚类算法 70 k-均值聚类算法 算法特点： 每次迭代中都要考查每个样本的分类是否正确，若 不正确，就要调整，在全部样本调整完之后，再修 改聚合中心，进入下一次迭代。如果在某一个迭代 运算中，所有的样本都被正确分类，则样本不会调 整，聚合中心也不会有变化，也就是收敛了。 初始聚合中心的选择对聚类结果有较大影响。 71 k-均值聚类算法 例：现有混合样本集，共有样本 20个，分布如下图 所示，类型数目 c=2。试用 k-均值算法进行聚类分析 72 k-均值聚类算法 73 改进 k-均值算法 (c-均值算法 ) 74 75 k-均值聚类算法 k-均值算法的结果受如下选择的影响： 所选聚类的数目 聚类中心的初始分布 模式样本的几何性质 读入次序 在实际应用中，需要试探不同的 K值和选择不同的 聚类中心的起始值。 如果模式样本可以形成若干个相距较远的小块孤 立的区域分布，一般都能得到较好的收敛效果。 k-均值算法比较适合于分类数目已知的情况。 76 ISODATA 此算法与 K均值算法有相似之处，即聚类中心也是 通过样品均值的迭代运算来决定的。但 ISODATA 加入了一些试探性的步骤。能吸取中间结果所得 到的经验，在迭代过程中可以将一类一份为二， 也可将两类合并，即自组织，具有启发性。 77 ISODATA算法 基本步骤和思路 (1)选择某些初始值。可选不同的指标，也可在迭代 过程中人为修改，以将 N个模式样本按指标分配到 各个聚类中心中去。 (2)计算各类中诸样本的距离指标函数。 (3)(5)按给定的要求，将前一次获得的聚类集进行 分裂和合并处理 (4)为分裂处理， (5)为合并处理 )， 从而获得新的聚类中心。 (6)重新进行迭代运算，计算各项指标，判断聚类结 果是否符合要求。经过多次迭代后，若结果收敛， 则运算结束。 78 迭代自组织数据分析 (ISODATA)算法 与 k-均值算法的比较 k-均值算法通常适合于分类数目已知的聚类，而 ISODATA算法则更加灵活； 从算法角度看， ISODATA算法与 K-均值算法相似， 聚类中心都是通过样本均值的迭代运算来决定的； ISODATA算法加入了一些试探步骤，并且可以结 合成人机交互的结构，使其能利用中间结果所取 得的经验更好地进行分类。 79 3.7 聚类评价 聚类中心间的距离 距离值大，通常可考虑分为不同类 每个聚类域中的样本数目 样本数目少且聚类中心距离远，可考虑是否为噪声 每个聚类域内样本的距离方差 方差过大的样本可考虑是否属于这一类 80 81 82 上机要求 1.编写最近邻规则的聚类算法程序 2.编写 k-均值的聚类算法程序