混合属性数据集的基于近邻图的两阶段聚类算法

混合属性数据集的基于近邻图的两阶段聚类算法 混合属性数据集的基于近邻图的两阶段 聚类算法 陈新泉 (重庆三峡学院智能信息处理研究所，重庆 404000) 5 摘要:面对混合属性数据集的数据预处理需求，本文在给出若干定义及相关性质之后，提出 了一种基于近邻图的两阶段聚类算法。为提高算法的时间效率，给出了几点算法改进技术。 多个人工数据集和 UCI 标准数据集的仿真实验结果表明，对于一些具有明显聚类分布结构的 数据集，该算法经常能取得比 k-means 算法和 AP 算法更好的聚类精度，说明其具有一定的 有效性。为进一步推广并在实际中发掘出该算法的应用价值，最后给出了几点较有价值的研 10 究展望。 关键词:计算机应用技术;混合属性; 聚类特征;初级聚类; 近邻图 中图分类号:TP181 15 A Dual-Steps Clustering Algorithm Based on Two Near Neighbor Graphs for Mixed-attributes Data Set Chen Xinquan (Graduate School of Intelligent Information Processing, Chongqing Three Gorges University, ChongQing 404000) Abstract: IIn order to effectively preprocessing mixed-attributes data sets, given, this paper first 20 gives a number of definitions and related properties, then presents a dual-steps clustering algorithm based on two near neighbor graphs. To improve the time efficiency of the algorithm, some improving techniques are described. Through the simulation experiments of some artificial data sets and UCI standard data sets, we can verify that this clustering algorithm can often obtain better clustering quality than k-means algorithm and AP algorithm when facing to some data sets 25 with apparent clusters. So we can say this clustering algorithm has certain value. In the end, it gives several research expectations to disinter and popularize this method. Keywords: computer application technology; mixed attributes; cluster feature; primary cluster; near neighbor graph 30 0 引言 由于应用领域的拓展及数据库技术的发展，从高维、海量、具有不同类型属性的数据库 中去发现潜在的模式或有价值的信息吸引了一些研究人员的注意。此时，作为数据预处理技 术的多元统计 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 (聚类分析的前身)得到了进一步的研究。 从数据挖掘的角度看，聚类分析的目的是为了获取数据集的空间分布结构，进而描述那 35 [1]。因此，聚类簇可近似 些有意义、有实际价值的数据集分布结构，从而简化数据集的描述 地、概要地描述数据集。 与本文有所关联的聚类算法有层次聚类算法、基于密度的聚类算法、概率层次聚类算法、 图聚类算法等。在一些经典的聚类算法中，BIRCH 算法[2]是一个利用聚类特征树结构进行 增量聚类或动态聚类的层次聚类算法，它首先对数据集进行一次扫描来构造一个具有层次树 40 结构的子聚类集合，接着通过多次扫描来改善聚类质量，其时间复杂度为 O(n)。由于 BIRCH 算法利用半径的概念来控制聚类的生成，所以它更适合于具有球形聚类分布结构的数值型数 据集。CURE 算法[3]也是一个层次聚类算法，它从最底层的数据点开始探测聚类结构，每次 作者简介:陈新泉，(1974-)，男，副教授，主要研究方向为:数据挖掘等。 E-mail: chenxqscut@126.com -1- 搜索出最相近的两个聚类进行合并，直到设定的聚类数目为止。由于 CURE 算法利用固定 数目的多个分散点来表示一个聚类，所以它可以发现数值型数据集中具有任意形状的聚类区 45 2)，高维 域。但 CURE 算法对参数比较敏感，而且需要较高的时间复杂度(低维数据需要 O(n 数据需要 O(n2?logn))，所以在处理海量数据时，必须采用一些基于抽样、划分的改进技术。 ROCK 算法[4]是一个通过反复地对两个相邻簇进行合并的层次聚类算法，它可以处理布尔型 或类别型数据集。CHAMELEON 算法[5]则是一个基于动态建模的层次聚类算法，它首先通 过图划分算法来获取大量较小的子聚类，然后采用一个凝聚型层次聚类算法来反复地合并子 50 聚类，最终探测出真实的聚类簇。该算法是通过计算聚类内部和聚类间的互连性及近似度来 自适应地探测数据集的聚类分布结构。由于该算法需要计算聚类内部和聚类间的互连性及近 似度，所以它至少需要 O(n2)的时间复杂度。DBSCAN 算法[6]则是一种基于密度的具有较高 复杂度的聚类算法，它将具有一定密度的区域划分为聚类，能发现带噪声的任意形状的聚类。 上述介绍的几个经典聚类算法主要是面向数值型数据集，或能定义合适相似度的数据 55 集。由于混和属性数据集在有序属性和无序属性上的分布及相异度计算上具有本质上的不 同，有时很难(甚至并不适合于)构造出一个准确的、统一的相异度计算式。尽管有研究者提 出了能处理类别数据的 k-modes 算法[7]和既能处理数值属性又能处理类别属性的 k-prototype 算法[8]，但它们的缺点也很明显，如所构造的相异度未必总是有效，仍存在 k-means 算法的 几个缺点等。在这样情况下，有必要进一步研究能有效处理不同类型或不同类别属性子集的 60 高效聚类算法。 本文在第二节先简要描述了所研究的问题和几个相关的定义及性质。第三节提出了一种 面向混和属性数据集的基于近邻图的两阶段聚类算法。第四节通过仿真实验来比较验证本聚 类算法的效果。第五节对本文作简要的总结并指出进一步的研究方向。 1 混合属性数据点集的存储方法 65 问题描述 1.1 设在混合属性空间的某个有限区域内分布着一个数据集 S = {X1, X2, … , Xn}。混合属性 空间可形式化地描述为: (OA1 , ..., OA OA , SA1 , ..., SA SA ) ，其中前面是|OA|个有序属性， 后面是|SA|个无序属性(这个描述可推广到具有多种不同类型属性的数据空间中，如空间数 70 据、图像数据等)。根据应用问题的领域知识，一般可构造出数据集在有序属性上的相异度 disorder(?, ?)和无序属性上的相异度 dissort(?, ?)。例如，式(1)和式(3)分别给出了有序属性和无 序属性上常用的一种相异度。 1 / 2 OA 2 (1) disorder ( X i , X j ) , L2 ( X i , X j ) , xik x jk k ,1 0, xik , x jk , k = 1, … , |SA| (2) d sort (xik , x jk ) , { 2, xik , x jk SA 75 (3) dissort ( X i , X j ) , d sort ( xik , x jk ) k ,1 其中， X i , ( xi1, xi 2 ,..., xim ) 和 X j , ( x j1, x j 2 ,..., x jm ) 分别为第 i 个数据点和第 j 个数据 点在 m = |OA| + |SA|个属性上的取值。易知，disorder(?, ?) ?[0, +?)，dissort(?, ?) ?[0, 2 * |SA|]。 -2- 定义与性质 1.2 定义 1(双重近邻点集):点 P 的双重近邻点集 NN(P)可定义为: NN(P) = {X | (disorder(X, P) ? NTorder) ? (dissort(X, P) ? NTsort), X ? P, X S} (4) 80 其中，disorder(X, P)为 S 中的点 X 与点 P 在有序属性上的相异度，dissort(X, P)为 S 中的点 X 与点 P 在无序属性上的相异度，NTorder 为有序属性上的近邻阈值，NTsort 为无序属性上的 近邻阈值。 1 的实质意义是:NN(P)是从 S = {X1, X2, … , Xn}中选取与点 P 在有序属性上相异度 定义 85 不超过 NTorder，在无序属性上相异度不超 NTsort 的其它点所构成的集合。 定义 2(有序属性上的平均聚类半径):混合属性聚类 C 在有序属性上的平均聚类半径可 定义为: 1 ( X , M ) (5) dis Rorder , order C X C 其中，|C|和 M 分别为聚类 C 的数据点数及平均点[8,9]，disorder(?, ?)为有序属性上的相异 度。 90 定义 3(无序属性上的平均聚类变径):混合属性聚类 C 在无序属性上的平均聚类变径可 定义为: 1 ( X , M ) (6) dis Rsort , sort C X C 其中，|C|和 M 分别为聚类 C 的数据点数及平均点[8,9]，dissort(?, ?)为无序属性上的相异度。 95 定义 4(聚类概要):混合属性聚类 C 的一种聚类概要可定义为: (7) CS(C) = (num, M, Rorder, Rsort) [8,9] 其中，num 为聚类 C 所包含的数据点数目|C|，M 为聚类 C 的平均点 ，Rorder 为聚类 C 在有序属性上的聚类半径，Rsort 为聚类 C 在无序属性上的聚类变径。有时我们采用聚类 C 在有序属性上的平均聚类半径 Rorder 和无序属性上的平均聚类变径 Rsort 来代替 Rorder 和 Rsort。 100 定义 5(聚类特征):借鉴文献[2]，混合属性聚类 C = {Y1, Y2, … , Y|C|}的一种聚类特征可 定义为: CF(C) = (N, LS, SS, SDS) (8) 其中，N 为聚类 C 所包含的数据点数目|C|，LS = (ls1, … , ls|OA|)为聚类 C 中所有点在|OA| 个有序属性上的线性和，SS = (ss1, … , ss|OA|)为聚类 C 中所有点在|OA|个有序属性上的平方 105 和，SDS = (sds1, … , sds|SA|)为一个存储聚类 C 在|SA|个无序属性上类别值分布信息的向量结 C C 2 , k = 1, … , |OA|。而 SDS 则通过一个定长与变长相 构。这里，lsk = ，y ， y jk ，osk = jk j ,1 j ,1 结合的向量数组 ValueVect[1 ?? |SA|][1 ?? |SAk|]来实现。ValueVect[k] , k = 1, … , |SA|是一个存 储第 k 个无序属性 SAk 的具有|SAk| (|SAk|表示第 k 个无序属性 SAk 所能取的不同无序类别值的 个数)个元素值的一维结构体数组，其中每个结构体至少包含 2 个元素(设为 SValue 和 110 PNum)。对任一个整数值对(k, j), k = 1, … , |SA|, j = 1, … , |SAk|来说，ValueVect[k][j].SValue 存 储着第 k 个无序属性 SAk 的第 j 个无序类别值，ValueVect[k][j].PNum 存储着聚类 C 在第 k 个无序属性 SAk 上取第 j 个无序类别值的数据点数目。 性质 1. 根据定义 5，显然可得 -3- SAk N = (9) ValueVect[k ][ j].PNum , k = 1, … , |SA| j ,1 115 这个公式仅仅对于无缺失项的混和属性数据集(或无序属性数据集)才是有效的。显然， 这个聚类特征定义扩展了文献[2]中的聚类特征概念，它同样满足两个聚类的加法运算。 1 和 C2 合并后的聚类 C 满足如下的加法运算 性质 2. 根据定义 5，两个混合属性聚类 C CF(C) = (N, LS, SS, SDS) = CF(C1) + CF(C2) 1) + (N2, LS2, SS2, SDS2) (10) = (N1, LS1, SS1, SDS 其中，N = N1 + N2; lsk = ls1k + ls2k, ssk = ss1k + ss2k, k = 1, … , |OA|;sdsk = sds1k + sds2k, k = 120 1, … , |SA|。这里，sdsk = ValueVect[k][1 ?? |SAk|], sds1k = ValueVect1[k][1 ?? |SAk|], sds2k = ValueVect2[k][1 ?? |SAk|], k = 1, … , |SA|。 显然，对任一个整数值对(k, j), k = 1, … , |SA|, j = 1, … , |SAk|来说，都满足如下的关系: ， ValueVect[k][j].SValue = ValueVect1[k][j].SValue = ValueVect2[k][j].SValue 125 ValueVect[k][j].PNum = ValueVect1[k][j].PNum + ValueVect2[k][j].PNum。 3. 三个混合属性聚类 C1、C2 和 C3 的加法运算满足 性质 CF(C) = CF(C1) + CF(C2) + CF(C3) (11) = (CF(C1) + CF(C2)) + CF(C3) = CF(C1) + (CF(C2) + CF(C3)) 证明:根据根据定义 5 和性质 2，容易验证混合属性聚类的加法运算满足结合律。 130 定义 6(有序属性上的聚类相离距离):两个混合属性聚类 C1 和 C2 在有序属性上的聚类 相离距离可定义为: (12) DisCorder(C1, C2) = disorder(M1, M2) - (Rorder(C1) + Rorder(C2)) 其中，M1 和 M2 分别为聚类 C1 和 C2 的平均点，Rorder(C1)和 Rorder(C2)分别为聚类 C1 和 C2 在有序属性上的聚类半径。为简化处理，有序属性上的聚类半径可采用平均聚类半径来 代替。 135 定义 7(无序属性上的聚类相离距离):两个混合属性聚类 C1 和 C2 在无序属性上的聚类 相离距离可定义为: (13) DisCsort(C1, C2) = |C1 + C2| * Rsort(C1 + C2) – (|C1| * Rsort(C1) + |Cj| * Rsort(C2)) 其中，Rsort(C1 + C2)是聚类 C1 和 C2 合并后的聚类变径，|C1 + C2| = |C1| + |C2| 是 C1 和 C2 在合并后的数据点数目。为简化处理，有序属性上的聚类变径可采用平均聚类变径来代替。 140 定义 8(无序属性上的聚类分布差):借鉴相对熵概念，两个混合属性聚类 C1 = (N1, LS1, SS1, SDS1)和 C2 = (N2, LS2, SS2, SDS2)在无序属性上的分布差可定义为: SA k (14) DisSCsort(C1, C2) = (C1, C2 ) sort disC k ,1 SAk ValueVect1[k ][r ].PNum ValueVect 2[k ][r].PNum k (15) 而 disCsort (C1, C2 ) , N1 N 2 r ,1 145 1 和 N2 分别为聚类 C1 和 C2 所包含的数据点数目，ValueVect1 和 ValueVect12 其中，N 分别为存储聚类 C1 和 C2 的聚类特征中的无序属性分量 SDS 的向量数组结构。 如果聚类 C1 和 C2 都只有一个点，那么 DisSCsort(C1, C2)等价于两个数据点在无序属性上 的相异度计算式。事实上，这个无序属性上的聚类分布差定义式与式(1)和(2)给出的无序属 性上的点对相异度计算式本质上是一致的。 如果采用文献[9]的方法来计算聚类平均点的话，那么聚类 C1 和 C2 在无序属性上的聚类 150 -4- 分布差 DisSCsort(C1, C2)与聚类 C1 和 C2 的平均点在无序属性上的相异度计算式相一致。 如果采用文献[9]的方法来计算聚类平均点的话，而聚类 C1 只有一个点，C2 有多个点， 那么聚类 C1 和 C2 在无序属性上的聚类分布差 DisSCsort(C1, C2)与一个数据点和一个聚类平均 点在无序属性上的相异度计算式也是相一致的。 155 2 混合属性数据集的基于近邻图的两阶段聚类算法 算法描述 2.1 算法名称:混合属性数据集的基于近邻图的两阶段聚类算法(算法 1) 输入:数据点集 S = {X1, X2, … , Xn}，有序属性上的近邻阈值 NTorder，无序属性上的近 邻阈值 NTsort，有序属性上的聚类融合阈值 CTorder，有序属性上的聚类相离距离阈值 COTorder， 160 sort。 无序属性上的聚类相离距离阈值 COT 输出:S = {X1, X2, … , Xn}的聚类簇描述。 步骤: Step1. 根据定义 1，为 S 中的每个点 Xi (i = 1, …, n)构造它的双重近邻点集 NN(Xi)。 Step2. 根据 S 中每个点的双重近邻点集 NN(Xi) (i = 1, …, n)，构造一个双重近邻无向图 G = (S, E)。其中 S = {X1, X2, … , Xn}，E = {(u, v) | u ?NN(v), u, v ?S}。 165 Step3. 采用一种连通子图搜索方法(如深度优先搜索等)来获取双重近邻无向图 G 的所 有有效连通子图(一般称结点数大于某个阈值的连通子图为有效连通子图，即下文的初级聚 类)。设初级聚类簇(设有 K 个, 0 < K < n)表示为 PC = {InitC1, InitC2, …, InitCK}，其平均点集 为 VM = {M1, M2, …, MK}。 Step4. 对 初 级 聚 类 簇 建 立 其 聚 类 特 征 集 CFS(PC) = {CF(InitC1), CF(InitC2), …, 170 CF(InitCK)}。根据聚类特征集 CFS(PC)，很容易计算其聚类概要描述结构集 CSS(PC)。 Step5. 以初级聚类簇 PC 的平均点集 VM = {M1, M2, …, MK}为结点集，以两个聚类 Ci 和 Cj 的聚类平均点在有序属性上的相异度不超过有序属性上的聚类融合阈值 CTorder 这个条 件来构造边集 NE = {(Mi, Mj) | weight(Mi, Mj) ? disorder(M1, M2) ? CTorder, i ? j, i, j = 1, 2, …, K}，最终可构造出一个初级聚类簇 PC 在有序属性上的 CTorder-近邻图 G(VM) = (VM, NE)。 175 Step6. 判断 G(VM)中每条边所连接的两个初级聚类是否满足聚类融合条件，如果满足， 就保留该边;否则，删除该边。经过该步处理后，设最终得到的图为 G*(VM)。 Step7. 根据图 G*(VM)中边的连接关系对位于同一个连通子图的平均点子集所代表的初 级聚类子簇进行融合(即对初级聚类子簇进行聚类的加法运算)。当图 G*(VM)所有的连通子 图都经过初级聚类的融合操作后，将最终获得的聚类簇作为本算法的输出结果。 180 算法 1 的若干说明: (1). 在 Step1 中，如果参数 NTorder 和 NTsort 设置较小的话，那么双重近邻点集所含的数 据点数目|NN(Xi)| (i = 1, …, n)也普遍比较小，通常可以小于 O(n2?(|OA| + |SA|))代价 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 出构 造 NN(Xi)的方法。 (2). 在 Step2 中，如果混和属性数据集含有较多的噪声点，那么可通过构造出一个过滤 185 掉噪声点的双重近邻无向图来增强本算法处理噪声的能力。 一种过滤掉噪声点的双重近邻无向图的构造方法为:从 S 的双重近邻点集的集合 {NN(X1), NN(X2), …, NN(Xn)}中选出所有非噪声点的双重近邻点集来组建一个新的集合 WithoutNoiseNNSet = {NN(Xi) | |NN(Xi)| ? Eps, i = 1, 2, …, n}。接着从 WithoutNoiseNNSet 中 -5- 190 构造出一个顶点集 WithoutNoiseNode = {Xi | |NN(Xi)| ? Eps, i = 1, 2, …, n} ? { Xj | Xj ? i)| ? Eps, i, j = 1, 2, …, n}和一个边集 WithoutNoiseEdge = {(Xi, Xj) | |NN(Xi)| ? NN(Xi),且|NN(X Eps, Xj ? NN(Xi), i, j = 1, 2, …, n}。显然，G* = (WithoutNoiseNode, WithoutNoiseEdge)就是 一个过滤掉噪声点的双重近邻无向图。这里，阈值参数 Eps 为预设的非噪声点的双重近邻点 集所含元素的最小数目，Eps 的大小与近邻阈值 NTorder、NTsort 及噪声过滤度有关，多数情 况下可设 Eps = 2。 195 (3). 在 Step3 中，一般定义不少于(Eps + 1)个结点的连通子图为有效连通子图(初级聚 类)。此时，初级聚类的数目满足 0 < K ? n/(Eps + 1)。 (4). 在 Step6 中，两个初级聚类 Ci 和 Cj (i ? j, i, j ? {1, 2, …, K})的聚类融合条件一般 可设计为: a. 两个初级聚类 Ci 和 Cj 在有序属性上的聚类相离距离小于阈值参数 COTorder。即:聚 200 类 Ci 和 Cj 需满足: (16) DisCorder(Ci, Cj) ? disorder(Mi, Mj) - (Rorder(Ci) + Rorder(Cj)) ? COTorder 其中，Mi 和 Mj 分别为聚类 Ci 和 Cj 的平均点，Rorder(Ci)和 Rorder(Cj)分别为聚类 Ci 和 Cj 在有序属性上的聚类半径。 205 i 和 Cj 在无序属性上的聚类相离距离小于阈值参数 COTsort。即:聚类 b. 两个初级聚类 C Ci 和 Cj 需满足: DisCsort(Ci, Cj) ? |Ci + Cj| * Rsort(Ci + Cj) – (|Ci| * Rsort(Ci) + |Cj| * Rsort(Cj)) ? COTsort (17) 其中，Rsort(Ci + Cj)是聚类 Ci 和 Cj 合并后的聚类变径，|Ci + Cj| = |Ci| + |Cj| 是 Ci 和 Cj 合 并后的数据点数目。 有时，条件 b 还可采用下面的任一个条件(当采用文献[9]的方法来计算聚类平均点时， 210 下面的两个条件 b1 和 b2 是等价的)来替换。 b1. 两个初级聚类在无序属性上的分布差小于阈值参数。 b2. 两个初级聚类的平均点在无序属性上的相异度小于阈值参数。 (5). 初级聚类在有序属性上的聚类半径的估计: a. 平均半径估计法:采用该聚类在有序属性上的平均聚类半径作为聚类半径的近似估 215 计值。 b. 密度分布估计法:如果两个初级聚类 Ci 和 Cj (i ? j, i, j ? {1, 2, …, K})在 CTorder-近 邻图中是相邻的，设它们的平均点在有序属性上的分量向量分别为 Oi 和 Oj。在 Oi 到 Oj 的 沿线上，构造一个从 Oi 到 Oj 的搜索向量 O ? Oi + step * (Oj - Oi)，其中 step 为从 0 到 1 的步 220 伐因子。计算每个搜索向量 O 的影响势值 f(O) ? ， ( X , O) ，其中 ， ( X , O) 取 X (C i ,C j ) 2 1 dis order ( X , O) 或 exp( ) 之类的近邻密度估计函数。从 Oi 到 Oj 的方向上， 2 1 ， disorder ( X , O) 2NTorde 找出第一个离 Oi 最近的使 f(O)值由大到小发生突变的拐点 Vi 出来。从 Oj 到 Oi 的方向上， 找出第一个离 Oj 最近的使 f(O)值由大到小发生突变的拐点 Vj 出来。如果拐点 Vi 到拐点 Vj 之间的 f(O)值都小于 f(Vi)和 f(Vj)且其变化都比较平缓，说明拐点 Vi 和 Vj 是初级聚类 Ci 和 Cj 225 之间的两个分割点。显然，向量(Vi - Oi)的长度可以初级聚类 Ci 在 Ci 和 Cj 方向上的聚类半径 估计值，而向量(Vj- Oj)的长度可以初级聚类 Cj 在 Ci 和 Cj 方向上的聚类半径估计值。直观上， 这种基于密度分布的聚类半径估计法比平均聚类半径更贴近公式(16)的计算。 (6). 在实际中，一般很难构造出一个混和属性上的合适的相异度计算公式，所以本聚类 -6- 算法由两个阶段的聚类探测过程构成。第一阶段是在数据点层面上通过不断地进行点的连接 操作来构造初级聚类，通常是尽量发现密集的小聚类区域。第二阶段是在前面找出的初级聚 230 类层面上不断地融合满足聚类合并条件的初级聚类。由于增加了第二步，所以这种聚类算法 能探测出含有多个大小不等的非“球状”的混和属性聚类区域。显然，第二阶段更象是对第 一阶段的补救或完善。 算法的改进与时空复杂度分析 2.2 算法的改进 235 2.2.1 为提高算法的效率，“以空间换时间”是一种常用的算法改进策略。本算法耗时最多之 处是 Step1 的构造所有点的双重近邻点集。当数据集是低维时，我们可以通过构造一些高效 -最近邻点的 的空间索引结构来减少搜索近邻点的代价，这种改进思路与文献[10]描述的求 k 几种改进技术有较大的区别。 240 (OA1 , ... , OAOA ) 所表示的|OA|维有序 例如，可以先对混和属性数据集的有序属性子集 属性空间进行规整化的多维网格划分。接着采用数组、链表、或树型结构来存储每个网格单 元的入口地址。当某个网格单元所含的数据点数目小于或等于某个阈值时，采用数组或链表 结构来存储该网格单元所包含的数据点是一种简单的实现方法。当某个网格单元所含的数据 点数目大于某个阈值时，可采用 k-d 树结构来存储该网格单元所包含的数据点。在 k-d 树的 每个叶子结点处，需存储一个指向其所含数据点的指针或句柄。 245 当某个网格单元所含的数据点数目大于某个阈值，且其在|OA|维有序属性上的空间分割 间隔向量 r = (r1, …, r|OA|)比较小时，此时就不宜采用 k-d 树作更细的空间分割。在这种情况 下，选取一个无序属性子集来建立一种网格单元数据点子集的索引结构是一种较好的 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 。 这种基于无序属性子集的分支树索引结构形式上与决策树分类器有些相似，但其本质是一种 对无序属性子空间的划分。一般这种划分应当考虑数据点子集在无序属性上的分布，从而尽 250 量构造出一棵平衡分支树。 有序属性上的 δ 近邻点查询是指在数据点集 S = {X1, X2, … , Xn}的存储空间中查找点 P 在有序属性上的 δ 区域内的所有近邻点。显然最简单也是最费时的方法是逐一比较，如果某 个点位于点 P 的有序属性上的 δ 区域内，那么该点就被选中。这种蛮力方法需要 O(n)的时 间代价。 255 通过构造合适的有序属性空间索引结构，一般可以提高 δ 近邻点查询的性能。例如可以 首先查找与“点 P 在有序属性上的 δ 超球”相交(含包含)的网格单元，然后在这些网格单元 子集范围内查找点 P 在有序属性上的 δ 区域内的所有点。一般情况下，从点 P 所在的网格 单元及其与“点 P 在有序属性上的 δ 超球”相交(含包含)的若干级邻居网格单元内的数据点 子集范围内检索点 P 在有序属性上的 δ 区域内的点，其时间代价要小于 O(n)。 260 显然，本算法 Step5 中为每个点构造其双重近邻点集及 CTorder-近邻图，也可以采用上面 介绍的思想和方法来降低算法的时间代价。 算法的时空复杂度分析 2.2.2 在 Step1 中，为 S 中的每个点 Xi (i = 1, …, n)构造双重近邻点集 NN(Xi)，若采用简单的 n 蛮力构造方法，需要 Time = O(n2?(|OA| + |SA|))，Space = O(n + 265 i NN ( X ) )。若采用一种 i ,1 -7- 合适的空间索引结构及优化技巧，可起到“以空间换时间”的效果，一般能取得低于 O(n2?(|OA| + |SA|))的时间代价，甚至可取得 O(n?logn?(|OA| + |SA|))的时间代价。 n 在 Step2 中，采用一般的构造方法，需要 O(n + NN ( X ) )的时空代价。 i i ,1 n 在 Step3 中，采用深度优先搜索方法，需要 O(n + NN ( X ) )的时空代价。 i i ,1 270 在 Step4 中，初级聚类的聚类特征计算分为两部分，有序属性部分需要 Θ(n?|OA|)的时间 代价，无序属性部分需要 ?(n?|SA|)的时间代价，有序属性部分的空间代价为 Θ(K?|OA|)，无 SA 序属性部分的空间代价为 Θ(K? )。 SAk k ,1 在 Step5 中，采用简单的蛮力方法，构造 CTorder-近邻图需要 O(K2?|OA|)的时间代价;如 果采用一种合适的空间索引结构及优化技巧，有时可以取得更小的时间代价。 275 在 Step6 中，因为图 G(VM)的边数不会超过 O(K2)，采用式(16)和式(17)来对这个 CTorder- 近邻图的每条边都判断一次时，时间代价不会超过 O(K2)。 在 Step7 中，图 G*(VM)的边数不会超过 O(K2)，但由于需要进行融合的初级聚类数不会 SA 超过 O(K)，所以该步需要 O(K?(|OA| + ))的时间代价。 SA k k ,1 参数的设置与优化 2.3 对于混和属性数据集，本算法需要设置五个参数(有序属性上的近邻阈值 NTorder，无序 280 属性上的近邻阈值 NTsort，有序属性上的聚类融合阈值 CTorder，有序属性上的聚类相离距离 阈值 COTorder 和无序属性上的聚类相离距离阈值 COTsort)。前两个参数是为数据点的近邻连 接操作而设置的，通过构造双重近邻点集来发现较为密集的数据点区域。如果这两个参数设 置过大，可能造成全部点连通起来，不能达不到探测数据分布模式的目的。如果这两个参数 285 设置较小，那么通过本算法的第二个阶段(初级聚类簇的合并)可达到融合相邻近的小聚类区 域，从而减少过多的小聚类数目的目的。 order 的设定方法:先构造数据集(或其样本)在有序属性上的 MST，然后观察该 参数 NT 生成树所有边的边权递增排列的变化规律，找出第一个拐点所对应的 MST 边长作为参数 NTorder 的一个最佳估计值。 参数 NTsort 的设定方法:先构造数据集(或其样本)在无序属性上的 MST，然后观察该生 290 成树所有边的边权递增排列的变化规律，找出第一个拐点所对应的 MST 边长作为参数 NTsort 的一个最佳估计值。 后三个参数是为初级聚类的近邻融合操作而设置的，一般可根据先验信息及第一个阶段 的结果试探设定。 参数 CTorder 的设定方法:先构造初级聚类簇在有序属性上的 MST，然后观察该生成树 295 所有边的边权递增排列的变化规律，找出第一个拐点所对应的 MST 边长与其后序边长的平 均值作为参数 NTorder 的一个最佳估计值。 参数 COTorder 的设定方法:一般在 NTorder 和 CTorder 之间取一个值。即:CTorder > COTorder > NTorder。 参数 COTsort 的设定方法:一般取一个稍大于 NTsort 的值。即:COTsort > NTsort。 300 -8- 3 仿真实验 仿真实验设计 3.1 实验环境 3.1.1 相关实验均在 Pentium(R) Dual-Core CPU T4500 2.30GHz 上进行，配备 2G 内存，在 305 Windows XP SP3 下的 Visual C++6.0 开发环境下采用 C 语言来进行仿真实验验证。 实验数据集 3.1.2 (1) 人工数据集。人工生成的 2 维实值数据集。人工数据集有四类，具体描述如下: DS1: 400 个数据点，设置为 5 个聚类(实际为 5 个聚类区)的人工无噪声数据集。 DS2: 400 个数据点，设置为 7 个聚类(实际为 6 个聚类区)的人工无噪声数据集。 310 DS3: 800 个数据点，设置为 5 个聚类(实际为 5 个聚类区)的人工带噪声数据集。 DS4: 800 个数据点，设置为 7 个聚类(实际为 6 个聚类区)的人工带噪声数据集。 (2) UCI 标准数据集。几个 UCI 标准数据集，如 Iris, Glass, Waveform, Wine, Vertebral, German, Credit[11]。除 Iris 外，其余几个 UCI 数据集都对有序数值属性部分进行了正规化数 据预处理，预处理后的属性取值范围为[0, 1]。 实验方法 315 3.1.3 采用几个人工数据集和几个 UCI 数据集作为算法的数据输入，以图形显示及聚类结果 输出的方式来验证基于近邻图的两阶段聚类算法探测聚类簇的准确性，并以 k-means 算法和 AP 算法作对比来分析它们的算法效率及聚类精度。 用来衡量算法的性能和聚类效果的指标有:算法所花费的时间(采用 ST 标记，单位为 320 秒)，聚类数目(采用 NC 标记)，预设的聚类数目(采用 PNC 标记)，所有数据点到其聚类平均 点的平均距离(采用 ADM 标记)，聚类纯度(采用 CP 标记)。 仿真实验结果 3.2 表 1 列出了基于近邻图的两阶段聚类算法(算法 1)与两个知名聚类算法(k-means 算法和 AP 算法)处理四类人工数据集的对比实验结果。表 2 列出了基于近邻图的两阶段聚类算法与 325 [12]处理五个 UCI 有序属性数据集的对比实验结果。表 3 列出了基于 k-means 算法和 AP 算法 近邻图的两阶段聚类算法与 k-means 算法(随机运行 10 次的平均结果)和 AP 算法处理二个 UCI 混和属性数据集的对比实验结果。在算法 1 中，对于混和属性数据集，需要对五个参数 进行全局的考虑来优化设置。为了简化本实验的验证工作，这里只使用了参数 DTorder 和 DTsort。 表 1. 三个聚类算法处理四类人工数据集的对比实验结果 330 Table1. Experimental results of three clustering algorithms of this paper (4 class artificial datasets) DS 算法 1 k-means 算法 AP 算法 ST NC ADM ST PNC ADM ST NC ADM DTorder 15 0 5 17.05 0 5 38.10 144 13 10.65 DS1 15 0 6 18.83 0 7 29.79 143 15 11.68 DS2 10 0 5 17.12 0 5 51.23 1239 21 9.59 DS3 10 0 6 18.06 0 7 27.66 1222 25 10.36 DS4 DS 算法 1 k-means 算法 AP 算法 ST NC/ CP ADM ST PNC/ CP ADM ST NC/ CP ADM DTorder 0.8 0 3/ 68.00% 0.8227 0 3/89.33% 0.7167 7 11/93.33% 0.3743 Iris 335 0.2 0 33/55.14% 0.1654 2 33 / - 0.2055 17 30/65.42% 0.08661 Glass 0.55 18 6/ 33.22% 0.3183 12 6 / - 0.2144 - - - Waveform 0.8 0 10/37.08% 0.6516 0 10 / - 0.4697 11 23/76.96% 0.3093 Wine 0.8 0 2/67.74% 0.4109 0 2/57.42% 0.2239 51 11/63.23% 0.01792 Vertebral -9- DS 算法 1 k-means 算法 AP 算法 ST NC / CP ADM ST PNC/CP ADM ST NC / CP ADM DTorder DTsort 0.8 5 0 20/71.10% 0.6022 German 1 20 / - 0.3540 2307 88/65.40.% 0.1719 0.8 14 0 20/70.80% 0.5973 0.4 4 0 8/ 45.63% 0.2595 Credit 0 8 / - 0.1446 628 54 /68.15% 0.08178 0.4 10 0 8/ 45.48% 0.2589 表 2. 三个聚类算法处理五个 UCI 有序属性数据集的对比实验结果 Table2. Experimental results of three clustering algorithms of this paper (Five order-attributes UCI datasets) DS 算法 1 k-means 算法 AP 算法 ST NC ADM ST PNC ADM ST NC ADM DTorder 15 0 5 17.05 0 5 38.10 144 13 10.65 DS1 15 0 6 18.83 0 7 29.79 143 15 11.68 DS2 10 0 5 17.12 0 5 51.23 1239 21 9.59 DS3 10 0 6 18.06 0 7 27.66 1222 25 10.36 DS4 DS 算法 1 k-means 算法 AP 算法 340 ST NC/ CP ADM ST PNC/ CP ADM ST NC/ CP ADM DTorder 表 3. 三个聚类算法处理二个 UCI 混和属性数据集的对比实验结果 0.8 0 3/ 68.00% 0.8227 0 3/89.33% 0.7167 7 11/93.33% 0.3743 Iris Table3. Experimental results of three clustering algorithms of this paper (Two mixed-attributes UCI datasets) 0.2 0 33/55.14% 0.1654 2 33 / - 0.2055 17 30/65.42% 0.08661 Glass DS 算法 1 k-means 算法 AP 算法 0.55 18 6/ 33.22% 0.3183 12 6 / - 0.2144 - - - Waveform ST NC ADM ST PNC ADM ST NC ADM order DT0.8 0 10/37.08% 0.6516 0 10 / - 0.4697 11 23/76.96% 0.3093 Wine 15 0 5 17.05 0 5 38.10 144 13 10.65 DS1 0.8 0 2/67.74% 0.4109 0 2/57.42% 0.2239 51 11/63.23% 0.01792 Vertebral 15 0 6 18.83 0 7 29.79 143 15 11.68 DS2 DS 算法 1 k-means 算法 AP 算法 10 0 5 17.12 0 5 51.23 1239 21 9.59 DS3 ST NC / CP ADM ST PNC/CP ADM ST NC / CP ADM DTorder DTsort 10 0 6 18.06 0 7 27.66 1222 25 10.36 DS4 0.8 5 0 20/71.10% 0.6022 German 1 20 / - 0.3540 2307 88/65.40.% 0.1719 注: 表格 关于规范使用各类表格的通知入职表格免费下载关于主播时间做一个表格详细英语字母大小写表格下载简历表格模板下载 中的"-"是因为算法执行过于费时或处理该数据集过于麻烦，故未进行计算。 DS 算法 1 k-means 算法 AP 算法 0.8 14 0 20/70.80% 0.5973 ST NC/ CP ADM ST PNC/ CP ADM ST NC/ CP ADM DTorder 0.4 4 0 8/ 45.63% 0.2595 Credit 0 8 / - 0.1446 628 54 /68.15% 0.08178 0.8 0 3/ 68.00% 0.8227 0 3/89.33% 0.7167 7 11/93.33% 0.3743 Iris 0.4 10 0 8/ 45.48% 0.2589 实验结果分析及结论 345 3.3 0.2 0 33/55.14% 0.1654 2 33 / - 0.2055 17 30/65.42% 0.08661 Glass 0.55 18 6/ 33.22% 0.3183 12 6 / - 0.2144 - - - Waveform 从实验结果图示及表 1 可以看出，当设置合适的参数 DTorder 后，算法 1 对于四类人工数 0.8 0 10/37.08% 0.6516 0 10 / - 0.4697 11 23/76.96% 0.3093 Wine 0.8 0 2/67.74% 0.4109 0 2/57.42% 0.2239 51 11/63.23% 0.01792 Vertebral 据集的聚类质量要远远好于 k-means 算法和 AP 算法。这是因为这些数据集具有良好的聚类 DS 算法 1 k-means 算法 AP 算法 分布结构，且该算法能排除近邻噪声点干扰，而不会将相近的不同聚类区域连通为一个聚类。 ST NC / CP ADM ST PNC/CP ADM ST NC / CP ADM DTorder DTsort 0.8 5 0 20/71.10% 0.6022 German 从表 2 和表 3 可以看出，算法 1 并非对所有的 UCI 数据集都能取得比 k-means 算法和 1 20 / - 0.3540 2307 88/65.40.% 0.1719 0.8 14 0 20/70.80% 0.5973 350 AP 算法更好的聚类质量。未能取得高聚类质量的首要原因是算法 1 在计算这些数据集的相 0.4 4 0 8/ 45.63% 0.2595 Credit 0 8 / - 0.1446 628 54 /68.15% 0.08178 0.4 10 0 8/ 45.48% 0.2589 异性度量时，设定这些 UCI 数据集(除 Iris 外，其余数据集都对有序属性部分进行了正规化) 的属性权重都为 1，并未考虑有些属性权重取值为 1 与该数据集的类别分布相差甚远(关于 属性权重的优化问题，可参见作者之前发表的多篇 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 或其他作者的研究成果)。另外一个 原因是算法 1 进行聚类分布探测的根基是通过发现近邻连通子图的方式来进行的，这类算法 一般都难以探测出不具有明显聚类分布结构数据集。 355 4 结束语 面对动态、海量的混合属性数据集的数据预处理需求，本文提出了一种可以处理混合属 性数据集的基于近邻图的两阶段聚类算法。通过四类人工数据集和七个 UCI 标准数据集的 仿真实验，验证了对于一些具有明显聚类分布结构的数据集，基于近邻图的两阶段聚类算法 经常能取得比 k-means 算法和 AP 算法更好的聚类精度，从而说明这个聚类方法具有一定的 360 有效性。 将基于近邻图的两阶段聚类算法与特征权重优化方法结合起来作进一步的改进，并与其 它更多经典的聚类算法在算法速度及聚类质量方面对更多的数据集做更多的比较是下一步 的工作。 365 [参考文献] (References) [1] L. Kaufman and P. J. Rousseeuw. Finding Groups in Data: An Introduction to Cluster Analysis [M]. John Wiley & Sons, 1990. [2] Zhang, T., Ramakrishnan, R., and Livny, M. BIRCH: an efficient data clustering method for very large 370 databases. In Proceedings of the 1996 ACM SIGMOD international Conference on Management of Data, pp. 103-114. [3] S. Guha, R. Rastogi, and K. Shim. CURE: An efficient clustering algorithm for large databases [C], In ACM - 10 - SIGMOD 1998. [4] S. Guha, R. Rastogi, and K. Shim. ROCK: A robust clustering algorithm for categorical attributes [C], In 375 ICDE1999, pp. 512-521, Sydney, Australia, March 1999. [5] G. Karypis, E.-H. Han, and V. Kumar. CHAMELEON: A Hierarchical Clustering Algorithm Using Dynamic Modeling [J], Computer, 32(8): 68-75, 1999. [6] M. Ester, H.-P. Kriegel, J. Sander, X. Xu, A density-based algorithm for discovering clusters in large spatial databases with noise [C], In KDD 1996, 1996. [7] Z. Huang, Extensions to the K-modes algorithm for clustering large data sets with categorical values [J], Data 380 Mining and Knowledge Discovery, 1998, 2(3): 283-304. [8] J.Z. Huang, M.K. Ng, H. Rong, Z. Li, Automated variable weighting in k-mean type clustering [J], IEEE Transactions on PAMI, 2005, 27(5). [9] Amir Ahmad, Lipika Dey. A k-mean clustering algorithm for mixed numeric and categorical data [J], Data & Knowledge Engineering, 2007, 63: 503-527. 385 [10] Hanan Samet 著, 周立树 等译. 多维与度量数据结构基础 [M], 北京:清华大学出版社，2011.5. [11] Frank, A. & Asuncion, A. (2010). UCI Machine Learning Repository []. Irvine, CA: University of California, School of Information and Computer Science. [12] Brendan J. Frey, Delbert Dueck. Clustering by Passing Messages Between Data Points [J]. Science, 315(16): 972-976. February, 2007. 390 - 11 -