（计算机软件与理论专业论文）基于som神经网络的聚类可视化方法研究.pdf

摘要 随着数据库技术的成熟应用和i n t e r n e t 的迅速发展，人们利用信息技术生产和搜 集数据的能力大幅度提高，使得从大量数据中挖掘出有用的信息或知识成为一个迫切需 要解决的问题。正是这种需求推动了数据挖掘的兴起和数据挖掘技术的发展。数据挖掘 经常要面对一些有噪声、杂乱、非线性的数据，而神经网络具有良好的鲁棒性、自适应 性、并行处理、分布存储和高度容错性等特点，因此神经网络非常适合解决数据挖掘的 一些问题。 聚类分析是数据挖掘的一项重要功能，特别对高维数据的分析具有非常大的优势。 自组织特征映射( s o m ) 神经网络不但在数据挖掘、机器学习、模式分类和可视化中得到 了广泛的应用，同时可视化技术是进行生物数据挖掘的重要手段。 本文以聚类算法为基础，总结和分析现有的数据可视化方法，对聚类结果可视化技 术进行深入且细致的研究。并提出用非线性主成分分析( n l p c a ) 和自组织映射( s o m ) 网 络相结合的方法对生物信息学中基因表达数据进行聚类可视化分析。通过对实验结果的 分析，表明这种方法有较高的聚类j 下确率，用于基因表达数据的聚类分析是行之有效的。 关键词：数据挖掘；自组织特征映射神经网络；非线性主成分分析( n l p c a ) ；聚类分 析；可视化 a b s tr a c t w i t ht h ew i d ea p p l i c a t i o no fd a t a b a s e sa n ds h a r pd e v e l o p m e n to f i i l t e m e t ，t h ec a p a c i t y o fu t i l i z i n gi n f o r m a t i o nt e c h n o l o g yt om a n u f a c t u r ea n dc o l l e c td a t ah a si m p r o v e dg r e a t l y i ti s a nu r g e n tp r o b l e mt om i n eu s e f u li n f o r m a t i o no rk n o w l e d g ef r o ml a 唱ed a t a b a s e so rd a t a w a r e h o u s e s t h e r e f o r e ，d a t am i n i n gt e c h n o l o g yi sd e v e l o p e dr a p i d l yt om e e tt h en e e d b u t d a t am i n i n g ( d m ) o f t e nf a c e ss om u c hd a t aw h i c hi sn o i s y , d i s o r d e ra n d n o n l i n e a r f o r t u n a t e l y , a r t i f i c i a ln e u r a ln e t w o r k ( a n n ) i ss u i t a b l et os o l v et h eb e f o r e m e n t i o n e dp r o b l e m so fd m b e c a u s ea n nh a ss u c hm e r i t sa s g o o dr o b u s t n e s s ，a d a p t a b i l i t y , p a r a l l e l d i s p o s a l ， d i s t r i b u t i n g - m e m o 巧a n dh i g hf a u l tt o l e r a n c e c l u s t e ra n a l y s i si sa ni m p o r t a n tf u n c t i o ni nt h ed a t am i n i n gt e c h n i q u e s ；e s p e c i a l l yi th a s s u p e r i o r i t yf o rh i g h t e rd i m e n s i o n a ld a t a t h es e l f - o r g a n i z i n gm a p ( s o m ) n e u r a ln e t w o r ki sa e x c e l l e n tt o o lf o rd a t a m i n i n g ，m a c h i n el e a r n i n g ，p a t t e r nc l a s s i f i c a t i o na n dv i s u a l i z a t i o n a n d t h ev i s u a l i z a t i o ni si m p o r t a n tm e t h o df o rd a t am i n i n gi nb i o i n f o r m a t i c s a sc l u s t e r i n ga l g o r i t h m ，t h ed i s s e r a t i o ns u m m a r i z e sa n da n a l y z e ss o m ee x i s t i n gd a t a v i s u a l i z a t i o nt e c h n i q u e s ，a n di nd e t a i ls t u d i e sr e s u l t so fc l u s t e r i n ga n a l y s i s a na p p r o a c ho f n o n l i n e a r p r i n c i p a lc o m p o n e n ta n a l y s i s ( n l p c a ) a n ds e l f - o r g a n i z i n gm a p ( s o m ) n e u r a l n e t w o r ki sp r e s e n t e di nt h i sp a p e r ，w h i c hc a nd i s c u s sc l u s t e r i n ga n dv i s u a l i z a t i o no fg e n e e x p r e s s i o nd a t a t h ee x p e r i m e n tr e s u l t ss h o w st h a tt h ep e r f o r m a n c eo fc l u s t e r i n gg e n e e x p r e s s i o nd a t ab a s e do nt h es o mn e t w o r ki se f f i c i e n t k e yw o r d s ：d a t am i n i n g ；t h es e l f - o r g a n i z i n gm a p ( s o m ) n e u r a ln e t w o r k ；n o n l i n e a r p r i n c i p a lc o m p o n e n t sa n a l y s i s ；c l u s t e r i n ga n a l y s i s ；v i s u a l i z a t i o n i i 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究 工作所取得的成果。据我所知，除了特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果。对本人的研究做出重要贡 献的个人和集体，均已在文中作了明确的说明。本声明的法律结果由本人 承担。 、 学位论文作者签名：氇 日期： 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规 定，即：东北师范大学有权保留并向国家有关部门或机构送交学位论文的 复印件和电子版，允许论文被查阅和借阅。本人授权东北师范大学可以将 学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或其它复制手段保存、汇编本学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：盟 指导教师签名：垡垫亟聋 学位论文作者签名：卫垒 指导教师签名：绁壁! 车 日 期：口掣，夕日期：立兰心 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 东北师范大学硕士学位论文 第1 章绪论 1 1 研究的背景和意义 现代信息技术的高速发展，数据库应用的规模、范围不断扩大，可以获得的数据量 越来越大，数据的种类也日益增多，特别是由于互联网的发展带来的海量的数据和信息。 面对如此大规模的、并且存在着噪声的数据海洋，如何从中提取出隐含的、有意义的、 对决策有用的信息或知识，进一步提高信息利用率，成为“信息时代 亟待解决的一个 问题。数据挖掘，又称为数据采掘、数据开采，相近的术语有k d d ( 数据库知识发现) 、 数据分析、数据融合、决策支持等。根据w j f r a w l e y 和g p s h a p i r o 等人的定义，数据 挖掘是指从大型数据库的数据中提取人们感兴趣的知识，而这些知识是隐含的、事先未 知的、潜在的有用信息。原始数据可以是结构化的，如关系型数据库中的数据，也可以 是半结构化的，如文本、图形、图像数据，还可以是分布在网络上的异构型数据。发现 知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现 的知识可以被用于信息管理、查询优化、决策支持、过程控制等，还可以用于数据自身 的维护。数据挖掘在数据库、人工智能、数理统计、可视化、并行计算等领域都有着广 泛的研究前景，国内外许多研究工作者对该领域投入了极大的热忱。 在数据挖掘中，聚类分析是一个具有挑战性的领域，聚类就是将数据对象分组成为 多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。 相异度是根据描述对象的属性值来计算的。距离是经常采用的度 量方式。聚类不同于分类，在分类模块中，对于目标数据库中存在哪些类是已知的，要 做的就是将每条记录分别属于哪一类标记出来；而聚类所要划分的类是未知的，也就是在 对目标数据库到底有多少类预先不知道的情况下，希望将所有的记录组成不同的类或者 说“聚类”，并且使得在这种分类情况下，以某种度量为标准的相似性，在同一聚类之 间最小化，在不同类之间最大化。由聚类所生成的簇是组数据对象的集合。 在数据挖掘中，多维数据的可视化分析已成为探测数据中隐藏信息的强有力工具。 通过人机交互，可以充分利用人类的感知、联想能力以及领域知识，将图形所呈现出的 数据结构特征及关联特征转换为可利用的、有用的信息。多维数据可视化比低维数据可 视化有更大的难度。 我们知道图形是帮助人们思维和判断的重要手段，当数据只有一个或两个变量时， 可以用通常的直角坐标在平面上作图。当数据有三个变量时，虽然也可以在三维坐标上 作图，但已经感到很不方便。当变量多于三个时，由于笛卡儿坐标系最多只有三个坐标， 因此已经不能用通常的方法作图了。而且在大型数据库中的多维数据集一般不含有空间 语义，数据集的各维之间没有空间连贯性，这也很难用传统的二维或三维图形直接表示 东北师范大学硕士学位论文 多维数据。数据挖掘中的可视化主要包括四个方面【2 】：数据准备阶段的可视化、模型生成 阶段的可视化、挖掘过程中的可视化和结果呈现阶段的可视化。 1 2 可视化技术的重要性和应用 l 、可视化数据挖掘的重要性：( 1 ) 通过提供对数据和知识的可视化，可以利用人类 的模式识别能力评估和提高挖掘出的结果模式的有效性。( 2 ) 利用可视化技术建立用户 与数据挖掘系统交互的良好沟通渠道，使用户能够通过专业知识来规整、约束挖掘过程， 改善挖掘结果。( 3 ) 提供对挖掘结果的可视化显示，使用户对结果模式能够有深刻直观 的理解，从而打破传统挖掘算法的黑盒子模式，使用户对挖掘系统的可信度大大提高。 2 、可视化技术的应用 数据可视化的应用十分广泛，几乎可以应用于自然科学、工程技术、金融、通信和 商业等各种领域，从医学到显微摄影学、物理学、化学、地质学、工业检测、计算流体 力学、有限元分析等学科和领域中，可视化都起到了非常重要的作用。这些应用可以概 括如下幻： ( 1 ) 医学成像：诊断、手术规模和模拟、整形术、定位、测量和分析等。 ( 2 ) 工业无损探伤：用工业c t 进行机械或铸造的质量检测。 ( 3 ) 生物学：对动物和植物的宏观和微观结构进行显示、分析。 ( 4 ) 计算模型可视化：对复杂的计算模型和一些隐式数学函数进行分析。 ( 5 ) 地质学：用各种探测仪器获得的测量数据重构地层结构，分析地质构成， 帮助地质学家发现矿藏。 ( 6 ) 物理和化学研究：对各种实验数据进行处理分析，如进行流体动力学分 析、电子雾分析。 ( 7 ) 造型设计：基于数据表示模型的计算机辅助设计，如机械零件的设计。 ( 8 ) 气象学：分析气压图、云层图、环流图等三维数据，进行天气预报。 可以通过数据可视化技术，发现大量金融、通信和商业和自然科学研究的数据中隐 含的规律，为决策提供依据。己成为数据挖掘中新的热点。 1 3 可视化数据挖掘的发展 可视化技术与数据挖掘技术的结合形成的可视数据挖掘经历了若干阶段1 ( 1 ) 初级 图表可视化阶段，在此阶段只是利用图表、曲线( 直方图、饼图等) 显示数据的统计信息 ( 总和、均值等) ；( 2 ) 信息查询可视化阶段，此阶段主要利用可视化的人机界面，用图 形、图像显示查询结果，对复杂的查询起到直观的表达，便于用户理解；( 3 ) 可视数据 挖掘阶段，此阶段可以用图形方式表示数据之间的内在联系及发展规律，并引导整个数 据挖掘过程的进行。 利用可视化技术表示抽象的数据集早在计算机图形发展的初期就被提出来，在实现 2 东北师范大学硕士学位论文 了可视化查询的阶段后，发展一度缓慢。但是近些年来，随着社会生活信息量的增大， 数据仓库技术的提出，人工智能、数据挖掘、机器学习等技术的发展，以及对数据分析 技术的需求，使可视化技术在数据库中的应用得到了普遍重视和新的发展，尤其是其中 更加突出了多维数据分析的手段和数据挖掘技术的运用，使数据可视化及可视数据挖掘 成为一个新兴的和重要的研究方向。 全世界各高校及科研单位中有5 0 多个数据可视化的研究组，1 0 多个专门的期刊和杂 志，每年都有多个数据可视化或可视化数据挖掘的国际会议或国际论坛，如i e e e 在1 9 9 5 年以后每年都举办一次信息可视化国际会议。目前研制和开发的数据可视化产品也有数 十种。比较完善的产品及其开发研究组包括：( 1 ) d e v i s e ：由w i s c o n s i n 大学开发，系统 中集成了多种可视化技术，对相同的数据集可用不同的方法观察。( 2 ) d q i ：由m a r y l a n d 大学开发，该系统主要运用散点图技术并采用了动态人机交互手段。( 3 ) v is d b ：由m u n i c h 大学开发。该系统采用面向象素的技术，运用颜色和距离反映数据之间的相似度。( 4 ) t a b l el e n s ：由施乐公司帕洛阿尔托研究中心开发，主要用符号或图形来代表数据表中 的数据。( 5 ) x g o b i ：由贝尔实验室开发，该系统也是多种技术的集成，提供动态的人机 交互功能。( 6 ) d b m i n e r ：由加拿大s i m o nf r a s e r 大学开发的可视化数据挖掘系统，该系 统集成了数据仓库技术、数据挖掘技术和可视化技术。 1 4 论文研究的内容 本文基于s o m 神经网络对数掘进行聚类分析，并对结果进行可视化研究。 论文将详细介绍非线性主成分分析法对数据进行降维处理的过程，并对基因表达样本数 据提取非线性主成分，然后结合传统s o m 网络进行聚类分析的可视化，通过映射结果分 析和传统方法的比对，表明这种方法具有较高的聚类正确率，而且有较好的可视化效果， 用于基因表达数据的聚类分析是行之有效的。 围绕以上问题，论文的章节及内容安排如下： 第一章主要介绍论文的写作背景和意义以及可视化技术的相关理论。 第二章主要介绍数据挖掘技术的发展及相关理论。 第三章侧重于研究基于神经网络的数据挖掘方法，介绍了神经网络的基本概 况，分析了s o m 神经网络的聚类过程。 第四章着重研究神经网络在可视化方面的应用，并介绍了解决可视化问题的常用方 法。 第五章总体设计是本文的精华所在，以第三、四章的理论知识为基础，提出了基于 s o m 神经网络的可视化模型。并在实验数据库上进行实验和测试，最终验证了本文方 法的优越性和准确度。 第六章全文的总结。 东北师范大学硕士学位论文 第2 章数据挖掘理论概述 2 1 数据挖掘的定义 1 9 8 9 年，在美国底特律召开的第十一届国际人工智能联合会议的专题讨论会上首次 提出了基于数据库的知识发现( k n o w l e d g ed i s c o v e rb a s e do i ld a t a b a s e ) 概念。到了1 9 9 5 年，k d d 专题讨论会更名为国际会议，并在加拿大蒙特尔市召开了第一届k d d 国际学术 会议，之后每年召开一次。同年，在美国计算机年会( a c m ) 上提出了数据挖掘的概念。“数 据挖掘”和“知识发现”两者在本质上是一致的，是对同一事物的不同表述。相对来讲， 数据挖掘主要流行于统计、数据分析、数据库和管理信息系统( m i s ) 界；而知识发现( k d d ) 主要流行于人工智能和机器学习界。 数据挖掘比较公认的描述性定义是由u m f a y y a d 等给出的，即数据挖掘是从数据 集中识别出有效的、新颖的、潜在有用的以及最终可理解的模式的非平凡( n o n t r i v i a l ) 过程h 1 。下面对这个定义中的几个关键词分别进行解释。 模式是一种用语言来表示的表达式，可用来描述数据集的某个子集。它可以看作我 们平常所说的知识，给出了数据的特征和数据之间的关系，是对数据包涵的信息更抽象 的描述。例如 i fx o 就可以称之为一条模式。多个模式组合在一起就形 成一个模型。 非平凡过程是指对大量数据进行分析处理的过程，包括数据准备、模式提取、知识 评价，以及反复的求精。该过程要求是非平凡的，意思是要有一定程度的智能性、自动 性。 有效性是指发现的模式对于新的数据仍保持有一定的正确性。 新颖性要求发现的模式应该是新颖的。判断是否新颖可以通过两个途径来衡量：首 先是通过对比当前得到的数据和以前的数据或期望得到的数据来判断该模式的新颖程 度；其次是通过其内部所包含的知识，并运用对比发现的模式的关系来判断该模式的新 颖程度。 潜在有用性是指发现的知识将来有实际效用，如用于决策支持系统里可以提高经济 效益。最终可理解性要求发现的模式能够被用户理解，无法理解的模式对用户是无用的。 2 2 数据挖掘工作流程 数据挖掘是一个多步骤的反复迭代的过程，根据用户对进程状态或结果模式的满意 度，可能需要返回到先前的某个步骤重新操作。粗略地可将数据挖掘过程分为四个主要 阶段n 1 ：问题定义、数据准备、数据挖掘算法执行( 模式提取) 、结果解释与评估，其基 本工作流程如图2 1 所示。 4 东北师范大学硕士学位论文 图2 - 1 数据挖掘工作流程 1 问题定义数据挖掘的目的是为了在大量数据中发现有用的令人感兴趣的信息， 因此发现何种知识就成为整个过程第一个也是最重要的一个阶段。在问题定义过程中， 数据挖掘人员必须和领域专家紧密协作，一方面明确实际工作对数据挖掘的要求；另一 方面通过对各种学习算法的对比进而确定可用的学习算法。后续的学习算法选择和数据 准备都是在此基础上进行的。 2 数据准备( d a t ap r e p a r a t i o n ) 阶段数据准备可以分为以下几个步聚：数据清洗、 数据选取、数据预处理和数据表示。拥有数据是进行数据挖掘的前提条件，但仅仅拥有 数据是不够的，因此必须在进行数据挖掘之前进行数据准备。所谓数据就是对被挖掘的 数据进行定义、处理和表示，以使它适应于特定的数据挖掘方法。数据准备是数据挖掘 过程中的一个重要前期步骤，在整个数据挖掘过程中起着举足轻重的作用。 数据清洗：数据清洗就是填充数据中的空缺值，清除噪声数据，纠正数据集中不一 致的数据。数据清洗可以在数据装入数据库之前或之后进行，常用的清洗方法有基于规 则的方法、可视化的方法及统计的方法。 数据选取：数据选取就是选择用于本次挖掘的数据列和行。例如数据库中的数据有 1 0 0 列和1 0 0 行，且其中只有1 0 列和1 0 行能用于某一决策。数据选择实际上是在两维 上进行的，其一是列或参数维的选择，其二是行或记录维的选择。 数据预处理：数据预处理就是对选择后的数据进行增强处理。这种增强处理可以根 据一个或多个字段产生新的数据项，还可以用一个信息量更大的字段去代替若干个字 段。应该说明的是，输入字段的数目不应该是提供给数据挖掘算法信息量的量度。因为 有些数据可能是冗余的，也就是说，有些属性只不过是相同事实的不同度量方式而已。 当数据挖掘的对象是数据仓库时，一般来说，数据预处理已经在生成数据仓库时完成了， 这时所要做的只是选择数据记录以及数据变换或表示即可。 数据表示：数据表示是将数据预处理后的数据转化成数据挖掘算法可以接受的形式 或者更适合的形式。这个过程通常采用编码的方式转换数据形式，最简单的方法就是建 立一个符号数据到数值数据或者数值数据到符号数据的一一对应的对照表。 3 模式提取( p a t t e r ne x t r a c t i o n ) 阶段模式提取阶段是整个知识发现过程中的核 心环节。在此阶段首先要明确数据挖掘的任务，如分类、聚类、关联规则或者序列模式 发现等。在确定任务之后，选择一个合适的数据挖掘算法或工具，并实施数据挖掘操作。 最后，结合挖掘任务选择一个合适的算法，也可以综合使用多种方法。 5 东北师范大学硕士学位论文 4 结果的解释与评估( i n t e r p r e t a t i o na n de v a l u a t i o n ) 阶段数据挖掘阶段产生的 模式，经过评估，可能存在冗余或无关的模式，这时需要将其剔除，也可能存在不满足 用户要求的模式，这时则需要返回到先前某个阶段重新执行，如重新选取数据、采用新 的数据转换方法、设定新的参数、甚至更换d m 算法等。发现的模式应该使用户容易理 解。其中包括对发现模式的进行多方面的检查，如有效性检验、一致性比较、是否满足 用户要求等，确认本次数据挖掘的效果。 有两个影响因素数据挖掘质量的好坏：首先应该采用有效性且可靠性的数据技术； 其次保证待挖掘数据的数量和质量。如果选择了错误的数据或不适当的属性，或对数据 进行了不适当的转换，则挖掘的结果会不理想。 数据挖掘过程是一个反复求精的过程。比如，用户在挖掘过程中发现选择的数据不 太好，或使用的挖掘技术产生不了理想的结果，这时，用户需要重复先前的过程，甚至 从头重新开始。 可视化在整个数据挖掘的各个阶段都发挥着重要的作用。用户可以使用散点图、直 方图等方法显示数据准备阶段有关数据，以期对数据有一个初步的把握，从而为更好地 选取数据打下孥实的基础。在挖掘阶段，用户则要使用与领域问题有关的可视化工具。 在表示结果阶段，也可以使用可视化技术发现知识。 2 3 数据挖掘的任务 数据挖掘的任务简单地说就是从数据集中发现隐含的、有用的模式。发现模式有两 大类畸1 ：描述型模式和预测型模式。描述型模式是对数据集中存在的事实做规范描述， 刻画数据的一般特性，预测型模式是根据模式的数据项的值确定或预测到某种未知的结 果。在实际应用中往往根据模式的实际作用又分为以下几种：分类、聚类、关联、序列 盘蟹 号字o 1 分类分析主要通过构造分类模型，把具有某些特征的数据项映射到某个给定的 类别。构造分类模型由两步完成：给定带有类别标号的样本数据，通过训练来建立分类 模型，并使用测试数据对模型进行准确性评价，其中样本数据都带有类别标号，也就是 说在分类之前，要划分的类别是已经确定的。 2 聚类分析将数据分成许多不同的类或簇，要求类之间的数据差异尽可能大，类 内的数据差异尽可能小。与分类分析不同，聚类分析法的输入集是一组未标定的记录， 也就是输入的记录不带有类别标号，聚类过程是无监督的学习过程。其目的是根据某种 规则，合理地划分记录集合，并用显式或隐式的方法描述不同的类型。而所依据的这些 规则是由聚类分析算法自己定义的。由于聚类分析可以采用不同的算法，所以对于相同 的记录集合可能有不同的划分。聚类有时直接满足用户的需求，有时是其它发现过程的 “预处理 。例如，由聚类所产生的类可以作为决策树生成算法的目标概念，也可作为 偏差分析的基础。 3 预测分析是从现有的数据中找出规律性并建立模型，再用此模型预测未知事例 6 东北师范大学硕士学位论文 的种类、特性等等。也可以说是根据t 。到t 。时刻发生的事件建立模型，并用此模型来预 测t 川时刻的解答。从实质看，它就是在对已知答案的训练集进行学习即建模的过程中， 对输入信息进行分类，建立输入到输出之间的隐含的对应关系。如输出是离散的，这个 模型便是分类模型；如果是连续的，则该模型是回归模型。 4 关联分析在事务数据库中挖掘关联规则是数据挖掘领域中的一个非常重要的研 究课题，如果两个或多个变项的取值之间存在某种规律性，那么称这种规律性为“关联”。 关联关系又可分为简单关联、时序关联和因果关联。简单关联无时间上的概念，仅强调 一种相关关系。例如，买面包的顾客中有9 0 的人同时买了牛奶。时序关联则不同，它 强调一种时间上的先后相关性。例如粮食涨价，副食品会相继涨价。因果关联则表示的 是条件与结论的依赖关系。挖掘关联规则的同时一般需要同时提供可信度和支持度参 考。 5 偏差分析是指通过分析数据，发现数据集中的异常或极端特例。偏差包括很多 有用的规则和知识，如分类中的反常实例、模式的例外、观察结果对模型预测的偏差量 随时间的变化等等。偏差检测的基本方法就是寻找观察结果与参照之间的差别。观察结 果常常是某一个域的值或多个域值的汇总。参照是给定模型的预测，外界提供的标准量 或另一个观察结果。偏差检测的数据模式有极值点、断点、拐点、零点和边界等不同的 偏差对象。 6 序列模式分是指从业务数据中的所有细节数据和事务的历史数据中找出经常发 生的规律或趋势，并对其建模。它与关联分析存在共同点，都是要找出数据之间的相互 联系，不同点在于序列分析更侧重于考察数据之间在时间维上的关联性，有个时间上的 概念。例如，将序列模式应用于分析客户潜在的购物模式，则可能分析出这样一种规则： 在购买电脑的顾客中，7 0 的人会在半年内购买内存条。 2 4 数据挖掘的常用算法 数据挖掘的方法陋可以分为两大类，一个是统计类型，采用的技术有概率分析、相 关性分析、聚类分析和判别分析等；另一个是人工智能中的机器学习类型，通过大量样 本集的学习训练得出需要的模式或参数。由于各种方法都有自身的功能特点以及适用领 域，数据挖掘技术的选择将影响最后结果的质量和效果，实际应用过程中通常是将多种 技术结合使用，形成优势互补。下面简单介绍一下数据挖掘应用中常用的几种算法和技 术引： 1 遗传算法遗传算法是一种全新的优化空间搜寻法，其最初概念是由j h o l l a n d 于1 9 7 5 年提出，是一种基于生物进化理论的技术，其基本观点是“适者生存”，在数据 挖掘中，常把任务表示成一种搜索问题，利用遗传算法强大的搜索能力找到最优解。具 体是模仿生物进化的过程，通过进行选择、交叉和变异遗传操作，直至满足最优解。遗 传算法己在优化计算和分类机器学习方面显示出了明显的优势。 2 决策树决策树主要是基于数据的属性值进行归纳分类，常用于分类的层次方法 7 东北师范大学硕士学位论文 有“i f - t h e n ”规则。决策树方法的最大优点就是可理解性强，比较直观。其缺点是处 理复杂性的数据时，分支数非常多，管理起来难度很大。同时，还存在数据的缺值处理 问题。其算法有i d 3 ，c 4 5 ，c a r t 等，目前出现的两种新算法s l i q 和s p r i n t 可以由非 常大的训练集进行决策树归纳，可以处理分类属性和连续性属性。 3 粗糙集该理论是波兰p a w l a k 教授在1 9 8 2 年提出的，它是一种新的数学工具。 这一方法在数据挖掘中具有重要的作用，常用于处理含糊性和不确定性的问题，发现不 准确数据或噪声数据内在的结构联系。也可以用于特征归约和相关分析。其主要优点就 是不需要任何关于数据的初始的或附加的信息，因此广泛应用于不确定、不完整的信息 分类和信息获取。 4 贝叶斯网络贝叶斯网络基于后验概率的贝叶斯定理，是建立在对数据进行统计 处理基础上的方法。将不确定事件通过网络连接起来，可以对与其他事件相关的事件的 结果进行预测，其网络变量可以是可见的，也可以隐藏在训练样本中。贝叶斯网络具有 分类、聚类、预测和因果关系分析的功能，其优点是易于理解，预测效果较好，缺点是 对发生频率很低的事件预测效果不好。在医学和制造业等领域的应用具有较好的效果。 5 统计分析统计分析的理论基础主要是统计学和概率论的原理，是一种较为精确 的数据挖掘技术。它是一种基于模型的方法，包括回归分析、因子分析和判别分析等， 该方法的优点是容易理解，对结果描述精确。统计分析在实际应用中较为广泛，著名的 统计产品供应商s p s s 公司开发了s p s s 和s y s t a t 统计软件包，同时，s a s 公司也开发出 相应的产品s a s 和j m p ，这些产品都占有一定的应用市场。 6 神经网络神经网络是最常用的数据挖掘技术之一，最早由心理学家和神经生物 学家提出的，旨在寻求开发和测试神经的计算模拟。它类似于人类大脑重复学习的方法， 先给出一系列的样本，进行学习和训练，从而产生区别各种样品之间的不同特征和模式。 样本集应该尽量体现代表性，为了精确地拟合各种样本数据，通过上百次，甚至上千次 的训练和学习，系统最后得出潜在的模式。当它遇到新的样本数据时，系统就会根据训 练结果自动进行预测和分类。最大的特点是难于理解，即无法解释如何得出结果和使用 了什么规则。它需要很长的训练时间，需要大量的参数，而且解释性较差。该算法的优 点是对复杂问题能进行很好的预测，对噪声数据的承受能力比较高，以及它对未经训练 的数据分类模式的能力。神经网络可细分为前馈式、反馈式和自组织神经网络，具有优 化计算、聚类和预测等功能，在商业界得到广泛的应用。金融市场采用神经网络建立信 用卡和货币交易模型，用于识别信贷客户、股票预测和证券市场分析等方面。 8 东北师范大学硕士学位论文 第3 章神经网络在可视化中的应用 3 1 数据可视化问题的由来 可视化遍及整个知识发现的全过程阴1 ，但主要集中在知识发现的前期和知识发现的 后期。由于所处理的是大型数据库，每个数据库中的数据经常是多维数据，因此必须对 数据进行处理。怎样根据目标任务选取相关数据，怎样进行数据维数的缩减，如何选取 数据中与目标变量相关的特征属性，在整个数据挖掘的过程中尤为重要，理解数据是做 好这些工作的前提。数据可视化无疑是一个较直观的方法。可视的一个重点是将多维空 间的数据在二维或三维空间内显示，并能理解各个特征属性的相关程度，有利于用户选 择相关的特征属性。通过数据可视化，可以初步对数据分类，并能对特征属性进行连续 属性离散化，这对于采用分类算法的数据挖掘过程是极其有意义的。 3 2 数据可视化的发展状况 由于目前处理的大多为多维数据库，怎样将多维数据库用二维或三维的情形表示出 来是要解决的核心问题。针对于此，产生了许多数据可视化的技术，大体分为散点矩阵 法、投影矩阵法、平行坐标法、面向象素的可视化技术、层次技术、动态技术、图标表 示技术及些几何学技术等等。目前已经有许多软件采用这些技术，例如i b m 的并行可 视系统，面向数据库的系统t r e e v i z 及面向可视的系统e x v i s 。根据数据挖掘及其所采 用的算法的特点，主要采用主成分分析法和因子分析法将多维变量表示为二维变量，依 据此算法对数据进行简单分类，并能了解各个特征属性之间的关系。 3 3 解决可视化问题的常用方法 数据可视化的基本手段是降维：在n 个属性中找出两个或三个用户关心的属性，然 后把多维空间投影n - 维或三维空间中。复杂的降维方法则是把多维空间投影到某些属 性的线形或布尔组合空间中，包括主成分分析、投影寻踪( p p ) 、自组织映射( s o m ) 神经 网络、主曲线和主曲面等。对于多变量数据集，可以采用主成分分析法、因子分析法、 散点矩阵法、投影矩阵法、平行坐标法、直方图法以及其他的几何影射技术进行可视化 数据，本文将采用非线性主成分提取与s o m 组合的方法。 3 3 1 主成分分析( p r i n c i p a lc o m p o n e n ta n a l y s i s ) 方法 主成分分析( p r i n c i p a lc o m p o n e n ta n a l y s i s ) 是研究如何将多指标问题转化为较 少的综合指标的一种方法扫1 ，即将高维空间的问题转化到低维空间去处理，实现维数的 9 东北师范大学硕士学位论文 降低以减低计算复杂度。而且这些综合指标之间互不相关，又能提供原有指标的绝大部 分信息。 主成分分析的基本原理： 假定有门个基因表达数据样本，每个样本共有p 个变量，构成一个甩p 阶的基因表达 数据矩阵，即 x = 人 而i ， a x 2 i ， m a x 叩 ( 3 1 ) 当p 较大时，在p 维空间中考察问题比较麻烦。为了克服这一困难，就需要进行降维处 理，即用较少的几个综合指标代替原来较多的变量指标，而且使这些较少的综合指标既 能尽量多地反映原来较多变量指标所反映的信息，同时它们之间又是彼此独立的。 定义：记五，恐，x 。为原变量指标，z 。，乞，z , m ( 优p ) 为新变量指标 f z 1 = 厶l 五+ 2 x 2 + 人+ p lz 2 = z 2 l 而+ 1 2 2 x 2 + 人+ 乞| 口讳 1 【z 掰= l r , , i x l + 乙2 x 2 + 人+ k 讳 ( 3 2 ) 系数乇的确定原则： ( 1 ) 乙与z ，( f ，；f ，j = - i ，2 ，m ) 相互无关； ( 2 ) 毛是_ ，x p 的一切线性组合中方差最大者，乞是与z , 1 不相关的一，屯， z 。的所有线性组合中方差最大者； 则新变量指标z 。，乞，气分别称为原变量指标x i ，恐，x 口的第1 ，第2 ， 第，1 个主成分。从以上的分析可以看出，主成分分析的实质就是确定原来变量( j 2 1 ， 2 ，p ) 在各主成分乙( i - = 1 ，2 ，m ) 上的载荷乇( i = 1 ，2 ，m ；j = 1 ，2 ， p ) 。 从统计模式识别的观点来看，主成分分析实际上是降维处理过程。它忽略了具有较 小方差的线性组成部分，保留具有较大方差的项，从而减小了有效数据表示的维数。在聚 类分析过程中，主成分分析( p c a ) 提取的主成分使聚类进程更快速更简单，但它是一种线 性算法，只能提取数据中的线性相关特性，同时聚类准确率方面有待于进一步提高。 1 0 东北师范大学硕士学位论文 3 3 2 非线性主成分分析( n o n l i n e a rp r i n c i p a lc o m p o n e n ta n a l y s i s ) 方法 对于高维数据，不但数据量庞大，而且都存在着不同程度的非线性关系。线性p c a 方法能够从中得到的有用信息十分有限。对于n l p c a ，它使原始数据到特征空间的映 射是非线性的，如下式所示。 t = f ( x ) + e ( 3 3 ) 其中f ( x ) 为非线性函数，t _ ，乞，l ，乙】为，维非线性主成分变量，e 为残差。 由于前馈神经网络有强大的拟合非线性函数的能力1 ，所以非线性函数f ( x ) 的确 定采用神经网络来学习，本文选取径向基( r b f ) 神经网络。对于上式，其输入为m 维原 始数据变量x ：中间层采用单隐层，称之为映射层，包括，个节点，且i j ：输出层则为， 个输出节点，即表示从原始数据空间映射到特征空间的，维主成分变量丁。 假设训练样本有个，其神经网络结构图如图3 - 1 所示。 - l 而 儿 l | 鞴 羼融含层猎出层 图3 - 1 提取非线性主成分的r b f 网络结构 神经网络的输入层有m 个神经元，其中任一神经元用m 表示；隐含层有，( ， x x o 。 ( 4 2 ) 一种常规的s 形函数如图4 1 ( b ) 所示，可由下式表示： 厂( x ) 2 百，o m ) 1 ( 4 3 ) 常用双曲正切函数( 如图4 一l ( c ) ) 来取代常规s 形函数，因为s 形函数的输出 均为正值，而双曲正切函数的输出值可为正或负。双曲正切函数如下式所示： m ) = 等，- l m ) 1 ( 4 4 ) f ( x )f ( x )f i x ) 确 ( a ) x l 1 ，_ 一 x jl 1 ，_ 一 ， r 1 ( b )( c ) 图4 - 1 神经元中的某些变换( 激发) 函数 x 4 2s o m 神经网络 自组织特征映射( s e l f - o r g a n i z i n gf e a t u r em a p ，也称k o h o n e n 映射) 神经网络( 简 称s o m 神经网络n 7 3 ) ，是由k o h o n e n 教授提出的对神经网络的数值模拟方法。这种方法是 人工神经网络的重要分支之一。自组织特征映射神经网络( s o m ) 模拟大脑神经系统的自 组织特征映射功能，是一种无监督竞争式学习的前馈网络，在训练中能无监督自组织学 习。它通过学习可以提取一组数据中的重要特征或某种内在规律，按离散时间方式进行 分类。网络可以把任意高维的输入映射到低维空间，并且使得输入数据内部的某些相似 性质表现为几何上邻近的特征映射。这样，就在输出层映射成一维或二维离散图形，并 保持其拓扑结构不变n 8 1 。这些特性表明s o m 网络非常适合用于聚类分析n 明和数据可视化 啪，特别是高维数据的分析。 s o m 网络结构乜h 2 如图4 - 2 所示，它由输入层和竞争层组成。输入层神经元数为n ， 竞争层由m = n 2 个神经元组成的二维平面阵列，输入层与竞争层各神经元之间实现全连 接。 1 6 东北9 币范大学硕士学位论文 层 x l 瓦 图4 2 二维阵列s o m 网络模型 s o m 神经网络的结构具有两个明显的特点：其一，拓扑映射结构不是通过神经元的运 动重新组织实现的，而是由各个神经元在不同兴奋状态下构成一个整体，所形成的拓扑 结构；其二，这种拓扑映射结构的形成具有自组织的特点。s o m 神经网络中神经元的拓 扑组织就是它最根本的特征。s o m 神经还具有按几何中心或特征进行聚类的独特性质。 4 2 1s o m 神经网络算法的训练过程 若输入为n 维向量x = ( x t ，x 2 ，x n ) ，建立一个有m 个输出节点的二维网络。第i 个输 入神经元节点与第j 个输出神经元节点之间的连接权值为w y 算法的训练过程如下： ( 1 ) 权值初始化 对所有的初始权值，w 选择 o ，1 之间的随机值。唯一的限制是：聊互不相同。 ( 2 ) 取样 以一定概率从样本输入空间里取刀维向量x ，表示应用于网格的激活模式。 ( 3 ) 计算时刻，的距离 计算输入向量在时刻，到所有输出节点的距离( 本文中采用e u c l i d e a n 距离定义) ： 西= ( 勋( f ) 一w ，( f ) ) 2 ( 4 5 ) i = 1 其中，勋( f ) 是输入向量在时刻f 的值。 ( 4 ) 选择获胜神经元f ( x ) 选择产生最小d j 的节点作为最匹配的神经元f ( 曲= n f m 西。神经元i 即为获胜神经元。 ( 5 ) 调整输出节点的连接权值向量 通过更新公式调整神经元的权值向量： w u ( t - ! - 1 ) = w o ( t ) + 7 7 0 ) 历，( j ) ( f ) ( x o ) 一w 驴( f ) ) ( 4 6 ) 其中，刀( f ) 是学习效率( 0 如 丸 0 与之对应的特征向量相互正交。 通过上述方法可求得k ( k p ) 个主成分。 屈= 坝纠 4 ， 在k 个主成分中，称前q 个主成分的贡献率之和为前q 个主成分的类级贡 东北师范大学硕士学位论文 口：圭以崖口= 以 f ；l，l - l ( 4 ) 求主成分载荷a ， a i = 瓜仅 ( 5 5 ) ( 5 6 ) 根据公式( 5 6 ) 计算主成分载荷矩阵x ，再计算各主成分得分 f = 口f xf = 1 , 2 ，k ，k( 5 7 ) ( 5 ) 主成分得分f 及贡献率的大小，计算综合得分 s = 届e + 及f 2 十人+ 尻最 ( 5 8 ) 主成分的贡献率和累计贡献率如表5 2 所示。可见，前七个特征值的累计贡献率已 达1 0 0 ，因此，可用这七个特征作为s o m 神经网络模型的输入变量。s o m 网络结构和网 络参数设置与a 类网络相同。经过聚类，将特性比较接近的样本聚到一个子类中，减少 了关联不大的样本在训练时的相互影响，提高了网络训练效率和聚类的正确率。b 类网 络可视化情况如图5 - 3 所示。 表5 - 3 特征值及主成分贡献率 主成分特征值贡献率累计贡献率 12 4 8 7 27 7 0 4 1 67 7 0 4 1 6 20 3 3 4 31 0 3 5 5 3 8 7 3 9 6 9 30 1 7 1 9 。 5