（概率论与数理统计专业论文）模糊kmeans聚类方法研究及改进.pdf

模糊k - m e a n s 聚类方法研究及改进 专业： 硕士生： 指导老师： 概率统计 胡婷婷 罗俊教授 摘要 聚类分析是统计学中的重要分支，在许多的领域中得以应用，如人工智能与 模式识别、生物统计学、市场营销分析和社会统计学等等。这促进了大量聚类方 法的提出和研究。其中基于划分的方法因其简单有效而成为最常用的方法之一， 代表方法有k - m e a n s 方法、k - m e d o i d s 方法以及它们的各种变体。 原始的k - m e a n s 方法其实是一种硬划分方法，后来发展产生了与之相对的 软划分方法。在软计算的方法中，模糊集理论被引用到聚类分析中，并逐渐成为 研究的主流方向。代表方法有f a n n y 方法、f k m 方法及其一系列变体如f u z z y k - m o d e s 、f u z z yk - m e d o i d s 方法，统称为模糊聚类方法。 聚类方法的效果依赖于选用的相似性( 相异性) 度量，在聚类方法中最常用的 度量是欧氏范数。本文引入另一种度量a e 度量( 4 3 节) ，实验说明，它的鲁 棒性优于欧氏范数。 本文对模糊k - m e a n s 方法作了两处改进：( 1 ) 用a e 度量替换经典f k m 、 w f k m 方法中的相似性度量，得到a f k m 、a w f k m 方法。( 2 ) 通过放宽隶属度 的约束条件，对w f k m 、a w f k m 方法作了进一步改进，得到i a f k m 、i a w f k m 方法。实验说明本文提出的新方法与原始方法相比，准确率提高，有效性指标的 变化也说明聚类质量得到改善。 关键词：聚类，k - m e a n s 方法，模糊聚类，特征加权 d i s c u s s i o no fi m p r o v i n gf u z z yk - m e a n sc l u s t e r i n g m a j o r ：p r o b a b i l i t ya n ds t a t i s t i c s n a m e ：h ut i n g t i n g s u p e r v i s o r ：p r o f l u oj u n a bs t r a c t c l u s t e ra n a l y s i si sa ni m p o r t a n tb r a n c hi ns t a t i s t i c sa n da p p l i e di nm a n yf i e l d s 。 i n c l u d i n ga r t i f i c i a li n t e l l i g e n c ea n dp a t t e r nr e c o g n i t i o n ，m a r k e t i n g ，p s y c h o m e t r i c s ， c h e m o m e t r i c s ，e t c t h e r ea r eal o to fd i f f e r e n tm e t h o d s ，a n dp a r t i t i o n i n gm e t h o d b e c o m e st h em o s tc o m m o n l yu s e do n ed u et oi t se f f i c i e n c y t h er e p r e s e n t a t i v e a l g o r i t h m si n c l u d ek m e a n s k - m e d o i d sa n dt h e i rv a r i o u sv a r i a n t s t h eo r i g i n a lk m e a n sa l g o r i t h mi sa c t u a l l yak i n do fh a r dc o m p u t i n g s i n c e f u z z ys e tt h e o r yw h i c hp r o d u c e dt h ei d e ao fu n c e r t a i n t yo fb e l o n g i n gd e s c r i b e db ya m e m b e r s h i pf u n c t i o nw a sp r o p o s e di n1 9 6 5 ，s o f tc o m p u t i n gw a sa p p l i e di nc l u s t e r i n g a n df u z z yc l u s t e r i n gh a sb e e nw i d e l ys t u d i e d t h er e p r e s e n t a t i v ea l g o r i t h m si n c l u d e f a n n yf k ma n dt h e i rv a r i a n t s t h ee f f e c to fc l u s t e r i n ga l g o r i t h m sr e l i e so nt h ed i s s i m i l a r i t ym e a s u r e i n s e c t i o n4 3w ei n t r o d u c ean e wd i s s i m i l a r i t ym e a s u r e a em e t r i c e x p e r i m e n t ss h o w t h a tt h en e wm e t r i ci sm o r er o b u s tt h a nt h ee u c l i d e a nn o r n l i nt h i sp a p e rw ep r e s e n tf o u rn e wa l g o r i t h m s ，t h ea l t e r n a t i v ef u z z yk m e a n s ( a w l m ) ，t h ea l t e r n a t i v ew e i g h t e df u z z yk - m e a n s ( a w f k m ) ，t h ef u r t h e ri m p r o v e m e n t o fw f k ma n da w f k m ( i w f k ma n dt a w f g m ) w h i c hm o d i f yt h eo r i g i n a l a l g o r i t h m sm a i n l yb yt w ow a y s ( 1 ) u s i n gt h en e wd i s s i m i l a r i t ym e a s u r e ，a em e t r i c ，t o r e p l a c et h e e u c l i d e a ns o n s ，( 萄r e l a x i n gt h ec o n s t r a i n t st ot h e m e m b e r s h i p c o e f f i c i e n t s w ei l l u s t r a t et h ea d v a n t a g e so fn e wa l g o r i t h m sw i t hs e v e r a le x a m p l e s k e yw o r d s ：c l u s t e r i n g 、k - m e a n s 、f u z z yc l u s t e r i n g 、f e a t u r ew e i g h t i n g m 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期：刊。年多月# f i 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：蜊黟导师签名：程心 日期：2 d f 啤5 月刁日日期：小1 声妇矽日 中山大学硕士学位论文 第一章绪论弟一早z 百y 匕 1 1 选题背景与研究现状 聚类分析是一门非常实用的统计分析技术。大概5 0 年前，生物学家和社会 学家开始寻找如何在他们的数据中找出同质组的方法。如今，聚类方法在很多领 域中得以应用，如人工智能与模式识别、生物统计学、生态学、经济学、地质、 市场营销分析、医学研究、政治学和社会统计学等等。这愈发促进了多种聚类方 法的产生，并且关于聚类的文章不仅仅只出现在统计学期刊上，而且大量分布在 所有这些领域的期刊杂志上。也正因为如此，还导致了聚类分析有各种各样的别 名，如数值的分类、自动数据分类，等等。 因为其简单有效，划分方法成为聚类分析中最常用的方法之一，代表方法为 k - m e a n s 方法【1 ，2 】和k - m e d o i d s 方法【3 】o 其他方法多为这两者的变体。如黄哲学于 1 9 9 8 年提出的k - m o d e s 方法【4 1 、k - p r o t o t y p e s 方法【4 】，将k - m e a n s 的聚类思想扩展 到分类型及混合型数据上。另外，k m e d o i d s 的代表方法p a m 方法【3 】由k a u f m a n 和r o u s s e c u w 在文献【3 】中提出，并在此基础上提出了改进方法c l a r a 5 1 ，该 方法将p a m 方法与抽样技术结合，对大型数据集表现出良好的伸缩性。n g 和 h a n 进一步提出c l a r a n s 方法【6 1 ，改进了c l a r a 方法每次只在固定样本内搜 索的缺陷。 原始的k m e a n s 方法其实是一种硬划分方法，后来出于发展的需要产生了与 之相对的软划分方法。软计算【7 】中的方法尤其是模糊集理论【8 】被引用到聚类分析 中来并逐渐成为研究的主流方向。代表方法有f a n n y 方法【9 1 、f k m 方法【1 0 1 及 一系列变体如f u z z yk - m o d e s 1 1 1 、f u z z yk - m e d o i d s 方法f 1 2 1 ，统称为模糊聚类方法。 与硬聚类相比，最大的改变是将隶属度系数的取值范围放宽至【0 ，1 】区间，实际意 义其实是允许一个对象同时分享于几个类别之间。 模糊聚类对隶属度系数的另一限制条件是同一对象对所有类别的隶属度之 中山大学硕士学位论文 和必须为1 ，这在某种程度上来说仍然不尽合理，特别是当数据集中有噪声存在 时。因此有的研究者提出通过放宽原始f k m 方法中的隶属度的限制而改进方法 的鲁棒性，如文献 1 3 1 、文献 1 4 1 。 模糊聚类方法还有一个不足之处，即没有细化考虑各维属性对聚类的不同影 响。为此，后来又有研究者提出基于特征( 即属性) 加权的模糊聚类方法，在关于 特征权重的更新方法上，又有两种思路：一种是采用独立的特征选择方法计算每 一个特征的权值，如文献【1 5 】；另一种是在迭代计算聚类中心和隶属度矩阵的同 时更新特征的权重，如文献 1 6 1 。 1 2 本文主要工作和创新 本文按聚类方法的演变顺序依次介绍了划分聚类、模糊聚类、加权模糊聚类 的若干代表方法，模糊聚类是对划分聚类的初步改进，加权模糊聚类则是对模糊 聚类的进一步改进。另外，受文献 1 7 1 提出、文献 1 8 s q i e j b 充的a 度量启发， 本文将修正后的a 度量a e 度量，引入模糊聚类方法及加权模糊聚类方法。 接下来，通过放宽隶属度的约束条件，对方法作了进一步改进。在第五章通过实 验将本文提出的方法与经典方法进行对比。 本文的创新之处有两点： 1 聚类方法的效果通常依赖于所选相似( 异) 性度量，本文介绍了一种新的 相异性度量a e 度量( 4 3 节) ，实验说明它的鲁棒性较欧氏范数更优。并在这 种度量的基础上对经典f k m 、w f k m 方法作出改进，即以a e 度量替代原来的 相异性度量，得到a f k m 、a w f k m 方法。 2 经典f k m 方法中的约束条件规定每个对象对所有类别的隶属度之和为 1 ，这意味着，即使是数据集中存在一个不属于任何类的噪声点，但它仍与其它 对象一样，以1 的隶属度分享于所有类之间。这显然是不合理的。本文通过放宽 隶属度的约束条件，对w f k m 、a w f k m 方法作了进一步改进，得到i w f k m 、 i a w f k m 方法，提高了方法的抗噪能力。 第五章的实验说明，本文提出的四种新方法与原方法相比，鲁棒性明显提高， 达到更好的聚类效果。 2 中山大学硕士学位论文 1 3 本文结构 全文结构安排如下t 第一章，介绍选题背景、本文所做工作及创新点。 第二章，介绍基于划分的聚类方法的几种代表方法，包括k m e a n s 方法、 k - m e d o i d s 方法及两种方法的若干种变体。 第三章，介绍模糊聚类方法的几种代表方法，包括f k m 方法及它的两种变 体。 第四章，主要介绍加权模糊聚类方法w f k m 及引进新度量后的a f k m 及 a w f k m 方法，以及放宽隶属度条件后的加权模糊聚类方法i w f k m 及i a w f k m 方法。 第五章，通过对若干组数据集的实验，将四种新方法与原始方法进行比较。 第六章，总结，并提出进一步改进方向。 3 中山大学硕士学位论文 第二章划分聚类经典方法简介 2 1 划分聚类 聚类分析是过去三十年里被广泛研究的统计学分支，并且在很多领域中广为 应用。聚类方法主要可分为以下几大类：基于划分的方法( p a r t i t i o n i n gm e t h o d ) 、 基于层次的方法( h i e r a r c h i c a lm e t h o d ) 、基于密度的方法( d e n s i t y b a s e dm e t h o d ) 、基 于网格的方法( g r i d b a s e dm e t h o d ) 、基于模型的方法( m o d e l b a s e dm e t h o d ) 等。本 章主要介绍划分方法中几种具有代表性的方法。 划分方法的主要任务是：将n 个对象，划分为k 个组，使在同一个g t ( 或簇) 中的对象之间尽可能的“接近 或相关，而不同组中的对象之间尽可能的“远离 或不同。最著名和最常用的划分方法是k - m e a n s ，k m e d o i d s 和它们的变种。 2 2k - m e a n s 方法 给定一个样本容量为n 的集合x 和类别个数k ，k - m e a n s 方法【1 2 1 的任务是搜 索对集合x 的一个最优k 划分，即分成k 个簇，使簇内离差平方和达最小值，“簇 内离差平方和”指簇内样本到簇均值的累计距离平方。即求解数学问题p ： 七 n m i n p 缈，q ) - 荟善m ，d 2 ( 置，a ，) ( 2 - 1 ) 善吐 h 妇万 m ， 0 ，1 ) ， 1sisn , 1slsk ( 2 - 2 ) 其中w 是一个n x k 矩阵，q 一 q l ，q ：，q 。) 是k 个对象构成的集合，也即各个 4 中山大学硕士学位论文 组( 或簇) 的均值。d ( ，) 是两个对象之间的距离，m ，= 1 表示样本置属于第i 个簇。 若将问题p 的限制条件作些微调整，允许m ，在区间【0 ，1 】上取值。扩展后问 题p 的求解，就需要用到模糊聚类方法【1 9 】，将在第四章具体介绍。 问题p 可通过迭代地求解以下两个问题来解决： 1 问题置：令q = 囝，对方程p ( ，西) 求解形。 2 问题最：令形= 矽，对方程p ( 谚，q ) 求解q 。 问题的解为： m j 一1f ，d ( x f ，q ，) sd ( x f ，q ，) ，f o ，1 s ts k m f 一0f o ，t l ( 2 - 3 ) 问题最的解为： 吼，2 紫 仁q 吼，为第，个簇均值q ，的第j 个分量，1 墨ts 七，1 sj s m 。 k - m e a n s 完整的方法步骤【2 0 ，2 1 1 如下： 1 随机地给q 赋一个初始值a o ，解方程p ( 形，q o ) 得形o 。将t 值赋为0 。 2 取矿一w ，求解方程p ( 谚，q ) 得到q 1 。如果p ( 形，q ) = p 秒，a ) ， 则输出谚，a ，结束；否则转至第3 步。 3 令6 ；q “1 ，求解方程p ( ，q ) 得到w 1 。如果p ( w t , 舀) ；p o , v t + l , 6 ) ， 则输出w t , 委，结束；否则令t = t + l ，转至第2 步。 以上步骤中，第二步实际上是对簇均值的更新，而第三步是对所有样本点的 重新归类。我们以图2 - 1 为例说明这个迭代过程。 图2 - 1 a ) 是十个数据点的初始划分，每个点以菱形标示，根据a ) 所标示的划 分状况计算出两个簇中心，用圆点标注，如b ) 所示。接下来，将每个点指派到离 它最近的簇中心，即对数据点的一次重新划分。重新指派后形成如图c ) 所示的划 分。然后，再根据新的划分重新计算簇中心，得出图中圆点所示的新的簇中心。 5 中山大学硕士学位论文 9 厂】_ 、 0 t 丫rl 6 f 一 。- 5 if l7 3 、 l 2 ii0 、 - 、 u o 23s670口帕 根据初始分布 计算簇中心 - - - - - - 根据新的划分计 算新的簇中心 - - - - - - - 一 图2 - 1k - m e a n s 迭代过程展示 不断地重复这样的迭代过程，最终，当簇中对象的划分不再变化时，方法便 终止。 关于方法的收敛性，文献1 2 1 得出以下结论：因为函数尸( ，) 是非凸的，并 且由方法生成的序列p ( ，) 是严格递减的，故在有限次迭代之后，方法必将收敛 于一个局部最小值。方法的计算复杂度是d ( 砌) ，其中t 是迭代的次数，n 是 输入的数据集中对象的个数，k 是簇的数目。 k - m e a n s 方法有以下几个重要特性： 1 对处理大数据集，方法是相对可伸缩和有效率的。 2 常常终止于局部最优解【1 2 1 1 。 3 只能作用于数值型数据。 4 适用于凸形分布的数据。 关于k - m e a n s 方法的不足及相应的改进方法，文献【2 2 】介绍了以下几个方面： 1 方法只能处理数值型数据，而不适用于分类型数据。k - m o d e s 方法【4 】通 6 中山大学硕士学位论文 过以众数代替均值作为簇中心，对k - m e a n s 作了扩展。 2 方法易受离群点数据的影响，少量的这些离群样本会使均值产生极大偏 差，进而影响聚类效果。p a m 方、法【3 】可弥补这点不足，它从每个簇中选出一个实 际的样本来代表该簇，降低了方法对离群点的敏感性。 3 使用k m e a n s 方法时要求类别的个数k 事先给定。而在现实生活中，k 通常事先是不能确定的。i s o d a t a 方法1 2 3 】是基于k - m e a n s 方法的另一种复杂变体， 该方法能自动调整类别数，找出最佳k 值。 2 3k - m o d e s 方法 在本节及下节将讨论的方法中，我们考虑两种一般的数据类型：数值型和分 类型，与这两种数据类型相对应的属性分别称为数值属性和分类属性。 上节指出，k m e a n s 方法的不足之一是不能用于分类数据的聚类，这是因为 它的相异型度量和所选簇中心均不适用于分类数据。黄哲学于1 9 9 8 年提出了 k m o d e s 方法【4 1 ，可以通过以下手段克服这两个障碍： 1 采用一个适用于分类数据的简单相异度度量。 2 将簇中心换成以众数来表示。 3 用一个基于频次的方法找到众数，解决问题只。 2 3 1 分类型数据的相异度度量 令x ，y 为两个由m 个分类属性描述的对象。x 与y 的相异度表示可以用 这两个对象的m 个属性的累计错配个数来表示。错配个数越少，两个对象就越 相近。这个度量可参考文i 歙 2 4 】中提到的简单匹配相异度( s i m p l em a t c h i n g d i s s i m i l a r i t y ) t 2 4 l 。数学表达式如下： d t ( x ，y ) ；6 ( x ，y ，) ( 2 - 5 ) 其中 7 中山大学硕士学位论文 6 c x ，y ，2 ? 罢，j - y y ，j ； 2 3 2 集合的众数 ( 2 - 6 ) 令x 为若干个由m 个分类属性描述的对象组成的集合。 定义2 1 【l ：向量q ；k 。，g ：，q 肘 是集合x = 怯，五，五 的众数，若它 使函数 d ( x ，q ) 著d - ( 置，q ) ( 2 - 7 ) 取最小值。在此，q 不必是x 中的一个元素。 2 3 3 如何计算集合的众数 令，z q ，为在属性4 上取值为q 。，的对象的个数，厂，似，一c 防) 一等 为属性值q ，j 在集合x 中出现的频率。 定理2 1 【4 l k m o d e s 更新众数方法：函数d 缈，q ) 达最小值当且仅当下列 不等式成立 厂，一q j i x ) l ( a ，一c k ，j 陋) ， 其中口，一c ，一1 ，m 证明：由公式( 2 - 7 ) 有 8 中山大学硕士学位论文 d ( x ，q ) = 善d ，( x ；，q ) 。善著6 “g ，) 。瓣) 2 舯一等) = 妻，z ( 1 一只口，训 因为，l ( 1 一厂，口，= g j 陋) ) 对所有1sj 墨朋都是非负的，故函数d 仁，q ) i 掳4 、值等 价于每项厅( 1 一f 口，- q x ) ) 都取最小值，所以厂，一g 阻) 必须取最大值。 定理2 - 1 给出了从一个给定集合x 求它的众数的方法，从而使k m e a n s 方法 能被扩展到分类数据的聚类。需要说明的是集合x 的众数并不一定惟一。例如， 集合弘，b1r 口，c1r c ，b1 阽，cn 的众数既可以是口，6 1 ，也可以是口，c 1 。 2 3 4k - m o d e s 方法 当采取公式( 2 - 5 ) 为分类数据的相异度度量，目标函数公式如下： 职q ) - 善善酗氓旭，) ( 2 - 8 ) 其中，w i , l 形，q = b ，1 ，劬，2 ，q l ，1 e q ，l isn , l 0 ，对象c 可能会被分到右边 的类，因为它的分类属性的值与该类的大多数对象相同。同样，对象d 可能会被 分到左边的类中。但是，对象a 可能仍将被分到左边的类中，因为它离右边太远， 尽管它的分类属性值与右边的类的大多数对象相同。同样，对象e 可能仍然在右 边的类中。 1 1 中山大学硕士学位论文 图2 3 权重) ，对聚类影响示意图 对象b 的所属类就不确定了，取决于) ，值是偏向分类属性还是数值属性。如果) ， 取值更偏向分类属性，对象b 更可能分到右边的类中，否则，它就更可能分到左 边一类。 对混合型数据采用公式( 2 - 9 ) 为度量函数，目标函数改为： 记 p 缈，q ，一蹇( 骞m ，薹 u 一吼+ y 砉m ，耋? ，吼_ c 2 - 1 。， 公式( 2 1 0 ) 可重写为 弘骞m 蔫k ，嘞) 2 ( 2 - 1 1 ) 。7 ，荟，髻( 2 - 1 2 ) p ，q ) 2 善( 毋7 + ) ( 2 - 1 3 因为只7 ，丑都是非负的，尸( 形，q ) 取最小值等价于e 7 ，异同时取最小值，1s zsk 。 我们可用与2 2 节同样的方法来找到一个局部最优解q + ，形+ ，因为除了d ( ，) 变了之外其它条件都没有变化。给定6 值，我们根据公式( 2 9 ) 按照k - m e a n s 方法 计算出w 。给定缈，我们只需求解出使只7 ，毋取最小值的q 值，1 - ：ls 七。要使 1 2 中山大学硕士学位论文 异7 取最小值，只需按公式( 2 - 4 ) 取口u ，1s j sp 。而要使只取最小值，只需按照定理 2 - 1 取，p + 1s ，sm 。 2 5k - m e d o i d s 方法 k - m e d o i d s 方法中，每个簇用接近聚类中心的一个对象劬( 1s fs k ) 来表示。 它首先为每个簇随机选择一个代表对象；样本集x 中剩余的对象根据其与代表 对象仍( 1 szs 七) 的距离分配给最近的一个簇，然后反复地用非代表对象来代替 代表对象，以改进聚类的质量。该方法的鲁棒性优于k - m e a n s 方法，改善了后者 对孤立点敏感的缺陷。 为了刻画k m e d o i d s 方法，我们以图2 4 所示的数据集为例来展示求解过程。 数据集包含1 0 个对象，每个对象由两个变量表示，x 与y 。表2 - 1 中列出了所有 对象对应的坐标值。 051 01 52 02 53 0 y 图2 - 4 聚类前的1 0 个对象 假定要将数据集分为两类。在方法中首先考虑选择两个代表元，然后在它们 周围构造两个簇。假设第一步选中的代表元为对象1 和5 。表2 2 中列出了此时 每个对象与两个代表元之间的相异度的值、这两个相异度中的较小值以及对应代 x o 8 6 4 2 o j 中山大学硕上学位论文 表元。为简单起见，本例中我们使用欧氏距离为相异度度量。通过计算得到，平 均相异度的值为9 3 7 。这个值能说明结果簇的紧密程度，即本次聚类的质量。 表2 - 1 图2 4 中各点坐标 表2 2 每个对象到代表元1 、5 的相异度 1 4 中山大学硕上学位论文 表2 3 中列出了对象4 和8 被选作代表元时，每个对象与两个代表元之间的 相异度的值、这两个相异度中的较小值以及对应代表元。 表2 3 每个对象到代表元4 、8 的相异度 两次聚类结果的效果图见图2 5 。 以对象4 和8 为代表元时，平均相异度的值为2 3 ，比以对象1 和5 为代表 元时的值要小。用p a m 方法得到的聚类结果与表2 3 中一样，但是最终的代表 对象换成了3 和8 ，更换之后平均相异度为2 1 9 ，要更小一些。 051 01 5 2 02 53 0 y a ) 以对象1 、5 为代表元时的聚类结果 x 0 8 6 4 2 o ，j 中山大学硕士学位论文 2 6p a m 方法 051 01 52 02 53 0 y b ) 以对象4 、8 为代表元时的聚类结果 图2 5 两次聚类结果比较图 k a u f m a n 和r o u s s e e u w 提出的p a m ( p a r t i t i o n i n ga r o u n dm e d o i d s ) 方法【3 】是 最早提出的k m e d o i d s 方法之一。方法由两个阶段组成。 第一个阶段称为b u i l d ，在这个阶段中依次选出k 个代表对象，得到一个 初始聚类。第一个选出的对象是所有对象中与其它对象的相异度的和最小的，也 是在所有对象中落在最中心位置的。接下来，每一步都选择一个对象，使得目标 函数值尽可能快地下降。找出这样一个对象的步骤如下： 1 考虑一个没被选为代表元的对象i 。 2 考虑除已被选为代表元和i 以外的对象j ，它与当前所有代表元的相异 度中的最小值记为d ，对象i 、j 的相异度的值记为d ( j ，f ) ，计算两者的差。 3 如果第2 步中计算的差值是正的，就说明对象j 对把对象i 选为代表对 象的决定有所贡献。这个贡献值记为： c f m a x ( d ，- d ( j ，f ) ，o ) ( 2 - 1 4 ) 4 计算所有未选中对象对对象i 的贡献值的和罗c 。 _ 。 1 6 x o 8 6 4 2 o 中山大学硕士学位论文 5 选择使c 的值最小的对象i 为下个代表元。 不断重复以上过程，直到找出k 个代表对象为止。 第二个阶段称为s w a p ，在这个阶段中尝试更新代表对象以优化聚类结果。 过程中需要考虑到所有的对象对( i ，h ) ，其中i 是已选的代表对象，h 不是。计算 若两者发生交换，即h 取代i 成为代表对象，聚类效果会有什么变化。聚类效果 的评价函数定义为所有对象到离自己最近的代表对象的相异度度量的值的和。 发生一次交换对评价函数产生的影响怎么度量? 在介绍计算方法之前，我们 先做一下符号说明： j ：任意一个未选中的对象 c 油：对象j 对交换( i ，h ) 的贡献值 毛= c 膨： 交换( i ，h ) 对聚类效果的影响值 d ( ，) ：相异度度量 d ，：对象j 到当前所有代表对象之间的相异度的最小值 e ，：对象j 到当前所有代表对象之间的相异度的次小值 对象j 对交换( i ，h ) 的贡献值c 油分三种情况考虑： a ) 若d ， m i n d ( j ，d ，d ( j ，| 1 1 ) ，c 肋= 0 b ) 若d ，id ( j ，i ) ，又分两种情况： b 1 ) 若d ( ，| 1 1 ) e ，则c 脚2d ( j ，j 1 1 ) - d ( j ，f ) b 2 ) 若d ( j ，i 1 ) 苫e ，则c 脚2 e ，- d ， 容易看到在情况b l 下，c 脚可正可负。当对象i 比h 离j 更近时，c 脚为正， 这意味着从对象j 的角度出发，这个交换并不可取。在情况b 2 下，c 脚总是取正 值，因为e ，总是大和。 c ) 若d ， d ( j ，f ) n u m l o c a l ，输出最优节点b e s t n o d e 并终止。否则，转至 第2 步。 第3 步到第6 步是搜索使目标函数值递减的节点。但是如果当前节点在与 m a x n e i g h b o r 个节点比较之后，它的目标函数值仍是最小的，则当前节点是一个 2 1 中山大学硕士学位论文 局部最优解。然后，在第7 步中，这个局部最小值与当前最小目标函数值进行比 较，两者中的较小值贮存在m i n c o s t 中。然后再重新搜索其它的局部最优解，直 到找到n u m l o c a l 个最小值。 从上面的描述中看到，c l a r a n s 有两个参数：n u m l o c a l 和m a x n c i g h b o r ， 前者是搜索次数，也即得到局部最小值的个数，后者是对每个节点搜索的邻居节 点数。参数m a x n e i g h b o r 值设得越大，c l a r a n s 与p a m 就越接近，每次搜索 一个局部最小值的时间也越长。但是同时每次搜索的质量也越高，从而需要的搜 索次数也就越少。 中山大学硕士学位论文 第三章模糊聚类经典方法简介 3 1 模糊聚类的思想 模糊聚类方法，其实是将软计算中的模糊逻辑方法应用到聚类。在本节中， 我们先对软计算做一个简单介绍，了解模糊聚类的应用背景和意义。 3 1 1 软计算的定义 硬计算与软计算这两个术语首先由z a d e h 教授于2 0 世纪9 0 年代初提出【7 1 。 传统计算( 硬计算) 的主要特征是严格、确定和精确。而软计算( s o f tc o m p u t i n g ) 通过对不确定、不精确及不完全为真的值的容错取得低代价的解决方案和鲁棒 性。它模拟自然界中智能系统的生化过程( 人的感知、脑结构、进化和免疫等) 来有效处理日常工作【矧。 软计算中的核心方法主要包括模糊逻辑、进化方法和神经网络以及这几种 方法之间的不同组合形式。这三者分别提供不同方面的能力：1 ) 模糊逻辑主要 处理非精确性和近似推理；2 ) 进化方法则提供进行随机搜索和优化的能力；3 ) 神经网络使系统获得学习和适应的能力。 近来许多学者将软计算中的方法论应用到数据挖掘中，包括对大型的异构数 据集的分析【2 9 1 。在文献【1 2 】中，s u s h m i t am i t r a 将软计算中的粗糙集及遗传算法 应用于聚类【1 2 1 ，对k - m e a n s 方法作出改进。本章介绍的模糊聚类，也是软计算在 聚类问题中的应用之一。 3 1 2 模糊聚类的意义 传统的聚类分析是一种硬划分，它把样本集中每个数据严格地划分到某个类 中山大学硕士学位论文 中，具有非此即彼的性质，因此这种分类的类别界限是分明的。而在现实生活中， 大多数时候事物之间的晃限是模糊的，这种情况下，硬划分方法不再适用。我们 以图3 1 为例说明【9 1 。 图3 1 包括2 2 个由两个数值属性描述的点对象。可直观看出它们大致分为三 类，另外还有两个中间点。如果我们用硬划分方法把对象集分为三类，将不得不 把对象6 姻j 1 ，2 ，3 ，4 ，5 、 7 ，8 ，9 ，1 0 ，1 1 ，1 2 两类中的任意一类，因为对象6 到这两 类的距离几乎相等。同样，对象1 3 也很难被归类，因为它几乎位于三类之间的中 心位置。一个对象属于某类的程度可由在o 至 j l 之间取值的隶属度系数来量化表 示。当我们采取模糊聚类方法( 将于3 3 1 中介绍) 对图3 1 的对象集进行分析时，得 到如表3 1 所示的隶属度系数列表。 图3 - 1 表3 1 包含6 6 个隶属度系数。从表的第一行我们看到对象1 属于类1 的程度是 8 7 ，属于类2 的程度是6 ，属于类3 的程度7 。注意到每一行的隶属度系数的 和为1 。同样的，对象2 、3 、4 、5 对类1 的隶属度较高。对象6 是一个中间情况， 因为它对类1 和类2 的隶属度较高( 4 2 和3 5 ) ，对类3 的隶属度较少( 2 3 ) 。这意 味着对象6 事实上并不属于任何单独的一类，但从数据知道，它离类1 和类2 较类3 更近些。或者说，对象6 构成了类1 和类2 之间的一座桥梁。 6 4 2 o 8 6 4 2 0 11_，_，l 中山大学硕士学位论文 接下来的6 个对象( 对象7 至0 1 2 ) 对类2 的隶属度最高，而对象1 4 到对象2 2 都是 对类3 的隶属度最高。 表3 1 各对象到每个类的隶属度 对象1 3 是最难界定的，因为它位于三类之间的中间位置。在这种情况下，模 糊聚类就发挥出了更好的作用。因为它允许每个样本在各模糊类间分享。例如， 模糊聚类方法可以说对象1 对第一个类的隶属度最高，而对象1 3 在三个类之间被 均匀分享。模糊聚类方法的结果也反映了这一点：从表3 1 可以看到，对象1 3 对 三个类的隶属度很接近，没有对任何一类表现出明显的偏好。 大多数时候，现实生活中的数据与上面的例子一样，并没有严格的界限，在 属性和类别方面存在着模糊性，因此更适合用软划分方法进行分析。z a d e h 提出 的模糊集( f u z z ys e t s ) 理论【8 】为此提供了有力的工具，人们开始用模糊方法处理聚 类问题，并称之为模糊聚类分析。 中山大学硕上学位论文 应用最为广泛的基于目标函数的模糊聚类方法包括以k m e a n s 及其变体为基 础的模糊聚类方法：f u z z yk - m e a n s ( 模糊均值方法) 、f u z z yk - m o d e s ( 模糊众数方 法) 等。本章将一一作出介绍。 为 3 2f u z z yk - m e a n s ( f k m ) 方法 我们在2 2 节曾经提到，f u z z yk - m e a n s 与k - m e a n s 方法的目标函数形式一样， f 眇，z ) 2 荟荟蜕螈工t ) ( 3 1 ) 其中七( s ，1 ) 是给定的类别个数，i 【】是k x n 隶属度矩阵，z ； z 。，z ：，z 。) r 被，为k 个对象组成的集合，d ( ，) q0 ) 一般取作欧氏范数的平方。 但是限制条件有所区别。k - m e a n s 中规定e 0 ，1 ) ，1 墨is 以，1 s ls k ，即 把每一个待识别的对象严格的划分到某个类中。而由上节所述，f u z z yk - m e a n s 对此放宽了限制，允许一个样本分享于几个模糊类之间，从而的取值范围放 宽至区间【0 ，1 】。 荟嘞吐 h 妇力 0s s1 1slsk , lsis 厅 0 善删， kh 七 ( 3 - 2 ) ( 3 - 3 ) ( 3 - 4 ) 在限制条件( 3 2 ) 至( 3 4 ) - f 使公式( 3 - 1 ) 中的目标函数f 最小化问题，是一个带 约束条件的非线性优化问题。常用的方法是先赋值给z ，找出使f 最小化的w 值。然后，固定w 的值，找出使f 取最小值的z 值。f u z z yk - m e a n s 的方法步骤 简述如下： 1 随机选择一个初始点z ( 1 e r 被，找出使f 缈，z o ) ) 取最小值的1 1 。将 t 值赋为1 。 中山大学硕士学位论文 2 找出使f 缈，z ) 达最小的z ( ) 。如果f ( 形，z 1 ) = f ( ，z ) ，结 束；否则转至第3 步。 3 找出使f ，z 1 ) 达最小的形m 。如果f ( ，z ) ；f 缈，z ) ， 结束；否则令t = t + l ，转至第2 步。 矩阵z 和w 根据下面两条定理求解。 定理3 - 1 ：2 值固定，考虑问题 m i nf 眇，2 ) ，以公式( 3 2 ) 至( 3 4 ) 为限制条件 矽 若a 一1 ，问题的解为： 2 d ( z f ，x j ) d ( z ，x f ) ， 1shs 七 其它 1 ， 0 ， 7 割糕广。 对所有1sls 七，1si 墨刀。 x il z l x j z ，h 一1 x f 一2 f 并且x j 一2 ，1s s 七 ( 3 5 ) 定理3 1 的证明在文献 1 0 ，3 0 q b 详细给出，此处不再赘述。注意到当口t1 时解可能存在不唯一的情况，此时w l f = 1 可能会分配给第一个满足条件的z 值， 其它的权值全都置零。 研究文献中多把欧氏范数的平方d ( x ，y ) = 址一y j1 2 用在 k - m e a n s 方法中。在这个前提下，定理3 - 2 成立1 3 0 m 1 ，见下。 定理3 - 2 ：w 值固定，考虑问题只 m i n f ( 形，z ) ， 中山大学硕士学位论文 若采用欧氏范数的平方为d ( ，) ，则问题最的解为： 孙攀， 1slsk ，z ，；j 二匕一， s s(36) 篆w 等 方法的计算复杂度为o ( t k m n ) ，其中t 是迭代次数，k 是类别个数，m 是属 性个数，r l 是样本容量。另空间复杂度为o ( n 似+ 七) + 砌) ，用以贮存n 个对象组 成的样本，聚类中心矩阵z 和隶属度矩阵w 。因此，f k m 方法适合处理大型数 据集。但是，方法只能处理数值型数据，这大大限制了它在数据挖掘方面的应用。 黄哲学继把k - m e a n s 方法推广至分类数据、提出k - m o d e s 方法【4 1 之后，又进一步 对f u z z yk - m e a n s 方法也作出改进，得到f u z z yk - m o d e s 方法【3 2 1 。 3 3f u z z yk - m o d e s 方法 2 3 节已经介绍过k - m o d e s 方法，为黄哲学于1 9 9 8 年提出【4 1 ，是对k - m e a n s 方法作了三处改进：1 ) 采用一个适用于分类数据的简单相异度度量，2 ) 将簇中 心换成以众数来表示，3 ) 用一个基于频次的方法找到众数，解决问题只。通过 这几处改进，k m o d e s 方法突破了k - m e a n s 只能处理连续变量的限制，而仍然保 持了原方法的效率。 2 3 1 中对分类数据的相异度度量已有定义，援引如下： 令x ，y 为两个由m 个分类属性描述的对象，分别记为【戈。，z ：，z 。】，【y ， y 2 ，y 。】。x 与y 的简单匹配相异度( s i m p l em a t c h i n gd i s s i m i l a r i t y ) 定义如下： 其中 州e y ) 。再似x j , y ，) ( 3 - 7 ) 脚沪f 琵j - y j 三 中山大学硕上学位论文 容易验证函数d 。在分数数据集合上定义了一个度量空间。在最初定义的时 候，简单匹配相异度是作用在由分类变量转换而得的0 - 1 变量上【3 3 1 。不难发现d 。 其实是一种广义汉明距离( h a m m i n gd i s t a n c e ) 3 4 1 。 f u z z yk - m o d e s 方法的目的是要找出使如下目标函数达最小值的z 和w ， e 缈，z ) 2 善荟蜕d - ( z ，置) ( 3 - 8 ) 限制条件与f k m 一样，见公式( 3 2 ) 至( 3 4 ) 。此处，z 代表k 类各自对应的k 个 众数的集合，众数的定义见2 3 2 小节。我们可用f u z z yk