一种基于粒度分析原理的模糊聚类算法

《一种基于粒度分析原理的模糊聚类算法》由会员分享，可在线阅读，更多相关《一种基于粒度分析原理的模糊聚类算法（4页珍藏版）》请在金锄头文库上搜索。

1、计算机科学2 0 0 7 V o i 3 4 N Q 8 A 一种基于粒度分析原理的模糊聚类算法* ) AF u z z yC l u s t e r i n gA l g o r i t h mB a s e do nG r a n u l a rA n a l y s i s 赵权1 2 梁吉业1 2 ( 山西大学计算智能与中文信息处理省部共建教育部重点实验室太原0 3 0 0 0 6 ) 1 ( 山西大学计算机与信息技术学院太原0 3 0 0 0 6 ) 2 A 五刚 r a c tB a s e dO nm a n ma l g o r i t h mw i t ht h ef i x

2、 e dn u m b e ro fc l u s t e r sa n df u z z ye - n l e a l 塔a l g o r i t h m an e w f t g z y c l u s t e r i n ga l g o r i t h mb a s e do ng r a n u l a ra n a l y s i si sp r o p o s e dt h r o u g ht h em e a s u r eo tc o u p l i n gd e g r e ea n dc l o s e n e s sd e - g r e eo fw h i c h

3、e x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h ev a l i d i t y K e y w e r d sC o u p l i n gd e g r e e ，C l o s e n e s sd e g r e e 。G r a n u l a rc l u s t e r i n g ，F u z z yc l u s t e r i n ga l g o r i t h m 1 引言 聚类分析作为一种非监督学习方法，是智能计 算领域中的一个重要的研究方向。同时，聚类技术 也是数据挖掘中进行数据处理的重要分析

4、工具和方 法 1 2 。聚类模型和聚类算法的设计是整个聚类分 析过程中最关键的步骤，设计不同的聚类模型，就可 以得到不同的聚类算法。目前出现的聚类算法主要 有 3 5 ：基于层次的方法、基于划分的方法、基于密 度的方法和基于网格的方法等。 聚类分析本身隐含着粒度的思想，因此将聚类 与粒度原理相结合的研究近年来引起了国内外的广 泛关注。国际上，P e d r y c z 6 在粒度计算方法学、信 息粒化算法、聚类意义下的粒度世界描述等方面做 了系统的研究。R a g h a v a n 7 提出了一种聚类算法 来构造最优的粒原型。S u 8 将粒度分析原理与聚 类算法相结合，提出了一种通过信息粒

5、度获取知识 的模型。在国内，卜东波 9 等论述了聚类和分类中 的粒度原理，并提出了一种有效的非均匀粒度分类 方法。徐峰E 1 0 3 等讨论了模糊商空间的聚类，从不同 层次、不同角度合成聚类结果，认为聚类可以以非均 匀粒度来描述样本集。张讲社 1 1 等提出了基于视 觉模拟展现原理的聚类算法，算法中隐含着重要的 粒度选择思想。 在某种程度上数据的聚类过程可看作是一个 数据粒度的变化过程，聚类结果就是在数据的粒度 空间中选择一个( 合适) 粒度。将某种准则下的粒度 选择原理、粒度特性评价思想与聚类分析相结合来 解决聚类分析中重要问题。因此，发展基于粒度分 析原理的聚类算法将成为聚类分析领域的研究

6、热 点。 本文给出了信息粒耦合度测度与贴近度测度的 定义，提出了一种新的基于粒度分析原理的模糊聚 类算法。该算法利用基于确定类别数的最大最小距 离算法构造初始聚类中心，引入隶属度矩阵调整聚 类中心，采用模糊迭代方法得到较优的聚类结果。 2 信息粒度的相关知识 2 1 信息粒度的定义 定义i E 1 2 设给定论域L ，和U 上的一个关系 R ：U 一P ( 【，) ，U U G i ，r 为正整数集，则称G f 为 一个信息粒， G 妇是论域的一种粒度。其中，P ( U ) 表示论域U 的幂集，R 可代表等价关系、不可区 分关系、功能相近关系、相似关系、相等关系、约束、 相容关系、复合关系、模

7、糊关系、属性、投影、结构关 系和一般的函数关系等。 当V ，歹r ，i 歹净Gn G ，= D ，则称 G i ) i Er 是 论域的无重叠粒度划分；当j i ，J r ，i 歹净G i n G p 时，则称 G f ) f r 是论域的一种覆盖。 2 2 信息粒有效性评价函数 本文给出信息粒耦合度测度与贴近度测度的定 义，对信息粒度的有效性进行评价。 定义2 设X = z 1 ，z 2 ，z 。 C R 5 是一s 维 的数据集理是数据集中元素的个数f 为初始聚类 - ) 本文得到国家自然科学基金( N o ：7 0 4 7 1 0 0 3 ) 、高等学校博士学科点专项科研基金( N o

8、：2 0 0 5 0 1 0 8 6 0 4 ) 、教育部科学技术研究苇点项目f N o ： 2 0 6 0 1 7 ) 和山西省重点实验室开放基金( N o ：2 0 0 6 0 3 0 2 3 ) 的资助。赵权硕上研究牛，主要研究领域：机器学习。梁吉业教授，博上生导 师主要研究领域：粗糙集理论、数据挖掘、人工智能等。 1 4 9 个数，d 叠= d ( 锄，v 1 ) = 0 丑一砧0 是样本点如和聚 类中心仇的欧式距离，肛是第惫个样本点属于第i 个类的隶属度值，U = 触) 是一个c X7 “ 的隶属度矩 阵。设C = C 1 ，C 2 ，e 是数据集X 上的一个无 重叠粒度划分。信息粒

9、耦合度测度( C o - ) 定义如下： 目2 ，2 G r , 一乓哗，i = 1 ，2 ，c ( 1 ) 厶1 c f 矗 信息粒之间的贴近度测度( 眈) 定义如下： D s # = d ( v i ，叻) ，i = 1 ，2 ，c ，歹一1 ，2 ，c ( 2 ) 一种新的模糊聚类算法 本文利用基于确定类别数的最大最小距离算法 构造初始聚类中心，采用模糊迭代方法得到较优的 聚类结果。 3 1基于确定类别数的最大最小距离算法 设X = 2 7 l ，z 2 ，磊) C R 是一s 维的数据 集，1 “ 是数据集中元素的个数，c 为初始聚类个数。 基于确定类别数的最大最小距离算法的具体步骤如

10、 下： ( 1 ) 从X 中任选一个样本点作为第一个聚类中 心，记为功。 ( 2 ) 从X 中选出距离口。最远的样本点作为第 二个聚类中心，记为现。 ( 3 ) 计算X 中剩余样本点 五) 与口t ，珑之间的 距离，并求出它们之中的最小值，即 d i = m i n d l i ，d 2 i ，i = 1 ，2 ，7 l ( 3 ) 选出m a x E m i n d 。；，d z i 对应的样本点X i 作为 第三个聚类中心，记为功。 ( 4 ) 设存在五个聚类中心，计算未被作为聚类中 心的各样本点到各聚类中心的距离幽，并选出m a x m i n E d “，d 扪，d 茸 对应的样本点X

11、 。作为一个新 的聚类中心，记为矾+ l z ，。如果五+ 1 O ，则 从垆高矗_ 1 2 ，而扣l 2 ，挖 角如( ) ( 5 ) 若d 叠( ) = o ，则弘叠( ) 一1 。 ( 4 ) 对于数据集X 中的每一个样本点2 7 。，根据 其隶属度触的最大值，将其划分到对应的类G 中， 从而得到聚类结果C ( ) = C 1 ，C 2 ，C ) 。 ( 5 ) 计算新的聚类中心y ( ) 。 ( 触( ) ) 2 z t V i ( ) 一生 一，i = 1 ，2 ，c ( 6 ) ( 妇( ) ) 2 ( 6 ) 计算信息粒的耦合度测度G r ( t ) 。 鲫，= 避Z 筹J x

12、嵩笋飙2 ，c e c , k t )V 证 厂 ( 7 ) 计算聚类的准则函数G D ( ) 。 G D ( t ) 一D s d ( ) 瓯( )( 8 ) ( 8 ) 令f f 一1 ，如果c 1 ，则从C ( ) 中去掉C - r 值最大的类C j ，一+ 1 ，转至( 3 ) ；否则，转至( 9 ) 。 ( 9 ) 选择m a x G D ( t ) 对应的聚类结果C ( f ) 即 为较优的聚类结果，算法结束。 4 实验结果分析 通过使用聚类结构已经确定的实数测试数据 集，对基于粒度分析原理的模糊聚类算法性能进行 测试，同时将其与传统最大最小距离算法0 3 J 和模糊 C 均值(

13、F C M ) 算法- 1 33 进行比较。 实验采用I R I S 数据14 1 作为测试数据集，如图 1 ，其中包含4 3 个样本点，数据集的聚类结构已经确 定，共包含4 个类，类S ：为一孤立点类S 2 的密度 比类s 3 和类S 4 的密度大。 图1 瓜I S 测试数据集 我们分别使用F C M 算法、传统最大最小距离 算法和本文提出的基于粒度分析原理的模糊聚类算 法对该测试数据集进行聚类。 F C M 算法在聚类个数c = 3 时的聚类结果如图 2 所示。 图2 聚类个数c = 3 时F C M 算法的聚类结果 从图2 中可以看出，当F C M 算法的聚类个数 为3 时，S 。和S

14、z 被聚为一类，聚类结果与数据集本 身的聚类结构不相同。 F C M 算法在聚类个数c - - 4 时的聚类结果如图 3 所示。 图3 聚类个数c = 4 时，F C M 算法的聚类结果 从图3 中可以看出，当F C M 算法的聚类个数 为4 时，S 和& 中的部分数据样本被聚为一类，s 2 中其余样本被聚为另一类，聚类结果与数据集本身 的聚类结构不相同。 传统最J c 1 J 、距离算法的聚类结果如图4 所示。 图4 传统最大最小距离算法的聚类结果 从图4 中可以看出，传统最大最小距离算法可 以将S ，聚为一类，但是由于聚类中心的选取，聚类 结果将S 3 中的部分样本点聚到了S z 中，聚类

15、结果 与数据集本身的聚类结构有细小的差别。 基于粒度分析原理的模糊聚类算法在初始聚类 个数c = 1 0 的聚类结果如图5 所示。 图5 初始聚类个数f = 1 0 时，基于粒度分析原理的模糊 聚类算法的聚类结果 3 捌 蛊2 轻 圜 菅1 j j O 1 0987654 3Z 聚类个数 图6 基于粒度分析原理的模糊聚类算法准则函数值随 聚类个数的变化关系 ( 下转第1 5 5 页) 1 5 1 t p Ap r o t o c o l t y p e = t c p Af l a g = S F 净I n t r u - s i o m _ t y p e = n o r m a l ) 的置信度变为0 9 1 。当我 们设置最小支持度为0 2 ， p r o t o c o l t y p e = t o p ， I n t r u s i o n - t y p e = n e p t u n e 从第一个时间窗口 里非频繁项变为最后个时间窗口里的频繁项，它 的支持度为0 2 1 7 ，然后我们得到较有价值的关联 规则I n t r u s i o n _ t y p e = n e p t u n e 净p r o t o c o l t y p e = t o p ，其置信度为1 。该示例验证了模型的正确 性和有效性。 结论本文的主要工作是提出一个面向时序