（计算机软件与理论专业论文）基于聚类分析的客户生命周期价值挖掘研究.pdf

基于聚类分析的客户生命周期价值挖掘研究 摘要 出 现于2 0 世纪8 0 年代后期的数据挖掘，目 前已 成为知识发现领域中的 一 个研 究热点，也是信息产业界的关注焦点。近年来，国内外学术界和企业界，在对数据 挖掘技术和软件工具的研究和开发上都取得了一 定的成果。 聚类分析是数据挖掘领域中的一种重要方法。聚类是人类一项最基本的认识活 动，通过适当的聚类，事物才便于研究。聚类分析既可以作为 一 个单独的工具以发 现数据库中数据分布的 一 些深入的 信息，也可以 作为其他数据挖掘分析算法的一 个 预处理步骤。聚类分析同时也是一个具有很强挑战性的领域，它的一些潜在应用对 分析算法提出了特别的要求:可扩展性、处理不同数据类型的能力、发现具有任意 形状的聚类的能力、 输入参数对领域知识的最小限度的依赖性、能够处理异常数据 的能力、 数据输入顺序对聚类结果的不敏感性、处理高维数据的能力、基于约束的 聚类以 及聚类结果的可解释性和可用性等。 本文对数据挖掘的相关技术与理论进行了一系列的研究工作，主要的研究集中 在聚类分析， 重点研究了k - m e a n s 算法及挖掘算法在实际中的应用。 主要工作包括: 1 )对聚类算法进行研究产特别研究了 k - m e a n s 这一经典的聚类算法.同时指出了 该算法在算法上及实际应用中的局限性:只有在簇的平均值被定义的情况下才 能使用;对于 “ 噪声”和孤立点数据是敏感的;对初始聚类中心是敏感的等。 2 )针对 k - m e a n s 算法的不足，本论文对其进行了改进，主要的改进在于初始聚类 中心的寻找_ l 。由于k - m e a n s 算法对初始中心点的选择是敏感的，初始中心点 不同，聚类的结果也不相同。针对这种情况，本文给出了一种网格划分的方法 用以寻找初始聚类中心，并给出了基于网格划分的聚类算法 c g k m ( c e n t e r f i n d i n g b a s e d o n g r i d d i n g k - m e a n s ) . 新算法分为两步:第一步是利用网格方法寻找合适的初始聚类中心;第二步是 执行k - m e a n s 算法。 算法首先将m 一 维数据空间的每一维划分为p 等份， 整个数 据空间即被划分为p . 个了立方体。然后计算每一子立方体的密度，也就是落在 立方体中的点的个数，然后按照密度的大小排序。根据要生成簇的个数计算高 基于聚类分析的客户生命周期价值挖抽研究 密度的子立方体的中心点，并将该中心点作为初始的聚类中心。然后在此初始 聚类中心的基础上执行k - m e a n s 算法。 本论文通过随机点和模拟数据两种方式分别对算法进行了验证。 实验结果表明， 新算法能够比 传统算法找到具有更优聚类质量的聚类划分， 且能减少算法的迭 代次数。 3 )根据改进的算法，结合汽车贸易行业的实际情况，设计了面向汽车贸易行业的 数据挖掘模型c l v - m i n e r ( c u s t o m e r l i f e t i m e v a l u e m i n e r ) ，并对客户生命周 期价值进行了挖掘。模型的设计遵循了数据挖掘的建模过程。模型主要包括以 下功能:数据抽取与转换，客户生命周期价值挖掘 ( 根据不同属性组合进行挖 掘，以c g k m 聚类算法作为基础算法) ，并将挖掘结果进行显示。 系统采用了面向对象技术进行设计及开发， 通过j a v a 语言实现，以s q l s e r v e r 为 底层数据库，使用 u ? s 进行数据的抽取、清洗及转换、 加载，建立了数据仓 库，并结合了a n a l y s i s m a n a g e r 建立了o l a p 分析。挖掘的结果以表格、图形 等形式进行了展现。 4 )最后，本文对挖掘算法及挖掘模型的设计进行了总结，以作为将来对汽车贸易 行业数据挖掘模型的进一步设计和研究的基础，同时也为其他行业的数据挖掘 模型的设计和研究提供 一 种思路。 关键字:数据挖掘:聚类;k - m e a n s ;客户关系管理 ( c r m ) ;客户生命周期价值 基于聚类分析的客户生命周期价值挖掘研究 ab s t r act d a t a m in in g , w h ic h d e v e l o p e d in 1 9 8 0 s , h a s b e c o m e a h o t s p o t i n k n o w l e d g e r e s e a r c h a n d t h e f o u c u s o f it . r e s e n t ly y e a r s , a c a d e m ie s a n d b u s i n e s s c ir c le s h a d g o t s o m e f r u it s in t h e r o y s t u d y a n d t o o ls d e v e lo p . c lu s t e r in g a n a ly s is is o n e o f t h e m o s t i m p o r t a n t m e t h o d i n d a t a m in i n g . c l u s t e r i n g i s a b a s ic c o g n it io n o f h u m a n b e in g . t h r o u g h p r o p e r c l u s t e r i n g , w e c a n d is c r i m i n a t e t h in g s e a s ie r . c l u s t e r i n g a n a n ly s is c a n b e t r e a t e d a s a t o o l i n f i n d in g d e e p im f o r m a t io n i n d a t a b a s e , a n d it a ls o c a n b e t r e a t e d a s p r e t r e a t m e n t o f o t h e r t e c h n iq u e s in d a t a m i n in g . c l u s t e r in g a n a ly s is is a c h a lle g e f ie ld , it h a s s e v e r a l d e m a n d s : e x t e n s ib ilit y , a b il ity o f d e a l in g w it h d a t a o f d iff e r e n t t y p e , a b il it y o f f i n d i n g c l u s t e r s w it h r a n d o m s h a p e , m in i m iz e d d e p e n d a b i l it y o f t h e i n p u t e d p a r a me t e r , a b ility o f t r e a t in g a b n o r m a l d a t a , r e s u lt s o f c l u s t e r in g i s in s e n s it iv e t o t h e s e q u e n c e o f t h e in p u t e d d a t a , a b ility o f t r e a t in g m u lt i d i m e n s i o n a l d a t a , c lu s t e r i n g w h ic h b a s e d o n r e s t r ic t io n , e x p la i n a b le a n d u s a b le o f t h e r e s u lt . i n t h e p a p e r , e ff o r t s m a in ly f o c u s o n t h e t e c h n iq u e s a n d t h e o r ie s o f d a t a m in i n g , e m p h s e s a r e o n t h e t h e o r ie s a n d a p p lic a t io n o f t h e k - m e a n s . m u c h r e s e a r c h w o r k s h a v e b e e n d o n e o n t h e r e la t e d t h e o r ie s . t h e k e y c o n t r ib u t io n s a r e m a in ly o n t h e f o l lo w i n g a s p e c t s . s t u d y o n c l u s t e r i n g a lg o r it h m , e s p e c ia l ly o n k - m e a n . i n t h e p a p e r , t h e lim it a t i o n o n t h e r o y a n d a p p li c a t io n o f t h e k - m e a n s h a s b e e n p r e s e n t e d : o n ly c a n b e u s e d w h e n t h e me a n o f t h e c l u s t e r h a d b e e n d e f i n e d ; s e n s it iv e o f n o i s e p o i n t s a n d o u t li n e p o i n t s ; s e n s it iv e t o t h e i n it i a liz e c e n t e r o f t h e c lu s t e r , e t c . a n e w m e t h o d o f f in d in g t h e i n it ia l iz e c e n t e r is f o r w a r d i n t h e p a p e r . b e c a u s e o f t h e k - me a n s i s s e n s it iv e t o t h e i n it i a l iz e c e n t e r a n d t h e i n it i a l i z e c e n t e r i s r a n d o m s e le c t e d , s o w e w ill g e t d iff e r e n t r e s u lt s . we im p r o v e t h e k - m e a n s t h o u g h f i n d i n g a b e tt e r in it ia l iz e c e n t e r w it h g r id d in g , c a lle d c g k m ( c e n t e r f in d i n g b a s e d o n g r i d d in g k - m e a n s ) . we p a rt it io n e a c h d im e n s io n i n t o p p a rt s , s o w e g e t p 基于聚类分析的客户生命周期价值挖掘研究 s u b d i m e n s io n . a n d t h e n , w e c a c u la t e t h e d e s it y o f e a c h s u b d im e n s io n , i n o t h e r w o r d , t h e p o in t s in e a c h s u b d im e n s io n . we s o rt a ll t h e s u b d im e n s io n s i n d e s c e n d in g o r d e r o f d e n s i诊a n d b a s e s o n t h e c lu s t e r n u m b e r w e w a n t t o c r e a t e , w e c h o o s e t h e h ig h e s t a s t h e in it ia l iz e c e n t e r . t h e n w e imp le m e n t s k - m e a n s u s i n g t h e s e i n it ia l iz e c e n t e r s . e x p e r i m e n t s b a s e d r a n d o m p o i n t s a n d t r a in in g d a t a a r e p r e s e n t e d . e x p e r i m e n t s s h o w t h a t t h e n e w a lg o r it h m c a n f i n d a c lu s t e r in g r e s u lt w it h b e tt e r q u a l it y a n d l e s s it e r a t io n s , i n c o m p a r is o n t o t h e t r a d it io n a l a lg o r it h m. i n a d d it io n , w e p u t t h e n e w a lg o r it h m i n t o p r a c t ic e . we p r e s e n t e d a d a t a m in in g m o d e l , c a lle d c l v - m i n e r ( c u s t o m e r l if e t im e v a l u e m i n e r )， w h ic h f a c e t o c a r b u s i n e s s . t h is m o d e l o b s e rv e d t h e p r o c e s s o f d a t a m i n in g , a n d h a s f u n c t i o n s a s f o llo w s : d a t a e x t r a c t io n a n d d a t a t r a n s f o r m a t io n , c l v m i n in g ( b a s e d o n d iff e r e n t a tt r i b u t e s a n d c g k m ) , r e s u lt s p r e s e n t . we d e v e lo p t h is m o d e l t h r o u g h j a v a a n d s o l s e rv e r , u s e d t s a s t h e t o o l o f d a t a e x t r a c t io n , d a t a c le a n i n g , d a t a t r a n s f o r m a t io n a n d d a t a lo a d . we h a d s e t u p a d a t a w a r e h o u s e , a n d o l a p a n a ly s is u s i n g a n a ly s is m a n a g e r . r e s u lt s a r e p r e s e n t e d t h r o u g h e x c e l , g r a p h , a n d s o o n . f in a lly , w e g iv e a s u m m a r iz a t io n o f t h e n e w m e t h o d a n d m i n i n g m o d e l , w h ic h c a n b e t r e a t e d a s t h e b a s is o f f u rt h e r d e s ig n a n d s t u d y . a n d p r o v id a m e t h o d o f d e s ig n a n d s t u d y o f m in i n g m o d e l in o t h e r t r a d e . k e y wo r d s : d a t a m i n in g ; c lu s t e r in g ; k - m e a n s ; c r m; c u s t o m e r l if e t i m e v a l u e l ia n g p e i p e i ( c o m p u t e r s c ie n c e a n d a p p lic a t io n ) d i r e c t e d b y p r o f . y a n g l ip i n g 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文 中除了特别加以标注和致谢的地方外， 不包含其他人或其他机构已经发表或 撰写过的研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作 了明确的声明并表示了谢意。 作 者 签 名 :瓤4q日 期 : i) - to. - 9 论文使用授权声明 本人同意上海海事大学有关保留、 使用学位论文的规定， 即: 学校有权保 留送交论文复印件， 允许论文被查阅和借阅; 学校可以上网公布论文的全部或 部分内容， 可以采用影印、 缩印或者其它复制手段保存论文。保密的论文在解 密后遵守此规定。 作者签名导师签名日期: 基于聚类分析的客户生命周期价值挖掘研究 引言 全球范围内数据库中存储的数据量正急剧增加，数据库系统提供了对这些数据 的管理和简单处理能力，人们可以利用这些数据进行商业分析和科学研究。面对庞 大的数据库，人们的需求已 经不只是简单的查询和维护，而是希望能够对这些数据 进行较高层次的处理和分析以得到关于数据总体特征和对发展趋势的预测。而这些 功能是数据库技术、人工智能和统计学等无法单独完成的。 我们淹没在信息之中， 但仍处 于知 识的 饥渴中 1 。 由 此， 数 据 挖掘技术便应用而生。 数 据挖掘的出 现， 使人 们得以借助计算机的强大的运算能力，从海量的数据中揭示出鲜为人知的规律，从 而对未来进行有限和有效的预测。 近些年来，随着人们生活水平的不断提高，汽车也静静地走进了人们的生活。 汽车贸易公司像雨后春笋般的出现，竞争进入了白热化阶段。面对有限的市场，如 何维系与现有客户的关系、发展潜在客户、扩 一 大市场的份额以提升企业竞争力成为 各汽车贸易公司的首要问题。与客户的关系变得空前的重要。从公司的现有客户信 息中发现不同客户的行为特征， 对市场趋势进行有效的分析， 评估客户价值，为企 业的各种决策提供定性和定量的依据，这对汽贸公司来说无疑是提高企业竟争力的 重要举措。 本论文正是在这样的背景下完成的。本论文得到了北京用友软件集团有限公司 c r m 事业部的红彤汽贸项目的支持， 在深圳红彤汽车贸易有限公司的配合下， 在导师 的指导下， 设计了面向汽车贸易行业的数据挖掘模型c l v - m i n e r 。 模型采用了新的基 于网格划分的聚类算法c c k m ，使用面向对象技术进行分析及设计，以 j a v a 作为开发 语言。 本论文分为七章。第一章介绍了数据挖掘及相关技术;第二章概述了聚类分析 的概念、原理、方法以及其研究的发展方向;第三章对经典聚类算法k - m e a n s 进行 了详细分析， 并提出了新的算法对其进行改进; 第四章主要介绍了c r m 的基础知识; 第五章和第六章重点介绍了客户生命周期价值挖掘模型c l v - m i n e r 的设计和实施， 基于 聚类分析的客户生命周期价值挖倔研究 包括设计方案、系统结构和数据库的分析与设计以及系统的相关开发1 - 作。第七章 给出了全文的总结。 基于聚类分析的客户生命周期价值挖掘研究 第 1 章绪 论 1 . 1 数据挖掘技术的历史与发展 随着数据库技术的不断发展及数据库管理系统的广泛应用， 数据库中存储的数 据量急剧增大。 由于大量数据的可获得性以及把它们转变为可用信息或知识的迫切 需求，在最近十年中， 数据挖掘( d a t a m i n i n g ) 在信息工业中引起了广泛的研究和 应用。 第一届数据挖掘和知识发现会议于1 9 8 9 年6 月在美国底特律召开， 1 9 9 5 年 成为国际会议，至今已召开了七届。第一本关于数据挖掘和知识发现的国际学术 杂志 ( d a t a m i n i n g a n d k n o w l e d g e d i s c o v e r y 于1 9 9 7 年3月创刊。不i司 领域 的研究者都对数据挖掘显示了极大兴趣，许多公司也把它作为提高利润的重要途 径。 数据挖掘是传统统计算法与数据库应用技术的结合和发展，其起源可追溯到二 十世纪五十年代人工智能的早期发展。在此期间， 模式识别和基于规则推理的发展 提供了基础构建块，数据挖掘就是建立在这些概念的基础之上的。 目 前，数据挖掘使用较多的定义:从大量的数据中挖掘出隐含的、未知的、 可能感兴趣的、对决策有价值的知识和规则。一般地，数据挖掘被认为是 k d d ( k n o w l e d g e d i s c o v e r y i n d a t a b a s e ) 中的 一个 重要步骤。图1 . 1 是目 前较为公 认的k d d 的主要过程，数据挖掘是其中最重要的一个步骤之一。 数据挖掘阶段是整个系统的核心部分， 它的主要任务是运用各种算法， 接受人 机交互输入的各种参数，寻找数据仓库中可能的、 潜在的、有价值的概念、规则、 模式、规律或约束，并以各种知识表达的方式表是出 来幻 现今，数据挖掘在生物研究、金融业、零售业、电信业、银行保险业等领域中得到 了广泛的应用。 数据挖掘在客户关系管理( c r m ) 、 供应链管理( s c m ) 和商业智能( b i ) 中的应用正日 益广泛。 由于数据挖掘任务和方法的多样性，数据挖掘语言的设计、高效而有用的数据 挖掘方法和系统的开发、交互和集成的数据挖掘环境的建立以及应用数据挖掘技术 基于聚类分析的 客户生命周期价值挖掘研究 解决大型应用问题，都是数据挖掘研究人员、系统和应用开发人员所面临的主要问 题。 知识 厂 熬 预处理的数据 解/.式 价j翔到一 平尸 江_- 1 数据源 图1 . 1 k d d 过程 1 . 2 数据挖掘与数理统计 数据挖掘与传统的数据统计技术实际上有着干丝万缕的关系， 从某种意义上说， 前者是后者的延续和扩展，它完成了后者所不能实现的任务。统计学和数据挖掘有 很多共同点， 它们有着共同的目 标:发现数据中的结构，但与此同时，它们也有很 多的差异。 数据挖掘是一个 “ 数据驱动”的过程，目的是发掘以前没有被发现或容易被忽 视的有意义的数据模式;而统计学推理规则是以某个假设为开端，然后再利用统计 学的方法来论证或否定这个假设。数据挖掘的目的是建立可以很容易地被转化为新 的商业规则的预测模型，这一点也和统计学有所不同。 数据挖掘的一个显著特点是，它依靠计算机而不是人力来做那些用来建立预测 模型的复杂的数据运算。大量原始数据的分析需要深层次的归纳推理，这部分工作 也是由计算机来完成。推理过程结束后，计算机再按照能为人所理解的格式输出分 析结果。只有通过大量的实例数据集的分析，才能得出比较准确的预测。纯粹的统 基于聚类分析的 客户生命周期价值挖掘研究 计分析要求统计学家与数据集进行大量的引导型交互，从而对做出新的发现产生了 消极的影响。 在数据挖掘领域中， “ 发现” 指的是这样一个过程: 通过扫描整个数据 库，找出数据中隐含的模式。该过程并非对以数据的某种预想甚至假设为前提。换 句话说，程序使用自己的计算能力来发现模式，并不需要用户的任何引导。 计算机 也可以帮助人们发现许多它们平时未曾想到过的模式。正是计算机使数据挖掘与统 计学区别开来。 图1 . 2概要说明了两种汇总的不同之处。 问题 卜暇设 .r “ 、 喊 从 s o l o l a p . 一_ i 口韶 扭 m傲川9 一 之豪 漏 碱一羹 图 1 . 2数理统计与数据挖掘 1 . 3 数据挖掘与数据仓库 数据仓库是一个面向主题的、集成的、时变的、非易失的数据集合， 支持管理 部门的决策过程。数据仓库为商务运作提供结构与工具，以便系统地组织、 理解和 使用数据进行战略决策。 构建数据仓库涉及到数据清理和数据集成，这一过程与数据挖掘中的数据清理 与集成过程相似，如果数据在导入数据仓库时进行了清理，则在数据挖掘过程中无 需再对数据进行清理。因此，数据仓库的建立可看作是数据挖掘的一个重要的预处 理过程。此外，数据仓库提供联机分析处理 ( o l a p )工具，用于各种的多位数据分 析，有利于有效的数据挖掘。 需要指出的是，数据仓库并不是必需的。建立数据仓库的是一个巨大的工程， 需要长时间才能完成。折衷的方法是把一个或多个事务数据库导入到一个只读的数 据库中作为数据集市，然后在其上进行数据挖掘。 基于聚类分析的客户生命周期价值挖掘研究 图1 . 3从事务数据库得出数据挖掘库 1 . 4 数据挖掘与o l a p o l a p 主要是允许客户端设计汇总表用来存储数据， 便于数据的修复和导航. o l a p 可以用来尝试发现新的数据，但因为数据发现的工作实际是由客户端完成的，所以 在o l a p 的协助下的数据发现是比 较局限的， 有偶然性， 不完全。 对于在客户端是否 易于浏览汇总数据，数据挖掘则不太在意，因为它主要是自 动的发现可以应用到预 测未来结果的新的模式和规则的。 鉴于这些区别， o l a p 被认为是 一 种高效的 存储和 修复机制，而数据挖掘是 个 知识发掘工具。 1 一 5 数据挖掘过程 数据挖掘是一个循环往复的过程。 一 个完整的数据挖掘过程包括: 1 .定义商业问题:了解数据和业务问题，定义一个清晰明确的目标。 数据准备:包括数据选择、数据清洗和预处理、数据变换 3 个步骤。 . 数据选择。 搜索所有与业务对象有关的内部和外部数据信息， 并从中选 择出适用于数据挖掘应用的数据。 . 数据清洗和预处理。 研究数据的质量，为进一步的分析作准备， 并确定 将要进行的挖掘操作的类型。 . 数据变换。将数据转换成一个分析模型。 建立模型: 选取数据挖掘工具提供的算法并应用于准备好的数据， 选取相应 参数，生成模型。 评价模型: 对模型进行比较和评估， 生成一个相对最优模型， 并对此模型用 业务语言加以解释。 实施与维护模型: 对模型在实际应用中的表现进行监控， 并对模型作进一步 的考察和修正，以反映业务运作规律的变化。 基于聚类分析的客户生命周期价值挖掘研究 1 . 6 数据挖掘的主要方法 数据挖掘算法将实例从原始数据转换为数据挖掘模型的数学和统计学的算法。 数据挖掘模型最终的形式很大程度上依赖于对数据所应用的数据挖掘算法。数据挖 掘的主 要方法有关联分析、决策树、分类、聚类、时序模式、偏差分析等。 m * m . 洲 戒 v ) 4 4 fm m p j冲( i v *五 玫 蜘 m琴 m wow 图1 . 弓数据挖掘的基木过程和主要步骤 . 关联分析 关联分析的目的是发现特征之间或数据之间的相互依赖关系。数据的相关性代 表了一类重要的可发现的知识。一般用支持度和可信度两个阀值来度量两个元 素间的相关性。 . 分类与 预测 分类就是找出一个类别的概念描述，它代表了 这类数据的整体信息，即该类的 内 涵描述，并用这种描述来构造模型，一般用规则或决策树模式表示。分类是 利用训练数据集通过一定的算法而求得分类规则。分类可被用于规则描述和预 测。 预测是利用历史数据找出变化规律，建立模型，并由此模型对未来数据的种类 及特征进行预测。预测关心的是精度和不确定性，通常用预测方差来度量。 . 聚类分析 聚类是根据数据的不同 特征，将其划分为不同的数据类。它的目的是使得属于 同一类别的个体之间的距离尽可能的小，而不同类别上的个体间的距离尽可能 的大。 . 时序模式 时序模式是指通过时间序列搜索出的重复发生概率较高的模式。时序模式通过 墓于聚类分析的客户生命周期价值挖掘研究 历史的和当前的数据推测未来的数据，也可认为是以时间为关键属性的关联分 析。 . 偏差分析 偏差分析的基本思想是寻找观察结果与参照量之间的有意义的差别。通过发现 异常，可以引起人们对特殊情况的加倍注意。 基于 聚类分析的客户生命周期价值挖掘研究 第z 章聚类分析概述 将物理或抽象对象的集合分组成有相似的对象组成的多个类的过程被称为聚 类。聚类是人类一项最基本的认识活动。通过适当的聚类，事物才便于研究，事物 的内部规律才可能为人类所掌握。 本章简要的介绍了聚类分析的概念与典型应用，以及卞要的聚类方法。 2 . 1 聚类分析的概念与用途 聚类分析 ( c l u s t e r i n g a n a l y s i s ) ，又称聚类，是一种广泛应用于k d 。 与数据 挖掘的分析手段。它是这样一个过程，即，按照事物的某些属性，将事物分成多个 类或簇，使得在同一类中的事物相似性尽量大，不同类间的事物相似性尽量小。 聚类作为 一 种非监督型的知识发现方法，不需要任何事先的训练数据，而仅仅 按照相似性原则，将一 组数据划分为事先未知的分类状态，因而是一 种有效的、得 到广泛应用的识别与发现未知模式的几种有效方法之 一 。 聚类分析是人类认识世界的重要方式，人早在婴幼儿时期，就开始通过不断地 改进潜意识中的分类主题学习如何区分猫和狗、区分动物与植物等。虽然人们可以 凭经验和专业知识实现分类， 但聚类分析作为一种定量方法，从数据分析的角度给 出了一个更准确的分类工具。目 前，聚类分析己经被广泛的应用于各个数值分析领 域，包括模式识别、数理统计、图像处理以 及市场分析等。在商业上，聚类分析可 以帮助市场分析人员根据客户消费模式对客户进行分类，发现不同类别客户的消费 偏好和特点，从而进行有针对性的服务和广告宣传。在生物学上，聚类能用于推导 植物和动物的分类，对基因进行分类，获得对种群中固有结构的认识。在天文学、 地理学以及文本挖掘等方面，聚类分析也有大量的应用。聚类分析己经成为数据挖 掘研究领域中一个非常活跃的研究课题。 近年来， 聚类作为一种基本的数据挖掘方法被广泛地应用于相似搜索、 顾客划 分、模式识别、趋势分析等领域中。例如，在超市中，把经常被同时购买的商品 基于案类分析的客户生命周期价值挖掘研究 项聚类到一起有利于改善商品的布置，提高销售利润。在电子商务的每天的日常 业务中，网上商店的 w e b服务器自 动收集并存储了网上客户的对商品的购买、浏 览倾向， 对不同类别的客户群分析其可能的兴趣特点和购买方式。在信息检索领 域中，聚类分析对文档进行分类，改善信息检索的效率，或者发现某一领域文献 的组成结构。在医疗分析中，通过对一组新型疾病聚类，得到每类疾病的特征描 述，就可以对这些疾病进行识别，提高治疗的功效。 2 . 2 聚类分析的原理与方法 聚类问题不是一个新提出的问题，对它的研究已有相当长的历史。早在 1 9 6 3 年， 由r o b e r t s o k a l 和p e t e r s n e a t h 合著的 p r i n c i p l e s o f n u m e r i c a l t a x o n o m y ) 一书对聚类的研究起了很大的推动和促进作用。 目 前，研究主要集中在基于距离的聚类分析。主要的聚类算法可以划分为 5大 类:基于划分的方法 ( p a r t i t i o n i n g m e t h o d ) ,基于层次的方法 ( h i e r a r c h i c a l m e t h o d ) , 基于密度的方法( d e n s i t y - b a s e d m e t h o d ) , 基于网格的方法( g r i d - b a s e d m e t h o d ) ,基于模型的方法 ( m o d e l - b a s e d m e t h o d ) . 2 . 2 . 1 基于划分的方法 划分算法的共同特点是聚类数目 给定， 即在己知聚类数目k 和目标函数r 的情 况下，把一组数据对象 d 划分成 k 个类，使得目 标函数在此划分下达到最优。划 分算法往往把聚类问题转化成一个组合优化问题，从一个初始划分或者一个初始 聚点集合开始，利用轮流部分优化的策略进行迭代计算，最终优化目标函数。最 常 用 的 目 “ 函 ” 是 客 咖 d (x;,m ) ， 即 所 有 数 据 对 象 “ 其 最 近 的 聚 类 中 心 的 距 “ 之 和。 8 0年代初， m i c h a l s k i 提出了概念聚类的技术，不仅考虑数据间的距离， 还 要求划分得到的类具有某种共同内涵。 k - m e a n s 聚类算法自 提出以后便成为一种经典， 并由之演绎出了系列的其它聚 类算法模型， 如k - m e d o i d s 算法， k - m o d e s 算法， k - p r o t o t y p e s 算法以及各个模型 对应的模糊聚类算法等。其中， k - m e a n s 算法能够很好的解决给出数值型属性的数 基于聚类分析的客户生命周期价值挖掘研究 据对象的聚类问题: k - m e d o i d s 算法是 k - m e a n s 的特殊情况， 要求聚类中心是某一 个数据对象:k - m o d e s算法根据数据对象的分类型属性对数据对象进行聚类; k - p r o t o t y p e s 算法则将分类型属性和数值型属性联合起来考虑， 共同组成聚类函数 的两个部分，给出了同时考虑混合型属性的聚类算法。 亦相当名的情n . 下。聚半问颗的最终聚类数目 可能是未知的， 这时， 确定聚类 的 数 目 就 是 聚 类 问 题 的 另 外 一 个 重 要 的 内 容 。 “ 口 果 仍 采 用 万 m in d (x ;,m ,-f ;-,， 作 为 目 标 函数，那么聚类的结果将是 n个聚集，每个单个点就成为一个类，目 标函数的值 为0 。 这显然不是希望的结果。 一般的处理方式是在目 标函数中增加 一 项或多项与 聚类数目正相关的成本项，从而遏制聚类数目增加所带来的目 标函数值总体降低。 由此提出了在定义点对聚类中心的隶属系数之外，还定义邻居系数，并由之在日 标函数中增加 一 项与聚类数目 正相关的成本项的方法，以及以控制类直径的一种 方式来获取聚类的最优数目的方法。 2 . 2 . 2 基于层次的万法 层次聚类算法是传统的处理聚类数目未知情况下的聚类方法。包括分裂式层次 聚类法和聚合式层次聚类法。其中，分裂式层次聚类法是将所有数据对象整个作为 一个聚类，然后按照使目 标函数值最优的原则将其拆分为两个聚类，之后选择聚类 直径最大的类再次按照同样的原则进行再次拆分，直至目标函数值不再降低为止。 聚合式层次聚类则相反，首先将所有的数据对象都各自 作为一个类，然后按照使目 标函数值最大降低的原则合并两个聚类，之后反复不断合并最适合的两个聚类直至 目 标函数值不再降低为止。层次聚类的结果可以用一个二分树表示，树中的每个节 点都是一个聚类，下层的聚类是上层聚类的嵌套，每一层节点构成一组划分。具有 代表性的层次方法有c u r e . c h a m e l e o n 和b i r c h . 2 . 2 . 3 基于密度的万法 为了发现任意形状的聚类结果，提出了基于密度的方法。这类方法将簇看作是 数据空间中被低密度区域分割的高密度对象区域。 基于密度的方法根据邻域对象的 基于 聚类分析的客户生命周期价值挖掘研究 密度，或者根据某种密度函数来生成聚类。对给定类中的每个数据点，在 1 个给定 范围的区域中必须至少包含某个数目的点。 一o sb ep l step兰p 3 sw p a epi i i i -i- 0、 、 护 前 、 iq 少 一- 牛 g ap 4 1 4 告 e p ， s p七可，俩一 川 ，ld ” 图2t聚合和分裂层次聚类 2 . 2 一 44 基于网格的方法 基于网格的方法把对象空间量化为有限数目 的单元，形成了一个网格结构。所 有的聚类操作都在这个网格结构 ( 即量化的空间)上进行。这种方法的主要优点是 处理速度快，处理时间与数据对象的个数无关，依赖的是量化空间中每一维上的单 元数目。有代表性的算法包括s t i n g , c l i q u e 和w a v e c l u s t e r a 2 . 2 . 5 基于模型的方法 基于模型的方法试图优化给定的数据和某些数学模型之间的适应性。它为每个 簇假定了一个模型，寻找数据对给定模型的最佳拟合。一 个基于模型的算法可能通 过构建反映数据点空间分布的密度函数来定位聚类。主要的方法有统计学方法和神 经网络方法两种。 2 . 3 聚类研究的发展方向 聚类问题作为一个古老而时下热门的问题，其研究和应用的相关文献已经不计 其数。其它最新的主要的有关研究方向还有: . 算法的规模性研究: 侧重于面向大量数据的聚类算法。 许多经典的聚类算法 在少量数据的时候具表现出良好的执行性能， 而当面对海量数据时却几乎是 基于 聚类分析的客户生命周期价值挖掘研究 不可用的。 混合属性类型的聚类算法研究: 卞要研究如何处理多种数据类型混合状态下 的聚类算法。如数值型、分类型、二值型、文木型、图像型等数据类型。 聚类算法抵抗噪声的研究: 现实数据库往往都是含有噪声或者错误数据信息 的， 这类问题主要研究如何增强聚类算法的容错能力， 以及降低聚类结果对 单个数据对象的敏感程度。 基于约束条件下的聚类问题: 增强聚类算法的实际应用性能， 使之能够考虑 更多的实际约束条件。 聚类问 题与其他研究领域的交叉综合研究:一 方面将聚类的理论与方法应用 到其它优化领域，同时也借助其它优化理论的方法来解决聚类问题的课题， 如遗传算法、退火算法在聚类问题中的应用等。 基于 聚类分析的客户生命周期价值挖掘 研究 第3 章c g k m 算法- 一对 k - m e a n s 算法的改进 k - m e a n s 算法是 一 种经典的基于划分的聚类方法。 本章对k - m e a n s 算法的优缺点 进行了分析， 并对其进行了 改进， 给出了基于一种网格划分的聚类算法c g k m ( c e n t e r f i n d i n g b a s e d o n g r i d d i n g k - m e a n s ) ,且 与传统的k - m e a n s 算法进行了比 较。 3 . 1 k - m e a n s 算法原理及其优缺点 对于已知聚类数目的聚类算法，通常的目 标函数是使所有数据对象与距其各自 所属聚类中心的距离之和最小。例如，将n 个数据对象划分为k 个聚类，目 标函数 一般为: ，z，) f (w ,z ， 一 著 w r d (x ; 其中z , , l = 1 , 2 , .二 ， k 是 聚类中 心: k 是 给定的 聚 类数目 : ws为 权重函 数， 描 述了 数 据 对 象x 对 聚 类中 心z ， 的 隶 属 程 度。 当w r. 取 值为1 或。 ， 即当 %= 1 时 表 示x 隶 属于 z , , 否 则 不 属 于 ， 这 是 的 聚 类 称 为 硬 聚 类. 当 w y 的 取 值 介 于 连 续区 间 0 , i 之 内 时， 称 为 模 糊 聚 类， w e 用以 描 述 数 据 对 象x 对 聚 类中 心z ， 连 续的 隶 属 程 度。 k - m e a n s 聚类算法是最常用的划分方法之一。 k - m e a n s 聚类分析的主要特征是可 以根据需要预先确定目 标聚类的数目k 。根据选定的 k 值，聚类可以产生两个完全 极端的结果: k = 1 , 得到一个没有意义的结果， 因为所有的数据会归类到一个节点中; 另一个极端是 k = n ，即实例集中记录的个数，同样也会得到一个毫无意义的结果。 任何其他的聚类个数取决于k 的值。 对于k 值的选取没有一个固定的快速规则可循， 通常一个比较理想的方法是对各种值进行试验。 k - m e a n s 算法的处理流程如下。 首先， 随机地选择k 个对象， 每个对象初始地代 表了一 个簇的平均值或中心。对剩余的每个对象，根据其与各个簇中心的距离，将 它赋给最近的簇。然后重新计算每个簇的平均值，平均值的计算方法一般为 基于聚类分析的客户生命周期价值挖掘研究 :，一 担 ， ，一 1,2,.,k 馨 w s 这个过程不断重复，直到准则函数收敛。如图 3 . 1 。通常收敛准则采用平方误差准 则 川 ， 定 义 如下 : e 一 i j- l j 、 ! ; 一 m ; !， 这里的e 是 数据库中 所有对象的平方误差的总和， p 是空间中的点，表示给定的数 据对象，m是簇c的平均值 ( p和m . 都是多维的) 。这个准则试