（计算机软件与理论专业论文）基于半监督聚类算法的研究与应用.pdf

!j一 i a b s t r a c t s u p e r v i s e dl e a r n i n gh a st ok n o wa l lt h el a b e l e di n f o r m a t i o n ，w h i l et h eu n s u p e r v i s e d l e a r n i n gd o e sn o tm a k ef u i l u s eo ft h ei a b e l e di n f o r m a t i o n ，w h i c hr e s u l t si nt h e b l i n d n e s so ft h ec l u s t e r i n g s e m i s u p e r v i s e dl e a r n i n gh a sa l w a y sb e e no n eo ft h ef o c a l p r o b l e m si nd a t am i n i n gr e a l mi nr e s e n ty e a r sb e c a u s ei t h a ss e m i - s u p e r v i s e dl e a r n i n g a n du n s u p e r v i s e dl e a r n i n gm e r i t s t h ep a p e rm a i n l yi n t r o d u c e ss e m i - s u p e r v i s e da l g o r i t h ma n dc l u s t e r i n ga n a l y s i s t h es e a r c h - k m e a n sc h o o s e st h ec e n t e rp o i n to n l yl o c a lo p t i m u ma n dn o tg l o b a lo p t i m u m ， w h i c hr e s u l t si nu n r e a s o n a b l ec l u s t e r r e s u l t b ya n a l y z i n g t h es e a r c h - k m e a n s s e m i s u p e r v i s e dc l u s t e r i n ga l g o r i t h m ，ad s - k m e a n sa l g o r i t h m i sp r e s e n t e da n dt h e a l g o r i t h mu s i n gt h ed i c h o t o m yf r o mt h eu n l a b e l e dd a t a s e t st oc h o o s et h ec e n t e rp o i n t t h em e t h o dc a nm a k et h ec l u s t e rr e s u l tg l o b a lo p t i m u m a n dm e a n w h i l e ，b yt h i sw a y , c h o o s i n ga l lt h ec e n t e rp o i n tn e e dt om a k eo n l yas i n g l ep a s st h r o u g h ad a t a s e t s c o m p a r e dw i t ht h es e a r c h - k m e a n sa l g o r i t h m ，t h ed s - k m e a n sa l g o r i t h md e c r e a s e st h e c o m p u t a t i o n a le x p e n s ea n dr e d u c e st h et i m ec o m p l e x i t y k - m e a n sa l g o r i t h ma n di m p r o v e da l g o r i t h m sh a st oa s s i g nc l u s t e rn u m b e r , w h i l e c h o o s i n gt h ec l u s t e rn u m b e rh a sb li n d n e s sa n dr a n d o m n e s s o nt h a tb a s i s ，ab s c k m e a n s a l g o r i t h mi sp r e s e n t e da n dt h ea l g o r i t h md o e sn o tk n o wt h ec l u s t e rn u m b e ra n da l s o c l u s t e r st h ed a t a s e t s b yu s i n gi r i sd a t a s e t sb s c k m e a n sc l u s t e r i n ga l g o r i t h ma r ed e e p l y a n a l y z e db yc h a n g i n gt h et h r e s h o l da n dl a b e l e dc l a s si n f o r m a t i o na n da u t o m a t i c a l l y g e n e r a t e dd a t a s e t sf i n a l l yc o m p a r e dw i t ht h es a m ec l a s s a l g o r i t h m s e a r c h k m e a n s a l g o r i t h m a n db yt e s t i n g ，t h eb s c k m e a n sa l g o r i t h mi sb e t t e rt h a nt h es e a r c h - k m e a n s a l g o r i t h mi nt h ea c c u r a c y a tl a s t ，b s c k m e a n sa n dd s - k m e a n sa l g o r i t h ma r er e s e a r c h e db a s e do na p p l i c a t i o n o fh a i e r sc u s t o m e rs e g m e n t a t i o n b yt h ec o m p a r i s o n ，t h es e g m e n t a t i o no fh a i e r s d i f f e r e n tc u s t o m e rg r o u pi si m p l e m e n t e da n dc h a r a c t e r i s t i c so fe a c hg r o u pa r er e s e a r c h e d r e l e v a n c ej u d g m e n t sw i l lp r o v i d ea na n c i l l a r ys u p p o r tf o rc o m p a n y sb u s i n e s sa n a l y t i c s a n dd e c i s i o nm a k i n g k e yw o r d s ：d a t am i n i n g ；s e m i - s u p e r v i s e dc l u s t e r i n ga n a l y s i s ；c u s t o m e r s e g m e n t a t i o n ，rp r i ， 夕oirlr， 11 11】 _j1 1-1 jl j11i 目录 第章绪论1 1 1 背景与意义1 1 2 研究动态4 1 3 论文结构5 j l 蹲i i ；二j f ：i i l ! ；l 晰6 f j 施6 2 1 聚类概述6 2 1 1 数据问的相似性度量6 2 1 2 类间距离8 2 1 3 主要的聚类分析方法9 2 2 半监督聚类相关理论基础一1 2 2 2 1 半监督聚类算法的分类1 2 2 2 2 半监督聚类算法分析与比较1 3 2 2 3 半监督聚类算法的应用1 4 2 3 本章小结1 5 第三章基于半监督聚类算法的改进算法1 6 3 1 半监督聚类算法1 6 3 1 1s e e d e d k m e a n s 算法及其性能分析1 6 3 1 2s e a r c h k m e a n s 算法及其性能分析1 8 3 2 基于二分搜索的半监督聚类算法1 9 3 2 1d s - k m e a n s 算法1 9 3 2 2d s - k m e a n s 算法实验及分析2 1 3 3 基于较优搜索约束的聚类算法2 3 3 3 1 相关定义2 3 3 3 2b s c - k m e a n s 算法2 4 3 3 3b s c - k m e a n s 算法实验及分析2 6 3 4 本章小节2 7 第四章半监督聚类算法在客户分群中的阙鹦 4 1 引言2 8 4 2 基于客户分群的模型理论2 8 ，r ， l-r，yrlrr y，r， 4 2 1 客户分群的目标2 8 4 2 2 客户分群的标准2 8 4 2 3 客户分群的流程2 9 4 3 半监督聚类算法在海尔客广分群中的应用3 3 4 3 1 实验环境3 3 4 3 2 数据的选取和预处理3 4 4 3 3 海尔客户分群的实验3 5 4 4 本章小结3 8 第五章皱总结与展望 5 1 伞文工作总结3 9 5 2 存在的问题与今后展望3 9 j l i j j ! 燃4 l 攻读学位期间的研究成果4 5 致谢4 6 学位论文独创性声明4 7 学位论文知识产权权属声明4 7 第一章绪论 1 1 背景与意义 第一章绪论 近年来，随着企业海最数据的出现，数据库技术为海鼍数据的存储提供了丌j 能， 而面对海量的信息，人们却无法利用和发现这些信息所含有的信息，更不用说得到 有价值的信息。面对传统的决策系统无法满足现在人们的迫切需求，同时，计算机 硬件技术和信息技术的飞速发展，数据挖掘技术应运而生。 目前，随着社会的发展和计算机技术的进步，企业能以各种快捷方便的方法和 方式得到海量数据，这样就造成了海量数据的快速增长。随着i n t e r n e t 的出现和 快速应用，加上后来应运而生的企业网的出现和发展及虚拟私有网的出现和发展， 让企业不仅仅在着眼于某个部门或者某个单位的数据库存储的海量数据，而是把眼 光放在世界的巨人信息海洋。 正足针对巨量信息的更加庞大的膨胀，数据挖掘作为解决海量数据而知识贫乏 的问题的挖掘技术被大量而广泛的应用于各个领域之内。 数据挖掘n 1 技术是基于统计学，数据库，人工智能，机器学习和模式识别等学 科而形成的一个多学科交叉学科。 数据挖掘的过程可以大体分为：数据准备和数据预处理、数据挖掘以及对于结 果的解释和评估，见图1 1 所示。 姗 图i 1 数据挖掘的流程 ，ri ， ， rrr olrrlrlr，iir ， r，-ro，l，-iri， r il【r， 青岛人学硕十学化论文 聚类心1 分析是数据挖掘技术里的重要挖掘技术之一，顾名思义，聚类就是根据 数据巾可能的描述对象的信息及其之问关系的描述信息，将一组数据对象划分成若 干个不i _ j 的簇，使得簇内对象相似性尽可能大，而簇问对象的相似性尽可能小。聚 类过程4 同于分类，它是一种无监督学习的过程，它可以在完全无相关先验信息的 情况下对数据对象进行内在关系的处理和分析。聚类分析在各个领域的用途特别广 泛。比如在商业中，分子生物学，气候分析中、社会学分析中以及网络信息安全中， 都有很好的应用。 在现实情况的应用巾，在对数据处理的时候，除了得到数据，有可能同时得到 和数据有关的一些先验知识，举例来说，对于一个数据集来说，可能事先知道一小 部分数据的类别信息。如果用传统的聚类算法，就会忽略这部分具有类别的数据， 不能很好的利用已知信息资源进行聚类分析。 针对这样的知道一部分标记信息的情况下，利用标记信息对数据集进行聚类的 情况，有人提出了半监督学习b 1 方法。 半监督学习是机器学习和模式识别领域的一个研究热点问题，它是介于完全标 记信息有监督的分类分析和完全无监督信息的聚类之问的一种情况，无监督学习是 一种自学习方式，一般不需要对数据集做类别标记，也可以不知道类别信息，就可 以处理未标记的含有噪声的数据对象，并且过程不需要进行人工干预，能够分析出 数据集的类别；监督学习是一种利用数据集和相关机器学习算法进行训练得到一个 模型，通过对模型的修正，然后利用已经得到的模型对其他的数据进行分类。 近年来，聚类分析方法作为数据挖掘技术中的重要方法中的一个，目前越来越 受关注，常常出现在各种实际应用领域。 例如图1 2 所示，这是2 0 0 8 年w w w k d n u g g e t s c o m 一做的调查，从图中可以看出， 目前数据挖掘已经在社会生活的各个方面和领域有了广泛的应用。特别是在客户关 系管理中的应用更为明显，说明目前很多企业特别是销售和服务业，已经越来越重 视客户的消费隋况。以及时作出相应的策略调整。 2 ，1 j1，11 1 1， 1 jj1j，1j-、1j，、 第一章绪论 i n d u s t r i e s ，f i e l d lw h e r ey o ua p p l i e dd a t am i n i n g n2 0 0 8 ：1 1 0 7v o t e r s c r m c o n s u m e r a n a l y l i c s 4 1 ) b a n k l n g ( 3 4 ) f r a u dd e t e c t i o nt 2 1 f i n 8 n c e ( 1 8 ) d = r e c tm a r k e t i n g f u n d r a i s i n g 1 5 c h h e f ( 1 4 i n v e s t m i n t ，s t o c k s 1 4 c r e c h ts c o n n gt 1 4 ) t e l e c o m c a b i et 1 3 ) r e t a l it 1 3 ) a d v e r t i s i n g 13 ) b o t e c l - # g e n o m i c s 1 劲 s c i e n c e 11 l i n s u r a n e e 11 ) h e a i t hc a r e h r 1 0 ) m a n u f a c t u r i n g1 9 ) e c o m m e r c e ( 8 ) w e bu s a g em in i n 口( 8 ) s o c i a lp o b c y s u r v e ya r i a l y s i s 8 ) m e d l c a vp h a r n q i a 8 ) s e c u n t y a n h t e r r o r i s m1 6 ) s e a r c h w e bc o n t e n tm l m n g 6 g o v e r n m e n t m i i t t a r y o ( 2 1 ) k = l 当q 分别为l ，2 ，o c 时，明氏距离变为绝对距离 欧式距离 以及切比雪夫距离 碣( f ，_ ，) = 圭i - - x k 量= i 毗) ：( 圭i x , , - x j k 2 ) ； 以( f ，j ) = m a x 觚，k - x j k l ( 2 2 ) ( 2 3 ) ( 2 4 ) 明氏距离函数以其简单直观在实际的应用中被广泛地使用，但是它也存在一些不 足，特别是受变量的量纲的影响比较大，通常为了消除量纲的影响要现对数据做 标准化处理。 2 马氏( m a h a l a n o b i s ) 距离 马氏距离是对明氏距离的改进距离。它克服了明氏距离受量纲的影响，考虑到 样本各个变量的观测值通常为随机变量，所以第i 个样品的p 个变量的观测值 五= ( 薯。，而：，) 7 是p 维随机向量。因为随机向量具有分布规律，各个分量之间可 能相关，所以将两个样品作为两个随机向量的个体，将第i 个样品和第j 个样品之 间的马氏距离的平方定义为： 7 u111 jjl1 1 第二：章基丁聚类分析的方法 旄( ，_ ，) = ( 薯- x j ) 7 叫( x , - x j ) ( 2 5 ) 其中，是随机变最的协方差矩阵，如果该值没有明确知道，可以用其估计 值。 马氏距离虽然是明氏距离的改进，但是在实际的应用中却尽可能的彳i 用，因为 在没有分好类别之前，直接采用整体样本矩阵的均值和协方差计算出的马氏距离并 不能得到很好的效果；并且对于数据量比较大的情况下，马氏距离的计算比较麻烦， 计算量也比明氏距离麻烦，所以在通常的使用中，马氏距离的使用很少。 相似性度量的标准除了利用对象问的距离之外，还可以用两个对象之问的相似 系数，同样地，两个对象问的相似系数也有多种定义形式，下面介绍常见的两种： 1 夹角余弦 在聚类分析中，样晶作为p 维空间的向量，它们的相似系数可以用两个向最问 的夹角余弦表示，所以可以把样本i 和样本j 之间的相似系数记作： 靠 “力- c o s 峨卜蕊 q 6 其中，q ( i , j ) 【一l ，l 】，当两个样本完全部相似时，口( ) = o 2 相关系数 两个向量之间的相关系数定义为 r ( i ，) = ( 一墨) ( 一弓) = l ( 2 7 ) 其中，焉= 去喜，弓= i l 善f o ，g j ) - l , q ，当， ) 2 l 时正相关，当 ，( f ，歹) = 0 时不相关，当，g 力一1 时负相关。 2 1 2 类间距离 设g 是有m 个元素g ，g ：，组成的集合，若将类g 的元素蜀看作随机向量薯， 8 青岛人学硕+ 学化论论文 则类间距离有如下几个： l 重心距离 类的中心记为各个元素的均向量： 而= 去善 ( 2 8 ) 2 类的直径 类的直径也有很多表示，其中比较简单是类中元素问的最长距离定义为直径， 见= m a x 帆伽( d ( ，) ) ( 2 9 ) 或者记作类中各个元素到重心的欧式距离之和。 见= ( 薯一瓦) ( 薯一磊) ( 2 1 0 ) 3 最短距离 也就是对于来自两个类g ，q 中的两个样本i 和j 之间的距离d ( f ，) ，最短距 离即是： 仇。m i n 艟q ，归g d ( i ，) ( 2 1 1 ) 通常在使用某一距离的时候，如果在计算数据对象的距离时采用的是欧式距 离，那么在其他的递推公式用到距离的地方都要统一用一个距离。 2 1 3 主要的聚类分析方法 聚类分析方法叫n 1 1 耻1 通常可以分为划分法、层次法、基于密度的方法、基于网 格的方法以及基于模型的方法等。下面介绍一下几种常用算法的思想： 1 划分法：对于给定的由若干个记录组成的数据集d ，划分的任务就是通过反 复迭代构造d 的k 个分组，这k 个分组迭代的结果必须使得目标函数达到最优，同 时，它还必须满足：每个分组至少含有一个数据对象；每个数据对象当且仅当被分 到一个分组。判断一个划分结果好的准则通常是，同一个组内记录越近越好，不同 分组内的记录越远越好。 利用了该算法思想的典型算法代表是1 9 6 7 年m a c q u e e n 首次提出k m e a n s 算 法n 3 1 。由于k m e a n s 算法是很多其他改进聚类算法的基础，所以下面重点介绍一 下k m e a n s 算法。 ，11111 j11，111，jj 第二章基丁聚类分析的方法 k m e a n s 算法的思想是，首先输入参数为聚类的数量k ，该算法是从含有n 个 数据对象的数据集巾任意选取k 个对象作为初始簇的均值或中心，对于数据集巾剩 下的其余数据对象，根据和各个簇均值的距离，将其指派到最相似的簇中，然后计 算新得到的聚类的聚类中心，不断重复这个过程，知道准则函数开始收敛为止。通 常情况下，从数据对象 ，i 2 ，) 中随机选出k 个 嵋，w 2 ，) ，其中 ，= ， _ ， 0 ；i ) ( o ，矿) 若i o 日k k l l ，则跳转s t e p 6 ，否则跳转s t e p 8 ； s t e p 6 ：在s ，数据集中，在区间( 堑；旦，歹i d 】随机寻找一个中心，若存在，说明 它为第l + 1 + k 个中心； s t e p t - i ：转s t e p 5 。 s t e p 8 ：若k ； b 重新估计均值：胪卜南磊，石 c 更新迭代次数： ，卜t + 1 。 、lrir l llllrr irir ： 青岛人学硕十学化论文 s t e p l1 ：输出k 个簇。 d s - k m e a n s 算法主要是首先通过在未标。址数据集巾寻找最远的点作为第一个 中心点，然后通过每次寻找该点和标记中心点直接中问的点作为第二个中心点，依 次寻找，直到找到k - l 个中心点，进行k - m e a n s 聚类，最终找到中心点的时间复杂 度为o ( n l o g n + n ) ，算法在执行第二步调整的时间复杂度为0 ( n k t ) ，其巾，n 为数据 集的大小，k 为输入的类别，d 为迭代次数。这样d s - k m e a n s 算法的时间复杂度为 0 ( n l o g n + n + n k t ) ；s e a r c h - k m e a n s 算法的寻找中心点的候选集合的时间复杂度为 0 ( n 2 k ) ，通过m 个候选点在进行寻找巾心点的算法时问复杂度为0 ( m ) ，第二步调 整的时间复杂度为o