手工做衣服网站有哪些,网站做推广赚钱项目,网站开发 建设叫什么,企业网站模板下载软件目录 一、聚类分析原理#xff08;一#xff09;聚类分析概述#xff08;二#xff09;聚类的数学定义#xff08;三#xff09;簇的常见类型#xff08;四#xff09;聚类框架及性能要求#xff08;五#xff09;簇的距离 二、划分聚类算法#xff08;一#xff0… 目录 一、聚类分析原理一聚类分析概述二聚类的数学定义三簇的常见类型四聚类框架及性能要求五簇的距离 二、划分聚类算法一划分聚类框架二划分聚类的质量三k-means算法四空簇与离群点五k-中心点算法 聚类分析 (clustering analysis) 是数据挖掘研究最为活跃、内容最为丰富的领域之一其目的是通过对数据的深度分析将一个数据集拆分成若干个子集 (每个子集称为一个簇cluster)使得同一个簇中数据对象 (也称数据点) 之间的距离很近或相似度较高而不同簇中的对象之间距离很远或相似度较低。
一、聚类分析原理
一聚类分析概述 聚类分析 (clustering analysis) 就是根据某种相似性度量标准将一个没有类别标号的数据集 S S S (表10-1) 直接拆分成若干个子集 C i ( i 1 , 2 , ⋯ , k ; k ≤ n ) C_i (i1,2, \cdots,k; k≤n) Ci(i1,2,⋯,k;k≤n)并使每个子集内部数据对象之间相似度很高而不同子集的对象之间不相似或相似度很低。每个子集 C i C_i Ci 称为一个簇所有簇构成的集合 C { C 1 , C 2 , ⋯ , C k } C\{C_1 ,C_2, \cdots,C_k\} C{C1,C2,⋯,Ck} 称为数据集 S S S 的一个聚类。 聚类分析与分类规则挖掘不同前者是一种探索性的分析过程。聚类分析的数据集 S S S 中没有已知的先验知识 (即对象的类别标号) 来指导它要求直接从 S S S 本身出发依据某种相似度标准为 S S S 的每个对象给出类别标号。因此聚类分析也称为无监督的分类 (unsupervised classification)。对于同一个数据集就算使用同一个聚类算法如果选择了不同的“相似度”标准也常常会得到不同的聚类结果。 聚类分析作为数据挖掘的一个热门研究领域在帮助人们获取潜在的、有价值的信息并过滤掉无用的信息方面起到了至关重要的作用。 目前数据聚类技术在许多领域都已得到实际应用。在生物学的研究中科学家们可以通过聚类算法来分析大量的遗传信息从而发现哪些基因组具有类似的功能以此获得对种群的认识在信息检索方面聚类算法可以将搜索引擎返回的结果划分为若干个类从每个类中获取查询的某个特定方面从而产生一个类似树状的层次结构来帮助用户进一步探索查询结果在医学领域的研究中一种疾病通常会有多个变种而聚类分析可以根据患者的症状描述来确定患者的疾病类型以此提高诊断效率和治疗效果在气象领域聚类已经被用来发现对气候具有明显影响的海洋大气压力模式在电子商务中聚类分析可以对用户群体进行细分并针对不同类型的用户进行不同的营销策略以提升销售额。
二聚类的数学定义
定义10-1 设有数据集 S { X 1 , X 2 , ⋯ , X n } S\{X_1 ,X_2, \cdots,X_n\} S{X1,X2,⋯,Xn}其中 X i X_i Xi 为 d d d 维向量 (表10-1) s ( X , Y ) s(X,Y) s(X,Y) 为定义在 S S S 上的相似度函数。若利用函数 s ( X , Y ) s(X,Y) s(X,Y) 可将 S S S 拆分成 k k k 个子集 C i C_i Ci并记 C { C 1 , C 2 , ⋯ , C k } ( k ≤ n ) C\{C_1 ,C_2, \cdots,C_k\}(k≤n) C{C1,C2,⋯,Ck}(k≤n)使 C C C 满足以下条件 1 C i ≠ ∅ ( i 1 , 2 , ⋯ , k ) C_i ≠ \varnothing (i1 ,2, \cdots,k) Ci∅(i1,2,⋯,k) (10-1) 2 C 1 ∪ C 2 ∪ ⋯ ∪ C k S C_1∪ C_2∪\cdots∪C_k S C1∪C2∪⋯∪CkS (10-2) 3 C i ∩ C j ∅ ( i 1 , 2 , ⋯ , k ; i ≠ j ) C_i∩C_j \varnothing (i1 ,2, \cdots,k; i≠j) Ci∩Cj∅(i1,2,⋯,k;ij) (10-3) 4 ∀ X , Y ∈ C i , s ( X , Y ) 1 \forall X,Y\in C_i, s(X,Y)1 ∀X,Y∈Ci,s(X,Y)1 或接近 1 1 1 ∀ X ∈ C i \forall X\in C_i ∀X∈Ci 和 Y ∈ C j ( i ≠ j ) , s ( X , Y ) 0 Y\in C_j(i≠j) ,s(X,Y)0 Y∈Cj(ij),s(X,Y)0 或接近 0 0 0则称 C i C_i Ci 为 S S S 由 s ( X , Y ) s(X,Y) s(X,Y) 生成的一个簇 (cluster)简称簇 C i ( i 1 , 2 , … ⋯ , k ) C_i (i1 ,2, …\cdots,k) Ci(i1,2,…⋯,k)同时称 C C C 为 S S S 由 s ( X , Y ) s(X,Y) s(X,Y) 生成的一个划分聚类 (partitional clustering)简称 C C C 为 S S S 的划分聚类或称为互斥 (exclusive) 的聚类。
(2) 如果将公式 (10-2) 改为 C 1 ∪ C 2 ∪ ⋯ ∪ C k ⊂ S (10-4) C_1∪C_2∪\cdots∪C_k \subset S\tag{10-4} C1∪C2∪⋯∪Ck⊂S(10-4) 而其它假设条件都不变则称 C { C 1 , C 2 , ⋯ , C k } C\{C_1 ,C_2, \cdots,C_k\} C{C1,C2,⋯,Ck} 为 S S S 的部分聚类 (partial clustering)。这时 S S S 中的某些对象没有分配到任何簇中。
(2) 如果将定义10-1中的公式 (10-2) 改为 C 1 ∪ C 2 ∪ ⋯ ∪ C k ⊆ S (10-5) C_1∪C_2∪\cdots∪C_k\subseteq S \tag{10-5} C1∪C2∪⋯∪Ck⊆S(10-5) 且至少存在两个簇 C i ∩ C j ≠ ∅ C_i∩C_j≠\varnothing Ci∩Cj∅而其它假设不变则称 C { C 1 , C 2 , ⋯ , C k } C\{C_1 ,C_2, \cdots,C_k\} C{C1,C2,⋯,Ck} 为 S S S 的非互斥聚类 (non-exclusive clustering)也称 C C C 为重叠聚类 (overlapping clustering)。 相似度函数 s ( X , Y ) s(X,Y) s(X,Y)通常可使用之前介绍的某种相似度但一般都需要根据实际数据集 S S S 的属性类型来选择或确定可选择距离或相异度 d ( X , Y ) d(X,Y) d(X,Y) 来作为相似性的度量标准这时只要将定义10-1中的第(4)条改为“对 X , Y ∈ C i , d ( X , Y ) 0 X,Y\in C_i, d(X,Y)0 X,Y∈Ci,d(X,Y)0 或接近 0 0 0对 X ∈ C i X\in C_i X∈Ci 和 Y ∈ C j ( i ≠ j ) , d ( X , Y ) Y\in C_j(i≠j) ,d(X,Y) Y∈Cj(ij),d(X,Y) 很大”即可。还可以定义其它广义的“相似度”比如簇内点的密度或要求每个簇构成某种形状等。聚类分析不仅与数据集 S S S 有关而且与所选择的相似性度量有关。 在实际应用中对于一个给定的数据集 S S S如何选择恰当的相似性度量却没有普遍适用的标准仍是一个困难而富有挑战性的问题。
例10-1 假设数据集 S S S 有20个点其在平面上位置如图10-1(1)所示。我们可将数据集 S S S 分别交给甲、乙、丙3个同学希望他们自己选择恰当的相似度标准对 S S S 进行聚类。 虽然三个同学的聚类结果不一样但老师在评分时给三个同学都是满分因为都是在各自选定的相似度标准下正确的聚类结果。
三簇的常见类型 聚类分析旨在发现“有用”或“有意义”的簇这里的有用性或意义完全由数据挖掘目的来决定。虽然实际存在有很多种类的簇但数据挖掘的实践表明无论多么奇怪的簇在实际应用中都可能是有用的。 簇的类型一般可从簇的形状和簇间关系来划分。
1、簇的形状 从簇的形状主要分为类球状 (凸形) 的簇非球状的簇两种类型。 1类球状的簇 (图10-2)一般是聚类算法使用距离函数所产生的簇而非球状的簇通常由基于密度或基于原型的聚类算法获得的簇。 2非球状的簇通常由基于密度或基于原型的聚类算法获得的簇。 2、簇间关系
1明显分离的簇 簇中每个数据对象到同簇中其它对象的距离比到不同簇中任意对象的距离更近下图中不同簇中任意两点之间的距离都大于簇内任意两点之间的距离。当然明显分离的簇不必是球形的也可以是其它任意的形状。 2基于原型的簇 所谓原型其实就是簇中最具代表性的点。对连续属性的数据簇的原型通常就是质心即簇中所有点的平均值。当数据包括分类属性时簇的原型通常是中心点即簇中最有代表性的点。对于许多数据类型原型可以视为最靠近中心的点因此通常把基于原型的簇看作基于中心的簇 (center-based cluster)下图就是一个基于中心的簇的例子。 3基于连片的簇 (contiguity-based cluster) 簇中两个相邻对象的距离都在指定的阈值之内即将其归为同一个簇。当簇的形状不规则或缠绕且数据集没有噪声时用这种方式来定义簇会收到很好的聚类效果。如果存在噪声其聚类效果就不一定理想。图中的哑铃状簇就是由线状 (噪声) 连接两个球状簇形成的一个簇。 4基于密度的簇 (density-based cluster) 基于密度的簇由对象间相对稠密的区域组成且其周围是低密度的区域。一般通过指定簇中任何一个对象周围区域内最少点数 (即密度) 来实现。下图有3个基于密度的簇它们是在哑铃状图中添加了一些低密度的对象创建的。由于增加了低密度噪声点的缘故原先的S状、线状簇不能形成较稠密的簇而被当作噪声排斥在外。当簇的形状不规则或互相盘绕并且有噪声和离群点时使用基于密度的簇定义通常得到较理想的聚类效果。 5基于概念的簇 即具有某种“共同性质”的数据对象集合。比如离相同的质心或中心点最近或组成三角形、梯形或圆环状 (重叠聚类) 等。 四聚类框架及性能要求 算法10-1 聚类算法框架 输入数据集 S S S相似度 s s s以及簇的个数 k k k 输出聚类 C { C 1 , C 2 , ⋯ , C k } C\{C_1,C_2,\cdots,C_k\} C{C1,C2,⋯,Ck} 1任意产生 S S S的一个聚类 C C C 2以 s s s为相似性标准对 S S S循环更新聚类 C C C的簇 C 1 , C 2 , ⋯ , C k C_1,C_2,\cdots,C_k C1,C2,⋯,Ck直到满意为止。 其中“满意”的标准一般是簇内对象之间的距离很近簇与簇之间的距离很远等相似度或相异度。
对数据集的可伸缩能力不仅在小数据集上聚类效果好而且在大数据集上的聚类也要效率高、效果好。处理混合属性的能力能够处理同时含有二元、分类、序数和数值等属性的数据集。发现任意形状簇的能力不仅能够发现凸型球状的、大小和密度相近的簇也能够发现一些特殊形状的簇。聚类参数自适应能力对用户输入初始参数如簇的个数 k k k密度半径 ε \varepsilon ε 和最少点数 MinPts 等具有自适应能力可以减少甚至克服初始参数对聚类的结果影响以保障聚类的质量。噪声数据的处理能力以减轻或者消除“噪声”数据影响提高聚类结果的质量。数据输入顺序的适应能力即适应数据集任意输入顺序的能力有助于提高聚类结果的稳定性。处理高维数据的能力不仅能高效地处理2-3维的数据集对高维数据 (几十个甚至更多的属性) 也能高效运行。带约束条件的聚类能力即聚类算法不仅能满足客户特定的约束条件又能得到具有良好聚类特性的簇。 值得注意的是在实际的算法设计中要求一个聚类算法同时具备以上所有能力是不现实的如果能够同时具备其中的3-4个能力已算是相对优质的算法了。
五簇的距离 数据集 S S S 的一个聚类 C { C 1 , C 2 , ⋯ , C k } C\{C_1,C_2,\cdots,C_k\} C{C1,C2,⋯,Ck} 的质量包括每个簇 C i C_i Ci 的质量和 C C C 的总体质量。前者用簇内距离来刻画后者用簇间距离来衡量。
1、簇内距离
1簇的直径 簇 C i C_i Ci 中任意两个对象之间欧氏距离的最大者也称为簇外径并记作 Φ ( C i ) m a x { d ( X , Y ) ∣ X , Y ∈ C i } (10-6) \Phi(C_i)max\{d(X,Y) | X,Y\in C_i\}\tag{10-6} Φ(Ci)max{d(X,Y)∣X,Y∈Ci}(10-6) 2簇的内径 簇 C i C_i Ci 中任意两个对象之间欧氏距离的最小者并记作 ϕ ( C i ) m i n { d ( X , Y ) ∣ X , Y ∈ C i } (10-7) \phi(C_i)min\{d(X,Y) | X,Y\in C_i\}\tag{10-7} ϕ(Ci)min{d(X,Y)∣X,Y∈Ci}(10-7)3簇的平均距离 簇 C i C_i Ci 中任意两个对象之间欧氏距离之和与 C ∣ C i ∣ 2 C i C^2_{|C_i|}C_i C∣Ci∣2Ci 中元素个数取2的组合数比值并记作 d a ( C i ) 1 C ∣ C i ∣ 2 ∑ X , Y ∈ C i d ( X , Y ) (10-8) d_a(C_i)\frac{1}{C^2_{|C_i|}}\sum_{X,Y\in C_i}d(X,Y)\tag{10-8} da(Ci)C∣Ci∣21X,Y∈Ci∑d(X,Y)(10-8) 4簇的中心距离和 设 X ‾ i \overline{X}_i Xi 为簇 C i C_i Ci 的中心点簇中每个点到中心点的距离之和并记作 d σ ∑ X ∈ C i d ( X , X ‾ i ) (10-9) d_{\sigma}\sum_{X\in C_i}d(X,\overline{X}_i)\tag{10-9} dσX∈Ci∑d(X,Xi)(10-9)
2、簇间距离 设有两个簇 C i C_i Ci 和 C j C_j Cj且对于任意 X ∈ C i X\in C_i X∈Ci Y ∈ C j Y\in C_j Y∈Cj其距离为 d ( X , Y ) d(X,Y) d(X,Y)则两个簇之间的距离 d ( C i , C j ) d(C_i, C_j) d(Ci,Cj)一般可采用以下几种方式来定义。
1簇间最小距离 以两个簇中任意两个元素距离的最小者 (smallest)即 d s ( C i , C j ) m i n { d ( X , Y ) ∣ X ∈ C i , Y ∈ C j } (10-10) d_s(C_i,C_j)min\{d(X,Y) | X\in C_i,Y\in C_j\}\tag{10-10} ds(Ci,Cj)min{d(X,Y)∣X∈Ci,Y∈Cj}(10-10) 2簇间最大距离 以两个簇中任意两个元素距离的最大者 (largest) 即 d l ( C i , C j ) m a x { d ( X , Y ) ∣ X ∈ C i , Y ∈ C j } (10-11) d_l(C_i,C_j)max\{d(X,Y) | X\in C_i,Y\in C_j\}\tag{10-11} dl(Ci,Cj)max{d(X,Y)∣X∈Ci,Y∈Cj}(10-11) 3簇间中心距离 以两个簇 C i C_i Ci 和 C j C_j Cj 的中心点 X ‾ i \overline{X}_i Xi 和 X ‾ j \overline{X}_j Xj 之间的距离作为两个簇之间的距离度量即 d c ( C i , C j ) d ( X ‾ i , X ‾ j ) (10-12) d_c(C_i,C_j)d(\overline{X}_i,\overline{X}_j)\tag{10-12} dc(Ci,Cj)d(Xi,Xj)(10-12) 其中 C i C_i Ci 的中心定义为 X ‾ i 1 ∣ C i ∣ ∑ X ∈ C i X (10-13) \overline{X}_i\frac{1}{|C_i|}\sum_{X\in C_i}X\tag{10-13} Xi∣Ci∣1X∈Ci∑X(10-13) 簇间中心距离也称为均值距离。值得注意的是簇中心常常不是该簇中的一个对象 (虚拟对象)。
4簇间平均距离 以两个簇中任意两个元素距离的平均值作为两个簇之间的一种距离度量即 d a ( C i , C j ) 1 ∣ C i ∣ ∣ C j ∣ ∑ X ∈ C i ∑ X ∈ C j d ( X , Y ) (10-14) d_a(C_i,C_j)\frac{1}{|C_i||C_j|}\sum_{X\in C_i}\sum_{X\in C_j}d(X,Y)\tag{10-14} da(Ci,Cj)∣Ci∣∣Cj∣1X∈Ci∑X∈Cj∑d(X,Y)(10-14) 实际应用中可以用 d ( X , Y ) 2 d(X,Y)^2 d(X,Y)2 替换 d ( X , Y ) d(X,Y) d(X,Y)。
5离差距离 令簇的中心距离平方和记作 r 2 ( C i ) ∑ X ∈ C i d ( X , X ‾ i ) 2 (10-15) r^2(C_i)\sum_{X\in C_i}d(X,\overline{X}_i)^2\tag{10-15} r2(Ci)X∈Ci∑d(X,Xi)2(10-15) 对于任意两个簇 C i C_i Ci C j C_j Cj如果令 C i j C i ∪ C j C_{ij}C_i\cup C_j CijCi∪Cj则簇 C i C_i Ci 与簇 C j C_j Cj 之间的平方和离差定义为 d 2 ( C i , C j ) r 2 ( C i j ) − r 2 ( C i ) − r 2 ( C j ) (10-16) d^2(C_i,C_j)r^2(C_{ij})-r^2(C_i)-r^2(C_j)\tag{10-16} d2(Ci,Cj)r2(Cij)−r2(Ci)−r2(Cj)(10-16) 并简称 d ( C i , C j ) d(C_i,C_j) d(Ci,Cj) 为簇 C i C_i Ci 与 C j C_j Cj 的离差距离。
二、划分聚类算法
一划分聚类框架 由定义10-1可知数据集 S S S 的划分聚类 C { C 1 , C 2 , ⋯ , C k } C\{C_1,C_2,\cdots,C_k\} C{C1,C2,⋯,Ck} 有两个特点 1每个簇至少包括一个数据对象 2每个数据对象属于且仅仅属于一个簇 将聚类算法框架10-1具体化可得划分聚类算法框架如下。 算法10-2划分聚类算法框架 输入数据对象集 S S S和正整数 k k k 输出“好”的划分聚类 C C C 1生成初始划分聚类 C ( 0 ) { C 1 , C 2 , ⋯ , C k } C^{(0)}\{C_1,C_2,\cdots,C_k\} C(0){C1,C2,⋯,Ck} 2REPEAT 3依照某种评价函数 f f f改变 C ( i ) C^{(i)} C(i)使新划分聚类 C ( i 1 ) C^{(i1)} C(i1)比 C ( i ) C^{(i)} C(i)更好 4UNTIL C ( i 1 ) C^{(i1)} C(i1)没有改变为止 5将 C ( i 1 ) C^{(i1)} C(i1)作为聚类 C C C输出 二划分聚类的质量
1、聚类C的簇内差异 设聚类 C { C 1 , C 2 , ⋯ , C k } C\{C_1,C_2,\cdots,C_k\} C{C1,C2,⋯,Ck}则它的簇内差异可选择某种距离函数通过计算簇内每个对象到其中心点距离的平方和来表示即聚类 C C C 的簇内差异定义为 w ( C ) ∑ i 1 k w ( C i ) ∑ i 1 k ∑ X ∈ C i d ( X , X ‾ i ) 2 (10-17) w(C)\sum^{k}_{i1}w(C_i)\sum_{i1}^{k}\sum_{X\in C_i}d(X,\overline{X}_i)^2\tag{10-17} w(C)i1∑kw(Ci)i1∑kX∈Ci∑d(X,Xi)2(10-17) w ( C ) w(C) w(C) 从总体上评价聚类 C C C 中每个簇的紧凑性在有些文献资料中也称为误差平方和 (sum of the squared error, SSE)并用 S S E ( C ) SSE(C) SSE(C) 表示。
2、聚类C的簇间差异 用 C C C 中任意两个簇中心之间的距离平方和来刻画聚类 C C C 的簇间疏远性并记作 b ( C ) ∑ 1 ≤ j i ≤ k d ( X ‾ j , X ‾ i ) 2 (10-18) b(C)\sum_{1≤ji≤k}d(\overline{X}_j,\overline{X}_i)^2\tag{10-18} b(C)1≤ji≤k∑d(Xj,Xi)2(10-18) 由于 C C C 有 k k k 个簇因此公式(10-18)右边是 k ( k 1 ) / 2 k(k1)/2 k(k1)/2 个距离平方之和。
3、聚类C的评价函数 为了同时评价聚类 C C C 的每个簇是紧凑的以及不同簇之间是疏远的即评价聚类 C C C 的总体质量其基本思想是同时考虑聚类 C C C 的簇内差异 w ( C ) w(C) w(C) 以及簇间差异 b ( C ) b(C) b(C) 的影响。因此可考虑使用以下几种形式的评价函数作为聚类的质量标准。
1 f ( C ) w ( C ) f(C)w(C) f(C)w(C)
2 f ( C ) 1 / b ( C ) f(C)1/b(C) f(C)1/b(C)
3 f ( C ) w ( C ) / b ( C ) f(C)w(C)/b(C) f(C)w(C)/b(C)
4 f ( C ) α w ( C ) β ( 1 / b ( C ) ) f(C) \alpha w(C)\beta(1/b(C)) f(C)αw(C)β(1/b(C))其中 α , β \alpha,\beta α,β 为指定的权值且 α β 1 \alpha\beta1 αβ1。
5 F ( C ) ( w ( C ) , 1 / b ( C ) ) F(C)(w(C),1/b(C)) F(C)(w(C),1/b(C))这里的 F F F 为二元目标函数或多目标函数。
因此算法10-2就是寻找使 f ( C ) f(C) f(C) 达到最小或使 F ( C ) F(C) F(C) 达到最小的聚类 C C C即是我们需要的好聚类。
三k-means算法
1、算法描述 k-means算法也称k-平均算法它采用距离作为相异度的评价指标以簇内差异函数 w ( C ) w(C) w(C) 作为聚类质量的优化目标函数即将所有数据对象到它的簇中心点的距离平方和作为目标函数算法寻找最优聚类的策略是使目标函数达到最小值 (簇中心不变化等价于 w ( C ) w(C) w(C)达最小)。 算法10-3 基本k-平均算法 输入数据对象集 S { X 1 , X 2 , ⋯ , X n } S\{X_1,X_2,\cdots,X_n\} S{X1,X2,⋯,Xn}和正整数 k k k 输出划分聚类 C { C 1 , C 2 , ⋯ , G k } C\{C_1,C_2,\cdots,G_k\} C{C1,C2,⋯,Gk} 1初始步从 S S S中随机选择 k k k个对象作为 k k k个簇的中心并将它们分别分配给 C 1 , C 2 , ⋯ , C k C_1,C_2,\cdots,C_k C1,C2,⋯,Ck 2REPEAT 3将 S S S的每个对象 X i X_i Xi归入距中心最近的那个簇 C j C_j Cj 4重新计算每个簇 C j C_j Cj的中心即每个簇中对象的平均值 5Until所有簇中心不再变化 2、计算实例
例10-2 设数据集 S { ( 1 , 1 ) , ( 2 , 1 ) , ( 1 , 2 ) , ( 2 , 2 ) , ( 4 , 3 ) , ( 5 , 3 ) , ( 4 , 4 ) , ( 5 , 4 ) } S\{(1,1), (2,1), (1,2), (2,2), (4,3), (5,3), (4,4), (5,4)\} S{(1,1),(2,1),(1,2),(2,2),(4,3),(5,3),(4,4),(5,4)}令 k 2 k2 k2, 试用k-平均算法将 X X X 划分为 k k k 个簇。 解数据集 S S S 可表示为一张二维表而每个对象在平面上的相对位置可用下图所示 因为 k 2 k2 k2故 S S S 的聚类 C { C 1 , C 2 } C\{C_1,C_2\} C{C1,C2}由k-平均算法得循环计算如下
1初始步任选 X 1 ( 1 , 1 ) , X 3 ( 1 , 2 ) X_1(1,1), X_3(1,2) X1(1,1),X3(1,2) 分别作为簇的中心即 C 1 { X 1 } C_1\{X_1\} C1{X1} 和 C 2 { X 3 } C_2\{X_3\} C2{X3}
2第一轮循环。 注意到 X 1 , X 3 X_1,X_3 X1,X3 已分配到 C 1 C_1 C1 和 C 2 C_2 C2因此 ① 计算 X 2 X_2 X2 的归属因为 d ( X 2 , X 1 ) 2 1 , d ( X 2 , X 3 ) 2 2 d(X_2,X_1)^2 1, d(X_2,X_3)^22 d(X2,X1)21,d(X2,X3)22 且 1 2 1 2 12所以 X 2 X_2 X2 归 X 1 X_1 X1 代表的簇即 C 1 { X 1 , X 2 } , C 2 { X 3 } C_1\{X_1,X_2\}, C_2\{X_3\} C1{X1,X2},C2{X3} ② 计算 X 4 X_4 X4 的归属因为 d ( X 4 , X 1 ) 2 2 , d ( X 4 , X 3 ) 2 1 d(X_4,X_1)^2 2, d(X_4,X_3)^21 d(X4,X1)22,d(X4,X3)21 且 2 1 21 21所以 X 4 X_4 X4 归 X 3 X_3 X3 代表的簇即 C 1 { X 1 , X 2 } , C 2 { X 3 , X 4 } C_1\{X_1,X_2\}, C_2\{X_3,X_4\} C1{X1,X2},C2{X3,X4} ③ 计算 X 5 X_5 X5 的归属因为 d ( X 5 , X 1 ) 2 13 , d ( X 5 , X 3 ) 2 10 d(X_5,X_1)^213, d(X_5,X_3)^210 d(X5,X1)213,d(X5,X3)210 且 13 10 1310 1310所以 X 5 X_5 X5 归 X 3 X_3 X3 代表的簇, 即 C 1 { X 1 , X 2 } , C 2 { X 3 , X 4 , X 5 } C_1\{X_1,X_2\}, C_2\{X_3,X_4,X_5\} C1{X1,X2},C2{X3,X4,X5} ④ 同理 X 6 , X 7 , X 8 X_6, X_7, X_8 X6,X7,X8 也归入 X 3 X_3 X3 代表的簇故得初始簇为 C 1 { X 1 , X 2 } C 2 { X 3 , X 4 , X 5 , X 6 , X 7 , X 8 } C_1\{X_1,X_2\}C_2\{X_3,X_4,X_5,X_6,X_7,X_8\} C1{X1,X2}C2{X3,X4,X5,X6,X7,X8} ⑤ 重新计算得 C 1 C_1 C1 和 C 2 C_2 C2 的中心点分别是 X ‾ 1 ( 1.5 , 1 ) X ‾ 2 ( 3.5 , 3 ) \overline{X}_1(1.5,1)\overline{X}_2(3.5,3) X1(1.5,1)X2(3.5,3)
3第二轮循环。 分别将 X 1 , X 2 , ⋯ , X 8 X_1, X_2,\cdots,X_8 X1,X2,⋯,X8 别分配到最近的中心点 X ‾ 1 \overline{X}_1 X1 或 X ‾ 2 \overline{X}_2 X2。 类似第一轮计算可得 S S S 的两个簇 C 1 { X 1 , X 2 , X 3 , X 4 } C 2 { X 5 , X 6 , X 7 , X 8 } C_1\{X_1,X_2,X_3,X_4\}C_2\{X_5,X_6,X_7,X_8\} C1{X1,X2,X3,X4}C2{X5,X6,X7,X8} 计算得 C 1 C_1 C1 和 C 2 C_2 C2 的中心点分别是 X ‾ 1 ( 1.5 , 1.5 ) X ‾ 2 ( 4.5 , 3.5 ) \overline{X}_1(1.5,1.5)\overline{X}_2(4.5,3.5) X1(1.5,1.5)X2(4.5,3.5)
4第三轮循环。 分别将 X 1 , X 2 , ⋯ , X 8 X_1, X_2,\cdots,X_8 X1,X2,⋯,X8 分配给最近的中心点 X ‾ 1 \overline{X}_1 X1 或 X ‾ 2 \overline{X}_2 X2。 类似第二轮循环的计算最终可得 S S S 的两个簇 C 1 { X 1 , X 2 , X 3 , X 4 } C 2 { X 5 , X 6 , X 7 , X 8 } C_1\{X_1,X_2,X_3,X_4\}C_2\{X_5,X_6,X_7,X_8\} C1{X1,X2,X3,X4}C2{X5,X6,X7,X8} 重新计算得 C 1 C_1 C1 和 C 2 C_2 C2 的中心点分别是 X ‾ 1 ( 1.5 , 1.5 ) X ‾ 2 ( 4.5 , 3.5 ) \overline{X}_1(1.5,1.5)\overline{X}_2(4.5,3.5) X1(1.5,1.5)X2(4.5,3.5)
由于簇中心已没有变化因此算法停止并输出 S S S 的聚类 C { C 1 , C 2 } { { X 1 , X 2 , X 3 , X 4 } , X 5 , X 6 , X 7 , X 8 } } C\{C_1,C_2\}\{\{X_1,X_2,X_3,X_4\}, X_5,X_6,X_7,X_8\}\} C{C1,C2}{{X1,X2,X3,X4},X5,X6,X7,X8}} 思考若在此例中指定 k 3 k3 k3而初始点选择为 X 1 , X 2 , X 3 X_1, X_2, X_3 X1,X2,X3 与 X 1 , X 5 , X 6 X_1, X_5, X_6 X1,X5,X6其结果会有啥差异。
3、算法分析说明
1算法的优点
① k-平均算法简单、经典常作为其它聚类算法的参照或被改进。 ② k-平均算法以 k k k个簇的误差平方和最小为目标当聚类的每个簇是密集的且簇与簇之间区别明显时其聚类效果较好。 ③ k-平均算法处理大数据集高效且具较好的可伸缩性其计算复杂性为 O ( n × k × t ) O(n\times k\times t) O(n×k×t) n n n是数据对象个数 k k k为簇个数 t t t是迭代次数。
2算法的缺点
① k-平均算法对初始中心点的选择比较敏感。对同一个数据集如果初始中心选择不同其聚类结果也可能不一样。 ② k-平均算法对参数 k k k是比较敏感的即使是同一个数据集如果 k k k选择不同其聚类结果可能完全不一样。 ③ k-平均算法以簇内对象的平均值作为簇中心来计算簇内误差在连续属性的数据集上很容易实现但在具有离散属性的数据集上却不能适用。
四空簇与离群点
1、空簇问题 基本k-平均算法在实际计算中可能出现的空簇现象导致算法下一轮循环无法进行。 例10-3 假设 S S S 由表10-3给出即 S S S 为二维平面上7个点的数据集。令 k 3 k3 k3请用k-平均算法将 S S S 聚类成3个簇。
解数据集 S S S 在平面上的相对位置如下图所示。 1初始步选择 X 1 , X 6 , X 7 X_1,X_6,X_7 X1,X6,X7 作为初始中心并将它们分别指派给三个簇即得 C 1 { X 1 } , C 2 { X 6 } , C 3 { X 7 } C_1\{X_1\},C_2\{X_6\}, C_3\{X_7\} C1{X1},C2{X6},C3{X7}
2第一次迭代 计算 X 2 , X 3 , X 4 , X 5 X_2,X_3,X_4,X_5 X2,X3,X4,X5 与中心点 X ‾ 1 ( 0 , 0 ) , X ‾ 2 ( 7 , 3 ) , X ‾ 3 ( 8 , 2 ) \overline{X}_1(0,0),\overline{X}_2(7,3),\overline{X}_3(8,2) X1(0,0),X2(7,3),X3(8,2) 的距离平方 将它们指派给距离平方最近的中心点可得3个簇 C 1 { X 1 , X 2 , X 3 , X 4 } C 2 { X 5 , X 6 } C 3 { X 7 } C_1\{ X_1, X_2, X_3, X_4\}C_2\{X_5,X_6\}C_3\{X_7\} C1{X1,X2,X3,X4}C2{X5,X6}C3{X7} 计算得簇 C 1 , C 2 , C 3 C_1,C_2, C_3 C1,C2,C3 新的中心点为 X ‾ 1 ( 1.5 , 2.25 ) X ‾ 2 ( 5 , 3 ) X ‾ 3 ( 8 , 2 ) \overline{X}_1(1.5,2.25)\overline{X}_2(5,3)\overline{X}_3(8,2) X1(1.5,2.25)X2(5,3)X3(8,2)。
3第二次迭代 计算 X 1 , X 2 , X 3 , X 4 , X 5 , X 6 , X 7 X_1,X_2,X_3,X_4,X_5,X_6,X_7 X1,X2,X3,X4,X5,X6,X7 与3个新中心点的距离 将 X 1 , X 2 , X 3 , X 4 , X 5 , X 6 , X 7 X_1,X_2,X_3,X_4,X_5,X_6,X_7 X1,X2,X3,X4,X5,X6,X7 指派给距离平方和最小的中心点可得 C 1 { X 1 , X 2 , X 3 , X 4 , X 5 } C 2 ∅ C 3 { X 6 , X 7 } C_1\{X_1, X_2, X_3, X_4, X_5\}C_2\varnothingC_3\{X_6 ,X_7\} C1{X1,X2,X3,X4,X5}C2∅C3{X6,X7} 这时 C 2 C_2 C2 就是一个空簇因此没有簇的中心点导致下一步计算无法进行。有以下两种策略来选择一个替补的中心。 1选择一个距离当前任何质心最远的点并可消除当前对总平方误差影响最大的点。 2从具有最大 w ( C i ) w(C_i) w(Ci) 的簇中选择一个替补质心并对该簇进行分裂簇以此降低聚类的 w ( C ) w(C) w(C)。
2、离群点问题 k-平均算法使用误差平方和 w ( C ) w(C) w(C) 作为优化目标时离群点可能过度影响所发现的簇质量即当存在离群点时聚类结果簇的质心可能不如没有离群点时那样具有代表性并且 w ( C ) w(C) w(C) 也比较高。此例 X 1 X_1 X1 就是明显的离群点。因此如果能够提前发现离群点并删除它们在k-平均算法的聚类应用中常常是有用的。 在有些实际应用中如股票市场交易分析一些明显的离群点 (股票黑马) 恰恰可能是最令人感兴趣的。
五k-中心点算法 为降低k-平均算法对噪声数据的敏感性k-中心点 (k-medoids) 算法不采用簇的平均值 (通常不是簇中的对象称为虚拟点) 作为簇中心点而是选择簇中一个离平均值最近的具体对象作为簇中心。
1、算法原理 k-中心点算法选择一个簇中位置距平均值点最近的对象替换k-平均算法的平均值中心点。首先为每个簇随机选择一个代表对象作中心点其余对象 (非中心点) 分配给最近的代表对象所在的簇。然后反复地用一个用非代表对象替换一个代表对象使其聚类质量更高 (用某种代价函数评估)直到聚类质量无法提高为止。 设 S { X 1 , X 2 , X 3 , ⋯ , X n } S\{X_1,X_2,X_3,\cdots,X_n\} S{X1,X2,X3,⋯,Xn}任选 k k k 个对象 O i ( i 1 , 2 , ⋯ , k ) O_i(i1,2,\cdots,k) Oi(i1,2,⋯,k) 作为中心点记作中心点集 O { O 1 , O 2 , ⋯ , O k } O\{O_1, O_2,\cdots, O_k\} O{O1,O2,⋯,Ok}其余 n − k n-k n−k 个对象称为非中心点记作非中心点集 Q { Q 1 , ⋯ , Q r , ⋯ , O n − k } ( S O ∪ Q ) Q\{Q_1, \cdots, Q_r,\cdots, O_{n-k}\}(SO\cup Q) Q{Q1,⋯,Qr,⋯,On−k}(SO∪Q)并将它们分配给最近的中心点并得聚类 C { C 1 , C 2 , ⋯ , C k } C\{C_1, C_2, \cdots,C_k\} C{C1,C2,⋯,Ck}其中 C i C_i Ci 的中心点为 O i ( i 1 , 2 , ⋯ , k ) O_i(i1,2, \cdots,k) Oi(i1,2,⋯,k)。 然后计算用一个非中心点 Q r Q_r Qr 去替换每一个中心点 O i ( i 1 , 2 , ⋯ , k ) O_i(i1,2,\cdots,k) Oi(i1,2,⋯,k) 的代价 E i r E_{ir} Eir找出代价最小且为负数对应的替代方案。若中心点 O i O_i Oi 被一个非中心点 Q r Q_r Qr 替换就得到新的中心点集合 O { O 1 , ⋯ , O i − 1 , Q r , O i 1 , ⋯ , O k } O\{O_1, \cdots,O_{i-1}, Q_r,O_{i1}, \cdots, O_k\} O{O1,⋯,Oi−1,Qr,Oi1,⋯,Ok}则可能引起 S S S 中每个对象 X j X_j Xj 到新中心点的距离变化将这种变化之和称为代价记作 E i r ∑ j 1 n W j i r (10-19) E_{ir}\sum_{j1}^nW_{jir}\tag{10-19} Eirj1∑nWjir(10-19) 其中 W j i r W_{jir} Wjir 表示 X j X_j Xj 因 O i O_i Oi 被 Q r Q_r Qr 替换后产生的代价用替换前后 X j X_j Xj 到中心点距离之差表示且 W j i r W_{jir} Wjir 的值因 X j ( j 1 , 2 , ⋯ , n ) X_j (j1,2,\cdots,n) Xj(j1,2,⋯,n) 原先是否在 O i O_i Oi 代表的簇中而对应不同的计算方法。
1若 X j X_j Xj 原先属于 O i O_i Oi 的簇 C i C_i Ci则有两种情况。 ① X j X_j Xj 现在离某中心点 O m ( m ≠ i ) O_m(m≠i) Om(mi) 最近 (图10-11a)则 X j X_j Xj 被重新分到 O m O_m Om 的簇其代价 W j i r d ( X j , O m ) − d ( X j , O i ) W_{jir}d(X_j,O_m)-d(X_j,O_i) Wjird(Xj,Om)−d(Xj,Oi) ② X j X_j Xj 现在离新中心点 Q r Q_r Qr 最近 (图10-11b)则 X j X_j Xj 被重新分配到 Q r Q_r Qr 的簇中, 其代价 C j i r d ( X j , Q r ) − d ( X j , O i ) C_{jir}d(X_j,Q_r)-d(X_j,O_i) Cjird(Xj,Qr)−d(Xj,Oi) 2若 X j X_j Xj 原先属于某中心点 O m O_m Om 的簇 C m ( m ≠ i ) C_m(m≠i) Cm(mi)也有两种情况 ① X j X_j Xj 现在离中心点 O m O_m Om 仍然最近 (图10-12a)则 X j X_j Xj 保留在 O m O_m Om 的簇中其代价 W j i r 0 W_{jir}0 Wjir0 ② X j X_j Xj 现在离新中心点 Q r Q_r Qr 最近 (图10-12b)则将 X j X_j Xj 重新分配到 Q r Q_r Qr 的簇中其代价 W j i r d ( X j , Q r ) − d ( X j , O m ) W_{jir}d(X_j,Q_r)-d(X_j,O_m) Wjird(Xj,Qr)−d(Xj,Om) 由于中心点有 k k k 个非中心点有 n − k n-k n−k 个因此中心点 O i O_i Oi 被一个非中心点 Q r Q_r Qr 替换就有 ( n − k ) × k (n-k)\times k (n−k)×k 个不同的方案及其对应的代价。 如果 E i h m i n { E i r ∣ i 1 , 2 , ⋯ , k r 1 , 2 , ⋯ , n − k ) } E_{ih}min\{E_{ir} | i1,2,\cdots,kr1,2,\cdots,n-k)\} Eihmin{Eir∣i1,2,⋯,kr1,2,⋯,n−k)} 且 E i h 0 E_{ih}0 Eih0则将中心点 O i O_i Oi 用非中心点 Q h Q_h Qh 替换使 S S S 中每个点到新中心点的距离之和减少即提高了聚类的总体质量。 在得到新的中心点集之后计算得到新的聚类然后继续寻找可替换的中心点直到中心点集没有变化为止。
2、算法描述 算法10-4 k-中心点聚类算法 输入簇的个数 k k k和数据集 S { X 1 , X 2 , ⋯ , X n } S\{X_1,X_2,\cdots,X_n\} S{X1,X2,⋯,Xn} 输出低价最小的聚类 C { C 1 , C 2 , ⋯ , C k } C\{C_1,C_2,\cdots,C_k\} C{C1,C2,⋯,Ck} 1从 S S S中随机选 k k k个对象作为中心点集 O { O 1 , O 2 , ⋯ , O k } O\{O_1,O_2,\cdots,O_k\} O{O1,O2,⋯,Ok} 2REPEAT 3将所有非中心点分配给离它最近的中心点并得聚类 C C C 4FOR i 1 , 2 , ⋯ , k i1,2,\cdots,k i1,2,⋯,k 5 FOR r 1 , 2 , ⋯ , n − k r1,2,\cdots,n-k r1,2,⋯,n−k 6 计算 S S S中每个 X j X_j Xj因中心点 O i O_i Oi被非中心点 Q r Q_r Qr替换后重新分配的代价 W j i r W_{jir} Wjir 7 E i r W 1 i r W 2 i r ⋯ W n i r E_{ir}W_{1ir}W_{2ir}\cdotsW_{nir} EirW1irW2ir⋯Wnir 8 END FOR 9END FOR 10 E i h min { E i r ∣ i 1 , 2 , ⋯ , k ; r 1 , 2 , ⋯ , n − k } E_{ih}\min\{E_{ir}|i1,2,\cdots,k; r1,2,\cdots,n-k\} Eihmin{Eir∣i1,2,⋯,k;r1,2,⋯,n−k} 11如果 E i h 0 E_{ih}0 Eih0则将 O i O_i Oi用 Q r Q_r Qr替换得新中心点集 O { O 1 , ⋯ , O i − 1 , Q r , O i 1 , ⋯ , O k } O\{O_1, \cdots,O_{i-1}, Q_r,O_{i1}, \cdots, O_k\} O{O1,⋯,Oi−1,Qr,Oi1,⋯,Ok} 12UNTIL中心点集 O O O无需变化 13输出 C { C 1 , C 2 , ⋯ , C k } C\{C_1,C_2,\cdots,C_k\} C{C1,C2,⋯,Ck}
