（计算机应用技术专业论文）数据挖掘在电信客户细分领域的应用.pdf

昆明理工大学硕士论文 摘要 摘要 随着数据挖掘技术的迅速发展，数据挖掘已经应用到生活的方方面 面。本文研究的主要内容是数据挖掘技术在电信客户细分领域的应用。 本文首先介绍了数据挖掘的基本理论知识，如数据挖掘的定义，数据挖 掘的任务等等。本文的重点在于如何对电信客户进行合理、有效的细分。 为了解决这一问题，我们进行了详细的需求分析，通过需求分析我们确 定了对电信客户数据进行挖掘所需要的数据集。通过对所需数据的预处 理，最终得到我们所需数据汇总表。之后，为了选择合适的聚类分析算 法实现对电信客户的分群，我们利用两种不同的算法k - m e a n s 算法和模 糊c 均值聚类算法对电信客户进行了细分。并通过修改不同的k 值和样 本点的个数，对结果进行修正，从而得到了合理的聚类结果。通过对两 种算法得到的结果的比较找到了解决电信客户细分这一实际问题的合理 方案。利用聚类算法解决电信客户细分问题，有利于电信运营商一对一 的面向不同的客户群体制定销售政策。总体说来，这一问题的研究和探 索，有着重要的现实意义。 关键词：数据挖掘，电信，聚类算法，k - m e a n s 算法，模糊c 均值聚类算 法 昆i ! | j 理工人学顿：j ：论文 a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fd a t am i n i n g ，d a t am i n i n gh a sb e e nu s e di na l l a s p e c to fl i f e t h ec e n t r a lo ft h i st h e s i si st h ea p p l i c a t i o no fd a t am i n i n gi n t e l e g r a p h i cc u s t o m e rc l a ss i f i c a t i o n f i r s t ，t h et h e s i si n t r o d u c eb a s a lt h e o r y ， s u c ha st h ed e f i n i t i o no fd a t am i n i n g ，t h et a s ko fd a t am i n i n g t h ec e n t r a l o ft h i st h e s i si sh o wt or e a l i z et e l e g r a p h i cc u s t o m e rc l a s s i f i c a t i o n i no r d e r t or e s o l v et h i sp r o b l e m ，w em u s ta n a l y z et e l e g r a p h i cd e m a n d b yt h e a n a l y s i s ，w ec o u l df i n dd a t aw h i c hw en e e d t h e nw es h o u l dp i c ku pd a t a a n dt r a n s f e rd a t a i no r d e rt or e a l i z et e l e g r a p h i cc u s t o m e rc l a s s i f i c a t i o na n d g a i nt h el o g i c a lr e s u l t ，w em u s tc h o i c er i g h tc l u s t e r i n ga l g o r i t h mt or e a l i z e t e l e g r a p h i cc u s t o m e rc l a ss i f i c a t i o n w eu set w ok i n d sc l u s t e r i n ga l g o r i t h m f k m e a n s a l g o r i t h ma n df u z z ycm e a n s c l u s t e ra l g o r i t h m ) t or e a l i z e s u b s e c t i o n t h r o u g hc o m p a r ek - m e a n sa l g o r i t h m w i t hf u z z ycm e a n s c l u s t e ra l g o r i t h m ，w eg a i nr i g h tm e t h o dt or e a l i z et e l e g r a p h i cc u s t o m e r c l a s s i f i c a t i o n i nt h ee n d a p p l yd a t am i n i n gt e c h n o l o g yt os e t t l ep r a c t i c a l p r o b l e misv e r yu s e f u l k e y w o r d ：d a t a m i n i n g ，t e l e c o m m u n i c a t i o n ，c l u s t e r i n ga l g o r i t h m ， k m e a n sa l g o r i t h m ，f u z z ycm e a n sc l u s t e ra l g o r i t h m 昆明理工大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下进行 研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做 出重要贡献的个人和集体，均已在论文中作了明确的说明并表示了谢 意。本声明的法律结果由本人承担。 学位论文作者签名：叶奔 日 期：i 扫日年弓月乡日 关于论文使用授权的说明 本人完全了解昆明理工大学有关保留、使用学位论文的规定，即： 学校有权保留、送交论文的复印件，允许论文被查阅，学校可以公布 论文的全部或部分内容，可以采用影印或其他复制手段保存论文。 ( 保密论文在解密后应遵守) 导师签名 昆明理工人学坝1 ：论文第一章绪论 第一章绪论 1 1 论文的研究背景 1 1 1海量数据的出现 计算机的出现带来了数据存储和处理方式的巨大变革。企业纷纷建 立了自己的数据库系统，由计算机管理数据代替了传统的手工操作，以 此来收集、存储、管理业务操作数据，改善办公环境，提高操作人员的 工作效率。随着数据库技术的成熟和数据应用的普及，人类积累的数据 量正在以指数速度迅速增长。进入九十年代，伴随着因特网( in t e r n e t ) 的出现和发展，以及随之而来的企业内部网( i n t r a n e t ) 、企业外部网 ( e x t r a n e t ) 和虚拟私有网( v p nv ir t u a lp r i v a t en e t w o r k ) 的产生和 应用，将整个世界联成一个小小的地球村，人们可以跨越时空的在网上 交换数据信息和协同工作。这样，展现在人们面前的已不是局限于本部 门，本单位和本行业的庞大数据库，而是浩瀚无垠的信息海洋，数据洪水 正向人们滚滚涌来。数据已经远远超出了它原始的范畴，它包含各种空 间数据、报表统计数据、以及文字、声音、图像、超文本等各种环境和 文化数据信息。 海量数据的出现向人们提出了新的挑战。人们感到面对信息海洋像 大海捞针一样束手无策。据估计，一个大型企业数据库中数据，只有百 分之七得到很好应用。这样，相对于“数据过剩”和“信息爆炸”，人们 又感到“信息贫乏”( 1n f o r m a t j o dp o o r ) 和“数据关在牢笼中”( d a ta inj a j1 ) ，奈斯伯特( 、l o h nx a is b e t t ) 惊呼：人类诈被数据淹没却饥渴 于知 = 。如何在火黾的数据中发现对我们有用的信息成为一个迫f ；! _ 需要 解决的问题。数据挖掘( d m ) 应运而生。 1 1 2数据挖掘技术的兴起 虽然人们认识到数据挖掘有着重要的意义，但对于数据挖掘的定义并 没有达成致的认识，不同的人有着不同的理解。总体来说，数据挖掘 ( d a t am in in g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的 原始数据中，提取隐含在其中的、人们事先不知道的、潜在的、但又是 有用的、可信的、新颖的信息和知识的过程。 昆明理工人学硕一l 论文第一章绪论 从广义角度讲数据、信息是知识的表现形式，但在数据挖掘中更多的 是把概念、规则、模式、规律和约束等看作知识。原始数据可以是结构 化的，如关系型数据库中的数据，也可以是半结构化的，如文本、图形、 图象数据，甚至是分布在网络上的异构型数据。发现知识的方法可以是 数学的或非数学的、演绎的或归纳的。发现的知识可以被用于信息管理、 查询优化、决策支持、过程控制等。总之，数据挖掘是一门交叉学科， 它的发展和应用涉及到不同的领域，主要包括数据库、人工智能、数理 统计、可视化、并行计算等。 数据挖掘也被称为数据库中知识发现( k n o w l e d g ed is c 0 v e r yin d a t a b a s e ，k d d ) 。它的主要三大技术支柱就是数据库、人工智能和数理统 计。图1 简要描述了数据挖掘技术的形成过程。数据库理论的发展促成了 数据仓库的形成，人工智能的发展又促进了机器学习的进步，同时这些 技术与传统的数理统计理论相结合，最终促成了数据挖掘的产生。 图1 数据挖掘的形成 1 1 3数据挖掘研究领域 数掘挖掘技术的发展可以说足闩新月异，其中其研究领域主要集中 在以卜- 儿个方而： l 、处理不同类型数据 绝大多数数据庠是关系型的，因此在关系数据库上有效地执行数据 挖掘是至关重要的。但是在不同应用领域中存在不同的数据和数据库， 而且经常包含复杂的数据类型，例如结构数据、复杂对象、事务数据、 历史数据等。出于数据类型的多样性，一个数据挖掘系统不可能处理各 种数据。因此针对特定的数据类型，需要建立特定的数据挖掘系统。 昆明理丁大学钡j ：论文 第一章绪论 2 、数据快照和时间戳 现实数据库通常是庞大、动态、不完全、不准确、冗余和稀疏的， 这给知识发现系统提出了许多难题。数据库中数据的不断变化造成先前 发现的知识很快过时，利用数据快照和时间戳方法可解决这一问题。前 者特别适用于阶段性搜集的数据，但需要额外空间存储快照。数据的不 准确性使知识挖掘过程需要更强的领域知识和更多的抽样数据，同时导 致发现结果的不f 确。例如：缺少单个记录的属性值或缺少关系字段； 以及重复出现的信息( 即冗余信息) ，为避免将对用户毫无意义的函数发 现作为知识发现的结果，系统必须了解数据库的固有依赖。另外数据的 稀疏性和不断增加的数据量增加了知识发现的难度。 3 、数据挖掘算法的有效性和可测性 海量数据库通常有上百个属性和表及数百力个元组。g b 量级数据库 已不鲜见，t b 量级数据库已经出现，高维大型数据库不仅增大了搜索空 间，也增加了发现错误模式的可能性。因此必须利用领域知识降低维数， 除去无关数据，从而提高算法效率。从一个大型数据库中抽取知识的算 法必须高效、可测量，即数据挖掘算法的运行时间必须可预测，且可接 受。指数和多项式复杂性的算法不具有实用价值。但当算法用有限数据 为特定模型寻找适当参数时，有时会导致物超所值，降低效率。 4 、交互性用户界面 数据挖掘的结果应准确地描述数据挖掘的要求，并易于表达。从不 同的角度考察发现的知识，并以不同形式表示，用高层次语言和图形界 面表示数据挖掘要求和结果。目前许多知识发现系统和t 具缺乏与用户 的交疆，难以有效利_ i = j 领域知识，对此可以利用贝叶斯方法和数据库本 身的演泽能力发现知t j 。 5 、在多抽象层i ：交互式挖掘知谚 很难预测从数据库中会挖掘出什么样的知以，因此。个高层次的数 据挖掘查询应作为进步探询的线索。交互式挖掘使用户能交互地定义 个数据挖掘要求，深化数掘挖掘过程，从彳i 同角度灵活看待多抽象层 上的数据挖掘结果。 6 、从不同数据源挖掘信息 局域网、广域网以及i n te r n e t 网将多个数据源联成。个大型分布、 异构的数据库，从包含不同语义的格式化和非格式化数据中挖掘知识是 昆则理t 人学硕士论土 第一章绪论 对数据挖掘的一个挑战。数据挖掘可以揭示大型异构数据库中存在的普 通查询不能发现的知识。数据库的巨大规模、广泛分布及数据挖掘方法 的计算复杂性，要求建立并行分布的数据挖掘。 7 、私有性和安全性 数据挖掘能从不同角度、不同抽象层上看待数据，将影响到数据挖 掘的私有性和安全性。通过研究数据挖掘导致的数据非法侵入，可以改 进数据库安全方法，以避免信息泄漏。 8 、和其它系统的集成 方法功能单一的发现系统的适用范围必然受到一定的限制。要在更 广泛的领域发现知识，系统就应该是数据库、知识库、专家系统、决策 支持系统、可视化工具、网络等技术的集成。 9 ，i n t e r n e t 上的知识发现 从i n t e r n e t 信息的海洋中可以发现大量的新知识，通过已有资源发 现工具可以发现含有关键值的文本。h a n 等人提出利用多层次结构化方 法，通过对原始数据的一般化构造多层次的数据库”“。 1 2 国内外研究现状综述 1 2 1数据挖掘技术的发展现状 研究知识发现( k d d ) 和数据挖掘( d m ) 技术的重大意义已经被人 们广泛的认识，并且被列为数据库研究领域中最重要的课题之一。许多 公司和企业也都充分认识了深层次的分析本企业业务数掘库中的数据能 够带来更多的商业机会，从而可以进一步的掌握和了解顾客的信誉、习 惯和消费心理，以便相应的调整它们的市场策略，拓宽市场。 l9 8 9 年8 月，固际上第一次关j 二数掘挖掘j 知识发现的研讨会在美国 底特律召开。知识发现一训就是在这次会议。j ：讵式形成的。此后，19 9 5 年在加拿大召丌了第届知识发现和数据挖掘国际学术会议 f i n t e r n a t i o n a lc o n f e r e n c eo nd a t am i n i n g & k n o w l e d g ed is c o v e r yi n d a t a b as e ) 。这次会议明确了知识发现的概念，并确定了知识发现过程和 数据挖掘的关系。此后，数据挖掘开始流行。可以晚，数据挖掘是知识 发现概念的深化，数据挖掘是人工智能、机器学习与数掘库技术相结合 的产物。 目前，数据挖掘技术已成为研究的热点。机器学习和数据分析的理 昆明理工大学颂士论文第一章绪论 论及实践成为数据挖掘研究的铺垫。极大的商业应用前景则又极大的推 动数了数据挖掘研究的发展。数据挖掘方法的提出，让人们有能力最终 认识数据的真正价值，即蕴藏在数据中的信息和知识。数据挖掘引起了 学术界的广泛认识，数据挖掘技术所表现出的广泛前景吸引了众多的研 究人员和商业机构。一批数据挖掘系统被开发出来，并在商业、经济、 电信、金融等领域取得了应用性成果。这些系统见证了 自2 0 世纪8 0 年代以来数据挖掘技术的发展。这些系统综合了数据库、专 家系统、模式识别、机器学习、统计学、科学发现和数据分析等领域的 研究成果。但这些系统还停留在试用阶段，在许多方面还有待改善。 1 2 2 数据挖掘技术在电信领域的应用 正如我们在前面所提到的，许许多多的研究人员正努力致力于数据 挖掘的研究。这主要是因为数据挖掘技术有着广泛的应用前景。在北美， 数据挖掘技术已经成功地应用于社会生活的方方面面，如政府管理决策、 商业经营、科学研究以及企业决策支持等领域这些领域都可以采用数据 挖掘技术来解决问题。尤其对于电信和银行这些数据密集型企业，数据 挖掘技术的应用就显得更有意义。 由于竞争的加剧，电信行业似乎从来没有像今天这样急于找寻新的生 机。一方面是过去曾经为电信运营商带来高额利润的传统话音业务价格 不断下调，另一方面是中国电信体制改革为这一市场带来的种种变化。 从宽带到w l a n ，从视讯到v p n ，电信运营商们正努力的尝试着从种种不 同的角度进行突破，寻找新的生机。事实证明数据挖掘技术可以很好的 满足我们这一需求。 随着数据挖掘技术的发展，数据挖掘在电信领域旱有着越来越广泛的 应用空问。具体的应用主要包括以f 几个方面： ( 1 ) 业务预测 预测就是通过对历史数据的分析，找出影响业务发展的因素。 从而对这些因素的未来发展做出预计，大致的确定未来业务量。对 业务的预测是制定今后发展计划的重要依据。通过实际值与预测值 的对比，可以测量预测的准确性，从而更加精确的找到相关因素， 改进预测的方法。由于电信行业的业务种类繁多，因此，应用预测 方法的场合也很多。例如，为了确定未来的市场规模，需要对移动 电话客户的增长做出预测；为了确定下一年的发展目标，需要对各 5 昆明理工太学硕士论文第一章绪论 种业务的增长做出预测；为了改善网络的运营质量，需要根据历史 信息，对未来可能发生故障的设备做出预测。 ( 2 ) 客户呼叫模式分析 对客户呼叫模式进行细致的分析能够使电信运营商更清楚的了 解客户的喜好，其分析结果是电信企业进行市场营销活动的依据。 通过对呼叫模式的分析，运营商可以了解到客户的一些基本特征， 例如，某些客户喜欢在白天打电话，某些客户主要的呼叫对象集中 在某几个电话。通过这些特征，将为分析客户的差异性提供依据， 从而使市场部门有能力对不同客户制定不同的营销策略。 ( 3 ) 大客户的识别 企业的大客户群体往往是利润的主要来源，大客户资源是企业 竞争力的重要体现，也是其他电信运营商争夺的焦点。识别出大客 户，为他们制定有针对性的措施，提高大客户的忠诚度，是电信运 营商继续保持领先的关键所在。此外数据挖掘工具不仅能够根据现 有的消费量的多少来判断用户是否为大客户，还应该可以根据现有 大客户的资料，提取大客户的特征，并发现潜在的大客户。 ( 4 ) 客户群体的细分 客户群体的细分是一对一营销的基础，包括两类方法：分类和聚 类。其中分类分析方法是指事先人为根据客户属性确定分类标准，再 对客户进行归类。聚类分析方法是指系统根据客户属性，使群内客户 具有最大的相同性，群问客户具有最大的相异性，自动产生聚类标准， 在按此标准对客户进行归类。数据挖掘系统应可以在客户群体细分的 基础上进行进一步的细分，知道所需要的粒度，并由此对客户群体进 行舞种分析。 ( 5 ) 客户欠费分析和动态防欺诈 通过数据挖掘，总结各种欺诈、欠费行为的内在规律。并建立一 套欺诈和欠费行为的规则库。当客户的话费行为与该库中规则吻合 时，系统可以提示运营商相关部门采取措施，从而降低运营商的损 失挑险。 ( 6 ) 客户流失的预测与控制 争取一个新客户的代价比留住一个老客户的代价要大得多。由 于关系到市场份额以及营业利润，客户流失预测是电信运营商最为 6 昆明理工大学硕士论文第一章绪论 关心的重点之一。根据已有的客户流失数据，建立客户属性、服务 属性、客户消费情况等数据与客户流失概率相关联的数学模型，找 出这些数据之间的关系，并给出明确的数学公式。然后根据此模型 来监控客户流失的可能性，如果客户流失的可能性过高，则通过促 销等手段来提高客户忠诚度，防止客户流失的发生。这就彻底改变 了以往电信运营商在成功获得客户以后无法监控客户流失、无法有 效实现客户关怀的状况。 ( 7 ) 网络资源的管理 通信网在运行过程中产生了大量的运行数据。对这些数据进行挖 掘，有利于尽早发现潜在的网络故障，提高网络的利用率。 具体来讲，数据挖掘可以应用于以下的网络管理领域： 1 )通信网流量峰值预测 2 ) 故障预测 3 ) 网络流量优化 数据挖掘技术的应用给电信运行商带来了巨大的商业利益的同时， 由于种种原因数据挖掘技术在国内的应用也受到了一定的限制。具体存 在的问题如下： ( 1 )数据质量和完备性：国内电信运营商现有的、面向事务的数捌 在质量、完熬性和。一致性上存在许多问题，必须投入大量的精 力去进行数据的抽取、净化和处理。此外，业务问题的相关数 据有时难以全面收集。例如客，。信用度是客户价值评估中的关 键因素，但由于国内来建立完善的信用体系，无法根据现有客 户数掘建立优质的信川评价模型，从而导致客户价值模型有效 性的降低。 ( 2 )棚艘的人员索质：任数据挖掘f 艇 ：| 过程的多个坏节中，人的主 观辨识和控制是应刚成败的关键，这就对系统使用人员提m 了 搬高的要求。如果没钉具备相应素质的使用和维护人次，必将 导致分析系统与现实脱钩，无法达到预期效果。 ( 3 ) 应用胤期：数据挖掘存在一。个较长的应用周期。技术本身不能 给使用者解决任何问题，只能从数据中把一些潜在的情况呈现 到使用者面前，山使用者采取相应措施。数据挖掘应用的有效 方法是：从一个较小的、关键的问题出发，建立起相对有效的 昆明理工大学硕十论文第一章绪论 模型，并通过应用实践不断检验和完善模型，逐步为使用者解 决问题”3 。 总之。数据挖掘技术在电信领域有着广泛的应用，随着数据仓库的 建设，数据挖掘也正逐渐走向深入，必将为电信运营商提供更多有价值 的信息。 1 3 本文的主要研究内容 本文的主要内容是围绕数据挖掘技术在电信客户细分领域的应用这 一实际问题展开的。主要解决如何使甩数据挖掘技术对电信客户进行合 理的、有效的划分这一问题。并通过两种不同解决方案的研究，找到解 决这一实际应用最好的方法。具体来说本文主要包括以下几个方面内容： l 、 对数据挖掘的相关概念、原理进行介绍。主要包括数据挖掘系 统的组成、数据挖掘的任务。此外，鉴于我们对电信客户细分 时会用到数据挖掘算法中的聚类算法，我们还要对聚类算法的 相关内容进行介绍。主要包括聚类算法的分类、聚类算法所处 理的数据对象等相关基础知识。 2 、 对我们要解决的问题一一电信客户细分这一具体应用进行需 求分析。确定进行数据挖掘所需的数据集，并对所需的数据进 行预处理，提取和转换数据。最终得到我们所需数据汇总表。 3 、 利用k m e a n s 算法对电信客户进行划分，并对得到的结果进行 分析。并通过修改不同的k 值和样本点的个数，对结果进行修 f 。 4 、 利用k m e a ns 算法的一种改进算法模糊c 均值聚类算法再一次 对电信客户进行划分，并对得到的结果进行分析和修j f 。 5 、 最后，对通过两种不同算法得到的结果进行比较，找到解决电 信客户细分这一实际问题的合理方案。 总之，本文下面的所有内容，都是围绕上面所提到的血大方面的内容 展丌的。最终日标通过对聚类算法的比较，得到对电信客户进行聚类的 有效方法。也希望可以对数据挖掘在实际中的应用有所帮助。 昆明理工大学硕士论文第二章数据挖掘技术申的聚类分析 第二章数据挖掘理论研究 2 1 数据挖掘系统组成 由于数据挖掘起源于多个学科，因此数据挖掘研究就产生了大量的、 各种不同类型的数据挖掘系统。典型的数据挖掘系统主要由以下几部分 组成。 数据库、数据仓库或其他信息库：他们是进行数据挖掘的数据 源，是一个或一组数据库、数据仓库、电子表格或其他类型的 信息库。可以在他们的数据上进行数据清理和集成。 数据库或数据仓库服务器：根据用户的数据挖掘要求，数据库 或数据仓库服务器负责提取相关的数据。 知识库：这是特定的领域知识，用于知道搜索或评估结果模式 的兴趣度。 数据挖掘引擎：这是数据挖掘的最重要的基本部分。由一组功 能模块组成，用于特征化、关联、分类、聚类分析以及演变和 偏差分析。 模式评估模块：通常此成分使用兴趣度度量，并与数据挖掘模 块交互，以便将搜索聚集在有趣的模式上。模式评估模块也可 以与挖掘模块集成在一起，这依赖于所用的数据挖掘方法的实 现。 图形用户界面：此模块在用户和数据挖掘系统之问通信，允许 用户与系统交瓦，指定数据挖掘查询或任务，提供信息、帮助 搜索聚焦，根据数据挖掘的中自j 结果进行探索式数据挖掘。此 外，此成分还允许用户浏览数据库和数据仓库或数据结构，评 估挖掘的模式以不同的形式使模式可视化。 典型的数据挖掘系统结构如图2 所示。该图清晰的表示出了数据挖 掘系统中各个功能模块之问的相互作用和依赖关系。 9 昆明理工太学碗士论文第二章数据挖掘技术中的聚类分析 图2 典型的数据挖掘系统结 2 2 数据挖掘发现的知识类型 l 、广义知识( g e n e r a l iz a t i o n ) 广义知识是指类别特征的概括性描述知识。根据数据的微观特性 发现其带有普遍性的、较高层次概念的、中观或宏观的知识，反映同类 事物共同性质，是对数据的概括、精炼和抽象。 广义知识的发现方法和实现技术有很多，如数据立方体、面向属性的 规约等。数据立方体的基本思想是实现某些常用的代价较高的聚类函数 的计算，诸如计数、求和、平均、最大值等。并将这些实现试图存储在 多维数据库中。另一种广义知议发现方法是加拿大s i m 0 1 3f r a s e t 大学提 出的面向属性的规约方法。这种方法以类似s q l 语青表示数据挖掘查询， 收集数据库中的柑关数据集，然后在相关数据集上应用一系列数据推j “ 技术进行数据推广，包括属性删除、属性阀值控制、计数及其他聚集函 数传播等。 2 、关联知议( a ss0 c ia t i0 n ) 它反映一个事件和其他事件之间依赖或关联的知识。如果两项或多项 属性之间存在关联。那么其中一项的属性值就可以依据其他属性值进行 预测。最为著名的关联规则发现方法是r a g r a w a l 提出的叫做a p r io r i 的算法。关联规则的发现可分为两步。首先是迭代识别所有的频繁项目 o 昆明理工大学硕七论文第二章数据挖掘技术中的聚类分析 集，要求频繁项目集的支持率不低于用户设定的最低值；第二步是从频 繁项目集中构造可信度不低于用户设定的最低值的规则。识别或发现所 有频繁项目集是关联规则发现算法的核心，也是计算量最大的部分。 3 、分类知识( c l a s s i f ic a t i o n c 1 u s t e r in g ) 它反映同类事物共同性质的特征型知识和不同事物之间的差异型特 征知识。最为典型的分类方法是基于决策树的分类方法。它是从实例集 中构造决策树，是一种有指导的学习方法。该方法先根据训练子集( 又 称为窗口) 形成决策树。如果该树不能对所有对象给出正确的分类，那 么选择一些例外加入到窗口中，重复该过程一直到形成正确的决策集。 最终结果是一棵树，其叶子结点是类名，中间结点是带有分支的属性， 该分支对应该属性的某一可能值。数据分类还有统计、粗糙集( r o u g hs e t ) 等方法。 4 、预测型知识( p r e d ic t i o n ) 预测型知识根据时间序列型数据，由历史的和当前的数据去推测未 来的数据，也可以认为是以时间为关键属性的关联知识。目前，时间序 列预测方法有经典的统计方法、神经网络和机器学习等。由于大量的时 间序列是非平稳的，其特征参数和数据分柿随时自j 的推移而发生变化。 因此仅仅通过对某段历史数据的训练，建立单一的神经网络预测模型， 还无法完成精确的预测任务。为此，人们提出了基于统计学和基于精确 性的再训练方法。当发现现存预测模型不再适用于当前数据时，对模型 进行重新训练，获得新的权重参数，建立新的模型。 5 、偏差型知识( d e v i a t i o n ) 此外，还可以发现其他类型的知识，如偏差型知识。它是对差异和极 端特例的描述，揭示事物偏离常规的异常现象。所有这些知识都可以在 不i 司的概念层次上被发现，并随着概念层次的提升，从微观到中观、到 宏观，以满足不同用户的不同层次决策的需要。 2 3数据挖掘的任务 数据挖掘最重要的任务是从数据中发现未知的模式。模式有很多种 按功能可以分为两大类：预测型( p r e d ic t i v e ) 模式和描述型 ( d es c r jp t iv e ) 模式。 其中，预测型模式是可以根据数据项的值，精确确定某种结果的模 昆明理工大学硕j ：论文第二章数据挖掘技术中的聚类分析 式。预测型的数据挖掘可以通过当前数据或样本数据进行推断，之后把 推断的结果用于预测；描述型模式是对数据中存在的规则做一种描述， 或根据数据的相似性把数据分组。描述型数据不能直接用于预测，它只 刻画当前数据的一般特性。 在实际应用中根据其实际作用的不同，常把数据挖掘细分为如下几种 模式： ( 1 ) 分类模式：分类模式是一个分类函数。即分类器。它基于对训练 数据集的分析，找出描述区分数据类或概念的模型或函数，并能够使用 该模型或函数把数据集合中未知对象类的数据项映射到某个类上。分类 的结果往往表现为一棵分类树。数据的分类一般分为两个过程：首先， 建立一个模型，描述预定的数据集，通过分析由属性描述的数据库元组 来构造模型；然后，使用该模型进行分类。 基本的分类技术有判定树归纳、贝叶斯分类、神经网络，其它的分类 方法有k 一最临近分类、基于案例的推理、遗传算法、粗糙集和模糊逻辑 技术。 ( 2 ) 回归分析模式：其函数定义与分类模式相似，差别在于分类模式 的预测值是离散值，回归模式的预测值是连续值。许多对连续值建模的 问题都可以用线性回归来解决，对于一些非线性问题，也可通过变量代 换，转化成线性问题加以处理。一元线性回归解决的是两个变量之问的 关系问题，只涉及一个预测变量，而多元线性回归则涉及多个预测变量。 ( 3 ) 时间序列模式：也称为演变分析模式。用于描述对象随时间变化 的规律或趋势，对其建模，并根据数据随时间变化的趋势来预测将来的 值。在进行演变分析时，主要有4 种变化或成分用于特化时序数据： 长期或趋势变化，它用j 二分析较长时间问隔的数据变化，即反映一般的 变化方向；循环变化，它用于反映某种趋势在长时间内呈摆动变化的 一种规律，这种规律町以是周期性的，也可以是非周期性的；季节性 变化，它反映的是每年都重复出现的事件，也就是指连续几年的有关月 份都重复出现同或近似同一的模式；随机变化，它反映的是出于随 机或偶然事件引起的零星时序变化。 时序分析，可以帮助人们选择合适的方法进行分析决策，有助于全 面地理解结果数据。并在较合理的情况下制定出长期或短期的预测。 ( 4 ) 聚类分析模式：聚类分析即把数据划分到不同的组，组问的差别 昆明理工大学颀士论文 第二章数据挖掘技术中的聚类分析 尽可能大，组内的差别尽可能小。所产生的每个组可以看作一个对象类， 由它可以导出规则。聚类分析的基本思想是：一个具有k 个字段的记录， 在知识发现系统中被视为k 维空间的一个点，在用户的参与下，对各个 维施以加权，构造一个k 维空间的距离公式。被分类的对象就像k 维空 间中的天体，然后以距离为原则被划分为星系或星团。同一个对象集合， 不同的距离公式，表达了不同的考察角度，有不同的聚类结果。 与分类不同的是，聚类用于分析数据对象，而不考虑已知的类标记， 进行聚类前并不知道要将训练数据集划分成几个组，也不知道将要划分 成什么样的组，更不知道根据哪些属性来定义组。一般情况下，领域专 家能够理解挖掘结果中每个组的含义。当如果无人能够理解挖掘的结果 时，该产生模式可能是无意义的，可以丢弃并返回上一阶段重新组织数 据。 目前存在大量的聚类算法，算法的选择取决于数据的类型、聚类的目 的和应用的领域等。主要的聚类算法有；k 平均算法、k 中- i i , 点算法、c u r e 算法、b i r c h 算法、d b s c a n 算法、s t i n g 算法、c l i q u e 算法等。 ( 5 ) 关联分析模式：关联分析就是发现数据项之间的关联规则，这些 规则表现了“属性一值”频繁地在给定的数据集中一起出现的条件。关 联分析一般用于购物篮或事务数据分析。 关联规则是形如“) 睁y ”的规则，即为“满足x 中条件的数据库元 组多半也满足y 中条件”。 关联规则的概念是1 9 9 3 年由a g r a w a lr 首次提出的。 近几年。已经提出了许多有效的关联规则挖掘算法，如快速a p r i o r i 算法，直接哈希修剪法d h p ，d i c 算法等等。在关联规则算法改进的同 时，关联规则的概念也得到了极大的拓展，提出了泛化关联规则、多级 关联规则、具有条件限制的关联规则等新概念。同时，关联规则挖掘算 法还与其它方法相结合，也呵产生了良好的挖掘效果，例如，试验表明 把关联规则用于分类任务所构造的分类器，其精度要高于c 4 5 标准分类 器。 ( 6 ) 序列模式；序列模式和关联模式相仿，不同之处在于序列模式把 数据间的关联性与时间联系起来了。为发现序列模式，不仅需要确定事 件是否发生，而且需要确定时间发生的时间和顺序。 在关联规则的挖掘中采用a p r i o r i 特性可以用于序列模式的挖掘，序 昆明理_ 大学颂十论文第二章数据挖掘技术中的聚类分析 列模式挖掘的许多算法都采用了类a p r i o r i 算法的变种：另外可以采用基 于数据库投影的序列模式生长技术。 许多情况下，用户并不明确什么类型的模式适用于自己的数据，会帮 助自己得到有趣的挖掘结果，因此可能希望并行地采用多种不同的挖掘 模式，以产生各种不同的搜索结果，再从中选取有趣的结论。从而，数 据挖掘系统经常同时使用多种模式进行挖掘，以适应各种不同的需求和 应用。其中，分类模式、回归模式、时间序列模式所挖掘出来的知识是 受监督知识，而聚类模式、关联模式、序列模式所挖掘出来的知识是非 受监督知识。受监督知识是指在建立模型前数据的结果已知，可以直接 用来检测模式的准确性，模式的产生是在受监督的情况下进行的。一般 在建立这类模式时，先用一部分数据作为样本，再用另一部分数据来检 验、校正模式。非受监督知识是指在建立模式前结果是未知的，模式的 产生不受任何监督。 此外，数据挖掘系统还应该在不同的抽象层( 即不同粒度) 上发现模 式：同时可以与用户进行交互，允许用户指导有趣模式的发现和搜索。 2 “数据挖掘算法 数据挖掘模型是通过一些算法来创建的。当算法应用于一个数据结 构时，该结构的填充数据从某种意义上来讲反映了存在原始数据集内部 的关联和模式。所以适当算法的选择对于数据挖掘来说是至关重要的。 总体上来说数据挖掘的算法主要分为以下几类。 1 、统计分析 统计分析是应用最早、也是目前最成熟和行之有效的一种数据挖掘 方法。方法的关键是构造合适的统计模型和数学模型来解释被分析的数 据模，。这种方法要求使用者其有较为丰富的领域知识。统计分析一般 由两大步骤构成：首先，使用者从数据仓库或其他数据源中选择抽取适当 的数据。第：，使用者执行统计分析工具中提供的可视化功能和分析功能 柬寻找数据日j 的关系，并构造统计模型和数学模型来解释数据。其中第二 步是反复的和刁i 断求精的。 2 、关联分析和顺序分析 关联分析的作用是在数据仓库的条目或对象问挖掘出满足一定条件 的依赖性关系，它展示出数据间未知的依赖关系，并有可能描述成关注数 昆硝理工大学顸士论文第二章数据挖掘技术中的聚类分析 据项间的因果关系。因此，关联分析常被用来分析顾客的购买模式、产品 生产模式等。 3 、决策树 计算机科学中广泛应用树形结构来组织和描述数据，同样，可以应用 树形结构来描述决策过程。决策树分析就是利用树形结构来建立决策规 则。进而进行决策的方法。决策树分析通常被用于诸如商场定位、产品定 位、贷款风险分析等场合。决策树分析首先利用决策树算法建立决策树， 可称之为“学习”或“训练”阶段。算法寻找历史数据库中具有最大信 息量的属性，构造出树根，再根据属性取值大于( 等于) 或小于树根的属性 值建立树的分支，如此下去，直到所有的属性( 或用户指定的所有属性) 都 被用于树形结构中为止。再根据历史经验将决策树转化为规则，即对每一 个树叶结点得出决策规则。然后，利用决策规则对新事例进行分类，即根 据新事例各属性的取值将其归入最接近的树叶结点，并利用决策规则做 出相应决策，同时调整决策树和决策规则。 4 、聚类 聚类分析主要是根据事物的特征对其进行聚类或分类，分析基于“物 以类聚”的朴素思想。以期从中发现规律和典型模式。当要分析的数据缺 乏描述信息，或者是无法组织成任何分类模式时，利用聚类分析可以自动 将数据按某些特征划分成几类。聚类分析问题的实质是一个全局最优问 题，常用于市场细分、目标顾客定位、业绩评估等多方面。 5 、遗传算法 遗传算法是所有的知识发现方法中人们理解最少的一种方法。它以 模仿生物进化过程为基础，就如同进化是产生较优的生物种类一样，遗传 分析应用搜索技术，先找出两个合适的父样本，通过“交叉”、“变异”等 带有生物遗传特j _ 的操作产生下一代样本，对予样本反复“交叉”、“变异” 操作直到予样本收敛为止，再找另外两个合适的父样本熏复上述过程，这 样，就能得到下一代的样本集。由此得到当前样本集较可能的发展方向一 子样本集。遗传分析常被用东做预测，也被用作如下用途：当某个样本的 属性空缺时，对其它样本应用遗传分析得出可能值，并用来取代空缺属 性。1 6 、神经网络算法 神经网络被设计成复制自然界中的神经网络，它由许多神经元所组成 昆明理工大学硕士论文第二章数据挖掘技术中的聚类分析 通过学习大容量数据中的模式来组织神经元，即用带有一定权重的“导线” 连接神经元以形成网络模型。通常，神经网络由输入、中间层和输出三个 层次构成。每一个神经元在接受了各种输入后，再计算总输入值，由过滤机 制( 例如阀值) 比较总输入，然后确定它自己的输出值。神经网络通过分层 组织和互联每层中的神经元来模型化复杂行为。当修改连接层与层之自j 、 神经元与神经元之间的连接权重时，神经网络就进行了学习或“训练”。经 过“训练”的神经网络可用于预测现有事例可能带来的结果，也可应用于 诸如分析客户关系等领域。 可以说，数据挖掘算法是数据挖掘的核心问题。不管如何使用数据 挖掘技术，最关键的问题就是算法的选择与实现。多年以来，许许多多 研究人员都致力与数据挖掘算法的研究工作。并取得了显著的成果。下 面我们将对数据挖掘算法中的聚类分析算法进行研究和探讨。由于我们 在下面的具体应用中将具体使用到聚类算法，所以在下面一节中我们将 具体详细的介绍聚类算法。 2 5 数据挖掘中的聚类分折算法 聚类分析是数据挖掘中的一种主要技术，是把一组个体按照相似性 分成若干类别。即“物以类聚”。它的目的是使得属于同一类别的个体之 间的距离尽可能的小，而不同类别上的个体间的距离尽可能的大。聚类 和分类之间的不同就在于：分类问题中我们知道训练例的分类属性，而 在聚类中就需要我们在训练例中找到这个分类属性值。聚类方法包括统 计方法、机器学习方法、神经网络方法和面向数据库的方法。 在统计方法中，聚类又称聚类分析，它是多元数据分析的三大方法 之- ( 其它两种是吲归分析和判别分析) 。它主要研究基于几何距离的聚 类：如欧式距离、明考斯基距离等。传统的统计聚类分析方法包括系统 聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和 模糊聚类等。 在机器学习中聚类称为无监督或无教师归纳。因为和分类学习相比 分类学习的例子或数据对象有类别标记，而聚类的例子则没有类别标记， 需要由聚类学习算法来自动确定。机器学习领域中的概念聚类算法通过 符号属性来进行聚类，并得出聚类的概念描述。当聚类对象可以动态增 加时，概念聚类则称作概念形成。概念聚类由两部分组成( 1 ) 发现合适 1 6 昆明理工大学硕士论文第二章数据挖掘技术中的聚类分析 的类；( 2 ) 形成对每个类的描述。 在神经网络中，有一类无监督学习方法，自组织神经网络方法；如 k o h o n e n 自组织特征映射网络、竞争学习网络等等。神经网络中的s o m 方法通过反复的学习来聚类数据，它由输入层和竞争层组成。输入层由1 1 个输入神经元组成，竞争层由m n = m 个输出神经元组成，且形成一个 二维平面阵列。输入层各神经元与竞争层各神经元之间实现交互连接。 矢量量化v q 方法中的l b g 方法只能对数值属性进行聚类，通常的做法 是将所有要识别矢量的集合分成若干子集，各子集中的矢量具有相似特 征，因而能用一个具有代表性的矢量来表示。该具有代表性的矢量称 为码字，全部码字的集合称为码本。 聚类分析问题可描述为：给定m 维空间r “中的n 个向量，把每个 向量归属到s 聚类中的某一个，使得每个向量与其聚类中心的“距离” 最小。聚类分析问题的实质是个全局最优问题。在这里，m 可认为是 样本参与聚类的属性个数，1 1 是样本的个数，s 是由用户预先设定的分类 数目。 定义对于m 维空问r “中的向量 x i ，x j ，x j = x i i ，x i 2 x i m ) ，x j = x j l ，x j 2 x j m ) ， 向量x i ，x j 之间的距离为： d ，= 数据聚类正在蓬勃发展，有贡献的研究领域包括数据挖掘、统计学、 机器学习、守问数据库技术、生物学、以及市场营销。由于数据库中收 集了人最的数据聚类分析已经成为数据挖掘研究领域巾个非常活跃 的研究课题。 2 5 1 聚类算法的分类 随着数据挖掘研究的深入，出现了很多的聚类算法。常见的聚类算法 有五大类。即划分法、分层法、基于密度的方法、基于网格的方法和基 于模型的方法。 l 划分方法( p a r t i t i o n in gm e t h o d ) 给定要构建的划分的数目k ，创建一个初始划分。每个划分表示一个 簇，每个簇至少包含一个数据对象，同时，每个数据对象只能属于一个 一计 一 一 一 一。揣 昆明理工人学硕：l 论史 第二章数据挖掘技术中的聚共分析 簇( 模糊聚类种可放宽约束) 。然后采用一种迭代的重定位技术，尝试通 过对象在划分间移动来改进划分，直到以局部最优结束。一个好的划分 的准则是：在同一类中的对象之间尽可能“接近”或相关，而不同类中 的对象之间尽可能的远离或不同。 最著名与常用的划分方法是k - m e a l l s 、k - m e d o i d s 以及它们的变种。 2 层次方法( h ie r a r c h i c a lm e t h o d ) 层次式聚类算法对给定数据对象集合进行层次的分解，根据层次分解 形成的方向又可以分成凝聚式和分列式两种。前者采用自底向上的方法， 先将每个对象归为单独底组，然后逐渐合并相近的对象或组，直到所有 的组合并为一个( 层次