第２８卷第１期 ２０１１年２月 邢台职业技术学院学报 Ｊｏｕｒｎａｌ ｏｆＸｉｎｇｔａｉ Ｐｏｌｙｔｅｃｈｎｉｃ Ｃｏｌｌｅｇｅ ｖ０１．２８ Ｎｏ．１ Ｆｅｂ．２０１１ 基于层次迭代思想的聚类算法的研究 柴旭光 （邢台职业技术学院信息工程系，河北邢台０５４０３５） 摘 要：聚类分析是数据挖掘中的一个重要研究领域，是一种数据划分或分组处理的重要手段 和方法。聚类无论在商务领域，还是在生物学、Ｗｅｂ：￣档分类、图像处理等其他领域都得到了有 效的应用。本文主要研究的是基于迭代思想的聚类算法。 关键词：数据挖掘；聚类分析；层次算法 中图分类号：ＴＰ３ １ １ 文献标识码：Ａ 文章编号：１００８－－６１２９（２０１ １）Ｏｌ—Ｏ０５２—Ｏ３ 所有的组合并为一个（层次的最上层），或者达到 一聚类是数据挖掘中的一种重要技术，是分析 数据并从中发现有用信息的一种有效手段。通过 聚类，人们能够识别密集和稀疏的区域，发现全 局的分布模式以及数据属性之间有趣的相互关 个终止条件。的方法，也称为自顶向下的 方法，一开始将所有的对象置于一个聚类中。在 迭代的每一步中，一个类被为更小的类，直 到最终每个对象在单独的一个类中，或者达到一 个终止条件。 ３．基于密度的方法（ｄｅｎｓｉｔｙ．ｂａｓｅｄ ｍｅｔｈｏｄ） 绝大多数划分方法基于对象之间的距离进行 聚类。这样的方法只能发现球状的类，而在发现 任意形状的类上遇到了困难。随之提出了基于密 系。聚类分析在客户分类、基因识别、ｗｗｗ文 本分类、空间数据处理、卫星照片分析、医疗图 像自动检测等领域有着广泛的应用，［１ｌ而其本身 的研究也是一个蓬勃发展的领域，数据挖掘、统 计学、机器学习、空间数据库技术、生物学和市 场学的发展推动着聚类分析研究的进展，使它已 成为数据挖掘研究中的一个热点。与其他数据挖 掘方法不同，在进行聚类分析前用户一般并不知 度的另一类聚类方法，其主要思想是：只要临近 区域的密度（对象或数据点的数目）超过某个阈 值，就继续聚类。也就是说，对给定类中的每个 数据点，在一个给定的范围的区域中必须至少包 含某个数目的点。这样的方法可以用来过滤“噪 声”孤立点数据，发现任意形状的聚类。【５Ｊ 本文通过分析研究以上算法，提出了基于层 次迭代思想的聚类算法。 二、基于层次迭代思想的聚类算法 （一）算法思想 通常情况下，样本空间为无数个分散的个 体，采用传统的分层算法，虽然能找到最终的结 果，但是往往计算量非常大，耗费的时间也非常 多，而采用传统的迭代算法，虽然也能算出密度 道数据集的特征。因此，从某种角度看，聚类分 析是一种无监督的学习过程，是基于观察的学习 而不是基于实例的学习。 一、聚类算法的分类 通常的聚类分析算法可分为如下几种：【２￣４】 １．划分方法（ｐａｒｔｉｔｉｏｎｉｎｇ ｍｅｔｈｏｄ） 给定一个ｎ个对象或元组的数据库，一个划 分方法构建数据的Ｋ个划分，每个划分表示一个 聚类，并且ＫＳ＿ｎ。也就是说，它将数据划分为Ｋ 个组，同时满足如下要求：每个组至少包含一个 对象；每个对象必须属于且只属于一个组，同时 某些模糊划分技术中第二个要求可以放宽。 ２．层次方法（ｈｉｅｒａｒｃｈｉｃａｌ ｍｅｔｈｏｄ） 层次的方法对给定的数据对象集合进行层次 的分解。根据层次的分解如何形成，层次的方法 可以分为凝聚的和的。凝聚的方法，也称为 在一定范围内的聚类集合，但是对样本空间的密 度有一定的要求，［６１既不能过于分散，也不能过 于集中，所以并不适用所有的情况。而本文提出 的基于层次迭代思想的算法正好可以弥补层次算 法与迭代算法的不足。 基于层次迭代思想的算法主要是先对样本空 自底向上的方法，一开始将每个对象作为单独的 一个组，然后相继地合并相近的对象或组，直到 收稿Ｅｌ期：２０１０—１１—１５ 作者简介：柴旭光（１９８３一），河北邢台人，邢台职业技术学院信息工程系，教师。 ５２ 邢台职业技术学院学报 间进行分层，使其每一层所具有的样本个数都比 较平均，且密度值符合迭代算法所要求的条件， 然后对每层子样本空间进行迭代算法，进而得出 最终的结果。 （二）算法描述 首先对样本空间分层：在给定的样本空间Ｙ 里，寻找“距离”最近的两个子样本结合。 １．有Ｎ个样本的集合Ｚｓ＝｛Ｚ１，Ｚ２…．，ＺＮ）。 ２．若想要聚成Ｋ１个聚类（事先给定Ｋ）， 即分成Ｋ１层。 ￣ｋ＝－Ｓ，Ｃｉ￣｛Ｚｉ），ｉ＝ｌ，２，．．．，Ｎ ￣ｉｆｋ＝Ｋ１ ｔｈｅｎＥＮＤ ③找到Ｃｉ与Ｃｉ之间的距离ｄ（Ｃｉ，ｃｊ）最小 的一对 ④ｃｉ和ｃｊ合成一个类Ｃｉ，并计算新的Ｃｉ 的中心 ⑤去除Ｃｉ，ｋ＝ｋ－１．ｇｏｔｏ② 三、基于层次迭代思想的算法程式 通过层次算法的计算，将已知的Ｎ个样本 并 集合Ｚｓ分成了Ｋ１个聚类，即Ｋ１层，然后对每个 聚类应用迭代算法，进行更进一步的划分，得出 最终的结果。 １．首先给一些参数： Ｋ２：期望分类个数的大致范围 ０ｋ：一个类内的最少样本数 Ｏｓ：关于类内分散程度的参数 ０ｃ：关于类问距离（最小）的参数 Ｌ：每次迭代允许合并的类数 Ｉ：允许迭代的最大次数 № ２．适当选取类中心｛ｚ１，ｚ２。…，ＺＮ ｝，Ｎｃ：类数；３．分配样本。如果有｛ｉ＝１，２，．．．，Ｎｃ｝； № ｌＩｚ一 ｌＩ－ＩＩＺ—Ｚｉ ｌ】则Ｚ∈ｓｊ，Ｊ＝１，２，．．．，Ｎ ４．如果ｓｊ类样本数Ｎｊ＜Ｏｋ，则取消ｓｊ类。 Ｎｃ＝Ｎｃ一１，ｇｏｔｏ ３）； ５．计算类Ｓｊ内平均距离： 一 １一 ＝ ｚ， ：ｌ，２，．．Ⅳｃ ｉ、ｊ ｚＥＳ Ｊ ６．如果叠代次数＞Ｉ，则转向１０）；若ⅣＣ ，√２， 则转向８）：其他情况，则转向１ｏ）。 ７．对全体样本求类内距离平均值： Ｄ：一 ｌ∑Ｎｃ ．Ｄ一ｊ，Ⅳ：兰 ８．计算各类中各分量的标准差： ＝压 ，．．一 ，．． ｋ＝１，２，．．ａＶｊ ｘ 为Ｚ∈ｓｊ的第ｉ个分量，ｚ 为 的第ｉ个 ２０１１年 第１期 分量， ，为第Ｊ类第ｉ个分量标准差。 ９．找到各类的标准差最大的分量： ６ｊ一＝ｍａｘ １ｊ，６２ ．，６崎、，Ｊ＝１，２，．．．，Ｎｃ １Ｏ．计算所有各类中心的相互距离： Ｄｉｊ＝ｌｌＺｉ—Ｚｊｉｌ，ｉ＝ｌ，２，…，Ｎｃ一１，ｊ＝ｉ＋ｌ，…，Ｎｃ １１．对于比０ｃ小的Ｄｉｊ从小到大排队。假定 为Ｄｉｌｊｌ Ｄｉ２ｊ２ …ＤｉＬｊＬ １２．按１＝１，２，．．．Ｌ的顺序，把Ｄｉｌ＿ｌ对应的Ｚｉｌ和 ｌ３．计算Ｄｉｌｉ１时的Ｚｉ，Ｚｊ，若至少其中一个是在 本次迭代中合并取得类中心，则越过此项。 １４．若叠代次数 Ｉ，或参数无改变，则终止。 否则ｇｏｔｏ（３），需要时可返回（１）修改参 数。 四、实验分析 为了验证上述算法的有效性，设计了基于层 次迭代思想的聚类算法程序，假设样本空间如图 １所示，通过该算法的分类后，结果如图２所示。 可见，该算法能将样本空间分类成有序的聚类集 合。 。 。．＝． ・ ．．・ ． ‘ ・ ：．０ ．二主 ：． ．二 ． ・．．．．．．．‘＾：．．：。 ．．‘ ・‘：．・ ．：：：．。； ・．．。：：：‘：ｔ ．： ．． ： ：；。．：ｃ ‘ ・・．．．．．＇’．． ・一・． ．‘０ ．． ．．，．．．．：： ．・ ．三．． ‘：＿．二。 ． ‘．二．：‘＝．：： ．・： 图１样本空间 岛零Ｉ 每毒爹 图２聚类集合 ５３ 邢台职业技术学院学报 ２０１１年 第１期 参考文献： 聚类算法『Ｊ１．计算机学报，２００３，２６（５）：６０５～６１０． 【１】周水庚，范晔，周傲英．基于数据取样的 【４】马帅，王腾蛟，唐世渭等．一种基于参考点和密 ＤＢＳＣＡＮ算法［Ｊ］．小型微型计算机系统，２０００， 度的快速聚类算法［Ｊ】．软件学报，２００３，（６）． ２１（１２）：１ ２７０￣１ ２７４． ［５】袁方，周志勇，宋鑫．初始聚类中心优化的 ［２】金阳，左万利．一种基于动态近邻选择模型的聚 Ｋ—ｍｅａｎｓ算法［Ｊ］．计算机工程，２００７，３３（３）：６５－－６６． 类算法［Ｊ】．计算机学报，２００７，３０（５）：７５６～７６２． ［６】邵峰晶，于忠清．数据挖掘原理与算法［Ｍ】．北 ［３】行小帅，潘进，焦李成．基于免疫规划的Ｋ－ｍｅａｎｓ 京：中国水利水电出版社，２００３，１９ ３５． Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍ ｏｆ Ｌｅｖｅｌ Ｉｔｅｒａｔｅｄ Ｔｈｅｏｒｙ ＣＨＡＩ Ｘｕ－ｇｕａｎｇ （Ｘｉｎｇｔａｉ Ｐｏｌｙｔｅｃｈｎｉｃ Ｃｏｌｌｅｇｅ，Ｘｉｎｇｔａｉ，Ｈｅｂｅｉ ０５４０３５，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｃｌｕｓｔｅｒｉｎｇ ｉｓ ａ ｍａｊｏｒ ｆｉｅｌｄ ｉｎ ｄａｔａ ｍｉｎｉｎｇ ｗｈｉｃｈ ａｌｓｏ ｉｓ ａｎ ｉｍｐｏｒｔａｎｔ ｍｅｔｈｏｄ ｏｆ ｄａｔａ ｐａｒｔｉｔｉｏｎ ｏｒ ｇｒｏｕｐｉｎｇ．Ｃｌｓｕｔｅｒｉｎｇ ｎｏｗ ｈａｓ ｂｅｅｎ ａｐｐｌｉｅｄ ｉｎｔｏ ｖａｒｉｏｕｓ ｗａｙｓ ｉｎ ｃｏｍｍｅｒｃｅ，ｍａｒｋｅｔ ａｎａｌｙｓｉｓ，ｂｉｏｌｏｇｙ，ｗｅｂ ｃｌｓａｓｉｉｆｃａｔｉｏｎ ｎａｄ ＳＯ ｏｎ．Ｔｈｉｓ ｐａｐｅｒ ｍａｉｎｌｙ ｓｔｕｄｉｅｓ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｈｅ ｌｅｖｅｌ ｉｔｅｒａｔｅｄ ｔｈｅｏｒｙ． Ｋｅｙ ｗｏｒｄｓ：ｄａｔａ ｉｍｎｉｎｇ；ｃｌｕｓｔｅｒｉｎｇ；ｈｉｅｒａｒｃｈｉｃａｌ ｍｅｔｈｏｄ （责任编辑马骅） （上接第４１页） 要原因，增大轴直径是个非常有效的减少应力的 三、结果 措施，同时花键到轴肩过渡阶段的加工工艺需要 由图６所示，花键轴的受力情况比较复杂， 改善，粗大的加工刀痕使应力集中系数增大也会 几乎每个齿都受力，其中花键齿最大一点处应力 导致花键轴断裂。 值达到了７２８Ｍｐａ。而对于２０ＣｒＭｎＴｉＨ这种材料， 外花键在扭转和弯曲及压轴力的作用下，将产生 参考文献： 弯曲应力ｃＦｎ和剪切应力ｘｔｎ（通常靠近花键收 ［１】于志伟，许晓磊，史雅琴．柴油机齿轮轴断裂失 尾处最大），这两种应力合成为当量应力Ｏ＇Ｖ。经 效分析［Ｊ］．大连海事大学学报，２００３，（２）． 过查资料，计算得：【ｏｗ］＝４６８．３２Ｍｐａ。 【２］姜涛，刘高远，张卫方．某传动装置主传动轴断 可见经有限元分析的实际等效应力值均明显 裂原因分析［Ｊ］．机械强度，２００４，（Ｓ１）． 大于所许用的当量应力。 ［３】刘永魁．推土机终传动花键轴断裂分析及改进 花键齿的应力最大值的位置位于花键到轴肩 【Ｊ１机械工人，２００５，（３）． 的过渡阶段。 ． 【４】王启义．中国机械设计大典（第三册）【Ｍ】．南昌： 由图７显示结果可知，增大轴径应力明显减 江西科学技术出版社，２００２．６０－￣－６３． 少，可以看出花键轴的轴径过小是导致轴断的主 Ｅｘｐｅｒｉｍｅｎｔａｌ Ｓｔｕｄｙ ｏｆ Ｆｒａｃｔｕｒｅ Ｆａｉｌｕｒｅ ａｂｏｕｔ ａｎ Ａｕｔｏｍｏｂｉｌｅ Ｒｅａｒ Ａｘｌｅ Ｓｐｌｉｎｅ Ｓｈａｆｔ ＺＨＡＯ Ｙｕ－ｑｉｎｇ （Ｘｉｎｇｔａｉ Ｐｏｌｔｙｅｃｈｎｉｃ Ｃｏｌｌｅｇｅ，Ｘｉｎｇｔａｉ，Ｈｅｂｅｉ ０５４０３５，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｎ ａｕｔｏｍｏｂｉｌｅ ｒｅａｒ ａｘｌｅ ｓｐｌｉｎｅ ｓｈａｆｔ ｒｆａｃｔｕｒｅ ｆａｉｌｕｒｅ ｏｃｃｕｒｓ ｗｈｅｎ ｃｈｅｃｋｉｎｇ ｆａｔｉｇｕｅ ｔｅｓｔｓ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｍａｃｒｏ—ａｎｄ ｍｉｃｒｏ．ｏｂｓｅｒｖａｔｉｏｎ ｏｆ ｈｔｅ ｓｐｌｉｎｅ ｓｈａｆｔ ｉｓ ｃａｒｄｅｄ ｏｎ，Ｐｒｏ／Ｅ４．０ ａｎｄ ｆｎｉｉｔｅ ｅｌｅｍｅｎｔ ａｎａｌｙｓｉｓ ｓｏｆｔｗａｒｅ ＭＳＣ．Ｐａｔｒａｎ ｎａｄ Ｍａｒｅ ａｒｅ ａｐｐｌｉｅｄ ｔｏ ａｎａｌｙｚｅ，ａｎｄ ｅｆｆｅｃｔｉｖｅ ｍｅａｓｒｕｅｓ ｒａｅ ｐｒｏｐｏｓｅｄ ｆｒｏｍ ｓｔｒｕｃｔｕｒｅ． Ｋｅｙ ｗｏｒｄｓ：ｓｐｌｉｎｅ ｓｈａｆｔ；ｆａｉｌｒｕｅ；ｆｒａｃｔｕｒｅ ｄａｍａｇｅ；ｆｉｎｉｔｅ ｅｌｅｍｅｎｔ ａｎａｌｙｓｉｓ （责任编辑王傲冰）
