（系统分析与集成专业论文）数据挖掘中聚类中心问题的光滑化和填充函数方法.pdf

摘要 聚类中心问题是数据挖掘中一类重要问题，它可以定义为在 整个空间中的无约束全局最优化问题由于这类问题在信息获得， 文件获取及图象分块等生产和生活中有着十分广泛的应用，因此 研究聚类中心问题的算法具有重要的现实意义本文所讨论的聚 类中心问题可以描述如下； ( p ) 蛐，x l i ：x q ) = 去薹。磐一妒“酽 s t z = ( z 1 ，z 。) “。9 这里，z ，一是g 个要求的聚类中心，m 是数据个数，a i r n 是数据库中的第i 个数据 由于目标函数，( z ) 是非凸非光滑函数，所以问题( j ) ) 是非光 滑全局优化问题，设计求解( _ 7 ) ) 的全局最优解的算法具有极大的 挑战性本文根据问题( p ) 的结构特点，提出了先利用光滑化方法 将f ( x ) 用光滑函数逼近，然后对光滑化问题利用填充函数搜索其 全局最优点的方法我们对不同的数据库进行了数值试验，数值 结果表明，本文提出的算法对求解问题( p ) 是可行和有效的 本文总共分为四章，第一章简单地介绍了数据挖掘及聚类的 概念，以及聚类中心问题的模型第二章简单介绍了求解聚类中 心问题的现有算法：分层聚类算法，分块聚类算法，k 最临近算 法，进化算法以及模拟退火法等等第三章是本文的主要结果， 我们提出了一种新的光滑化和填充函数方法求解聚类中心问题， 并给出了数值试验结果，第四章总结了本文的主要结果并对未来 的研究进行了展望 关键词：数据挖掘，聚类中心，全局优化，光滑化函数，逐步求 中心法，填充函数法 a b s t r a c t c l u s t e r i n gc e n t e rp r o b l e mi sa ni m p o r t a n tc l a s so fd a t am i n i n gp r o g r a m m i n g p r o b l e m sw h i c hc a r lb ed e f i n e da st h em i n i m i z a t i o no fa nu n c o n s t r a i n t e dg l o b a l f u n c t i o n d u et oi t sw i d ea p p l i c a t i o n si ni n f o r m a t i o nr e t r i e v a l ，f i l ee x t r a c t i n g ， o b j e c ta n dc h a r a c t e rr e c o g n i t i o na n di m a g es e g m e n t a t i o n ，i ti so fg r e a ti n t e r e s t t os t u d yc l u s t e r i n gc e n t e rp r o b l e m s a c l u s t e r i n gc e n t e rp r o b l e mc a nb ee x p r e s s e d a sf o l l o w s ： ( = ) ) m i nm 1 = 去耋。璺划x s - - a i l q 旷 7 n ，。，s = ， s t z = ( z 1 ，z 9 ) r ”。g w h e r ez 1 ，x qa r en d i m e n s i o n a lv a r i a b l er e p r e s e n t i n gt h ec e n t e r so ft h eqe l u s t e r s ，mi st h en u m b e ro fd a t a a 。r “i st h ei - t hp o i n ti nd a t a b a s e s i n c et h eo b j e c t i v ef u n c t i o n ( x ) i sn o n c o n v e xa n dn o n s m o o t h ，t h ep r o b 1 e m ( p ) i san o n s m o o t hg l o b a lo p t i m i z a t i o np r o b l e mi nt h i st h e s i s ，w ep r o p o s ea s m o o t h i n ga n df i l l e df u n c t i o nm e t h o df o r ( p ) b ye x p l o i t i n gt h es p e c i a ls t r u c t u r e o ft h ep r o b l e m ，w ep r o p o s eas m o o t l d n ga n do ft h ep r o b l e m u s i n gt h es m o o t h - i n gf u n c t i o n ，w ea p p r o x i m a t et h en o n s m o o t hn o n c o n v e xo b j e c t i v ef u n c t i o nb ya s m o o t hf u n c t i o n f i l l e df u n c t i o nm e t h o di st h e na d o p t e dt os e a r c hf o rag l o b e lo p t i m a ls o l u t i o no ft h ea p p r o x i m a t i o np r o b l e mn u m e r i c a 2e x p e r i m e n t so n d i f f e r e n td a t a b a s ea r er e p o r t e df o rt h ep r o p o s e dm e t h o d t h et h e s i si so r g a n i z e da sf o l l o w s i nc h a p t e r1 ，w eg i v es o m eb r i e fi n t r o - d u c t i o no fd a t am i n i n ga n dc l u s t e r i n gc e n t e rp r o b l e m s o m eg e n e r a lm e t h o d s a r ed i s c u s s e da n dr e c e n tr e s e a r c hp r o g r e s so nc l u s t e r i n gc e n t e rp r o b l e m si sb r i e f l y i n t r o d u c e d i nc h a p t e r2w ed i s c u s ss o n l eo ft h ee x i s t i n gm e t h o d sf o rs o l v i n g t h ec l u s t e r i n gc e n t e rp r o b l e m si n c l u d i n gb o t hl o c a la n dt h eg l o b a lo p t i n f i z a t i o n m e t h o d sb a s e do nc u t t i n ga n g e lm e t h e o da n dd i s c r e t eg r a d i e n t an e wc o n v e r g e n t s m o o t h i n ga n df i l l e df u n c t i o nm e t h o di sp r e s e n t e di nc h a p t e r3f o rs o l v i n gt h e n o r * s m o o t hc l u s t e r i n gc e n t e rp r o b l e m s n u m e r i c a lr e s u l t so ns e v e r a ld a t a b a s e s a r ep r e s e n t e d f i n a l l y , w es u m m a r i z et h em a i nr e s u l t so ft h et h e s i si nc h a p t e r 4a n ds u g g e s ts o m ef u t u r er e s e a r c hd i r e c t i o n s k e yw o r d s ：d a t am i n i n g jc l u s t e rc e n t e r ，g l o b a lo p t i m i z a t i o n ) s m o o t h i n g f u n c t i o n ，s t e p b y - s t e pm e t h o d ，f i l l e df u n c t i o nm e t h o d 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作除了 文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写 过的研究成果参与同一工作的其他同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意 签名：一* - q 一一日期：一卫彩- 多趔 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有 权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布 论文的全部或部分内容 ( 保密的论文在解密后应遵守此规定) 豁嘲新硌砑l 矗啉迎纵l 毕 第一章前言 1 1 数据挖掘与聚类 随着数据库技术的飞速发展以及人们获取数据手段的多样化，人类所拥有的数 据急剧增加，可是目前用于对这些数据进行分析处理的工具却很少数据库系统所 能做到的只是对数据库中已有的数据进行存取和简单操作，人们通过这些数据所获 得的信息量仅仅是整个数据所包含的信息量的很少一部分，隐藏在这些数据之后的 更重要的信息是关于这些数据的整体特征的描述及对其发展趋势的预测，这些信息 在决策制定的过程中具有重要的参考价值 例如，股票经纪人需要从日积月累的大量股票行情变化的历史记录中发现其变 化规律，以供预测未来趋势；超级市场的经理人员希望能够从过去几年的销售记录 中分析出顾客的消费习惯和行为，以便及时变换营销策略；地质学家想通过分析地 球资源卫星发回的大量数据和照片来发现有开采价值的矿物资源等有一个很普 通却很能说明数据挖掘如何产生效益的例子：美国加州某个超级连锁店通过数据挖 掘，从记录每天销售信息和顾客基本情况的数据库中发现，在下班后前来购买婴儿 尿布的顾客多数是男性，而且往往也同时购买啤酒于是这个连锁店的经理当机立 断，重新布置了货架，把啤酒商品布置在婴儿尿布货架附近，并在二者之间放上土 豆之类的佐酒食品，同时把男士们需要的日常生活用品也就近布置这样一来，上 述几种商品的销量大增通过上面的例子可以看出，数据挖掘能为决策者提供重要 的、极有价值的信息或知识，从而产生不可估量的效益 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的 数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的 过程数据挖掘的应用领域非常宽广，从农业生产的预测到基因分类，从化学分子 结构的识别到n b a 教练临场更换队员，从信用卡欺诈到税务稽查，数据挖掘技术 对未来社会的各个领域将起到越来越主要的作用数据挖掘的主要方法可以分为 下面五大类： ( 1 ) 预测模型( p r e d i c t i v em o d e l l i n g ) ：目的是通过预测数据库中的某些数据得到 另外的数据 ( 2 ) 聚类( c l u s t e r i n g ) ：将数据组成一些子集，相对其他子集合同一子集中的数 据尽可能相似，而不同子集中的数据尽可能不相似 ( 3 ) 可靠性模型( d e p e n d e n c ym o d e l l i n g ) ：建立产生数据过程的联合概率密度函 2 数模型 ( 4 ) 数据总结( d a t as u m m a r i z a t i o n ) ：发现部分数据有趣的概要 ( 5 ) 异常和偏差检测( c h a n g ea n dd e v i a t i o nd e t e c t i o n ) ：说明数据记录的系列信 息。 本文对上述第二类方法：聚类方法，进行研究聚类是数据挖掘中的一种常用 方法聚类是一种无指导的学习，在基于相似性的基础上聚类分析将模式集合组织 成聚类聚类与分类是不同的，聚类对数据几乎没有可获得的优先信息，需要解决 的问题是将已给定的若干无标记的模式聚集起来使之成为有意义的聚类；而分类是 预先给定了若干已标记的模式，再对新模式，没有标记的模式进行标记聚类有硬 聚类( h a r dc l u s t e r i n g ) 与软聚类( f u z z yc l u s t e r i n g ) 之分硬聚类是指每一个数据都只 能属于一个聚类，而模糊聚类中每一个数据在每一个聚类中以一个可变的隶属度存 在聚类有广泛的应用在商业上，聚类可以帮助市场分析人员从消费者数据库中 区分出不同的消费群体来，并且概括出每一类消费者的消费模式或者说习惯；在生 物学中，它可以被用来辅助研究动、植物的分类，可以用来分类具有相似功能的基 因，还可以用来发现人群中的一些潜在的结构等；聚类还可以用来从地理数据库中 识别出具有相似土地用途的区域；可以从保险公司的数据库中发现汽车保险中具有 较高索赔概率的群体；还可以从一个城市的房地产信息数据中，根据房型、房价及 地理位置分成不同的类；还可以用来从万维网上分类不同类型的文档等等 下面是本文用到的一些记号和概念： 模式( 或特征向量，观察对象，数据) z 是用于聚类算法中的单个数据项它通常 是一个n 维向量：z = ( z 1 ，z 。) ； 模式z 中的单个分量x i ( i = 1 ，n ) 叫做特征； n 是模式空间维数； 距离测量是用来确定特征空间上模式间的相似性的度量； j = 1 ，：n ) ： 如果z ，y 冗“，则。2y 营y 。对所有的i j ； 如果z ，y 口则z y 营 y 。对所有的i j ； r 旱：= z = ( z 1 ，z n ) r “：x i 0v i ， ； 聚类算法主要有三种不同的类型： ( 1 ) 划分聚类：试图找到一个最优划分以把数据分成指定数量聚类的方法 ( 2 ) 层次聚类：试图发现聚类结构的层次方法 3 ( 3 ) 基于混合模型的概率聚类：对潜在聚类建模的基于概率模型方法 聚类任务通常包括下面的步骤： ( 1 ) 数据表示( 选择性的包括特征选择和提取( f c a t u r es e l e c t i o f fo re x t r a c t i o n ) ) ( 2 ) 最恰当的相似性的度量 ( 3 ) 数据聚类 ( 4 ) 聚类描述 ( 5 ) 评估 数据表示涉及数据集的大小、类中聚类的个数、可获得数据的个数以及可获得 特征( f e a t u r e ) 的个数、类型和数值范围对于实践者来说这些信息有些是不可控 的特征选择是一个识别用于聚类的原始特征中最有效特征子集的过程特征提取 是通过使用输入特征的一种或更多种变化产生新的显著特征这两种方法都可以用 来获得聚类中使用的最恰当的特征集 数据点之间的相似性通常是通过定义在特征空间的对点间的距离来度量，同一 聚类中点之间的距离尽可能的近，而不同聚类间点的距离尽可能的远我们这里 关注的是连续特征的模式间的距离度量不同的组织使用不同的距离测量( 【4 3 9 3 0 ) 对连续特征最常用的度量就是欧氏距离： d d 2 ( x t ，x j ) = ( ( z 。，k x j ，r ) 2 ) k 慨一z j l l 2 k = 】 它是m i n k o w s k i 度量的一种特殊情况( p = 2 ) ： 旦， d p ( z i ，吻) = ( ( 孔，k x j ，k ) 9 ) i = 慨一忆 k = l 欧氏距离适用于聚类为紧的独立的数据集( 5 1 1 ) 欧氏距离具有直观吸引人的特点， 它经常被用于二维或三维空间对象相似性的估计m i n k o w s k i 度量直接使用的缺点 就是有大规模特征占主导地位的趋势特征间的线性关联也会歪曲距离度量；这种 歪曲可以通过对数据漂白变换或应用m a h a l a n o b i s 距离 d m ( x i ，x j ) = ( 孔一) 。( 甄一q ) t 得到修正这里，模式，是行向量，是模式的样本方差矩阵 数据聚类能以多种方法实现输出聚类可能是硬聚类也可能是模糊聚类层次 聚类算法产生依据某个标准融合或切分基于相似性的聚类的嵌套划分序列划分 4 聚类算法识别优化( 通常是局部) 聚类准则的划分其他的聚类操作方法包括概率 ( 24 ) 和图论( 6 7 ) 聚类法 聚类描述是获取简单的紧凑的聚类表示的过程这里：简单性或是从自动分析 的前景考虑( 这样机器能够进一步进行有效处理) ，或是以人为中心( 这样得到的表 示易于理解且直观上吸引人) 在聚类的背景下，典型的聚类表示是每个聚类的紧凑 描述，通常用例如中心( c e n t e r ) 这样的聚类的典型代理模式所有的聚类算法都将 产生聚类，无论数据中是否包含有聚类如果数据中包含聚类，总有一些聚类算法 比其他算法得到更好的聚类那么如何评估聚类算法结果，一个聚类结果的好与不 好该怎样判断呢? 聚类结果的评估有几个方面一个实际上是数据领域而不是聚类 算法本身的评估不包含聚类的数据集不应该通过聚类算法处理相反，聚类有效 性( c l u s t e r i n gv a l i d i t y ) 分析是对聚类处理结果的评估通常这种分析使用一个具体 的优化标准；然而，这个标准往往是主观上达到有效性评估是客观的，且决定结 果是否有意义一个聚类结构是有效的如果它在偶然发生或人工制约聚类算法的条 件下不能合理的获得 1 - 2一些常用的聚类方法 1 2 1 划分聚类算法 划分聚类算法得到的是单个的数据划分而不是数据的结构，列如由层次方法得 到的树状图划分方法在大型数据库上非常有优势完成划分算法应用的一个问题 是期望的输出聚类数目的选择划分方法通常是通过局部( 定义在某一模式子集上) 或全局最优化( 定义在所有模式上) 评估函数产生聚类实际上，算法以不同的初始 状态运行多次，从每次的输出聚类中挑选最好的配置本文考虑的聚类模型即是划 分模型 1 2 1 1 平方误差算法 划分聚类算法中最直观的和常用的评估函数就是平方误差估计，它适用于独立 的紧聚类模式集4 ( 包含k 个聚类) 的聚类g 的平方误差是： k n e 2 ( 4 ：9 ) = i i z p 一勺1 1 2 j = l i = 1 这里z 是属于j 地聚类的i 讹模式，勺是j 砘聚类的中，l - 5 一均值算法( 5 0 】) 是应用平方误差估计的最简单和常用的算法它以任意的 初始划分开始，根据模式与聚类中心的相似性不断重新分配模式直到评估收敛( 也 即，不再有模式从一个聚类重新分配到另一聚类，或者在一定次数迭代后平方误差 不再显著下降) k 一均值算法因为它的易实现性及它的复杂性仅为0 ( n ) ( 这里n 是模 式个数) 而广受欢迎此算法的一个主要问题是对初始划分的选择敏感，且如果初 始划分选择不恰当评估函数可能收敛到一局部最小值 算法1 2 1 ( 平方误差聚类算法) 第一步：选择固定聚类个数和聚类中心的初始划分 第二步：将模式分配给离它最近的聚类中心，且计算聚类新的中心做为聚类中心 重复这个过程直到收敛，也即直到聚类成员稳定 第三步：基于一些启发式信息融合或分裂聚类 算法1 , 2 2 ( k 均值聚类算法) 第一步：选择任意k 个模式为初始个聚类的中心 第二步：根据模式与中心的最短距离将余下的模式分配给个聚类中离它最近的 那个聚类 第三步：用当前聚类的成员重新计算聚类中心 第四步：若当前不收敛，返回第二步典型的收敛准则是：不再有模式重新分配给 新的聚类中心，或者平方误差达到最小下降 k 一均值算法的几种变形可以参见| 4 一些变形通过选择一个好的初始划分使 得算法更可能找到全局最小值一些变形允许切分或融合产生的聚类典型地，当 聚类的偏差高于预先设定的阔值则它应该被切分，而当两个聚类中心的距离低于预 先设定的阈值则它们应该被融合假定指定了恰当的阈值，应用这种变形，从任意 的初始划分开始算法可能获得最优的划分另一些k 均值算法的变形是完全选择 一个不同的评估函数d i d a y 2 9 】和s y m o n 6 5 提出了动态聚类算法，他们通过系 统地阐述最大似然估计框架中的聚类问题描述动态聚类算法 1 2 2 层次聚类算法 层次聚类方法是逐步地融合点或切分聚类根据这一思想我们可以把分层方法 划分成两类：凝聚( a g g l o m e r a t i v e ) 和分裂( d i v i s i v e ) 凝聚算法是以聚类间的距离尺度 为基础的对于给定的初始聚类，凝聚方法是把最临近的聚类融合起来，重复这个 过程，每次都把两个最临近的聚类融合，直到仅有一个包括所有数据的点的聚类 分裂方法从一个由所有数据点组成的聚类起步，然后把这个聚类分割成多个部分， 6 再对分出的部分进行进一步的分割，重复这个过程直到满足需要为止一般来说， 分裂方法的运算量比凝聚方法更大，而且应用不如后者广泛 大部分的层次聚类算法是单链接( s i n 出l i n k ) ，完全链接( c o m p l e t el i n k ) 以及最 小偏差( 1 e a s td e v i a t i o n ) 的变形其中，单链接与完全链接算法是最普遍的这两个 算法的不同之处在于它们刻画一对聚类问相似性的方法不同在单链接算法中，两 个聚类间的距离定义为两个最临近点( 每个聚类各取一点) 间的距离而在完全连接 算法中，两个聚类间的距离定义为两个最远点( 两个点分别来自两个聚类) 间的距 离无论哪种情况，根据最小距离准则将两个最近的聚类融合成一个更大的聚类 完全链接算法产生紧凑球形聚类( 【7 ) 相反单链接算法由于受链条影响( 5 5 ) ，可能 产生散乱的、细长聚类单链接算法有一个显著特征，就是如果两个聚类是等距离 的，那么先融合哪一对都无所谓无论融合的顺序如何，最终的结果都相同 层次算法与划分算法是聚类的两类主要算法一方面，层次聚类算法比划分聚 类算法更通用例如，单链接聚类算法适用包含非等方性聚类的数据集( 包括完全 分离的，链状的以及同中心的聚类) 而象k 一均值算法这样典型的划分算法仅适用 包含等方性聚类的数据集( 5 5 ) 另一方面，划分算法的时空复杂性明显低于层次算 法的时空复杂性利用两类算法的优良特性发展混合算法是可能的( 【5 4 】) 1 2 3 最近邻聚类算法 既然相似性在一个聚类的直观概念中起关键作用，最临近距离则可看作是聚类 过程的基础最近邻法就是计算模式与已知聚类的距离，看该模式与哪一类距离更 近，就把该模式归于哪一类 l u 和f u 在文 4 9 】提出一个迭代过程，它分配每一 无标注模式到它最临近带标注模式所属的聚类，假定到最临近邻居的距离低于临界 值重复这个过程直到所有模式被标记或没有另外的标记出现 1 2 4 模糊聚类 传统的聚类方法产生划分，每一划分中，每个模式属于且仅属于一个聚类因 此，硬聚类中的聚类是互不相交的模糊聚类应用隶属函数( 【6 6 】) 将这一概念延展 到每一模式以一定的隶属度隶属每一聚类这样的算法得到的结果是聚类而不是划 分 算法1 2 3 ( 模糊聚类算法) 第一步：通过选择n k 的关系矩阵u ，选择将n 个目标划分到k 个聚类的一个初 始模糊划分矩阵中元素u 。，表示目标x ；隶属于聚类c ，的程度( 也即隶属度) 7 通常，。， 0 ，1 】 第二步；利用矩阵u 找到模糊评估函数值，也即，一个带权的平方误差评估函数， 联合相应的划分一个可能的模糊评估函数是： n e 2 ( a ，u ) = “灯l i 甄一c f | | 2 ， i = 1z = 1 这里，c l = 警1u i i x i 是第2 个模糊聚类中心重新分配数据点到聚类来降低评 估函数值，且重新计算u 第三步：重复第二步直到u 中的元素不再显著变化 在模糊聚类中，每一个聚类都是所有数据点的模糊集隶属度越大表示数据点分配 到该聚类的可能性越高一个硬聚类可以通过界定模糊划分的隶属度得到 1 9 6 9 年模糊集理论被r u s p i n i 6 0 】初始应用于聚类最常用的模糊聚类算法是 模糊c - 均值算法( f c m ) 尽管在避免局部优化上f c m 优于k 一均值算法，f c m 依然 收敛于平方误差评估的局部最小值在模糊聚类中，隶属函数的设计是最重要的 借助一族目标函数，b e z d e k 【2 2 】给出广义的f c m 算法 1 2 5 人工神经网络聚类 人工神经网络( a n n s ) ( 3 6 ) 是由生物神经网络引出的在过去三十年a n n s 被 广泛地应用于分类和聚类( 6 2 ) 神经网络系统由一系列类似于人脑神经元一样的 处理单元组成，我们称之为节点( n o d e ) 一个节点将其他节点对它的信息总输入作 用后( 通过作用函数) 的输出，相当于该节点所代表的超平面将n 维空间( n 个节点 构成的空间) 中超平面上部结点转换成1 类，超平面及其下部结点转换成0 类也 即，一个节点相当于空间中一个超平面一个超平面将空间划分为上下两部分，通 过作用函数将空间两部分的所有结点( 含超平面结点) ，分别变换为取二进制( 0 或1 ) 的两个点多个节点相当于空间中多个超平面将空间划分成若干个区，同一个区的 所有结点变换成同一个多位二进制的点这些节点通过网络彼此互连，因此如果有 数据输入，它们便可以进行确定数据模式的工作竞争神经网络( 【4 0 】) 经常被用于 聚类输入数据在竞争学习中，相似模式被网络聚集在一起并用单个单位( 神经元) 表示这种聚集是根据数据联系自动聚集的 典型的神经网络模型有：反向传播模型( b p 模型) ，反馈式h o p f i e l d 模型神 经网络用于聚类的著名例子包括：l e a r n i n gv e c t o rq u a n t i z a t i o n ( l v q ) ，s e l f - o r g a n i z i n g m a p ( s o m ) ( 【4 4 】) 以及适应回馈理论模型( 2 6 ) 其中s o m 给出了多维数据集的一 个直观吸引人的二维图然而，如果初始权选择不恰当s o m 得到次优化划分更 8 有，它的收敛性由不同参数控制，如学习速度，学习中得到的节点的邻域特别的 输入模式在不同的迭代中可能导致取消不同的输出模式，这就产生了学习系统的稳 定性问题一个系统被认为是稳定的，如果在学习迭代的有限次后没有模式改变它 的类别这个问题与可塑性( 是指算法适应新数据的能力) 问题密切相关对稳定性 来说，学习速度应该随着迭代过程逐渐趋于零，而这影响可塑性a n n s 的结构是 非常简单的单层结构模式在输入时被表示且与输出节点相关输入节点与输出节 点间的权迭代变化( 这就叫做学习) 直到终止准则满足所有a n n s 都固定输出节点 数，这样能限制所产生的聚类数目 1 2 6 进化方法 进化方法起源于自然演变，它利用进化算子和种群获得数据的全局最优划分 进化方法将问题可能的解按某种形式进行编码，编码后的解称为染色体最常用的 进化算子是：选择( s e l e c t i o n ) ，交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 每个算子都是将一 个或更多个输入染色体转化成一个或更多个输出染色体适应函数对染色体的估计 决定了该染色体在下一代的存活性下面我们给出进化算法应用于聚类的高水平描 述 算法1 2 4 ( 进化算法) 第一步：选择任一种群这里每个解对应数据的一个有效b 划分假定每个个体 的适应值有代表性地，适应值与平方误差值成反比平方误差值小的个体适 应值大 第二步：利用进化算子( 选择，交叉及变异) 产生下一个种群估计这些个体的适 应值 第三步：重复第二步直到某一终止条件满足 最著名的、在聚类中最常使用的进化算法是遗传算法( g a s ) ( 3 s 1 ) 在g a s 中个 体编码中有代表性的是二进制串在g a s 中，选择算子是从种群中选择生命力强的 染色体产生新种群的过程依据每个染色体的适应值大小，适应值越大，被选中的 概率就越大，其子孙在下一代产生的个数就越多选择操作是建立在群体中个体的 适应值评估基础上的选择算子又称复制、繁殖算子目前常用的选择算子有以下 几种 1 适应值比例法该方法是目前遗传算法中最常用的选择方法在该方法中， 各个个体的选择概率和其适应值成比例 2 最佳个体保存法该方法的思想是把群体中适应最高的个体不进行配对交叉 9 而直接复制到下一代 3 期望值方法计算群体中每个个体在下一代生存的期望数目 4 选择排序方法1 该方法是指在计算每个个体的适应值后，根据适应值大小顺 序对群体中个体顺序，然后把事先设计好的概率表按排序分配给个体，作为各自的 选择概率 5 比例排列法将比例法和排列法结合起来的比例排列法，即当群体中某个染 色体的适应值远远大于其他染色体的适应值或群体中每个染色体的适应值相似时， 按排列法进行后代选择，而在一般情况下采用比例法进行后代选择 交叉算子又称重组、配对算子当许多染色体相同或者后代的染色体与上一代 没有多大差别时，可通过染色体重组来产生新一代染色体染色体重组是分两个步 骤进行的，首先在新复制的群体中随机选取两个个体，然后，沿着这两个个体随机 地去一个位置，二者互换从该位置起的末尾部分 遗传算法的有效性主要来自选择和交叉操作，尤其是交叉，在遗传算法中起着 核心作用目前有如下几种基本交叉方法 1 一点交叉一点交叉又叫简单交叉具体操作是在个体串中随机设定一个交 叉点实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个 体 2 二点交叉二点交叉的操作与一点交叉类似，只是设置两个交叉点 3 多点交叉多点交叉是前述两种交叉的推广，有时又被称为广义交叉 4 一致交叉所谓一致交叉是指通过设定屏蔽字来决定新个体的基因继承两个 旧个体中哪个个体的对应基因 选择和交叉算子基本上完成了遗传算法的大部分搜索功能，而变异则增加了遗 传算法找到接近最优解的能力变异就是以很小的概率，随机地改变字符串某个位 置上的值遗传算法引入变异的目的有两个一是使遗传算法具有局部的随机搜索 能力当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部随 机搜索能力可以加速向最优解收敛二是使遗传算法维持群体多样性，以防止出现 未成熟收敛现象 1 2 7 搜索方法 搜索方法用来获得评估函数的最优值，它分为确定性与随机性搜索方法确定 性搜索方法通过穷举法保证一个最优划分另一方面，随机搜索方法合理地，快速地 产生一个近似最优划分，并且保证渐进收敛到最优划分在前面考虑到的方法中， 1 0 进化方法是随机的，而其他都是确定方法另一些应用于聚类的确定性方法包括分 支定界方法( 【4 5 ) 用来生成最优划分确定性退火方法( 【5 7 】) 也被用于聚类这种方 法在光滑粗糙平面上应用退火技术，但不能保证收敛到全局最优点：h o f i n a n n 和 b u h m a n n 3 7 1 考察了确定性退火方法在近似模式聚类上的应用，后来的工作将确定 性退火方法应用在结构分割 确定性方法是典型的贪婪下降方法，而随机方法允许解以非零概率在非局部最 优方向的扰动随机搜索方法可能是序列的，也可能是平行的模拟退火方法( s a ) ( 【4 2 ) 是一种序列随机搜索方法，它在聚类上的应用可参见 4 3 模拟退火算法得益 于材料的统计力学的研究成果统计力学表明材料中粒子的不同结构对应于粒子的 不同能量水平在高温条件下，粒子的能量较高，可以自由运动和重新排列在低 温下，粒子能量较低如果从高温开始，非常缓慢地降温( 这个过程被称作退火) ，粒 子就可以在每个温度下达到热平衡模拟退火过程被设计来避免或覆盖目标函数局 部最优值对应的解这个过程通过为下次迭代以某一概率接收新的解接收概率由 温度参数控制，温度从第一次迭代的初始值变化到最后迭代的最终值模拟退火聚 类算法任意选择数据的初始划分，初始和最终的温度值且计算平方误差根据平方 误差值带有或不带有依赖温度概率数据点被重新分配给聚类温度值迭代降低 模拟退火方法搜索到最优解的速度可能比较慢最优解要求温度随着迭代缓慢 下降 s e l i m 和a 1 s u l t a nf 6 1 研究了控制参数对算法行为的影响模拟退火法统计 保证搜索到全局最优解( 算法1 2 5 ( 模拟退火算法) 第一步：任意选择初始划分昂，计算平方误差值e p o 为控制参数选择初始和最终 温度值蜀和研 第二步：选择划分p 0 的邻划分p 1 且计算它的误差值e p l 如果e p l 大于e p o ，则以 依赖温度概率指派尸1 给局否则指派p 1 给p 0 固定迭代步骤重复这个过程 第三步：降低的值，也即，= c 如，c 是预定常数如果大于巧，则返回第 二步否则算法终止 t a b u 搜索( f 3 3 1 ) 也是一种启发式搜索方法为了能在搜索了较小的解空间之后 获得较优的解，t a b u 搜索算法有一个隐含的假定：一个解的邻域中往往存在性能 更好的解因此t a b u 搜索仅仅在一些解的邻域中进行为了避免搜索过程的重复， 从而能更快地搜索更大的解空间，该算法要求记录近期搜索过的解，记录这一搜索 过程的结构叫做t a b u 表用于解决聚类问题的t a b u 搜索方法可参见文 2 1 姐3聚类中心问题的模型 1 3 1 相关介绍 在聚类分析中，我们假定a 为船空间上的有限集，也即： a = a 1 ，n ”。 ，a 2 彤，i = 1 ，m 前面我们介绍了不同类型的聚类方法，如划分，覆盖和层次等等在本文中我们考 虑划分聚类 聚类分析的目标是将集合a 划分到给定的相交或不相交的子集，i ：1 ，k ， 且 k a = u a 。 t = 1 集合a 2 ，i = l ，k 叫作聚类 如果每个点都属于且仅属于一个聚类，聚类问题称为硬聚类与硬聚类不同的 是，在模糊聚类方法中聚类允许重叠在本文中我们考虑无约束硬聚类问题，也即， 我们假定 a 。n a = o ，v z ，j = 1 ，：i j 许多作者将聚类问题归纳成下面的最优化问题( 2 3 j 6 3 j ) ： m i n 妒( ，z ) ：磊1 k 一。幢 ( 1 叫 i = la e a s t f 工z = ( 一，) 础“， 这里恻1 2 是欧氏范数，= a 1 ，：以。) 是聚类集，是集合a 所有可能的k 一划 分，一是聚类a 2 ，i = 1 ，的中心除了问题( 1 31 ) 下面的问题也被考虑： m i n ，小：去圭忙z 叫i ( 1 t 3 2 ) 。= 1a e a i s t f ，1 z = ( z 1 ，z ) r “。 问题( 1 3 2 ) 依赖于范数的选择：不同的范数可能导致不同的聚类中心既然聚类是 个灵活概念，使用不同范数也是可以接受的 1 2 问题( 1 3 1 ) 的下面形式更适合于最优化方法的应用： mk m i n9 ( 叫) ：2 圭归_ 一| | 2 ( 133 ) s t z = ( x 1 ，：z 。) ，一r “，j = l ，k ， = l ，i = 1 ，m j = 1 = 0 1 ，i = 1 ，m ，j = 1 ， 这里k 是给定的聚类个数，m 是可获得的模式个数，一er ”是需求解的第j 个聚 类中心，是模式n 。与的相关权，它由下式给出： 1w i j = 1i ，a iea j 1w i j = 0i ，a i 仁朋v i = 1 ，m ，j = 1 ，k ， 这里u 是一个m k 矩阵问题( 1 33 ) 是一个混合优化问题，包含连续和整数变 量， 1 3 2 聚类优化模型 本小节我们介绍文【2 0 中的聚类方法该方法得到一个与( 1 33 ) 等价但计算相 对简单的非光滑非凸全局优化问题 我们考虑一个n 维空间r “及范数”m 我们假定”| | = ”p 1 ，这里 1 1 2 1 1 ，= ( 蚓) ；，1 p l ，a 是非凸非光滑函数可以证明该函数 有许多浅的局部最小值该优化模型即是本文讨论的聚类中心模型 1 3 3 大规模聚类的优化模型 显然最优化问题1 3 4 的变量个数是k n 如果聚类个数k 及特征个数1 3 相当 大，则该问题就是个大规模全局最优化问题大规模数据集通常拥有大量数据点， 且这些数据点存在于一有界集中因此该数据集的许多数据点彼此靠近设ac r n 是一有限集假定点be 形的某一小邻域包含a 中m 6 个点我们可以用b 逼近该 邻域的每个点并用m 6m i n 。l 一6 1 1 2 代替上述聚类函数的相应部分 更具体地，对一给定a 和一给定准则考虑集合b 形，使得对任意的n a 存在b b 且满足j | 。一6 | | e a 的子集的一个聚集( a b ) b b 是a 的一个不相交覆 盖如果 | | 血一6 | | 0 和q = q o 1 作为初始聚类个数选取一初始点 一= z 2 ，z ! ，z p ，z 帮) 1 t “，解问题( p ) 设x “冗“q o 是问题( p ) 的一个解，“是相应的目标函数值令k = q o s t e pj ( 计算下一个中心) 任选一初始点x o 咿解下面的最小化问题： 删r a i n 。f k ( z ) = m i n l l z h n 2 n 巾船一。i z 一矿n ( 2 1 1 ) 。 i = 1 s t e p2 ( 中心的改进)设砂+ 1 ，+ 是问题( 2 11 ) 的一个解取x 2 + 1 ，o r “【+ ”， 扩+ 1 ，o = ( z “，x h ，i 8 十1 ，4 ) 作为新的初始点解下面最小化问题( q = + 1 ) 1 5 22o 一一 n 蚪血。产 。嚣 = q 甸 时 弋 r 焘、 蜒 n h 呲 1 6 s t e p3 ( 终止准则) 设z + 1 ，+ r “。( + 1 ) 是问题( 2 1 2 ) 的解，c + 1 一+ 是相应的目标 函数值若 生竺 1 时这类问题的目标函数非凸非光滑且具有多个局部最优点关于这类问题求解的相 关文献并不多见，下节主要介绍两种非光滑优化方法 2 2 局部优化方法 我们用来聚类的优化问题的目标函数具有下面形式 这里函数z 一也( z 1 ，a ) 对每个i 和a 是凸的 性质2 2 1 ( 2 2 3 ) 式中定义的函数f k 是d c 实际上，我们可以用下面的形式表示最： j k ( z ) = 1 ( ( z ) 一f 2 ( x ) ) f l ( x ) = 忱( 矿，n ) ， a e a t = l z = ( x 1 ，z ) ， ，2 ( z ) = 吼m a x 。叻( 一，n ) a c a j 2 ，1 ( z ) ，f 2 ( x ) 均是凸函数， 推论2 2 1 函数r 伪可微，局部l i p s c h i t z 和半光滑( 5 2 ) 在本节中我们只考虑r 简单形式的函