（概率论与数理统计专业论文）基于混合模型聚类的方法.pdf

， | ， 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究工作所取得的研究成果。据我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得东北师范大学或其他教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示谢意 学位论文作者签名衅 日期： 学位论文版权使用授权书 目 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东北师范大学有权保留 并向国家有关部门或机构送交学位论文的复印件和磁盘，允许论文被查阅和借阅本人授权东北师范大学 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保存、 汇编学位论文 f 保密的学位论文在解密后适用本授权书) 学位论文作者签名；龌指导教师签名：貉 日 学位论文作者毕业后去向： 工作单位： 通讯地址：越b 趣玷唾喳整套型叁凌l 才 徘蝴撇浮燃 电话：必幽印 邮编：边妞 染 月 ， 、 - 1 ， 俩 “ 磕 摘要 聚类分析是多元统计学的一个分支基于混合模型聚类算法是众多聚类算法的一种。本文 全面探讨基于混合模型聚类算法的一般理论框架和聚类方法，给出一种基于独立的g a u s s i a n 和 b e t a 分布数据的有限维联合模型的耨的聚类算法b g m m n 。通过模拟比较了聚类算法b g m m n 与聚类算法b g m m s ，b g m m a 和b g x , l m h 的整体预测聚类精度e - s c o r e ，及对聚类数目估计 的准确率，说明b g m m n 聚类算法比聚类算法b g m m s ，b g m m a ，b g m m h 更具有优势， 而且b g m m n 聚类算法特别适用于g a u s s i a n 分布数据容易聚类的情形 关键词：聚类；混合模型；模型选择；e m 算法 | o a b s t r a c t t h ec l u s t e ra n a l y s i si sab r a n c ho fm u l t i v a r i a t es t a t i s t i c s m i x e dm o d e l b a s e dc l u s t e ra l g o r i t h m i so n eo ft h en u m e r o u sc l u s t e ra l g o r i t h m s i nt h i sp a p e r ，ic o m p r e h e n s i v e l yd i s c u s st h eg e n e r a lt h e - o r yf r a m eo fm i x e dm o d e l b a s e dc l u s t e ra l g o r i t h m ，a n dc l u s t e ra l g o r i t h m s ，id e v e l o p ean e wc l u s t e r a l g o r i t h m ，j o i n tf i n i t em i x e dm i x t u r em o d e lf o rc l u s t e r i n gf r o mi n d e p e n d e n tg a u s s i a na n db e t ad i s - t r i b u t c dd a t a ，w h i c hc a l l e db g m m n b yt h es i m u l a t i o n ，g i v i n gt h ec o m p a r i s o nb e t w e e nt h ec l u s t e r a l g o r i t h mo fb g m m n ，b g m m s b g m m a ，b g m m h ，o nt h ec l u s t e r i n ga c c u r a c ya n dt h ec o r r e c tn u m b e r o fc l u s t e r s t h u s , p o i n to u tt h a tt h eb g m m nc l u s t e ra l g o r i t h mi sb e t t e rt h a nt h eo t h e rt h r e ec l u s t e r a l g o r i t h m s ，a n dt h eb g m m nc l u s t e ra l g o r i t h mi sb e t t e rf o ru s e i n g ，w h e ng a u s s i a nd i s t r i b u t e dd a t a s 8 f i ee a s yt oc l u s t e r k e y w o r d s ：c l u s t e r i n g ；m l x e dm o d e l ；m o d e ls e l e c t i o n ；e ma l g o r i t h m i i - 自 3 2b g m m n 算法1 0 3 3 模型选择1 1 3 4 算法优良的评价标准1 2 53 5 模拟和结论1 2 参考文献2 0 致谢2 3 i i i n m 1 3 3 5 5 5 6 8 9 ， 东北师范大学硕士学位论文 引言 聚类分析是多元统计学的一个分支，是研究对观测样本或指标进行分类的统计方法聚类 分析的主要目的是在缺少先验知识或没有先验知识的条件下，将新来的观测样本或指标分到 已知的类，或将一个大的杂乱的数据集分成多个更小更相似的类聚类的原则是使分到同一类 问的观测样本或指标尽可能相似，不同类间的观测样本或指标尽可能分开聚类分析方法的提 出具有重要的意义以分析数据为例，聚类分析极大地简化了对大量数据进行分析研究的工作 量，因为对大数据集聚类后，大数据集分成多个彼此差异较大，但内部性质相近的小数据集， 这样对大数据集的疏密程度就比较直观，对大数据集就更容易进行处理。聚类分析发展的历史 悠久，在现实生活中应用极其广泛 例如在商业上，聚类分析是戈l j 分消费市场的有效工具，也用于寻找新的潜在商机，研究消 费者的喜好等；环境上，聚类分析用于归类并预测环境污染成分；医学上，聚类分析用于分析 对病因起主要作用的蛋白质合成路径，归类不同的病例，获取对病菌间的相似性或差异性的认 识；生物上，聚类分析广泛应用于对动植物进行分类，获取对不同物种闻基因相似性或差异性 的固有认识，发现新的基因及其新功能等；聚类分析也应用于修复被损坏的照片及文件档案等 等 近年来，各行各业的数据呈指数形式增长，而且这些数据具有维数大，内部关需复杂，来 源广泛等特点，这使得聚类分析成为数据挖掘领域很重要的研究课题之一如何处理这些数 据，从中获得我们关心的信息，困扰了各行各业的人不无争议，不同的数据来源从不同的角 度提供了不同的信息因此，如何把所有不同来源的数据整合在一起，充分利用数据提供的各 种信息；如何给出将要聚类数据集的最优聚类数目，使聚类预测精度更高，成为聚类分析研究 的一个难点： 聚类分析从起源至今，针对不同的研究对象，不同的聚类目的已经发展了各种不同的聚类 方法，对此在第一章中对各种聚类算法给出介绍，并指出算法的优缺点及算法适合使用的范 围 本文主要是综述前人的工作结果，介绍聚类方法的发展状况，着重讨论基于混合模型聚类 算法，在受x i a of e n gd a i ，t i m o ，o l l i ，h a r r i ( 2 0 0 9 ) 提出的文献【1 j 的启发下，给出一种新的 基于有限维联合混合模型的聚类算法b g m m n ，并通过模拟，对聚类算法b g m m n 和文献【1 】 提出的3 种聚类算法b g m m s ，b g m m a 和b g m m h ，在聚类预测精度e - s c o r e 和聚类数目估 1 东= i 计的准确率上进行了比较，并给出相 混合模型b g m m 和g a u s s i a n 混合模 2 东北师范大学硕士学位论文 1 聚类算法简介 聚类算法按照不同的划分标准有多种分类方式依其对研究的观测样本或指标的先验知 识的有无，将聚类分为有监督聚类和无监督聚类。有监督聚类是指对当前所研究的观测样本或 指标，已知它们的类别及数目特征，只需将新来的未知类别的观测样本或指标分到已知的样本 或指标所在的类；无监督聚类是事先不知道研究的观测样本或指标分为凡类，更不知道将要分 类对象的结构特征，需要对观测样本或指标进行分析处理，从而确定分类数目，建立一种恰当 的分类方法，然后按照观测样本或指标的相似程度对它们给出合理的分类。依其对观测样本或 一指标的概率框架有无，聚类又可以分为基于判断的聚类和基于模型的聚类【2 】 实际问题中观测洋本或指标的来源非常广，特别是基因表达数据由于基因表达数据的维 数高，关系复杂，因此对聚类分析要求聚类结果直观，思路清晰。对此，研究者提出了许多聚 类的方法例如分层聚类 3 - 5 ，对于给定的观测样本或指标进行层次上的分解，可分为自底 向上的凝聚算法和自顶向下的分裂算法；分层聚类的方法虽然聚类结构图很明显，直观，但它 “ 不能自动给出聚类的最优数目；k m e a n s 聚类【倒，在将要分类的数据中任意选择k ( 数据集分 类数) 个对象作为初始聚类中心，计算每个数据与k 个聚类中心的距离，把距离最短的分在 一个类，重新计算有变化的聚类中心，重复上述过程，直到聚类中心不再发生变化+ k h l e a h s 聚类算法收敛速度快，适用于对大小、密度相近的凸分布的聚类，但不适用于分布形状比较 复杂的聚类，而且聚类结果特别依赖于初始中心k 的选择； k o h o m c n ( 1 9 9 0 ) 提出的自组织映 射( s o m ) 1 7 】，是一种将1 1 维模式空间各点输出到空间有少数点的映射此算法虽简单，但是 收敛速度太慢；d c m b c l e 和k a s t n c r ( 2 0 0 3 ) 给出f c m 模糊聚类算法【8 】，利用模糊数学中的隶 属概念对基因表达数据进行聚类。算法的缺点是很容易收敛到局部的极值，与真实值差距往往 ，很大；基于图论的聚类算法对分布形状复杂的数据有很大的优势，并且对孤立点的处理也较 好。s h a m i r ，s h a x a n 和c l i c k ( 2 0 0 0 ) 提出基于图论的c l i c k 聚类算法f 9 】；b e n d o r ，s h a m i r 和y a k h i n i ( 1 9 9 9 ) 提出基于图论的c a s t 聚类算法；还有一些基于最小生成树的聚类算法 i l l - - 1 6 等等。 虽然上述的分层聚类法，k m e a n s 法，s o m 法等非监督聚类方法聚类思想比较直观， 容易理解，有其优势，但这些方法有很大的弊端，它们不能对观测样本和指标自动给出最优的 聚类数目，对于观测噪音不能给出恰当的处理对解决这两个弊端，基于模型聚类【2 j 有很大 的优势对观测样本或指标的最优聚类数目的确定，可以转化为模型选择问题；对观测噪音的 处理，可以通过添加一个或多个对观测噪音为不同分布的成分 2 】【17 1 来处理。故而基于模型聚 3 东北师范大学硕士学位论文 类成为近年来聚类算法研究的主流 基于模型的聚类算法是以概率统计理论为基础的一种有效灵活的聚类算法，应用范围很 广，受到统计学界，生物界，医学界，计算机，金融领域等诸多领域的广泛关注根据要聚类的基因 表达数据的不同特点，已经发展了许多不同的聚类模型。在同一生物条件的假设下，对基于比较 长的基因临时表达数据，r a m o n i ，s c b a s t i a n i 和k o h a n e ( 2 0 0 2 ) 给出了自回归模型( c a g e d ) 1 1 8 ， s c h l i e p ，依据序列的相关关系给出动态数据的分析模型s c h o n h u t h 和s t e i l l l l o f f ( 2 0 0 3 ) 提出隐 藏马尔克夫模型，l u a ny 和l ih ( 2 0 0 3 ) 给出b 样条模型【2 0 等；对基于比较短的基因临 时表达数据，w a n g l ，r a m o n i 和s c b a s t i a n i ( 2 0 0 6 ) 建立了多项式混合模型 2 l 】，把时间的信 息并入设计阵，因此不要求观测数据是静止的。对模型参数给与恰当的先验，使得聚类结果在 时间的线性变换下是不变的基于多项式的b a y e s i a n 模型的算法提供了一个自动选择拥有最 大后验概率的聚类数目。此模型特别适用于有孤立点的数据。为了分析基因在不同的生物条件 下是否有不同的表示符号，并且即希望及时发现这些有不同表示符号的基因，又想在相同生物 条件下，把它们同其它基因聚类。l i n gw a n g ，m o n t y 和m a t t a n d ( 2 0 0 8 ) 在文献【2 1 的基础上 给出一种方法 2 2 】，此方法有2 个步骤，1 ) 在每一个实验条件下，利用基于多项式的b a y e s i a n 模型把基因聚类；2 ) 把1 ) 得到的所有类看成一个基因表达符号，再按上述方法聚类，若没有 g c p ，则得到最后结果，否则，把g c p 去掉，对其它数据按上述方法聚类。最后利用r a n d 统 计量估计结果和真实聚类间的相似性 但是随着实验设备的改进及更新，基因表达数据的形式越来越复杂，数目越来越庞大，关 系错综复杂，分布的形式差异越来越大于是，如何充分的利用基因表达数据所提供的各种信 息，给出更实用的聚类方法成为一个焦点 4 东北师范大学硕士学位论文 2 基于混合模型聚类 基于混合模型聚类可以解决一般非监督聚类的弊端，能确定聚类的数目及恰当的处理观 测噪音为了对基于混合模型聚类有更清楚的认识，在本章中主要介绍基于混合模型聚类在 2 1 节主要介绍聚类的混合模型，2 2 节介绍混合模型聚类的理论，2 3 节介绍混合模型聚类的 主要结果 2 1 聚类的混合模型 给定观测数据集x = x 1 ，x 2 ，拖，) 设 ( 蜀愀) 是数据向量五所在第k 个类的概 率密度函数，0 k 为第k 个类的分布的参数设观测数据集x 可分为g 个类，令砜为咒来自 第k 个类的权重，其中丌- ，霄2 ，j ，丌g 满足是1 “= 1 ，则模型的一般框架为 g f ( x i ) = 万k f k ( x i o k ) ， k = 1 假设x l ，托，托，x 。独立，秒= ( 口一，p g ) ，则观测数据的联合模型为 等式( 2 ) 的l o g - 似然函数为 ng l o g l ( o ) = z o g ( i z ；丌k ( 恐】) i = lk = l ( 3 ) 2 2 混合模型聚类的理论 一 对观测数据集x = 置x 2 ，x a ，) 建立一个有限维的混合模型，见等式( 2 ) ，对给定 数据集x ，等式( 3 ) 直接极大化很困难为此，引入数据集x 最有可能的分类标签向量集 h = 日1 ，凰，凰，巩 ，k 的分类标签记为皿= ( h m 6 协，九t g ) r ，若数据置来自第 k ( k = l 。2 ，- ，g ) 个类，则豇= 1 ；否则h i k = o 通常情况下假定凰，凰；凰，独立同分布， 以概率f f l ，7 f 2 ，7 r 3 ，7 r g ，( 是l7 r 知= 1 ) 来自一个多维分布则有 p h i k = 1 1 0 】= 饥， 5 如鼍“ g 眦。 l i 他 x 磁 x 八 东北师范大学硕士学位论文 g p 阢 皿，刎= 1 - i 帆( 置陬) p k 七= l 利用分类标签向量集h ，等式( 2 ) 的似然函数可以表示成 。l n ( o ) = f ( h i o ) f f x i h ，0 ) ， ( 4 ) 通过等式( 4 ) ，等式( 3 ) 可以写成 。 ng 一l o g l h ( 0 ) = i ( h i k = 1 ) t o g ( t r k f k ( x i o k ) ) ， ( 5 ) 其中i ( h 姥= 1 ) 为示性函数。把分类标签向量集h 看成缺失向量集，利用e m 算法估计等 式( 4 ) 中的参数0 ，使得似然函数最大化令参数0 的极大似然估计为每，x 来自第k 个类 的后验概率为死路，表达式为 吒七= 尸 h i k = 1 i x i 扫七，= 芝主塞蹁+ ， 根据后验概率瓦进行聚类，聚类准则如下：若龟= m a x k 知，其中k = 1 ，2 ，g ，则把 数据五分到第t 个类 由模型选择准则m c 2 4 ，b i c ：撕，a i c 3 t m ，i c l 1 7 等给出观测数据集x 的聚类数 目g 的最优选择 、 2 3 混合模型聚类的主要结果 s c o t t 和s y m o n s ( 1 9 7 1 ) 给出多元正态的概率模型! 矧，指出当协方差矩阵k = ( 已 知或未知) 两种情行下不同的聚类法，以及知= k ( 矗已知或未知) 的讨论b a n f i e l d 和 r a f t e r y ( 1 9 9 3 ) 讨论多元混合正态模型 2 8 】，提出对协方差矩阵重新参数化，把协方差矩阵表示为 = d k a k a k d 手，其中仇为协方差矩阵的特征向量组成的正交矩阵，a k = d i a g a l ，a 2 k ， ，o p 奄) ，且1 = a 拙a 2 k a p k 0 k 为七的第一特征值， a k ( r k 的特征值矩 阵) = a a 七对协方差矩阵重新参数化后聚类簇分布的定向性，体积，形状的特征分别由仇， k ，a 七三个参数决定。并且对不同参数进行变化给出的六种不同形式的聚类模型d e b a s h i s 和a r u l ( 2 0 0 1 ) 建立混合正态模型分析微列阵数据，讨论聚类结果的可靠性此篇文章中的 算法和用会凝聚的层次聚类法初始化，用e m 算法估计分布中的参数，用b i c 选择聚类的最优 数目。y u a n j i ，c h u n l c i w u ( 2 0 0 5 ) 1 7 建立b c t a 混合模型讨论基因表达水平的相关系数的变化 x i a of e n gd a i ，t i m oe r k k i l a ，o l l iy l i h a r j a h a r r il a h d e s m a k i ( 2 0 0 9 ) 1 建立独立的g a u s s i a n 与b e t a 6 7 东北师范大学硕士学位论文 3 b g m m i ，聚类算法 在文献【1 】的启发下，本篇论文提出了下述新的基于有限维联合混合模型的聚类算法b g m m n b g m m n 聚类算法大致表述如下：对来自g a u s s i a n 分布的数据用e m 算法【1 4 】给出 g a u s s i a n 分布的参数的估计，确定g a u s s i a n 分布并基于使g a u s s i a n 分布似然函数极大化的 原则，利用分类指标确定初始聚类；利用初始聚类，用矩法去估计初始类中每一类的b e t a 分 布的参数，从而确定b e t a 分布；把两种数据的分布整合起来，基于使整体似然函数最大化的 原则，利用分类指标给出最终的聚类用模型选择标准a i c 给出聚类数目的估计，根据算法优 良的评价标准去衡量b g m m n 聚类算法的整体聚类的预测精度e - s e o r e 一 文献【1 j 建立了两种不同分布的有限维联合混合模型，独立地g a u s s i a n 与b e t a 分布的有 限维联合混合模型( b g m m ) ，b g m m 模型的提出可以看成是对g a u s s i a n 分布有限维混合模 型( g m m ) 和b e t a 分布有限维混合模型( b m m ) 的自然扩充，并且联合混合模型b g m m 的建 立比分开各自独立建馍( 只建立g m m 模型或者只建立b m m 模型) 的聚类的效率要高，聚类结 果更精确，因为联合混合模型充分利用了数据提供的信息文献【1 】针对有限维联合混合模型 b g m m ，基于似然最大化的原则提出了3 种不同的e m 聚类算法，标准的e m 算法( b g m m s ) ， 近似的e m 算法( b g m m a ) 和混合的e m 算法( b g _ m m h ) 对聚类的数目的估计，采取如下的 方法：在3 种e m 聚类算法中应用4 种模型选择标准：a i c ，b i c 。，a i c 3 ，i c l ，根据每种 标准分别给出3 种e m 聚类算法的聚类数目，从中选择每种e m 聚类算法最适合的一个标准 。( 在相同的模拟框架下，针对每种e m 聚类算法，从4 种模型选择标准中，选择估计的聚类数 目与真实聚类数目一致的次数最多的标准) 即：b g m m s 用模型选择标准i c l 给出聚类的数 目估计；b g m m a 用模型选择标准a i c 给出聚类的数目估计；b g m m h 用模型选择标准a i c 给出聚类的数目估计 b g m m n 聚类算法的提出有下面几个原因；1 ) 对g a u s s i a n 分布数据与b e t a 分布数据假设 有相同的类的结构；2 ) 对同一分类指标，g a u s s i a n 分布数据与b e t a 分布数据彼此独立；3 ) e m 算法对g a u s s i a n 分布参数的估计有显示表达，而且估计的好坏评价标准，估计的性质等结论 都有理论保证，但是e m 算法对b e t a 分布的应用时，计莽比较复杂，丽且估计没有显示表 达；4 ) 文献 1 】中得到联合混合模型b g m m 对正态分布数据比较敏感的结论因此b g m m n 聚类算法最初只利用来自g a u s s i a n 分布的数据给出初始聚类这样不仅提高了每个类给出的 b e t a 分布参数的估计的准确度，而且在相同的背景框架下可以提高聚类的效率为了充分利 用数据提供的信息，把两种分布整合在一起去确定最后的聚类 8 东北师范大学硕士学位论文 本章主要介绍b g m m n 聚类算法，在3 1 节介绍b g m m 联合混和模型【1 l ，在3 2 节具体 介绍b g m m n 聚类算法，并在3 5 节给出模拟和结论，利用模拟比较b g m m n 聚类算法与聚 类算法b g m m s ，b g m m a ，b g m m h 的聚类整体预测精度e - s c o r e ，及对聚类数目估计的准 确率，指明b g m m n 聚类算法的优势 3 1b g m m 混合模型 一给定数据集x = x l ，x 2 ，凰，) ，假定x 1 ，拖，拖，以概率矾来自每个类，其中 七= i , 2 ，g 记x = ( y r ，z 丁) r ，其中y 表示b c t a 分布数据，z 表示g a u s s i a n 分布数据。对y 与z 假 设有相同的类的结构，并假定对同一分类指标k ，k = 1 ，2 ，g ，k 与五独立，i = 1 ，2 ，n y = ( k ，蚝，碥) ，k ( i = 1 ，2 ，n ) 为p l 维向量，且m ，k 彼此独立，密度函数为 砌t 吨乒， 其中参数0 1 k = ( q 胁o t k 2 ，o 卸1 ：仇1 ，觑2 ，风p 1 ) z = ( z l ，忍，磊) ，磊( 江1 ，2 ，他) 为p 2 维向量，且历，历，磊彼此独立，密度函数为 y k ( z d 0 2 t ) 2 赢e x p 一壶( 磊一肛七) 丁一1 ( 磊一p t ) l ? ， 其中参数0 2 k = m 批# k 2 ，p p 2 ；盯 ，程，嚷) ，= d i a g ( a 2 ，砖，吃) 记o k = ( 口1 ，0 2 k ) ，0 = ( 秽1 ，鲐) ，则式子( 2 ) 可以写成 五g o ，( x l ，x 2 ，x 3 ，x 。i o ) = n 讯a ( m 矽l 七) ( 五| 如) ， ( 6 ) 引入数据集x 的分类标签鼠= ( h i l ，h i 2 ， t g ) 丁，若数据五来自第k 个类，则h i k = l ；否则 h i k = 0 ，其中k = 1 ，2 ，g ，i = 1 ，2 ，n 则( 5 ) 式的l o g - 似然函数为 ng l o gl h ( 0 ) = i ( h i k = 1 ) l 。g a ( m | 秽l k ) a ( 磊l 如女) ) ，( 7 ) i = 1k = l 其中i ( h i 奄= 1 ) 为示性函数令参数0 的极大似然估计为每，x i 来自第k 个类的后验概- g i g 为瓦k ，表达式为 讯卵 h i k = - 1 嗍2 糍， 9 东北师范大学硕士学位论文 把分类标签h 看成缺失，则由e m 算法的e 步得完全数据的l o g - 似然函数 q ( o l o ( ”) ) = i x , o f 。) ( 1 0 9 l n ( o ) ) ng = e = 1 x i ，p ：m 】l o g 7 r k a ( y i l o l 七) f k ( z j j 0 2 知) i = 1k = l ， 其制= 蔷鬻， 咿( m ) 表示第1 n 部迭代参数的估计 3 2b g m m n 算法 o ) 给出分布中参数订，肛，盯的初值： 7 r k ( o ) 2 刀1 ， p 知。( ，c r v 2 ( o ) 利用模糊c m e a n s 聚类算法给出 1 利用e m 算法估计g a u s s i a n 分布的参数| “，即，在给定第1 l l 步迭代的参数p 2 ( m ) 的 条件下，求使l o g - 似然函数 取得最大值时的f l ，宝更新参数： 卢譬+ 1 1 = i ：。厶r i i k ：( ，m ，) 。z 。、_ v 万， ， 方p d = 去气七m ( 一胁( m ) 2 ， 膏：m + d = 去兀七( m ) ， ( 秽= 1 名慨南= 1 ，2 ，g ) r 2 l 更新分类指标矗k 3 ) 重复 1 】， 2 ) 直到收敛为止 1 0 、l ， k如磊k 一 吼p取g o 絮 g 糊n 汹 = 、l ， 弘 秽 邑a 丌 ，t g b m 七t g 随n 谢 1 1 0 _ p 2 p q 东北师范大学硕士学位论文 4 ) 利用第 3 ) 步收敛时n 七的取值，根据分类准则：若 k 0l 瓦知。= m a x 气k ，把数据 k 分到第k o 类，给出数据x 的初始聚类 5 记，f 0 表示第 4 步得到的第k 个类的集合，( 南= l ，2 ，g ) n ? 表示集合o 中 包含数据的个数。在给定第m 步的分类集合妒，第m 步的分类集合包含的数据的个数n ， 的条件下，更新模型中的参数6 l 七，秽z 知，使得( 6 ) 式达到最大更新参数： a ( m + ，反+ 1 由m a t l a b 中的b e t a f i t ，给出，其中u 妒， d 2 + 1 ) - 去， 佗孟诞j ， 子：( ”1 7 = 凳，g ( z 。一p ? m ) ) 2 ，i e i i m k = l k j 缈删= 去喜制， ( 一囊。砌； 2 9 6 ) 利用 5 得到的估计重新更新分类指标瓦知 7 妒“通过 6 ) 得到的于i k + 1 按照分类标准给出 8 ) 重复 5 ) ， 6 ) ， 7 ) 直到收敛为止 3 3 模型选择 通过对模型选择标准a j c ，a i c 3 2 绷，b i c 2 5 【2 6 】，i c l i l 7 ：各自确定的聚类数目的比 较，选择最优的模型选择标准在b g m m n 聚类算法中分别应用模型选择标准a i c ，a i c 3 ， b i c ，i c l ，在相同的背景框架下，把由算法得到的正确的聚类数目次数相加，模拟结果对 a i c ，a i c 3 ，b i c ，i c l 分别为2 2 ，1 9 ，6 ，6 因此b g m m n 聚类算法选择a i c 作为给 出最优聚类数目的选择标准 a i c = - 2 l o g l ( o ) + 2 d ， a i c 3 = 一2 l o gl ( o ) + 3 d ， b i c = - 2 l o g l ( o ) + d l o g n m ， 。 = 2 l o gl 0 ) + ：n m 一勺il o g ( 勺i c l - 2 l o g l ( od l o g n m 2 l o g ( g i ) ， = +一 ：勺i ) ， j = li = 1 其中d 为模型中自由参数的个数，m 为数据集的总数( m = w ：l ，表示数据集 揣耥冀 牡 东北师范大学硕士学位论文 w 的大小，w 表示输入数据集的个数) 在b m m 模型中自由参数1 3 细有最g 个，自由参数傀。 有p 1 g 个，在g m m 模型中自由参数| “妇有p ：g 个，自由参数盯i 有b 个。因为是l7 r k = 1 ， 则自由参数丌有g 一1 个因此d = 2 1 g + 恳+ 2 g + g 一1 3 4 算法优良的评价标准 为了估计b g m m n 聚类算法的整体聚类预测精度e - s c o r e 。我们研究由b g m m n 聚类算法 得到的聚类宜与真实聚类h 之间所有可能的联系。定义由b g m m n 聚类算法得到的聚类矗与 真实聚类h 之间的最好的匹配的得分为e - s c o r e 1 i ，对每个数据集，由算法得到的聚类詹与真 实聚类h 之间的最后的得分e - s c o r e ，用此数据集得到的1 0 个e - s c o r e 的中位数去估计 令乃定义为蜀的真实聚类数r 表示f 与h 间所有可能的联系，r t 表示由b g m m n 算法得到属于第i 类的数据的标签，j 5 r j 为数据通过b g m m n 算法得到的聚类数字0 为 b g m m n 算法得到的聚类的个数，g 为真实的聚类的个数则得分e - s c o r e 定义为： e f ( ；) ：| 1 当岛= i 并且n 2 t j 时； 。 ”7 10 其他情形 肚 r m a r x - 去薹啪) r = r = ( r l ，r 2 ，r 0 ) jv i 歹，r t 勺：r i 1 ，2 ，：, m a x g ，g ) ， 。 如上定义的算法评价标准，不仅记录了算法聚类结果的精确性，也反映了模型选择标准的 优良程度 。 3 5 模拟和结论 模拟1 模拟1 主要是比较的b g m m s 聚类算法，b g m m a 聚类算法，b g m m h 聚类算法与b g m m n 聚类算法的整体预测聚类精度e - s c o r e ，以及4 种聚类算法对聚类数目估计的准确率。 在比较b g m m s 聚类算法，b g m m a 聚类算法，b g m m h 聚类算法与b g m m n 的聚类算 法的整体预测聚类精度e - s c o r e 时，选用和文献f 1 】中相同的模拟数据集，其中分布的参数见表 t a b l e1 数据集分为高质量( 容易聚类) 和低质量( 不容易聚类) 两种数据类型，用g b 表示 容易聚类的b e t a 分布，b b 表示不容易聚类的b e t a 分布，g g 表示容易聚类的g a u s s i a n 分布，b g 表示不容易聚类的g a u s s i a n 分布同时对b g 又设计有两种数据类型，一种是 因均值间彼此接近而不容易聚类的数据，用b g m 表示；一种是因方差很大而不容易聚类 1 2 东北师范大学硕士学位论文 的数据，用b g v 表示模拟数据集设计为有3 个真实的类，佗= 1 0 0 ，只= 4 ，恳= 4 对随机产生的每一数据集模拟1 0 次，聚类算法最后的e s c o i e 为对随机产生数据集模拟1 0 次 得到的e - s c o r e 的中位数，对4 种聚类算法的整体预测聚类精度e - s c o r e 的描述见图f i g u r e1 在比较b g m m n 聚类算法，b g m m a 聚类算法，b g m m h 聚类算法与b g m m s 聚类算法 对聚类数目估计的准确率时，模拟数据集同上，见t a b l e1 每种聚类算法对随机产生的数据 集模拟1 0 0 0 次，在1 0 0 0 次模拟中，把估计的聚类数目e = 真实的聚类数目g 的次数相 加，和记为n ，则聚类数目估计的准确率为去熹4 种聚类算法对聚类数目估计的准确率的 描述见表t a b l e2 t a b l e1 模拟1 的数据集 c l u s t e r1c l u s t c r2c l u s t e r3 g ba l p h a 1 52 02 52 02 02 51 5512 013 0 b e t a2 01 52 02 52 02 51 5。5 2 013 01 b b a l p h a 1 51 02 52 0l o51 51 23 02 53 03 5 b e t a l o1 5 2 02 5 51 0 1 2 1 52 53 03 53 0 g g i l l c a b99 1 1一1 1 1 01 01 2一1 2王1 1 l 1 31 3 v a r i a n c eo 10 20 1 50 2 50 10 20 1 5 0 2 5 0 10 20 1 5o 2 5 + b g m i n e a n 9 19 11 1 1一1 1 19 29 21 1 21 1 29 39 3 1 1 3 1 1 3 v a r i a n c e0 10 20 1 5o 2 5o 10 20 1 5o 2 50 10 20 1 5o 2 5 b g vm e a n991 l1 11 01 01 21 21 1 1 1 1 3一1 3 v a r i a n c el21 52 5。l21 52 5121 52 5 g b ，b b 和g g 分别代表容易聚类的、不容易聚类的b e t a 分布数据和容易聚类 的g a u s s i a n 分布数据；b g m 和b g v 分别代表均值接近时和方差很大时不容易聚类的 g a u s s i a n 分布数据。 1 3 东北师范大学硕士学位论文 1 0 9 0 8 一b g m m a = b g m m h 二二 b g m m s lb g m m n 2345 6 f i g u r e 1 横一轴表示不同的模拟数据集：1 ；g b + g g ，2 ：b b + g g ，3 ：g b + b g m ，4 ：b b + b g m ， 5 ：g b + b g v ，6 ：b b + b g v 纵一轴表示聚类算法的整体聚类预测精度e - s c o r e b g m m a ，b g m m h ，b g m m s 分别表示近似的e m 算法，混合的e m 算法，标准的e m 算 法，b g m m n 表示本篇论文中提出的算法 t a b l e2 聚类个数预测的准确度 g g + g b ，g g + b b ，b g m + g b ，b c m + b b ，b g v + g b ，b g v + b b 表示不 同的数据集，b g m m n 表示本文提出的聚类算法，b g m m a ，b g m m h ，b g m m s 表示文献 【l 】提出的3 种聚类算法 从图f i g u e r1 可以看出，尽管4 种聚类算法对不同的数据集聚类的整体预测聚类精度b s c o r e 有所不同，但是对模拟1 设计的模拟数据集，4 种聚类算法的整体预测聚类精度e - s c o r e 大体上是可以看做是相似的( b b + g g 除外，对b b + g g b g m m n 聚类算法的整体预测 1 4 7 6 5 4 3 2 1 0 0 o 0 0 0 0 0 东北师范大学硕士学位论文 聚类精度e - s c o r e 比其它3 种聚类算法的整体预测聚类精度e s c o r e 高，但是b g m m s ，b g - m m a ，b g m m h ，3 种聚类算法对b b + g g 的整体预测聚类精度e - s c o r e 大体上是相似 的) 这说明b g m m n 聚类算法并不比b g m m a 聚类算法，b g m m s 聚类算法，b g m m h 聚类 算法差，甚至对数据集g g + b b ，b g m m n 聚类算法更有优势从表t a b l e2 可以看到，除数 据集b g m + g b 外，b g m m n 聚类算法对聚类数目估计的准确率比b g m m s ，b g m m a ， b g m m h3 种聚类算法高。特别是对数据集g g + g b 和g g + b b ，b g m m n 聚类算法对 聚类数目估计的准确率比其它三种聚类算法的高很多说明b g m m n 聚类算法得到的类更准 确模拟1 不仅对4 。种聚类算法的整体预测聚类精度e - s c o r e 和对聚类数目估计的准确率进 行比较，对4 种聚类算法的运行时间也给出比较，在相同的背景框架下，4 种聚类算法的运 行时间相差不大，可以说没有很大的区别。综上所述，b g m m n 聚类算法比文献【1 提出的3 种聚类算法更有优势。而且b g m m n 聚类算法对g a u s s i a n 分布数据容易聚类的情况下更适合 模拟2 模拟2 主要是比较有限维联合混合模型b g m m 与b g m m 的一个极端模型( 有限维正态混 合模型g m m ) 的整体预测聚类精度e - s c o r e 设计数据集见表t a b l e2 与模拟1 数据集的设计 一样，数据集有高质量( 容易聚类) 和低质量( 不容易聚类) 两种类型数据集设计有3 个真实 的类，仃= 1 0 0 ，p a = 尼= 4 。由模拟1 可以看出文献f 1 中给出的3 种聚类算法的整体预测 精度e - s c o r e 没有太大的差异，因此，在此模拟中以b g m m a 聚类算法为代表进行研究。对随 机产生的每一数据集模拟1 0 次，b g m m n 聚类算法，b g m m a 聚类算法和极端模型g m m 聚 类算法的整体预测精度e s c o r e 的描述见图f i g u r e2 t a b l e3 模拟2 的数据集 c l u s t e r1c l u s t e r2 c l u s t e r3 g b a l p h a 1 52 0 2 52 0 2 02 51 5512 013 0 1 ) e t a2 01 52 02 52 02 51 552 01 。 3 01 b b a l p h a 1 51 02 52 01 051 51 23 02 53 03 5 b e t a1 01 52 02 551 01 21 52 53 03 53 0 g g m e a n99 51 11 19 51 01 1 51 1 51 01 0 51 21 2 v a r i a n c e0 50 60 7 0 8 o 50 6 0 7 0 8 0 5 0 60 70 8 b g mi n e a l l 9 19 11 1 11 1 19 29 21 1 21 1 29 3 9 31 1 3 1 1 3 v a r i a n c eo 5o 6o 70 8o 5o 6o 70 80 50 60 70 8 b g vi l l e a n99 51 11 l9 51 01 1 51 1 51 01 0 51 21 2 v a r i a n c e1 522 531 522 531 52 2 53 1 5 东北师范大学硕士学位论文 g b ，b b 和g g 分别代表容易聚类的、不容易聚类的b e t a 分布数据和容易聚类 的g