（管理科学与工程专业论文）粗糙集技术在电信客户分类中的应用.pdf

南京邮电大学硕士研究生学位论文摘要 摘要 随着电信市场竞争的加剧，客户选择电信产品的余地越来越大，电信运营商需要从市 场细分入手，明确营销方向，协调产品、定价、渠道、促销等领域，形成独特的竞争优势。 通过市场细分，根据不同客户群的特点采取卓有成效的营销措施，在竞争中立于不败之地。 本论文利用粗糙集技术在处理模糊、不确定信息等方面的优势，把粗糙集技术运用于 电信客户分类，寻找比传统运营商按照a r p u 值进行电信客户分类更好的方法，具体分析 重点及解决的问题为以下几个方面：( 1 ) 粗糙集算法及其在处理模糊、不确定性信息方面 的优势分析：( 2 ) 把粗糙集和决策树技术相结合应用于分类，并通过试验的方法证明了其 分类的可行性，并分析其优势；( 3 ) 寻找科学的，能确实有助于电信营销的市场细分方法。 本论文把粗糙集技术的数据归约功能，与其他数据挖掘算法相结合，优势互补，应用 与电信客户分类并证明其有效性，通过实验的方法，证明了粗糙集这种挖掘方法存在的优 势，把它应用于电信小灵通市场细分，并针对不同客户群提出营销建议。 南京邮电大学硕士研究生学位论文 a b s t r a c t a b s t r a c t a st h ec o m p e t i t i o na m o n gt e l e c o mo p e r a t o r sg e t sf i e r c e r ，c l i e n t sm a yh a v em o r ec h o i c e st o u s ed i f f e r e n tt e l e c o mp r o d u c t sa n ds e r v i c e s t e l e c o mo p e r a t o r sn e e dt os t a r tf r o mm a r k e t s e g m e n t a t i o n ，s oa u st of i xac l e a rm a r k e t i n gd i r e c t i o n ，a n dr e a l i z et h ec o o r d i n a t i o no fp r o d u c t s ， p r i c i n g ，c h a n n e l ，m a r k e t i n ga n d o t h e ra r e a s t h r o u g hm a r k e ts e g m e n t a t i o n ，t e l e c o mc o r p o r a t i o n s c a l lt a k ee f f e c t i v em a r k e t i n gm e a s u r e sa c c o r d i n gt ot h ec h a r a c t e r i s t i c so fd i f f e r e n tc u s t o m e r g r o u p sa n dm a k et h e m s e l v e si n v i n c i b l ei nt h ec o m p e t i t i o n r o u g hs e ti san e wd a t a - m i n i n ga l g o r i t h mf o rc l a s s i f i c a t i o n i nt h i sp a p e r , t h ea u t h o ra p p l i e s t h em i n i n gc l a s s i f i c a t i o nr u l eb a s e do nr o u g hs e tt h e o r yt ot h et e l e c o mc u s t o m e rs e g m e n t a t i o n a n dt h ea d v a n t a g eo nd e a l i n gw i mf u z z yi n f o r m a t i o ni sa n a l y z e da n dg i v e n i na d d i t i o n , t h e c l a s s i f i c a t i o na l g o r i t h m so fr o u g hs e ta n dd e c i s i o nt r e ea r ec o n n e c t e dt o g e t h e ra n da p p l i e dt ot h e t e l e c o mc u s t o m e rs e g m e n t a t i o n , f o rt h e yh a v ec o m p l e m e n t a r ya d v a n t a g e sw h e nb e i n gu s e d t o g e t h e r i nt h i sw a y , w ea r et r y i n gt o f i n dab e a e rw a yo fc u s t o m e rs e g m e n t a t i o n , w h i c hi s u s e f u lf o rm a r k e t i n g a n o t h e rt a s ko ft h i st h e s i si st os u b d i v i d ep h sc u s t o m e r si n t os o m eg r o u p s a n da n a l y z ec u s t o m e r s c h a r a c t e ro fe v e r yg r o u p i nt h i sp a p e r , t h ea u t h o rc o n n e r st h ea t t r i b u t e sr e d u c t i o nf u n c t i o n so fr o u g hs e tt h e o r yw i t h o t h e rd a t am i n i n ga l g o r i t h m s ，a n da p p l i e st h e mi n t ot h et e l e e o mc u s t o m e rc l a s s i f i c a t i o n t h r o u g h e x p e r i m e n t a lm e t h o d ，t h i sm e t h o dp r o v e dt ob ee f f e c t i v e t h e nt h ea u t h o ra p p l i e si t i n t ot h e c l a s s i f i c a t i o no fp h s ，a n dp u t sf o r w a r ds o m ea d v i c ea c c o r d i n gt ot h ed i f f e r e n tc u s t o m e rg r o u p s 1 1 南京邮电大学硕士研究生学位论文目录 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学 或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研 究所做的任何贡献均已在文中作了明确的说明并了表谢意。 研究生签名：逝日期： 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所 送交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保 存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保 密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部 分内容。论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名：凶；臻师签名： 研究生签名： 芝垫! 导师签名： 南京邮电大学 硕士学位论文摘要 学科、专业：管理学管理科学与工程 研究方向： 堡皇墨笙量旦鱼箜篁堡 作2 0 0 4 级研究生汪金丽 指导教师高卫国 题目：粗糙集技术在电信客户分类中的应用 英文题目：a p p l i c a t i o no fr o u g hs e tt ot e l e c o m m u n i c a t i o nc u s t o m e r s e g m e n t a t i o n 主题词：数据挖掘分类粗糙集决策树聚类 市场细分 k e y w o r d s ： d a t am i n i n g c l a s s i f i c a t i o n r o u g hs e t d e s i s i o nt r e e c l u s t e r i n g c u s t o m e rs e g m e n t a t i o n 南京邮电大学硕士研究生学位论文 第一章：绪论 1 1 课题研究背景和意义 第一章：绪论 我们现在生活在一个网络化的时代，信息技术的发展推动了整个人类社会的进步：人 们利用信息技术生产和搜集数据，无数个数据库被用于商业管理、政府办公、科学研究和 工程开发中，这一发展趋势还会持续下去。但是，在这个被称之为信息爆炸的时代，如何 才能不被过量的信息所淹没，从信息中提取有用的知识，为人们所理解和应用呢? 要想企 业的大量信息成为公司有用的资源，只有充分利用它为公司的业务决策和战略发展服务才 行。因此，面对“人们被数据淹没，人们却饥饿于知识的挑战，数据挖掘和知识发现( d m k d ) 技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力n 1 。 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的数据 中，提取隐含在其中的，人们事先不知道的，但又是潜在有用的信息和知识的过程。还有 很多和这一术语相近似的术语，如从数据库中发现知识( k d d ) 、数据分析、数据融合( d a t a f u s i o n ) 以及决策支持等。人们把原始数据看作是形成知识的源泉，就像从矿石中采矿一 样。原始数据可以是结构化的，如关系型数据库中的数据，也可以是半结构化的，如文本、 图形、图像数据，甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也 可以是非数学的；可以是演绎的，也可以是归纳的。发现了的知识可以被用于信息管理、 查询优化、决策支持、过程控制等，还可以用于数据自身的维护。因此，数据挖掘是- - f 3 广义的交叉学科，它汇聚了不同领域的研究者，尤其是数据库、人工智能、数理统计、可 视化、并行计算等方面的学者和工程技术人员2 。从企业应用而言，数据挖掘可以帮助企 业对数据进行微观、中观乃至宏观的统计、分析、综合和推理，从而利用已有数据预测未 来，帮助企业赢得竞争优势。 随着电信市场的开放，电信的竞争越来越激烈。任何一家电信企业要想在电信市场中 保持竞争优势，需要从市场细分入手，通过市场细分，明确营销方向，协调产品、定价、 渠道、促销等领域，形成独特的竞争优势。通过市场细分，电信运营商能确定最能为之服 务并能取得可观利润的细分市场，开展卓有成效的营销活动，在竞争中立于不败之地n 1 。 然而，传统运营商按a r p u 值客户分类方法，只是单纯地考虑了客户的消费额度，并 南京邮电大学硕士研究生学位论文第一章：绪论 没有深入分析电信用户的消费行为。数据挖掘技术的出现，为运营商进行客户分类提供了 一种有力的研究工具和分析方法。电信企业有其先天性的工t 优势，大量的数据包括：客 户基本信息、产品服务使用信息、各种通话时长、各种通话费用、通话时间偏好、与企 业互动信息等“1 。电信的数据具有属性多，冗余信息多，信息不确定等特点，如何应用数 据挖掘的思想方法，合理地选择挖掘算法，进行科学有效地客户分类，成为研究的一个热 点：数据挖掘算法很难找一药而包治百病。我们试图根据电信客户数据的特点出发，寻找 有利于改进电信客户分类的办法。 1 2 国内外研究现状 k d d 一词首次出现在1 9 8 9 年8 月举行的第l l 届国际联合人工智能学术会议上。迄今 为止，由美国人工智能协会主办的k d d 国际研讨会已经召开了7 次，规模由原来的专题讨 论会发展到国际学术大会，人数由二三十人到七八百人，论文收录比例从2 x l 到6 x l ，研 究重点也逐渐从发现方法转向系统应用，并且注重多种发现策略和技术的集成，以及多种 学科之间的相互渗透。其他内容的专题会议也把数据挖掘和知识发现列为议题之一，成为 当前计算机科学界的一大热点。 1 9 9 7 年亚太地区在新加坡组织了第一次规模较大的p a k d d 学术研讨会，很有特色。1 9 9 3 年，i e e e 的k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊领先出版了k d d 技术专刊，所发表的 5 篇论文代表了当时k d d 研究的最新成果和动态，较全面地论述了k d d 系统方法论、发现 结果的评价、k d d 系统设计的逻辑方法，集中讨论了鉴于数据库的动态性冗余、高噪声和 不确定性、空值等问题，k d d 系统与其它传统的机器学习、专家系统、人工神经网络、数 理统计分析系统的联系和区别，以及相应的基本对策。6 篇论文摘要展示了k d d 在从建立 分子模型到设计制造业的具体应用1 1 。 在国外，数据挖掘已经有不少成功案例。数据挖掘首先在金融、证券、电信、零售业 等数据密集型行业实施，因为这些行业信息化程度比较高，数据库中已经保留了大量数据 资源n 1 。 在国内，数据挖掘的好处也已经引起国内许多企业的重视，但实施存在许多困难：如 缺少数据积累、难于构建业务模型、缺少有经验的实施者、初期投入资金较大等。因而， 国内只有少数信息化程度比较高的行业实施了数据挖掘，电信企业是实施数据挖掘较多的 2 南京邮电大学硕士研究生学位论文第一章：绪论 行业之一。目前电信行业已经把数据挖掘应用于客户欺诈分析、客户流失分析、客户盈利 能力分析、客户细分、交叉销售等。我们这里主要介绍一下研究应用中的三个专题： ( 1 ) 流失预测专题聆1 根据流失客户和没有流失的客户性质和消费行为，进行挖掘分析。建立客户流失预 测模型。分析哪些客户的流失率最大，流失客户的消费行为如何，客户流失的其它相关因 素：如竞争对手的优惠政策，业务系统事故，国家政策和现行经济运行环境等，为市场经营 与决策人员制定相应的策略，留住相应的客户提供决策依据，并预测在该策略下客户流失 情况。 ( 2 ) 交叉销售专题 经营分析系统根据数据仓库中的相关信息。通过交叉模型和产品关联分析等数据挖掘 方法，针对不同类型客户的特征，找出最优的产品组合。分析得到目前存在哪些销售机会， 哪些客户可能会对哪些业务感兴趣以及感兴趣的程度。 ( 3 ) 客户细分专题 客户细分就是把广大的客户群分割为具有不同需要、性格或行为特征等的消费群 体。使用聚类分析、因子分析等数据挖掘方法定义不同的细分用户群。目的是使同一细分 客户内个体之间的固有差异减少到最小，使不同细分客户群之间的差异增加到最大。通过 对客户进行细分，可以针对不同细分特征的客户群体采取独特的产品或市场营销组合战略 以求获得最佳收益。 电信企业使用数据挖掘技术，取得了一定的成效，但很多时候挖掘的结果不尽如人意。 其中部分原因是由于数据缺失量大，噪音数据多造成的。电信营销人员一方面在想办法通 过呼叫中心搜集资料、有奖填写资料等方式获取更真实、准确的客户信息，另一方面，数 据挖掘人员在不断研究挖掘算法的改进，研究如何从噪音数据中提取出确实有用的知识。 1 3 论文结构 本论文把粗糙集技术应用于电信客户分类，借助于数据挖掘工具，对某地市电信公司 的小灵通客户数据做了分析，利用粗糙集和决策树相结合的挖掘方法，验证了粗糙集对电 信客户分类的有效性，显示了粗糙集在处理不确定性信息时具有的优势；通过试验的方法， 证明了传统运营商按a r p u 值进行客户细分的不足，最后用聚类的方法，对小灵通客户进 3 南京邮电大学硕士研究生学位论文 第一章：绪论 行分类，并根据不同客户群提出营销建议。 第一章绪论 简要介绍了本课题的研究背景及意义，以及数据挖掘技术在国内外的研究现状，明 确了研究电信行业客户细分的目标。 第二章分类模型构建技术基础 简要介绍了数据挖掘的常用算法，分析常用算法在进行电信客户分类时存在的不 足；较详尽地介绍了粗糙集技术及其在处理不确定性信息的优势，并提出把租糙集技术和 决策树算法相结合应用与电信客户分类的思路，给出分类规则输出步骤。 第三章客户分类研究准备 从业务理解、数据准备和预处理方面介绍，为电信客户分类研究作铺垫工作。 第四章基于粗糙集技术的客户分类以及营销策略 根据电信数据的特点，把粗糙集技术和决策树技术相结合应用于电信客户分类，通 过实验证明其有效性；然后把粗集约简的结果，作为细分维度对小灵通市场进行客户细分， 并针对不同客户群提出营销建议。 第五章知识扩展 对本论文的知识领域进行进一步拓展。 第六章总结 总结本论文所做的工作，分析存在的不足，指出需要进一步研究的工作。 4 南京邮电大学硕士研究生学位论文第二章分类模型构建技术基础 第二章：分类模型构建技术基础 2 1 数据挖掘的常用方法及其特点 2 1 1 关联方法 关联分析( a s s o c i a ti o na n a l y s i s ) 是指在数据记录的数据项之间挖掘关联关系，某 些数据项的出现预示着该记录中其它一些数据项出现的可能。关联分析的目的是找出数 据库中隐藏的关联网( 一般用支持度和可信度两个阀值来度量关联规则的相关性，还不断 引入兴趣度、相关性等参数，使得所挖掘的规则更符合需求) ，常用的方法有a p r i o r i 算 法。 2 1 2 分类法 分类1 就是找出一个类别的概念描述。它代表了这类数据的整体信息，即该类的内涵 描述，并用这种描述来构造模型。一般用规则或决策树模式表示。分类是利用训练数据集 通过一定的算法求得分类规则；分类可被用于规则描述和预测。分类的常用方法有人工神 经网络、决策树、粗糙集算法、贝叶斯算法等，这里简单介绍一下决策树，粗糙集算法将 在下一节重点介绍。 2 1 2 1 决策树概述 决策树是一个类似于流程图的树结构口1 ，由决策节点、分支和叶子构成。其中，每个 内部节点表示在一个属性上的测试，每个分支代表一个测试输出，而每个树叶节点代表类 或类分布。 决策树的基本算法是贪心算法，它以自顶向下递归的各个击破方式构造决策树。建模 的基本思想是：选取一个最能区分不同类别样本的属性，让其作为树根，并把训练样本集 分为相应的几块，接下来再依次在每一块样本集中选出区分度最大的属性，作为树的第二 层结点。依此类推，直到所有的叶结点都只包含一类样本时终止。其基本算法如下陋1 ： 算法：g e n e r a t e d e c i s i o nt r e e 由给定的训练数据产生一棵决策树 输入：训练样本s a m p l e s ，有离散值属性表示；候选属性的集合a t t r i b u t e l i s t 输出：一个决策树 方法： s 南京邮电大学硕士研究生学位论文第二章分类模型构建技术基础 ( 1 ) 创建节点n ； ( 2 ) i fs a m p l e s 都在同一各类ct h e n ( 3 ) 返回n 作为叶节点，以类c 标记； ( 4 ) i fa t t r i b u t e l i s t 中具有最高信息增益的属性t e s t _ a t t r i b u t e ； ( 5 ) 返回作为叶节点，标记为s a m p l e s 中最普遍的类：使用多数表决 ( 6 ) 选择a t t r i b u t e l i s t 中具有最高信息增益的属性t e s t _ a t t r i b u t e ； ( 7 ) 标记节点为t e s t _ a t t r i b u t e ： ( 8 ) f o re a c ht e s t _ a t t r i b u t e 中的已知值a i ； 划分s a m p l e s ( 9 ) 由节点n 长出一个条件为t e s t a t t r i b u t e = a l ；的分技： ( 1 0 ) 设s i 是s a m p l e s 中t e s t _ a t t r i b u t e = a t 的样本的集合；一个划分 ( 1 1 ) i fs l 为空t h e n ( 1 2 ) 加上一个树叶，标记为s a m p l e s 中最普遍的类； ( 1 3 ) e l s e 加上一个由 g e n e r a t e d e c i s i o n _ t r e e ( s ，a t t r i b u t e l i s t t e s t a t t r i b u t e ) 返回的节点； 递归划分步骤仅当下列条件之一成立时停止： ( 1 ) 给定节点的所有样本属于同一类( s t e p 2 、3 ) ； ( 2 ) 没有剩余属性可以用来进一步划分样本( s t e p 4 ) 。在此情况下，使用多数表决 ( s t e p 5 ) 。这涉及将给定的节点转换成树叶，并用s a m p l e 中的多数所在的类标记它； ( 3 ) 对测试属性创建的某分枝( t e s t _ a t t r i b u t e = a 。) 没有样本，在这种情况下， 以s a m p l e s 中的多数类创建一个树叶( s t e p l 2 ) 。 决策树模型中最重要的部分是计算“信息增益 ，该数值用以辅助选择大区分度属性。 按照信息论的定义9 1 ，设有m 类样本，每类c 。有s 。个实例，则把它们分类所需要的信息量i 为： i ( s l ，s 2 ，s ) = 一p i l o g z ( p i ) 其中，p ；是任意样本属于c 。的概率，用s 。s 估计。 设用属性a 将s 划分为v 个子集 s 1 ，s v ) ，如果选择a 作测试属性，设s i j 是 子集s j 中类c j 的样本数。根据由a 划分成子集的熵或期望信息由下式给出： e ( a ) = 羔华i ( s 。j + + s j ) 6 南京邮电大学硕士研究生学位论文 第二章分类模型构建技术基础 其中，鱼二= 鱼充当第j 个子集的权，并且等于中的样本个数除以s 中的样本总 s 数。熵值越小，子集划分的纯度越高。另外，对于给定的子集s ， i ( s - j + ”+ s - j ) = 一喜p i j l 。g z ( p i j ) 其中，p i j 2 高p i - 是s 中的样本属于类c ，概率。 因此，如果按属性a 划分的信息增益是： g a i n ( a ) = i ( s i ，s 2 ，s ) - e ( a ) 以上算法计算每个属性的信息增益。具有最高信息增益的属性选作给定集合s 的测试 属性。创建一个节点，并以该属性标记，对属性的每个值创建分技，并据此划分样本。 2 1 2 2 应用决策树的优劣势分析 建立决策树需要的计算资源较少，可能只要对数据库进行几遍扫描之后就能完成，另 外决策树可以很容易地处理包含很多预测变量的情况，因此决策树模型可以建立得很快， 并适合应用于数据量大的情况。 对于决策树的输入参数可以是非数值型数据，这样就在处理非数值型数据前没有必要 增加数据的处理工作。决策树的另一个显著优点，就是建模结果易理解和解释。决策树的 输出结果可以有两种形式：树状模型和规则集，以节点、分支、叶子以及各叶节点的概率 等元素，综合直观地展示给分析人员预测样本数据的分类情况，能清楚地看到每一个类别 划分的依据，以及对目标变量影响较大的变量，便于更好地应用分类结论。而规则集是从 树状模型衍生而来的，树的每一条从根到叶子节点的路径就是一条规则，将所有规则综合 就形成了规则集；规则集更条理地显示规则的形成原则。 当然，决策树模型也有其自身的缺点。如决策树模型对连续型的字段在分割上算法众 多，但不同的算法不是针对每个变量都很适用，影响了整棵树的预测准确性。而且，当类 别太多时，错误可能就会增加的比较快。另外，当属性比较多时，决策树选取所有的属性 进行分类，一方面容易造成分类过细，规则不具有代表性的缺点：另一方面，决策树不能 克服数据噪音大、信息不确定等的不利因素。 应用决策树的过程中，建模不是一劳永逸的，要通过检测数据不断地评估模型的准确 性，调整模型的各项参数，以追求更可靠的模型。 7 南京邮电大学硕士研究生学位论文 第二章分类模型构建技术基础 2 1 3 聚类法 聚类是把数据按照相似性归纳成若干类别，同一类中的数据彼此相似，不同类中的数 据相异。聚类分析可以建立宏观概念，发现数据的分布模式，以及可能的数据属性之间的 相互关系。 目前存在着大量的聚类算法，大体可以分为划分方法、层次方法、基于密度方法，基 于网格方法和基于模型方法。 ( 1 ) 划分方法( p a m ：p a r t i t i o n i n gm e t h o d ) ：首先创建k 个划分，k 为要创建的划分个数： 然后利用一个循环定位技术通过将对象从一个划分移到另一个划分来帮助改善划分质量。 典型的划分方法包括：k - m e a n s ，k - m e d o id s ，c l a r a ，c l a r a n s 等。 ( 2 ) 层次方法( h i e r a r c h i c a lm e t h o d ) ：创建一个层次以分解给定的数据集。该方法可 以分为自上而下( 分解) 和自下而上( 合并) 两种操作方式。为弥补分解与合并的不足， 层次合并经常要与其它聚类方法相结合，如循环定位。 典型的这类方法包括：b i r c h 、c u r e 、r o c k 、h e m a l o e n 等方法。 ( 3 ) 基于密度方法，根据密度完成对象的聚类。它根据对象周围的密度不断增长聚类， 如d b s c a n 。 ( 4 ) 基于网格方法，首先将对象空间划分为有限个单元以构成网格结构：然后利用网格 结构完成聚类。如：s t i n g 、c l i q u e 和w a v e c l u s t e r 。 ( 5 ) 基于模型方法，它假设每个聚类的模型并发现适合相应模型的数据。如： c o b w e b 、c l a s s i t 等方法。 这里主要介绍一下k 一均值法( k - m e a n s ) ，这种算法与其他大多数算法相比，它更易 于理解，在一般商业数据挖掘工具中有广泛的应用。另外，关于通信用户的消费数据多为 数值型数据，将k m e a n s 算法应用于对通信用户的细分上，将会取得较好的效果，能够很 容易找到具有相同消费默认的客户。 2 1 3 1k - m e a n s 聚类算法 k - m e a n s 算法是把数据集拆分成预先给定数目的类，这个数目就是k ，均值就是平均 数口1 。为了组成不同的类别，每个记录都映射到“记录( 样本) 空间 的一个点，记录有 几个字段，这个空间就是几维，每个字段的值相当于该点到对应坐标轴的距离。所有字段 都要转化为数值型，才能用在这种几何运算上。为了便于不同维度量纲统一，便于比较， 数据最好能够预先进行标准化处理。 每条记录都是通过迭代过程进行归类。迭代开始时，每个类别都是处于记录空间的随 r 南京邮电大学硕士研究生学位论文 第二章分类模型构建技术基础 机中心位置，然后通过计算各个类的质心，不断改变各个类别的中心位置，直到每个类的 质心就是处于该类的中心位置。 举例来说，把n 个对象分为k 个类，在类内具有较高的相似度，而类间的相似度较底。 相似度的计算根据一个类中对象的平均值( 质心) 来进行。随机的抽取k 个对象，每个对象 初始地代表一个类的平均值。对剩余的每个对象，根据与各个类中心的距离，将它赋给最 近的类。然后重新计算各个类的平均值。过程不断反复，直到准则函数收敛。一般采用平 方误差准则： 七 层p e c i i - - i lp m i1 2 上式中，p 是空间的点，表示给定的对象，m ；是簇c ；的平均值。 2 1 3 2k - m e a n s 方法的应用 k - m e a n s 聚类方法的实际应用过程中，如何选择合适的类别个数是一个关键步骤。对 于不同的k 值，聚类结果有着较大的差别，k 值选择的好与坏直接影响该方法是否能对解 决问题有明显的帮助。一般来说，除非有确定的理由决定某一特定的k 值，一般的数据挖 掘分析者都会用不同的k 值来试验，然后再对每种聚类结果进行评估。一般认为，理想的 结果是：它使得同一类不同成员之间的距离较小而使相邻类别之间的距离较大。对于描述 性数据挖掘来说，最好的聚类结果则可能只是展示出数据中的意想不到的聚类模式。有些 软件可以辅助产生一系列k 值，如s g i 公司的产品m i n e s e t 。 当然，聚类成功后，如何说明聚类结果也是有效应用的一个重要环节。由于聚类方法 是一种无监督性的知识发现方法，并没有明确的分类目标，也无法很直观地发现有趣的结 论。介绍几种辅助解释聚类结果的方法，能使该方法的应用更具使用价值： ( 1 ) 把类别作为目标变量建一个决策树，并用它产生一些规则解释说明如何把新的样 品正确归类： ( 2 ) 使用可视化方法研究观察这些类别如何受输入变量变化的影响； ( 3 ) 检查一个类别与另一类别变量分布的差异。 2 1 4 电信客户分类时常用挖掘算法的不足 在数据挖掘实践中，算法是死板的，没有一种算法可以一统江湖，算法的适用性非常 重要。针对电信企业的客户分类，通常由于数据的噪音大、细分维度多、信息不确定等特 9 南京邮电大学硕士研究生学位论文第二章分类模型构建技术基础 点，给挖掘带来一定的困难：通过上两小节对决策树和k 一1 n e a n s 聚类挖掘算法的分析， 我们发现，用这两种常用算法主要存在如下不足： ( 1 ) 数据的不确定、模糊性给客户分类带来的困难：k _ 咖e a n s 聚类算法不适用于噪 音较多的数据，同时，决策树技术在形成树，通过信息熵的计算来选取属性，并不考虑条 件属性对决策属性分类能力影响的重要程度，从而不能克服噪音数据带来的负面影响。 ( 2 ) 细分维度过多给分类带来的困难：对于决策树而言，容易造成分支过多，分类 不具有代表性等不足；对于k - - m e a n s 聚类算法，在细分维度的选取上存在困难：选取哪 些细分维度能够更有利地将客户聚成不同的类，使得不同类的客户特征更鲜明。k - 1 i i e a n s 聚类算法不适用于高维的样本集，维度选得过多，容易造成时间空间浪费大、分类结果不 明晰的不足。维数选得太少或不合适，又会导致聚类结果不符合实际情况的缺点。一般在 使用k 皿e a n s 聚类进行客户聚类时，维度的选择通常是通过经验去选取。这样就容易因 为人为因素过多、选取不科学造成违背数据客观事实的弊端。 由于本文重点研究粗糙集算法在电信客户分类规则中的应用，下面重点介绍粗糙集算 法。 2 2 粗糙集理论和算法介绍 粗糙集理论( r o u g hs e t ，r s ) n 0 1 是波兰数学家p a w l a k 在1 9 8 2 年提出的一种分析数 据的数学理论，其特点是不需要预先给定某些特征或属性的数量描述，而是直接从给定问 题的描述集合出发，进行等价类的划分，确定问题的近似域，从而对含糊性和不确定性信 息进行分析和处理，揭示出数据间隐含的知识和规划。 近年来，粗糙集理论和应用取得了很快的发展，粗集理论对模糊和不完全知识的处理 比较出色，成为不确定性计算的重要分支，其涉及的领域包括模式识别、机器学习、决策 分析和决策支持、知识获取、知识发现等，并且其算法简单、易于操作。 2 2 1 基本概念： 定义1 信息系统与决策表系统 一个信息系统s = ( u ，a ，v ，f ) ，其中，u 为非空有限集，称为论域；a 为非空有限属 性值，v 为属性值的集合，f ：u x a - v 为一个信息函数，指定每一个对象关于属性的取值。 为简化常用s = ( u ，a ) 来代替s = 。 1 0 南京邮电大学硕士研究生学位论文 第二章分类模型构建技术基础 如果a 由条件属性集合c 和决策属性集合d 组成，c 、d 满足cud = a ，cnd = ， 则称s 为决策系统。为简化起见，本文用( u ，cu d ) 表示决策系统，即决策属性值集合 只包含一个元素，对于多元素的决策属性集合，其处理方法与之类似。 定义2 不可分辨关系和等价类 对于决策系统s = ( u ，cu d ) ) ，称二元关系i n d ( c ， d ) ) = ( x 。，x ：) uxu ：d ( x ，) = d ( x 。) 或者ae c ，a ( x 。) = a ( x ：) ) 为s 的不可分辨关系，其中，x ，x 。为u 中的 元素。基于这种不可分辨关系，可以将论域u 划分成不同等价类。论域c 关于条件属性c 的等价类划分记为i n d ( c ) = u c 。 定义3 属性约简和核 在决策系统s = ( u ，cu d ) 中，c 中的某种属性可能是多余的，在保持分类能力 不变的情况下，可以删除这些冗余的属性，这就是属性约简。经过约简可得到不含多余属 性并保证分类正确的最小条件属性集。如果i n d ( b ) = i n d ( b 一 a ) ) ，其中，b 包含于a ，a a ， 则称b 是可约简的。一个决策表可能同时存在几个约简，这些约简的交集定义为决策表的 核，核中的属性是影响分类的重要属性。 ? 定义4 上近似集、下近似集、正域、负域 在信息系统s = ( u ，cu d ) ) 中，x c u 为一对象集，r 为一等价关系，则在r 水平下x 的下近似垦( x ) 和上近似r ( x ) 定义为： 墨( x ) = x t u rl x 。c _ x ) ， 尺( x ) = f i x 。u rl x 。n x 痧) 其中 x 。是包含x 的等价关系r 的等价类。而集合x 相对于r 的正区域就是x 的下 近似，即p o s t ( x ) = 墨( x ) ；集合x 相对r 的负区域是：n e gt ( x ) = u - u - r ( x ) 。 星( x ) 或p o s 。( x ) 是由那些根据知识r 判断肯定属于x 的u 中元素组成的集合：r ( x ) 是那些根据知识r 判断可能属于x 的u 中元素组成的集合；n e g 。( x ) 是那些根据知识 r 判断肯定不属于x 的u 中元素组成的集合。定义5 属性间的依赖关系和属性重要度 在信息系统s = ( u ，cu ( d ) 中，设一等价关系为属性集r c c ，对于决策属性d 以 依赖度r 。( d ) 依赖于s 中c 的子集r ，即：r 。( d ) = fp o s 。( d ) i lp o s 。( d ) i ； 设属性a ec ，则a 的属性重要度定义为：s g f ( a ，c ，d ) ：r 。( d ) 一r j ( d ) s g f ( a ，c ，d ) 表明从c 中去除a 后对分类决策的影响程度n 1 1 南京邮电大学硕士研究生学位论文第二章分类模型构建技术基础 2 2 2 粗糙集理论的特点和属性约简算法 2 2 2 1 粗集理论特点： ( 1 ) 数据挖掘研究的对象多为关系型数据库，关系表可作为粗集理论中的信息表或 决策表，这给集合方法的应用带来极大的方便1 姐； ( 2 ) 粗集的约简( r e d u c t ) 理论可用于高维数据的预处理，以去除冗余属性从而达 到降低维数的目的；研究人员发现，对许多大型系统，仅有部分数据库表属性必须保留， 如果能将冗余属性删除，可大大提高系统潜在知识的清晰度n 钉。 因而我们可以把粗糙集用于数据归约，识别和删除无助于给定训练数据分类的属性和 相关分析，这样，根据分类任务评估每个属性的贡献或意义n 钉。 下面举一个简单的例子说明粗糙集的属性约简功能。有一个有关天气预测的决策表， 如图2 3 2 1 所示： uo u t l o o k ( a 1 )t e m p r a ( a 2 )h u m i d i t y ( a 3 )w i n d y ( a 4 )决策属性( d ) l s u n n y h o t h i g h f a l s en 2 s u n n y h o t h i g h f a l s en 3 o v e r c a s t h o t h i g h f a l s ep 4r a i nm i l d h i g h f a l s ep 5r a i nc o o ln o r m a lf a l s ep 6r a i nz o o ln o r m a l r u en 7 o v e r c a s t c o o ln o r m a l t r u e p 8s u n n yi i dh i g hf a l s e n 9 s u n n y c o o ln o r m a lf a l s ep 1 0r a i ni l dn o r m a lf a l s ep 1s u n n ym i i d n o r m a l r u ep 1 2o v e r c a s t哺i l d h i g h r u ep 1 3o v e r c a s th o tn o r m a lf a l s ep 4r a i nh i l d h i g hr u e n 图2 3 2 1 天气预测决策表 令q = 决策属性集= d ) ，p = 条件属性全集= a l ，a 2 ，a 3 ，a 4 ) ，则由表得到： i n d ( p ) = 1 ) ， 2 ) ， 3 ) ， 4 ) ， 5 ) ， 6 ) ， 7 ) ， 8 ， 9 ) ， 1 0 ) ， 1 1 ) ， 1 2 ) ， 1 3 ， 1 4 ) i n d ( q ) = “1 ，2 ，6 ，8 ，1 4 ) ， 3 ，4 ，5 ，7 ，9 ，1 0 ，1 1 ，1 2 ，1 3 p o sp ( q ) = u 因此，论域u 是p 相对于q 一致的，这说明该决策表是完全确定的决策表，决策表中 1 2 南京邮电大学硕士研究生学位论文 第二章分类模型构建技术基础 不包含不一致信息。 i n d ( p f a l ) = “1 ，3 ，f 2 ) ， 4 ，8 ， 5 ，9 ， 6 ，7 ) ， 1 0 ， 1 1 ， 1 2 ，1 4 ) ， 1 3 ) i n d ( 卜 a 2 ) ) = “1 ，8 ) ， 2 ， 3 ) ， 4 ) ， 5 ，1 0 ) ， 6 ) ， 7 ) ， 9 ， 1 1 ) ， 1 2 ) ，( 1 3 ， 1 4 ) ) i n d ( p - a 3 ) ) = 1 ， 2 ) ，( 3 ，1 3 ) ，f 4 ，1 0 ，f 5 ) ，( 6 ， 7 ， 8 ) ， 9 j ，f l l ， 1 2 ， 1 4 i n d ( p - a 4 ) ) = “l ，2 ) ， 3 ) ， 4 ，1 4 ) ， 5 ，6 ) ， 7 ， 8 1 ( 9 j ，q o j ，j l l j ，! 1 2 ) ， 1 3 ) p o s p - a ij ( q ) = 2 ，5 ，9 ，1 0 ，l l p o s ( p 一 a 2 ，( q ) = u = p o s p ( q ) p o s ( p 一：a 3 ；) ( q ) = u = p o s p ( q ) p o s ( ，一 “ ) ( q ) = 1 ，2 ，3 ，7 ，8 ，9 ，1 0 ，1 1 ，1 3 由此可见，属性a 2 ，a 3 是相对于决策属性d 可省略的，但不一定可以同时省略( 这里 不能同时省略) 。而属性a 1 ，a 4 是相对于决策属性d 不可省略的，因此 c o r e q ( p ) = a l ，a 4 ，r e d q ( p ) = a 1 ，a 3 ，a 4 ， a 1 ，a 2 ，a 4 ” 然而，粗糙集的求核和属性约简过程是较为困难的，下面主要介绍粗糙集的属性约简 算法。 2 2 2 2 粗糙集的属性约简算法 在智能数据分析研究中，原始的决策表信息系统中的知识( 条件属性) 并不是同等重 要的，甚至其中某些条件属性是冗余的。冗余属性的存在，一方面是对资源的浪费( 需要 存储空间和处理时间) ；另一方面，也干扰人们作出正确而简洁的决策。所为决策表的属 性约简，就是在保持条件属性相对于决策属性的分类能力不变的条件下，删除其中不必要 的或不重要的属性。一般来讲，一个决策表的知识相对约简不是唯一的，即对同一个决策表 可能存在多个相对约简。因为知识约简的目的是导出关于决策表的决策规则，约简中属性 的多少直接影响着决策规则的繁简，因此，人们期望找到具有最少属性的约简，即最小约 简。然而，遗憾的是w o n g s k m 和z i a r k o w 已经证明找出一个决策表的最小约简是 n p - h a r d 问题1 1 5 1 。导致n p - h a r d 的主要原因是属性的组合爆炸问题。 ( 1 ) 一般属性约简算法 一般约简算法是通过搜索决策表里的每个条件属性，看去掉它是否改变条件属性的分 类能力，该算法容易理解，但是却是一个组合爆炸问题，穷尽的搜索所需要的时间和空间 代价都很高( 上例中采用的是一般属性约简算法) 。 南京邮电大学硕士研究生学位论文 第二章分类模型构建技术基础 该算法可描述为： 对于