基于非欧式距离的可能性C一均值聚类.pdf

《基于非欧式距离的可能性C一均值聚类.pdf》由会员分享，可在线阅读，更多相关《基于非欧式距离的可能性C一均值聚类.pdf（4页珍藏版）》请在三一文库上搜索。

1、第 3 8 卷第 6期 2 0 0 6 年 l 2 月 南京航空 航 天 大学学 报 J o u r n a l o f N a n j i n g Un i v e r s i t y o f Ae r o n a u t i c s As t r o n a u t i c s V0 1 3 8 No 6 De c20 06 基于非欧式距离的可能性C一 均值聚类 武 (1 小红 。 周建江 李海林 胡彩平 南京航空 航天大学信息科学与技术学 院 ， 南 京，2 1 0 0 1 6 ； 2 江苏大学电气信息工程学 院 ， 镇江 ，2 1 2 0 1 3 ) 摘要 ： 改进型 可能性 C 一

2、均值 聚类( I mp r o w ! d p o s s i b i l i s t i c C me a n s ， I t C M) 是在 综合 了模糊 c 均值 聚类( F u z z y C me a n s ， F C M) 和可能性C 一 均值聚类 ( P o s s i b i l i s t i c C me a n s ， P C M) 的基础 上得到的 。 在 I P C M 的基础上 ， 利用鲁棒 统计观 点和影响 函数 ， 引入一种 新的距 离度量 以代替 I P C M 的 目标 函数 中的 欧式距 离度 量， 提 出 了一种新 的可 能性c一 均值 聚类模型 (

3、Ah e r n a t l v e i mp r o v e d p o s s i b i l i s t i c C me a n s ， AI P C M) ， 并给 出了该模 型的具体 实现算法 。 AI P C M 具有 良好 的鲁棒 性， 更适合 对舍 有噪 声或 野值 的数据进行划 分聚类。 仿真 实验表 明， AI P C M 能克服噪 声 敏 感性 问题 ， 获得合 适的聚类中心和高的聚类准确率 。 关键词 ： 模糊聚 类；改进型可能性 ( 一 均值聚类 ； 新 的改进 型可能性 C 一 均值 聚类 中图分类号 ： T Pl 8 l 文献标 识码 ： A 文章编 号 ： l

4、 0 0 5 2 6 l 5 ( 2 0 0 6 ) 0 6 0 7 0 2 一 o 4 No n - Eu c l i de a n Ty p e o f Po s s i b i l i s t i c C- - M e a ns Cl u s t e r i n g Wu Xi a o h o n g ，Zh o u i a n j i a n g ，L i Ha i l i n ，t t u Ca i pi n g ( 1 C o l l e g e o f I n f o r ma t i o n S c i e n c e a n d Te c h n o l o g y，Na n

5、 j i n g Un i v e r s i t y o f Ae r o n a u t i c s As t r o n a u t i c s ， Na n j i n g， 2 1 0 0 1 6 ， C h i n a ； 2 Co l l e g e o f El e c t r i c a l I n f o r ma t i o n En g i n e e r i n g，J i a n g s u Un i v e r s i t y，Z h e n j i a n g，2 1 2 0 1 3，Ch i n a ) Ab s t r a c t ：Th e i mp r

6、o v e d p o s s i b i l i s t i c C me a n s ( I P CM )a l g o r i t h m i s a c o mb i n a t i o n o f f u z z y C me a n s ( FCM )a l g o r i t h m a n d p o s s i b i l i s t i c C me a n s( PCM )a l g o r i t h mB a s e d o n I P CM a n d b y u s i n g t h e r o b u s t s t a t i s t i c a l v i

7、 e wp o i n t a n d t h e i n f l u e n c e：f u n c t i o na n e w n o n Eu c l i d e a n d i s t a n c e i S i n t r o d u c e d t o r e p l a c e t h e E u c l i d e a n d i s t a n c e i n I P CM An d t h e n a n o v e l f u z z y c l u s t e r i n gc a l l e d t h e a l t e r n a t i v e i mp r

8、o v e d p o s s i b i l i s t i c C me a n s ( AI P CM )c l u s t e r i n g mo d e l i S p r o p o s e d ，Th e n e w n o n Eu c l i d e a n d i s t a n c e i S mo r e r o b u s t t h a n t h e Eu c l i d e a n d i s t a n c e S o AI P CM i S mo r e r o b u s t t h a n I P CM a n d FC M Fu r t h e r

9、mo r ewi t h t h e n e w n o n Eu c l i d e a n d i s t a n c e ，AI P CM c a n d e a l wi t h n o i s e s o r o u t l i e r s t h a n I P CM a n d FCM Nu me r i c a l s i mu l a t i o n s d e mo n s t r a t e t h a t AI P CM c a n o v e r c o me t h e n o i s e s e n s i t i v i t y a n d o b t a i

10、n mo r e a p p r o p r i a t e c l u s t e r c e n t e r s a n d t h e i mp r o v e d c l u s t e r i n g a c c u r a c y Ke y w o r d s ：f u z z y c l u s t e r i n g；i mp r o v e d p o s s i b i l i s t i c C me a n s c l u s t e r i n g； a l t e r n a t i v e i mp r o v e d p o s s i b i l i s t

11、i c C me a n s c l u s t e r i n g 引 目 在模式识别领域中， 聚类分析是一种非监督学 习算法。而同传统聚类相比， 模糊聚类通常表现出 非 常 明显 的优 势。模 糊 C 一 均 值 聚 类 ( F u z z y C me a n s ， F C M) 是一种非常著名的模糊聚类算法 。 通过可能性约束条件 ， 模糊c均值聚类使数据点在 所有类 中的隶属度之和为 1 。模糊c 一 均值聚类的隶 属度适合解释共享 的概率 ， 但是这个隶属度对于直 观上的属于程度概念不是常常一致相符的。并且 ， 模糊C 一 均值聚类对噪声或野值敏感r 2 】 。为了克服 F C

12、M 的这个缺点 ， Kr i s h n a p u r a m 和 Ke l l e r 2 放弃 收稿 日期 ： 2 0 0 6 0 6 一 l 6 ； 修订 日期 ： 2 0 0 6 0 9 1 2 作者简 介： 武小红， 男 ， 博士研究生， 讲师， 1 9 7 1年生 ； 周建江( 联系人) ， 男 ， 教授 ， 博士生导师 ， E ma i l ： z j j e e n u a a e d u c n 。 维普资讯 第 6期 武小红 ， 等 ： 基于非欧式距离 的可 能性 c 均值聚类 7 O 3 了F C M 的可能性 约束条件 ， 构造 了一个新 的 目标 函数 ， 提 出

13、可能性 ( = 均值聚类 ( P o s s i b i l i s t i c C me a n s ， P C M) 。P C M 能够聚类包含噪声或野值点 的数据 ， P C M 使噪声数据具有很小的隶属度值 ， 因 而噪声对聚类的影响可以忽略。但是P C M 对初始 化 条件很 敏感 ， 常 常会导致 一 致性 聚类结 果口 。 P C M 重视了典型性思想 ， 从而减少了噪声对聚类 的影 响， 但它忽略了隶属度 ， 隶属度可以使类 中心 和数据紧密联系在一起 。为了克服 P C M 的缺点 ， Z h a n g和 I e u n g 在F CM 和P C M 的基 础上 提 出了

14、改进型 可能性 C 一 均值 聚类 ( I mp r o v e d p o s s i b i l i s t i c c me a n s ， I P C M) 。I P C M 解决了F C M 对噪声敏感 和 P C M 一致性聚类的缺点。但 是 F C M， P C M 和 I P C M 的目标 函数中都使用的是欧式距离 ， 在现实 t 日 = 界 中， 这种情况不是常常存在的。最近， Wu和 Ya n g 在鲁棒统计观点和影响函数基础上提出 了一种新的非欧式距离以替代 F C M 和 P C M 中的 欧式距离。 Z h a n g和( ； h e n _ 7 进一步解释了这种新

15、的 非欧式距离 ， 给出了精确的定义 。现将这种新的非 欧 式距离 引入到 I P C M 中以替代 I P CM 中的欧式 距离， 从而得到新 的改进 型可能性C均值聚类( Al t e r n a t i v e i mp r o v e d p o s s i b i l i s t i c C me a n s ，AI P C M) 。由于新的非欧式距离是基于鲁棒统计观点 和影响函数基础上的 ， 所以 AI P C M 比I P C M 更有 鲁棒性 ，为类中心矢量或“ ， 的原型。在 P C M 中 计算如 下 “ 一 K 七一， K 0 ( 3 ) “ = 1 式( 3 ) 中的K

16、通常为 1 。 如果对于所有的 和k ， D O ， 同时m， w1 ； 包含 c个数 据 子集， 则 以下算 法称 为 ： I P C M A( ) 。 初始化： ( 1 ) 固定 f ， 和 的值 ，1 2 c n ， 1 ， +。 。 ； 设置循环初始值 r 一1和最大循环数为r m ( 2 ) 运行F C M 算法 ， 把 F C M 得到的隶属度作 为 I P C M 的初始隶属度 ， 类中心作为I P C M 的 初始类中心 V“ ” ， 然后用方程 ( 3 ) 计算出) 7 ， 。 循环： 用方程 ( 2 b ) 更新典型值 ； 川方程 ( 2 a ) 更新隶属度值u ； 用方程

17、 ( 2 c ) 更新 V ； 增 加 r 。 直到满足条件 (1 l 一 “ l l r )。 1 改进 型可 能性c 一 均值聚 类( I P c M) 2 新的可能性 c 一 均值聚类 ( AI P c M ) 对于给定一个无标记的数据集 一 ， ， ， )c ，将 分成 ( 1 f l ， o ， t ,k l ， 和 一1 ， V k 。 为了优化最小化式 ( 5 ) ， 利用拉格 朗 日乘子法 构造拉格朗 日方程如下 L ( 口 ， t ik , lai ) 一 u ；1 ( 1 一 e x p ( 一 I D l l X 一 I ， ， l l ) )+ 】7 “ ( 1 一 ，

18、 ) 一a ( 一1 ) ( 6 ) 对式 ( 6 ) 中的变量求偏导后等于0 ， 整理和计算得到 如 下方程 = 耋 ( ， V i ， k ( 7 a ) “ = + ( ， V i ， k( 7 b) t ( e x pU ik ( e x p ( 一 X k I， ) ( 一ID ll I， 1l ) ) 一 生一， V i ， J U i k t i ( e x p ( 一 一I， ) ) 将式( 4 ) 代入式( 3 ) 得到 ( 1 一e x p ( 一ID ll 一I， ， ll 。 ) ) ： = K 3 实验仿真 3 1 对噪声数据处理 作者对数据集 X1 2 F 8 9

19、1 做实验 ， 。 是有 1 2个数 据点的二维数据集 ， 它的坐标值和数据在坐标上的 分布见文献 8 ， 9 。 。 中的1 O个数据点 ( 除了点X 和X ) 组成 2个菱形分布在 Y轴两边 ， X 和X 2 到两 类中心距离相等是噪声点。初始化类中心I_ 】 r 0 0 8 0 3 6 l l o 9 9 J 实验条件 ： 一0 0 0 0 0 1 ，最大循环数为 ， 一1 0 0 ， 一 2 0， W = 2 0 数据点 。 和X 在运算F C M 和I P C M 后的隶属 度值均为0 5 。比较文献 8 ， 9 中F C M 得到的隶属 度值 和表 1可看 出， F C M 仅仅产

20、 生隶属度值 ， 而 I P C M 可产生隶属度值和典型值 ， 比如数据点X 和 X 。 的典型值分别为 0 1 5和 0 0 2 ， 也就是说， X 比 X 更加非典型 所 以I P C M 区别出X 和X 并且将 X 和X 从其他数据 中区别开来。因此， I P C M 能区 别出噪声点 ， 对噪声不敏感 ， 而 F C M 对噪声敏感 。 表2为AI P C M 对 运算后的隶属度值和典型 ( 7 c ) 值。首先，设置 ID 一1 1 0 5 8 ， N 2F C M 算法后计算 襄1 I P C M 对X ： 运算后的隶属度值和典型值 ，K 0 ( 8) 式( 8 ) 中的K通常为

21、 1 。 如 果 对 于 所 有 的 i 和 k ，D = 1 一 e x p( 一 l D l l X I ， ， I l ) 0 ， 同时 ， 1 ； X包含 f个数据子 集 ， 则以下算法称为AI P C M A O。 初始 化 ： ( 1 ) 固定 f ， 和W 的值 ， 1 ( ，1 ， +。 。 ； 设置循环初始值 ， 一1和最大循环数为 r m ( 2 ) 选取合适的ID 值 。 ( 3 ) 运行F C M 算法 ， 把 F C M 得到的隶属度作 为 AI P C M 的初始隶属度 ， 类中心作为AI P C M 的初始类 中心 V ， 然后用方程 ( 8 ) 计算出】 7 ，

22、 。 循环 ： 用方程 ( 7 a ) 更新隶属度值U ； 用方 程( 7 b ) 更新典型值 T ； 用方程 ( 7 c ) 更新类 中心 V ” ； 增加 ， 。 直到 满 足 (1 l ， 一 ， l l ， ) 。 寰2 A I P CM对 ： 运算后的隶属度值和典型值 维普资讯 第 6 期 武小红 ， 等 ： 基于非欧式距离 的可能性 c 均值聚类 7 O 5 得到 7 ， 。然后 没置 ， J 一1 2 0 0 ， 运行 AI P C M 算 法 ， 如 何正确选择参数 P的值是一个需要进一步研究的 问题 。 AI P C M 和I P C M 都能避免噪声的影响， 比较 表 1和

23、表 2 ， 对于噪声数据点x ， 运行AI P C M 算法 得到 的典型值要小于运行 I P C M 算法得到的典 型 值， 对于噪声数据 4x 运行AI P CM 和I P C M 得到 的典型值差别不大。所以AI P C M 比I P C M 对噪声 更加 不敏感 。 3 2 聚类中心分析 作者 对数 据 集 做实 验 ， 主 要考 察 F C M， I P C M 和AI P C M 对 运行后所得到的聚类 中心 。 如果所得到 的聚类 中心距离真实聚类 中心 最 近， 则表示该算法得到的聚类中心最好 。 的真实 聚类 中心 足 r 3 3 4 3 34 V Y l l L 0 0 0

24、 0 00J 实验条件和3 1 节一样 ， 这里P = = = 1 ； 3 种算法得到的 聚类中心如表3 所示 。 用 ， I P ( 和 。 分别为 表3中的类 中心 ， 利用下式 汁算类中心 E 一 l l 一 ( 1 0 ) 式中 *表示 F C M I P C M AI P C M。计算 结果 为： E H M一 0 4 1 4 ，EI I 】【 M一 0 0 1 7 ，E A l M= 0 0 0 0 ， 则 E m E【 IJ E 【 ， 。 所 以 Al P C M 得 到 的类 中心 最好 。 表 3 F CM ，I PCM 和 AI P CM 对 t z 和 m运 算 后 得

25、到的聚类 中心 数 据 集 F CM I P CM AI PCM r_ _ 29 9 2 9 9r 3 2 1 3 21 r一 3 3 4 3 3 4 Xl l l l l l l L 0 5 4 0 5 4 L 0 01 0 01 J L 0 00 0 00 r4 94 5 04 r5 0 3 5 12 r5 0 4 51 2 Xm - - l l l l l l L 6 0 7 1 2 2 1 J L 6 0 2 1 2 2 8 J L 6 0 1 l 2 2 8 接管对数据集 做实验 ， 由按正 态分 布的两类组成， 每类 2 0 0个数据点， 两类的均值为： 5 0 6 0 ， 5 0

26、 1 2 o T 。 均方差为1 。 实验条件和 3 1节一 样 ， P 一1 2 0 0 。初使化类中心为数据集的 前 两 个 数 据 点 。 数 据 集 的 真 实 均 值 为 。 ? 。曼 。 运 行 F c M 和 A I P C M,I P C M 算 法 l 6 1 3 1 2 09j 。 运 行 F c M 和 算 法 后得到的类 中心见表 3 ， 3种算法的类 中心都接近 真实的均值 。 3 3 聚 类准确 性 现对 I R I S l 州数据集做实验验证算法 。实验条 件： 一0 0 0 0 0 1 ，最 大循 环数 为 一1 0 0 ， 一 2 0， 一2 0 ， p一 1

27、 2 0 0 。FCM ，I P CM 和 AI P CM 对 I R I S数据集聚类 的准确率 如表 4所示 ， 显然， AI P C M 具 有最 好 的聚类 准确 率 ， I P C M 和 AI P C M 比F C M 计算循环次数多 ， 耗费时间也多。 表 4 F CM ，I PCM 和 AI P CM 对 I RI S数 据 集 的 聚 类 情 况 4 结束语 在基于鲁棒统计观点和影响函数的基础 k， 本 文提 出新的改进型可能性c 一 均值聚类算法， 扩展了 改进 型可能性 f 一 均值聚类算法。与F C M 和I P C M 不 同之处在 于本 文引入新 的非 欧式距 离以

28、代替 I P C M 中的欧式 距离， AI P CM 比I P C M 更加具有 鲁棒性 。用数据集 和I R I S运行 F C M， I P C M 和 AI P C M 算 法 ， 实 验 结 果 表 明 ， AI P c M 比 F C M 和 I P C M 具有更好 的处理噪声数据能力和聚类的准 确率 。 参考文献： 1 B e z d e k J C P a t t e r n r e c o g n i t i o n wi t h f u z z y o b j e c t i v e f u n c t i o n a l g o r i t h ms M N e w Y

29、 o r k： P l e n u m P r e s s ， l 98 1 2 Kr i s h n a p u r a m R，K e l l e r J M A p o s s i b i l i s t i c a p p r o a c h t o c l u s t e r i n g J 1 E E K T r a n s F u z z y S y s t e rns ，1 9 9 3，】 ( 2) 9 8 1 J O Ba r n 1 M ，Cap pe l l i n i V ，M e c o c c i ACo mme nt s on p o s s i b i l i

30、s t i c a p p r o a c h t o c l u s t e r i n g J I E E E Tr a n s F u z z y S y s t e ms ，1 9 9 6，4 ( 3 ) ：3 9 3 - 3 9 6 Z h a n g J i a n g s h e ，L e u n g Y W I mp r o v e d p o s s i b i l i s t i c C me a n s c l u s t e r i n g a l g o r i t h ms J I E E E T r a n s F u z z y S y s t e ms ，2

31、0 0 4 。1 2 ( 2 )：2 0 9 2 1 7 ， W u Ku ol u ng，Ya n g M i ns he ngAl t e r na t i ve C me a n s c l u s t e r i n g a l g o r i t h ms J P a t t e r n R e c o g n i t i o n ， 2 0 0 2，3 5 ( 1 0 ) ： 2 2 6 7 2 2 7 8 Yt , n g M i ns he ng，W u Ku ol ungA po s s i bi l i s t i c t yp e o f a l t e r n a t

32、i v e f u z z y C me a n s ( ： P mc c c d i n g s o f t h e 20 02 I EEE I nt e r na t i o na l Co nf e r en c e on Fuz z y Sy s t e rns Ha wai i ， USA ： I EEE Pr e s s， 2 0 02， 2： 1 45 6 1 45 9 Z h a n g Da o q i a n g Ch e n S o n g c a n A c o mme n t o n AI t e r n a t i v e( me a n s c l u s t e

33、 r i n g I t l g o r i t h ms J j P a t t e r n Re c o g n i t i o n， 2 0 0 4 ， 3 7 ( 2 ) ： 1 7 3 1 7 4 P a l N R，P a l K， Be z d e k J CA mi x e d me a n s c l u s t e r i n g mo d e l ( ： P r o c e s s d i n g s o f t h e I E E E T r a n s Fu z z y Sy s t e ms Ba r c e l on a， Sp a i n： I EEE Pr e

34、s s， l 99 7 1 1 1 21 9 P a l N R， P a I K， B e z d e k J CA p o s s i b i l is t i c f u z z y C me a n s c l u s t e r i n g a l g o r i t h m J I E E E Tr a n s F u z z y S y s t e ms ，2 0 0 5 ，1 3 ( 4 ) ：5 1 7 5 3 0 1 0 B e z d e k J C，K e l l e r J M ，Kr i s h n a p u r a m R，e t a 1 Wi l l t h e r e a 1 r j d a t a s t a n d u p ? J I E E E Tr a n s F u z z y S y s t e m ，1 9 9 9 7 ( 3 ) ： 3 6 8 3 6 9 维普资讯