（计算机软件与理论专业论文）一种kdd算法及其应用研究.pdf

摘要 在过去的3 0 年中，计算机硬件稳定的、令人吃惊的进步导致了功能强大的 计算机、数据收集设备和存储介质的大量供应，这些技术大大推动了数据库和信 息产业的发展，使得大量数据和信息存储用于事务管理、信息检索和数据分析。 由于数据量的剧增，对于隐含在数据中信息的理解已经远远超出了人的能力，这 就是所谓的“数据丰富，但知识贫乏”现象。于是，用数据库管理系统来存储数 据，用机器学习的方法来分析数据，挖掘大量数据背后的知识，这两者的结合促 成了数据库中的知识发现( k d d ：k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ) 的产生。 实际上，数据库中的知识发现是一门交叉性学科，涉及到机器学习、模式识别、 统计学、蟹能数据库、知识获取、数据可视化、高性能计算、专家系统等多个领 域。它是“从大量数据中提取出可信的、新颖的、有效的并能被人理解的模式的 非平凡过程”。通过k d d ，人们可以将知识发现的研究成果应用于实际数据处理 中，为科学决策提供支持。k d d 系统中的知识学习阶段被称为“数据挖掘”( d a t a m i n i n g ，d m ) ，它的算法是k d d 系统的核心。 本文立足于k d d 知识学习过程( 数据挖掘) ，侧重于对数据挖掘算法特别 是神经网络自组织映射图( s o m ) 、结合数理统计知识，提出一种切实可行的 k d d 聚类算法，d a s o m ，并以类j a v a 语言实现，对海量数据在无指导学习的 基础上进行自动聚类。最后，以电信行业客户呼叫行为分析、客户分群等应用为 背景，论证这种算法在实际应用中的价值。 通过在中国电信实际生产系统中的应用，已经基本证明本文提出的聚类算法 相对于现有基于s o m 的传统算法来说，具有动态结构、参数自调节、对不稳定 数据集的学习机制和层次化的聚类等特点和优势，值得在今后的学习和工作中继 续深入研究。 关键词：k d d ，神经网络，聚类，d a s o m ，客户呼叫行为分析，客户分 群 址誊t r a 蛆 i nt h ep a s tt h i r t yy e a r s ，t h es t e a d y ，s t a r t l i n gd e v e l o p m e n t 篚c o m p u t e rh a r d w a r eh a s r e s u l t e di nal a r g es u p p l yo fp o w e r f u lc o m p u t e r s ，d a t a c o l l e c t i n gd e v i c e sa n ds t o r a g e m e d i a t h e s et e c h n i q u e sh a v eg r e a t l ya c c e l e r a t e dt h ea d v a n c e m e n to fd a t a b a s ea n d i n f u r m a t i o ni n d u s t r y , w h i c hp r o d u c e dag r e a td e a lo fd a t aa n di n f o r m a t i o nc o n d u c i n g t ot r a n s a c t i o nm a n a g e m e n t ，i n f o r m a t i o nr e t r i e v a la n dd a t aa n a l y s i s b e c a u s eo fg r e a t d a t aq u a n t i t y , i t sf a rb e y o n dt h ea b i l i t yo fh u m a nt ou n d e r s t a n dt h ek n o w l e d g eh i d d e n i nd a t a , w h i c hi st h ep h e n o m e n o nk n o w na sr i c hi nd a t ab u ts h o r ti nk n o w l e d g e t h u s d a t a b a s em a n a g e m e n ts y s t e mf o rd a ms t o r a g e ，i nc o m b i n a t i o nw i t hm a c h i n el e a r n i n g f o rd a t aa n a l y s i st om i n et h ek n o w l e d g eb e h i n dg r e a ta m o u n to fd a t a ，g a v eb i r t ht o k n o w l e d g ed i s c o v e r y i nd a t a b a s e ( k d d ) i nf a c t ，k d di sac r o s s s u b j e c tr e l a t i n gt om a c h i n el e a r n i n g ，p a t t e r nr e c o g n i t i o n ， s t a t i s t i c s ，i n t e l l i g e n td a t a b a s e ，k n o w l e d g ea c q u i s i t i o n ，d a t a v i s u a l i z a t i o n ，h i g h p e r f o r m a n c ec o m p u t i n g a n de x p e r t s y s t e m ，e t c i t s t h en o n t r i v i a lp r o c e s so f i d e n t i f y i n gv a l i d ，n o v e l ，p o t e n t i a l l yu s e f u l ，a n du l t i m a t e l yu n d e r s t a n d a b l ep a t t e r ni n d a t a b yk d d ，w e c a na p p l yt h ek n o w l e d g et op r a c t i c a ld a t ap r o c e s s i n g ，s u p p o r t i n g s c i e n t i f i cd e c i s i o n t h ep h a s eo fk n o w l e d g el e a r n i n gi nk d d i sc a l l e dd a t am i n i n g ( d m ) ，w h o s ea l g o r i t h mi sc o r e o fk d d s y s t e m t h i sp a p e ri sb a s e d o n p r o c e s s o fk n o w l e d g el e a r n i n gi nk d d ，e m p h a s i z e s p a r t i c u l a r l y o nd ma l g o r i t h m ，e s p e c i a l l y o na r t i f i c i a ln e u r a ln e t w o r k ss u c h a s s e l f - o r g a n i z e df e a t u r em a p ，a n di s c o m b i n e dw i t hm a t h e m a t i c a ls t a t i s t i c s w ep u t f o r w a r daf e a s i b l ek d dc l u s t e r i n ga l g o r i t h m ，d a s o m ，i m p l e m e n t e di na n a l o g o u s j a v a ，a n dt h i sa l g o r i t h mi sh e l p f u lt oa u t o m a t i cc l u s t e r i n gb yn o n s u p e r v i s e dl e a r n i n g f i n a l l vw ed r o v et h ev a l u eo fd a s o mi np r a c t i c a la p p l i c a t i o nb yi l l u s t r a t i n g a p p l i c a t i o n s o fc u s t o m e rc a l l i n gb e h a v i o ra n a l y s i sa n dc u s t o m e rs e g m e n t a t i o n 1 n t e l e c o mi n d u s t r y t h r o u g ha p p l i c a t i o ni np r o d u c t i o ns y s t e mo fc h i n at e t e c o r n ，w ea r g u e b a s i c a l l y - c o m p a r e dw i t he x i s t i n gs o m s a l g o r i t h m s t h a tc l u s t e r i n ga l g o r i t h mi nt h i sp a p e r h a s f e a t u r eo ra d v a n t a g eo fd y n a m i cs t r u c t u r e ，p a r a m e t e rs e l fa d j u s t m e n t ，n o n s t e a d yd a t a s e tl e a r n i n ga n dh i e r a r c h i c a lc l u s t e r i n g ，w h i c hi sw o r t hf u r t h e rr e s e a r c hi ns t u d ya n d w o r ki nf u t u r e k e y w o r d s ：k d d ，n e u r a ln e t w o r k s ，c l u s t e r i n g , d a s o m ，c u s t o m e rc a l l i n gb e h a v i o r a n a l y s i s ，c u s t o m e rs e g m e n t a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： ! 造t 。造 日期：0 j 年# 月矗日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：弦腑_导师签名： 日期：a 皇 电子科技大学硕士学位论文 1 1 研究背景 第一章引言 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数 据越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更 高层次的分析，以便更好地利用这些数据。传统的关系型数据库系统可以商效地 实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无 法根据现有的数据预测未来的发展趋势。让我们回头来看一个事实：纽约时报 由6 0 年代的1 0 2 0 版扩张至现在的1 0 0 2 0 0 版；北京青年报也已是1 6 4 0 版。现在入均日阅读时间通常为3 0 4 5 分钟，只能浏览一份2 4 版的报纸。 在商业上，随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积 累的数据越来越多，动辄以t b 计。总体来说，目前l t 业界普遍缺乏挖掘数据 背后隐藏的知识的手段，导致了“数据丰富，但知识贫乏”的现象。这样收集在 大型数据库系统中的数据变成了“数据坟墓”难得再访问的数据档案，重要 的决定常常不是基于数据库中信息丰富的数据，而是基于决策者的直觉，因为决 策者缺乏从海量数据中提取有价值知识的工具。此外，考虑当前的专家系统技术， 通常，这种系统依赖于用户或领域专家人工地将知识输入知识库，这一过程常有 偏差和失误，并且既耗时又耗费用。人们期待有一种高效地发现海量数据存储中 的有价值知识的系统来帮助企业和研究机构作出正确的判断，将“数据坟墓”变 成“数据金块”。 从上个世纪末开始出现的一种数据库结构称为数据仓库，这是种多个数据 源在单个站点以统一模式组织的存储，以支持管理决策。数据仓库技术包括数据 清理、数据集成和联机分析处理( o l a p ) 。o l a p 是种分析技术，具有汇总、 合并和聚集功能，以及从不同的角度观察信息的能力。尽管o l a p 工具支持多维 分析和决策，在发现海量数据背后的知识方面迈出了可喜的一步，但对于深层次 的分析功能，如数据分类、聚类和发现数据随时间变化的特征，仍然需要其他分 析工具。其实，从1 9 8 9 年8 月在美国底特律召开的第1 1 届国际人工智能联合会 议的专题讨论会上就首次出现了k d d ( k n o w l e d g ed i s c o v e r y i nd a t a b a s e s ，数据 库中的知识发现) 这个术语。随后在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年都举行了k d d 专题讨论会，汇集来自各个领域的研究人员和应用开发者，集中讨论数据统计、 第】页 电子科技大学硕士学位论文 海量数据分析算法、知识表示、知识运用等问题。随着参与人员的不断增多， k d d 国际会议发展成为年会。k d d 系统包括了数据预处理、数据选择、数据变 换、数据挖掘、模式评估、知识表示多个阶段，其中的知识学习阶段被称为“数 据挖掘”( d a t am i n i n g ，d m ) ，它的算法是k d d 系统的核心。在多种学术著作 及期予u 中，为了专注于核心的研究并方便表述，其实已经将“数据挖掘”作为了 “数据库中的知识发现”的同义词( 本文中也将k d d 和d m 视为同一个名词) 。 1 9 9 8 年在美国纽约举行的第四届知识发现与数据挖掘国际学术会议不仅进行了 学术讨论，并且有3 0 多家软件公司展示了他们的数据挖掘软件产品，不少软件 已在北美、欧洲的多国得到应用。在我国，许多研究机构已进行较长时间的数据 挖掘技术的研究，但还没有看到数据挖掘技术在我国成功应用的大型系统的典型 案例；不过，在银行业和电信业中，由于信息化程度较高，已经存在实施k d d 的应用需求和前提，中国移动在近年来依据t m f o r u m ( 国际电信论坛) 提出的 n g o s s 建设b o s s 系统的前提下，开始了数据挖掘应用系统的建设，并取得了 初步的成就。 1 2 相关工作 正如上文所述，k d d 已成为近十多年来计算机应用研究方面的热点，全世 界出现了成千上万的关于k d d 的研究方面的论文。k d d 作为一门交叉性学科， 与机器学习、模式识别、统计学、智能数据库、知识获取、数据可视化、高性能 计算、专家系统等密切相关。在从事本文相关的主要研究工作的同时，本人搜集 了与本文提出的k d d 聚类算法相关的最新研究成果，它们包括：机器学习( 特 别是神经网络) 的最新进展，数据仓库应用系统的设计、开发和部署，遗传算法 与神经网络的结合，k d d 过程和功能，数据挖掘算法，电信行业增强业务映射 图( e t o m ) 等，对其中有助于算法研究和应用研究的部分做了简单的总结。 1 3 研究目的、内容、重点和创新点 本文的研究目的十分明确，就是在分析现有的各种聚类算法的基础上，提出 一种有价值的动态适应、自动聚类算法，并应用到电信行业的具体业务中。 在国外，数据挖掘在电信行业已经有较多的研究和成功应用，但在国内，这 方面的研究还大有作为，主要基于以下几点事实： 1 )从前在电信行业的应用研究主要针对数据仓库，还停留在使用已 第2 页 电子科技大学硕士学位论文 知规则来分析数据的初级阶段，真正能够使用数据挖掘技术自动高效地挖掘 知识的应用极少； 2 ) 从前的研究大多数是使用别人已有的算法，是纯粹的应用研究， 缺乏理论创薪： 3 ) 我们国内对这方面的研究属于刚刚起步的阶段，国外在这方面已 经大大地超前于国内，我们希望本研究能够结合我国国情，为加强与提高数 据挖掘技术在我国电信行业中的应用起到一点推动作用。 因此，本文有针对性地将重点放在了聚类算法的研究，电信行业的应用之上， 也就是本文的第四、五两章，这两章也是本文的难点所在。 本文的主要创新点在于( 1 ) 分析并结台自组织映射神经网络的特点，提出 了一种新的聚类算法并加以实现；( 2 ) 针对国内电信行业业务支撑系统的特点， 以中国电信当前正在建设的综合营帐系统为背景，提出了适合于客户行为分析、 客户群细分的数据挖掘模型。 1 4 论文的研究方法和组织结构 本文采用理论与实际相结合，定性与定量相结合的研究方法，在阅读大量文 献的基础上，将算法研究与实验数据以及业务数据结合进行挖掘分析；同时在定 性研究的基础上，大量结合定量分析手段，以期提出切实可行的创新算法。 本文共分为六章。 第一章，引言，简要阐述本文的研究背景，研究工作在国民经济中的实用价 值与理论意义；本研究主题范围内国内外已有的文献综述以及论文所要解决的问 题。 第二章，数据库中的知识发现( k d d ) 综述。简单阐述k d d 的发展历程， k d d 的主要过程和功能，并重点分析现有的聚类算法，指出各种方法的优缺点。 第三章，人工神经网络( a n n ) 。简要阐述人工神经网络的发展历程，仅对 本文需要使用的自组织映射图( s o m ) 神经网络做重点分析。 第四章，提出一种基于自组织映射图神经网络的聚类算法，详细说明算法的 特性、流程、性能，并给出此算法的实现代码。此章是本文的重点内容，也是主 要的难点和创新点所在。 第五章，在前一章提出算法的基础上，具体阐述该算法在真实的电信行业业 务支撑系统中的实现过程，并以大量的数据说明该算法的成效。此章是本文的重 点内容，也是主要的刨新点所在。 第3 页 电子科技大学硕士学位论文 第六章，总结和展望。阐述了本文提出的算法中几个尚需改进之处简要提 出了下步工作中应该关注的重点。 第4 页 电子科技大学硕士学位论文 第二章数据库中的知识发现( k d d ) 综述 2 1k d d 简介 在本节中我们简单地回顾一下k d d 的发展过程。 2 1 1k d d 的定义 对k d d 最权威的定义是由f a y y a d 等人做出的：“t h en o n t r i v i a lp r o c e s so f i d e n t i l y i n gv a l i d 、n o v e l 、p o t e n t i a l l yu s e f u l ，a n du l t i m a t e l yu n d e r s t a n d a b l ep a t t e mi n d a t a ”，其流程和步骤是：先理解要应用的领域、熟悉相关知识，接着建立目标 数据集，并专注所选择( s e l e c t i o n ) 的数据子集；再从目的数据中作预处理 ( p r e p r o c e s s i n g ) ，去除错误或不一致的数据；然后作数据简化与转换工作 ( t r a n s f o r m m i o n ) ；再经由“d a t am i m n g ”的技术程序成为模式( p a t t e r n s ) 、做 回归分析或找出分类型态；最后经过“i m e r p r e t a t i o r d e v a l u a t i o n ”成为有用的知识。 这些程序是一个循环的关系，一直重复的步骤，最后才得到一些有用的知识。所 以，k d d 是一连串的程序，d a t am i m n g 是其中的最重要的一个步骤。也有人将 k d d 称为“资料考古学”( d a t aa r c h a e o l o g y ) 、“数据模式分析”( d a t ap a t t e m a n a l y s i s ) 或“功能相依性分析”( f u n c t i o n a ld e p e n d e n c ya n a l y s i s ) 。不论以何 种形式出现，但现在对这些概念都己形成个共识，即认为他们是结合数据库系 统与机器学习技术的重要领域，许多产业界人士也认为此领域是一项增加各企业 潜能的重要指标。正如前文所述一样，我们将在本文中不断地提及“数据挖掘” 和“数据库中知识发现”两个术语，为统一起见，并有利于我们专注于对本文核 心算法的研究，在下文中，我们将正式把“数据挖掘”d m 和“数据库中知识发 现”k d d 作为同一个名词对待。更多的关于定义方面的争论，留给产业界、媒 体等去进行。 2 1 2k d d 的发展历史 到目前为止，我们还没有对k d d 的历史进行过详细的寻根，现在我们不妨 通过“图】k d d 的发展历史”来认识一下k d d 的发展历程。 图中所列与k d d 相关的领域，主要有数据库理论、数学理论和人工智能三 方面，其实，由于k d d 得益于多个学科，是一门交叉性很强的学问，所以我们 还会在很多学术期刊及论坛上看到对于k d d 发展有贡献的其他相关学科，这不 第5 页 电子科技大学硕士学位论文 足为奇。本图中列出的是理论界有较高认同度的一种看法，并不排斥其他说法的 存在。 2 2k d d 过程 1文件管理1 匝蓟 厂面矗i 【人工智能 e 匠巳虹 j ，。一 _ 二= j 置p = 二 l k d d l 图1k d d 的发展历史 正如定义中所说的一样，y j d 是一连串的过程的总和，以下我们将简要阐 述这些过程的含义及作用。根据本人在实际的研究和应用中的经验，我将f a y y a d 等人对k d d 所定义的过程进行了扩充和改进。我认为k d d 应该包含以下五大 过程： 问题定义与主题分析 数据准备 数据挖掘 模式评估 知识表示和知识管理 2 2 1 问题定义与主题分析 开始k d d 其他步骤前必须针对具体应用进行问题定义和分析，这包括了应 用中的各种知识和应用目标。阃题定义是了解相关领域的有关情况，熟悉背景知 识，弄清用户要求。清晰她定义出业务问题，认清k d d 的目的是k d d 最重要 的第一步，如果此步出错，以后的工作都将是徒劳。开始真正的数据挖掘之前最 先也是最重要的就是了解用户的数据和业务问题，精确定义所要解决的问题是数 据挖掘成功的关键要素之一。在确定用户的需求后，应对现有资源如已有的历史 数据进行评估，确定是否能够通过数据挖掘技术来解决用户的需求，然后将进一 步确定数据挖掘的目标和制定数据挖掘计划。 数据是数据挖掘工作成败的基础，因此，分析主题的任务包括对数据进行进 第6 页 电子科技大学硕士学位论文 一步的理解，如确定数据挖掘所需要的具体数据，对数据进行描述，检查数据的 质量等。理解相应的问题领域是设法发现任何有用信息的前提。数据挖掘不会在 缺乏指导的情况下自动地发现知识。数据挖掘永远不会替代有经验的商业分析师 或管理人员所起到的作用。数据挖掘需要有一个明确的主题目标，该主题目标决 定了此后数据挖掘的各种操作，并且在数据挖掘过程中是可修正的，但其基本原 则内容要保持稳定。在k d d 过程中，面对不同的用户需要制定不同的主题，主 题是一个在较高层次将数据归类的标准，每一个主题对应一个宏观的分析领域， 即将不同的主题按照一定的标准集成，将原始数据结构进行从面向应用向面向主 题的转变。 2 2 2 数据准备 数据准备包括两个方面，一是从多个数据源去整合所需要的数据，保证数据 的综合性、易用性、数据质量和时效性，这就需要用以数据仓库( d a t a w a r e h o u s e ) 的思想和技术；另一方面就是如何从现有数据中衍生出所需要的指标，这主要取 决于数据挖掘者的分析经验和工具的方便性。 数据准备包括了数据的抽取、清洗、转换和加载( e c t l ) ，具体可描述为数 据清洗( 或清理) 、集成、选择、变换、归约、质量分析等步骤。 2 。2 - 2 。1 数据清洗 数据清洗是在数据中消除错误和不一致，并解决对象识别问题的过程，包括 空值处理、噪声数据处理和不一致数据处理等。数据的不一致导致数据挖掘结果 的可信度降低，数据清理去除噪声或无关数据，并处理数据中缺失的数据域。 数据清洗主要是针对多个数据源中的数据的不规范性、二义性、重复和不完 整等问题，对有问题的数据进行相应的清洗操作，例如，关于“高薪”和“低收 入”的含义在不同的数据集中可能有不同的定义，在一个数据集中“高薪”的人 在另一个数据集中则可能不是，因此所挖掘的的数据必须有一致的含义。 数据清洗首先要将数据值进行标准化，即相同含义的值应具有统一的形式。 如人员的出生地在不同的数据源中可能分别使用“北京”、“京”、“北京市”、 “b e i j i n g ”、“p e k i n g ”等表示方法，因此应将这类值统一表示。标准化的另一个 问题是外观形式完全一样的数据如“2 0 0 3 ”，在不同的数据源中可能是不同的数 据类型( 数值型和字符串型) ，因此必须在确认他们的确是同一数据后，转换为 相同的数据类型。 数据清洗必须处理数据的致性问题，如人员的联系信息在地址域的值为 第7 页 电子科技大学硕士学位论文 “电子科技大学”，而在相应的邮编域值为“6 1 0 0 4 1 ”，则记录的数据存在不一致， 因为“电子科技大学”的邮编应为“6 1 0 0 5 4 ”，假如存在一个标准的地址和邮编 的对应表，则可对记录中的邮编自动更正。当然，这需要结合定的业务规则， 因为也有可能邮编的值正确而地址填写错误了。手工进行数据一致性的确认的时 间、金钱开销很大，只适用于小规模的数据对于大数据集通常都需要自动的数 据清洗。数据错误的自动清洗主要包括以下三个步骤：( 1 ) 定义并测定错误类型， ( 2 ) 搜寻并识别错误实例，( 3 ) 纠正发现的错误。 对于含空值比例较小的数据集，删除空值的数据记录不失不一种有效的方 法。然而当空值达到一定的比例时，如采用直接删除方法将大大减少数据集中的 记录，从而将可能丢失大量信息。因此，空值是数据清洗的一项重要内容和难点。 补全空值的方法有如下一些：( 1 ) 均值替换法：计算数据集中空缺值域属性的平 均值并用该值替换空值；( 2 ) 专家经验法：业务领域专家制定相应的领域规则， 然后根据这些规则推测空值处应有值；( 3 ) c o l dd e c k 猜测：根据以往分析中所 得的数据取代空值；( 4 ) 回归分柝法：利用回归分析方法分析空值属性和其他属 性的关系，从而推测空值的取值；( 5 ) 数据挖掘法：使用数据挖掘技术，通过已 有的数据集预测空缺值的可能取值。 2 2 2 2 数据集成 数据挖掘需要对数据进行集成，也就是将多个数据源中的数据台并存放在一 个统一的数据存储中。数据集成将多数据源中的数据进行合并处理，解挟语义模 糊性并整合成一致的数据存储。涉及三个方面的问题。 模式集成：模式集成从多个异构数据库、文件或遗留系统( 1 e g a c y ) 提取并集成数据，解决二义性，统一不同格式的数据，消除冗余、熏复存放 数据的现象。因此，模式集成涉及实体识别，即如何表示不同数据库中的字 段是同一个实体，如何将不同信息源中的实体匹配来进行模式集成，通常借 助于数据库或数据仓库的元数据进行模式识别，帮助避免模式集成中的错 误。此外还涉及异构数据的转换问题和数据类型的选择问题。 冗余：数据集成往往导致数据冗余，如同一属性多次出现、同一属 性命名不一致等。对于属性间冗余可以用相关分析检测到，然后将其删除。 数据值冲突的检测与处理：由于表示、比例、编码等不同，现实世 界中的同一实体，在不同数据源中的属性值可能不同，这种数据语义上的歧 义性是数据集成中的最大的难点。 第8 页 电子科技大学硕士学位论文 2 2 2 3 数据选择 数据挖掘通常并不需要使用所拥有的所有数据，有些数据对象和数据属性对 建立模型获得模式是没有影响的，这些数据的加入会大影响挖掘效率，甚至还可 能导致数据挖掘结果的偏差。因此，有效地选择数据是很有必要的。数据选择有 时也称为数据取样或数据简化。 数据选择是在对发现任务和数据本身内容理解的基础上，寻找依赖于发现目 标的表达数据的有用特征，以缩减数据规模，从而在尽可能保持数据原貌的前提 下最大限度地精简数据量。通过数据选择可咀合得数据的规律性和潜在特性更加 明显。 在缩减数据规模的同时，数据选择应完整，需要覆盖业务目标所涉及的相关 数据。数据选择过程将搜索所有与业务对象有关的内部和外部数据信息，并从中 选择出适用于数据挖掘应用的数据。数据选择包括属性选择和数据抽样，即在数 据源中选择：( 1 ) 数据域：也称“字段”或“列”；( 2 ) 元组：也称“记录”或 “行”。针对特定的数据挖掘应用，并不是数据中的所有项都有用，无用的属性 数据对数据挖掘是有害的。因为不相关的数据五方面会增加数据挖掘计算的时间 和空间开销，另一方面可能导致错误的结果。 选择记录与选择数据域类似，一方面是考虑到计算开销的问题，另一方面选 择高质量的有代表性的记录进行挖掘，通常会取得更好的挖掘结果。数据选择需 要在相关领域和专家知识的指导下，辨别出需要进行分析的数据集合，缩小挖掘 范围，避免盲目搜索，提高数据挖掘的效率和质量。 2 2 2 4 数据变换 数据变换包括( 1 ) 数据离散化：将属性( 如数量型数据) 离散化成若干区 间。( 2 ) 新建变量：很多情况下需要从原始数据中生成一些新的变量作为预测变 量。( 3 ) 转换变量：例如将学生的考试成绩由百分制映射为五分制。( 4 ) 拆分数 据：依据业务需求对数据项进行分解。如将邮件地址信息分解为国家、省州、 城市、邮政编码、街道和f q 牌号码等。( 5 ) 格式转换：规范化数据格式，如定义 时间、数值、字符等数据加载格式。 将数据进行离散化，有许多不同的方法。( 1 ) 等宽方法：等宽方法将数据的 取值范围按等距离划分成若干区间，然后将落在区间内的数据映射为相应的离散 值。等宽方法比较简单，直观，但存在两个比较明显的缺点，一是很难有效地体 现数据的实际分布情况，二是划分边界过硬。( 2 ) 等深方法：等深方法按照数据 的个数将数据划分为不同的组，各组的数据个数近似相同，等深方法划分的区间 第9 页 电子科技大学硕士学位论文 ( 组) 可能无实际意义，并可能将数据相关很远的值放在一组。( 3 ) 等数据语义 距离：等数据语义距离按数据的语义距离将数据划分为不同的组。如将人员按“儿 童”、“青少年”、“中年”、“老年”划分为若干组，而不是等宽方法按年龄值的大 小划分为e o ，2 0 、 2 0 ，4 0 3 、 4 0 ，6 0 ；如按年龄将人员排序，然后按人数的 多少分成人员相等的组，则是等深方法。 显然，基于数据语义距离的划分既考虑整个范围内数据的分布稠密性，也考 虑各组内数据的接近性。等数据语义距离方法可以产生更有语义意义的离散化， 但如何合理地度量语义距离及定义语义和数据间的映射关系则比较困难。 2 2 2 5 数据归约 数据归约将辨别出需要挖掘的数据集合，缩小处理范围，是在数据选择基础 上对挖掘数据的进一步约简。数据归约又称为数据缩减或数据浓缩，数据归约就 是将初始数据集转换到某种更加紧凑的形式而又不丢失有意义的语义信息的过 程。 数据归约技术可以甩来褥到数据集的归约表示，它接近子保持原数据的完整 性，但数据量比数据小得多。与非归约数据相比，在归约的数据上进行挖掘，所 霈要的时间和内在资源更少，挖掘将更有效，并产生相同的或几乎相同的分板结 果。数据归约技术主要包括： ( 1 ) 数据聚集 数据聚集采用数据仓库中的切片、旋转和投影技术，对原始数据进行抽象和 聚集。数据聚集技术可聚集现有字段中的数值。或对数据字段进行统计。如将月 薪一年薪，月产量一季产量一年产量按地区进行汇总等。根据挖掘处理的业务需 求对数据进行聚集，不仅大大减少了数据量，而且加快了数据挖掘的处理过程， 数据挖掘系统可以直接在合适的数据上进行挖掘，无需进行额外的数据预处理。 数据聚集可以在不同的粒度上进行聚集，如轻度汇总或高度汇总等。 ( 2 ) 维归约 维归约即数据选择中的属性选择。维归约的主要方法为筛选法。筛选法根据 一定的评价标准在属性集上选择区分能力强的属性子集。从基数为的原属性 中选择出基数为肘的属性集的选择标准通常是：使所有决策类中的例子在m 维属性空间中的概率颁与它们在原n 维属性空间中的概率分布尽可能相同。根 据和挖掘目标间的关系，数据集的属性可分为三类：a ) 相关属性：b 1 冗余属性； c ) 不相关属性。相关属性和挖掘目标有着直接或间接的联系，数据挖掘所发现的 知识就是从相关属性的数据中获取的。冗余属性与挖掘目标相关，但冗余属性不 第1 0 页 电子科技大学硕士学位论文 能为挖掘目标提供任何新的信息。通常情况下，冗余属性是指数据集中已有类似 的属性，或该属性可根据属性集中其他属性推导或计算出来。不相关属性是指和 挖掘目标没有任何关系的数据。维归约即发现属性集中和挖掘目标盯着的属性 集，剔除冗余和不相关属性。删除不相关属性的操作也称为就即去除对发现 任务没有贡献或贡献率极低的属性域。类似魄删除冗余属性可称为属性的并往。 即对属性进行主成分分析或因子分析，寻找属性之间的依赖关系，把相近的属性 进行综合归并处理。维归约的实质是相关属性的选择，而相关属性集的可能情况 是原属性的幂集，共1 罗c ：= 2 “一1 种可能，其中矗为原属性集中属性的个数。 如何在这巨大的搜索型闯中发现最优或合适的楣关属性集是维归约的关键技术。 因此不少学者先后提出了许多方法和算法，其中零维特征法和全维特征法是最简 单也是最早提出的方法。零维特征法也称逐步向前选择法，逐步选择原属性集中 最好的属性，将其加入到相关属性子集中，并从原属性集中删除选出的属性，然 后再对原属性集剩下的子集进行迭代选择，直到发现所有的媚关属性。全维特征 法与此相反，也称逐步向后删除法，该方法从整个属性集开始，每次删除一个属 性( 冗余或不相关) 直到没有多余的属性可删除。 ( 3 ) 属性值归约 属性值归约包括两方面，即连续值属性的离散化和符号型属性的合并。连续 值属性的离散化就是在属性的值域范围内，根据某种评价标准，设定若干个划分 点，用这些划分点将属性的值域划分为若干个子区间，然后用特定的符号或整数 值代表每个子区间。连续值属性的离散化的形式化定义如下： 对于连续值属性口的值域圪，选择个分割点集合e = c ? ，c ；，c ： ，在 口的连续取值空间 m i n f ( a ) ，m a ) ( ，( 口) 】上形成区间集合a a = p ? ，以，p ：+ ， ，其 中： f 【m i n ，( 口) ，c 叫，= 1 p 。a = c ：。，c ；) ，= 2 ，3 ， i k ，m a x f ( 口) 1 = r + 1 公式( 2 1 ) 定义映射& ：圪一匕= 1 ，2 ，+ 1 对连续值属性离散化合原始数据获得了简化，但是如果分割点选择不当，将 会导致原始数据集中有用信息的丢失。符号型属性的合并主要检验两个相邻属性 值之间对决策属性的独立性，然后判断是否应将其合并。 属性值归约通过选择替代的、较小的数据表示形式减少了数据量。属性值归 第1 1 页 电子科技大学硕士学位论文 约技术可以是有参的，也可以是无参的。有参方法是使用一个模型来评估数据， 只需要存放参数，而不需要实际数据，例如线性回归和多元回归。无参的数值归 约技术对属性值进行变换，如采用直方图或聚类法。聚类法是将属性值视为对象， 并对属性值进行聚类，使得在一个聚类中的对象“类似”，而与其他聚类中的对 象“不类似”，在数据归约是用数据的聚类代替实际数据。 ( 3 ) 数据压缩 应用数据编码或变换，得到原数据的归约或压缩表示。数据压缩分为无损压 缩和有损压缩。如果原数据可以由压缩数据重新构造而不丢失任何信息，则所使 用的数据压缩技术是无损的，否则该技术是有损的。目前使用比较普遍的数据压 缩方法如小波变换和主成分分析是有损数据压缩方法，对于稀疏或倾斜数据有很 好的压缩结果。倾斜度用来衡量一个分布是否具有单一而且很长的末端。如果一 个分布的漫长末端是伸向数值增长方向的，豇l j 称其为右倾斜，反之刚称为左倾斜。 ( 4 ) 数据抽样 数据抽样用数据的较小的样本表示大的数据集。它主要利用统计学中的抽样 方法，如简单随机抽样、等距抽样、分层抽样等。 2 2 2 6 数据质量分折 数据挖掘结果质量的好坏有两个影响因素：一是所采用的数据挖掘技术的有 效性，二是有用于挖掘的数据的质量和数据量。如果选择了错误的数据或不适当 的属性，或对数据进行了不适当的变换，则不能取得好的挖掘结果。 数据挖掘的效果和数据质量之间有着紧密的联系，所谓“垃圾入，垃圾出”， 即数据的质量越好，则挖掘的结果就越精确，反之则不可能取得好的挖掘结果。 研究数据的质量，为进一步的分析做准备，并根据数据情况确定将要进行的挖掘 操作的类型。数据质量的含义包含四个方面，即( 1 ) 数据的正确性；( 2 ) 数据 的一致性；( 3 ) 数据的完整性；( 4 ) 数据的可靠性。 2 2 3 数据挖掘 在问题进一步明确，数据结构和内容进步调整的基础上，就可以形成知识 的模型。对历史数据建立一个预测模型，需要有严格的理论指导，也就是必须有 适用于当前知识领域的算法，建立模型之后，采用历史数据进行训练，当训练达 到一定的稳定程度之后，再用另外一些新的数据对这个模型进行测试。这一步是 数据挖掘的核心环节，一个好的模型算法没必要与已有数据1 0 0 地相符，但模 型算法对未来的数据应有较好的预测。建立模型算法是一个反复的过程。需要 第1 2 页 电子科技大学硕士学位论文 仔细考虑不同的模型以判断哪个模型，算法对所需要解决的问题最有用。 2 2 3 1 建立什么样的模型，算法 数据挖掘的目的是生成可以据其所示的含义采用行动的知识，也就是建立一 个现实世界的模型。模型是对客观事物的种抽象描述，人们通过模型来增加对 复杂问题的理解和处理，它使得复杂数据更容易被理锯。其中数学模型可以用数 学公式表示，也可以用算法描述。数据处理模型一般用数据处理过程来说明，模 型是模式和数据间相关性的形式化描述。概括地说，模型是整数据集的全局性描 述。挖掘数据的过程就是按照人们设计的“模型”对数据进行处理、分析、预测 的过程，它是人的经验、分析过程在计算机中的实现。模型法通过历史数据预测 未来，它的有效性的前提条件隐藏着三个假设：( 1 ) 过去是未来的好的预测器； ( 2 ) 数据是可利用的；( 3 ) 数据包含我们想要的预测。 在数据挖掘中，我们可能使用许多不同的模型，如关联规则模型、决策树模 型、神经网络模型、粗糙集模型、数理统计模型( 如回归模型) 、时间序列分析 模型等。针对同模型，可以使用不同的算法进行数据挖掘。 各种不同的模型有其自身的适应性，针对不同的应用场合，某些模型可能表 现出适应性，但另一些模型则可能很不适应，所以模型无所谓好坏。但这不等于 说模型不需要改进，即使同一种模型，经过无数次研究和应用的检验，也会逐渐 地改善，算法更是如此。所以本文在神经网络模型的基础上提出相应的算法，既 有理论研究上的需要，也是实际应用的需要。 2 2 3 2 模型，算法的精确度 使用模型出现错误的数目与总数之间的比，称为错误率。类似地，正确的数 目与总数的比称为准确率。对回归模型来说，可以用方差来描述模型的准确程度。 测试数据挖掘模型需要把数据至少分成两个部分：一个用于模型训练，另一个用 于模型测试。如果不进行测试，那么模型的准确性就无法度量。模型准确性的测 试分为两类。 ( 1 )封闭测试：训练模型的训练集数据即为测试模型的测试集数据。 封闭测试显然无法验证模型的推广能力，即对未知数据的准确度， 但封闭测试可以测试模型的稳定度。 ( 2 )开放测试：开放测试的测试模型的测试集数据和训练模型的训练 集数据不同，即测试模型的数据是模型先前未见的数据。开放测 试可以很好度量模型的准确性。 模型的精确度越高，其可用性就越强，就越有利于做出正确的决策。精确度 第1 3 页 电子科技大学硕士学位论文 将取决于方法的设计和历史数据量及用户的期望值。通常在具体应用中，模型不 可能精确地表示整个数据集，因此在使用训练数据建立模型时，并不要片面追求 封闭测试的正确率，否则可能造成过匹配现象( 也称过学习) 。例如，假设学校 对学生信息进行挖掘，希望发现成绩优异的学生的原因，假设在挖掘的数据集中 所有的成绩优异的学生的身高都低于1 7 5 米，如果据此建立模型，认为所有成 绩优异的学生身高都应低于1 7 5 米，则可能精确度很差。也就是说，过匹配将 会影响模型的推广能力。对于不是样本集中的输入也能给出合适的输出，这种性 质称为推广能力，或称泛化能力。 2 2 3 3 模型，算法的验证 在建立模型后，不直接利用这个模型做出决策或采取行动，而是先对模型测 试和验证，是一种较好的做法。模型建立好之后，必须评价其结果，解释其价值。 在实际应用中，模型的准确率会随着应用数据的不同发生变化。 j