（计算机软件与理论专业论文）基于数据挖掘技术的crm研究.pdf

哈尔滨理工大学工学硕士学位论文 基于数据挖掘技术的c r m 研究 摘要 客户关系管理( c r m ) 是一种旨在改善企业与客户之间关系的新型管理机 制，它可以通过提供优质服务吸引和保持更多的客户，并通过对业务流程的全 面管理降低企业的成本。 本论文首先从c r m 的起源入手，详细分析了c r m 的含义与作用。在分 析c r m 与企业资源计划( e r p ) 之间关联的基础上，提出了一种c r m 与e r p 的集成模型，实现对企业内、外部资源的统一管理和充分共享，以更好地为企 业和客户服务。 然后，深入研究和分析了聚类中基于划分的k - m e a n s 算法和基于密度的 d b s c a n 算法，结合两种算法的优点和不足提出了一种改进的聚类分析算 法。该算法由于划分了数据集，降低了对主存的要求，而且算法中给出了计算 各局部数据集参数的方法。对于分布不均匀的数据集，由于各个局部采用不同 的参数值，使得算法对全局参数的依赖性降低，聚类质量更好。 最后，重点研究数据挖掘技术与客户关系管理中的结合。客户细分是客户 关系管理的基础，也是实施客户关系管理的关键环节。利用数据挖掘中的聚类 分析技术将一个大的客户群划分成一个个小的客户群体，且每个客户细分群内 的客户具有较大的相似性，而不同细分群之间的客户具有较小的相似性，从而 用来指导企业针对不同的客户细分群采取差异化的策略。通过将改进的聚类算 法应用于c r m 中，建立基于客户价值的客户细分模型，可以实现将企业客户 群按客户价值标准分类，对于保留高价值客户、重定价或抛弃负价值客户有重 要指导意义。 关键词客户关系管理；客户细分；数据挖掘；聚类分析 哈尔滨理工大学工学硕士学位论文 t h er e s e a r c ho fc r mb a s e do nd a t am i n i n g t e c h n o l o g y m , a d a b s t r a c t c u s t o m e rr e l a t i o n s h i pm a n a g e m e n t ( c r m ) i sak i n do fn o wm a n a g e m e n t s y s t e m sa i m i n ga ti m p r o v i n gt h er e l a t i o n s h i pb e t w e e nc o r p o r a t i o n sa n dt h e i r c u s i 0 m e r & i t 啪k e e pt o u c hw i 也a n da t t r a c tm o r ea n dm o r ec u s t ( m n e r st h r o u g h e f f i c i e n ta n dk i n ds e l v i e e $ m e a n w h i l e , i tc a nd e c r e a s et h ec o r p o r a t i o n s c o s t s t h r o u g hc o m p l e t em a n a g e r a e n to ft h eo p e r a t i o nf l o w f i s to fa l l ，i nt h i sp a p e r , w es t a r tf r o mt h eo r i g i no fc r m ，a n de x p l a i nt h e m e a n i n g sa n df i m e t i o no fc r mi nd e t a i l s b a s e do nt h ea n a l y s i s e so fr e l a t i o n s h i p b e t w e e nc r ma n de n t e r p r i s e 代s 讲l “冷p l a n n i n g ( e r p ) ，w ep r o p o s ea ni n t e g r a t e d s o l u t i o no fc r ma n de r pt oa c h i e v eau n i f i e dm a n a g e r n e n to fi n s i d ea n do u t s i d e e n t e r p r i s er e s o u r c e st os e l v oe n t e r p r i s ea n dc u s t o m e r sb e t t e r t h e n , b a s e do nt h ea l g o r i t h m s a d v a n t a g e sa n dd i s a d v a n t a g e s ，w ea n a l y z ek - m 既l l sa l g o r i t h ma n dd b s c a na l g o r i t h m , a n dd e s i g na ni m p r o v e dc l u s t e r i n g a l g o r i t h m 1 蛔u s eo ft h ep a r t i t i o no fd a t as e t , t h ei m p r o v e da l g o r i t h mr e d u c e st h e r e q u i r e m e n to fm e m o r y ；, t h em e t h o do fc o m p u t i n gv a r i a b l ev a l u ei sp u tf o r w a r dt o t h eu n e v e nd a t as e t , b e c , a u s eo fa d o p t i n gd i f f e r e n tv a r i a b l ev a l u 馏i ne a c hl o c a ld a t a 鞠t ，t h ed e p e n d e n c eo ng l o b a lp a r a m e t e r si sr e d u c e d , s ot h ec l u s t e r i n gr e s u l ti sb e t t e r a tl a s t , w ep u tm o r es 臼e n g t ht or e s e a r c ht h ec o m b i n a t i o nb e t w o e nd a t am i n i n g a n dc r m t h ee o u s t o m e rs e g m e n t a t i o ni st h eb a s i co fc r m ，a n di sa l s ot h ek e y d e p a r to fp u t t i n gc r mi n t of a c t u s i n gt h ec l u s t e ra n a l y s i st e c h n o l o g yi nd a t a m i n i n g , w ed e p a r t e dab i gc o u s t m e rd u s t e ri n t op i e c e s ，a n dc o u s t m e r si ns m a l l o o u s t o m 盯c l u s t e rh a v et h es a m ec h a r a c t e r s ，w h i l ec o s t m e r si nd i f f e r ts m a l l e o u s t o m e rc l u s t e rh a v ed i f f e r e n tc h a r a c t e r s ，s oi tc a ng u i d ee n t e r p r i s e st ot a k e d i f f e r e n c e so fs t r a t e g yt od i f f e r e n ts u b - g r o u p so fc u s t o m e r so nb a s i so ft h i sm o d d w ed i s c u s st h ec o u r s eo fb u i l d i n gac u s t o m e rc l a s s i f i c a t i o nm o d e lb a s e do nc u s t o m e r v a l u eb yt h ei m p r o v e dc l u s t e ra l g o r i t h m t h r o u g ht h i sp r o c e s s ，c u s t o m e r sc a nb e 哈尔滨理工大学工学硕士学位论文 置皇皇置毫詈| 置一i iil i irm g r o u p e da c c o r d i n gt ot h e i rc o n t r i b u t i o nt oe n t e r p r i s e i t c a l lp l a ya l li m p o r t a n t g u i d i n gs i g n i f i c a n c e f o rm a i n t a i n i n gh i g h - v a l u ec u s t o m e r s , r e s e t t i n gv a l u eo r a b a n d o n i n gn e g a t i v ev a l u ec u s t o m e r s k e y w o r d s c u s t o m e r r e l a t i o n s h i pm a n a g e m e n t ， m i n i n g , c l u s t e r i n ga n a l y s i s i i i 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文 2 一的理想效 果，最大化地提高企业对市场的快速响应能力和满足客户个性化需求的能力。 2 5本章小结 本章首先简述了c r m 的产生及核心管理理念。c r m 是一种以客户为中心 的管理理念与经营策略，它实施于企业的市场营销、销售、客户服务与支持等 与客户相关的领域，努力提高对客户的服务水平。但是单独使用c r m ，缺乏 来自企业后台的动态信息支持，无法实现实时信息处理，很难快速准确地响应 客户需求。因此，在分析了c r m 与e r p 之间关联的基础上，提出了一种 c r m 与e r p 的无缝集成模型，并简单分析了集成系统为企业带来的优势。 哈尔滨理工大学工学硕士学位论文 第3 章数据挖掘中聚类算法的改进 数据挖掘技术可以挖掘出大量隐藏数据，为c r m 系统提供技术支持，而 聚类技术作为数据挖掘的重要方法可以对数据进行合理划分，因而对数据挖掘 技术和数据挖掘中聚类算法的研究具有重要意义。 3 1数据挖掘技术 3 1 1数据挖掘的定义 1 技术上的定义数据挖掘a t am i n i n g ) 就是从大量的、不完全的、有噪 声的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又 是潜在有用的信息和知识的过程 2 2 , 2 3 。 与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。这个定义 包括多层含义：数据源必须是真实的、大量的、含噪声的、发现的是用户感兴 趣的知识。发现的知识是可接受、可理解和可运用的，并不要求发现放之四海 皆准的知识，仅支持特定的发现问题【2 4 , 2 5 1 。 数据和信息是知识的表现形式，发现的知识可以被用于信息管理，查询优 化，决策支持和过程控制等，还可以用于数据自身的维护。因此，数据挖掘是 一门交叉学科，它把人们对数据的应用从低层次的简单查询，提升到从数据中 挖掘知识、提供决策支持【2 6 】。在这种需求牵引下，汇聚了不同领域的研究者， 尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行计算等方面 的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域，形成新的技术 热点 2 商业上的定义数据挖掘是一种新的商业信息处理技术，其主要特点是 对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从 中提取商业决策的关键性数据。简而言之，数据挖掘其实是一类深层次的数据 分析方法。数据分析本身已经有很多年的历史，只不过在过去数据收集和分析 的目的是用于科学分析，另外，由于当时计算能力的限制，对大数据量进行分 析的复杂数据分析方法受到很大限制【2 7 , 2 8 。现在，由于各行业业务自动化的实 现，商业领域产生了大量的业务数据，这些数据不再是为了分析目的而收集 的，而是由于纯机会的商业运作而产生。分析这些数据也不再是单纯为了研究 哈尔滨理工大学工学硕士学位论文 的需要，更主要是为了商业决策提供真正有价值的信息，进而获得利润。但是 所有企业面临的一个共同问题是：企业数据量非常大，而其中真正有价值的信 息却很少，因此从大量的数据中经过深层分析，获得有利于商业运作、提高竞 争力的信息删。 因此，数据挖掘可以描述为：数据挖掘是提取有用信息的“数据产生一过 程，是从大量数据中挖掘出隐含的、先前未知的、对决策有潜在价值的知识和 规则，并能够根据已有的信息对未发生行为做出结果预测，为企业经营决策和 市场决策提供依据【3 。 3 1 2数据挖掘的实施 数据挖掘分为三个主要阶段：数据准备、数据挖掘、结果评价和表达，具 体过程如图3 1 所示。 i 一 数据准备 -j 如拥j 由j ， - l - 一岫 l 1 ，姒拍亿卿 7 ：1 葡禾1 , t 口r 刊衣硷1 数据挖掘 、嘎石弋田 、 l 数据清洗和集成 ，。a 。l 剁，户 f ，i 荔l l ： 一一 足f = w ，一、 义j 赢隈_知识 、 一一 数据1樨 l 达l k 一一- - 数据库 数据选择和转换 ，一一：， 图3 - 1 数据挖掘的过程 f i g 3 - 1t h ep r o c e s so f d a t am i n i n g 哈尔滨理工大学工学硕士学位论文 3 1 3数据挖掘的方法 数据挖掘通过对大量历史数据的分析，发现潜在有用的规则及预测未来趋 势，做出前摄的、基于知识的决策。数据挖掘的对象有如下若干种数据源：关 系数据库、面向对象数据库、空间数据库、文本数据源、多媒体数据、异质数 据库以及w e b 数据源等。数据挖掘的目标是从中发现隐含的、有意义的知 识，其功能用于指定数据挖掘任务中要找的模式类型，一般可以分为两类：描 述和预测 3 2 , 3 3 1 。经常使用的数据挖掘技术方法主要有： 1 统计分析方法统计分析方法是利用统计学、概率论的原理对各属性进 行统计分析，从而找出它们之间的关系和规律。统计分析方法是最基本的数据 挖掘技术方法之一。在数据挖掘领域，统计分析方法可用于分类和聚类。 2 聚类方法聚类分析输入的是一组未分类记录，被合理地划分为一系列 有意义的记录子集，即类或簇，分类的原则是最大化类内相似性、最小化类间 相似性。聚类是数理统计中研究“物以类聚的一种常用方法，是数据挖掘领 域最为常见的技术之一 3 决策树方法决策树方法就是利用训练集生成一个测试函数，根据不同 取值建立树的分支：在每个分支子集中重复建立下层结点和分支，这样便生成 一棵决策树。然后对决策树进行修剪处理，最后把决策树转化为规则，利用这 些规则可对新事例进行分类。这种方法实际上是根据信息论原理对数据库中存 在的大量数据进行信息量分析，在计算数据特征互信息的基础上提取出反映类 别的重要特征。典型的决策树方法有分类回归树( c a r t ) 、i d 3 、c 4 5 等。 4 粗糙集方法粗糙集理论是波兰p a w l a k z 教授在1 9 8 2 年提出的。在数 据挖掘领域，粗糙集方法被广泛应用于不精确、不确定、不完全的信息的分类 和知识获取粗糙集理论的特点是不需要预先给定某些特征或属性的数量描 述，如统计学中的概率分布、模糊集理论中的隶属度或隶属函数等，而是直接 从给定问题的描述集合出发，通过不可分辨关系和不可分辨类确定给定问题的 近似域，从而找出该问题中的内在规律。它无须任何先验信息，能有效地分析和 处理模糊和不确定数据，并从中发现隐含的知识，揭示潜在规律。 5 关联规则挖掘算法关联规则是数据挖掘的核心技术，是由r a g r a w a l 等人首先提出的，关联规则就是给定一组属性和一个记录集合，通过分析记录 集合，推导出属性间的相关性，是以形式为“a l 八a 2 八a n b i 八b 2 八 b n 一来描述数据之间存在的关系规则l 。其作用是在数据仓库的对象间挖掘出 满足一定条件的依赖关系，并有可能描述属性间的因果关系。 哈尔滨理工大学工学硕士学位论文 除了上述的常用方法外，还有模糊集合方法、最邻近算法( k n e a r e s t n e i g h b o r sm e t h o d ，k n n ) 和可视化技术等。在实际问题解决中，数据挖掘算 法是最核心的问题，关键就在于算法的选择和实现【3 5 1 。一般根据实际问题决定 选择采用何种挖掘算法，但往往为了达到更好的挖掘效果，还要同时使用多种 数据挖掘技术 3 6 , 3 ；5 。例如：在数据预处理阶段，会使用粗糙集方法进行属性归 约；在挖掘初期会使用聚类分析方法来预分类，简约规格化后的数据集合，为 后面采用其他的数据挖掘方法来达到更好的挖掘效果；当在挖掘过程中，发现 选择的数据不合理，或者采取的挖掘技术达不到预期效果，就重新开始挖掘过 程，因此可以说，整个挖掘过程就是一个不断反复的过程，通过运用多项技术 对原数据进行处理和分析，最后得出宝贵知识的过程 通过上面的分析我们可以发现，应用数据挖掘中的聚类技术可以发现数据 背后隐藏的知识，更好地利用这些数据，所以，c r a m 采用数据挖掘中的聚类 方法可以为企业经营决策提供重要支持1 3 引。 3 2基于划分的k m e a n s 算法 k - m e a n s 算法是聚类算法中经常实用的一种算法，它具有简单、快速并且 能够有效地处理大数据库的优点，但是算法是从n 个数据对象中随机选择k 个 对象作为初始聚类中心，使得产生的聚类结果具有很大的不确定性，因此算法 自身的缺陷限制了其应用范围。 3 2 1k - m e a n s 算法的原理 k - m e a n s 算法是硬聚类算法，是典型的基于划分的目标函数聚类方法的代 表，它是数据点到原型( 类别中心) 的某种距离和作为优化的目标函数，利用函 数求极值的方法得到迭代运算的调整规则【3 9 1 k - m e a n s 算法以欧式距离作为相 似性测度，它是求对应某一初始聚类中心向量w - ( v t ，吻，v k ) 7 最优分类， 使得评价指标五值最小。算法常采用误差平方和准则函数作为聚类准则函数， 误差平方和准则函数定义为公式( 3 1 ) 。 生一 ， 以= | i p ml l ( 3 1 ) i = lp e q 其中，m 是类c ：f 中数据对象的均值，p 是类c ：f 中的空间点。 分析误差平方和准则函数发现：k - m e a n s 算法是一个最优化求解问题，目 标函数存在着许多局部极小点，只有一个是全局最小点。目标函数的搜索方向 哈尔滨理工大学工学硕士学位论文 总是沿着误差平方和准则函数减小的方向进行。不同的初始值使得聚类中心向 量y 沿着不同的路径使目标函数减少1 4 0 1 如图3 - 2 所示，目标函数分别沿着 玖、圪三种不同的初始值向量的路径逐步减小，分别找到各自对应的最小 值。其中，只有b 点对应的最小值才是全局最小点，而a 、c 两点对应的最小 值是局部极小点。k - m e a n s 算法是一种爬山算法( h i l lc l i m b i n g ) ，算法终止时往 往找到的是局部极小值。 b 图3 2 局部极小与全局最优 f i g 3 - 2l o c a lm i n ；m u l na n dg l o b a lm o s to p t i l m n m k - m e a n s 算法采用迭代更新的方法：在每一轮迭代中，依据k 个聚类中心 将周围的点分别组成k 个簇，而重新计算的每个簇的质心( 即簇中所有点的平 均值，也就是几何中心) 将被作为下一轮迭代的参照点。迭代使得选取的参照 点越来越接近真实的簇质心，所以目标函数越来越小，聚类效果越来越好。 3 2 2k m e a n s 算法分析 k - m e a n s 的目标是根据输入的参数k ，将数据划分成k 个簇。该聚类方法 用到的数学思想很简单，但聚类的效果很好。 算法首先随机选取k 个点作为初始聚类中心，然后计算各个样本到聚类中 心的距离，把样本归到离它最近的那个聚类中心所在的类；对调整后的新类计 算新的聚类中心，如果相邻两次的聚类中心没有任何变化，说明样本调整结 束，聚类准则函数以已经收敛。 该算法属于动态聚类法( 也称逐步聚类法) ，其迭代过程采用按批修改方 法，即在每次迭代中都要考察每个样本的分类是否正确，若不正确，就要调 整。在全部样本调整完后，再修改聚类中心，进入下一次迭代。如果在次迭 代算法中，所有的样本被正确分类，则不会有调整，聚类中心也不会有任何变 化，这标志着以己经收敛，算法结束, 4 2 1 该算法框架如下： 1 给定大小为刀的数据集，令i - - 1 ，选取k 个初始聚类中心乃， 哈尔滨理工大学工学硕士学位论文 产l 2 ，3 ， ； 2 计算每个数据对象与聚类中心的距离d ，硼) ，i l ，2 ，3 ，o o b ，l ， 户l ，2 ，3 ，乒，如果满足公式( 3 2 ) d ( 而，乙( ，) ) = m i n d ( x , ，乙( ，) ) ，j = l ，2 , 3 ，力) ( 3 - 2 ) 则x t e w k 。 3 计算误差平方和准则函数五如公式( 3 3 ) 所示。 上万 上( ，) = f l 掣- z j ( i ) 1 1 2 = ik = l ( 3 3 ) 4 判断：若l 以( ，) 一( j 一1 ) i 孝则算法结束；否则，仁- + 1 ，计算七个新 的聚类中心，乙( j ) = ! n 兰i = i ，歹= 1 ，2 ，3 ，七，返回第2 步。 3 3 基于密度的d b s c a n 算法 e s t e rm a r t i n 等人提出的d b s c a n 聚类算法是一个基于密度的聚类算法。 该算法将具有足够高密度的区域划分为一类，并可以在带有。噪声 的空间数 据库中发现任意形状的聚类，它定义为密度相连的点的最大集合。 3 3 1d b s c a n 算法原理 d b s c a n 涉及一些新的定义： 1 给定对象半径e p s 内的区域称为该对象的e p s 邻域 2 如果对象的e p s 邻域至少包含最小数目m i n p t s 个对象，则称该对象为 核心对象。 3 给定一个对象集合d ，如果p 是在g 的e p s 邻域内，而g 是一个核心 对象，我们说对象p 从对象霉出发是直接密度可达的。 4 如果存在一个对象链p j ，p z ，内，p ，即，胁7 ，p i + i 是从以l f 刀) 关于e p s 和m i n p t s 直接密度可达的，则对象p 是从对象g 关于e p s 和 m i n p t s 密度可达的。 5 如果对象集合d 中存在一个对象d ，使得对象p 和g 是从d 关于e p s 和m i n p t s 密度可达的，那么对象p 和口是关于e p s 和m i n p t s 密度相连的。 哈尔滨理工大学工学硕士学位论文 该算法首先从数据库中选择任意的一个对象d ，然后查找该对象d 关于 e p s 和m i n p t s 的可密度到达的所有对象。如果对象d 的e p s 邻域内所有对象 个数大于某个阀值m i n p t s ，则该对象d 为核心对象，邻域中的点将作为下一 次的考察对象，否则，对象d 被暂时标记为噪声点若对象d 是核心对象， 则在数据库中存在一个关于e p s 和m i n p t s 的类c ，这个类c 能够被其中的任 意一个核心对象所确定。该算法就是不断地进行区域查询来进行类的扩展，直 到一个完整的类【4 3 川。 3 3 2d b s c a n 算法分析 d b s c a n 算法使用基于密度的聚类概念，即要求聚类空间中一定区域内所 包含对象( 点或者其它空间对象) 的数目不小于某一给定的阀龇l i n p t s 在该算法中，为了提高查询速度，进行区域查询时使用了r 树。在最坏情 况下，对于有n 个数据对象的数据库d 而言，这棵r 树的高度是o ( 1 0 9 n ) ，一次 区域查询的平均时间复杂度是o ( 1 0 9 n ) 。与整个数据库相比较而言，区域查询的 数据量是很小的。对于数据库中的对象最多只进行一次区域查询，所以对于有 价数据对象的数据库而言，d b s c a n 算法的平均运行时间复杂度是o ( n l o g n ) 。 d b s c a n 算法的显著优点是聚类速度快，且能够发现任意形状的聚类和有 效地处理。噪声点 ，但是它也存在如下一些缺点： 1 由于其算法是直接对整个数据库进行聚类，需要把所有数据载入内 存，因此当数据量很庞大时对主存要求较高。在聚类过程中，d b s c a n 旦找 到一个核心对象，即以该核心对象为。中心向外扩展一。在此过程中，核心对 象将不断增多，未处理的对象被保留在内存中。如果数据库中存在非常庞大的 聚类，用于存储核心对象信息的内存需要将很大且难以预料 2 输入参数敏感，不同的参数值可能会造成不同的聚类结果。d b s c a n 提供了一种可视化的方法辅助参数e p s 的确定。d b s c a n 计算每个对象与它的 第阶最近对象之间的距离k - d i s t ，并对库中对象按照k - d i s t 由大到小进行排序， 随后绘制“排序k - d i s t 图一，横坐标代表排序后的对象，纵坐标为对应的k - d i s t 值。用户根据排序k d i s t 图确定参数e p s 。在实际操作中，通过这种方法确定的 e p s 与理想的e p s 常有差距，可能造成聚类结果的很大不同。 3 由于在d b s c a n 算法中，变量e p s 、m i n p t s 是全局唯一的，因此当数据 分布不均匀时聚类质量较差。在一般情况下，为减少运算量，可以固定e p s 、 m i n p t s 中任意一个参数的值，而根据需要确定另一个参数的值。若固定m i n p t $ 哈尔滨理工大学工学硕士学位论文 值，根据较密的那些类来选取较小的e p s 值，那么对于客观上相对较稀的那些 类中的对象，他们邻域中的数据对象的数目将可能要小于m i n p t s ，也就是说这 些对象将被认为是噪声点，从而不被用于所在类的扩展。因此较稀的类被分成 多个性质相似的类；与此相反，若根据较稀的那些类来选取较大的e p s 值，那 么离的较近而且密度较大的那些类将很可能被合并为同一个类，他们之间的差 异也就因为选取较大的值而被忽略。很明显，在上述两种情况下，其实很难选 取一个合适的值来进行聚类且得到比较准确的聚类结果。 在图3 3 中，e p s 值的选取即为画出的圆的半径。从图上可以看出，左边圆 内的数据对象分布较稀疏，而右边圆内的数据对象分布较左边圆内数据对象密 集。d b s c a n 算法使用的是统一的全局变量e p s ，如果根据左边数据分布较稀 疏的类c 3 来选取e p s 值( m i n p t s = 7 ) ，那么右边比较靠近的两个类c l 、c 2 就会由 于选取的e p s 值较大而合并成为一个类】。 图3 - 3 根据数据分布较稀的类c l 确定e p s 值 f i g 3 - 3d e t e r m i n ee p sb a s e do nt h ed i l u t ec io f d a t ad i s t r i b u t i o n 同理，在图3 4 中，e p s 值为图中圆的半径( m i n p t s = 7 ) 。选取e p s 时根据数 据分布较密的类a 来确定，这样导致在数据分布较稀疏的类c 2 中的对象p 成 为噪声点俨邻域内的对象个数小于m i n p t s ) ，类c 2 中的其它对象可能会出现 类似对象p 的情况，从而类c 2 被分裂了。 图3 4 根据数据分布较密的类c l 确定e p s 值 f i g 3 - 4d e t e r m i n ef p sb a s e d0 1 1t h ed e n s ec io f d a t ad i s t r i b u t i o n 哈尔滨理工大学工学硕士学位论文 3 4聚类算法的改进 本文提出了依据d b s c a n 算法和k - m e a n s 算法的改进算法，改进步骤 是：首先采用抽样技术优化k - m e a n s 算法并划分数据集：然后根据每个数据集 的情况，分别选取每个局部数据集的m i n p t s i 并进行d b s c a n 聚类；最后合并 各个局部数据集的聚类结果，得到整个数据集的聚类结果。 3 4 1用抽样技术优化k m e a n s 算法 速度和效率是评价数据挖掘技术好坏的两大主要因素。数据挖掘的速度和 效率取决于系统软硬件的运算能力、采用的分析工具和算法、选取数据的方法 以及数据集的特点这几个方面。合理运用抽样技术可以在保证大部分信息不丢 失的同时，提高速度、降低成本，而且由此得出的结论在统计意义上是能够让 人信服的。采用了抽样技术，数据挖掘工作者就可以把精力主要放在建立模 型、选择模型上，而不用把时间浪费在等待系统运算庞大数据的过程中。有时 数据收集过程中的一些原因可能会造成数据库中会存在一部分无关的、过时 的、错误的或者缺省的记录。当然在进行数据挖掘之前应把这部分数据删除掉 或加以修正，即是数据挖掘中的数据清理。对整个原数据进行数据清理也许会 比较因难，比较费时费力，即使有时数据挖掘是直接在已经预处理过的数据仓 库里进行，但为了解决具体的商业问题，根据问题关于数据的一些假设对数据 进行进一步的调整仍是必需的。 在统计学中，简单随机抽样是所有其他抽样方法的基础，但它在大规模的 抽样调查中，很少被单独采用。主要原因是它需要一个对全部基本单元的完整 抽样框，且所得的样本单元相当分散，调查不便。而在数据挖掘技术中，因为 总体的确定性，这样的限制被消除，所以简单随机抽样是数据挖掘技术中最常 用的抽样策略。这种抽样方法简单易行，仅需借助于随机数生成函数并扫描一 遍总体数据集就可以产生样本数据集，它主要可以应用在：( 1 ) 生成用来估计初 始化参数的随机样本：( 2 ) 数据约简生成代表总体数据的样本数据，数据挖掘算 法在此样本数据上挖掘结果。 抽样策略是一种将大数据集的处理任务转化到小数据集上来处理的方法。 它主要是在算法的执行效率和挖掘结果的精确性之间的寻求一种折衷。主要目 的是减少算法扫描整个数据库的规模和次数。抽样方法可以在大大减少数据库 的处理规模的基础上加快算法的速度。m j z a k i 首次给出了单纯在小样本集上 哈尔滨理工大学工学硕士学位论文 获取近似规则的简单随机抽样算法，结果表明：一般只要抽样率达到2 0 一 3 0 ，在样本集上获得的规则就可以很好地近似原始数据库中蕴含的精确规 则。 k - m e a n s 聚类算法需要不断地进行样本分类调整，不断地计算调整后的新 的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。所以需要 对算法的时间复杂度进行分析、改进，提高算法应用范围。本文使用的k - m e a n s 算法是对抽样数据进行聚类，无论是初始点的选择还是一次迭代完成时 对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算 法的收敛速度。 3 4 2确定局部数据集参数m i n p t s i 本文采用以下方法选取各个局部数据集的参数：取一个固定的e p s 值，对 每个局部数据集分别计算m i n p t s i 的值。每个局部数据集的参数m i n p t s i 可由 如下公式( 3 _ 4 ) 确定。 m i n p t s f ：e p sv o l u m e | m ( 3 - 4 ) t o t a l v o l u m e f 其中，是以聚类中心五为中心的局部数据集中数据点的个数； t o t a l v o l u m e i 代表能够包含所有以五为中心的局部数据集的数据点的超长方体的 体积；而e p s v o l u m e 根据所属的不同维数，取值分别为： 一维数据：e p s v o l u m e i = 2x e p s 二维数据：e p sv o l u m e i - - - x e p s z 三维数据：e p s v o l u m e i = 4 3 x x x e p s j 本文中主要在二维空间上进行讨论，故本文所采用的m i n p t s i 的计算公式 如公式( 3 5 ) 所示。 m i n p t s ：j 生m(35)i t o t a l v o l u m e ， 3 4 3合并局部数据集聚类结果 在对整体数据集进行划分时，有可能出现将一个类划分到两个局部数据集 的情况，故应该对得到的局部数据集的聚类结果进行可能的合并，得到最终的 聚类结果。具体合并说明如下： 设点a 、b 分别为类a 和类b 中的点，若满足以下任一条件，则合并类a 哈尔滨理工大学工学硕士学位论文 和类b ： 1 b 从a 关于e p s 和m i n p t , s a 密度可达，而a 从b 关于e p s 和m i n p t s s 密 度不可达，则取m i n p t s = m i n p t s a ，合并类a 和类b ； 2 a 从b 关于e p s 和m i n p t s b 密度可达，而b 从a 关于e p s 和m i n p t s a 密 度不可达，则取m i n p t s = m i n p t s s ，合并类a 和类b ； 3 a 从b 关于e p s 和m i n p t s e 密度可达，同时b 从a 关于e p s 和m i n p t s a 也密度可达，则取m i n p t s = n f m m i n p t s n ，m i n p t s a ，合并类a 和类b 。 聚类合并的各种情况如图3 5 ，图3 击，图3 7 所示。图3 5 所示为数据集 的分布情况。由于本文所提出的改进算法对数据集进行划分，可能将图中数据 点划分到两个局部数据集；而对不同数据集分别进行聚类，可能出现将这个大 的类分成两个类的情况。此时应该对局部数据集的聚类结果进行合并，以避免 将大的类分开的情况发生。图3 5 中的a 、b 两点被划分到不同的局部数据 集，通过局部数据集聚类后，分别属于两个不同的类，点a 所在的局部数据集 所选取的m i n p t s a = 3 ，点b 所在的局部数据集所选取的m i n p t s e = 5 。对于合并的 第一种情况，b 从a 关于e p s 和m i n p t s a 密度可达，如图3 - 6 所示；a 从b 关于 e p s 和m i n p t s b 密度不可达，如图3 7 所示。此时，需要将这两个类合并，从 而避免将较大的类分开，并选取m i n p t s = m i n p t s a 。 图3 - 5 数据分布 f i g 3 - 5d a t ad i s t r i b u t i o n 图3 - 6b 从a 关于e p s 和m i n p t s a 密度可达 f i g 3 - 6d e n s i t yr e a c h i n gf r o mb t oaa b o u te p sa n dm i n p t s 哈尔滨理工大学工学硕士学位论文 图3 - 7a 从b 关于e l m 和m i n p t s b 密度不可达 f i g 3 - 7d e n s i t yn o tr e a c h i n gf r o mat oba b o u te l ma n dm i n p t s e 3 4 4 改进算法的框架 输入：控制参数、聚类数据集 输出：聚类结果 s t e p l ：初始化控制参数，包括：抽样率，k 值，e p s 值； s t e p 2 ：从点集中按抽样率随机选取点集的子集； s t e p 3 ：子集大小为一，对子集进行以下操作： ( 1 ) 选取k 个初始聚类中心刁，j = l 2 ，3 ，j ； ( 2 ) 计算子集中每个数据对象与聚类中心的距离d ( x i , z j ( ) ) ， f = l ，2 ，3 ，刃，户l ，2 ，3 ， ，如果满足： 晰石产i l l i n d 阮石) ，户1 ，2 3 ，刀) 则却； ( 3 ) 确定差平方和准则函数七，如公式( 3 6 ) 所示。 以( ) ：圭兰i 蟛一乙( j ) o z ( 3 6 ) j lk = l ( 4 ) 判断：若l 也( ，) 一以( j 1 ) i 乡，则算法结束；否则i = i + 1 ，计算 七个新的聚类中心，z j ( 1 ) = 亡d ，_ = l ，2 ，返回( 2 ) ； ( 5 ) 将点集中，其余的点加入距离最近的类中，每一类为一个局部数 据集； s t e p 4 ：对于各个局部数据集进行以下操作： ( 1 ) 计算各局部数据集的参数m i n p t s ，m i n p t $ 1 ：! 竺吐m ； 。totalvolume, 哈尔滨理工大学工学硕士学位论文 ( 2 ) 根据e p s 值和m i n p t s f 值，应用d b s c a n 算法进行聚类： s t e p 5 ：合并各个局部数据集的聚类结果； s t e p 6 ：输出聚类结果，算法结束。 3 4 5改进算法的性能分析 k - m e a n s 算法的时间复杂度为d ( n 枷，其中n 指的是总的样本点的个数，k 是指定的聚类数，龌样本点的维数；d b s c a n 整个算法的平均运行时间复杂 度是o ( n l o g n ) ，若不使用空间索引，则计算复杂度为勺；改进算法首先应用 抽样技术得到抽样数据集朋( 设聊= n 2 ) ，然后运行k - m e a n s 算法，时间复杂度为 o ( m 叻，然后在每个划分后的数据集上的时间复杂度为o ( ( n k ) t o 烈n k ) ) ，合并 数据集所用时间复杂度为) ，所以改进的聚类算法总的时间复杂度为o ( m 崩o + k x o ( ( n k ) l o g 【n k ) ) + 0 ( 刀) 。当数据量很大时，改进算法在时间上优于d b s c a n 算法。三种算法时间复杂度比较如图3 8 所示。 图3 8 三种算法的时间复杂度分析 f i g3 - 8t i m ec o m p l e x i t ya n a l y s i so ft h r e 圮a l g o r i t h m s 基于上述的分析，下面对改进算法与一些常用聚类算法从可伸缩性、发现 聚类的形状、对。噪声一的敏感性、对数据输入顺序的敏感性、高维性和算法 效率六个方面进行比较，结果如表3 1 所示。 由表3 1 的比较可以看出，所有聚类算法在某些方面达到数据挖掘对聚类 分析的要求，但是没有哪一种算法是绝对优越的。由于数据挖掘在不同领域的 应用对聚类算法提出了各自特殊的要求，我们可以根据具体的要求选择适当的 哈尔滨理工大学工学硕士学位论文 聚类算法。此外，某些应用可能有特定的聚类标准，要求综合多种聚类技术。 对于中小规模比较均匀的数据聚类，划分方法就可以得到局部最优而且划分 方法在易理解性、易实施性和通用性等方面优于其他的聚类方法。 表3 - 1 聚类算法比较 t a b l e3 - 1t h ec o m p a r i s o no f c l u s t e r i n ga l g o r i t h m 可伸发现聚类对“噪声”的对数据输入顺高维算法 缩性的形状敏感性序的敏感性性效率 c l a r a n s 好凸型或球形不敏感非常敏感 一般较高 a 瓜e 较差任意形状不敏感敏感好较高 b i r c h 较差凸型或球形一股不太敏感 好高 d b s c n 较好任意形状不敏感敏感一般一般 s t i n g 好任意形状不敏感不敏感 好高 c o b w e b 较好任意形状一般敏感好较低 k - m e a n s 较好球形 敏感不太敏感一般一般 s o m 较好任意形状敏感敏感好一般 改进算法较好球形敏感不太敏感 一般较高 由表3 1 的比较可以看出，所有聚类算法在某些方面达到数据挖掘对聚类 分析的要求，但是没有哪一种算法是绝对优越的。由于数据挖掘在不同领域的 应用对聚类算法提出了各自特殊的要求，我们可以根据具体的要求选择适当的 聚类算法。此外，某些应用可能有特定的聚类标准，要求综合多种聚类技术。 对于中小规模比较均匀的数据聚类，划分方法就可以得到局部最优。