（管理科学与工程专业论文）基于粗糙集的决策树算法研究及在crm中的应用.pdf

基于粗糙集的决策树算法研究及在c r m 中的应用 摘要 数据挖掘是一种能够从海量数据中提取有价值信息的技术。它可用于 发现隐藏在数据中的聚类模式、关联模式、分类模式等，以辅助人们决策。 其中，分类是数据挖掘的一项重要任务，而决策树就是一种能有效用于数 据分类的方法。决策树结构简单、容易产生规则、易于理解，在实际中应 用极为广泛。 首先，本文基于粗糙集理论改进决策树算法。先利用粗糙集理论进行 决策表的属性约简，再进行基于粗糙集的决策树构建。经典粗糙集存在着 处理噪声数据能力差的不足。为此，本文基于变精度粗糙集的思想对蒋芸 博士等( 2 0 0 4 ) 提出的决策树算法进行改进，提出变精度加权平均粗糙度的决 策树构造算法。实验结果表明改进后算法构造的决策树结构简洁，泛化能 力更强。 其次，本文还将提出基于属性区分度的决策树构造算法。其主要思想 是决策树的每一次分枝都尽可能使属于不同决策类的数据分开，而使属于 同一决策类的数据集中在一起。同样，仿真实验结果表明该算法在多数数 据集上构造的决策树比经典的i d 3 算法要好。 最后，本文以电信业客户关系管n ( c r m ) 为背景，基于数据挖掘的基本 流程，在一个电信客户流失数据集上分别以i d 3 算法以及本文改进和提出 的决策树算法构建一个客户流失预警模型。模型结果比较表明后两者构建 的模型均优于前者。 关键词：数据挖掘粗糙集决策树c r m客户流失 t h er e s e a r c ho nd e c i s l 0 nt r e ea l g o r i t h mb a s e d o nr o u g hs e ta n da p p l i c a t l o ni nc r m a b s t r a c t d a t am i m n gi sak i n do ft e c h n o l o g yt h a tc a l le x t r a c tt h ev a l u a b l ei n f o r m a t i o nf r o mt h e m a s s i v ed a t a i tc a nb eu s e dt of i n dt h ec l u s t e rp a t t e r n ，t h ea s s o c i a t i o np a t t e r n , a n dt h e c l a s s i f i c a t i o np a t t e r n ，h i d d e ni nt h ed a t a , i no r d e rt oh e l pp e o p l ed e c i s i o n m a k i n g t h e c l a s s i f i c a t i o ni sa l li m p o r t a n tt a s ko fd a t am i n i n g ，a n dt h ed e c i s i o nt r e ei sam e t h o du s e d e f f e c t i v e l yf o rd a t ac l a s s i f i c a t i o n t h es t r u c t u r eo f t h ed e c i s i o nt r e ei ss i m p l e t h ed e c i s i o n t r e ei se a s yt op r o d u c er u l e sa n dt ob eu n d e r s t o o d i ti su s e dw i d e l yi np r a c t i c a la p p l i c a t i o n s f i r s t l y , t h i sp a p e ri m p r o v e st h ed e c i s i o nt r e ea l g o r i t h mb a s e do nr o u g hs e tt h e o r y b a s e d o nr o u g hs e tt h e o r y , i tr e d u c e sa t t r i b u t e so ft h ed e c i s i o n - m a k i n gt a b l ea n dt h e nc o n s t r u c t st h e d e c i s i o nt r e e t h ec a p a c i t yo f h a n d l i n gt h en o i s ed a t ab a s e do nc l a s s i cr o u g h s e ti si n s u f f i c i e n t t h e r e f o r e ，b a s e do nt h ev a r i a b l ep r e c i s i o nr o u g hs e tt h i n k i n g ，t h i sp a p e rp r o p o s e st h ed e c i s i o n t r e e a l g o r i t h mb a s e do nt h e v a r i a b l ew e i g h t e da v e r a g er o u g h n e s s ，w h i c hi m p r o v et h e a l g o r i t h m sp r e s e n t e db yd r j i a n gy u n e ta l ( 2 0 0 4 ) t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h e d e c i s i o nt r e eb a s e do nt h ei m p r o v e da l g o r i t h mi ss i m p l e ri nt h es t r u c t u r ea n di t se x t e n s i v e a b i l i t yi ss t r o n g e r s e c o n d l y , t h i sp a p e rw i l lp r e s e n td e c i s i o nt r e ea l g o r i t h mb a s e do nt h ed i s c e r nd e g r e eo f a t t r i b u t e s t h em a i ni d e ai sd u r i n ge v e r yb r a n c ho ft h ed e c i s i o nt r e et h ed a t ab e l o n gt o d i f f e r e n tc a t e g o r i e ss e p a r a t ea sm u c ha sp o s s i b l ea n dt h ed a t ab e l o n gt ot h es a m ec a t e g o r i e s p o o lt o g e t h e ra sm u c ha sp o s s i b l e s i m i l a r l y , s i m u l a t i o nr e s u l t ss h o wt h a ti nm o s td a t as e t s t h i sd e c i s i o nt r e ea l g o r i t h mi sb e t t e rt h a nt h ec l a s s i ci d 3a l g o r i t h m f i n a l l y , 而mt h ec 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 nt e l e c o m m u n i c a t i o n s i n d u s t r ya st h eb a c k g r o u n d ，t h i sp a p e rb u i l d st h ec h u mo fe a r l yw a r n i n gm o d e l s ，b a s e do nt h e b a s i cd a t am i n i n gp r o c e s s t h e s em o d e l sa r eb u i l tb a s e do nt h ei d 3a l g o r i t h ma n dt h e a l g o r i t h m st h a tw ei m p r o v ea n dp r e s e n ti nac h u mo ft e l e c o md a t as e t t h er e s u l ts h o w st h a t t h em o d e l sc o n s t r u c t e dw i t ht h e1 a t t e rt w oa l g o r i t h m sa r eb e t t e rt h a nt h ef o r m e r k e yw o r d s ：d a t am i n i n g ；r o u g hs e t ；d e c i s i o nt r e e ；c r m ；c u s t o m e r sc h u m 广西大学学位论文原创性声明和使用授权说明 原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相 关知识产权属广西大学所有，本人保证不以其它单位为第一署名单位发表或使用本论文 的研究内容。除已注明部分外，论文中不包含其他人已经发表过的研究成果，也不包含 本人为获得其它学位而使用过的内容。对本文的研究工作提供过重要帮助的个人和集 体，均已在论文中明确说明并致谢。 论文作者签名： ，乞 、 易 学位论文使用授权说明 僻石月z 汨 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本： 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 函口时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：扳、7 易导师签文差戽少口挣z 月丫日 基于粗事t 集的决策树算法研究及在c r m 中的矗l j 罚 1 1 选题的背景和意义 第1 章绪论 信息时代，数据如海。 我们正被数据所淹没。当前随着信息技术的发展，数据自动收集工具和数据库技术 逐渐成熟以及存储数据的成本不断降低，各行各业积累了大量的关于自身和生存环境数 据。在超市，顾客的购物选择会被超市数据库所记录；在银行，客户的个人理财习惯被 存储记录；而在互联网上，用户所做的每一次点击链接也都会被记录。随着企业信息化 的日益普及，企业中存储的数据随着时间的推移会不断积累。数据泛滥或信息爆炸已经 成为当今信息化社会面临的巨大挑战。传统的数据库管理系统( d b m s ) 虽然可以实现高 效的数据录入、查询、统计等功能，却无法发现数据中隐含的关系和规则，不能给相关 部门的决策者们提供有效的、可供支持决策的信息。这样，面对如此大量或者说海量的 数据，人们往往陷入“数据爆炸而知识贫乏 的困境。为了能够走出这种困境，我们迫 切需要一些有效的方法将这些数据转换成对我们有用的知识，进而辅助我们决策。“需 要是发明之母 正是在这种需求动力下，2 0 世纪9 0 年代以来出现了一种融合多种学科 知识的新学科数据挖掘。 数据挖掘就是从大量的、有噪音、纷繁复杂的数据中，提炼和发现蕴含在其中、人 们事先不知道，但又有潜在价值、能够提高决策或管理效益的信息、知识或规律的过程 1 1 。它融合了多个领域的理论和技术，包括数据库、人工智能、机器学习、统计学等。 数据挖掘是一种用于信息资源开发的数据处理新技术，是一种决策支持的新手段。 数据挖掘的核心部分是为数据建立模型的过程，不同的数据挖掘方法构造数据模型 也不相同。总的来说，数据挖掘主要集中在分类、聚类、关联规则挖掘、序列模式发现、 异常和趋势发现等方面，其中分类挖掘在商业等领域中的成功应用使它成为数据挖掘中 最活跃、最成熟的研究方向。分类算法也是数据挖掘中最重要的技术之一，是数据挖掘 中的一个重要课题。分类的目的【2 】就是学会一个分类函数或分类模型( 也常常称为分类 器) ，该模型能把数据库中的数据项映射到给定类别中的某一个。 分类模式在现实商业应用中有着重要的实用价值。一个目录邮递公司需要根据客户 历史数据开发一个客户响应模型，把商品目录邮递到购买其商品可能性大的顾客手中， 基于囊l 犍集的决策树算法研究及在c r m 中的应用 以避免大量无目的投放商品目录，耗费营销成本。而对于一个电信企业面临的一个重要 的问题就是客户流失的问题，所以几乎每一家电信公司都正在或即将建立客户流失预警 模型。根据历史客户流失数据建立流失预警模型，转换出一定的分类规则，用以对现有 客户数据进行分类，发现流失可能性大的客户，并采取一定的方法进行客户挽留，从而 提高企业的竞争力。银行信用卡业也同样需要分类技术建立信用评分模型。当一个新的 客户提出信用卡申请时，通过模型可以得到该客户风险类型，以辅助决策是否对其发放 信用卡。通过应用模型提高了信用卡公司的运营效率，同时也帮助其控制风险。 常见的用于分类的方法有决策树、神经网络、支持向量机、k 小、贝叶斯分类、 l o g i s t i c 回归、粗糙集等等。在众多分类算法中，决策树算法以其简单、易于被人理解的 特点而被人们广泛接受。决策树方法从其产生以来，先后出现了许多算法，包括i d 3 、 c 4 5 、c 5 0 、c a r t 、c h a i d 、s l i q 、s p i n t 等。它们都采用自顶向下的递归方式进行 属性值的比较并根据不同值判断从该节点向下分支，在决策树的叶子结点得到结论。决 策树从根到叶子节点的一条路径就对应这一条合取规则，整棵树对应这一组析取表达式 规则。人们对决策树算法的研究与改进一直是一个热点。近年来，很多研究者提出许多 基于其他软计算方法构造决策树的优化算法，比如神经网络、遗传算法、粗糙集、模糊 集等，以寻求更好的决策树分类规则。基于此，本课题主要研究基于粗糙集构造决策树 的方法，并将决策树分类算法应用到电信业的客户关系管理( c i m i ) 中建立模型。 1 2 研究的历史和现状 最早的决策树学习系统要追溯到h u n t 、m a t i n 和s t o n e 于1 9 6 6 年研制的一个概念学 习系统( c o n c e p tl e a r n i n gs y s t e m ) c l s 3 1 ，该系统第一次提出使用决策树进行概念学习。以 后的许多决策树算法都是对c l s 算法的改进或由c l s 衍生而来。 1 9 8 6 年j rq u i n l a n 提出了当前国际上最有影响的示例学习方法1 1 9 3 算法【4 】，它的 主要工作是引进了信息论中互信息的概念，q u i n l a n 将其称之为信息增益( i n f o r m a t i o n g a i n ) ，i d 3 选择信息增益值最大的属性划分训练样本，其目的是进行分裂时系统的熵最 小。但是i d 3 算法的主要缺陷是，用信息增益作为分裂属性选择标准时，有偏向于取值 较多属性的毛病，而在有些情况下，这类属性可能不会提供太多有价值的信息。 1 9 9 3 年q u i n l a n 对i d 3 算法进行了改进和补充，提出了后来非常流行的c 4 5 算法【5 】。 c 4 5 不仅可以处理离散值属性，还能处理连续值属性。c 4 5 采用了信息增益比率作为 2 广西大掌硕士学位论文基于毫l 奉t 二的决策树算法习阳宅及在c r m 中的量u 景 选择分裂属性的标准，弥补了i d 3 的不足。 19 8 4 年b r e i m a n 等人提出c a r t ( c l a s s i f i c a t i o na n dr e g r e s s i o nt r e e ) 算法【6 】，该算法 生成的决策树是一棵二叉树。在测试属性选择上，c a r t 基于的选择标准是g i n ii n d e x 。 另外一种典型的决策树算法是c h i a r d t 7 ( s q u a r e da u t o m a t i ci n t e r a c t i o nd e t e c t o r ) 。它采用 统计学中的卡方统计量作为属性选择标准构造决策树，该方法在建树前连续属性必须先 作离散化处理。 以上几种方法只适用于较小规模的数据，而在大型数据库中往往性能不佳。针对海 量数据集上的数据挖掘任务，决策树算法的有效性和可伸缩性成为值得关注的问题。 i b ma l m a d e n 研究中心开发ys l i q t 8 和j o h ns h a f e r 等人s p r i n t 9 】算法，分别使用了不同 的数据结构，使算法具有良好的伸缩性，能够在非常大的训练样本集上进行决策树归纳 学习。 上述六种决策树算法都是目前比较典型的方法。一直以来，很多研究人员尝试在控 制树的大小和简化决策树等方面做出努力，通过研究各种前剪枝算法和后剪枝算法来控 制树的规模，同时在修改测试属性空间、改进测试属性选择方法、限制数据集、改变数 据结构等方面提出了许多新的算法和标准【1 0 1 9 1 。 近年来，如何将决策树和新兴的技术相结合以取长补短成为决策树研究的热点，在 国际上发表的的有关决策树的文章也大都集中在这几个方面的研究。主要包括【2 0 】：决策 树技术与神经网络技术相结合，决策树技术与模糊集合原理相结合，决策树技术与进化 算法、遗传算法及遗传编码的结合，决策树技术与粗糙集理论结合等。 粗糙集理论是z p a w l a k 教授 2 1 】于1 9 8 2 年提出来的，它是一种新的处理模糊和不确定 性知识的数学工具。目前，许多研究者提出了基于粗糙集理论的决策树构造算法 2 2 - 3 s 】。 s o n a j h a r i am i n z 2 2 1 、吴成东【2 3 1 、吴艳艳【2 4 】等提出了结合粗糙集理论最为直接的一种方法， 即首先基于粗糙集进行属性约简，再利用其他传统的方法构造决策树。另外有基于粗糙 集的增量式决策树【2 5 1 。而更多的是基于粗糙集理论选择决策树构建过程中的分裂属性。 2 0 0 1 年卫金茂 2 6 2 7 】在其博士论文中提出基于粗糙集的h a c r s 算法，该算法选取决策属性 相对于每个条件属性的为明确区( h 口i e 域) 最大的属性作为分裂属性。2 0 0 3 年蒋芸等人【2 8 】 提出以加权平均粗糙度作为属性选择标准构造决策树的算法。2 0 0 4 年管红波、田大纲【2 明 提出基于粗糙集中属性重要度构造决策树提取规则。2 0 0 5 年赵翔、向一丹等人【3 0 】利用粗 糙集中近似分类质量的概念，选取其最大的属性作为分支节点，在本质上和卫金茂的方 法是一致的。2 0 0 5 年乔梅掣3 1 】提出了一种新的属性选择标准：属性分类粗糙度。它全面 3 基于粗糙集的决策树算法司晒巴及在c r m 中的应用 地刻画了条件属性与决策属性的相关性，它不仅反映了属性可鉴别对象的多少，而且反 映了等价类中对象所属决策类数及偏向性。2 0 0 6 年关晓蔷【3 2 】选取根据条件属性，决策属 性的近似分类精度最大的属性作为分裂属性选择标准。针对明确区的概念是一种精确的 集合包含关系，2 0 0 5 年王名扬、卫金茂等人【3 3 。3 5 1 提出变精度明确区作为属性选择的标准。 2 0 0 6 年常志玲等人【3 6 】提出变精度分类质量作为属性选择标准。这两种方法允许决策中存 在一定的误差，但却能够使生成的决策树将一些小规模特性化的实例划入大规模的实例 中，从而弱化这些少数实例对决策树造成的不良影响，最终生成的决策树也比较简洁， 泛化能力更强。 最后值得注意的是，苗夺谦3 7 1 、x u m i nl i u 【3 8 】等提出基于粗糙集构造多变量决策 树。该方法先找出条件属性对于决策属性的核，选择核中的属性作为构造多变量检验的 属性，并且多变量检验并不是被选属性的简单合取，而是由它导出一个新的属性。 1 3 论文的组织结构 第一章绪论。简要介绍了论文所研究课题的背景和意义，本课题研究的国内外现 状，以及本论文的组织结构。 第二章数据挖掘和客户关系管理。本章前半部分主要介绍了数据挖掘的基本理论， 包括数据挖掘的概念、流程、任务和常见的几种数据挖掘算法；而在本章后半部分则简 要介绍了客户关系管理( c 蹦) 的基本含义，以及数据挖掘在客户关系管理中的应用。 第三章相关理论介绍。分两部分分别介绍了粗糙集和决策树的基本理论。 第四章基于粗糙集的决策树构造算法改进。首先基于粗糙集属性约简决策表，然 后基于变精度粗糙集模型改进了基于加权平均粗糙度构造决策树的算法，使生成的决策 树简洁、泛化能力强。 第五章一种基于属性区分度的决策树构造算法。提出一种新的基于属性区分度的 决策树构造算法，并仿真实验验证其有效性。 第六章决策树在电信客户流失管理中的应用。本章将以电信业为背景，按照数据 挖掘基本流程，在一个电信数据集上构建决策树模型，初步说明决策树在电信业客户流 失管理中的应用。 结束语概括了本文所做的工作与存在的不足，提出迸一步研究的方向i 4 墓于粗犍集的决策树算法研究及在c i 瑚中的应乙用 2 1 数据挖掘理论 第2 章数据挖掘与客户关系管理 2 1 1 数据挖掘的概念 数据挖掘( d a t a m i n i n g ) 是从大量的、不完全的、有噪声的、模糊的、随机的数据中， 提取隐含在其中、事先未知、但又潜在有用的信息和知识的过程，从中发现模型和数据 间关系的过程，用其做出预测【3 9 1 。它是通过分析数据发现内部信息和知识的过程。 数据挖掘的定义包括几层含义：数据源必须是真实的、大量的、含噪声的；发现的 知识是用户感兴趣的知识；发现的知识要可接受、可理解、可运用；不要求发现所有准 确定义的知识，仅支持特定的发现问题。 数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的简单查询，提升到从 数据中挖掘知识，提供决策支持。 2 1 2 数据挖掘的过程 数据挖掘是一个反复迭代的人机交互处理过程。可以大致的分为四个阶段：问题定 义、数据准备、数据挖掘、模型解释及评估。其具体过程见下图2 1 。 lli l i _ - - - - l - - _ - - l _ - _ - l _ _ 图2 - 1 数据挖掘过程 i i 一土 f i g 2 - 1d a t am i n i n gp r o c e s s ( 1 ) l h - j 题定义 这是数据挖掘的第一步，清晰地定义出业务问题，明确数据挖掘的目的。只有确定 了分析的目的才能提取正确的数据，选择合适的方法。这个过程建立在对企业的业务知 识充分理解上，所以数据挖掘人员必须不断地与企业中熟悉业务知识的人员沟通，了解 其具体的业务需求，最终明确该数据挖掘项目实施的目的。 资料来源：李雄飞，李军数据挖掘与知识发现北京：高等教育出版社，2 0 0 3 5 基于老l 糙集的决策树算法研究及在c f 瑚中的应用 ( 2 ) 数据准备 这个过程包括数据选取、数据预处理、数据变换三个子过程。 数据选取是根据用户的需要从原始数据库中抽取一定的数据形成目标数据； 数据预处理是对目标数据检查其数据一致性，消除孤立点以及重复的记录，运用 一些特定的方法填补缺值数据等； 数据变换主要包括：派生新变量，通过概化、比率、日期等生成一些新变量；变 量归约( 降维) ，采用主成分分析或粗糙集中的属性约简等方法对数据进行降维处理；开 发预测性较强的变量，在作预测性模型时通常对变量转换，使转换后的变量预测能力更 强。数据准备阶段最终使数据满足数据挖掘模型建立的需要。 ( 3 ) 数据挖掘 数据挖掘模型建立阶段就是要根据事先对问题的定义明确挖掘的任务或目的，比如 做一个市场细分模型、一个客户流失模型，一个客户的购物篮分析。然后根据所要解决 的问题选择合适的数据挖掘算法生成模型。在算法选择上，往往是解决一个问题有很多 算法可以选择，比如做一个二元分类模型可以用l o 西s 石c 回归、决策树、神经网络等。 可以根据具体的数据情况选择合适的算法。在很多情况下，选择那种算法对模型结果没 有实质性的影响，在条件允许情况下，可以多用几种技术，再作比较验证。 ( 4 ) 结果解释与评估 该阶段就是对前期数据挖掘阶段发现的模式进行解释和评估。经过评估，剔除冗余、 无关的模式。如果发现的模式不能够满足用户的需要，那么就需要返回前面的某些步骤 中反复提取。比如重新选取数据、采用新的数据变换方法，设置新的参数值或另选其他 数据挖掘算法进行建模【4 0 1 。 2 1 3 数据挖掘的任务及技术 数据挖掘的一些基本任务主要有聚类分析、关联分析、序列模式分析、分类和预测、 孤立点分析等。就这几种数据挖掘基本任务，简要介绍如下： ( 1 ) 聚类分析 聚类就是将数据对象分成不同的簇，使得同一簇内部对象之间具有较高的相似性， 而不同簇中对象之间具有较高的相异性。聚类是一种无监督的分类过程，它解决的问题 是将已给定的若干无分类标记的模式聚集起来使之成为有意义的聚类。聚类在数据挖掘 中是一种非常有用的方法，它可以作为数据挖掘的一个模块来对数据进行深层次分析， 6 基于粗糙集的决策树算法研究及在c r m 中的应用 也可以作为数据挖掘中其他分析算法的一个预处理步骤。目前主要的聚类方法有：划分 法、层次法、基于密度法、基于网格法、基于模型法等。 ( 2 ) 关联分析 关联分析即发现关联规则，其反映的是一个事物与其他事物之间的相互依赖性和关 联性。关联性是一种统计意义上的关联。关联规则是数据库中支持度和信任度分别满足 给定阈值的规则。关联规则的典型应用是在超市中的货篮分析。比如，在商店的销售数 据库中有2 顾客购买的面包，1 5 的顾客购买了牛奶，这里的2 和1 5 就是支持度。 另外，如果在所有购买面包的顾客中有6 0 的顾客同时也购买了牛奶，那么6 0 就是信 任度。目前主要的关联规则算法有：a p r i o r i 算法、l i g 算法、f pg r o w t h 算法等。 ( 3 ) 序列模式分析 序列模式分析和关联分析相似，其目的也是发现数据之间的联系，但序列模式分析 主要用于分析数据间的前后序列关系。它能发现数据库中形如“在某一段时间内，顾客 购买商品a ，接着购买商品b ，而后购买商品c ，即序列a b c 出现的频度较高 之类的知识。在进行序列模式分析时同样也需要由用户输入最小置信度c 和最小支持度 j 【4 l 】。 ( 5 ) 分类与预测 分类是找出描述并区分数据类或概念的模型( 或函数) 的过程，以便能够使用模型预 测类标记未知的对象类。导出模型是基于对训练数据集( 即其类标记己知的数据对象) 的 分析。导出模式可以用多种形式表示，如分类规则、判定树、数学公式或神经网络。 分类可以用来预测数据对象的类标记。然而，在某些应用中，人们可能希望预测某 些空缺的或不知道的数据值，而不是类标记。当被预测的值是数据值时，通常称之为预 测。尽管预测可以涉及数据值预测和类标记预测，通常预测限于值预测，并因此不同于 分类。预测也包含基于可用数据的分布趋势识别 4 2 1 。 ( 6 ) 孤立点分析 数据库中可能包含一些数据对象，他们与数据的一般行为或模式不一致，这些数据 对象是孤立点( o u t l i e r ) 。大部分数据挖掘方法将孤立点视为噪音或异常丢弃。然而，在一 些应用中，罕见的事件可能比正常出现的那些更有趣。 孤立点可以使用统计实验检测。它假定一个数据分布或概率模型，并使用距离度量， 到其他聚类的距离很大的对象被视为孤立点。居于偏差的方法通过考察一群对象主要特 征上的差别识别孤立点，而不是使用统计或距离度量 4 2 】。 7 基于粗糙集的决策树算法研究及在c r m 中的应用 数据挖掘常用技术如下： ( 1 ) 决策树 决策树是一种重要的分类分析算法。它是一个类似树的结构图，直观、易于理解。 树的内部节点表示属性的选择，每个分枝表示属性的某一取值，叶子节点表明类别即分 类结果。构造决策树的关键问题是确定分枝属性。生成决策树后，从树的根节点到叶子 节点的每一条路径对应一条决策规则。目前主要的决策树算法有：i d 3 、c 4 5 、c 5 0 、 c a r t 、c h a i d 等。 ( 2 ) 神经网络 神经网络是一种基于对人脑思维的探索和模仿的技术。它能够把各种投入要素通过 复杂的网络转换成产出的信息加工结构。在数据挖掘中，借助神经网络的非线性处理能 力和容躁能力，在有些问题的处理上我们能够得到较好的数据挖掘结果。神经网络在数 据挖掘中主要用来分类和聚类。常见的神经网络模型有：前向神经网络b p 算法、离散 h o p f i e l d 神经网络和连续h o p f i e l d 神经网络模型、b o l t z m a n n 机、自组织特征映射( s o m ) 。 ( 3 ) 粗糙集方法 粗糙集( r o u g hs e t ) 理论是波兰数学家p a w l a k 教授于1 9 8 2 年提出的，它是一种新的处 理含糊性和不确定性的问题数学工具【4 3 1 。它已经成为一种重要的数据挖掘方法，主要用 于数据库的属性约简和规则提取。粗糙集主要的优点就是它不需要任何关于数据的初始 的或附加的信息，因此广泛应用于不确定、不完整的信息分类和信息获取。粗糙集理论 和技术的出现，大大地提高了数据挖掘和知识发现的效率。 ( 4 ) 遗传算法 遗传算法起源于对生物系统进行的计算机模拟研究。1 9 7 5 年，由美国密西根大学 d j h o l l a n d 教授和他的同事们首次提出。遗传算法是一种将自然界有机体的优胜劣汰的 自然选择、适者生存的的进化机制，以及在同一种群个体之间的随机信息交换相结合的 搜索算法。它最大的优点就是问题求解与初始条件无关，搜索最优解能力极强。它可以 对各种数据挖掘算法进行优化，例如，神经网络、最近邻规则等。 ( 5 ) 贝叶斯网络 贝叶斯网络基于后验概率的贝叶斯定理，是建立在对数据进行统计处理基础上的方 法。将不确定事件通过网络连接起来，可以对与其他事件相关的事件的结果进行预测， 其网络变量可以是可见的，也可以隐藏在训练样本中。贝叶斯网络具有分类、聚类、预 测和因果关系分析的功能，其优点是易于理解，预测效果较好，缺点是对发生概率很低 8 广西大掌硕士掌位论文基于粗糙集的决策树算法习阳纪及在c i 瑚中的五u 书 的事件预测效果不好。在医学和制造业等领域的应用具有较好的效果m 】。 ( 6 ) k - n n 分类 k - n n 是基于实例学习或懒惰学习方法，因为它实际并没有构造一个分类器，而是 将所有训练样本首先存储起来，当需要分类时，就临时进行计算处理。当给定一个未知 类别的样本，k - n n 算法搜索k 个与给未知样本最近的训练样本，样本问的距离使用欧 式距离，这样未知类别样本就被分类到“k 个最近邻”中出现次数最多的类别。 2 2 客户关系管理( c r m ) 客户关系管理c r m ( 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 ) 最早e h g a r t n e rg r o u p 提出。 所谓的客户关系管理就是为企业提供全方位的管理视角，赐予企业更完善的客户交流能 力，最大化客户的收益率。c r m 使企业全面观察其外部的客户资源，实现获得潜在客户， 保留现有客户和提高客户忠诚度和满意度的目标，完成从“以产品为中心”的模式向 “以客户为中心的模式的转变。c r m 包括了三层涵义【4 5 】： 首先，c r m 被认为是一种管理理念，其核心思想被认为来自市场营销理论。c r m 是将企业的客户作为企业最重要的资源，强调以客户为中心，通过完善的客户服务和深 入的客户分析来满足客户的需求，不断提高客户的满意度和忠诚度，争取实现客户的终 生价值。 其次，c r m 又是一种旨在改善企业与客户之间关系的新型管理机制。它实施于企业 的市场营销、销售、服务与技术支持等与客户相关的领域。通过对业务流程的全面管理 来优化资源配置、降低成本、增加市场份额。 最后，c r m 还是一套管理软件和技术，它将最佳的商业实践与数据挖掘、数据仓库、 销售自动化以及其它信息技术紧密结合在一起，建立能收集、跟踪和分析客户客户信息 的系统，或建立可增加客户联系渠道、客户互动以及对客户渠道和企业后台的整合功能 模块。从而为企业的销售、客户服务和决策支持等领域提供了一个业务自动化的解决方 案。 2 3 数据挖掘在客户关系管理中的应用 客户关系管理要解决三个基本问题：如何发展和获得客户、如何留住客户、如何极 大的提升客户价值。这也是客户生命周期的三个阶段。围绕客户的生命周期，数据挖掘 9 基于粗稠归的决策树算法研究及在c r m 中的应用 在其每个阶段均能够挖掘结果转化为c r m 的商务行为，提高企业的收益。 结合客户生命周期的三个阶段，数据挖掘在c r m 中的应用主要有以下几个方面： ( 1 ) 获取新客户 对于企业而言，企业的壮大需要新客户的不断加入，以保持其有足够的市场占有率。 在开发新客户的过程中，利用数据挖掘技术建立客户回应模型来预测潜在客户对业务开 发活动的反应，从而识别出有积极反应的客户。这样可以帮助市场人员对潜在的客户进 行筛选，然后有针对性地实施营销活动，有效降低营销成本。 ( 2 ) 客户保持 市场竞争日益激烈，保持原有客户的价值也显得越来越重要。企业可通过数据挖掘 技术对客户数据库中大量的客户数据进行分析和处理，建立流失客户模型，分析其特征， 识别导致客户流失的模式，改善企业的营销管理。另一方面，根据模型结果可以预测哪 些客户可能会离开，以使企业制定一些有利于这些潜在流失者留下来的营销计划和方 案，改善企业与客户的关系，争取保持客户并提高企业收益。 ( 3 ) 提升客户价值 客户细分。客户细分是将企业面对的客户或潜在客户，按人口、地理、消费行为 和对企业的价值等，把具有相同或相近特点的客户划分到同一群体的过程。在了解相同 群体的需求之后，营销人员就能够有针对性地实施营销策略，即对不同群体采取不同营 销方针、营销策略、营销渠道和优惠计划。在数据挖掘技术中，决策树和聚类是典型的 进行客户细分的算法。 交叉营销。交叉营销是指企业为客户提供现在消费商品之外的其他商品的营销活 动。这些商品往往是互补、升级产品，对企业而言附加价值较高。它能够挖掘出不同的 顾客在不同产品和服务上的消费模式，从而达到既满足企业的需求，又满足客户的需求， 使双方之间达到双赢的状态。 客户盈利能力分析。不同客户的盈利能力对企业的利润贡献是不同的，一般的准 则是2 0 的客户给企业带来8 0 的利润。所以从企业的角度来讲，客户是需要区别对待的。 企业可以设置一些计算盈利能力的参数，利用数据挖掘对客户信息和客户历史交易记 录、售后服务等进行分析，得出每位客户的盈利能力。这样，当企业的客户服务资源有 限时，优先对那些有价值和有潜在价值的客户投入较多资金，向其提供及时的个性化服 务，留住这类客户。 1 0 广西大掌硕士掌位论文基于粗糙秦的决策树算法研究及在c r m 中的矗u 啊 2 4 本章小结 本章前半部分简要的介绍了数据挖掘的基本理论，包括数据挖掘的定义、流程、 任务和常见的几种数据挖掘算法，可以对数据挖掘有一个初步的认识。本章后半部分介 绍了客户关系管理的基本含义，围绕客户生命周期简要介绍了数据挖掘在客户关系管理 中的应用。 基于粗稠归的决策树算法句”i 巴及在c f 泓中的应用 3 1 粗糙集理论 第3 章相关理论介绍 粗糙集( r o u g hs e t ) 理论是1 9 8 2 年由波兰数学家z p a w l a k 提出的。它是一种新的处 理含糊性和不确定性问题的数学工具。相对于概率统计、证据理论、模糊集等处理含糊 性和不确定性的数学工具而言，粗糙集理论有这些理论不具备的优越性。统计学需要概 率分布，证据理论需要基本的概率赋值、模糊集理论需要隶属函数，而粗糙集理论的主 要优势就在于它不需要关于数据的任何预备的或额外的信息【加】。 目前，粗糙集理论已广泛应用于知识发现、机器学习、决策支持、模式识别、专家 系统、归纳推理等领域。 3 1 1 知识与不可区分关系 在粗糙集理论中，所要研究的对象组成的一个非空有限集合，称为论域u 。任何子 集x u ，称为u 中的一个概念。特殊的，空集也是一个概念。u 中的任何概念族成 为关于u 的抽象知识，简称知识。“知识 被认为是对研究对象进行分类的能力。 定义3 1 等价关系【4 6 】 设r 是集合彳到彳的二元关系，若它满足： ( 1 ) 对于任意口a ，都有( 口，口) r ( 2 ) 对于任意口，b a ，有( 口，b ) r ，则必有( 6 ，口) r ( 3 ) 对于任意口，b ，c a ，有( 口，b ) r 和( 6 ，c ) r ，则必有( 口，c ) r 则r 是彳上的等价关系。 定义3 2 等价类【蛔 设r 是彳上的等价关系，与彳中的一个元素x 等价的所有元素组成的集合叫做x 的 一个等价类，记为 x 足。 令r 为等价关系族，设p 尺，且p o ，则p 中所有等价关系的交集称为尸上的 不可区分关系，记作i n d ( p ) ，即有： b l n d c 一= r n e p b k 显然i n d ( p ) t g 是等价关系。不可区分关系是p a w l a k 粗糙集理论中最基本的概念。 1 2 广西大掌硕士学位论文 | 0 于粗和u 的决策树算法习阳；巴及在c i 瑚中的屋乙甩 若( x ，y ) i n d ( p ) ，则称对象x 与y 是p 不可区分的，即x ，y 存在于不可区分关系i n d ( p ) 的同一个等价类中。 3 1 2 信息系统与决策表 信息系统是一种知识表达方式，知识的表达方式在智能数据处理中有十分重要的地 位。信息系统有时也称为知识表示系统【4 7 1 。 形式上，四元组s = ( u ，a ，v ，门是一个信息系统，其中： u ：对象的非空有限集合，即论域； 彳：属性的非空有限集合： 矿= u 圪，圪是属性的值域： a e a f ：u xa _ y 是一个信息函数，它为每个对象的每个属性赋予一个信息值，即 v a a ，x u ，厂b ，a ) e 圪。 信息系统可以用数据表格来表示，表格的行对应论域中的对象，列对应对象的属性。 一个对象的全部信息由表中一行属性的值来反映。 决策表是信息系统的一个特例，它是信息系统中最为常用的一个决策系统。多数决 策问题都可以用决策表形式来表达。它可以根据信息系统定义如下： 设s = ( u ，a ，y ，f ) 是一个信息系统( 知识表达系统) ，a = c u d ，c n d = o ，c 称 为条件属性集合，d 称为决策属性集。具有条件属性和决策属性的信息系统称为决策表。 决策表分成两类： 决策表是一致的当且仅当d 依赖于c ，即cjd ； 决策表是不一致的当且仅当cj 。d 。 3 1 3 上下近似与粗糙集 给粗糙集下定义，需要先给出上下近似的概念【删。 定义3 3 设集合x u ，r 是一个等价关系。 称丛= 扛ij u ，且b l x ) 为集合x 的r 下近似集； 称面= 扛iz u ，且b knx 刃 为集合x 的r 上近似集； 称集合b n 胄( x ) = 麟一些为x 的尺边界域； 称p o s 置( x ) = 丛为x 的足正域； 1 3 基于粗糙集的决策树算法研究及在c r m 中的应用 称n e g 月( x ) = u r x 为x 的尺负域。 由上述定义3 3 ，可以知道：下近似心是由必定属于x 的对象组成的集合；而上 近似麟是由可能属于x 的对象组成的集合；b n 置( x ) 表示既不能明确判断属于工，也 不能明确判断不属于肖的对象组成的集合；n e g 胄( x ) 则表示一定不属于x 的对象组成 的集合。 定义3 4 粗糙集与精确集 当b n 五( x ) = l z i 时，即肘= 丛，称x 是尺精确集； 当b n 置( x ) 1 2 i 时，即r x 一r x ，称x 是尺粗糙集。 集合( 范畴) 的不精确性是由于边界引起的。集合的边界越大，其精确性则越低。 为了准确表达这一点，引入精度的概念。 定义3 5 由等价关系尺确定的集合x 的近似精度 州耻篱 ( 3 1 ) 其中x 1 2 i ，lxi 表示集合x 的基数。 3 1 4 属性约简与属性依赖 属性约简，就是在保持知识库分类能力不变的条件下，删除其中不相关或不重要的 知识【4 0 1 。这里面有两个基本概念：约简与核。 定义3 6 令尺为等价关系族，厂r ，如果有i n d ( r ) = r n d ( r 一 ，) ) ，则称，为r 中 不必要的；否则称，为r 中必要的。如果每一个，r 都为尺中必要的，则称r 为独立的； 否则称r 为依赖的。 定义3 7 设q p ，若q 独立的，且r n d ( q ) = i n d ( p ) ，则称q 是等价关系族尸的 一个约简，记作：r e d ( p ) 。尸中所有不必要关系的集合称为等价关系族尸的核，记作： c o r e ( p ) 。 定理3 1 等价关系族p 的核等于尸的所有约简的交集，即c o r e ( p ) = n r e d ( p ) 通过这个定理告诉我们约简与核的关系，一方面，核是所有约简的计算的基础；另 一方面，核可以看作知识库中最重要的部分。 在应用中，一