（计算机应用技术专业论文）改进聚类分析算法及其在成绩分析中的应用研究.pdf

摘要 摘要 数据挖掘被称为未来信息处理的骨干技术，它以一种全新的概念改变着人类利用数 据的方式。数据挖掘是指从大量的数据中提取有用的信息和知识的过程。这里要求数据 源应该是大量的、真实的、含有嗓音的，所发现的信息和知识是潜在的并隐藏在大量数 据背后的，是用户感兴趣的、可理解、可运用的知识。聚类分析是数据挖掘的一项基本 任务，聚类就是将数据对象分组成为多个类或簇，划分的原则是在同一个簇中的对象之 间具有较高的相似度，而不同簇中的对象差别较大o 本文的课题以省信息产业厅项嗣“嵌入式网上智能教学平台”为背景，主要通过对 数据挖掘技术的相关分析与比较，提出改进的聚类分析算法，并将此算法与教育统计学 相结合，从海量成绩数据中提取出隐藏于其中的有用信息。开发了嵌入式网上智能教学 平台的成绩分析系统，实现学生成绩分析和试卷质量评价报告的自动生成。 本文针对传统的基于遗传算法的k m e a n s 算法由于在遗传过程中易早熟，在算法后 期整个种群停滞不前而得不到全局最优解的问题。提出一种改进的基于遗传算法的聚类 分析算法。该算法用一种改进的基于模拟退火的自适应方法对适应度进行拉伸，然后动 态调整交叉概率与变异概率并用跨世代精英选择镱略进行选择，同时结合经典的 k i y l e a r l s 算法，使该算法可得到聚类划分效果极佳的聚类中心。 本文使用j a v a 语言进行了k - m e a n s 算法和传统的基于遗传算法的k - m e a n s 算法与 本文算法的对比实验，实验结果表明，本文算法有效地避免了k m e a n s 算法受初始聚类 中心选择的影响而容易陷入局部最优的可能，并消除了对孤立点数据的敏感性，同时也 克服了传统的基于遗传算法的k n l e a l 3 _ s 算法因过早收敛而陷入局部最优的缺点。理论分 析与实验表明，该算法的聚类划分效果明显优于k m e a n s 算法和其它传统的基于遗传算 法的k - m e a n s 算法。将改进的基于遗传算法的k m e a r t s 算法应用到试卷质量的成绩分析 中，并结合到网上教学当中去，从而发现嵌入式系统网上智能教学平台中试题的不足之 处，并进一步改善试卷的质量，取得令人满意的智能化教学效果。 关键词：数据挖掘；聚类；遗传算法；成绩分析；k n l e a l l s 算法 火连交通人学：r 学硕0 ：学何论文 a b s t r a c t t h ed a t am i n i n gi sc a l l e dt h eb a c k b o n et e c h n o l o g yo ft h ef u t u r ei n f o r m a t i o np r o c e s s i n g ， i tc h a n g e st h ew a yo ft h eh u m a nu s i n gd a t ab yb r a n d n e wc o n c e p t t h ed a t am i n i n gi sr e f e r s t ot h ep r o c e s so ff r o mt h el a r g ea m o u n t so fd a t at oe x t r a c tu s e f u l i n f o r m a t i o na n dk n o w l e d g e h e r er e q u e s t st h ed a t as o u r c e st ob eh u g e ，r e a l ，i n c l u d e st h en o i s e t h ei n f o r m a t i o na n dt h e k n o w l e d g ew h i c hi sd i s c o v e r e di sl a t e n ta n dh i d e sb e h i n dt h em a s sd a t a ，i su s e ri n t e r e s t i n g ， a p p r e h e n s i b l ea n de x e r c i s a b l ek n o w l e d g e c l u s t e ra n a l y s i si sab a s i ca s s i g n m e n to fd a t a m i n i n g ，c l u s t e r i n gi sg r o u p i n gt h ed a t ao b j e c ti n t om a n ys p e c i e so rt h ec l u s t e r ，d i v i s i o r y p r i n c i p l ei sb e t w e e nt h eo b j e c to f t h es a m ec l u s t e rh a st h eh i g hs i m i l a r i t y ，b u tt h eo b j e c to ft h e d i f f e r e n tc l u s t e rh a sb i gd i f f e r e n c e t h es u b je c to ft h et h e s i si s b a s e do nt h ep r o je c t e m b e d d e di n t e l l i g e n to n l i n et e a c h i n g p l a t f o r m “o fd e p a r t m e n to fi n f o r m a t i o ni n d u s t r yo fl i a o n i n gp r o v i n c e ，a f t e ra n a l y z i n ga n d c o m p a r i n gt h ed a t am i n i n gt e c h n o l o g yd e e p l y ，a ni m p r o v e dc l u s t e r i n ga p p r o a c ha l g o r i t h mi s p r e s e n t e d c o m b i n et h i sa l g o r i t h mw i t ht h ee d u c a t i o n a ls t a t i s t i c st oe x t r a c tu s e f u l i n f o r m a t i o n f r o mm a s sg r a d ed a t a id e v e l o pa n a l y s i so fa c h i e v e m e n ts y s t e mo fe m b e d d e di n t e l l i g e n t o n l i n et e a c h i n gp l a t f o r m ，w h i c hr e a l i z ea u t o m a t i cg e n e r a t i o no ft h es t u d e n ta c h i e v e m e n t a n a l y s i sa n dt h ee x a m i n a t i o np a p e rq u a l i t yr a t i n gr e p o r t t h et r a d i t i o n a lk m e a n sa l g o r i t h mb a s e do ng e n e t i ca l g o r i t h mc a n tg e tg l o b a l l yo p t i m a l v a 1 u e ，b e c a u s ei ti sp r e m a t u r eq u i c k l yi ng e n e t i cp r o c e s sa n da l lt h ep o p u l a t i o na r es t a l l i n gi n t h ee n do fa l g o r i t h m a ni m p r o v e dc l u s t e r i n ga p p r o a c hb a s e do ng e n e t i ca l g o r i t h mi s p r e s e n t e d t h i sa l g o r i t h ma p p l i e sa ni m p r o v e da d a p t i v eg e n e t i ca l g o r i t h mb a s e do ns i m u l a t e d a n n e a l i n ga l g o r i t h mm a k e st h ef i t n e s sp r o p e r l y ，a n dt h e na d a p t i v e l ya d j u s t sc r o s s o v e ra n d m u t a t i o np r o b a b i l i t ya n ds e l e c tw i t hc r o s sg e n e r a t i o n a le l i t i s ts e l e c t i o n ，a tt h es a m et i m eu s e t h ec l a s s i c a lk m e a n sa l g o r i t h m ，t h eo p t i m a lc l u s t e rc e n t e r sc a nb es e a r c h e db yt h i s a l g o r i t h m t h ep a p e ru s e sj a v al a n g u a g et oc a r r yo nt h ee x p e r i m e n tw h i c hc o m p a r e sw i t hk m e a n s a l g o r i t h ma n dt h et r a d i t i o n a lk m e a n sa l g o r i t h mb a s e do ng e n e t i ca l g o r i t h m ，e x p e r i m e n t a l r e s u l t sd e m o n s t r a t et h a tt h i sa l g o r i t h me f f e c t i v e l ya v o i d ee a s i l yf a l l i n gi n t ot h el o c a lo p t i m u m b e c a u s eo ft h ee f f e c to ft h es e l e c t i o no ft h ei n i t i a lc l u s t e rc e n t e r ，a n de l i m i n a t es e n s i t i v i t yt o t h ed a t ao fi s o l a t e dp o i n t a tt h es a m et i m eo v e r c o m ed i s a d v a n t a g eo ft h et r a d i t i o n a lk m e a n s a lg o r i t h mb a s e do ng e n e t i ca l g o r i t h mf a l l i n gi n t ot h el o c a lo p t i m u mb e c a u s eo fp r e m a t u r e c o n v e r g e n c e t h e o r e t i c a la n a l y s i sa n de x p e r i m e n ti n d i c a t et h a t ，t h i sa l g o r i t h mi sb e t t e rt h a n k m e a n sa l g o r i t h ma n dt h et r a d i t i o n a lk m e a n sa l g o r i t h mb a s e do ng e n e t i ca l g o r i t h m t h e i m p r o v e dk ，m e a n sc l u s t e r i n ga l g o r i t h mb a s e do ng e n e t i ca l g o r i t h ma p p l i e dt oa n a l y s i so f a c h i e v e m e n to fe x a m i n a t i o np a p e r s sq u a l i t y ，a n dc o m b i n i n go n l i n et e a c h i n g ，t h u sd i s c o v e r s i i 摘要 t h a tt h et e s tq u e s t i o nd e f i c i e n c yo fe m b e d d e di n t e l l i g e n to n l i n et e a c h i n gp l a t f o r m ，a c c o r d i n g l y f u r t h e ri m p r o v e st h eq u a l i t yo ft h ee x a m i n a t i o np a p e r s ，t h u sa c h i e v e st h es a t i s f y i n g i n t e l l e c t u a l i z e dt e a c h i n ge f f e c t k e yw o r d s - d a t am i n i n g ；c l u s t e r i n g ；g e n e t i ca l g o r i t h m ；k - m e a n sa l g o r i t h m ； a c h i e v e m e n ta n a l y s i s 大连交通大学学位论文独创性声明 本入声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢及参考 文献的地方外，论文中不包含他人或集体已经发表或撰写过的研究成 果，也不包含为获得太董銮通太堂或其他教育机构的学位或证书丙 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意。 本人完全意识到本声明的法律效力，申请学位论文与资料若有不 实之处，由本人承担一切相关责任。 学位论文作者签名： 莉自 日期：2 d 。暑 年f 。月叮日 大连交通大学学位论文版权使用授权书 本学位论文作者完全了解太蔓塞通太堂有关保护知识产权及保 留、使用学位论文的规定，即：研究生在校攻读学位期间论文工作的 知识产权单位属太董交通太堂，本人保证毕业离校后，发表或使用 论文工作成果时署名单位仍然为太查交通太堂。学校有权保留并向 国家有关部门或机构送交论文的复印件及其电子文档，允许论文被查 阅和借阅。 本人授权太蔓壅通太堂可以将学位论文的全部或部分内容编入 中国科学技术信息研究所( ( 中国学位论文全文数据库等相关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后应遵守此规定) 学位论文作者签名：司剑导师签名：荔卸 日期：2 0 0 8 年1d月2 5 日 日期：2 0 0 8 年1o 月2 5 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 电子信箱： 电话： 邮编： 绪论 绪论 一、课题的提出 随着计算机网络技术和现代化信息技术的不断发展，基于w e b 的远程教育正在逐 渐取代传统的教学方式，远程考试系统作为远程教育系统中不可缺少的一部分，也发挥 着越来越重要的作用。然而，目前的基于w e b 的远程教育系统大多以系统自身为中心， 缺乏学习者的个性化特征，同样远程考试系统也缺乏智能性，只能简单地对考生试卷成 绩和知识点方面的统计分析功能，不能很好地对大量的远程考试系统数据进行深入的挖 掘分析。 数据挖掘，也叫数据开采、数据采掘等，就是从大量的、不完全的、有噪声的、模 糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的但又是潜在有用 的信息和知识的过程f j 】。现存的信息系统的数据量非常大，而其中真正有价值的信息却 很少，因此从大量的数据中经过深层分析，获得有利于业务运作、提高竞争力的信息， 就像从矿石中淘金一样，数据挖掘也因此得名。这种新式的信息处理技术，可以按既定 业务目标，对大量的数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性， 并进一步将其模型化。它能深层次的分析信息背后未被人们所知的问题。该技术已被广 泛应用到经济效益巨大的金融、商业等领域。但是如果将数据挖掘应用到试卷成绩分析 中，那么就可以从现在海量的试卷和分数背后发现考试成绩中的一些问题，从而对试卷 的质量的研究无疑又多了一种好的方法，从而能进一步改善试卷的质量。将试卷质量分 析结合到网上教学当中去，会更有利于改善远程教育的质量。为此，提出了基于数据挖 掘的远程考试系统结构，利用数据挖掘对远程考试系统的数据库中的大量的用户考试结 果信息等数据进行挖掘，从中挖掘出对提高教学质量和教学效果有益的数据和结果进行 有效分析，从而有利于远程教育教学管理人员和教师掌握学生对知识的掌握情况，对教 学内容加以改进以及对教学平台进行优化等，全面提高教学质量。 本论文研究课题来源为省信息产业厅项目“嵌入式网上智能教学平台”，该项目建 立一套大型嵌入式系统网上智能教学平台，该平台为远程教育提供了一个智能化的网络 平台，能够实现网上教学、网上答疑、网上交流、网上测试等。该教学平台包括大量嵌 入式系统领域的网上教学课件、资料、案例等，通过网上教学方式实现对复合型、应用 型嵌入式人才的培养。同时深入研究数据挖掘的关联规则和聚类分析等高级技术、计算 智能、网络安全和专家系统在i n t e m e t 上的应用，提高该系统的智能性。 二、论文主要研究内容 大连交通人学- l ：学硕十学位论文 本课题研究的目的是针对数据挖掘技术在嵌入式网上智能教学平台应用的问题，通 过对问题的深入研究，提出了一种改进的基于遗传算法的k m e a n s 算法，并将这一算法 应用到网上智能教学平台，开发出网上智能教学平台的成绩分析系统。主要研究内容有： ( i ) 介绍数据挖掘的研究背景，并对数据挖掘技术与理论进行深入的研究。 ( 2 ) 研究聚类分析算法的概念及其应用情况，并详细研究了聚类算法的分类，以及 它们各自的特点。 ( 3 ) 针对传统的基于遗传算法的k m e a n s 算法的缺点，提出了一种改进的基于遗传 算法的k m e a n s 算法，并进行了实验，验证了该算法的聚类划分效果明显优于k m e a n s 算法和其它的传统的基于遗传算法的k m e a n s 算法。 ( 4 ) 将改进的基于遗传算法的k m e a n s 算法应用到网上智能教学平台，并开发设计 了网上智能教学平台的聚类成绩分析系统，用改进的基于遗传算法的k m e a n s 算法，通 过对网上智能教学平台上的各门课程的成绩进行聚类分析，可以得到网上智能教学平台 上的各门课程的试题质量，有利于网上智能教学平台的教学管理人员和教师及时掌握试 题的质量情况，对试题结构进行改进即对网上智能教学平台进行优化等，从而全面提高 教学质量。 2 第章数据挖掘技术 第一章数据挖掘技术 数据挖掘是2 0 世纪9 0 年代中期兴起的一项新技术，它是知识发现过程中的关键步 骤。国内外学术界和企业界，都非常重视对数据挖掘技术和软件工具的研究和开发。 数据挖掘是多门学科和多种技术相结合的产物，也是一个非常年轻而又活跃的研究 领域，它融合了数据库技术、人工智能、机器学习、统计学、知识工程、面向对象方法、 信息检索、高性能计算、及数据可视化等最新技术的研究成果 2 1 。经过十几年的研究， 产生了许多新概念和新方法。特别是最近几年，一些基本概念和方法趋于清晰，它的研 究正向着更深入的方向发展。 1 1 数据挖掘的概念 数据挖掘的产生有着它的应用背景。当全球向信息化社会迈进之际，人类利用信息 技术收集、加工、组织、生产信息的能力也大大提高，致使数以万计的各种类型的数据 库诞生，它们在科学研究、技术开发、生产管理、市场扩张、商业运营、政府办公等方 面发挥着巨大作用。然而，随着信息量的不断增多，特别是网络信息资源的迅猛扩张， 人类面临着新的挑战。如何不被堆积如山的信息所淹没? 如何能够迅速地从海量信息中 获取有用数据? 如何能够充分提高信息的利用率? 数据挖掘技术应运而生。 数据挖掘出现于2 0 世纪8 0 年代末，最早是以从数据库中知识发现( k d d ，k n o w l e d g e d i s c o v e r yi nd a t a b a s e ) 研究起步，k d d 一词首先出现在1 9 8 9 年人工智能国际会议上， 以后这一研究逐渐成为热点。由于这项研究对象的扩展，人们更多的称之为数据挖掘。 1 9 9 5 年，召开了第一届知识发现与数据挖掘国际会议，以后每年召开一届【3 】。 数据挖掘研究不仅来自于对“堆积如山 信息量的处理需求，更是由于社会发展各 方面的迫切需要而发展起来的【4 】。如企业为了提高自己的竞争力、开展良好的商业运作、 信息提供商对网络信息资源的组织等都需要研究数据挖掘技术。 数据挖掘是指从大量的数据( 结构化和非结构化) 中提取有用的信息和知识的过程 【5 1 。在这个定义中，要求数据源应该是大量的、真实的、含有噪音的；所发现的信息和 知识是潜在的并隐藏在大量数据背后的，是用户感兴趣的、可理解、可运用的知识。所 以，数据挖掘有时也被人们称为知识挖掘、知识提取、知识发现等。 数据挖掘也可视为是一类深层次的新型数据分析方法，它与传统的数据分析( 查询、 报表、联机应用分析) 的本质区别在于：数据挖掘是在没有明确假设的前提下去挖掘信 息、发现知识，所得到的信息通常是预先未知的、也是很难预料到的，甚至与人的直觉 大连交通大学工学硕士学位论文 是相违背的，但又是非常有用的；而传统的数据分析得到的信息则是浮在表面的、人的 直觉能够感受到的、或与人的直觉较为相近的。 从商业角度出发，数据挖掘可理解为一种商业信息处理技术，其主要目的是对大量 的商业数据进行抽取、转换、分析和其他模型化处理【6 1 ，从中提取辅助商业决策的关键 性数据。由于在商业运作过程中，无时不在产生数据，对企业来说，这种数据是大量的， 收集这些数据不再是单纯的以分析研究为目的，更主要的是通过对这些数据进行深入挖 掘，提供真正有价值的商业决策信息，从而获得更多利润。 数据挖掘的本质就是知识发现，但不要认为这里所指的知识发现是发现放之四海而 皆准的真理，也不是去发现新的物质或新的自然科学定理，更不是利用计算机证明某个 定理是否正确。实际上，它所有发现的知识都是隐藏在大量数据之中的关联信息，所有 的知识都是有特定前提和约束条件的，是面向特定领域的，而且，这些知识还要能够易 于被用户理解，能用自然语言表达所发现的结果。 1 2 数据挖掘的任务 数据挖掘任务有6 项：关联分析、时序模式、聚类、分类、偏差检测、预测【7 l 。 ( 1 ) 关联分析 关联分析是从数据库中发现知识的一类重要方法。若两个或多个数据项的取值之间 重复出现且概率很高时，就存在某种关联可以建立起这些数据项的关联规则。 在大型数据库中，这种关联规则是很多的，需要进行筛选。一般用“支持度”和“可 信度 两个阀值来淘汰那些无用的关联规则。“支持度 表示该规则所代表的事例( 元 组) 占全部事例( 元组) 的百分比。“可信度 表示该规则所代表事例占满足前提条件事例 的百分比。 ( 2 ) 时序模式 通过时间序列搜索出重复发生概率较高的模式。这里强调时间序列的影响。在时序 模式中，需要找出在某个最小时间内出现比率一直高于某一最小百分比( 阀值) 的规则。 这些规则会随着形式的变化做适当的调整。 时序模式中，个有重要影响的方法是“相似时序”。用“相似时序 的方法，要 按时间顺序查看时间事件数据库，从中找出另一个或多个相似的时序事件。 ( 3 ) 聚类 数据库中的数据可以划分为一系列有意义的子集，即类。在同一类别中，个体之间 的距离较小，而不同类别的个体之间的距离偏大。聚类增强了人们对客观现实的认识， 4 第章数据挖掘技术 即通过聚类建立宏观概念。聚类方法包括统计分析方法、机器学习方法和神经网络方法 在占 守o ( 4 ) 分类 分类是数据挖掘中应用得最多的任务。分类是找出一个类别的概念描述，它代表了 这类数据的整体信息，即该类的内涵描述。一般用规则或决策树模式表示。该模式能把 数据库中的元组映射到给定类别中的某一个。 类的内涵描述分为：特征描述和辨别性描述。 特征描述是对类中对象的共同特征的描述。辨别性描述是对两个或多个类之间的区 别的描述，特征描述允许不同类中具有共同特征。而辨别性描述中不同类不能有相同特 征。辨别性描述用得更多。 分类是利用训练样本集( 己知数据库元组和类别所组成的样本) 通过有关算法而求 得。建立分类决策树的方法，典型的i d 3 ，c 4 5 ，i b l e 等方法。建立分类规则的方法， 典型的有a q 方法、粗集方法、遗传分类器等。 ( 5 ) 偏差检测 数据库中的数据存在很多异常情况。从数据分析中发现这些异常情况也是很重要 的，应引起人们对它更多的注意。 偏差包括很多有用的知识 分类中的反常实例； 模式的例外； 观察结果对模型预测的偏差； 量值随时间的变化。 偏差检测的基本方法是寻找观察结果与参照之间的差别。观察常常是某一个域的值 或多个域值的汇总。参照是给定模型的预测、外界提供的标准或另一个观察。 ( 6 ) 预测 预测是利用历史数据找出变化规律，建立模型，并用此模型来预测未来数据的种类、 特征等。 典型的方法是回归分析，即利用大量的历史数据，以时间为变量建立线性或非线性 回归方程。预测时，只要输入任意的时间值，通过回归方程就可求出该时间的状态。近 年来，发展起来的神经网络方法，如b p 模型，实现了非线性样本的学习，能进行非线 性函数的判别。分类也能进行预测，但分类一般用于离散数值；回归预测用于连续数值； 神经网络方法预测既可以用于连续数值，也可以用于离散数值。 大连交通大学工学硕士学位论文 1 3 数据挖掘的过程 数据挖掘的过程可粗略的分为：问题定义、数据抽取、数据预处理、数据挖掘算法 执行，以及模式评估。 ( 1 ) 问题定义 在问题定义过程中，数据挖掘人员必须和领域专家以及最终用户紧密协作，一方面 了解相关领域的有关情况，熟悉背景知识，弄清用户要求确定挖掘的目标等要求；另 一方面通过对各种学习算法的对比进而确定可用的学习算法。后续的学习算法选择和数 据准备都是在此基础上进行的。 ( 2 ) 数据抽取 数据抽取的目的是选取相应的源数据库，并根据要求从数据库中提取相关的数据。 源数据库的选取以及从中抽取数据的原则和具体规则必须依据系统的任务来界定。 ( 3 ) 数据预处理 数据预处理主要对前一阶段抽取的数据进行再加工，检查数据的完整性及数据的一 致性。包括消除噪声、推导计算缺值数据、消除重复记录、完成数据类型转换等。当数 据挖掘的对象是数据仓库时，一般来说，数据预处理已经在生成数据仓库时完成了。 ( 4 ) 数据挖掘算法执行 运用选定的数据挖掘算法，从数据中提取出用户所需要的知识，这些知识可以用一 种特定的方式表示。选择数据挖掘算法有两个考虑因素：一是不同的数据有不同的特点， 因此需要用与之相关的算法来挖掘；二是用户或实际运行系统的要求。 ( 5 ) 模式评估 前一阶段发现出来的模式，经过评估，可能存在冗余或无关的模式，这时需要将其 剔除；也有可能模式不满足用户要求，这时则需要整个发现过程回退到前续阶段，如重 新选取数据、采用新的数据变换方法、设定新的参数值，甚至换种算法等等。 1 4 数据挖掘方法和技术 数据挖掘方法是由人工智能、机器学习的方法发展而来，结合传统的统计分析方法、 模糊数学方法以及科学计算可视化技术，以数据库为研究对象f 8 】，形成的数据挖掘的方 法和技术。 数据挖掘的方法和技术可以分为六大类。 ( 1 ) 归纳学习方法 归纳学习方法是目前重点研究的方向，研究成果较多。从采用的技术上看，分为两 大类：信息论方法( 这也是常说的决策树方法) 和集合论方法。 6 第一章数据挖掘技术 信息论方法：是利用信息论的原理建立决策树。由于该方法最后获得的知识表示形 式是决策树，故一般文献中称它为决策树方法。该类方法的实用效果好，影响较大。 集合论方法：是开展较早的方法。近年来，由于粗集理论的发展使集合论方法得到 了迅速的发展。这类方法中包括：覆盖正例排斥反例的方法( 典型的方法是a q 系列方 法) 、概念树方法和粗糙集( r o u g hs e t ) 方法。 ( 2 ) 仿生物技术 仿生物技术典型的方法是神经网络方法和遗传算法。这两类方法已经形成了独立的 研究体系。它们在数据挖掘中也发挥了巨大的作用，我们将它们归并为仿生物技术类。 神经网络方法：是模拟了人脑神经元结构，以m p 模型和h e b b 学习规则为基础的。 建立了三大类神经网络模型，包括前馈式网络、反馈式网络、自组织网络。神经网络的 知识体现在网络连结的权值上，是一个分布式矩阵结构。神经网络的学习体现在神经网 络权值的逐步计算上( 包括反复近代或者是累加计算) o 遗传算法：是模拟生物进化过程的算法，通过选择、交叉和变异操作，产生新的较 优良个体，经过若干代的遗传，最终得到满足条件的子代，即问题的解。 ( 3 ) 公式发现 在工程和科学数据库( 实验数据组成) 中对若干数据项( 变量) 进行一定的数学运算， 求得相应的数学公式。例如：物理定律发现系统、经验公式发现系统等。 ( 4 ) 统计分析方法 利用统计学原理对数据库中的数据进行分析，能得到各种不同的统计信息和知识， 它是- r - j 独立学科，也作为数据挖掘的一大类方法。 常用统计 相关分析 回归分析 差异分析 求大量数据中的最大值、最小值、总和和平均值等。 求相关系数来度量变量间的相关程度。 求回归方程( 线性或非线性) 来表示变量间的数量关系。 从样本统计量的值得出差异，来确定总体参数之间是否存在差异( 假设 检验) 。 聚类分析：直接比较样本中各样本之间的距离，将距离较近的归为类。而将距离 较远的分在不同类中。 判别分析：建立一个或多个判别函数，并确定一个判别标准。对未知对象利用判别 函数将它划归某个类别。 ( 5 ) 模糊数学方法 大连交通大学工学硕士学位论文 模糊性是客观的存在，当系统的复杂性愈高，其精确化能力便愈低，这就意味着模 糊性愈强。这是z a d e h 总结出的互克性原理。利用模糊集合理论进行数据挖掘的方法有： 模糊模式识别、模糊聚类、模糊分类和模糊关联规则等。 ( 6 ) 可视化技术 可视化技术是一种图形显示技术。例如，把数据库中多维数据变成多种图形，这对 于揭示数据中内在本质以及分布规律起到很强的作用。对数据挖掘过程可视化，并进行 人机交互可提高数据挖掘的效果。d a k e i m 把数据挖掘可视化定义为：数据挖掘可视化 是指寻找和分析数据库，以找到潜在的有用信息的过程。 1 5 数据挖掘的主要应用 下面主要从科学研究、商业应用以及w e b 挖掘这三个方面来总结数据挖掘的主要 应用，因为它们分别代表了各自不同的应用领域1 9 j 。 ( 1 ) 科学研究 下面从天文学和分子生物学的角度来介绍数据挖掘在科学上的应用。 数据挖掘在天文学上有一个非常著名的应用系统：s k i c a t 。它是加州理工学院喷 气推进实验室与天文科学家合作开发的用于帮助天文学家发现遥远的类星体的一个工 具。s k i c a t 的任务是构造星体分类器对星体进行分类，使用了决策树方法构造分类器， 结果使得能分辨的星体较以前的方法在亮度上要低一个数量级之多，而且新的方法比以 往方法的效率要高4 0 倍以上。 数据挖掘在生物学上的应用主要集中于分子生物学特别是基因工程的研究上。近几 年，通过用计算生物分子系列分析方法，尤其是基因数据库搜索技术己在基因研究上作 出了很多重大发现。数据挖掘在分子生物学上的工作可分为两种：一是从各种生物体的 d n a 序列中定位出具有某种功能的基因串；二是在基因数据库中搜索与某种具有高阶 结构( 不是简单的线性结构) 或功能的蛋白质相似的高阶结构序列。 陀) 商业应用 商业或企业上对数据挖掘的应用需求很大，商业应用领域有：市场营销、金融、银 行、制造和通信等。商业上的大多数应用针对的是分类预测任务【l 伊1 4 j 。 市场营销。数据挖掘在市场营销业上的应用可分为两类：数据库市场营销和货 篮分析。前者的任务是通过交互式查询、数据分割和模型预测等方法柬选择潜在的顾客 以便向它们推销产品，而不是像以前那样盲目地选择顾客推销；后者的任务是分析市场 销售数据( 如p o s 数据库) 以识别顾客的购买行为模式，从而帮助确定商店货架的布局排 放以促销某些商品。 8 第一章数据挖掘技术 金融投资。典型的金融分析领域有投资评估和股票交易市场预测，分析方法一 般采用模型预测法( 如神经网络或统计回归技术) 。这方面的系统有f i d e l i t ys t o c k s e l e c t o r 、l b sc a p i t a l 。前者的任务是使用神经网络模型选择投资，后者则使用了专家系 统、神经网络和遗传算法技术辅助管理多达6 亿美元的有价证券。 欺诈甄别。银行或商业上经常发生诈骗行为，如恶性透支等。这方面应用非常 成功的系统有：f a l c o n 系统和f a i s 系统。f a l c o n 系统是h n c 公司开发的信用卡 欺诈估测系统。它己被相当数量的零售银行用于探测可疑的信用卡交易，其数据格式只 有几种，因为流行的信用卡公司只有几家( 如v i s a 、m a s t e r 等) ，因此它的应用面很 大。f a i s 是一个用于识别与洗钱有关的金融交易的系统，它使用的是一般的政府数据 表单。 ( 3 ) w e b 挖掘 随着i n t e r n e t 的迅猛发展，今天它己成为各行各业的人们交流思想、获取信息的便 利手段。但随着这些信息缺乏机构化、组织的规整性，随意地散布在这个网络的各个角 落，这已成为这座世界性图书馆的一大缺憾。而今天的i n t e m e t 网的规模在急剧地扩大， 其上的信息量也在爆炸般地增长，这时入们若不有意识地去寻求弥补该缺憾的有效途 径，在不远的将来人们将迷途于信息的汪洋中。数据挖掘在i n t e m e t 上的应用包括三种： 在搜索引擎上对文档进行归类、帮助寻找用户感兴趣的新闻以及利用数据挖掘设计一个 电子新闻过滤系统。它利用文本学习建立起该用户的趣向模型，当用户进入一份电子报 纸的网页时，该系统就会根据学习所得的模型对其中的每一篇文章按与该用户的兴趣的 接近程度进行打分排序，使用户最先看到的是他最感兴趣的新闻。 经过多年来的研究和实践，数据挖掘技术已经吸引了许多学科的最新研究成果而形 成了独具特色的研究分支。但由于数据、数据挖掘任务和数据挖掘方法的多样性，给数据 挖掘和应用带来了许多具有挑战性的课题。这也正是数据挖掘今后的发展方向，主要包 括以下几个方面： 改进数据挖掘算法。 应用的探索。 数据挖掘语言的标准化。 可视化数据挖掘。 w e b 挖掘。 数据挖掘中的隐私保护与信息安全。 可伸缩的数据挖掘方法。 数据挖掘与数据库系统、数据仓库系统和w e b 数据库系统的集成。 9 大连交通人学丁学硕十学位论文 数据挖掘这个数据库研究、开发和应用最活跃的分支之一，它的内容是极其丰富和 具有挑战性的，引起了人们的广泛关注，对它的研究正在蓬勃发展。 本章小结 本章主要论述了数据挖掘技术的基本理论。介绍了数据挖掘的起源和定义，并且阐 述了数据挖掘的任务和过程。同时本章还介绍了当前的数据挖掘的方法与技术以及数据 挖掘的主要应用，并且还探_ 寸了数据挖掘将来的方向和发展趋势。 l o 第二章聚类分析的研究 第二章聚类分析的研究 2 1 聚类分析概述， 聚类是人类一项最基本的认识活动【1 5 】。聚类的用途是非常广泛的。在生物学中，聚 类可以辅助动、植物分类方面的研究，以及通过对基因数据的聚类，找出功能相似的基 因。在地理信息系统中，聚类可以找出具有相似用途的区域，辅助石油开采。在商业上， 聚类可以帮助市场分析人员对消费者的消费记录进行分析，从而概括出每一类消费者的 消费模式，实现消费群体的区分【1 6 1 。 聚类就是将数据对象分组成为多个类或簇，划分的原则是在同一个簇中的对象之间 具有较高的相似度，在不同簇中的对象差别较大。聚类操作中要划分的类事先未知的， 类的形成完全是数据驱动的，属于一种无指导的学习方法。 聚类分析的数学定义： 给定数据集合x 而i i - - - i ，2 ，n ) ，其中薯为数据对象，根据数据对象间的相似程度 将数据集合分成k 组，并满足： c ，b = 1 2 k c i 暑x er 、q = 囝 u ：。e = x ( 2 1 ) 则该过程称为聚类，e ( i = l ，2 ，k ) 称为簇f 1 7 1 。 聚类分析源于许多研究领域，包括数据挖掘、统计学、机器学习和模式识别等。它 是数据挖掘的一个功能，但也能作为一个独立的工具来获得数据分布的情况，概括出每 个簇的特点，或者集中注意力对特定的某些簇做进一步的分析。此外，聚类分析也可以 作为其他分析算法( 如关联规则和分类等) 的预处理步骤，这些算法在生成的簇上进行 处理。 2 2 聚类分析中的数据结构 聚类算法一般采用两种具有代表性的数据结构，一个是数据矩阵，一个是相异度矩 阵【1 引。 人们在考察一个实体集时，常常选用p 个属性来刻画该实体集。实体集中的每个成 员都可以用一组属性值来表示，这些属性值是有序的，可以记为一个向量。如果该实体 集中有n 个成员，那么，就可以用n 个含有p 个元素的向量来表示该实体集。这n 个向 大连交通大学工学硕士学位论文 量可以组成一个矩阵，即数据矩阵。数据矩阵如( 2 2 ) 所示，数据矩阵的每一行对应实体 集中的一个实体。 五l五p 葺t 。 而l ( 2 。2 ) 为了考察实体集中n 个成员的近似性，人们引入相异度矩阵进行度量。相异度矩阵 是一个n x n 的矩阵，如下所示： 0 d ( 2 ，1 ) a ( 3 ，1 ) d ( n ，1 ) d ( 1 ，2 ) o d ( 3 ，2 ) d ( n ，2 ) d ( 1 ，3 ) d o ，刀) d ( 2 ，3 ) d ( 2 ，胛) 0 a ( 3 ，刀) ： d ( 聆，3 ) 0 ( 2 。3 ) 其中d ( i j ) 是成员i 和成员j 之间相异性的量化表示，通常为非负数，d ( i j ) = 如，i ) ， d ( i ，i ) - - o 。成员i 和成员j 越相似，则d o , j ) 越接近于0 ，成员i 和成员j 的差异越大，则 d ( i j ) 越大。 因为数据矩阵的行和列含义不同，所以它经常被称为二模矩阵，而相异度矩阵的行 和列代表同一个实体，所以它经常被称为单模矩阵。许多聚类算法是以相异度矩阵为基 础的。如果数据是以数据矩阵的形式给出，可以将数据矩阵转化为相异度矩阵。 2 3 相似度的度量与准则函数 2 3 1 相似性的度量方法 一个聚类分析过程的质量取决于对度量标准的选择，因此必须仔细选择度量标准。 在通常的情况下，聚类算法是用特征空间中的距离作为度量标准来计算两个样本间的相 异度。相异度的度量用d ( x y ) 来表示，通常称相异度为距离。当x 和y 相似时，距离a ( x ，y ) 的取值很小，当x 和y 不相似时，d ( x ，y ) 就很大【1 9 2 。 按照距离公理，在定义距离测度时需要满足距离公理的四个条件：自相似性、最小 性、对称性以及三角不等性。这里仅介绍当数据对象的描述属性都是区间标度量属性时， 常用的距离测度有以下几种： ( 1 ) 明可夫斯基距离 1 2 第二章聚类分析的研究 下： 假定，x ，y 是相应的特征，n 是特征的维数。x 和y 的明可夫斯基距离度量的形式如 d ( w ) = l 卜乃i ，l lj = ij 当r 取不同的值时，上述距离度量公式演化为一些特殊的距离测度。 当r = l 时，明可夫斯基距离演变为绝对值距离 d ( x ，y ) = e i x , 一弘i 当r = 2 时，明可夫斯基距离演变为欧氏距离 d ( x ，少) ：| - 窆l 薯一”j z 2 li i lj ( 2 ) 二次型距离 二次型距离测度的形式如下： d ( x ，y ) = ( ( z y ) r 彳( x 一少) ) 1 ，2 其中，a 是非负定矩阵。 当a 取不同的值时，上述距离度量公式演化为一些特殊的距离测度。 当a 为单位矩阵时，二次型矩阵演变为欧氏距离。 当a 为对角阵时，二次型距离演变为加权欧氏距离 广h- 1 1 2 d ( w ) = i 卜咒1 2i li = l j 当a 为协方差矩阵时，二次型距离演变为马氏距离。 ( 3 ) 余弦距离 余弦距离的度量形式如下： d ( x ，y ) = 以 x i y | = l ( 2 4 ) ( 2 5 ) ( 2 6 ) ( 2 7 ) ( 2 8 ) ( 2 9 ) 2 3 2 聚类的准则函数 在样本相似性度量的基础上，还需要确定评价聚类划分结果质量的准则函数，才能 把真正属于同一类的样本聚合成一个类型的子集，而把不同类的样本分离开来。如果聚 1 3 大连交通大学工学硕士学位论文 类准则选得好，聚类质量就会高。同时，聚类准则函数还可以用来评价一种聚类结果的 质量，如果聚类质量不满足要求，就要反复执行聚类过程以便于优化聚类结