（计算机软件与理论专业论文）面向高维数据挖掘的特征选择方法研究.pdf

面向高维数据挖掘的特征选择方法研究 论文题目： 专业： 硕士生： 指导教师： 面向高维数据挖掘的特征选择方法研究 计算机软件与理论 孙婧吴 印鉴教授 摘要 数据挖掘是目前国际上数据库和信息决策领域最前沿的研究方向之一。由于 高维数据日益成为主流，在实际应用中经常会遇到高维数据的情况，对高维数据 挖掘的研究有着越来越重要的意义。但高维数据本身独有的一些特点，使得高维 数据挖掘变的非常困难，因此必须采用一些特殊的方法进行研究处理。 本文从数据挖掘的概念及高维数据的特点入手，围绕着“面向高维数据挖掘 的特征选择方法”这一核心思想，探讨了分别应用于文本数据和基因表达数据的 特征选择方法。 针对文本数据，采用词的q u a l i t y 标准进行特征选择及降维，同时在稀疏向 量筛除、基于密度及散布的初始中心点搜索等方法进行改进，提出了一种面向文 本聚类的改进的k 均值算法。通过采用2 0 n e w s g r o u p 数据集进行实验，结果表 明，改进后的算法无论在聚类精度还是在稳定性方面，都明显优于标准的k 均 值算法。 对于基因表达数据，提出了一种新的面向基因表达高维数据的特征选择方 法，特征子集的搜索采用遗传算法进行随机搜索，特征子集的评价采用基于边界 点可分性度量作为评价指标及适应度函数。实验表明，该算法可有效的找出具有 较好的可分离性的特征子集，从而实现降维并提高分类精度。在此研究的基础上， 又提出一种综合了f i l t e r 及w a p p e r 模型的特征选择方法，首先基于特征之间的信 息增益进行特征分组及筛选，然后针对经过筛选而精简的特征子集采用遗传算法 进行随机搜索，并采用感知器模型的分类错误率作为评价指标。实验表明，该算 法可有效的找出具有较好的线性可分离性的特征子集，从而实现降维并提高分类 精度。 关键词：高维数据挖掘，特征选择，文本聚类，基因表达数据，遗传算法 面向高维数据挖掘的特征选择方法研究 t i t i e ：t h er e s e a r c ho nf e a t u r es e l e c t i o nm e t h d d s i i lh i 曲d i m e n s i o n a ld a t am i n i n g m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：s u nj i n g h a n s u p e r v i s o r ：y i nb a n a b s t r a c t d a t am i n i n gi so n eo ft h ef r o n t i e r so fr e s e a r c hi nt h ef i e l d so fd a t a b a s ea n dd s s i n p r a c t i c e ，t h eh i 。曲d i m e n s i o n a ld a t ai sf r e q u e n t l yu s e d ，a si tb e c o m e sm a i n s t r e a mi n r e a l l i f ed a t ai n c r e a s i n g l y , t h er e s e a r c ho nh i g hd i m e n s i o n a ld a t am i n i n gi sm o r ea n d m o r ei m p o r t a n t h o w e v e r , m i n i n gi nh i 曲d i m e n s i o n a ld a t ai se x t r e m e l yd i f f i c u l td u e t os o m ep a r t i c u l a rc h a r a c t e r i s t i c so fi t so w n t h e r e f o r e ，s p e c i f i cm e t h o d sm u s tb e a d o p t e dt os o l v et h e s ep r o b l e m s t h i sp a p e rs t a r t sw i t ht h e c o n c e p to fd a t am i n i n ga n dc h a r a c t e r i s t i c so fh i 【曲 d i m e n s i o n a ld a t a ，r e g a r d sf e a t u r es e l e c t i o nm e t h o d si nh i 曲d i m e n s i o n a ld a t am i n i n g a sc o r ec o n t e n t f e a t u r es e l e c t i o nm e t h o d sa p p l i e di nt e x td a t aa n dg e n ee x p r e s s i o n d a t aa r ed i s c u s s e dr e s p e c t i v e l y f o rt h ep r o b l e m ss u c ha sd i m e n s i o nc u r v e ，s p a r s ev e c t o ra n dr a n d o ms e l e c t i o no f i n i t i a lc e n t e r si nt h ea r e ao ft e x tc l u s t e r i n ga n dk - m e a n sa l g o r i t h m ，w ep r o p o s e da n i m p r o v e dk - m e a n sa l g o r i t h mf o r t e x tc l u s t e r i n g ，w h i c hi si m p r o v e db yf e a t u r e s e l e c t i o n , s p a r s ev e c t o rf i l t e r i n g ，d e n s i t ya n ds c a t t e r i n g b a s e di n i t i a lc e n t e r ss e a r c h i n g v i au s i n gd a t a s e t2 0n e w s g r o u pf o re x p e r i m e n t ，t h er e s u l t ss h o wt h a tt h ep r o p o s e d a l g o r i t h mw o r k s b e t t e rt h a ns t a n d a r dk - m e a n sa l g o r i t h mb o t hi nq u a l i t ya n d s t a b i l i t y f o rg e n ee x p r e s s i o nd a t a ，w ep r o p o s e dan e wf e a t u r es e l e c t i o nm e t h o d ，w h i c h r e a l i z e st h ef e a t u r es u b s e ts e a r c hb yg e n e t i ca l g o r i t h m ；a n dt h ef e a t u r es u b s e tf i t n e s s i se v a l u a t e db yt h es e p a r a b i l i t ym e a s u r eb a s e do nb o u n d a r yp o i n t s t h ee x p e r i m e n t a l r e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h mc a nf i n dt h ef e a t u r es u b s e t sw i t h g o o d s e p a r a b i l i t y , w h i c hr e s u l t si nt h el o wd i m e n s i o n a ld a t aa n dt h eg o o dc l a s s i f i c a t i o n a c c u r a c y b a s e do nt h er e s e a r c hm e n t i o n e da b o v e ，a n o t h e rf e a t u r es e l e c t i o nm e t h o d 塑鳖塑塑丝塑竺竺堑兰兰塑鎏竺! 垄 一一一 c o m b i n gf i l t e ra n dw r a p p e rm o d e l s ，w h i c hf i r s tf i l t e r sf e a t u r e sb yf e a t u r ep a r t i t i o n b a s e do ni n f o r m a t i o ng a i n ，a n dt h e nr e a l i z e st h en e a ro p t i m a lf e a t u r es u b s e ts e a r c ho n t h ec o m p a c t r e p r e s e n t a t i v ef e a t u r es u b s e tb yg e n e t i ca l g o r i t h m t h ef e a t u r es u b s e ti 8 e v a l u a t e db yt h ec l a s s i f i c a t i o ni n a c c u r a c yo ft h ep e r c e p t r o nm o d e l t h ee x d e r i m e n t a l r c s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h mc a nd i s c o v e rf e a t u r es u b s e t sw i t hg o o dl 访e a r s e p a r a b i l i t y , w h i c hr e s u l t si nt h el o wd i m e n s i o n a ld a t aa n dg o o dc l a s s i f i c a t i o n a c c u r a c v k e yw o r d s ：h i 曲d i m e n s i o n a ld a t am i n i n g 、f e a t u r es e l e c t i o n 、t e x tc l u s t e r i n g 、 g e n ee x p r e s s i o nd a t a 、g a 面向高维数据挖掘的特征选择方法研究 引言 计算机发展日新月异，互联网的诞生促进了电子信息的快速积累，各行各业 都习惯采用计算机及相应的信息技术进行管理和运营，这使得人们生成、收集、 存储和处理数据的能力大大提高，数据量也与日俱增。人们一直在研究如何高效 利用这些信息来服务大众。数据挖掘就是在这样的背景下发展起来的。它的应用 非常广泛，如商场、证券、地理信息系统、气象、交通等。可以说，只要涉及到 从海量数据集中发现有用的信息、潜在的知识，就脱离不了数据挖掘。随着高维 数据日益成为主流，海量数据及其高维特征使得传统的数据分析手段相形见绌。 同时由于高维数据本身固有的一些特点，在许多情况下，我们不能将用于低维数 据的分析方法直接推广到高维，必须对高维数据进行一些针对性的处理。 本文从数据挖掘的概念及高维数据的特点入手，围绕着“高维数据挖掘中的 特征选择方法”，探讨了分别应用于文本数据和基因表达数据这两种典型的高维 数据的特征选择方法。 针对文本数据，采用词的q u a l i t y 标准进行特征选择及降维，同时在稀疏向量 筛除、基于密度及散布的初始中心点搜索等方法进行改进，提出了一种面向文本 聚类的改进的k 均值算法。 对于基因表达数据，首先提出了一种新的面向基因表达高维数据的特征选择 方法，在特征子集搜索上采用遗传算法进行随机搜索，在特征子集评价上采用基 于边界点可分性度量作为评价指标及适应度函数。进而在此研究的基础上，又提 出一种综合了f i l t e r 及w a p p e r 模型的特征选择方法，首先基于特征之间的信息增 益进行特征分组及筛选，然后针对经过筛选而精简的特征子集采用遗传算法进行 随机搜索，并采用感知器模型的分类错误率作为评价指标。 本文共分为五章，各章主要内容如下： 第一章总体论述了数据挖掘背景，数据挖掘的应用与发展，以及高维数据挖 掘的理论，现状和研究方向。 第二章阐述了特征选择过程，特征选择方法分类以及特征选择方法的选取 原则。 面向高维数据挖掘的特征选择方法研究 第三章讨论用于文本数据的特征选择方法。首先介绍了文本的向量空间模 型，并给出了相似度的定义，然后围绕两个要解决的关键问题进行了算法描述， 并详述了相关的实验研究。这一章的最后给出了此部分问题的结论。 第四章研究用于基因表达数据的特征选择方法，分为两个主要部分。首先介 绍了一种基于区问的二进制编码方案，并提出了一种基于边界点的可分性度量的 特征选择方法。第二部分介绍了在此基础上提出的一种基于信息增益及遗传算法 的特征选择方法。两部分的最后都对相关的实验研究分别进行了详细的论述。 第五章为总结和展望。 面向高维数据挖掘的特征选择方法研究 第1 章数据挖掘概述 1 1 数据挖掘背景 在过去的几十年中，随着计算机硬件技术、数据收集技术和数据存储技术的 快速发展，各行各业都逐步建立起各自的数据库体系。在这些数据库中存放着大 量的数据，如何能有效的利用这些信息，使之能为人们的生产生活实践所利用， 成为一个引起日益关注的问题。然而面对堆积如山的丰富的数据，人们缺乏行之 有效的分析手段和工具，从而造成“数据丰富而信息缺乏”的状况。现有的数据 库检索和查询已经难以满足人们的需要，伴随着数据仓库出现的o l a p ( 联机分 析处理) 技术具有总结、概化和聚集的功能，可以从不同角度来观察数据，支持 多维分析和决策支持，但是它无法进行更深层次的分析和挖掘出大量数据背后所 蕴藏的知识。在这种情况下，数据挖掘技术便应运而生。 数据挖掘( d a t a m i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随 机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和 知识的过程“。还有很多和这一术语相近似的术语，如从数据库中发现知识 ( k d d ) 、数据分析、数据融合( d a t af u s i o n ) 以及决策支持等。人们把原始数 据看作形成知识的源泉，就像从矿石中采矿一样。原始数据可以是结构化的，如 关系数据库中的数据，也可以是半结构化的，如文本、图形、图像数据，甚至是 分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的； 可以是演绎的，也可以是归纳的。发现了的知识可以被用于信息管理、查询优化、 决策支持、过程控制等，还可以用于数据自身的维护。 数据库中的知识发现是一个多步骤的处理过程，一般分为【2 j ： ( 1 ) 学习某个应用领域：包括应用中的预先知识和目标。 ( 2 ) 建立一个目标数据集：选择一个数据集或在多数据集的子集上聚焦。 ( 3 1 数据清理和预处理：去除噪声或无关数据，去除空白数据域，考虑时间 顺序和数据的变化等。 ( 4 1 数据转换：找到数据的特征进行编码，减少有效变量的数目。 面向高维数制挖掘的特征选择力泣f i 究 ( 5 ) 选定数据挖掘算法：决定数据挖掘的目的，用k d d 过程中的准则选择 某一个特定数据挖掘算法( 如汇总、聚类、分类、回归等) 用于嫂索数 据中的模式，它可以是近似的。 ( 6 ) 数据挖掘：通过数据挖掘方法产生一个特定的感兴趣的模式或一个特定 的数据集。 ( 7 ) 斛释：解释某个发现的模式，去掉多余的不切题意的模式，转换某个有 用的模式为知u 。 ( 8 ) 评价知识：将这些知识放到实际系统中，查看这些知识的作用，或者证 明这些知识。用预先可信的知识检查和解决知识中可能的矛盾。 作为现实中的一个应用实例，下图展示了i b m 的i n t e l l i g e n t m i n e r 的通用数 据挖掘方法，此方法体现了这个多步骤处理过程之间的关系。 图1 - 1i b m 的通用数据挖掘方法 面向高维数据挖掘的特征选择方法研究 由此可见，数据挖掘只是数据库中知识发现的一个步骤，但又是最重要的一 步。因此，往往可以不加区别地使用k d d 和数据挖掘。一般在研究领域被称作 数据库中知识发现的，在工程领域则称之为数据挖掘。 数据挖掘是- - f 3 广义的交叉学科，涉及多学科技术的集成，包括数据库技术、 人工智能、统计学、机器学习、高性能计算、模式识别、神经网络、数据可视化、 信息检索、知识库系统、图像与信号处理和空间数据分析。机器学习和数据分析 的理论及实践是数据挖掘研究的基础，极大的商业应用前景又是数据挖掘研究工 作的巨大推动力。传统的数据库查询和统计、报表的处理方式都是对指定的数据 进行简单的数字处理，而不能对这些数据所包含的内在信息进行提取，因此只能 够提供用户想要的信息，而数据挖掘技术则可以发现用户没有意识到的未知的有 价值信息。作为一种在海量数据中发现知识的手段，与传统的数据分析( 如查询、 报表、联机应用分析o l a p 等) 的本质区别在于数据挖掘是在没有明确假设的前 提下去挖掘信息、发现知识的，它可以从大型的数据库或数据仓库中提出隐藏的 预测性信息，从浩如烟海的企业信息资料库中挖掘出更有价值的信息，具有广泛 的应用前景。 数据挖掘所能发现的知识有如下几种【1 l ：广义型知识，反映同类事物共同性 质的知识；特征型知识，反映事物各方面的特征知识；差异型知识，反映不同 事物之间属性差别的知识：关联型知识，反映事物之间依赖或关联的知识；预 测型知识，根据历史的和当前的数据推测未来数据；偏离型知识，揭示事物偏 离常规的异常现象。所有这些知识都可以在不同的概念层次上被发现，随着概 念树的提升，从微观到中观再到宏观，以满足不同用户、不同层次决策的需要。 例如，从一家超市的数据仓库中，可以发现的一条典型关联规则可能是“买面 包和黄油的顾客十有八九也买牛奶”，也可能是“买食品的顾客几乎都用信用 卡”，这种规则对于商家开发和实施客户化的销售计划和策略是非常有用的。 数据挖掘所得到的知识应具有先前未知、有效和可实用性三个特征 1 。先 前未知是指挖掘得到的知识是预先未曾预料到的，即数据挖掘是要发现那些不 能靠直觉发现的信息或知识，甚至是违背直觉的信息或知识，挖掘得到的知识 越是出乎意料，就可能越有价值。知识的有效性要求挖掘前要对被挖掘的数据 进行仔细检查，保证它们的有效性，才能保证挖掘所得知识的有效性。最为重 面向高维数据挖掘的特征选择方法研究 要的是要求所得的知识有可实用性，即这些信息或知识对于所讨论的业务或研 究领域是有效的，是有实用价值和可实现的。常识性的结论，早已被人们或竞 争对手掌握的或无法实现的事实都是没有意义的。 1 2 数据挖掘的应用与发展 1 2 1 数据挖掘的技术和方法 数据挖掘方法是由人工智能、机器学习的方法发展而来，结合传统的统计分 析方法、模糊数学方法以及科学计算可视化技术，以数据库为研究对象，形成了 数据挖掘方法和技术。 下图是摘自k d n u g g e t s c o m 的关于常用数据挖掘技术使用状况的一份调查 ( 2 0 0 3 1 1 1 。 d e c i s i o nt r e e s r u l e s ( 12 0 ) c l u s t e r i n g ( 9 3 ) s t a t i s t i c s ( 9 2 ) n e u r a ln e t w o r k s ( 7 1 ) l o g i s t i cr e g r e s s i o n ( 6 9 ) v i s u a l i z a t i o n ( 5 5 ) a s s o c i a t i o nr u l e s ( 4 2 ) n e a r e s tn e i g h b o r ( 3 8 ) t e x tm i n i n g ( 3 0 ) w e bm i n i n g ( 2 9 ) b a y e s i a nn e t s n a i v eb a y e s ( 2 4 ) s e q u e n c ea n a l y s i s ( 2 4 ) s v m ( s n p p o r tv e c t o rm a c h i n e ) ( 2 4 ) h y b r i dm e t h o d s ( 2 3 ) g e n e t i ca l g o r i t h m s ( 1 2 ) o t h e r ( 2 2 ) 图1 2 k d n u g g e t s ：p o l l sd a t am i n i n gt e c h n i q u e s ( n o v2 0 0 3 ) 从此图看出，当前世界流行的数据挖掘方法或技术大概分为以下几大类1 , 3 1 。 ( 1 ) 信息论方法( 决策树方法) 面向高维数据挖掘的特征选择方法研究 信息论方法是利用信息论的原理建立决策树。在知识工程领域，决策树是一 种简单的知识表示方法，它将事例逐步分类成代表不同的类别。由于分类规则是 比较直观的，因而比较易于理解。该类方法的实用效果好，影响较大。由于该方 法最后获得的知识表示形式是决策树，故一般文献中称它为决策树方法。这种方 法一般限于分类任务。 ( 2 ) 聚类分析 与分类和预测不同，聚类是对记录分组，把相似的记录集中在一个聚类中， 聚类分析数据对象，而不考虑已知的类标记。聚集和分类的区别主要在于聚类不 依赖于预先定义好的类，不需要训练集。聚类分析通常作为数据挖掘的第一步。 例如，“哪一种类的促销对客户响应最好? ”，对于这一类问题，首先对整个客户 做聚类，将客户分组在各自的聚类( c l u s t e r ) 里，然后对每个不同的聚类回答问 题，往往效果更好。 ( 3 ) 统计分析方法 利用统计学原理对数据库中的数据进行分析。属于这类商品有美国的s a s ， s p s s 等。 常用统计：求整个数据集合中的最大值、最小值、总和、平均值等。 相关分析：求相关系数来度量变量间的相关程度。 回归分析：求回归方程( 线性或非线性) 来表示变量问的数量关系。 差异分析：从样本统计量的值得出差异，来确定总体参数之间是否存在差异 ( 假设检验) 。 判别分析：建立一个或多个判别函数，并确定一个判别标准。对未知对象利 用判别函数将它划归某一个类别。 b a y e s 网络：利用联合概率和b a y e s 公式所描述的各网络变量( 节点) 间的 因果关系来进行数据分析。 ( 4 ) 仿生物技术 仿生物技术典型的方法是神经网络方法和遗传算法。这两类方法已经形成了 独立的研究体系。它们在数据挖掘中也发挥了巨大的作用，将它们归并为仿生物 技术类。 神经网络方法是模拟了人脑神经元结构，以m p 模型和h e b b 学习规则为基 面向高维数据挖掘的特征选择方法研究 础的，建立了如下三大类多种神经网络模型。 前馈式网络：它以感知机、b p 反向传播模型、函数型网络为代表。此类网 络可用于预测、模式识别等方面。 反馈式网络：它以h o p f i e l d 的离散模型和连续模型为代表，分别用于联想记 忆和优化计算。 自组织网络：它以a r t 模型、k o h o n e n 模型为代表。 神经网络的知识体现在网络连结的权值上，是一个分布式矩阵结构。神经网 络的学习体现在神经网络权值的逐步计算上( 包括反复迭代或者是累加计算) 。 当需要复杂或不精确数据巾导出概念和确定走向比较困难时，利用神经网络技术 特别有效。 遗传算法是模拟生物进化过程的算法。它由三个基本算子组成： 繁殖( 选择) ：从一个旧种群( 父代) 选择出生命力强的个体产生新种群( 后 代) 的过程。 交叉( 重组) ：选择两个不同个体( 染色体) 的部分( 基因) 进行交换，形 成新个体。 变异( 突变) ：对某些个体的某些基因进行变异( 1 变0 ，0 变1 ) 。 这种遗传算法起到产生优良后代的作用。这些后代需要满足适应值，经过若 干代的遗传，将得到满足要求的后代( 问题的解) 。遗传算法已在优化计算和分 类机器学习方面发挥了显著的效果。 ( 5 ) 可视化技术 可视化数据分析技术拓宽了传统的图表功能，使用户对数据的剖析更清楚。 例如把数据库中多维的数据变成多种图形，这对于揭示数据中的状况，内在本质 以及规律性起到很强的作用。可视化数据挖掘的目的是使用户能够交互地浏览数 据，挖掘过程等，可分为：源数据叮视化，规则可视化，数据挖掘结果可视化， 数据挖掘过程可视化等。 ( 6 ) 模糊数学方法： 利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识别和模 糊聚类分析。由于模糊性是客观的存在，而且系统的复杂性愈高，使精确化能力 便愈低，这就意味着模糊性愈强，这就是z a d e h 总结出的互克性原理。以上提到 8 面向高维数据挖掘的特征选择方法研究 的模糊方法都取得了较好的效果。 ( 7 ) 其它的方法：还有许多其它的方法如逻辑回归方法、关联规则方法、最 近邻方法、文本挖掘、w e b 挖掘、序列分析、s v m 、h y b r i d 等，也常被一些 特定领域广泛采用。 1 2 2 数据挖掘的研究现状及发展趋势 数据挖掘技术从一开始就是面向应用的。它不仅仅是面向特定数据库的简单 的检索查询或者调用，而且要对这些数据进行微观、中观乃至宏观的统计、分析、 综合和推理，以指导实际问题的求解，企图发现事件间的相互关联，甚至利用已 有的数据对未来的活动进行预测。例如在银行信用卡和保险行业，预测存贷款 趋势，优化存贷款策略，利用数据挖掘将市场划分为有意义的群组和部门，从 而协助市场经理和业务执行人员更好地集中于有促进作用的活动和设计新的市 场运动。近年来，数据挖掘技术在基因工程中的染色体、基因序列的识别、分析、 基因挖掘、基因表达路径分析、基因表达相似性分析、基因表达共发生分析、制 药、生物信息、科学研究等方面也有重要的应用。在客户关系管理方面，数据挖 掘能找出产品使用模式或协助了解客户行为，从而可以改进通道管理( 如银行分 支和a t m 等) ，又如正确时间销售( r i g h tt i m em a r k e t i n g ) ，基于顾客生活周期 模型来实施的产品推荐、客户细分、客户流失、客户利润、客户响应等。这样一 来，就把人们对数据的应用，从低层次的末端查询操作，提高到为各级经营决策 者提供决策支持。这种需求驱动力，比数据库查询更为强大。 同时需要指出的是，这里所说的知识发现，不是要求发现放之四海而皆准的 真理，也不是要去发现崭新的自然科学定理和纯数学公式，更不是什么机器定理 证明。所有发现的知识都是相对的，是有特定前提和约束条件、面向特定领域的， 同时还要能够易于被用户理解，最好能用自然语言表达发现结果。 自k d d 一词首次出现在1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会 议以来。迄今为止，由美国人工智能协会主办的k d d 国际研讨会已经召开了1 3 次，规模由原来的专题讨论会发展到国际学术大会，人数由二三十人到超过千人， 论文收录数量也迅速增加，研究重点也从发现方法逐渐转向系统应用直到转向大 面向高维数据挖掘的特征选择方法研究 规模综合系统的开发，并且注重多种发现策略和技术的集成，以及多种学科之间 的相互渗透。其他内容的专题会议也把数据挖掘和知识发现列为议题之一，成为 当前计算机科学界的一大热点。 目前，国外数据挖掘的发展趋势主要有：对知识发现方法的研究进一步发展， 如近年来注重对b a y e s ( 贝叶斯) 方法以及b o o s t i n g 方法的研究和提高：传统的 统计学回归法在k d d 中的应用；k d d 与数据库的紧密结合等。在应用方面包括： k d d 商业软件工具不断产生和完善，注重建立解决问题的整体系统，而不是孤 立的过程。用户主要集中在大型银行、保险公司、电信公司和销售业。国外很多 计算机公司非常重视数据挖掘的开发应用，m 和微软都成立了相应的研究中 心进行这方面的工作。很多大公司也对数据挖掘应用的研究投入大量精力，经过 多年的努力，关于数据挖掘技术应用的研究也取得了丰硕的成果。一些公司已经 开发了多种数据挖掘相关的产品，据不完全统计，目前已经有了数百个数据挖掘 软件产品。如m 公司开发的q u e s t 和i n t e l l i g e n tm i n e r ；a n g o s ss o f t w a r e 开 发的基于规则和决策树的k n o w l e d g es e e k e r ；a d v a n c e ds o f t w a r ea p p l i c a t i o n 开发 的基于人工神经网络的d bp r o f i l e ：加拿大s i m o nf r a s e r 大学开发的d bm i n e r ； s g i 公司开发的m i n es e t 等。 与国外相比，国内在该领域的研究起步稍晚，没有形成整体力量。1 9 9 3 年 国家自然科学基金首次支持对该领域的研究项目。近年来，国内的许多科研单位 和高等院校竞相开展知识发现的基础理论及其应用研究，这些单位包括清华大 学、中科院计算技术研究所、空军第三研究所、海军装备论汪中心等。其中，北 京系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究，北京大 学也在开展对数据立方体代数的研究，华中理工大学、复旦大学、浙江大学、中 国科技大学、中科院数学研究所、吉林大学等单位开展了对关联规则丌采算法的 优化和改造；南京大学、四川联合大学和上海交通大学等单位探讨、研究了非结 构化数据的知识发现以及w e b 数据挖掘。 可以看出，数据挖掘的研究和应用受到了学术界和商业界越来越多的重视， 预计在本世纪中期还会形成更大的高潮，研究焦点可能会集中到以下几个方面： 研究专门用于知识发现的数据挖掘语言，也许会像s q l 语言一样走向形式化和 标准化；寻求数据挖掘过程中的可视化方法，使得知识发现的过程能够被用户理 面向高维数据挖掘的特征选择方法研究 解，也便于在知识发现过程中的实现人机交互；研究在网络环境下的数据挖掘技 术，特别是在i n t e m e t 上建立数据挖掘与知识发现服务器，与数据库服务器配合， 实现数据挖掘：加强对各种非结构化数据的挖掘，如文本数据、图形图像数据、 多媒体数据。但是无论怎样，需求牵引与市场驱动是永恒的，数据挖掘将首先满 足信息时代用户的急需，大量基于数据挖掘的决策支持软件工具产品将会问世。 1 3 高维数据挖掘 如前所述，数据挖掘技术已经在许多领域得到了广泛的应用，在这些应用中， 人们经常会遇到一些对象，它们可能有几十、几百甚至上万个属性。通过将这些 对象表示成高维属性空间中的点或向量，把客观世界中的对象集用高维数据集合 来表示。高维数据挖掘就是通过对这类数据进行一系列的挖掘工作来解决问题。 下面是一些常见的高维数据的例子。 1 3 1 购物篮数据 在零售商业中，一个客户的一次购物行为可以看作是一个交易。该客户所购 买的商品集合构成一个交易记录，形象的称为“购物篮”。交易数据库中记录着 许多客户的交易记录。可以将所有的商品种类看作一个表的列，而客户的一次购 物看作表的行，如果在该次购物中有某种商品，就在对应的列上记录1 ( 表示购 买了该商品) 或一个其它有意义的数值( 如商品的数量或价值等) ，否则就记为 0 或空值。由此，将购物篮数据看作以商品的种类为维，以交易为记录的多维数 据。由于商品的种类一般都非常多( 几千甚至几万种) ，因此购物篮数据实际上 是一种很高维的数据。 1 3 2 文本数据 在信息检索领域，经常用向量空间模型来表示每个文本。在这种模型中，每 个文本d 被认为是向量空间内的一个向量。通常，每个文本用词频t f ( t e r m - f r e q u e n c y ) 向量办= c t f a ，吸，坑) 来表示，这里够指在这篇文档中第i 个词出现的频率。大多数情况下，词空间是一个很高维的空间，因此在空间向量 面向高维数据挖掘的特征选择方法研究 模型中，文本数据是一种高维的数据。 1 3 3 时间序列数据 时间序列数据是一种特殊的序列数据，时间序列数据由一系列随时间变化的 值组成，测量这些值的时间间隔是等问距的。时间序列数据库在证券期货、科学 实验和药物研究等方面都有重要的应用。如一个事件在一个等间隔的时间序列 ，f 2 ，乙上的值分别为_ ，屯。，那么我们可以把这个事件表示为 x = x j x ：矗，这样就将时间序列数据看作一个n 维的向量。由于在实际中时间 序列的长度很长，因此时间序列数据是一种高维数据。 i 3 4 基因表达数据 基因表达数据是由基因芯片实验产生的。如酵母基因芯片实验可产生6 2 2 3 种基因在7 9 种条件f 的表达数据。这种数据可以表示成一个矩阵，每个行对应 一个基因，每- y u 表示一个条件。每个数值表示一个基因在特定条件下的m r n a 相对丰度。由此可见，基因表达数据是一种相当高维的数据。生物学家意在通过 这种数据找到在特定条件组合下表现出强烈相似基因集合。 1 3 5 w e b 使用数据 在基于w e b 的应用中，w e b 日志记录用户对w e b 页的使用模式，通过分析和 探索w e b 日志中的用户规律，可以为电子商务识别潜在客户，提高终端用户的 服务质量以及改善w e b 服务器的性能。用户使用w e b 的模式页可以表示成高维 数据的形式，w e b 服务器中的每一个w e b 孤可以看作高维空间中的一维，在每一 维上的数值可以表示多种意义，如，用户是否访问该网页或在该网页停留的时问 等等。 由于在现实世界中存在大量的高维数据，而这些高维数据与低维数据相比， 在许多方面表现出不同的特征。如果将用于低维数据的挖掘方法直接应用于高维 数据可能会产生完全不同的结果，因此必须研究适用于高维数据挖掘的理论和方 法，这对完善数据挖掘理论以及拓展数据挖掘的应用领域有着重要的意义。 面向高维数据挖掘的特征选择方法研究 1 4 高维数据挖掘中的问题及研究方向 1 4 1 高维数据的特点 ( 1 ) 稀疏性 假设一个d 维的数据集d 存在于一个超立方体单元q = o ，l r 中，数据在空 间中均匀分布，并且各个维之间是独立的。对一个边长为s 的超立方体范围，一 个点在这个范围内的概率为一，由于s l ，因此随着维数d 的增大，这个概率 值会越来越小，也就是说即使在一个很大的范围内也很可能一个点也不包含。因 此得出结论，在高维空间中，数据点是非常稀疏的。前面所提到的文本数据就是 高维空间中非常稀疏的数据的一个典型的例子。 ( 2 ) 维度灾难 b e l l m a n 第一次提出了“维度灾难”这一术语( ”。它最初的含义是不可能在 一个离散的多维网格上用蛮力搜索去优化个有着很多变量的函数，这是因为网 格的数目会随着维数( 也即是变量的数目) 呈指数级的增长。后来，“维度灾难” 这一术语用来泛指在数据分析中遇到的由于变量( 属性) 过多而引起的所有问题， 其中一个主要的表现为，在高维空间中，查询点到它的最近邻和最远邻在很多情 况下几乎是等距离的，在这种情况下，最近邻的概念常常失去意义5 1 。 1 4 2 高维对数据挖掘的影响 数据挖掘面对的是海量的数据，为了提高最近邻查询的效率，往往需要索引 结构的支持，在进行高维数据的最近邻查询时，由于维度灾难而导致索引结构的 性能下降或失效，从而使得算法的复杂度增加，导致查询效率的下降。到目前为 止，对高维最近邻查询的研究主要集中在一般数值型数据的选维，降维和高维索 引结构等方面，高维数据间的相似性度量还主要采用上一范数。其中，选维和降 维技术在数据集的维之间存在较强的相关性时效果较好，且采用不同的选维和降 维标准，得到的维空间大小会有不同，其结果也会有较大的差别。另外，所有的 高维索引结构都有一个性能上限，超过这个界限后，就会失去对数据的修剪作用。 更进一步，维度灾难还可能会使高维空间中的最近邻概念失去意义。 面向高维数据挖掘的特征选择方法研究 此外，目前在数据挖掘中的分类聚类和异常的概念大多是基于距离或密度 的，高维对分类聚类和异常检测的影响主要表现在两个方面，一方面由于在高维 空间中索引结构的失效使得聚类和异常检测算法的性能下降；另一方面由于在高 维空问中很多情况下，数据点之间几乎是等距离的，使得分类聚类的概念失去意 义，同样由于高维空间中数据的高度稀疏性，每个数据点在距离或密度的意义上 都可以看作是一个异常点，使得异常的概念也失去了本意。 1 4 3 高维数据挖掘的研究方向 ( 1 ) 距离函数或相似性度量函数 由于“维度灾难”与传统上采用上一范数作为距离函数有关，因此通过重新 定义合适的距离函数或相似性度量函数可以避开“维度灾难”的影响。 ( 2 ) 高效的相似性搜索算法 设计更为高效的相似性搜索算法，包括两部分内容：一是对现在未涉及或研 究较少的其它类型高维数据相似性搜索方法的研究：另一个是对现有高维索引结 构或搜索算法性能的改进。 ( 3 ) 高效的聚类算法和异常检测算法 在高维索引结构失效的情况下，在聚类算法或异常检测算法中采用并行算 法、增量算法以及采样技术等提高算法的效率。 ( 4 ) 在高维空间中对失效问题的处理 如前所述，在高维的情况_ f ，最近邻的概念失去了意义，从而也会导致基于 距离的聚类和异常检测问题失去意义，这些问题在高维情况下需要重新定义，并 设计或改进相应的挖掘算法。 ( 5 ) 选维和降维 通过选维和降维，可以将高维数据转换为低维数据，然后采用低维数据的处 理方法进行处理。因此研究行之有效的选维和降维技术也是解决高维数据挖掘问 题的重要手段之一。 面向高维数据挖掘的特征选择方法研究 第2 章特征选择概述 特征选择是模式识别与数据挖掘领域的重要数据处理方法之一。随着模式识 别与数据挖掘研究的深入，研究对象越来越复杂，对象的特征维数越来越高。大 量高维数据对象的特征空间中含有许多冗余特征甚至噪声特征，这些特征一方面 可能降低分类或聚类的精度，另一方面会大大增加学习及训练的空间及时间复杂 度。因此，在面对高维数据进行分析时，通常需要运用特征选择方法找到具有较 好可分性的特征子空间，从而实现降维，降低机器学习的时间及空间复杂度。 2 1 特征选择过程 特征选择定义为从有n 个特征的集合中选出具有m 个特征的子集，并满足 条件m n 6 1 。它包括特征提取和特征选择两个方面：特征提取广义上指的是一 种变换，将处于高维空间的样本通过映射或变换的方式转换到低维空间，达到降 维的目的：特征选择指从一组特征中去除冗余或不相关的特征来降维。二者常联 合使用，如先通过变换将高维特征空间映射到低维特征空间，然后再去除冗余的 和不相关的特征来进一步降低维数。 有很多学者从不同的角度对特征选择进行了定义。j o i l n 【从提高预测精度角 度定义特征选择为选择特征子集来增加分类精度，或者在不降低分类器精度的条 件下降低特征集维数的过程；k o l l e r 8 l 从类分布的角度定义特征选择，即，在保 证结果类分布尽可能与原始数据类分布相似的条件下，选择尽可能小的特征子 集；d a s h 9 】认为选择尽量小规模的特征子集，同时不会显著降低分类精度和不会 显著改变类分布。上述定义各有侧重点，但均未对特征子集的稳定性加以考虑。 而不同的分类器适应的特征组合和数目是不同的，能够使一个分类器获得最优结 果的特征子集，却不一定适用于其他分类器 10 】。因此，特征选择除了考虑对分 类结果等的影响外，特征自身的稳定性也是一个值得关注的因素。 面向高维数据挖掘的特征选择方法研究 2 2 特征选择方法分类 特征选择需要解决两个问题，一是确定选择算法，在允许的时问内，以可以 容忍的代价找出最小的、最能描述类别的特征组合；二是确定评价标准，衡量特 征组合是否最优，得到特征选择操作的停止条件。因此，一般分两步进行特征选 择，首先产生特征子集并对特征子集进行评价。如果满足终止条件则操作完毕， 否则重复上述步骤直到条件满足为止。 按照特征子集的形成方式，特征选择方法可分为穷举法、启发法和随机法三 类 9 o 穷举法指遍历特征空间中所有特征的组合，选取最优特征组合子集的方法。 假设特征个数为n 时，计算复杂度为0 ( 2 ”) 。常用的方法有回溯方法及其变体等， 其优点在于一定能得到最优子集，但实际情况下由于特征空问过于庞大，时间代 价和计算复杂度太大，因此实用性并不强。 启发式方法是一种近似算法，具有较强的主观倾向。实际应用中通过采用期 望的人工机器调度规则，重复迭代产生递增的特征子集。特征个数为n 时，复 杂度一般小于或等于o ( n 2 ) 。这种方法实现过程比较简单且快速，在实际中应用 的较为广泛，如前向( 后向) 选择、决策树方法、r e l i e f 方法等，不过一般能够 获得的是近似最优解。 随机方法是一种相对较新的方法，细分为完全随机方法和概率随机方法两 种。完全随机方法是指“纯”随机产生子集，概率随机方法是指子集的产生依照 给定的概率进行。虽然计算复杂度仍为0 ( 2 ”) ，但通过设置最大迭代次数可以限 制复杂度小于0 ( 2 ”) 。常用的方法有l v f ( l a sv e g a sf i l t e r ) 、遗传算法及其变体 等。这类方法需要进行参数设置，并且参数值决定是否能得到最优解，如何有效 的设置这些参数也是一个值得研究的问题。 上述三类算法中只有穷举法能保证最优