（计算机软件与理论专业论文）独立分量分析及其在数据挖掘中的应用.pdf

独立分量分析及其在数据挖掘中的应用 中文摘要 近年来，伴随盲信号分离问题产生的独立分量分析( i n d e p e n d e n tc o m - p o n e n ta n a l y s is ，简称为i c a ) 理论己逐渐成为统计信号处理中的一个研究 热点，并正迅速成为多维数据分析的一个有力工具。独立分量分析算法根 本原理是通过分析多维观测数据间的高阶统计相关性，找出相互独立的隐 含信息成份，完成分量问高阶冗余的去除及独立信源的提取。与其他方法 相比较，独立分量分析的突出特点是：它以分量间相互独立为分离准则， 在源数据和混合方式均未知的前提下，尽可能无失真的从观测数据中分离 出隐含的独立信源。这一特点使得独立分量分析方法在图像特征提取，压 缩，模式识别和数据挖掘等领域中有着广泛的应用前景。 数据挖掘是近年来计算机领域的研究热点。它是一个非平凡的模式辨 识过程，它从大量的数据中寻求正确的、新颖的、具有内在价值的、和最 终可解释的模式。海量科学数据不但数量巨大，而且特征复杂、维数高， 向传统的数据挖掘预处理技术提出了挑战。复杂数据的出现迫切要求新的 特征处理技术，而数据挖掘书中却常将降维技术忽略。本文针对当前情况 结合实际系统详细介绍了特征空问组合优化技术，着重阐述了独立分量分 析的降维技术。主要有以下几方面的工作： 1 描述了特征空间组合优化技术的基本思想，并对两种典型的优化判 据进行了阐述，给出了特征选择的算法。 2 详细概述了独立分量分析理论的研究和发展现状及存在的问题。 3 介绍了与独立分量分析研究密切相关的统计和信息论基本知识。 4 对独立分量分析优化算法进行了研究，重点讨论了基于非高斯性极 大原理和信息熵极大原理的两类有代表性的i c a 算法，完成f a s t l c a 算法的实现工作。 5 以科学数据挖掘实验系统为例介绍了数据挖掘的定义、发展和应用 系统的实现方法。 关键字：独立分量分析，数据挖掘，特征提取，信息论，模式识别 独立分量分析及其在数据挖掘中的应用 a b s t r a c t r e c e n t l y , w i t h t h eb l i n ds i g n a ls e p a r a t i o np r o b l e mt h ei n d e p e n d e n t c o m p o n e n t a n a l y s i s ( 1 c a ) h a sb e e nh i g h l i g h t e di ns t a t i s t i cs i g n a lp r o p o s i n g ，a n db e c o m et h e m o r ep o w e r f u lh i g h - d i m e n s i o n a lm u l t i v a r i a t ed a t aa n a l y s i st 0 0 1 t h eb a s i cp r i n c i p a l o f l c ai st of i n dt h ei n d e p e n d e n th i d d e ni n f o r m a t i o nt h r o u g h a n a l y z i n g t h eh i g h - o r d e r s t a t i s t i cr e l a t i o no fo b s e r v e dd a t a , a n da c h i e v et h eg o a lo f g e t t i n gr i do f t h er e d u n d a n t l l i g ho r d e rc o m p o n e n ta n de x t r a c t i n gt h ei n d e p e n d e n ts 0 1 1 r c ed a t a c o m p a r e dw i t h o t h e rm e t h o d s ，i c ah a st h ec h a r a c t e r i s t i c sb yw h i c hw ec a nr e c o v e rt h ei n d e p e n d e n t h i d d e ns o u r c ef r o mo b s e r v e dd a t ai nt h ec o n d i t i o nt h a tt h e r ei sn oi n f o r m a t i o na b o u t t h es o u r c ed a t aa n dt h em i x i n gm e c h a n i s m t h es p e c i a la d v a n t a g em a k e si c am o r e a n dm o r e w i d e l ya p p l i e di ni m a g ef e a t u r ee x t r a c t i o n ，c o m p r e s s i o n ，p a t t e r nr e c o g n i t i o n a n dd a t am i n i n ge t c d a t am i n gi st h eh o t s p o ti nr e c e n tc o m p u t e rr e s e a r c h ，t h a ti sa nu n o r d i n a r y p a t t e mr e c o g n i t i o np r o c e s s t h eg o a lo fd a t am i n i n gi st of i n dt h ec o r r e c t ，n o v e l ， v a l u a b l ea n di n t e r p r e t a b l ep a t t e r nf r o mt h em a s sd a t a t h em a s ss c i e n t i f i cd a t an o t o n l yh a st h eg r e a tq n a n t i t y , b u th a st h eh i g hd i m e n s i o n a lc o m p l i c a t e df e a t u r e s ，t h e s e c h a r a c t e r i s t i c sc h a l l e n g et - h et r a d i t i o n a ld a t am i n i n g t e c h n o l o g y s ow e n e e dt h en e w f e a t u r ep r o c e s s i n gt e c h n o l o g y , b u tt h e s ek n o w l e d g ec a nh a r d l yb ef o u n di nn o r m a l d a t am i n i n gb o o k t h i sp a p e rw i l li n t r o d u c et h e o p t i m i z i n gt e c h n o l o g yo f f e a t u r e si n d e t a i l ，e s p e c i a l l yt h ei c a f e a t u r er e d u c i n gt e c h n o l o g y t h em a i nw o r ko ft h i sp a p e r f o c u so nt h e f o l l o w i n ga s p e c t s ： 1 i n t r o d u c et h eb a s i ci d e ao f o p t i m i z i n gt e c h n o l o g yo ff e a t u r e ，a n dt h e t w ok i n d so fo p t i m i z i n gc r i t e r i o n g i v et h ed e c i s i o nt r e ea l g o r i t h mo f f e a t u r es e l e c t i o n 2 i n t r o d u c et h et h e o r yo fi c ai n d e t a i l ，i n c l u d i n gt h ep r o b l e ma n dt h e f u t u r eo fi c a 3 i n t r o d u c et h es t a t i s t i ct h e o r ya n di n f o r m a t i o n t h e o r yr e l a t e dt oi - c a 4 r e s e a r c ht h e o p t i m i z i n ga l g o r i t h m so fi c a ，d i s c u s st h et w ok i n d s r e p r e s e n t a t i v ea l g o r i t h m s b a s e do n n o n g a u s s i a n m a x i m u mo r i n f o r m a t i o ne n t r o p ym a x i m u m ，f i n i s ht h er e a l i z a t i o nw o r ko ff a s t i c a a l g o r i t h m 5 i n t r o d u c et h ec o n c e p t so fd a t am i n i n g ，i n c l u d i n gd e f i n i n gd e v e l o p m e n t 独立分量分析及其在数据挖掘中的应用 a n di m p l e m e n tm e t h o d so f a p p l i c a t i o ns y s t e m ，r e g a r dt h ee x p e r i m e n t a l s c i e n t i f i cd a t am i n i n gs y s t e m k e yw o r d s ：i n d e p e n d e n tc o m p o n e n ta n a l y s i s ，d a t am i n i n g ，f e a t u r ee x t r a c t i o n ，i n f o r m a t i o nt h e o r y ，p a t t e r nr e c o g n i t i o n - l l i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 嚣辘日期：硼眸r7 月门日 独立分量分析及其在数据挖掘中的应用 1 2 项目背景和意义 1 。2 1 问题的提出 第一章绪论 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积 累的数据越来越多。商品条形码的广泛使用，企业信息化程度的提高，科 学研究中仿真数据的积累，政府部门中电子化事务处理技术的运用，以及 数据收集工具和技术的多元化( 从文本扫描到卫星遥感) 等等，使得数据快 速膨胀。互联网的发展更积累了海量的数据和信息。如何理解和概括存储 在各种数据媒介中的海量数据? 在缺乏强有力的分析工具的情况下，己远 远超出了人类的自然能力。这种情况被人们描述为“数据丰富，但信息贫 乏”( d a t ar i c hb u t i n f o r m a t i o np o o r ) 。许多的数据库被戏称为“数据 坟墓”( d a t at o m b ) 就是拥有大量数据，但却无法被人理解。 激增的数据背后隐藏着许多重要的信息，但却因为缺乏从海量数据中 提取有价值知识的工具，使得拥有这些数据库的决策者们，在做决策时无 法从数据中获取有效的信息，而是只能凭直觉做决定。传统的数据库管理 系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中 存在的关系和规则，无法根据现有的数据预测未来的发展趋势，缺乏发现 数据背后隐藏的知识的手段。数据与信息之间的鸿沟要求有更强用力的数 据分析工具，将数据坟墓转换成知识“金块”。 在数据库技术飞速发展的同时，智能技术迅速发展，可大致分为商业 智能，人工智能和计算智能。商业智能对变换的商业环境提供决策支撑， 主要有数据仓库、数据挖掘和联机分析处理技术。人工智能采用的技术是 符号推理，通过推理形成概念化的推理链。计算智能则采用计算的方式模 拟人和生物的模糊推理、神经网络计算和遗传进化过程。智能领域的一个 分支一机器学习的研究自5 0 年代开始以来也取得了很大进展。用数据库管 理系统来存储数据，用机器学习的方法来分析数据，挖掘大量数据背后的 知识，这两者的结合促成了数据库中知识发现( k n o w l e d g ed i s c o v e r y i n d a t a b a s e s ，简记k d d ) 的产生，k d d 亦称为数据挖掘( d a t am i n i n g ，简称 d m ) 。 数据挖掘是数据库和智能技术自然演化的结果。该技术的发展大致可 以描述为如下的过程：初期是简单的数据收集和数据库的构造；然后是对 独立分量分析及其在数据挖掘中的应用 数据的管理，这包括：数据存储、检索以及数据库事务处理；最后到数据 的分析和理解，这时候出现了数据仓库技术和数据挖掘技术。早期数据收 集和数据库的建造为数据存储、检索和事务处理技术的发展创造了必要条 件，随着查询、事务处理等成熟技术被频繁的应用在大量的数据库系统上， 数据的分析和理解也就自然成为了发展的下一个目标。 数据挖掘是当前研究的热点，从大量的数据中智能地、自动地提取出 有价值的知识和信息，即数据挖掘，它不但具有十分重要的理论意义而且 也更有广泛的应用前景。目前，很多研究者对此投入了极大的热情，并取 得了不少理论和应用上的成果。 在科学研究领域，科学仿真实验数据的越来越多，且不同实验采集数 据分散于不同的计算机中，科学家们几乎不可能通过手工的方式来发现各 数据源之间的内在联系。这迫切需要研究出与此对应的新的数据挖掘技术 及挖掘工具来解决此类问题。目前， 但专门针对科学数据的研究非常少。 段，成熟的研究成果基本空白。 国外对数据挖掘技术的研究比较多， 国内此领域的研究处于初步的起始阶 科学数据挖掘是数据挖掘中较复杂且国内研究较少的领域。现在科学 仿真数据，试验数据越来越多，越来越复杂，这给表示、存储、理解、分 析和可视化这些数据带来了困难。目前，国外已有不少的科学数据格式系 统，如c d f 、n e t c d f 、h d f 5 ”等，也相应地诞生了各种各样的科学数据管理 系统，同时由于模拟数据常常以网格( m e s h ) 形式表示，而通用的格式系统 ( 如上述三种数据格式系统) 均支持网格数据( m e s hd a t a ) 的存储和处理， 它们给科学数据的存储和管理带来了方便。尽管如此，要理解、分析这些 数据，并从中获取知识仍是不易，由此科学数据挖掘势在必行，且由于科 学数据具有规模大、特征复杂的特点，使得科学数据分析不但具有显著的 理论研究价值，同时也具有很高的应用价值。 本项目的研究工作源于上述背景。我们的目的是对科学数据挖掘的核 心算法进行深入的研究，期望能在这些已有算法和理论的基础上，搭建起 合理且高效的科学数据挖掘架构，研究出科学高效的数据挖掘算法，并开 发出应用于实际的科学数据挖掘平台，以填补国内本研究领域和相关产品 的空白。 1 2 2 独立分量分析理论的发展概况和主要研究问题 独立分量分析( i n d e p e n d e n tc o m p o n e n th n a l y s is ，简称z c a ) 最早应用 于盲信号分离( b s s ) 问题一即是在未知输入信号的情况下通过观察输出 独立分量分析及其在数据挖掘中的应用 信号确定源输入信号的问题。它是2 0 世纪近1 0 年来迅速发展起来的一个 研究领域。c j u t t e n 和j h e r a u l t 于1 9 9 1 年首创将人工神经网络算法用于 b s s 问题，从而开启了一个新的领域。1 9 9 4 年，p c o m m o n 首先界定了解决 b s s 问题的i c a 方法的假设条件”1 ( i c a 这个名称就是他提出的) ，并指出可 以通过某个称为对比函数的目标函数达到极大值来消除观测信号中高阶统 计关联，从而实现b s s 。1 9 9 5 年a j b e l l 和t j s e j n o w s k i 发表了i c a 发 展史中的里程碑文献“1 。其重要贡献在于：第一，利用神经网络的非线性特 性来消除观察信号中的高阶统计关联；第二，用信息最大化准则建立目标 函数，从而掩信息论方法与i c a 结合起来：第三，给出了神经网络的最优w 迭代学习算法，成为后续算法的基础：第四，成功地对1 0 个人说话的鸡尾 酒会问题给出了很好的分离效果。1 9 9 6 年，b a p e a r l m u n t t e r 在i c a 中引 入最大似然为准则的目标函数。同年，j - f c a r d o s o 和b h l a h e l d 提出了 i c a 学习算法中的“相对梯度”、“等价变换”等重要思想和方法”1 。1 9 9 7 年， d t p h a m 和p 6 a r a t 通过准最大似然途径对i c a 的学习算法、稳定性、分 离精度和源d d f 的确定作了进一步讨论”1 。1 9 9 9 年，ah y v a r i n e n 提出i c a 的快速顶点迭代算法，被称为f a s t l c a ，大大提高了收敛速度。 如今，除了解决b s s 问题，i c a 方法还广泛地应用于图像处理和数据处 理。i c a 研究中的主要问题有： i c a 的目标函数。研究目标函数的选择和所用的准则，如信息最大化准 则、最大似然准则、最大独立性准则等； i c a 的学习算法。与其它神经网络学习算法相同，为了求得使目标函数 达到极值的矽，使用的迭代算法应尽可能简单、收敛快，如相对梯度、自 然梯度等算法： i c a 算法的稳定性。指i c a 迭代计算中达到正确源信号分离的解可能是 一个平衡点而不是稳定点。 i c a 中源信号p d f 的确定。如果关于源信号p d f 的先验知识很少甚至完 全没有时，必须在学习过程中加以确定，否则将进行反复尝试，可能会浪 费大量时间而分离效果不佳。 i c a 豹各种模拟实验和具体应用研究。 1 1 项目概述 本论文是在自然科学基金项目“基于神经网络的大规模数值模拟数据 分析技术研究”的支持下完成的。该项目研究的目标是采用理论分析、数 独立分量分析及其在数据挖掘中的应用 值计算、计算机编程、计算机仿真、真实数据测试相结合的研究途径，发 展适合于大规模、复杂、高维的数值模拟科学数据的数据挖掘算法，并实 现代码级的数据挖掘应用系统模型。从大规模科学数据中寻求正确的、新 颖的、具有内在价值的和最终可理解的模式，为科学家提供有用的信息。 我们在以前的研究成果上，以具体的科学仿真实验产生的数据作为挖掘对 象，主要研究利用独立分量分析技术在特征空间组合优化技术、自组织映 射神经网络在图像处理方面的应用、新的前馈式递归聚类算法，并结合已 有的数据挖掘技术，开发新的基于科学仿真数据的智能挖掘平台。在实际 应用中，检测和发展数据挖掘算法。 1 4 论文主要内容 本文较系统得介绍了独立分量分析理论，并将其应用于科学数据挖掘， 针对科学数据的高维特性提出适合的降维算法，并结合数据挖掘实验原型 系统给出i c a 算法的具体实现。论文分为5 章，具体安排如下： 第一章是引言部分。简要介绍了本文的研究背景( 包括i c a 理论的发展 和数据库的发展) 和主要研究内容。 第二章介绍了数据挖掘这一新领域，着重阐述了数据挖掘的定义，现 状和发展趋势，以及数据挖掘的意义和过程。另外简述了降维的必要性以 及常用的特征空间组合优化技术。 第三章从多方面讨论独立分量分析理论的基础知识。首先就其中涉及 的统计基本术语和信息论基本知识做了简要介绍。然后以分析多维数据的 线性描述方法开始，给出传统的线性描述一主分量分析方法的概念和特 征值分解算法，同时指出p c a 的一些不足之处。在此基础上自然引出独立 分量分析理论，给出i c a 的定义、常用线性模型和若干的限制条件。i c a 问 题可以总结为两个主要方面：目标函数( 优化判据) 和寻优算法( 优化算 法) ，其中i c a 方法的稳健性主要取决于目标函数的选择，而算法的收敛速 度，占用内存情况等则主要依赖于优化算法。本章分别介绍了阻峭度、负 熵、近似负熵及互信息为判据的目标函数，并在第四节中结合峭度和负熵 的目标函数，分析研究了i c a 的多种算法，主要是f a s t l c a 算法。 第四章是本文的实践部分，以数据挖掘原型系统为例，介绍了数据挖 掘应用系统的设计，并在第三节详细介绍了i c a 在数据挖掘中的应用，并 给出了具体的实现办法。 第五章为论文的总结和展望。 独立分量分析及其在数据挖掘中的应用 第二章数据挖掘与特征空间组合优化 2 1 数据挖掘概述 本节主要介绍数据挖掘的相关知识，包括数据挖掘的定义、数据挖掘 的研究现状和发展趋势，并对数据挖掘过程进行了简单的介绍，最后，介 绍了数据挖掘的功能( 可以挖掘什么类型的模式) ，即概念类描述：特征 化和区分、关联分析、分类和预测、聚类分析、孤立点分析和演变分析。 2 1 1 数据挖掘的定义 所谓数据挖掘( d a t am i n i n g ，简记d m ) ，就是从大量的、不完全的、有 噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先 不知道的、但又是潜在有用的信息和知识的过程“1 。这个定义包括好几层含 义：数据源必须是真实的、大量的、含噪声的；发现的必须是用户感兴趣 的知识；而且发现的知识要可接受、可理解、可运用；并不要求是放之四 海皆准的知识，仅支持特定的发现问题。 与数据挖掘相近的同义词有知识挖掘、知识获取、模式分析、数据考 古等。还有一个经常与之相混的术语：数据库中的知识发现( k n o w l e d g e d i s c o v e r yf r o md a t a b a s e ，简记k d d ) ，一般的看法是d m 只是k d d 的一个 步骤，但是由于d m 这个词的广泛使用，我们也可不对他们进行严格的区分， 而把他们看成同义词。 何为知识? 从广义上理解，数据、信息也是知识的表现形式，但是人 们更把概念、规则、模式、规律和约束等看作知识。人们把数据看作是形 成知识的源泉，好像从矿石中采矿或淘金一样。原始数据可以是结构化的， 如关系数据库中的数据；也可以是半结构化的，如文本、图形和图像数据； 甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可 以是非数学的；可以是演绎的，也可以是归纳的。发现的知识可以被用于 信息管理、查询优化、决策支持和过程控制等，还可以用于数据自身的维 护。 因此，数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的 简单查询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下， 汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、 可视化技术、并行计算等方面的学者和工程技术人员，投身到数据挖掘这 一新兴的研究领域，形成新的技术热点。 独立分量分析及其在数据挖掘中的应用 2 1 2 数据挖掘的研究现状和发展趋势 k d d 一词首次出现在1 9 8 9 年8 月举行的第1 l 届国际联合人工智能学 术会议上。随着k d d 在学术界和工业界的影响越来越大，国际k d d 组委 会于1 9 9 5 年把专题讨论会更名为国际会议，在加拿大蒙特利尔市召开了第 一届k d d 国际学术会议，以后每年召开一次。1 9 9 7 年亚太地区在新加坡组 织了第一次规模较大的p a k d d 学术研讨会，以后每年召开次。 此外，数据库、人工智能、信息处理、知识工程等领域的国际学术刊 物也纷纷开辟了k d d 专题或专刊。i e e e 的k n o w l e d g e a n dd a t ae n g i n e e r i n g 会刊首先在1 9 9 3 年出版了k d d 技术专刊，所发表的5 篇论文代表了当时 k d d 研究的最新成果和动态。随后，各类k d d 会议、研讨会纷纷涌现， 许多领域的国际会议也将k d d 列为专题讨论。1 9 9 9 年，i e e e 和a c m 再 次推出k d d 专刊，介绍数据挖掘在各个领域的应用成果。 不仅如此，在i n t e r n e t 上还有不少k d d 电子出版物，其中以半月刊 k n o w l e d g ed i s c o v e r yn u g g e t s 最为权威，在h t t p ：w w w k d n u g g e t s c o r n 还可 以下载各种各样的数据挖掘工具软件和典型的样本数据仓库，供人们测试 和评价。另一份在线周刊为d s ( d s 代表决策支持) ，1 9 9 7 年1 0 月7 日开始 出版，可向d s t r i a l t g c c o r n 提出免费订阅申请。在网上，还有一个自由论 坛d me m a i lc l u b ，人们通过电子邮件相互讨论d m 的热点问题。 目前，国外数据挖掘的发展趋势及研究方向主要有：对知识发现方法 的研究和进一步发展，如近年来注重传统的统计学回归法在k d d 中的应用； k d d 与数据库的紧密结合，人工神经网络应用于数据挖掘方面的研究。应 用方面有：k d d 商业软件工具不断产生和完善，注重建立解决问题的整体 系统，而不是孤立的过程。用户主要集中在大型银行、保险公司、电信公 司和销售业。国外很多计算机公司非常重视数据挖掘的开发应用，i b m 和 微软都成立了相应的研究中心进行这方面的工作。许多著名的计算机公司 开始尝试k d d 软件的开发，比较典型的如s a s 公司的e n t e r p r i s em i n e r , i b m 公司的i n t e l l i g e n t m i n e r , s g i 公司的s e tm i n e r , s p s s 公司的c l e m e n f i n e ，还 有k n o w l e d g ed i s c o v e r y w o r k b e n c h 、d b m i n e r 、q u e s t 等。w e b 数据挖掘产 品有n e t p e r c e p t i o n s ，a c c r u ei n s i g h t 和a c c r u e h i tl i s t 。c o m m e r c et r e n d s 等。 与国外相比，国内对k d d 的研究稍晚，目前进行的大多数研究项目是 由政府资助进行的，如国家自然科学基金、8 6 3 计划、“九五”计划等。1 9 9 3 年国家自然科学基金开始对数据挖掘研究进行支持。1 9 9 9 年4 月在北京召 开的第三届亚太地区k d d 国际会议( p a k d d 9 9 ) 响应热烈，收到论文l5 8 篇。 独立分量分析及其在数据挖掘中的应用 国内从事数据挖掘研究的人员主要在大学，也有部分在研究所或公司。所 涉及的研究领域很多，一般集中于学习算法的研究、数据挖掘的实际应用 以及有关数据挖掘理论方面的研究。如北京系统工程研究所对模糊方法在 数据挖掘中的应用研究、北京大学对数据立方体的研究、华中理工大学、 复旦大学、浙江大学等对关联规则的研究、电子科技大学从神经网络等方 面对数据挖掘进行的研究等。西安交通大学己知的有机械学院、电信学院、 工程学院和管理学院在从不同角度对数据挖掘进行研究。但是到目前为止， 国内还没有比较成熟的数据挖掘产品。 当前，d m 研究正方兴未艾，预计今后还会形成更大的高潮，研究焦点 可能会集中到以下几个方面： 1 ) 研究专门用于知识发现的数据挖掘语言，也许会像s q l 语言一样 走向形式化和标准化： 2 )寻求数据挖掘过程中的可视化方法，使得知识发现的过程能够被用 户理解，也便于在知识发现过程中的人机交互； 3 、研究在网络环境下的数据挖掘技术，特别是在i n t e m e t 上建立d m 服务器，与数据库服务器配合，实现数据挖掘； 4 ) 加强对各种非结构化数据的挖掘，如文本数据、图形图像数据、多 媒体数据。 但是，d m 将首先满足信息时代用户的急需，因此，研制开发大量基于 d m 的决策支持软件工具产品将是首要的任务。 目前有很多通用的数据挖掘系统趋向于提供适用于各种商业应用的横 向解决方案( h o r i z o n t a ls o l u t i o n ) ，而不是针对某个特定的应用的解决方案。 对某个特定领域的一些数据或应用可能需要特定的算法来查找模式，而通 用的数据挖掘系统对这些特定领域的数据有其固有的局限性，有可能不能 满足要求。因此，研制某个特定领域的数据挖掘工具将显得尤为重要。专 用的数据挖掘系统能够提供纵向解决方案( v e r t i c a ls o l u t i o n ) ，把特殊领域的 业务逻辑和数据挖掘系统集成起来，将数据分析技术与特定领域知识结合 以完成特定的任务。目前的应用领域多集中于生物医学、d n a 分析、金融、 零售业和电信部门等。 2 1 3 数据挖掘过程简介 数据挖掘有以下主要的过程： 1 确定业务对象 清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一 独立分量分析及其在数据挖掘中的应用 步。挖掘的最后结构是不可预测的，但要探索的问题应是有预见的，为 了数据挖掘而数据挖掘则带有盲目性，是不会成功的。 2 数据准备 1 ) 数据的选择 搜索所有与业务对象有关的内部和外部数据信息，并从中选择出适 用于数据挖掘应用的数据。 2 ) 数据的预处理 研究数据的质量，为迸一步的分析做准备。并确定将要进行的挖掘 操作的类型。 3 ) 数据的转换 将数据转换成一个分析模型，这个分析模型是针对挖掘算法建立 的。建立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键。 3 数据挖掘 对所得到的经过转换的数据进行挖掘。除了选择合适的挖掘算法外， 其余一切工作都能自动地完成。 4 结果分析 解释并评估结果。其使用的分析方法一般应视数据挖掘操作而定， 通常会用到可视化技术。 5 知识的同化 将分析所得到的知识集成到业务信息系统的组织结构中去。 2 1 4 数据预处理 存在不完整、含噪声和不一致的数据是现实世界数据的共同特点。所 谓不完整是指数据中感兴趣的属性缺少属性值，含噪声是指含有错误或存 在偏离期望的孤立点值，不一致是指由于数据库等的原因使数据不符合逻 辑。产生的原因有很多种，可能是人员录入数据时的疏忽或者是理解错误、 设备故障等。在科学测试和实验中更易产生不完整、含噪声的数据，这给 科学数据分析带来了极大的障碍，不但会使分析结果出现较大误差而且还 有可能得到完全错误的结果。数据预处理可以改变数据的质量提高数据挖 掘过程的精度和性能。特别在科学数据挖掘中，数据预处理显得尤为重要， 它几乎占据了整个数据分析工作量的7 0 。数据预处理大致有这几方面的 工作。 数据清理 数据清理的日的是消除或减少噪声数据以及处理空缺值。通常采用分 独立分量分析及其在数据挖掘中的应用 箱、聚类和回归分析等技术消除或减少噪声数据；对于空缺值，可用该属 性最常出现的值，或根据统计，用最可能的值替代。尽管大部分的数据挖 掘算法都会处理噪声和空缺值，但经过清理的数据将更有助于减少学习时 间。 数据集成 数据集成是将多个数据源集中起来存放到一个一致的数据存储中，便 于处理和分析。对于多个数据源造成的冗余、重复甚至冲突的数据要在这 个过程中进行处理。 数据变换 数据可以概化到较高层的概念。例如，对于连续值的属性，“收入”的 数字值可以概化到离散的区间，如“低，中，高”。类似地，对于离散值的 属性，如“街道”，可以概化到高层概念，如“城市”。这样的概化便是数 据变换。通常还需要做的数据变换有平滑、聚类、规范化和属性构造等。 数据规约 数据规约包括维规约、数据压缩等内容，其目的都是让数据量变小便 于后续数据分析。所谓维规约就是要让数据的属性数量变小，如何缩减属 性，去除意义不大的属性列是本文讨论的重点。 2 1 5 数据挖掘功能 利用数据挖掘技术可以获得多种知识，在许多情况下，用户并不知道 数据库中存在哪些有价值的知识，因此一个数据挖掘系统应该能够同时发 现多种模式的知识，以便满足用户的需要。下而介绍一下数据挖掘的功能。 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任 务一般可以分为两类：描述和预测。描述性挖掘要刻画数据库中数据的一 般特性。预测性挖掘要在当前数据上进行推理，来进行预测。 1 、概念描述：定性与对比 通过对含有大量数据的数据集进行概述性的总结，可以获得简明、准 确的描述，这种描述就称为概念描述。获得概念描述的方法主要有以下三 种： ( 1 ) 利用更为广义的属性，对所分析的数据进行概要总结，被分析的数 据称为目标数据集； ( 2 ) 将所分析的两类数据的特点进行对比，并对对比结果进行概要总结， 这两类数据分别称为目标数据集和对比数据集。 ( 3 ) 数据特征化和比较。 独立分量分析及其在数据挖掘中的应用 2 、关联分析 关联分析就是从给定的数据集中发现频繁出现的项集模式知识，即关 联规则，形如( x ；y ) ，即( 4n n 以j 皇n n e ) 。关联分析广泛用于市 场营销、事务分析等应用领域。 关联规则的挖掘问题可形式化描述如下，设i = ，0 ) 是数据项集 合，d 是与任务相关的数据集合，也就是一个交易数据库，其中每个交易丁 是个数据项子集，即t d ，t e ，每个交易均有一个识别编号t i d 。设 a 为一个数据项集合，当且仅当爿时，称交易，包含a 。一个关联规则 就是具有a j b 形式的蕴涵式，这里a c ，b c j ，并且4r 、b = 。关联规 则a j b 在交易数据库d 中成立，并且具有s 支持度和c 信任度。这也就意 味着交易数据库d 中有s 比例的交易丁包含a w b 数据项，并且交易数据库 d 中有c 比例的交易7 1 满足“如果包含a ，则包含b ”的条件。即 s u p p o r t ( a = 亭b ) = e ( a u 口)( 2 1 ) c o n f i d e n c e ( ajb ) = p ( alb )( 2 - 2 ) 满足最小支持度阀值和最小信任度阔值的关联规则称为强规则。通常 将最小支持度阀值简写为m i n s u p ，最小信任度阀值简写为m i n c o n f ，这 两个阀值用0 到1 0 0 之间的值表示而不用0 到1 之间的值表示。 一个数据项的集合称为项集，一个包含k 个数据项的项集称为k 一项集。 一个项集的出现频度就是交易数据库d 中包含该项集的交易记录数。如果 一个项集的出现频度大于或等于最小支持度阀值乘以交易记录集d 中的记 录数，那么该项集满足最小支持度阀值。满足最小支持度阀值的项集称为 频繁k 一项集。所有频繁项集的集合记作上 。 关联规则的挖掘问题可以分解为两个子问题。 ( 1 ) 找出所有的频繁项集。这些项集的频度至少应等于最小支持度； ( 2 ) 根据所获得的频繁项集生成相应的强关联规则。对于每个频繁项集 x ，如果y c x ，y ，且s u p p o r t ( x ) s u p p o r t ( y ) m i n c o n f ，则有关联规则 y x y 。 3 、分类和预测 分类和预测是两种数据分析形式，它们可用于抽取能够描述重要数据 集和预测未来数据趋势的模型。分类方法用于预测数据对象的离散类别， 预测方法用于预测数据对象的连续取值。机器学习、专家系统、统计学和 神经生物学等领域的研究人员已经提出了许多具体的分类预测方法。数据 分类过程主要包含两个步骤，第一步是建立一个描述己知数据集类别的模 独立分量分析及其在数据挖掘中的应用 型。该模型通过对数据库中各数据对象内容的分析获得。它是在已知训练 样本类别的情况下，通过学习建立相应的模型。通常分类学习所获得的模 型可以表示为分类规则形式、决策树形式和数学公式形式。第二步是利用 所获得的模型进行分类操作。经过评估，如果模型的分类准确率是可以接 受的，那么就可以使用这一模型对未来的数据对象进行分类。与分类学习 方法相比，预测方法可以认为是对未知类别数据对象的类别取值，利用学 习所获得的模型进行预测。目前分类与预测方法已被广泛应用于各行各业， 如信用评估、医疗诊断、性能预测和市场营销等应用领域。 4 、聚类分析 根据对象之间的相似程度，将一群对象分为若干组的过程就是聚类过 程。一个聚类就是由彼此相似的一组对象所构成的集合，不同聚类中的对 象通常是不相似的。聚类分析就是从给定的数据集中搜索数据对象之间所 存在的有价值的联系。在许多应用中，一个聚类中所有对象常常被当作一 个对象进行处理，聚类分析己被应用于模式识别、数据分析、图像处理和 市场分析等领域。聚类分析与分类预测方法的区别在于两者的学习方法不 同，前者是无监督的学习方法，后者属于有监督的学习方法。 5 、孤立点分析 与其它数据不一致或非常不同的数据就称为孤立点数据。大部分挖掘 将孤立点视为噪声或异常而丢弃了。但在一些应用场合，如各种商业欺诈 行为的自动检测，小概率事件往往比经常发生的事件更有价值。对孤立点 的分析处理通常称为孤立点挖掘。它的用途很广，例如，它可以用于欺诈 检测，即监测信用卡使用或电信服务中的异常行为；还可以用于市场分析， 即通过分析花费较小或较高顾客的消费行为制定营销策略。 6 、演变分析 演变分析就是对随时间变化的数据对象的变化规律进行描述并建模。 这类分析包括时间序列数据分析、序列或周期模式匹配和基于近似性的数 据分析。例如，利用演化分析方法，我们可以分析股票市场上主要股票的 交易数据，获得整个股票市场的股票演化规律。这样，我们能够准确地预 测股票市场上的股票价格，提高投资回报率。 2 1 6 数据挖掘的主要方法 数据挖掘的方法很多，每种方法都有其特定适用领域。某一种方法不 可能胜任所有的数据挖掘任务，一个复杂的数据挖掘系统常常采用多种数 据挖掘方法，通过整合多种数据挖掘方法来弥补不同数据挖掘方法所存在 独立分量分析及其在数据挖掘中的应用 的不足。数据挖掘的方法主要有以下几种： 1 、基于决策树的方法 决策树也称为判定树。它是用于分类和预测的主要方法之一。决策树 技术发现数据模式和规则的核心是归纳算法。它的目的是根据某个新记录 的属性，将其分派到预先定义好的若干类中的一个，并为其添加一个字段 以标识该记录的类别。构建决策树的算法很多，其中最具代表性的是c 4 5 算法。它们的算法思想大致如下： 将给定训练集作为决策树的根节点，训练集中的记录具有标识类别的 字段，刹甩信息增益来寻找节点上具有最大信息量的字段，根据对该字段 的不同取值建立该节点的若干分支，并为所有分支子集建立对应的节点。 在每个分支子集中重复建立下层分支和节点，直到节点中所有记录的类别 都相同为止，这样便生成了一棵完整的决策树。因为完整的决策树不利于 分类和预测，因此还要对该决策树进行剪枝处理，产生最终的决策树。然 后把决策树的节点分裂过程转化为“i f t h e n ”的规则，利用这些规则 就可以对新数据进行分类。 决策树方法在许多应用领域被广泛地应用，主要优点有： 第一，生成的规则容易理解：决策树产生的规则能够轻易地转化为 “i f t h e n ”这种形式的关联规则，也可以被翻译成自然语言或s q l 语 句；而且决策树模型的建立过程也比较直观。 第二，决策树进行分类时所需的计算量不大。 第三，决策树既支持离散数据也支持连续数据。 第四，决策树的输出包含属性的排序：决策树能够清楚地指出哪一个 数据域对决策是最重要的。 当然，决策树方法也存在着一定的不足。例如，训练一棵决策树的耗 费很大；对具有连续值的属性预测比较困难；在类过多的情况下分类容易 出错等。 2 、基于神经网络的方法 神经网络最早是由心理学家和神经生物学家提出的。神经网络是大量 的简单神经元按一定规则连接构成的网络系统。网络能够模拟人类大脑的 结构和功能，采用某种学习算法从训练样本中学习，并将获取的知识存储 在网络各单元之间的连接权中。神经网络和基于符号的传统人工智能技术 相比，具有直观性、并行性和抗噪声等优点。目前己出现了多种网络模型 和学习算法，主要用于分类、优化、模式识别、预测和控制等领域。在数 据挖掘领域，主要采用前向神经网络提取分类规则。从网络中提取规则， 独立分量分析及其在数据挖掘中的应用 主要有下述两种方向： ( 1 ) 网络结构分解的规则提取。 它以神经网络的隐层结点和输出层结点为研究对象，把整个网络分解 为许多单层子网的组合。通过研究较简单的子网，便于从中挖掘知识。k t 算法是有代表性的方法：k t 方法的缺点是通用性差，并且当网络比较复杂 时算法的复杂性高，容易产生组合爆炸问题。所以，对于大规模网络，此 类算法在提取规则前，需要对网络结构进行剪枝和删除冗余结点等预处理 工