（计算机应用技术专业论文）基于rough集的层次聚类算法研究及应用.pdf

独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得重庆邮电太堂或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 关右荔2 签字日期： 少p 宁年乡月纠日 学位论文版权使用授权书 本学位论文作者完全了解重迭邮电太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权重迭整电太堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：曩磊磊 导师签名： 签字日期：伽7 年箩月叫日签字日期：1 年箩月2 1 日 重庆邮电大学硕士论文 摘要 摘要 随着信息技术的发展，数据挖掘技术得到了广泛的关注。在数据挖 掘技术中有很多研究领域，聚类分析是数据挖掘的一个非常活跃的研究 方向，有着重要的理论意义和应用价值。目前在文献中存在大量的聚类 算法，算法的选择取决于数据的类型，聚类的目的和应用。聚类算法具 体可以分为划分方法，层次方法，基于密度的方法，基于网格的方法， 以及基于模型的方法等。 在中、小规模的数据聚类应用中，层次聚类算法不仅适合用于任意 属性和任意形状的数据集，还可以灵活控制不同层次的聚类粒度，因此 具有较强的聚类能力。而传统的凝聚层次聚类算法大部分只能处理数值 属性数据，本文针对字符型数据和混合型数据的聚类方法进行了研究。 首先，在经典粗糙集( 又称r o u g h 集) 理论的基础上，通过松弛对象 之间的不可分辨和相容性条件，得到了基于和谐关系的扩展粗糙集模型。 该方法有别于传统凝聚层次聚类算法中广泛应用的距离方法，采用和谐 度的定义，有效地解决了混合属性对象间的相似性度量问题。 其次，重新定义了个体间不可区分度、类间不可区分度、聚类结果 的综合近似精度等概念，提出了一种新的混合数据类型层次聚类算法。 该算法不仅能处理数值型数据，而且能处理大多数聚类算法不能处理的 字符型数据和混合型数据。实验验证了算法的可行性。 最后，结合w e b 用户的行为模型，将新的层次聚类算法应用于w e b 用户挖掘中，提出了一种新的w c b 用户聚类算法。该算法综合考虑了 w e b 用户浏览行为中的浏览时间和浏览频率，提高了w c b 用户挖掘的准 确度。实验证明该算法比单纯考虑时间或单纯考虑频率的算法具有更好 的聚类结果。 关键词：数据挖掘，层次聚类，粗糙集，w e b 用户挖掘 雾琴琴警零爹鬻鼍甍零露臻焉露麓爨霉霹# 器翳露鬻鞲鞭鬻舅紊票臻笺詈烹覆焉焉麓霭 j 重型堕大学硕士论文a b s t r a c t - _ _ _ - _ _ _ _ _ _ - _ - _ - _ _ _ - _ 一一一_ a b s t r a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y ，t h ed a t am i n i n gh a s b e e np a i dm o r ea t t e n t i o n a sw ek n o w ，t h cc l u s t e r i n gi sav e r ya c t i v ef i e l d i nt h ed a t a m i n i n gr e s e a r c h t h e r e f o r e ， t h e r ea r cd i f f e r e n t c l u s t e r i n g a l g o r i t h m sf i tt 0d i f f e r e n td a t at y p e s c l u s t e r i n ga 1 9 0 r i t h m sc a nb er e a l i z e d t h r o u g ht h ep a r t i t i o n i n gm e t h o d ，t h eh i e r a r c h i c a lm e t h o d ，t h ed e n s i t y b a s e d m e t h o d ，t h eg f i d b a s e dm e t h o d ，a n dt h em o d e l b a s e dm e t h o dc t c a m o n gm e d i u ma n ds m a l ls c a l ca p p l i c a t i o no fd a t a c l u s t e r i n g ， h i e r a r c h i c a lc l u s t e r i n ga l g o r i t h mi sn o t0 n l ys u i t a b l cf o ra r b i t r a r y s h a p e d a n da r b i t r a r y a t t r i b u t ed a t as e t s ，b u ta l s 0f l e x i b i l i t vt 0c o n t r o lt h ec l u s t e r s i z ea td i f f e r e n tl e v e l s t h e r e f o r e ， i th a sas t r o n ga b i l i t yt o c l u s t e r i n g t r a d i t i o n a lh i e r a r c h i c a l c l u s t e r i n ga l g o r i t h m c a no n l yd e a lw i t ht h c n u m e “c a lt y p ed a t a ，t h i sp a p e r p r e s e n t san e wc l u s t e r i n gm e t h o dw h i c hc a n d e a lw i t hm i x e dt y p ed a t a f i r s t l y ， t h ep a p e rp r o p o s e sa ne x t e n d e dr o u g hs e t sm o d e lb a s e d0 n c o n c o r d a n c ef e l a t i o nb yt h er e l a t i o n s h i pb e t w e e nt h ei n d i s c e r n i b i l i t ya n d t o l e r a n c ea m o n gr e l a x e do b j e c t s t h i sm e t h o di sd i f f e r e n tf f o mt h ed i s t a n c c m e t h o da p p l y i n gw i d e l yt ot h et r a d i t i o n a lh i e r a r c h i c a lc l u s t e r i n ga 1 9 0 r i t h m ， e f f e c t i v e l yr e s o l v i n gt h ep r o b l e mo fs i m i l a r i t ym e a s u r eb e t w e e no ft h et w o m i x e dt y p eo b j e c t sw i t ht h ed e f i n i t i o no fah a r m o n i o u sd e g r e c s e c o n d l y ， t h e p a p e r ，f e d e f i n e ss o m e c o n c e p t s ， s u c ha st h c i n d i s c c r n i b i l i t yd e g r e eb e t w e e nt w oo b j e c t s ，t h ci n d i s c e r n j b j l j t yd e g r e c b e t w e e nt w oc l u s t e r s ，i n t e g r a t e da p p r o x i m a t i o nr a t eo ft h cc l u s t e r i n gr e s u l t ， e t c m o r e o v e r ，t h ep a p e rp r o p o s e san e wh i e r a r c h i c a lc l u s t e r i n ga l g o r i t h mt 0 d e a lw i t hm i x e dd a t a t h ea l g o r i t h mn o to n l yc a nd e a lw i t ht h en u m e r i c a l l y p ed a t aa st h eo t h e ra l g o r i t h m s ，b u ta l s oc a nd e a lw i t ht h ec h a r a c t e rt y p e d a t aa n dm i x e dt y p ed a t a t h ee x p e r i m e n ts h o wt h em e t h o di sf e a s i b l e f i n a l l y ，an e wh i e f a r c h i c a lc l u s t e r i n ga l g o r i t h mi su s e di nw e bu s e f m i n i n gb a s eo nw e bu s e rb e h a v i o rm o d e l t h ea l g o r i t h mt a k e si n t 0a c c o u n t t h eb r o w s et i m ea n db r o w s ef r e q u e n c yi nb e h a v i o ro fw e d u s e r s ，i m p r o v i n g t h ea c c u r a c y0 fe x c a v a t i o n e x p e r i m e n t ss h o wt h a tt h en e w a 1 9 0 r i t h mh a sa b e t t e re f f e c tt h a nt h ec l u s t e r i n ga l g o r i t h mb y0 n l yc o n s i d e r i n gt i m e0 ft h e j 1 忡一”“叫一i 、。“ 懈o 1 - q # ；_ 媾n 。耳；* 、。? i 船d 二t ，i ”r ? 斗，“n “| 州”矗* ：”l js 4t l 静- o4 川，i - 帏，1e 1 ￥；r 4 “强扣。j 岬# n 学k _ 稿十i 琦m | “。# - ，盈矗女强 t m 赢m ；二；t 拼? ；，一一一“* h i h o 一二一口j 十，。二= 。h * ：f ：州i 。施? 。：一，o 。赢。一。：。一一一二， 、 。一。一- 。 。1， 。一 重庆邮电大学硕士论文 a b s t r a c t f r e q u e n c y k e y w o r d s ： d a t a m i n i n g ，h i e r a r c h i c a lc l u s t e r i n g ，r o u g hs e t ，w c b u s e r o m l n l n g o 重庆邮电大学硕士论文目录 目录 摘要i a b s t r a c t l i 第一章绪论”1 1 1 论文选题背景“1 1 2 层次聚类算法的研究现状2 1 3r o u g h 集研究现状4 1 4 论文主要工作6 1 5 论文组织结构一7 第二章相关理论基础一8 2 1 集合论基础一8 2 2r o u g h 集理论的基本概念一9 2 2 1 信息系统9 2 2 2 不可分辨关系一1 0 2 2 3 可分辨矩阵1 0 2 2 4 信息熵1 1 2 2 5 相容关系1 1 2 3 聚类分析概述1 2 2 ：3 1 聚类的概念1 2 2 3 2 聚类过程1 3 2 3 3 聚类的数据类型- 1 3 2 3 4 相似性度量1 4 2 3 5 主要的聚类算法一1 6 2 3 6 聚类算法的选择一1 8 2 3 7 聚类算法的评价标准1 8 2 4 本章小结1 9 第三章基于r o u g h 集扩展模型的层次聚类算法2 0 3 1 引言2 0 3 2 相关定义2 l 3 2 1 和谐关系与和谐度2 1 3 2 2 层次聚类相关定义2 2 3 3 基于r o u g h 集扩展模型的层次聚类算法2 3 重庆邮电大学硕士论文目录 3 3 1 算法框架概述2 4 3 3 2 算法描述2 5 3 3 3 实例分析2 6 3 4 仿真实验3 1 3 4 1 测试平台和测试数据3 1 3 4 2 实验1 3 2 3 4 3 实验2 一3 3 3 4 4 实验3 3 4 3 5 本章小结3 4 第四章聚类技术在w c b 用户挖掘中的应用3 5 4 1 引言3 5 4 2w c b 用户挖掘3 5 4 3 数据预处理3 7 4 4 用户浏览行为和w e b 站点表示3 7 4 5 基于e r s h c 算法的w c b 用户聚类。3 8 4 5 1 相似性的度量一3 8 4 5 2w e b 用户聚类算法一3 9 4 6 用户聚类实例分析4 0 4 6 1 实例介绍_ 4 0 4 6 2 实例测试4 1 4 7 实验结果及分析一4 2 4 7 1 实验环境4 2 4 7 2 结果对比4 3 4 8 本章小结4 3 第五章总结及未来的工作一4 4 5 1 总结4 4 5 2 未来的工作4 5 致谢4 6 攻硕期间从事的科研工作及取得的研究成果4 7 参考文献”4 8 v 重庆邮电大学硕士论文 第一章绪论 1 1 论文选题背景 第一章绪论 早在1 9 8 2 年，趋势大师约翰奈斯比( j o h nn a i s b i t t ) 在他的首部著作 o ，略( g ) 为对象f 和j f 之间的距离，常用于欧式空间中。 当口= 1 时，明氏距离即为绝对值距离( 又叫曼哈坦距离) 1 4 二：“* - 十二ir ；_ 订；，r 球f m 一q 一 一。砖 t7 ；一d 十乱t ， - * 书w o 一，一* 一。一，- 一，f ，、舐。，一一，船，v h ? q # o 一jw - 。 _ 。o j 1 斗。椰p ：舢一批蒜，。 h d ? 肌t - ；一，一+ 、f 一一4 ，? j _ ，t t 加“卉“渤“# - 。j 二“二“二_ 山m ：。皿。x i k 一o 五血 龇二t i 出女孟品。一 。，“赢。、二 麓厶证， 茄n j ，二吣。”，。“+ ，。“j r 。彳。稚，：，矗：。二一1 。；# 一_ ； 重庆邮电大学硕士论文第二章相关理论基础 州= ( 扣一h i ) 他 当日= 2 时，明氏距离即为欧式距离( e u c l i d e a nd i s t a n c e ) 略( 2 ) 一( 薹i 一x 肚1 2 ) 7 2 c2 1 3 ， ( 2 ) 马氏距离( m a h a l a n o b i sd j s t a n c e ) 考虑到对象的各变量的观测值往往为随机值，因此第f 个对象的p 个分量观测值鼍暑“1 ，毛2 ，嘞) 1 为p 维随机向量。由于随机向量有一 定的分布规律，各个分量之间有具有一定的相关性，因此两个对象作为 两个随机向量的个体，则第f 个与第j 个对象间的马氏距离的平方表示为： 喀j 似) 一“一_ ) r - 1 “一x ，) 其中是随机变量的协方差矩阵 ( 2 1 4 ) ( 3 ) c o s i n e 距离 在聚类分析中，每个对象可以看作n 维空间中的向量，第f 个对象 可以表示为：毛- 。，薯：，屹y 。它们相似系数可用两个向量间的夹角 余弦来表示，于是第f 个与第j 个对象的相似系数表示为： d 玎- c o s ( ) 一 蓍h 味律 ( 2 1 5 ) 与距离函数相对应的能作为相似性度量的相似性函数也应满足四个 条件： ( a ) 对称性 s ( 毛，z ，) - s ( 工，毛) 一 ( 2 1 6 ) ( b ) 正态性 s ( 毛，) 0 f o ra l l 毛a n d ( 2 1 7 ) ( c ) 三角不等式s ( 五，_ ) ss ( 五，) + s ( 以，_ ) ，f o ra l l 薯，吩( 2 1 8 ) ( d ) 自反性 s ( 薯，石，) 一0 i f 五- ( 2 1 9 根据对象特征数据的不同，一般有如下定义相似度的方法。 ( 1 ) 基于距离的方法：距离d 描述的是数据的差异性，而相似度s 描述的是数据的相似程度。相似度和距离的关系可以看为：d 一1 s 一1 ， 即s = 1 + 1 ) 。可以使用上一小节介绍的集中计算距离的方法来计算相似 度占。如使用欧式距离，则有： s “，) 一_ 二可 ( 2 2 0 ) 1 + 陆一嘶2 重庆邮电大学硕士论文第二章相关理论基础 ( 2 ) j a c c a r d 相似度：给出了两个数据公共特征在总特征的比值。 这种方法可以应用在超市购物数据【3 7 】等非数值数据中 跏c 叩以( 训一燕 2 1 ， 通过上面的相似度的计算，得到对象间的相似度，用矩阵的形式表 示出来，通常有两种形式：相似矩阵和相异矩阵。 ( a ) 相似矩阵( s i m i l a r i t ym a t r i x ) 是一个对象一对象的结构。存储 对象间的近似度，表现形式为一个刀厅的矩阵 1 d ( 1 ，2 ) d ( 1 ，3 ) d ( 1 ，厅) 1 d ( 2 ，3 ) d ( 2 ， ) 1 d ( 3 ，厅) i 1 ( 2 2 2 ) d ( i ，_ j ) 也是对象f ，j 之间相似性的量化表示，通常它是一个非负的数 值，当对象f 和j 越相似或越接近，其值越接近1 ；两个对象越不同，越 接近0 。 ( b ) 相异矩阵( d i s s i m i l a r i t ym a t r i x ) 与相似矩阵一样，都是存储刀 个对象两两之间的近似值，表现形式为一个以以矩阵。 0 d ( 2 ，1 ) ，0 d ( 3 ，1 ) ，d ( 3 ，2 ) ，0 d ( 。，1 ) ，d ( 。，2 ) ，彳( i ) ，0 ( 2 2 3 ) 这里的d o j ) 是对象f 和对象j 之间的相异性的量化表示，与相似矩 阵不同的是，当对象f 和j 越相似或接近，其值越接近o ；两个对象越不 同，其值越大。许多聚类算法都是基于相似度矩阵进行聚类分析的，如 果数据是以数据矩阵形式给出的，就需要先转换为差异矩阵，才能利用 聚类算法进行处理。 2 3 5 主要的聚类算法 就目前研究的状况和成果分析，主要的聚类算法大体上可以分为如 1 6 重庆邮电大学硕士论文第二章相关理论基础 下几类： ( 1 ) 基于划分方法 划分方法的基本思想是：给定一个刀个对象或元组的数据库，一个 划分方法构建数据的七个划分，每个划分表示一个类，并且七s 厅，也就 是说它将数据划分为七个组同时满足如下的要求：( a ) 每个组至少包括 一个对象；( b ) 每个对象必须属于且只属于一个类。给定要构建的划分 数目七，划分方法首先创建一个初始划分然后采用迭代的重定位方法， 尝试通过对象在划分间移动来改进划分。 为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。 绝大多数应用采用以下两个比较流行的启发式方法：( a ) k m e a n s 算法， 在该算法中，每个类用该类中对象的平均值来表示。( b ) k m e d o i d s 算 法，每个类用接近该类中心的对象来表示，因此称之为k 中心点方法。 k m e d o i d s 方法比k m e a n s 方法更健壮。这两种启发式方法对在小规模 数据库中发现球状类很适用。 ( 2 ) 基于层次的方法 在第一章已有详细介绍，这里不再赘述。 ( 3 ) 基于密度的方法 基于距离的聚类方法只能发现球状的簇，而在发现任意形状的簇上 遇到了困难，为此提出了基于密度的聚类。其中心思想是：只要临近区 域的密度( 对象或数据点的数目) 超过某个阈值就继续聚类。也就是说， 对类中的每个数据点，在给定范围的区域中必须至少包含某个数目的点。 这种方法可以用来过滤噪声数据，发现任意形状的簇。 多数基于密度的聚类方法对参数都很敏感，参数设置的细微不同可 能导致差别很大的聚类结果。 ( 4 ) 基于网格的方法 基于网格的方法是采用了一个网格的数据结构。它首先将数据空间 划分成有限个单元的网格结构，所有的处理都是以单个的单元为对象的。 这么处理的一个突出的优点就是处理速度快，通常与目标数据库中记录 的个数是无关的，它只是与把数据空间分成多少个单元有关。 、 ( 5 ) 基于模型的方法 基于模型的方法每个簇假定了一个模型，寻找数据对给定模型的最 佳拟合。一个基于模型的算法可以通过构造反映数据点空间分布的密度 函数来定位聚类，也可以基于标准的统计数字自动决定聚类的数目。 1 7 重庆邮电大学硕士论文第二章相关理论基础 2 3 6 聚类算法的选择 使用哪种聚类算法需要考虑各种各样的因素。对于特定的聚类任务， 选择哪种聚类算法更合适，主要取决于以下几个方面的因素。 聚类的类型：不同的应用都有其适合的聚类方法。例如，对于生物 学方面的应用，层次是首选的。 数据集和属性的特性：数据集和属性的类型可能决定所用算法的类 型。例如，k 均值算法只能处理连续型数值属性数据。对于凝聚层次聚 类方法，只要可以创建相似度矩阵，数据集和属性的基本性质就不那么 重要了。 数据的对象个数：数据对象的个数对聚类有着非常重要的影响。例 如：层次聚类算法时间复杂度较高，更适合中、小规模数据集。 属性的个数：属性的个数对聚类算法的影响也较明显。在聚类算法 中，选择那些属性作为聚类依据对聚类结果影响较大。 选择合适的聚类算法涉及很多问题，以及特定的领域知识。不存在 确定的合适的技术公式。 2 3 7 聚类算法的评价标准 聚类是一个富有挑战性的研究领域。如何衡量一个聚类算法的好坏， 主要有以下几种评价标准。 ( 1 ) 可扩展性：好的聚类算法不仅在小数据集上运行良好，在大数 据集上也能运行良好。 ( 2 ) 处理不同类型属性的能力：许多聚类算法是设计来对基于区间 的数值型数据进行聚类的。然而，在许多应用中待聚类的数据可能是二 值型、枚举型、序列性、符号类型，或者这些数据类型的混合体。聚类 算法需要具有处理这些数据类型的能力。 ( 3 ) 发现任意形状的聚类：当前的许多聚类算法基于欧几里德距离 或者曼哈坦距离的相似性度量方法来进行聚类，而这些聚类算法发现的 聚类通常是球状的、大小和密度相近的。而实际上一个聚类是可以具有 任意形状的，如线形、环形、凹形以及其它各种复发不规则形状。这就 要求聚类算法能够发现任意形状的聚类。 ( 4 ) 输入参数对领域知识的弱依赖性：许多聚类算法要求用户输入 一定的参数，如需要发现的聚类数、结果的支持度和置信度等。而聚类 1 8 鐾釜鍪篓篓篓黧篓! 燮! 喾鬻鬻雾鬟+ 曩篓爹寒鬟篓黧篡篓篓篡篓：篓篓薹篓薹嚣薹篓翼纂荔：荔i 篆瑟瑟薹墓器蒌：薹：磊。薹荔篆鋈荔鍪鬟薹器 重庆邮电大学硕士论文第二章相关理论基础 结果通常对这些输入参数非常敏感。但一方面，这些参数往往很难确定， 特别对于高维数据集而言更是如此。这不仅给用户带来了难题，而且也 使得聚类结果难以控制。一个好的聚类算法应该对此给出一个好的解决 方法。 ( 5 ) 处理噪声数据的能力：聚类算法所对应的数据环境中可能存在 大量孤立点、空缺数据、未知数据或错误数据。聚类算法对这些噪声的 敏感度，是评价聚类算法的一个标准。 ( 6 ) 对于输入记录的顺序不敏感：有些聚类算法对数据的输入顺序 非常敏感。同一个数据集按不同的顺序输入，可能产生差别很大的聚类， 这是我们不希望看到的。 ( 7 ) 高维性：目前大部分的聚类算法对于低维数据有很好的效果， 但对于高维数据的效果很差。 ( 8 ) 基于约束的聚类分析能力：在现实世界中的一些应用中，可能 需要在一些约束之下进行聚类分析。假设要在一个城市中确定一些新加 油站的位置，可以对居民住地区域进行聚类，同时考虑城市中的河流、 交通网络，以及每个区域的客户需求等约束条件。设计能够发现满足特 定约束条件且具有较好聚类质量的聚类算法也是一个重要聚类研究任 务。 ( 9 ) 聚类结果的可解释性和可用性：用户往往希望聚类结果是可理 解的、可解释的和可用的。这就需要聚类分析要与特定的解释和应用联 系在一起。因此，应用目标如何影响聚类方法的选择，也是一个很重要 的研究课题。 2 4 本章小结 本章主要对后续章节做一个理论铺垫，首先介绍了r o u g h 集中的一 些基本概念，然后介绍了聚类算法中处理的数据类型和相似性度量等基 本知识，最后阐述了聚类算法的评价标准。 1 9 重庆邮电大学硕士论文 第三章基于r o u g h 集扩展模型的层次聚类算法 第三章基于r o u g h 集扩展模型的层次聚类算法 3 1 引言 聚类就是将数据对象组成不同的类( 或簇) ，使得类间的相似性尽量 小，而类内的相似性尽量大。聚类问题就是在数据未“标记一的情况下， 将数据对象分组成不同的类【3 8 ，3 9 1 。 聚类的关键是要找到这个分类的属性值。事物的属性主要分为数字 属性和字符属性。数据的聚类方法按照处理的属性来划分，可以分为： ( 1 ) 专门处理数字属性的方法； ( 2 ) 专门处理字符属性的方法； ( 3 ) 处理混合属性的方法，可以同时处理数字属性和字符属性。 大部分的聚类方法都是面向数值属性的，针对于字符属性的聚类方 法近些年也出现了一些，而能够处理混合属性的聚类方法则比较少【4 引。 在经典的p a w l a k 粗糙集模型中，近似空间上的二元关系是一种不可 分辨关系，即两个对象是不可分辨的当且仅当对于信息系统中的所有属 性这两个对象的属性值都是相同的。这种关系对知识过分细划，造成知 识“颗粒一太小，而根据o c c a m sr a z or 【4 1 】原理，当不一致率( 不相容对 象的比例) 相等时，粒度大的等价类划分效果好于粒度小的等价类划分。 为此，s k o w r o n 等【4 2 l 提出了利用对象之间的相容关系代替原来的不可分 辨关系来进行近似分类的相容粗糙集( t 0 l e r a n tr o u g hs e t ) ，即两个对象 是相容的当且仅当对于信息系统中的所有属性这两个对象的属性值都是 相似的。 两个对象是等价或相容的当且仅当它们在所有的属性上都是不可分 辨或相容的，这个条件过于苛刻，也过于保守，因而在实际应用中往往 会使得问题复杂化。 针对于上述问题，本章提出了一种基于和谐关系的簇间距离度量方 法，该方法有别于传统凝聚层次聚类算法中广泛应用的距离方法，引入 r o u g h 集中的容差关系采用和谐度作为簇间的相似度，有效地解决的混 合属性对象间的相似度度量问题。并在此基础上提出了一种基于r o u g h 集的层次聚类算法，该算法具有较好的柔韧性，不仅能够处理数值属性 和字符属性，而且可以处理混合属性。 重庆邮电大学硕士论文 第三章基于r 0 u g l l 集扩展模型的层次聚类算法 3 2 相关定义 下面给出本文算法中用到的定义和公式。 3 2 1 和谐关系与和谐度 定义3 1 ：( 和谐关系) 设u 是有限非空的论域，一个和谐关系z 是 一个二元关系，如果丁：u u 一【0 ，1 】满足下面的性质： ( 1 ) 自反性：z o ，x ) 一1 坛u ( 2 ) 对称性：r o ，y ) - z ( ) ，工)坛，) ，u 显然z 是一个定义在精确域上的模糊关系，其中z ( ) 表示两个对象 间的和谐程度，我们定义如下： ， 定义3 2 ：( 和谐度) 令s - 缈，彳，y ，厂) 是一个知识表达系统，定义 z 伍，y ) 竺丝里业鲤生丝业生型盟丝坦型盟坠业( 3 1 ) 伽以h ) 其中伽甩( ) 表示集合的势数，4 为不可分辨属性集，彳：为相容属性 集，且彳一4u 彳2 。当y 一石时， 一 耐( p 黾i 厂口) 一厂( y ，口) ) + 锨以( 口魁i ，似口) 既厂( ) ，口) ”= 缎耐所以 r ，力- 1 。 由于不可分辨关系和相容关系都满足对称性，所以二元关系z 也是 ： 满足对称性的。因此，r 是知识表达系统s 的一个和谐关系【4 叭。 定义3 3 ：( 口一和谐) 如果r 是论域u 上的一个和谐关系，那么对于 任意的口【o 1 】，两个对象工，) ，u 被称为口- 和谐的，记为斌。y ，当且仅 当z ，y ) 口或存在一个序列气，z 2 ，乙u 使得 z ，气) 乏口，丁( 气，z 2 ) 苫口，r ( 磊，) ，) 苫口【3 4 1 。 定义3 4 ：( 等价关系) 对象的初始等价关系定义为民。 珊，一毋 其中 j 2 i t 包i 地再) 咄 ( 3 2 ) z “，工，) 为毛与工，的和谐度，口为所取的阈值。上述定义将一个论域分为 了相似类和不相似类两部分。 定理3 5 ：如果r ：u u 呻【o ，1 】是论域u 上的一个和谐关系，那么凡 是一个等价关系【3 4 1 ，其中口【o 羽。 根据等价关系r 来对论域划分，我们可以得到互不相交的等价类， 记为k 】凡。 燕善罄誉黧笺孽! ，尊孽毫誓荸“曩叠黑i 孽：；了：麓! 善誓臻琵爱毒譬焉0 臻露 冀? j 7 0 0 ? “：等篡：孑- j = ；五z ：i 劳：等”眷冀嚣：篡爿譬”：j 声霸f i 嚣：蔗w i “ 二二。一二一。 一一。 。二 。上。_ “。：。：五；二“：。“一。，二 j 。? 二1 ，。i 如o 。2 ，。盘i z ：二。! 二二，t 罂一一二卅一。i 一”j m 面r ；j n ；一一；：一7 ：e ：。 重庆邮电大学硕士论文 第三章基于r o u g l l 集扩展模型的层次聚类算法 3 2 2 层次聚类相关定义 聚类操作实质上是在样本点之间利用不可分辨性或相似性定义一种 等价关系，在当前的阈值尺度下，类中的任意两个样本点是没有区别的， 一个等价关系就定义了样本点的一个划分，它把样本点划分成一些子集， 一个子集就对应着一个类1 4 3 1 。 下面我们给出个体间不可区分度和类间不可区分度的概念： 定义3 6 ( 个体间不可区分度) 设坛；，x ，u ，则鼍，石，不可区分度 a ；，工，) 定义如下： a “一，) - 高茎几“j ，) ( 3 3 ) 其中y 七( z ；，工，) 一 ：篙z 乞之：t 【t 】r 。，b ，l 曩。分别为形成的r 等价 类。由个体间的不可区分度，可定义类之间的不可区分度： 定义3 7 ：( 类间不可区分度) 设论域u 中的n 个个体经过聚类后得 到c 1 ，c 2 ，c 共r 个互不相交的类，类c p 和类q 之间的不可区分度定 义为 “。去而毒毛从砀 ( 3 4 ) 其中玎p ，刀叮分别为类c p 和c 口中的个体数。 聚类过程可以看作是一种无监督的学习过程，因为没有预先定义的 分类或示例来表明数据集中哪种期望的关系是有效的，多数聚类算法依 靠假设和猜测进行。如何用一种客观公正的质量评价方法来评判聚类结 果的有效性是一个困难而复杂的问题。 广义上讲，聚类有效性评价包括聚类质量的度量、聚类算法适合某种 特殊数据集的程度，以及某种划分的最佳聚类数目。聚类结果的好坏取 决于该聚类方法采用的相似性评估方法以及该方法的具体实现，也取决 于该方法是否能发现部分还是全部的隐含模式。相对评价法寻求一个聚 类算法在一定假设和参数下能定义的最好聚类结果。为