（计算机应用技术专业论文）参数改变的重复聚类问题研究.pdf

摘要 摘要 聚类分析是数据挖掘的主要技术之一，在各种领域的用途广泛，用户借助 于对数据集的聚类分析来挖掘数据集中数据对象的分类模式。聚类分析挖掘过 程和分类不同，是在无导师监督的情况下进行的，用户不具备对于所处理数据 集的先验知识，为了得到满足实际需求的聚类结果，用户需对同一个数据集进 行参数改变下的重复聚类，其原因在于：( 1 ) 由于缺乏先验知识，用户不能给 出聚类算法的适当参数，而当前的聚类算法大都对于输入参数敏感，这时需要 通过重复聚类寻找其最佳的参数及对应的聚类结果。( 2 ) 用户也常常会人为地 调整参数，以了解不同参数下的聚类结果，而有些聚类算法对于初始条件敏感， 即使输入参数相同，由于初始条件不同，得到的聚类也是不同的，常会陷入局 部最优，参数调整后还需要进行重复聚类以得到较好的一个聚类结果。本文针 对重复聚类的优化与效率问题进行研究，给出相应的解决方法，所做的主要创 新工作如下： 对上述两种需要进行参数改变的重复聚类的情况进行了概括，给出了其形 式化定义，定义其为以输入参数作为决策变量、以评价对应聚类结果的基于相 对标准的有效性函数为优化函数的非线性规划问题： i i l i n ( i n a ) 【)，( c ) j j 只i g d 其中，p 出为输入参数，约束条件d 表示参数的允许取值范围。对于用户人 为调整参数的情况，d 表示用户指定特定参数值；在参数未知的情况下，d 表示 参数可能的取值范围；c 为p m 。对应的最佳聚类结果。 制定了适用于作为重复聚类问题优化函数的有效性索引函数：i e c c 索引和 c o ms e p 索引，这两个索引函数不仅能够对聚类结果的整体情况作出评价，而 且还能够对聚类结果中簇的具体分布情况作出评价。i e c c 索引速度较快，但是 主要适用于只包含凸形簇的聚类结果，应用范围较窄。c o ms e d 索引可以评价 出包含任意形状簇的聚类结果的性能，应用范围更加广泛，但是计算时间复杂 度比i e c c 高。 给出了参数改变时重复聚类问题的可继承算法和迭代优化方法。由用户调 摘要 节的参数改变下的重复聚类问题，主要通过对现有聚类结果的继承，避免新聚 类结果受到初始条件的影响而陷入局部最优，以较快的速度得到质量较好的新 聚类结果。对于用户未知参数的重复聚类问题，本文深入地研究了有效性索引 函数各组成项与输入参数之间的关系，利用在最佳参数附近簇内紧密程度关于 输入参数曲线曲率最大这一特性，得到最佳参数的近似值，把参数限定到有效 性索引函数包含极小值的单谷部分，利用改进的步长加速法求得极值，即最佳 的参数和其对应的聚类结果。 本文对不同参数对应聚类结果中簇的可能变化情况进行分析，指出在参数 变化时应该引起用户的注意、需要报告出来的聚类结果变化情况，并提出通过 比较聚类结果中各个簇几何信息得到。本文采用c f 簇表示方法，通过其储存的 信息可以快速有效地得到所需要的几何信息，给了检测聚类结果变化的c a 检测 算法，实验表明该算法能够有效地检测出不同参数下聚类结果中簇分布情况的 变化，提供给用户关于不同聚类模型变化的知识，以指导其更好地进行决策。 关键词：数据挖掘聚类分析有效性索引函数非线性规划重复聚类 i l a b s t r a c t a b s t r a c t c l u s t e r i n ga n a l y s i si so n eo ft h em o s ti m p o r t a n ta r e a so fd a 恤i i l i i l i n g ，a i l di th 够 b e e n 、i d e l yu s e di l ln u m e r o l l s 印p l i c a t i o n s nc a i lh e l pm e u s e rd i s c o v e ri m e r e s t i n g d i 蚰曲u t i o i l sa n dp a n e m si nt h cu n d e d y i n gd a 协u m i k ei nc l a s s i f i c a t i o n ，m ep r o c e s s o fc l l l s t e r i i l ga n a l y s i si so fl l i l s u p e r v i s e dl e 锄i n g ，锄dt h eu s e r sh a v en oa p r i o r i k n o w l e d g ea _ b o u tm ec o 璐i d e r e d 出妇s e t t ba c l l i e v eas 仃a t i 母i n gc l u s t e r i n gr e s u l t ，i t r l e e dt h eu s e rr e p e a tc l u s t e f i n gp r o c e s ss e v e r a lt i m e so nm es a m ed a t 觞e t ，t l l i si s a c c o r d si i lt h ef o l l o 丽n gc 船e s ：( 1 ) b e c 肌s eo f h a v i n gn o 面o rk i l o w l e d g e ，t l l el l s e r c a n tg i v e 也ep m p e r 血p u tp a m m e t e r s ，a i l dt l l ee x i s t i n gc l l l s t e r i n ga l g o r i t i l m sa r e s e n s i t i v et ot l l ei 叩u tp 甜a r n e t e r s ，i no r d e rt oa c h i e v et h ep r o p e rp a m m e t e r sa i l dt l l e o p t i m 啪c l u s t e 血gr e s l l l t ，t l l ec l u s t e r i n gp r o c e s ss h o l l l db em ni t e 枷v e l y ( 2 ) t of m d 也ed i f f b r e mc l u s t e 血gk 1 1 0 w l e d g eo fd i f f e i 。e n tp a r a m e t e r s ，m eu s e r so f t e na d j u s tn l e p a r 锄e t e r sb y 血e m s e l v e s b u ts o m ec l u s t e r i n ga l g o r i m m sa r es e i l s i t i v et ot h ei i l i d a l c o n d i t i o n s ，d u et od i 矗b r e mi l l i t i a lc o r l d i t i o n sl e a dt od i f f b r e n tc l l l s t e r i n gr e s u h su n d e r 血ed a r 锄e t e r sa r es a m e ，孤dt h er e s i l l t so f t e nf 融l i m ot h e1 0 c a lo p 6 m 啪mt h i sc a s e ， i ta l s 0n e e dr e p e a tt h ec l u s t e r i n ga l g o r i m mt og e tak t t e rr e s u l t f o rt l l ea b o v e m e 矾o n e dr e 硒o n s ，i ti sn e c e s s a r yt or e p e a tc l u s t e 血ga i l a l y s i si no r d e rt og e tt l l e o 埘删l r n 他s u l t s i i lt 1 1 i st h e s i sw eg i v et h er e s o l v es 仃钺e g yf o rt l l i sp r o b l e m ，a i l dm e m a i nc o n l 五b u t e so f t l l i sd i s s e r t a t i o na r ea sf o n o w s ： s 啪m a r i z e 也et w oc 勰e sn e e d i n gr e p e a tc l u s t e r i n ga i l dg i v et l l ef o m l a l d e f i 疵i o n ，w h i c hl l s e st 1 1 ei n p u tp a r a m e t e r sa sd e c i s i o n v a r i a b l ea i l dt l l ec l u s t e r i n g r e s u l ta st a r g e tf i l n c t i o n i ti sd e f i n e da s ： m i n ( m a x )厂( c ) j j 只】g d w h e r edi st h ev a l u er a l l g eo f p a r a m e t e r 蹁g ，i ti s 印e c i f i e db yt h eu s e ri nt h ef i r s t c a s e ，a i l di ti st 1 1 ea l lt l l ea l l o 、e dv a l u e si nm es e c o n dc a s e ，ci s 也ec l u s t e r i n gr e s l l l t u n d e r p m 分 t w oc l u s t e rv a l i d i t yi n d i c e sa r ed e f i n e d ，w h i c ha r es u i t a b l e t om er e p e a t i i i a b s t r a c t c l u s t e r i n g ，a 1 1 db o t ho fm e mn o to n l yc a i la s s e s st h ev a l i d i t yo fw h o l er e s u l tb u ta l s o c a i la s s e s st h ev a l i d i t yo fe v e r yc l u s t e ri nm er e s u l t t h ef i r s tc o m a i n i n gi si e c c i n d e xw h i c hc a l lb ec o m p u t e dq u i c k l yb u tc a no n l yb eu s e dt oe v a l u a t et l l ec l u s t e r r e s u l ti n c l u d i n go n l yc o n v e xc l u s t e r s t h es e c o n dc a i le v a l u a t et 1 1 e c l u s t e rr e s u l t i n c l u d i n g 抽i 仃a 町s h a p ec l u s t e r sb u ti t sc o r n p u 诅t i o n a lc o m p l e x 毋i sh i 曲e rt l a i lt 1 1 e f i r s t g i v et l l ei n t e r c a l a t i v eo p t i m a ls t r a t e g yo fr e p e a t c l u s t e r i n g i nt h ec a s eo f p a r a m e t e r sa d j l l s t e db ym eu s e r w ea i l l lt oi i l l l 甜tt l l ek n o w l e d g eo ft h ee x i s 廿n g r e s u l t s ，州c hc a i la v o i dt l l en e wr e s u l t 脚l i m o 也el o c a lo p t i m u i n ，a 1 1 dg e tab e t t e r r e s i l l tq u i c k l y f o rt 1 1 ec a s ei nw h i c ht l l eu s e rc a n tg i v et l l ep m p e rp a r a m e t e r s ，w e e s t a b l i s h 也er e l a t i o n sb e t 、v e e nt h ev a l i d i t ) ri n d i c e sa n dt 1 1 ep a r 锄e t e r s ，a n du s et l l e f b a t l l r et of i n dm ea p p r o x i m a t ev a l u eo f 叩t i m a lo fp a r 锄e t e rw h i c hi sp r o x i m a lt h e c u a t u r eo nt 1 1 ec u r v eo fc o i n p a c m e s so fc l u s t e rw r t p 猢e t e r s ，a 1 1 du s i n gt l l e a p p m x i m a t e 砌u ea st l l ei i l i t i a lo f m en o i l l i n e a rp r o g r 锄，w ec a l lg e tt 1 1 eo p t i m 啪b y i m p r o v e dh o o k - r e e v e sa l g o r i t h m t l l i sm e s i sa l s oi n v e s t i g a t e sm ec h a i l g es 协t e sb e t w e e nd i 娲r e n tc l u s t e r i n gr e s u l t s 1 1 1 1 d e rd i 虢r e n tp a r 咖e t e r ，a n dp o i n t so u tt 1 1 ec h a n g es t a t e sw h i c hs h o u l db en o t m e d a b o u tt 1 1 eu s e la n dm er e s e a r c hs h o w st l l a tb yt 1 1 eg e o m e 仃yi 耐o r n l a t i o no fc l u s t e r s c a ng e tt l l ec o n c r e t ec h a l l g eo f d i 脏r e n tr e s u l t s a n a l y z i n gm e e x p r e s s i o n so f c l u s t e r s ， w ef i n dt 1 1 a tb ym ec fe x p r e s s i o nw ec a ng e tm eu s e 龟lt l l eg e o m e t r yi n f o 瑚a t i o n s o an e w a l g o r i m m ，c a ，i sp r o p o s e d ，w 1 1 i c hd e t e c t st 1 1 ec h a l l g e so fr e s u l tb a s e do nc f v 甜f i e db yt l l ee x p e r i m e n t sc ac a nr e p o r tt l l ec h a n g eo fr e s u l t se 脏c t i v e l y ，a i l dg i v e m o r ek n o w l e d g et ot h eu s e ro f d a t a s e tw l l i c hc a nh e l p 也e mm a k eo u tb e t t e rs n a t e 黟 k e yw b r d s ：d a 协m i i l i n g ，c l u s t e r i n ga n a l y s i s ，c l u s t e r i n gv a l i d i t yi n d i c e s ，n o n l i n e a r p r o 孕锄，r 印e a tc l u s t e r i n ga n a l y s i s 柯开人学学位论文版权使用授权书 y 9 6 8 9 2 3 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定，同意 如下各项内容：按照学校要求提交学位论文的印刷本和电子版本；学校有 权保存学位论文的印刷本和电子版，并采用影印、缩印、扫描、数字化或 其它手段保存论文；学校有权提供目录检索以及提供本学位论文全文或者 部分的阅览服务；学校有权按有关规定向国家有关部门或者机构送交论文 的复印件和电子版；在不以赢利为目的的前提下，学校可以适当复制论文 的部分或全部内容用于学术活动。 学位论文作者签名：别烫 如d 年占月工 日 经指导教师同意，本学位论文属于保密；在年解密后适用本授 权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： 内部5 年( 最长5 年，可少于5 年) 秘密l o 年( 最长1 0 年，可少于l o 年) 机密2 0 年( 最长2 0 年，可少于2 0 年) 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究 工作所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成 果不包含任何他人创作的、已公开发表或者没有公开发表的作品的内容。 对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明 确方式标明。本学位论文原创性声明的法律责任由本人承担。 学位论文作者签名：剀复 m g 年岁月砀日 第一章绪论 1 1 1 聚类的基本概念 第一章绪论 第一节聚类分析研究现状 数据挖掘是指从数据库或数据仓库中提取隐含的、未知的、非平凡的、有 潜在应用价值的信息或模式，它是数据库研究中很有价值的新领域，融合了数 据库、人工智能、机器学习、统计学等多个领域的理论和技术。在银行、电信、 保险、交通、零售( 如超级市场) 等商业领域已有广泛的应用，如数据库营销、 客户群体划分、背景分析、交叉销售等市场分析行为，以及客户流失性分析、 客户信用记分、欺诈发现等等。 聚类是数据挖掘的主要技术之一，是一种无监督的模式识别方式，它的主 要任务是将物理的或抽象的对象分组成为由类似对象组成的多个类( 簇) 的过 程。聚类的结果是一组数据对象的集合，这些对象与同一类中的其它对象彼此 相似，与其它类中的对象相异。在许多应用中可以将类中的对象作为一个整 体来对待。 在统计分析中，聚类也称为聚类分析，它与回归分析、判别分析并称为多 元分析的三大方法，主要研究基于几何距离的聚类，如欧氏距离、明考斯基距 离等。传统的统计聚类方法包括：系统聚类法、分解法、加入法、动态聚类法、 有序样品聚类、有重叠聚类和模糊聚类等。这些聚类方法属于基于全局比较的 聚类方法，它需要考察所有个体才能决定类的划分，因此所有的数据必须事先 给定，而不能动态增加新数据对象。这样的聚类分析方法不具有线性的计算复 杂度，难于适应数据库非常大的情况。 在机器学习中，聚类称作无监督或无教师归纳”。同分类学习2 】【3 】【4 1 相比， 分类学习的例子或数据对象有类别标记，而要聚类的例子则没有标记，需要由 聚类学习算法自行确定。在神经网络中【5 】【6 j ，有一类无监督学习方法：自组织神 经网络方法，如k o h o n e n 自组织特征映射网络、竞争学习网络等等。在数据挖 掘领域里，神经网络聚类方法主要是自组织特征映射方法，i b m 在其发布的数 第一章绪论 据挖掘白皮书中就特别提到了使用此方法进行数据库聚类分割。 在数据挖掘中，聚类问题实质上是在一定的规则约束下的优化问题，只是 不同的聚类方法其聚类对象的属性值与优化函数不同。多元数据分析处理的大 多是矩阵型的数据，或者是经过预处理后可以表示为矩阵的数据，这种包含了 待处理数据对象及其属性值的矩阵也称为二维数据。但是在许多情况下，将数 据随时间变化的信息也包含进来，就形成了三维数据，显然二维数据只是三维 数据的一种特殊情形，即某一时刻的数据表现【7 】q 为了更清楚地描述聚类问题， 聚类分析的定义如下： 簇( c l u s t e r ) ：一个数据对象的集合。在同一个类中，对象之间具有相似性； 不同类的对象之间是相异的。 聚类分析：把一个给定的数据对象集合分成不同的簇。具体定义如下： 在空间x 中给定一个有限的取样点集( 或从数据库中取得有限个例子的集 合) ， x l ，x 。) ， 聚类的目标是将数据聚集成类，使得类间的相似性最小，而 类内的相似性尽量大。【8 j 1 1 2 主要聚类算法 1 1 2 1 基于分割的算法 给定一个n 个对象的数据集，一个划分方法构建数据的k 个划分，每个划 分表示一个簇，并且k o ( 4 ) + l2 + 气 ( 5 ) 若满足终止条件准则，令z + = & + 1 ，输出x + ，计算停止；否则，k k + l ， 转( 2 ) 。 2 3 1 4 牛顿法 设无约束问题为m i nf ) ，x e ；设f ) 为二次可微函数，x 是f ) 的无 约束极小点，当前点x k 在x + 的附近，那么，优化函数的过的等值面是近似 的椭圆面。这时可以采用n 咖o n 方向作为下降方向，表示为 p k 2 一h ( x k ) 一1 v f ( x k ) 。若8 l ，8 2 为事先给定的小整数，x o 为初始点，k = o 。则其 步骤如下： ( 1 ) 计算v 2 “) ，令：= v 2 ，( k ) ( 2 ) 若鬈1 存在，且可孤& ) 丁v 日君w 弋x ) 气，令气2 一丐1 可丁( & ) ， 否则，令最= 一v 厂( 墨) ； 第二章重复聚类的形式化描述 ( 3 ) 求解i i l i n 厂( 墨+ 丑只) s t ，五0 设五是此一维搜索的最优解 ( 4 ) 气+ 1 2 + 气气 ( 5 ) 若满足终止条件准则，输出令x k + l ，计算停止；否则，七+ ，转( 1 ) 。 2 3 1 5 步长加速法 步长加速法也称之为离散步长的h o o k r e e v e s 算法，是一种不使用导数的直 接搜索算法，其算法过程可以分成两个基本阶段：坐标循环试探及模矢加速搜 索。坐标循环试探，就是在第k 次迭代时，从初始试探点y 0 出发，依次沿n 个 坐标方向用固定的步长进行试探，寻找更好的点y l ，y 2 ，y 。，并记y n 为 凰小而模矢加速搜索，就是沿模矢方向( 凰+ ) 加大步长前进，以得到第n j 次迭代的出发点，这样就完成了一次迭代，然后再从新的场出发，进行下一 轮坐标循环试探，如此重复进行，使目标值不断减少。 可以证明，步长加速法的收敛速度是线性的，且如果优化函数可微，则可 收敛到平稳点。另外，由于该方法不使用导数，故可应用于任何形式的优化函 数。h 3 l 以上五种方法为常用的非线性规划寻优算法，用户可以根据具体问题的特 点和具备的实际条件选择最为合适的方法进行求解，另外一些优化算法的详细 内容请参看文献【4 3 ，6 1 】，例如，共轭方向法和共轭梯度法、拟n e w t o n 法、罚函 数法和障碍函数法。 2 3 2 重复聚类问题的优化算法 由上面的介绍可以看出，部分非线性规划最优化算法对优化函数有一定的 要求，例如，迭代下降算法、最速下降法都要求优化函数可微，n c w t o n 法要求 优化函数二次可微。由于重复聚类问题的优化函数( 基于相对标准的有效性索 引函数) 是一个以数据集中所有数据对象( 或者所有簇) 为决策变量的函数， 很难判断其是否可微，所以为了得到最佳的聚类结果，我们除了要制定出适于 非线性优化问题的有效性函数作为优化函数外，还需要对现有的非线性优化算 第二章重复聚类的形式化描述 法进行研究，找出适于参数改变的重复聚类问题的迭代寻优方法步骤。为此本 文把要求连续、可微的优化方法排除在外，余下的几种方法为对分法、f i b o n a c c i 法和0 6 1 8 法( 都属于一维搜索算法) 、以及步长加速法等。 其中对分法、f i b o n a c c i 法和o 6 1 8 法都属于一维搜索算法，主要是求一元函 数的最小值，且多应用于单谷函数( 或称下单峰函数) ；步长加速法可以用于多 维无约束极小化问题，并可以证明其收敛速度是线性的。目前聚类算法的输入 参数形式多样，例如，基于分割的聚类算法一般要求用户输入簇的个数作为参 数，而d b s c a n 算法要求输入邻域的半径和最少数据对象数目蚴印招两个参 数，e m 聚类算法会要求用户输入高斯模型的参数。显然三种优化方法中，步长 加速法较前两种适合于解决重复聚类问题。我们将对其进行深入研究，以找出 重复聚类问题的迭代优化方法。 表2 10 6 1 8 算法 第二章重复聚类的形式化描述 表2 2 加速步长法 x o 为初始点，q ，8 2 ，依次是n 个坐标轴的单位方向向量， 0 为 初始坐标循环试探的步长，口 1 为模矢加速的加速步长因子。s 为预先 确定的正数，占为迭代终止条件。 ( 1 ) k = ，_ i = o ，j = o 0 + 勺+ l ，( 0 + 勺+ 1 ) ，( 0 ) 0 一0 “，( 1 ：，一吩+ 1 ) ，( 0 ) 】= ，其他情形 ( 3 ) 若j n 1 ，令j j + 1 ；转( 2 ) ；否则，转( 4 ) ( 4 ) 若厂( e ) 且毛5 以，那么蜀 ( 5 ) 如果02 且嘭 如 粕为非负数。 = t s t + s 3 | d ， d b 索引定义如下： 强2 玄酗 ( 3 1 0 ) r 5 恶j 一- r ，t 其中，d b n c 为簇c 。最大相似性的平均值，i - 1 ，i l c 。观的值越小表示当 前的聚类结果越好。 文献【5 6 】提出了基于m s t ，r