kmeans类型变量加权聚类算法的研究与实现---优秀毕业论文 参考文献 可复制黏贴.pdf

- 工学硕士学位论文 k-means 类型变量加权聚类算法的研究 与实现 李晓明 哈尔滨工业大学 2006 年 6 月 - 国内图书分类号：tp311.3 国际图书分类号：681.3 工学硕士学位论文 k-means 类型变量加权聚类算法的研究 与实现 硕士研究生： 李晓明 导师： 徐晓飞教授 副 导 师： 叶允明副教授 申 请 学 位： 工学硕士 学 科 、 专 业：计算机科学与技术 所 在 单 位： 深圳研究生院 答 辩 日 期： 2006 年 6 月 授予学位单位： 哈尔滨工业大学 classified index: tp311.3 u.d.c: 681.3 dissertation for the master degree of engineering research and implementation on variable weighting in k-means type clustering candidate: li xiao ming supervisor: prof. xu xiao fei associate supervisor: associate prof. ye yun ming academic degree applied for: master of engineering specialty: computer science and technology affiliation: shenzhen graduate school date of defence: june, 2006 degree-conferring-institution: harbin institute of technology 哈尔滨工业大学工学硕士学位论文 - i - 摘 要 迄今为止，人们已经提出了许多聚类算法。由于 k-means 类型算法在对 大规模数据进行聚类时效率较高而且具有处理数值属性和分类属性的能力， 从而被广泛应用在市场研究和数据挖掘领域中。 然而，在数据挖掘过程中，应用 k-means 类型算法的一个主要问题就是 变量选择问题。k-means 类型算法在聚类过程中对每一个变量都同等看待， 不具备自动选择变量的能力。实际上，一个用户感兴趣的聚类结构通常只限 定在变量集合的一个子集上，而并非整个变量集合，由于包含了某些噪音变 量可能会掩盖了聚类结构的发现。在现实世界的数据库中,例如大银行中的 客户数据库, 通常包含大量的属性（变量） ，而每个变量对聚类结果的贡献 都不相同。因此，怎样从大量的变量当中选择合适的变量进行聚类是一个非 常困难并且非常重要的问题。 本文实现了一个基于k-means的变量自动加权聚类算法w-k-means， 并通 过在模拟数据上与不带权重的k-means类型算法和具有固定权重的k-means 类型算法进行了实验分析，证明了w-k-means算法在识别噪音变量和发现聚 类能力上的优越性。其次，本文基于w-k-means算法并结合k-mode和 k-prototypes算法，分别提出了处理分类属性的变量加权聚类算法w-k-mode 和处理数值和分类混合属性的变量加权算法w-k-prototypes，并通过实验证 明其发现聚类能力的优越性。最后，基于w-k-prototypes算法实现了一个符 合业界标准crisp（cross industry standard process for data mining）模型的 聚类分析系统。 关键词关键词 数据挖掘；聚类分析；变量加权； 哈尔滨工业大学工学硕士学位论文 - ii - abstract so far, many clustering algorithms have been proposed, but the k-means type clustering algorithms are widely used in real world applications such as marketing research and data mining to cluster very large data sets due to their efficiency and ability to handle numeric and categorical variables that are ubiquitous in real databases. however, a major problem of using the k-means type algorithms in data mining is selection of variables. the k-means type algorithms cant select variables automatically because they treat all variables equally in the clusting process. in pratice, an interesting clustering structure usally occurs in a subspace defined by a subset of the initially selected variables in stead of the entire variables set, some noise variables hinder cluster discovery. data in real databases, such as customer databases, are often described by a large number of attributes (variables). selection of a proper set of variables for clustering from a real world database is a very difficult and important problem in data mining applications because variables do not contribute equally to discovery of clusters. fistly, an automated variable weighting in k-means type clusting algorithm is implemented in this paper and an experiment conducted on a synthetic data set is presented. the w-k-means results are compared with the results from the standard k-means algorithm without variable weighting and the k-means algorithm with the fixed variable weighting to verify the good perfomence of w-k-means in identifying noise variables and discovering cluster. secondly, in order to handle categorical variables, a new algorithm called w-k-mode based on w-k-means and k-mode is proposed and implemented. in order to handle numeric and categorical variables, a new algorithm called w-k-prototypes based on w-k-means and k-prototypes is proposed and implemented .finally, based on the w-k-prototypes algorithm, a clusting analysis system fiting the crisp (cross industry standard process for data mining) model is implemented . keywords data mining, clustering analysis, variables weighting 哈尔滨工业大学工学硕士学位论文 - iii - 目 录 摘 要 i abstract . ii 第 1 章 绪 论 1 1.1 课题研究的背景和意义.1 1.2 国内外研究现状 2 1.3 本文的主要研究内容和结构安排 .4 第 2 章 数据挖掘中的聚类分析 .6 2.1 引言 .6 2.2 聚类分析中的数据结构和数据类型6 2.2.1 数据结构 .6 2.2.2 聚类分析的数据类型 7 2.2.3 聚类准则的确定10 2.3 数据挖掘中的聚类分析算法. 11 2.3.1 划分聚类算法 11 2.3.2 层次聚类算法 11 2.3.3 基于密度的聚类算法 13 2.3.4 基于网格的聚类算法 13 2.3.5 基于模型的聚类算法 14 2.3.6 模糊聚类算法15 2.4 聚类结果的评价 15 2.5 本章小节17 第 3 章 基于k-means的变量加权聚类算法的研究 .18 3.1 引言 .18 3.2 基本的k-means聚类算法 18 3.2.1 k-means算法的基本思想.18 3.2.2 k-means算法的主要步骤.19 3.2.3 k-means算法的优缺点.20 3.3 基于k-means改进后的w-k-means算法21 3.3.1 变量的选择和权重对聚类结果的影响 .21 3.3.2 w-k-means算法的基本原理 23 哈尔滨工业大学工学硕士学位论文 - iv - 3.3.3 w-k-means算法的主要步骤 24 3.3.4 w-k-means算法中变量权重的计算.25 3.3.5 w-k-means算法的可扩展性和时间复杂性 .25 3.4 w-k-means算法的实验结果分析26 3.4.1 合成数据集合26 3.4.2 实验结果评价方法26 3.4.3 实验结果分析27 3.4.4 实验结论 .31 3.5 本章小结31 第 4 章 处理多数据类型的变量加权聚类算法.32 4.1 引言 .32 4.2 k-mode聚类算法.32 4.3 k-prototypes聚类算法 33 4.4 处理分类属性的变量加权算法w-k-mode35 4.5 处理数值和分类混合属性的变量加权算法w-k-prototypes.36 4.6 实验结果分析38 4.7 本章小节41 第 5 章 聚类分析系统的设计与实现42 5.1 引言 .42 5.2 系统参考标准42 5.3 系统总体设计42 5.4 系统功能实现43 5.4.1 数据访问模块43 5.4.2 数据预处理模块46 5.4.3 模型构建模块51 5.5 本章小节55 结 论56 参考文献57 哈尔滨工业大学硕士学位论文原创性声明.61 致谢62 哈尔滨工业大学工学硕士学位论文 - 1 - 第1章 绪 论 1.1 课题研究的背景和意义 近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高。千 千万万个数据库被用于商业管理、政府办公、科学研究和工程开发等等，要 想使数据真正成为一个公司的资源， 只有充分利用它为公司自身的业务决策 和战略发展服务才行， 否则大量的数据可能成为包袱， 甚至成为垃圾。 因此， 面对人们被数据淹没却饥饿于知识的挑战，数据挖掘和知识发现技术1应运 而生，并得以蓬勃发展，越来越显示出其强大的生命力。 数据挖掘2 3（data mining）就是从大量的、不完全的、有噪声的、模 糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在 有用的信息和知识的过程。人们把原始数据看作是形成知识的源泉，就像从 矿石中采矿一样。原始数据可以是结构化的，如关系数据库中的数据。也可 以是半结构化的，如文本图形、图像数据、甚至是分布在网络上的异构型数 据。发现知识的方法可以是数学的、也可以是非数学的、可以是演绎的、也 可以是归纳的、挖掘出的知识4可以被用于信息管理、查询优化、决策支持 5、过程控制等。还可以用于数据自身的维护。因此，数据挖掘是一门很广 义的交叉学科，涉及人工智能技术，统计技术与数据库技术等多种技术。它 汇聚了不同领域的研究者，尤其是数据库、人工智能、数理统计、可视化、 并行计算等方面的学者和工程技术人员。 聚类是数据挖掘中一种重要的挖掘任务和挖掘方法。 它从数据库中寻找 数据间的相似性， 并依此对数据进行分类， 使得不同类中的数据尽可能相异， 而同一类中的数据尽可能相似。即，物以类聚，从而优化大规模数据库的查 询和发现数据中隐含的有用信息或知识。 数据聚类在很多领域中有着广泛的 应用，如：模式识别、图象处理、数据压缩、空间数据分析6 7、市场研究、 www 上的文本分类。对 web 的日志数据聚类以后发现相似的访问模式， 等等。迄今为止人们提出了很多聚类算法，例如分割的方法、层次的方法、 基于密度的方法、基于网格的方法和基于模型的方法。不同的算法有着不同 的应用背景，有的适用于大数据集，可以发现任意形状的聚类，有的算法思 想简单，适用于小数据集，总的说来，算法都试图从不同的途径实现对数据 哈尔滨工业大学工学硕士学位论文 - 2 - 集进行高效、可靠的聚类。 迄今为止,人们已经提出了许多聚类算法,如 k-means、dbscan、 cure、clique、sting 和 c2p，所有这些算法都试图通过不同的途径实 现对大规模数据库的有效聚类，但总的来说，都没有取得理想的效果。可以 说， 对大规模、 高维数据库的高效聚类分析仍然是一个有待研究的开放问题。 目前， 由于 k-means 类型算法在对大规模数据进行聚类时效率较高而且 具有处理数值属性和分类属性的能力， 从而被广泛应用在市场研究和数据挖 掘领域中8。然而，在数据挖掘过程中，应用 k-means 类型算法的一个主要 问题就是变量选择问题。 由于 k-means 类型算法在聚类过程中对每一个变量 都同等看待，因而不能够自动选择变量。实际上，一个用户感兴趣的聚类结 构通常只限定在变量集合的一个子集上8，而并非整个变量集合，由于包含 了某些噪音变量可能会掩盖了聚类结构的发现。在现实世界的数据库中,例 如大银行中的客户数据库, 通常包含大量的属性（变量） ，而每个变量对聚 类结果的贡献都不相同。因此，怎样从大量的变量当中选择合适的变量进行 聚类是一个非常困难并且非常重要的问题。 1.2 国内外研究现状 目前在文献中存在大量的聚类算法。大体上，主要的聚类算法可以划分 为如下几类： (1)划分方法 代表算法 k-means， 该算法试图找出满足某一特定标准的k 个划分(聚类)，通常采用平方差的标准。k-means 算法的时间复杂度为 o(tkn)，其中 n 是数据的总数，k 是聚类的个数，t 是算法循环的次数，通常 有 k，t1 或者0，),(wzup 被最小化当且仅当 = = = 0 1 00 1 1 1 j h t t j j j dif d d dif w (3-5) 其中 ),( , 11 ,jlji k l n i lij zxdud = = (3-6) h 是0 j d的变量数目。 (2)如果1=，),(wzup 被最小化当且仅当= j w1 并且0= j w， jj 。 其中对于所有的j都有 j j dd 。 3.3.3 w-k-means 算法的主要步骤 (1)随机选择一个初始中心点集合, 21 0 k zzzz?=，随机生成一个初 始权重集合, 00 2 0 1 0 m wwww?=。 通过最小化),( 00 wzup 确定 0 u。 设 t=0； (2)设 置 t zz = ， t ww = 。 通 过 最 小 化),( wzup获 得 1+t u。 如 果 ),( 1 + wzup t ),( wzup t 输出),( wzu t ，算法结束；否则，执行步骤(3)。 (3)设置 1+ = t uu， t ww = ，通过最小化),( wzup获得 1+t z。如果 哈尔滨工业大学工学硕士学位论文 - 25 - ),( wzup t ),( 1 + wzup t 输出),( wzu t ，算法结束；否则执行步骤(4)。 (4) 设 1+ = t uu， 1+ = t zz， 通 过 最 小 化),(wzup 获 得 1+t w。 如 果 ),( t wzup ),( 1+ t wzup输出),( t wzu ，算法结束；否则设置tt+1,然后 跳转到步骤(2)。 通过以上有限次的迭代后，w-k-means算法将收敛到一个局部最优解。 3.3.4 w-k-means 算法中变量权重的计算 给定一个数据划分，变量权重的分配原则是，给那些簇内距离之和较小 的变量赋予较大的权重， 簇内距离之和较大的变量赋予较小的权重。 变量 j x 的簇内距离之和可由公式 3-6 计算， 赋予变量 j x的权重 j w 可由公式3-5 计算。 而赋予变量 j x的真正权重 j w则依赖于的取值。基于以上的变量权重分配 原则可以确定的取值范围。 当0=时，无论 j w取何值，公式 3-2 都等价于公式 3-1。 当1=时，1= j w，其它变量的权重都等于 0。尽管此时目标函数被最 小化， 然而聚类结果只包含一个变量。 显然， 在解决高维数据的聚类问题时， 这并不是合理的结果。 当10时， j d越大， j w越小， j w也就越小。从而使具有较大 j d变量 的影响被减弱。 当0。 3.3.5 w-k-means 算法的可扩展性和时间复杂性 由于w-k-means算法只是在k-means类型算法迭代求解的过程中， 添加 一步用来计算变量的权重， 从而并不会严重影响k-means类型算法在对大规 模数据进行聚类时的可扩展性。因此，w-k-means算法适合大规模数据的数 据挖掘应用。 哈尔滨工业大学工学硕士学位论文 - 26 - w-k-means的时间复杂性是()tmnko，t 是算法在求解第(2)步、第(3) 步、第(4)步的需要的迭代次数，k 是簇的数目，m 是属性(变量)的数目,n 是数据对象的数目。 3.4 w-k-means 算法的实验结果分析 这一部分，我们将用实验结果来证明w-k-means算法的性能。合成数 据经常用来验证一个聚类算法36。在实验中，我们使用一个人工构造的具 有正态分布的合成数据集合来验证w-k-means算法发现聚类以及识别噪音 变量的能力。 3.4.1 合成数据集合 合成数据集合包含5个变量，共300条记录。已知这些数据在前三个变 量上，被分成三个具有正态分布的簇，每个簇具有100个点。后两个变量代 表统一分布的噪音变量。这三个簇的中心点和标准差如下表所示： 表 3-1 三个簇各个变量的中心点和标准差 table 3-1 centroids and standard deviations of clusters in different variables cluster cluster centroids standard deviations no.of points 1 0.547,0.728,0.424,0.492,0.561 0.547,0.728,0.424,0.492,0.561 100 2 0.299,0.585,0.318,0.555,0.455 0.061,0.044,0.069,0.269,0.274 100 3 0.422,0.452,0.636,0.520,0.536 0.055,0.050,0.075,0.263,0.274 100 从上表可以看出，前三个变量的中心点能够较好的彼此区分，标准差也 较小。而后两个噪音变量的中心点很接近，标准差也远大于前三个变量的标 准差。 3.4.2 实验结果评价方法 由于合成数据集合中的点所属的簇标号是已知的， 所以， 我们使用rand index来评价聚类算法的性能37。设, 321 cccc =是合成数据的三个簇集 合，, 3 2 1 cccc =是由聚类算法生成的三个簇集合。给定数据集合中的一 个点对),( ji xx我们有如下四个定义： 哈尔滨工业大学工学硕士学位论文 - 27 - (1)ss 如果这两个点在c中属于同一个簇并且在 c中也属于同一个簇。 (2)dd 如果这两个点在c中属于两个不同的簇并且在 c中也属于两个不 同的簇。 (3)sd 如果这两个点在c中属于同一个簇，而在 c中属于两个不同的簇。 (4)ds 如果这两个点在c中属于两个不同的簇，而在 c中属于同一个簇。 设a、b、c、d分别是ss、sd、ds、dd中的点对数量， 那么，a+b+c+d=m， 其中mn(n-1)/2 是所有可能的点对数量。rand index通过公式 3-7 来计 算。 m da r + = (3-7) rand index 衡量的是属于ss或dd中的点对占所有点对的比例。r值越大， c和 c的相似度越高。 我们引入评价聚类结果的另一个方法，聚类精确度，计算方法如公式 3-8 所示。 n a r k i = 1 100 (3-8) 其中 i a是那些属于 i c并且被算法聚类到 i c中的点的数量，n是数据集合所有 点的数量。 3.4.3 实验结果分析 标准的k-means算法在聚类过程中产生一个局部优化解， 最终结果依赖 于初始的簇中心点。在w-k-means算法的聚类过程中，初始的权重分配也 将影响最终的聚类结果。为了测试w-k-means算法的性能，我们首先固定 初始的簇中心点，在合成数据上分别使用不同的权重集合运行w-k-means 算法。然后，我们使用不同的簇中心点集合和初始的权重集合再次运行 w-k-means算法。在实验中，设置8=。我们把w-k-means算法的实验结 果和标准的k-means算法以及具有权重距离函数的k-means算法（在距离函 数中引入一个权重集合，但是在聚类过程中权重并不改变）的实验结果进行 比较。 给定一个初始簇中心点集合，首先，用monte carlo 抽样方法38生成一 个随机初始权重集合，并在距离函数中引入这个权重集合，运行k-means算 法，生成聚类结果。然后，利用同样的权重集合运行w-k-means算法。 w-k-means算法的收敛曲线如图3-6所示： 哈尔滨工业大学工学硕士学位论文 - 28 - 图3-6 w-k-means算法的收敛曲线图 fig. 3-6 convergence curve of the w-k-means algorithm. 上图中，横轴代表迭代的次数，竖轴代表目标函数值（公式3-3）。图 中的每一个点都代表由k-means算法每一次迭代所生成的划分。算法在经过 六次迭代后收敛， 同时计算出一个新的权重集合 1 w。 然后， 以权重集合 1 w和 目前的中心点，再次重复聚类过程。从图中我们可以看到，在引入权重集合 1 w后，目标函数值明显下降。在经过两次迭代后，k-means聚类过程再次收 敛，同时计算出一个新的权重集合 2 w。这个聚类过程不断重复，直到目标 函数值达到局部最小值。最终获得权重集合 4 w。 随机生成10组权重集合，分别使用每个权重集合运行k-means算法，共 执行10次，每次都使用相同的初始簇中心点。聚类结果如下表3-2所示，从 表中可以看出，只有第二次的聚类结果具有较高的精确度。 k-means算法的聚类结果如下表所示 哈尔滨工业大学工学硕士学位论文 - 29 - 表3-2 k-means算法使用10组随机生成的权重所产生的聚类结果 table 3-2 ten randomly generated weights and the clustering results by the k-means algorithm num weight0 weight1 weight2weight3weight4rand index accuracy 1 0.2185 0.2845 0.0809 0.2457 0.1704 0.7577 0.7467 2 0.2968 0.3261 0.0982 0.1740 0.1049 0.9738 0.9800 3 0.3637 0.1018 0.1642 0.2899 0.0804 0.7766 0.7967 4 0.2661 0.1881 0.0680 0.2413 0.2365 0.6738 0.6033 5 0.3841 0.1989 0.0841 0.1500 0.1829 0.7795 0.7933 6 0.3337 0.0510 0.0496 0.2351 0.3305 0.6174 0.5367 7 0.3377 0.0285 0.1386 0.0844 0.4109 0.5661 0.4367 8 0.2804 0.2525 0.0821 0.0172 0.3678 0.5663 0.4367 9 0.3569 0.1190 0.0654 0.4327 0.0261 0.5545 0.3767 10 0.2503 0.1202 0.1236 0.3400 0.1658 0.5545 0.3733 随机生成10组权重集合作为初始权重， 分别使用每组权重在同样的数据 集合上运行w-k-means算法10次。每次都使用相同的初始簇中心点。聚类结 果和最终的权重如下表3-3所示，从表中可以看出10次聚类结果中有5次达到 了很高的精确度。w-k-means算法的聚类结果如下表所示： 表3-3 w-k-means算法的聚类结果以及最终计算出的权重集合 table 3-3 ten final weights and the clustering results by the w-k-means algorithm num weight0 weight1 weight2weight3weight4rand index accuracy 1 0.3021 0.4137 0.2268 0.0301 0.0273 1.0000 1.0000 2 0.3021 0.4137 0.2268 0.0301 0.0273 1.0000 1.0000 3 0.3078 0.4035 0.2310 0.0302 0.0274 0.9956 0.9967 4 0.3078 0.4035 0.2310 0.0302 0.0274 0.9956 0.9967 5 0.3078 0.4035 0.2310 0.0302 0.0274 0.9956 0.9967 6 0.3249 0.1362 0.1212 0.0814 0.3362 0.6204 0.5533 7 0.1204 0.0942 0.0850 0.0601 0.6403 0.5721 0.4500 8 0.1204 0.0942 0.0850 0.0601 0.6403 0.5721 0.4500 9 0.1092 0.0826 0.0772 0.6822 0.0487 0.5545 0.3767 10 0.1091 0.0826 0.0772 0.6824 0.0487 0.5545 0.3733 从这5次聚类过程所计算出的最终权重可以看出， 5个变量中前三个变量 哈尔滨工业大学工学硕士学位论文 - 30 - 的权重远大于后两个变量，从而能够明显地区分正态变量和噪音变量。这5 次聚类过程最后计算出的权重如图3-7所示，随机生成的初始权重如图3-8所 示。根据随机生成的权重，是识别不出噪音变量的，而根据w-k-means算法 所计算的变量最终权重，却很容易做到这一点。 图3-7 w-k-means算法在5次聚类过程中计算出的最终权重 fig. 3-7 plots of the final weights of the five good clustering results. 图3-8 5次聚类过程的初始权重 fig. 3-8 plots of the initial weights of the five good clustering results. 上述实验使用的都是相同的初始簇中心点， 而选择不同的初始簇中心点 对k-means类型算法的聚类结果是有影响的。 为了进一步证明w-k-means算法 的性能，我们随机生成10个初始簇中心点集合。首先，对于每一个中心点集 合，运行一次k-means算法，聚类结果如表3-4第二列所示，括号内的第一个 值是聚类准确度，第二个值是rand index。然后，对每一个初始簇中心点， 随机生成100个初始权重集合，运行把权重引入距离函数的k-means算法（权 重在迭代过中保持不变） ，聚类结果的平均准确度和平均rand index如表3-4 第三列所示。最后，对于每一个初始中心点集合，随机生成100个初始权重 哈尔滨工业大学工学硕士学位论文 - 31 - 集合，运行w-k-means算法，聚类结果的平均准确度和平均rand index 如表 3-4第四列所示。 表3-4 三种聚类算法聚类结果比较 table 3-4 comparison of results num no weights fixed weights weights changed 1 (0.4767,0.5768) (0.6764,0.7317) (0.8225,0.8671) 2 (0.4833,0.5797) (0.6990,0.7462) (0.8453,0.8809) 3 (0.5267,0.6052) (0.6871,0.7429) (0.7830,0.8357) 4 (0.7200,0.7652) (0.6880,0.7448) (0.7893,0.8403) 5 (0.7800,0.7877) (0.6938,0.7445) (0.8682,0.8963) 6 (0.4764,0.5780) (0.6930,0.7444) (0.8337,0.8713) 7 (0.7167,0.7610) (0.6960,0.7479) (0.7992,0.8474) 8 (0.7767,0.7884) (0.6778,0.7361) (0.8003,0.8478) 9 (0.7800,0.7877) (0.7040,0.7515) (0.8426,0.8776) 10 (0.7200,0.7589) (0.6740,0.7379) (0.7810,0.8341) average (0.6457,0.6989) (0.6889,0.7428) (0.8156,0.8599) 3.4.4 实验结论 通过以上实验结果表明，w-k-means算法发现聚类的能力要优于k-means 类型算法。 它通过在迭代求解过程中计算出的变量最终权重能够识别出噪音 变量，这个能力对于大规模高维数据聚类的变量选择具有重要意义。 3.5 本章小结 本章主要介绍了一种基于k-means的变量自动加权聚类算法。 叙述了该 算法的基本思想以及主要步骤，并通过在合成数据上的实验，证明了该算法 在发现聚类的能力上要优于k-means类型算法。 哈尔滨工业大学工学硕士学位论文 - 32 - 第4章 处理多数据类型的变量加权聚类算法 4.1 引言 上一章介绍的w-k-means算法所处理的数据对象只限于数值类型的数 据， 而大多数实际的数据库和大的数据集不仅包括数值类型的数据而且包括 大量的非数值类型数据 （分类数据） 。 因此， 针对这个问题， 本文把w-k-means 与能够处理分类属性的k-mode3940聚类算法和处理数值和分类混合属性的 k-prototypes25聚类算法相结合，提出了w-k-mode 和w-k-prototype算法， 并给予实现。 4.2 k-mode 聚类算法 假定， m aaa, 21 ?是描述空间的m维属性，)( 1 adom，)( 2 adom， )( m adom是各个属性的值域。值域中属性的取值是有限的和无序的，如 “红”，“黄”，“蓝”，“绿”，“正方形”，“圆形”，“梯形” 等。设一个数据对象)( i adomx ，mi, 2 , 1?=,以一个向量表示中的数 据对象, 21m xxxx?=，对于不同的数据对象 i x和 k x当且仅当 ji x , 和 jk x , ，mj, 2 , 1?=时， i x= k x。 定义4.1 设yx,，d(x,y) 是x,y的差异度函数，则： = = m j jj yxyxd 1 ),(),( (4-1) 其中 )(0),( )(1),( jjjj jjjj yxyx yxyx = = (4-2) 这个差异度定义赋于一个属性的所有可能取值同等的重要性。 定义4.2 设, 21n xxx?是一组数据元组，其中, 21imiii xxxx?=表 示具有m个属性值的数据对象。则用“模式”来代表这组数据元组，x的模 式定义为=, 21m zzzz?，使得 = = n i i zxdxzd 1 ),(),( (4-3) 取得最小。 哈尔滨工业大学工学硕士学位论文 - 33 - 设 jk c n , 是数据集中属性 j a取值为 jk c , 的数据对象个数，而 n n xcaf jk c jkjr , )|( , = (4-4) 是数据集中属性 j a取值为 jk c , 的数据对象频率，则有： 定理4.1函数),(xzd取得最小，当且仅当， )|()|( , xcafxzaf jkjrjjr =，其中mj, 2 , 1?=且 jkj cz , 。即，模式的各 属性值应取使得在各属性上数据对象频率最大的属性值。 设k是一个正整数，对x聚类的目的就是要将x中的n个对象划分到k个不 同的类别中。代价函数如4-5所示： ),( 11 ji k j n i ij zxdue = = (4-5) 这里，, 21jmjjj zzzz?=是能够代表聚类j的向量即模式，1 , 0 ij u是划分 矩阵 kn u 的一个元素，1= ij u表示数据对象 i x属于聚类j，否则 i x不属于聚 类j，d是差异测度，可用式4-1表示。令： ),( 1 ji n i ijj zxdue = = (4-6) 是将x划分到聚类j中的代价， 即聚类j中所有数据对象到它的原型 j z的距离 之和。模式, 21jmjjj zzzz?=可按照定理4.1获得。 算法的具体步骤： (1)选择k个初始模式，分别对应k个聚类。 (2)根据差异度的定义， 将各数据对象分配到离它最近的初始模式所代表 的聚类中，并根据定理4.1更新各聚类模式。 (3)所有数据分配完之后， 对所有数据分别与当前的各聚类模式进行差异 度计算，如果发现距离数据对象 i x最近的模式 j z不是该数据对象当前所属 的聚类模式 k z，分配它到聚类 j z中，并更新模式 j z和 k z。 (4)重复(3)直到对所有数据对象，各聚类中的数据不再变化为止。 4.3 k-prototypes 聚类算法 k-prototypes算法将k-means算法和k-modes算法结合起来，引入参数来 控制数值属性和分类属性对聚类过程的作用。 结合x中的数据对象的分类属性，定义差异测度 ： 哈尔滨工业大学工学硕士学位论文 - 34 - = += cr m j c lj c ijl m j r lj r ijli zxzxzxd 11 2 ),()(),( (4-7) 其中，),(zx由式4-2定义。 r ij x和 r lj z分别是数据对象 i x和聚类l的原型 l z 的数值属性的取值，而 c ij x和 c lj z是分类属性的取值。 r m和 c m分别是数值属性 和分类属性的个数。 l 是聚类l的分类属性的权值。如果对所有聚类， l 取 同一值，则用表示。对数值属性采用欧式距离，式4-6变为： = += cr m j c lj c ij n i ill m j r lj r ij n i il zxuzxue 111 2 1 ),()( (4-8) 其 中 ， r l e是 基 于 聚 类 l 中 所 有 数 据 对 象 数 值 属 性 的 代 价 。 设 )( jj adomc =是分类属性j上的所有取值集合，类似于k-modes算法，对一 个指定的聚类， 其原型的分类属性只有取聚类中数据对象的分类属性中出现 最频繁的值才能使代价最小。 对于数值属性，当 mjxu n z r ij n i il l r lj , 2 , 1, 1 1 ?= = (4-9) 时，式4-7中的 r l e达到最小，其中 = = n i ill un 1 是聚类l中的数据对象个数。这 里利用了k-means聚类的方法。 对一个具有数值属性和分类属性的数据集进行聚类的代价函数可写作： cr k l c l k l r l k l c l r l eeeeeee+=+=+= =111 )( (4-10) 每个聚类原型的数值属性和分类属性可由式4-9和定理4-1确定。 综上所述，k-prototypes聚类算法步骤描述如下： (1)从数据集中选取k个初始聚类原型。 (2)按照上述定义的差异度最小原则将数据集中的数据对象划分到离它 最近的聚类原型所代表的聚类中。 (3)对于每个聚类，重新计算聚类原型。 (4)计算每个数据对象对于新的聚类原型的差异度，如果离一个数据对 象“最近”的聚类原型不是当前数据对象所属聚类的原型， 则重新分配这两 个聚类的对象。 (5)重复(3)、(4)直到各个聚类中不再有数据对象发生变化。 哈尔滨工业大学工学硕士学位论文 - 35 - 4.4 处理分类属性的变量加权算法 w-k-mode k-mode算法的求解过程可以归结为最小化公式4-5的过程，在公式4-5 中，每个变量都被赋予同等权重。为了在最小化4-5的过程中发现变量的最 优权重，w-k-mode算法把一个新的未知集合 m wwww, 21 ?=引入公式4-5 中。修改后的代价函数定义如下： = = k l n i m j ljijjil zxdwuwzup 111 ),(),( (4-11) 1 , 0 il u 1 1 = = k l il u 1 1 = = m j j w kl0 ni1 这里m 是变量的数目, j w 是变量 j x的权重其中1。差异度 d 通过 公式4-1、4-2计算，优化公式 4-11 的过程与求解w-k-means算法的过程相 同。其中，权重 j w通过公式 4-12 来求解。 = = = 0 1 00 1 1 1 j h t t j j j dif d d dif w (4-12) 其中 ),( , 11 ,jlji k l n i lij zxdud = = (4-13) h 是0 j d的变量数目。 w-k-mode算法的具体步骤如下： (1)随机选择一个初始模式集合, 21 0 k zzzz?=形成k个聚类，随机生 成一个初始权重集合, 00 2 0 1 0 m wwww?=。 (2)根据差异度的定义，将各数据对象分配到离它最近的初始模式所代表 的聚类中，并根据定理4.1更新各聚类模式。 (3)所有数据分配完之后，对所有数据分别与当前的各聚类模式进行差异 度计算，如果发现距离数据对象 i x最近的模式 j z不是该数据对象当前所属 的聚类模式 k z，分配它到聚类 j z中，并更新模式 j z和 k z。 (4)根据权重公式4-12重新计算各个变量的权重。 (5)重复(3)直到对所有数据对象，各聚类中的数据不再变化为止。 w-k-mode算法的实现的流程图如图4-1所示： 哈尔滨工业大学工学硕士学位论文 - 36 - 图 4-1 w-k-mode 算法的流程图 fig.4-1 the flow diagram of w-k-mode 4.5 处理数值和分类混合属性的变量加权算法 w-k-prototypes k-prototypes算法的求解过程可以归结为最小化公式4-8的过程，在 公式4-8中，每个变量都被赋予同等权重。为了在最小化4-8的过程中发现 开始 随机选择 k 个模式 随机生成权重集合 w 分配数据对象到最近的 模式，形成 k 个簇 对象的隶属关系是 否发生变化 重新计算 k 个簇的模式 重新分配数据对象 重新计算变量的权重 结束 输出聚类结果 输出权重集合 否 是 哈尔滨工业大学工学硕士学位论文 - 37 - 变 量 的 最 优 权 重 ，w-k-prototypes算 法 把 一 个 新 的 未 知 集 合 m wwww, 21 ?=引入公式4-8中。修改后的代价函数定义如下： = += k l n i m j c lj c ijjill k l n i m j ljijjil cr zxwuzxdwuwzup 111111 ),(),(),( (4-14) 1 , 0 il u 1 1 = = k l il u 1 1 = = m j j w kl 0 ni 1 其中，),(zx由式 4-2 定义。 r ij x和 r lj z分别是数据对象 i x和聚类 l 的原型 l z的 数值属性的取值，而 c ij x和 c lj z是分类属性的取值。 r m和 c m分别是数值属性和 分类属性的个数。 l 是