142 2010，46（25） Computer Engineering and Applications 计算机工程与应用 改进的基于遗传算法的粗糙聚类方法 洪亮亮，罗 可 HONG Liang-liang，LUO Ke 长沙理工大学 计算机与通信工程学院，长沙 410014 Institute of Computer and Communication Engineering，Changsha University of Sciences and Technology，Changsha 410014，China E-mail：hongliangliang2008@163.com HONG Liang-liang，LUO Ke.Improved rough clustering method based on genetic algorithm.Computer Engineering and Applications，2010，46（25）：142-145. in reality，the objects of different Abstract： Traditional clustering methods use hard calculations to divide data objects，but theory provides a method of deal- classes often do not have clear boundaries between different kinds of clusters.Rough set ing with uncertain boundary objects.Therefore，the rough theory and k-means method are combined.Meanwhile，the traditional k-means clustering method must be given in advance the number of clusters k，but in the actual cases，k is difficult to estab- lish；In addition，traditional k-means algorithm has powerful local search capability，but easily falls into local optimum.Genetic the convergence is fast.In view of this，this paper presents an improved algorithm can get rough clustering method based on genetic algorithm.The algorithm can dynamically generate the number of k-means cluster- ing，using max-min principle to generate the initial cluster centers.Rough set is combined to deal with the boundary object.Finally，the UCI’s Iris set the algorithm.The experimental results show that the algorithm has higher accuracy rate and more stable performance. Key words：cluster analysis；genetic algorithm；rough set；k-means theory’s upper and lower approximation set the global optimal solution，but is used to test 摘 要：传统的聚类算法都是使用硬计算来对数据对象进行划分，然而现实中不同类之间对象通常没有明确的界限。粗糙集理 论提供了一种处理边界对象不确定的方法。因此将粗糙理论与 k-均值方法相结合。同时，传统的 k-均值聚类方法必须事先给定 聚类数 k，但实际情况下 k 很难确定；另外虽然传统 k-均值算法局部搜索能力强，但容易陷入局部最优。遗传算法能得到全局最优 解，但收敛过快。鉴于此，提出了一种改进的基于遗传算法的的粗糙聚类方法。该算法能动态地生成 k-均值聚类数，采用最大最 小原则生成初始聚类中心，同时结合粗糙集理论的上近似和下近似处理边界对象。最后，用 UCI 的 Iris 数据集分别对算法进行实 际验证。实验结果表明，该算法具有较高的正确率，综合性能更加稳定。 关键词：聚类分析；遗传算法；粗糙集；k-均值算法 DOI：10.3778/j.issn.1002-8331.2010.25.042 文章编号：1002-8331（2010）25-0142-04 文献标识码：Ａ 中图分类号：TP311 1 引言 将物理或抽象的集合分成相似的对象类的过程称为聚 类。簇是数据对象的集合，这些对象与同一个簇中的对象彼 此相似，而与其他簇中的对象相异。聚类分析现已成为数据 挖掘研究领域中一个非常活跃的研究课题[1]。 现有的 k-均值聚类算法简单、收敛速度快、局部搜索能力 强，不过易陷入局部最优。遗传算法是一种通过模拟自然进 化过程搜索最优解的方法 。隐含并行性和对全局信息的有 效利用能力是遗传算法的两大显著特点，前者使遗传算法只 需检测少量结构就有反映搜索空间较大的区域，便于实时处 理；后者使遗传算法具有较强的稳健性，可避免陷入局部最优。 同时 k-均值算法对初始条件较为敏感，不同的初始值的 选择产生不同聚类结果。采用最大最小距离法能动态调整簇 的数目和初始中心点，但用 k-均值仍不能有效处理边界范围， 仍不能保证将对象准确地聚类。 文献[2]虽然能自动得到聚类数目 k，但是在中心点的选取 上是随机的，文献[3]虽然能自动得到聚类数和较好的初始中 心点，但是没有考虑到对边界点处理。 纵观目前各种与 k-均值算法相关的混合算法，大多数基 本上采用某种方法改进，有些与其他算法结合，有些加入其他 挖掘技术进行改进，同时将这几种方法集合的不多。 因此，提出了一种新的改进策略：将局部搜索能力强的 基金项目：国家自然科学基金（the National Natural Science Foundation of China under Grant No.10926189，No.10871031）；湖南省科技计划项 目基金（No.2008FJ3015）。 作者简介：洪亮亮（1987-），女，硕士，研究方向为数据库技术、数据挖掘；罗可（1961-），男，博士，教授，研究方向为数据挖掘、计算机应用等。 收稿日期：2009-10-23 修回日期：2009-12-14 

洪亮亮，罗 可：改进的基于遗传算法的粗糙聚类方法 2010，46（25） 143 k-均值算法和和全局寻优能力强的遗传算法相结合，并引入 粗糙集中的下近似集、上近似集和边界集来处理边界对象。 通过适当调节，发挥各自的优点，提高了聚类的准确性，减少 孤立点对聚类的影响。通过与文献[2]与文献[3]中提出的方 法对比，这种改进的粗糙集聚类算法的聚类效果更好。 X 和 pos R R - (X )是由那些只是根据 R 判断肯定属于 X 的 U 中的元素组成的集合；R- X 是由那些只是根据 R 判断可能属于 X 的 U 中的元素组成的集合；bn (X )是由那些根据知识 R 既不 能判断肯定属于 X 又不能判断肯定属于~X ( = U - X )的 U 中的 元素组成的集合。 R 2 预备知识 2.1 k x 2 }，每个聚类中心个数k，并 n 。聚类可描述如下：对于给定 k-均值聚类算法简介 x 设给定样本集 X={x 1 c 设k个聚类中心分别为c 2c 1 ，…，x 数据集的 n 个点x 按照它们间相似性程度将其划分 ，x 2 1 ，将样本集 X 中各个样本根据最大最小距 为k个簇C ，…，C ，C k 2 1 离原则分配给簇C ；计算新聚类中心c' （i=1，2，…，k），即c' i i X ，其 中 | |C 1 |C J = å 为 第 i 个 簇 的 对 象 数 ，根 据 使 准 则 函 数 )为点 x到簇中心c 的欧氏距离的平 )（d(x - c k å d(x - c å X Î C = | n i i i i i i i i = 1 x Î C i 方）最小进行迭代，直到簇中心不再变化。 2.2 遗传算法简介 遗传算法 [3]是美国 Michigan 大学 John Holland 教授根据 生物进化论和遗传学的思想提出的一种全局启发式优化算 法，它利用遗传算子（选择、交叉和变异），促进解集合类似生 物种群在自然界中自然选择、优胜劣汰不断进化，最终收敛于 最优状态。步骤如下：（1）对解空间进行编码，初始化；（2）初 )i = 12,k；（3）对当前种群的 x 始化种群P(i) = (x 1 )；（4）应用选择算子从当前群 每个染色体x 体中按概率选择个体；（5）按交叉概率 p 将选中的个体基因进 行交叉；（6）按变异概率进行等位基因的变异；（7）应用遗传算 子产生新一代群体 P(i + 1)；（8）判断终止条件，不满足继续 迭代。 计算适应度值 f (x x 2 N c i i 一般每个类都有一个最大的类别数 MaxCNum，杨善林[4] 已经证明，空间聚类能够达到优化MaxCNum £ n，其中 n 为样 本数目。 2.3 粗糙集理论 粗 糙 集（Rough Set）[5] 理 论 是 有 波 兰 数 学 家 Pawlak 在 1982 年提出的一种数据分析理论，常用于处理模糊和不精确 的问题。下面给出粗糙集的一些定义和与本文相关的部分粗 糙集性质： 定义 1 设 U 表示研究对象组成的非空有限集合，称为论 域。R 是 U 上等价关系的族集。U R表示 R 的所有等价关系， [X ]表示包含元素X Î U的 R 等价类。 R 定义 2（不可区分关系） R 的非空子集 P 上的不可区分关 系为ind(P)。 定义 3（上近似、下近似） 给定知识库K = (UR)，对 X ¹ Æ X = {Y Î U/R|Y Í X } 且 X Í U ，一个等价关系R Î ind(K)。称 R - 为 X 关于 R 的下近似，R- X = {Y Î U/R|Y  X ¹ Æ}为 X 关于 R 的 上近似。 定义 4（粗糙集） 若 R - 为 R 的精确集。 X ¹ R- X 则 X 为 R 的粗糙集，否则 X 基本性质：（1）Æ Í A - (X i ) Í A- (X ) Í U； i （2）A - （3）A - (X )  A - i (X )  A- (X (X i j j ) = Æi ¹ j； ) = Æi ¹ j； （4）如果一个对象不属于任何一个下近似，则它必然属于 两个或两个以上的上近似。 3 设计思想 3.1 遗传算法参数及设置 c c m m = 0.07； = 0.005； = 0.6~0.9，取 p = 0.001~0.05，取 p （1）种群大小 p Î[20150]，取 p = 30； （2）交叉概率 p （3）变异概率 p （4）规定初始群体中产生的个体，在将其转化为十进制时 取值不能为 0 和 1 以及大于 MaxCNum 的值，以保证个体的有 效性。交叉后若有个体的十进制值大于 MaxCNum，则重新选 择交叉点直到满足条件为止。变异后若有个体的十进制值等 于 0 或大于 MaxCNum，重新选择变异点直到满足条件为止； （5）选择算子采用轮盘赌注法，每次选择复制时保留当前 种群中适应度值最大的 3 个个体直接进入子代，再从所有的 父代个体中按该法选取剩余的子代个体；采用单点交叉和单 点变异。 3.2 非孤立点选取 设对象x Î C i i ，设置一个半径d 的圆，c(x d)表示以x i i 为中 心d为半径的小圆内点的数目，判断条件： i d(x ) = c(x dd) ³ τ i （1） 若式（1）成立，记该对象为非孤立点，选取所有对象中满足该 条件的点集，以此作为初始中心点的候选点集，尽可能地避免 将孤立点选为初始中心而影响聚类质量。 ))/2。 x 定义 5（圆半径） dd = (max d(x i 定义 6（判决门限） τ = sqrt(n)。 j 3.3 近似集范围 若d(xc ) - d(xc ) £ γ*d(c c i j i j )，则认为 x 同时属于簇 i 和 簇 j 的上近似集，根据γ可动态地调节近似集的范围[6-14]，本文中 取γ = 0.07。 3.4 权重因子 l bnr w ，w 分别调节上近似集和边界集中对象在计算簇中 心时对象所占的比重，两者中的一者太大或太小 ，都会造成 簇中心的偏移，恰当的w 能使簇中心更加准确，文献中 =0.2[15]。 取w 3.5 新的聚类中心 =0.8，w ，w bnr bnr l l ' = w c j l w 其中C ，C l bnr å å i i x x bnr Î C + w 1 |C 1 | |C x l + w i 分别表示第 j 个簇的上近似和边界集。 = 1 Î C bnr bnr | bnr x i l i j = 12,k， （2） 

144 2010，46（25） Computer Engineering and Applications 计算机工程与应用 该个体的适应度。 步骤 2 初始化种群：随机生成 p个染色体的种群。 步骤 3 粗糙聚类：将群体中各个染色体解码，得到各染色 体对应的类别数k，从候选点集中按照最大最小距离原则选取 k 个 对 象 作 为 聚 类 中 心 ，再 按 照 粗 糙 k-均 值 聚 类 准 则 分 配 各点。 （3） （5） （6） 步骤 4 计算适应度： 适应度为：Fit(k) = (E *D 1 步骤 5 选择、交叉、变异。 步骤 6 若达到最大迭代次数，转步骤 7，否则继续步骤 3~ )（对固定的数据集E 固定）。 1 k )/(k*E k 步骤 5。 步骤 7 算法结束。 5 仿真实验及分析 仿真环境：软件：操作系统 Windows XP，编译软件 Mat- ® lab7.0.1；硬件：Pentium D CPU 2.80 GHz，内存 1 GB。 采用最大最小原则能较好地产生初始点，但是对于初始 点选择仍然要有h作为限定来选取个数，而当具体分类不清楚 的情况下很难把握。首先采用重复实验的方法得到h = 4时能 将 Iris 数据集划分得比较精确，再与粗糙集结合得到表 1 中结 果，说明最大最小距离原则与粗糙聚类相结合时能得到更好 的结果。因为h的影响，将遗传算法动态地产生聚类的类别数 k作为最大最小距离原则产生初始中心点的个数（在粗糙聚类 算 法 输 入 ，新 的 中 心 点 按 照 最 大 最 小 距 离 原 则 选 取 d = max(min(d ))，直到找到k个点为止），消除了h对 中心点个数选取的影响，而只与遗传算法的编码有关，而遗传 算法本身又能产生全局最优解；另一方面由于遗传算法收敛 过早，故将其与 k-均值结合，避免早熟；同时将粗糙集中的上 近似与下近似引入用于处理边界点问题，采用粗糙 k-均值收 敛准则作为类内距标准。 ,d i2 d i1 ic 4 改进的基于遗传算法的粗糙聚类方法 4.1 k-均值收敛准则 采用均方误差函数作为收敛准则： J = å k å d(X - c ) i 的欧式距离的平方。 k i X Î C )是对象 X 到簇C i = 1 其中d(X - c 4.2 所提出的粗糙 k-均值收敛准则 * å RJ = å * å d(X - c ) + w (w k i i bnr l i = 1 X Î C lk X Î C lbnr d(X - c )) i （4） 其中第一项为下近似集中的对象到所属中心的距离的加权 和，第二项为边界集中的对象到所属中心的距离的加权和。 粗糙类间距： E 类间距： = RJ k j i k k 2 c D  - c = max ij = 1  粗糙聚类算法： ，h； 输入：w ，w 。 输出：RJ，D k 步骤 1 "x Î U ，按照式（1）算得d(x bnr l i 数是否大于τ，若是则认为对象x 存入另一矩阵，记为 x； i )；判断d(x ) < dd 的个 是非孤立点，将所有非孤立点 i i 步骤 2 对 x 中对象，采用最大最小距离法得到初始k个中 心点：任意选取一个点作为第一个聚类中心记为c ，再选所有 1 对象中与c 距离最大的那个对象作为第二个聚类中心并记为 1 c 2 d 同 时 令 c=2，对 X 中 剩 余 x d d ,d = min(d i1 i1 i2 c )/h（本实验取h = 4）是否成立，若成 步骤 3 判断d > d(c 1 为新的聚类中心，c=c+1，按同样方法继续选取新的 c c 分 别 计 算 到c 1 2 ,d )，d = max(d )； i2 ，取d ic 距 离 为 ic 2 c i i i i 立，则令x 中心点；否则已经得到了k个聚类中心； 步 骤 4 进 行 一 次 粗 糙 聚 类 ："x Î U ，找 出 d(x i c i ) - d(xc j ，使 得 d(xc j j j c i γ*d(c )，则令x )j = 12k} ；若 $c min{d(x c Î-C i i 步骤 5 根据式（2）更新簇中心； c' 步骤 6 对新的k个中心点，c' 1 Î- C j，反之，令x c' 2 k 于距离再次聚类，求出每个簇的下近似集C ； i i ；对每个簇中心，基 和边界集C ； bnr l 步骤 7 判断准则函数式（4）是否收敛；若是则转步骤 8， 否则 iter=iter+1，转步骤 4；得到聚类数k及各中心点； 步骤 8 算法结束。 4.3 改进的基于遗传算法的粗糙聚类算法 取1 < k £ MaxCNum，染色体长度为比 MaxCNum 大的最小 的十进制转换成二进制时对应的二进制的最高的次数再加 2。这样染色体的长度不会因为对象数目的增加而快速增加， 同时能动态地得到聚类中心数目。采用二进制编码。 输入：n 个数据对象，参数 p，p 输出：输出最大适应度对应的类中心及成员对象。 步骤 1 编码：对聚类数k编码。染色体长度为k + 2，前k位 为二进制形式的类别数，第k + 1位为十进制的类别数，末位为 ，γ； m ，p c ) = ) £ i i 通过对 Iris（3 类，150 个对象）数据集进行仿真实验，来验 证提出的算法性能，并与 k-均值算法做了对比，以类间距、类 内聚和分类正确率[16]作为指标。在上述仿真环境下进行 20 次 仿真实验（结合遗传算法的最大迭代次数为 50），结果见表 1， 每类算法对应两行，上下分别为最优解及最差解出现情况。 表 1 对 Iris 数据集聚类结果表 类间距 类内距 最解出现次数 正确率/（%） 算法 Rk+KM MMk+ KM Rk+ RKM MMk+RKM Rk+GA+KM MMk+GA+KM Rk+GA+RKM MMk+GA+RKM 24.88 16.03 25.15 15.41 25.21 12.02 28.59 21.31 33.58 33.23 32.83 32.66 27.59 26.59 32.84 46.87 1 838.00 838.45 1 857.10 830.08 264.82 454.80 268.58 217.02 67.20 37.05 54.53 39.74 118.98 64.49 123.74 67.27 10 5 3 12 2 5 1 2 1 1 1 1 8 6 5 1 89.33 56.00 90.00 66.67 94.00 63.33 97.33 82.67 84.00 42.67 90.00 52.00 82.00 54.67 90.00 66.67 

洪亮亮，罗 可：改进的基于遗传算法的粗糙聚类方法 2010，46（25） 145 实验证明本算法更加稳定。 [2] 刘婷，郭海湘，诸克军，等.一种改进的遗传 k-means 聚类算法[J].数 选择算子采用轮盘赌注法，同时每次选择复制时保留适 应度值最大的 3 个个体直接进入子代，再从所有的父代个体 中按该法选取剩余的子代个体，进行下一次迭代时仍保留适 应度值最大的 3 个个体直接进入子代；交叉算子采用单点交 叉；变异算子采用单点变异。求适应度过程中分别采用 k-均 值收敛准则和粗糙 k-均值收敛准则。采用随机选择k个中心 点记为 Rk，采用最大最小距离原则选择中心点记为 MMk，粗 糙聚类记为 RKM。 6 结论 提出了一种改进的基于遗传算法的粗糙聚类算法。传统 的 k-均值算法和遗传算法都需要确定聚类数目，按照最大最 小原则产生时仍然需要有参数作为限定来选择初始个数，上 述前 4 个算法都需要确定聚类数，而下面 4 个则是动态地产生 聚类个数。本文中算法结合了 k-均值聚类，因而该算法局部 搜索能力强、运算量小，从而能加快算法的局部寻优速度；另 一方面，结合了遗传算法，防止其陷入局部最优；最后运用粗 集理论中上近似集和边界集的思想，使得算法能处理那些处 于边界的很难区分到底是属于哪个簇的类。因此，本文算法 收敛速度较快以及进一步提高了聚类质量。实验结果也表 明，算法能够有效地收敛于全局最优解。但还需要解决以下 几个问题：（1）如何进一步降低计算的复杂度；（2）对于高维度 数据集利用粗糙集属性简约算法进行分析以及如何对海量的 数据进行有效分析将是下一步研究的重点。 参考文献： [1] Han Jia-wei，Kamber M. 数 据 挖 掘 ：概 念 与 技 术 [M]. 范 明 ，译 . 学的实践与认识，2007，37（8）：105-108. [3] 孙秀娟，刘希玉.基于初试中心优化的遗传 k-means 聚类新算法[J]. 计算机工程与应用，2008，44（23）：167-168. [4] 杨善林，李永森，胡笑旋，等.k-means 算法中的 k 值优化问题研究[J]. 系统工程理论与实践，2006，26（2）：97-101. [5] 王彪，段禅伦，吴昊，等.粗糙集与模糊集的研究和应用[M].北京： 电子工业出版社，2008：1-8. [6] 王明春，王正欧.基于粗集与遗传算法相结合的文本模糊聚类方法[J]. 电子与信息学报，2005，27（4）：548-551. [7] 郑超，苗夺谦，王睿智.基于密度加权的粗糙 k-均值聚类改进算法[J]. 计算机科学，2009，36（3）：220-221. [8] 王慎超，苗夺谦，陈敏，等.基于覆盖的粗糙聚类算法[J].电子与信 息学报，2008，30（7）：1713-1715. [9] 王明春，唐万生，江琪，等.基于相对距离的改进粗 k-means 方法[J]. 计算机应用，2009，29（4）：1102-1104. [10] 田地，王世卿.数据挖掘中基于密度和距离聚类算法设计[J].计算 机技术与发展，2006，16（10）：49-51. [11] 万志华，欧阳为民，张庸平.一种基于划分的动态聚类算法[J].计 算机工程与设计，2005，26（1）：177-179. [12] 杨鑫华，于宽.基于密度半径自适应选择的 k-均值聚类算法[J].大 连交通大学学报，2007，28（1）：41-43. [13] 陈燕，耿国华，郑建国.一种改进的基于密度的聚类算法[J].微机 发展，2005，15（3）：17-19. [14] 程国庆，陈晓云.基于网格相对密度的多密度聚类算法[J].计算机 工程与应用，2009，45（1）：156-158. [15] 冯征.一种基于粗糙集 k-means 聚类算法[J].计算机工程与应用， 2006，42（20）：141-142. [16] Davies D，Bouldin D.A cluster separation measure[J].IEEE 北京：机械工业出版社，2007：263-265，383-384. Trans on Pattern Anal，1979，1（2）：224-227. （上接 123 页） 增加，推荐系统的系统实时性要求越来越难以满足，针对上述 问题，提出了一种基于页面内容与页面关联信息的排名技术 算法。该算法结合了页面自身重要度和页面之间的主-子关 联信息从而提高了主页面的排名得分，使主页面的排名优于 子页面，解决了“主题蒸馏”问题。并将排名结果与传统的基 准算法进行了对比，实验结果表明，提出的推荐算法可以大幅 度提高页面排名的准确度，从而有效解决推荐系统处理大规 模数据面临的问题。本文提出的方法还可以应用于音乐、旅 行、购物和 Web 搜索其他领域。 参考文献： [1] Qin T，Liu T Y，Lai W.Topic distillation via sub-site retrieval[J]. Information Processing Management，2007，43（2）：445-460. [2] Shakery A，Zhai C.A probabilistic relevance propagation model retrieval[C]//CIKM2006.New York，USA：ACM for hypertext Press，2006：550-558. [3] Voorhees E，Harman D.TREC：Experiment and evaluation in in- formation retrieval[M].Cambridge，USA：MIT Press，2005. [4] Herbrich R，Graepel T，Obermayer K.Support vector learning for ordinal regression[C]//ICANN.New York：ACM Press，1999： 97-102. [5] Joachims T.Optimizing search engines using clickthrough data[C]// Proceedings of the 8th Discovery and Data Mining.New York， USA：ACM Press，2002：133-142. [6] Liu T Y，Xu J，Qin T.Letor：Benchmark dataset for research on learning to rank for information retrieval[C]//Proceedings of SI- GIR 2007 Workshop on Learning to Rank for Information Re- trieval.Amsterdam：ACM Press，2007. [7] Jarvelin K，Kekanainen J.IR evaluation methods for retrieving highly relevant documents[C]//SIGIR 2000.New York：ACM Press， 2000：41-48.