（计算机软件与理论专业论文）基于复杂网络的数据挖掘分类问题研究与应用.pdf

摘要：随着信息技术的快速发展，特别是计算机技术的不断普及，“数据丰富而信息贫 乏 这一矛盾显得日益突出，数据挖掘技术正是迎合了这一需求，同时结合数理统计、 人工智能、神经网络和信息技术等学科出现的一项新技术，并得到了迅速发展。数据挖 掘的主要目的是从数据集中发现隐含的、事先未知的和用户感兴趣的知识。作为一种 有效的数据分析技术，近年来分类( c l a s s i f i c a t i o n ) 已成为数据挖掘领域中的一项重要研 究内容，并广泛应用于商业、电子商务、基因工程和医学等诸多领域。 复杂网络作为一门新兴学科，在不同的领域( 如生态、人口、经济、社会、地理、 军事、医学) 中有着很强的应用背景，倍受广大学者的青睐和关注，已成为一个充满 生命力的交叉研究领域。一切事物都是相互作用的表现，大多可以通过复杂网络来表 现，如物理学研究物体间最基本的相互作用；化学研究分子间的相互作用；生物学研究 基因、蛋白质以及生物体之间的相互作用；社会科学研究人和各种人类组之间的相互 作用；分类问题研究数据点之间的相互作用。因此，事物作为系统，其结构可以抽象 为网络，各类作用体抽象为网络节点，各种相互作用抽象为节点之间的连接线或边。 基于这种思想，本文将数据集按照某种度量抽象成为复杂网络，结合复杂网络的理论、 成果和已有的某些分类、聚类方法对数据挖掘分类问题进行了相关研究，提高了对大 型数据库中的数据进行分类的能力，具有一定的研究价值。 复杂网络的社团探测与数据挖掘中分类、聚类问题在本质上是一样的，因而社团 探测的研究和分类问题的研究在某种角度上是一脉相承的。 本文在复杂网络的基础上，对分类问题做了以下三个方面的工作： 提出了一种基于k - m e a n s 聚类算法的复杂网络社团结构划分方法，丰富和发展了 复杂网络社团探测理论和方法。算法基于f o r t v n a t o - 等人提出的边的信息中心度，定义 了节点的关联度，并通过节点关联度矩阵来进行聚类中心的选择和节点聚类，从而将 复杂网络划分成k 个社团，然后通过模块度来确定网络理想的社团结构。该算法时间复 杂度为线性的，适合大型网络的社团发现。通过z a c h a r yk a g 8 t e 甜曲和c o e g e f o o t b a l ln e t w o r 炳个经典模型验证了该算法的可行性。 遗传算法作为一个成熟的理论，在分类方面有着很大优势，结合复杂网络的部分 新理论和遗传算法的思想，提出了一种新的分类方法。该方法将数据集按给定的相似 度公式构造出具有社团结构的网络，在此网络的基础上用遗传算法的思想进行分类。 算法引进社团模块度作为适应度函数，并且提出了节点归类错误率( n c m ) 对每次迭代产 生的解进行纠错，提高了分类质量和速度。实验证明该方法在分类精度和分类速度方 面都非常理想，并可实现并行性，将遗传算法的优点发挥到极致。 医学图像分类对实现智能化诊断系统有着重要的实际意义，是典型的分类挖掘问 题之一，同时也是一个热点的应用研究课题。为了建立高效的肿瘤自动诊断系统，克 服因医学m i r 图像的复杂性带来的直接从图像中看出肿瘤及良、恶性质的困难，结合 复杂网络的部分理论成果和k m e a n s 聚类算法的思想，提出了基于加权复杂网络聚类 的医学图像分类器。该分类器对医学图像进行预处理，建立图片特征库，构建图片加 权复杂网络，在此基础上根据网络节点的加权网络特征值和连接度选取初始聚类中心 进行聚类，有效地克服了传统k - m e a n s 聚类算法对初始化选值敏感性的问题，从而大 大提高了分类精度。通过对某医院p a c s 系统中的部分m i r 脑部图片进行分类，表明了 该方法的分类精度比传统的k - m e a n s 聚类算法平均提高了8 左右。 关键字：数据挖掘；分类；复杂网络；社团探测；遗传算法；医学图像分类器 a b s t r a c t ：w i t ht h er a p i dd e v e l o p m e n to ft h ei n f o r m a t i o nt e c h n o l o g y , e s p e c i a l l yi nt h e r e a l mo fc o m p u t e rs c i e n c e ，t h ec o n t r a d i c t i o n sb e t w e e nr i c hd a t aa n dp o o ri n f o r m a t i o na r e b e c o m i n gi n c r e a s i n g l ya c u t e t h e r e f o r e ，t h eu r g e n tr e q u i r e m e n t o f r e s o l v i n g t h e c o n t r a d i c t i o nc o n f r o n t su s an e wt e c h n o l o g yn a m e dd a t am i n i n ge m e r g e sa n ds h o r t l y b e c o m e sf l o u r i s h e di nt h i sb a c k g r o u n d i tc o m b i n e sw i t hm a t h e m a t i c a ls t a t i s t i c s ，a r t i f i c i a l i n t e l l i g e n c e ，n e u r a ln e t w o r ka n di n f o r m a t i o nt e c h n o l o g y t h em a i np u r p o s eo fd a t am i n i n g i st od i s c o v e rt h eu n k n o w n ，p o t e n t i a lk n o w l e d g e a sa ne f f e c t i v et e c h n o l o g yo fd a t aa n a l y s i s ， c l a s s i f i c a t i o nh a sb e e nc o n s i d e r e dap r o m i s i n gr e s e a r c hf i e l di nd a t am i n i n gd u et oi t s u n i q u es u p e r i o r i t ya n dh a sb e e nw i d e l yu s e di nc o m m e r c 宅，e l e c t r o n i cc o m m e r c e ，g e n e t i c e n g i n e e n n g ，m e d i c a ls e r v i c e sa n ds of o r t h c o m p l e xn e t w o r ki sab u r g e o n i n g ，p o p ，i n t e r d i s c i p l i n a r yr e s e a r c ha r e ai nr e c e n ty e a r s s o m es c h o l a r sf o c u so ni td u et oi t se x t e n s i v ea p p l i c a t i o n ，s u c ha se c o l o g y , d e m o g r a p h y , e c o n o m i c s ，s o c i o l o g y , g e o g r a p h y m i l i t a r ya f f a i r s ，m e d i c i n ea n ds oo n e v e r y t h i n gc a nb e t r a n s f o r m e di n t oac o m p l e xn e t w o r kb e c a u s ee v e r y t h i n gi sm a n i f e s t a t i o no fi n t e r a c t i o n ，s u c h a st h eb a s i ci n t e r a c t i o nb e t w e e no b j e c t si n p h y s i c s ，t h ei n t e r a c t i o na m o n gm o l e c u l e si n c h e m i s t r y , t h er e s e a r c ho fg e n ea n dp r o t e i n ，t h ei n t e r a c t i o na m o n go r g a n i s m si nb i o l o g y , t h e i n t e r a c t i o na m o n gh u m a n o r g a n i z a t i o n si ns o c i o l o g y , t h ei n t e r a c t i o nb e t w e e nd a t ap o i n ti n c l a s s i f i c a t i o n t h e r e f o r e ，t h es t r u c t u r eo fa no b j e c tc o n s i d e r e da ss y s t e mc a nb eg i v e na n a b s t r a c to fan e t w o r k ，c o n s t i t u e n t so ft h es t r u c t u r ec a nb ev i e w e da st h en e t w o r kn o d eb y a b s t r a c t i o na n dt h en e t w o r k se d g er e p r e s e n t st h ei n t e r a c t i o n b a s e do na b o v ev i e w p o i n t s ， t h i sp a p e rt r a n s f o r m sc l a s s i f i c a t i o nd a t a s e ti n t oc o m p l e xn e t w o r ka c c o r d i n gt os p e c i f i c m e a s u r ea n da p p l i e sr e l a t e dt h e o r e t i c a la n dr e s e a r c hf r u i t si n t oc o m p l e xn e t w o r ki n c l a s s i f i c a t i o n t h er e s u l to fe x p e r i m e n t ss h o wt h a to u rv a l u a b l em e t h o dc a ni m p r o v et h e c l a s s i f i c a t i o ne f f e c ti nl a r g ed a t a b a s ea n dc a nb ed e p l o y e di nm a n i f o l da p p l i c a t i o nf i e l d s c o m p l e xc o m m u n i t yd e t e c t i n ga l g o r i t h mi si n t e r l i n k e dw i t hc l a s s i f i c a t i o na n dc l u s t e r i n g o ft h ed a t am i n i n g ，b e c a u s et h e ya r es a m ei ne s s e n c e t h em a i nr e s e a r c hw o r k so nc l a s s i f i c a t i o nb a s e do nc o m p l e xn e t w o r k sa r ea sf o l l o w s ： an e wd e t e c t i n gm e t h o db a s e do nk - m e a n sc l u s t e ra l g o r i t h mw a sp r o p o s e d t h r o u g ht h e d e f i n i t i o no fn o d el i i l l 【b a s e do ni n f o r m a t i o nc e n t r a l i t yw h i c hf o r t u n a t ow a sp r o p o s e da n d t h es e l e c t i o no ft h ec l u s t e r i n gc e n t e ra n dt h ec l u s t e r i n go ft h en o d ea c c o r d i n gn o d el i n k ，t h e a p p r o a c hi d e n t i f yt h en e t w o r kt okc o m m u n i t i e s ，t h e ni d e n t i f yt h ei d e a l l yc o m m u n i t y s t r u c t u r ea c c o r d i n gm o d u l a r i t y t h ea l g o r i t h mc a nf i n dc l u s t e r i n gc e n t e rb e t t e ra n di ti s r o b u s tt oi n i t i a l i z a t i o n ，s ot h eq u a l i t yo fd e t e c t i n gi si m p r o v e dg r e a t l y t h ea l g o r i t h mi s t e s t e do nt h et w on e t w o r kd a t an a m e dz a c h a r yk a r a t ec l u ba n dc o l l e g ef o o t b a l l g e n e t i ca l g o r i t h ma sam a t u r et h e o r yh a sm a n ya d v a n t a g e so nc l a s s i f i c a t i o n an e w c l a s s i f i e dm e t h o di sp r o p o s e dw h i c hb a s e do ns o m en e wt h e o r yr e s u l t sa c h i e v e di nt h ef i e l d o fc o m p l e xn e t w o r ka n dt h ei d e ao fg e n e t i ca l g o r i t h m t h em e t h o dc o n v e r t sd a t as e t si n t oa c o m m u n i t yn e t w o r ka c c o r d i n gt ot h es i m i l a r i t yf o r m u l af i r s t l y , t h e nu s e sg e n e t i ca l g o r i t h m t oc l a s s i f yt h en e t w o r k t h em e t h o du s e sc o m m u n i t ym o d u l a r i t ya st h ef i t n e s sf o r m u l a ，a n d p r o p o s e dm i s t a k er a t eo f n o d ec l a s s i f i c a t i o n ( n c m ) t oc l e a nu pt h es o l u t i o na f t e ri t e r a t i o n s t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h i sa l g o r i t h mi sb e t t e ri na c c u r a c ya n dt i m e m e d i c a li m a g ec l a s s i f i c a t i o nh a si m p o r t a n tp r a c t i c a ls i g n i f i c a n c ef o rt h er e a l i z a t i o no f i n t e l l i g e n td i a g n o s i ss y s t e m i ti sat y p i c a lc l a s s i f i c a t i o no fd a t am i n i n ga n da h o tr e s e a r c h t o p i co fa p p l i c a t i o n d e t e c t i n gt u m o ri nm e d i c a lm i ri m a g e si sad i f f i c u l tt a s kb e c a u s eo f c o m p l e x i t yi n t h ei m a g e t h i sb r i n g st h en e c e s s i t yo fc r e a t i n ga u t o m a t i ct o o l st of i n d w h e t h e rai m a g ep r e s e n tt u m o ro rn o t n i sp r o p o s e dm e d i c a li m a g ec l a s s i f yb a s e do n w e i g h t e dc o m p l e xn e t w o r kd u s t e ra f t e ra n a l y z i n ga d v a n t a g e sa n dd i s a d v a n t a g e so ft h e t r a d i t i o n a lk - m e a n sc l u s t e r i n ga l g o r i t h ma n dt h en e wt h e o r yr e s u l t sa c h i e v e di nt h ef i e l do f c o m p l e xn e t w o r k s t h ee x p e r i m e n t a lr e s u l t s c e n t e r sb e t t e rb a s e do nt h ew e i g h t e dc o m p l e x i n i t i a l i z a t i o n ，s ot h eq u a l i t yo fc l u s t e r i n gi s c l u s t e r i n ga l g o r i t h m s h o wt h a t t h i sc l a s s i f yc a nf i n dc l u s t e r i n g n e t w o r k sf e a t u r eo fn o d e sa n di ti sr o b u s tt o i m p r o v e d8 t h a nt h et r a d i t i o n a lk - m e a n s k e y w o r d s ：d a t am i n i n g ；c l a s s i f i c a t i o n ：c o m p i e xn e t w o r k ；c o m m u n i t yd e t e c t i n g ； g e n e t i ca i g o r i t h m ；m e d i c a ii m a g ec i a s s i f i c a t i o n 基于复杂网络的数据挖掘分类问题研究与应用 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除 特别加以标注和致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果， 其他同志的研究成果对本人的启示和所提供的帮助，均已在论文中做了明确的声明并 表示谢意。 学位论文作者签名：赵丛霞 赵匡l ! 覆 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校 有权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文 授权辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内 容和纸质论文的内容相一致。 保密的学位论文在解密后使用本授权书。 学位论文作者签名：嫠旦盾。赵婚指导教师签名：靠 签名日期：2 0 0 9 年5月1 9 日 5 7 基于复杂网络的数据挖掘分类问题研究与应用 1 绪论 1 1 研究背景及意义 2 0 世纪9 0 年代以来，随着信息技术和数据库技术的迅猛发展及互联网的普及， 各行各业产生和收集数据的能力迅速提高，在这大量的数据背后隐藏着许多重要的信 息。面对大规模的海量数据，人们对数据处理技术的要求也不断提高，需要对数据进 行更深层次处理，从中找出规律和模式，以得到关于数据的总体特征，对未来的发展 趋势进行预测。而传统的数据分析工具( 如管理信息系统) 只能进行一些表层的处理 ( 如查询、统计等) ，而不能获得数据之间的内在的关系和隐含的信息。因此，迫切地 要求自动和智能地将待处理的数据转化为有用的信息和知识。正是由于实际工作的需 要及机器学习等相关技术的发展，数据挖掘技术应运而生，并得以蓬勃发展，越来越 显示出其强大的生命力n 棚。 数据挖掘是从数据集合中抽取隐藏在数据中的那些有用的信息。这些信息的表现 形式为：规则、概念、规律及模式等。它可以帮助决策者分析历史数据及当前数据， 并从中发现隐藏的关系和模式，进而预测未来可能发生的行为。数据挖掘是瓦d d 中的 重要技术，与传统的数据库查询技术存在显著的不同，它并不是用规范的数据库查询 语言( 如5 弛) 进行查询，而是对查询的内容进行模式的总结和内在规律的搜索。数据 挖掘一般有数据总结、分类和预测、聚类、关联分析和决策分析等几类主要任务。其 中分类( c l a s s i f i c a t i o n ) 是一种重要的数据分析技术，它可以用于提取描述重要数据类 的模型，可以预测未来的数据趋势h ，。数据挖掘分类算法的工作方法是通过分析已知 分类信息的历史数据总结出一个预测模型。分类问题在人工智能、机器学习以及模式 识别等领域已经得到了广泛的研究，并己产生了许多的分类方法。但是，传统的分类 算法在可扩展性、高效率性和对大规模的海量的数据分类等方面还面临大量的问题。 因此，近年来分类问题己成为数据挖掘领域的一项重要研究内容，获得了更加广泛的、 深入的研究。 复杂网络自2 0 世纪末逐渐兴起以来，其思想已经充斥到科学和社会的每一个角落 睁7 1 。由于其有着广泛的应用背景，复杂网络已经成为国际上一个十分引人注目的新 兴研究领域。目前，复杂网络研究的主要问题是：网络拓扑特性与模型、复杂网络上 的传播行为、相继故障、搜索算法和社团结构以及复杂网络的同步与控制等。其中复 杂网络中社团结构具有社团内节点之间的连接非常紧密，而社团间的连接却相对比较 稀疏的性质。这与数据挖掘中分类、聚类问题本质是相同的，即同一类的对象相互之 间的相似度大，而不同类中的对象是相似度小。类内的相似性越大，类间差别越大， 分类就越好。因此复杂网络社团探测算法的研究和我们对分类问题的研究是密切相关 基于复杂网络的数据挖掘分类问题研究与应用 的，可以相互借鉴。 一切事物都是相互作用的表现，都可以通过复杂网络来表现。物理学研究物体间 最基本的相互作用，化学研究分子间的相互作用，生物学研究基因、蛋白质以及生物 体之间的相互作用，社会科学研究人和各种人类组之间的相互作用，分类问题研究数 据点之间的相互作用。因此，事物作为系统，其结构可以抽象为网络，各类作用体抽 象为网络节点，各种相互关系抽象为节点之间的连接线或边。基于这种思想，本文将 分类数据按照某种度量抽象成为复杂网络，并把复杂网络的理论和成果应用于数据挖 掘分类问题的研究，提高了对大型数据库中的数据进行分类的能力，具有广泛的应用 前景和实用价值。 现实中的很多问题都可以转化为分类问题，因而数据挖掘分类技术的潜在应用十 分广泛，政府管理决策、商业经营、科学研究、工业企业决策支持和智能医学诊断系 统等各个领域都应用了分类技术。例如，可以建立一个分类模型，对银行的贷款客户 进行分类，以降低贷款的风险：也可以通过建立分类模型，对已有的病例进行分析，来 预测病人可能出现的疾病；还可以通过建立分类模型对医学图像分类，来预测肿瘤的 良恶性来以辅助医生诊断，这是本文研究的任务之一。 1 2 研究现状 本文是在复杂网络的基础上研究数据挖掘分类算法和应用的。课题研究涉及到的 领域知识包括数据挖掘、复杂网络和医学图像挖掘。下面从这三个方面介绍一下本课 题的研究现状。 1 2 1 数据挖掘的研究现状 数据挖掘( d a t am i n i n g ，简称d m ) ，简单地讲就是从大量数据中挖掘或抽取出知 识。数据挖掘，又称为数据库中知识发现( k n o w l e d g ed i s c o v e r yf r o md a t a b a s e ，简称 k d d ) ，它是一个从大量数据中抽取挖掘未知的、有价值的模式或规律等知识的复杂 过程。整个知识挖掘( k d d ) 过程是由若干挖掘步骤组成，而数据挖掘仅是其中的一 个主要步骤。整个知识挖掘的主要步骤有：数据清洗、数据集成、数据转换、数据挖 掘、数据评估和知识表示。尽管数据挖掘仅仅是整个知识挖掘过程中的一个重要步骤， 但由于目前工业界、媒体、数据库研究领域中，“数据挖掘 一词已被广泛使用并被 普遍接受，因此我们也可不对他门进行严格的区分，而把他们看成同义词。我们通过 数据挖掘的进化过程( 如图1 1 所示) 和k d d 的研究现状来了解数据挖掘的研究现状。 1 9 8 9 年8 月举行的第十一届国际联合人工智能会议上首次出现了k d d 一词，随着k d d 在学 术界和工业界影响力的扩大，国际k d d 组委会将专题讨论会更名为国际会议，并且规定 每年召开一次。1 9 9 7 年亚太地区在新加坡召开了第一次大规模的d m 学术研讨会，以后 2 基于复杂网络的数据挖掘分类问题研究与应用 每年召开一次。此外，诸多领域( 如数据库、人工智能、信息处理、知识工程等) 的 国际学术刊物纷纷开辟了k d d 专题或专刊。喇k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊领先在1 9 9 3 年出版了蹴术专刊；i n t e r n e t j z 还有不少砒子出版物，其中以 半月刊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 ：删v k d n u g g e t s c 鲫还可以 下载各种各样的数据挖掘工具软件和典型的样本数据仓库，供人们测试和评价。 国外，数据挖掘的研究方面主要集中在进一步对知识发现方法的研究和数据挖掘 可开发应用方面( 如k d d 商业工具的开发：比较典型的d m 软件如s a s 公司的e n t e r p r i s e m i n e r 、i b m 公司的i n t e l l i g e n tm i n e r 、s g i 公司的s e t m i n e r 、s p s s 公司的c l e m e n t i n e ，还 有k n o w l e d g ed i s c o v e r yw o r k b e n c h 、d bm i n e r 、q u e s t 等。) 。 国内，对肋d 的研究稍晚，目前进行的大多数研究项目是由政府资助进行的，如 国家自然科学基金、8 6 3 计划、“九五 计划等。研究人员主要集中在大学，也有部分 在研究所或公司。研究领域集中于学习算法的研究、数据挖掘的实际应用以及理论方 面的研究。但是到目前为止，国内还没有比较成熟的数据挖掘产品。 数据挖掘时一个年轻而又非常活跃的研究领域，目前面临的问题，除了基础理论 和技术方面的外，更重要的是开发和应用。 3 基于复杂网络的数据挖掘分类问题研究与应用 数据挖掘中经常遇到的技术难题有：超量数据，数据库中数据量的迅速增长， 是促进数据挖掘技术发展的原因之一，也是数据挖掘技术首先要解决的问题。以往的 大多数机器学习算法都是针对少量( 如几百个) 样本数据开发的，因而不能用于比它 大几千倍的数据库。现在的许多数据挖掘技术的时间复杂度和模式复杂度对数据量的 大小非常敏感。可能的解决方法是尽可能降低算法的复杂度，后者使用数据会及方法 限制搜索空间，以及使用比较快的家算计等；噪声数据，通常把数据输入或惠及过 程中发生的非系统误差成为噪声。它有两种形式：第一种是腐烂的属性值。训练样本 的某些值相对于它们应有的值发生了变化，从而使数据模糊不清，这可能与已经建立 的规则相冲突。腐烂值还可以能改变已经识别到的正确模式。第二种是一楼的属性值。 相对于训练样本或待识别的对象，可能遗漏一个或几个属性值，从而使数据不完整。 如果属性只是在训练中遗漏的，则系统可能从总体上把这个对象忽略掉，或者作为“未 知对象处理，从而影响规则的准确性。如果一个属性值仅仅在被分类的某个对象上 遗漏掉，则系统可能要检查所有匹配规则，并计算最可能的分类，从而降低了响应速 度；控值，由于数据不可利用或人类本身的只是不完整，导致数据库中个别或某些 记录的属性域出现空值现象，或者对于一发现任务来说，不存在其必须的数据记录。 空值不仅仅表示一个未知的值，还说明该指属性值是不可利用的。空值现象尤其在关 系数据库中经常发生。这种现象给发现、评估和解释模式带来了困难。这时，知识发 模型应当具有近似决策能力，方法主要有模糊集合论和粗糙集理论等；冗余数据， 与不完整数据相反，给定的数据集中可能含有冗余的或不重要的属性，从而增加时间空 间开销和结果规则的复杂度。解决这个问题的方法主要是属性约简；动态数据，数据 库的基本特点是，库中得分内容是动态改变的，它对于发现方法的影响主要表现在： 首先，如果发现是作为数据可应用的，那么，要求发现方法高效率，并能充分利用d b m s 的检索功能。其次，对于动态变化数据，只是发现方法应当具有增量式( 或渐进式) 学 习的能力。 数据挖掘今后可能的研究方向是：a 加强应用研究：针对不同数据挖掘任务的专用 数据挖掘系统。不同的应用领域可能使用多种类型数据和数据库，知识发现系统应当 能够对不同类型的数据和数据库进行有效的数据挖掘。虽然大多数数据库是关系型的， 但许多实际应用的关系数据库还可能含有复杂的数据类型，如结构数据和复杂数据对 象、超文本和多媒体数据、空间和事态数据、事务数据以及历史数据等，因此一个多 功能很强的数据挖掘系统应能对各种复杂数据类型进行挖掘。鉴于数据类型的差异和 不同的数据是不现实的，应当更具特定类型数据的挖掘任务结构专用的数据挖掘系统， 如系统数据库挖掘等。b 高效率挖掘数据算法：未能从大量数据( 特定是大型数据) 中 有效的抽取信息，数据挖掘算法必须是高效的，即算法的运行时间必须是可测的和可 接受的，带有指数甚至中阶多项式的算法，没有实际使用价值。他搞数据挖掘结果的有 4 基于复杂网络的数据挖掘分类问题研究与应用 效性、确定性和可表达性。已发现的只是应能准确的描述数据库中的内容，并能用于 实际领域。对有缺陷的数据应当根据不确定性的度量，以近似规则或定量规则形式表 达出来。数据挖掘系统还应该能很好地处理和抑制噪声数据和不希望的数据。所以要 研究度量知识质量的方法，包括模型和工具的实用性和可靠性。c 数据挖掘结果的可 视化：数据挖掘的最后阶段是分析发现的知识，有多种不同的分析观点和表示形式， 要求用高级语言( 最好是自然语言) 或图形界面表示数据挖掘需求和已发现的知识， 并采用适合的只是表示技术。这样，数据挖掘人物就可由非领域专家指定，也便于用 户理解和直接应用及发现的知识。d 多源数据挖掘：计算机网络( 包括局域网和广域网， 特别是i n t e r n e t ) 把许多数据连接在一起，形成巨大的分布示异结构数据库。不同来 源数据的格式和语义可能不统一，数据挖掘系统应当能够帮助用户揭示异结构数据库 中的高级数据规律。数据库规模的扩大，数据费弥补的广泛性，以及分布式数据挖掘 的复杂性，促进了并行和分布式数据挖掘算法的研究。在分布式数据挖掘研究方面， 今后应特别重视把数据挖掘机属与i n t e r n e t 技术及w e b 技术紧密结合起来，开发出基于 i n t e r n e t 和w e b 得数据挖掘软件工具。同时，加强对分布式软代理( a g e n t ) 技术的研 究和应用。e 数据挖掘的安全性和保密性：当从不同角度和不同抽象层次观察数据的时 候，就要考虑数据的安全性，防止侵犯别人隐私和泄露敏感信息。实现与西安与数据 库系统或者数据库的无缝集成，进一步扩大数据挖掘工具的范围和提高现有数据的利 用率。 分类盥9 1 是数据挖掘中一项非常重要的任务，目前在商业上应用最多。分类的目的 是提出一个分类函数或分类模型( 即分类器) ，通过分类器将数据对象映射到一个给定 的类别中。现阶段分类模式中比较常用的方法有k 一最近邻分类方法n 、遗传算法n 扣、 决策树方法n3 。、贝叶斯方法n 制、粗糙集方法n 副、神经网络方法n 6 3 和支持向量机方法n 刀。 目前国内外学者对数据挖掘分类问题的研究焦点可以集中在以下几个方面： 1 ) 扩展和改进现有的分类方法；2 ) 多种分类方法融合的应用；3 ) 不确定性方法 的分析和构造；4 ) 对数据中噪声、空缺等实际问题的处理；5 ) 数据挖掘分类过程中 各个步骤的紧密结合。 1 2 2 复杂网络的国内外研究现状 传统的对网络的研究最早起源于著名的欧拉七桥问题。对网络最早进行研究的是 数学家，其基本理论是图论。之后的近两百年中，数学家们一直致力于简单的规则网 络和随机网络进行抽象的数学研究。直到最近十多年，由于计算机数据处理和计算机 能力的飞速发展，科学家们发现大量的真实网络即不是规则网络，也不是随机网络， 而是具有与这两种网络不同的统计特征的网络。这种网络被科学家们称作复杂网络， 其诸多统计特征中最重要的是小世界效应和无标度特性。 5 基于复杂网络的数据挖掘分类问题研究与应用 复杂网络陆1 是1 9 9 8 年以来出现的新的复杂性系统研究热点，它描述了广泛多样的 高科技和智能重要性的系统。复杂网络研究正渗透到数理科学、生命科学、社会科学、 政治科学、医药科学和经济科学等众多不同领域。自然界与社会生活众多的问题都可 用复杂网络来描述( 如蛋白质的相互作用、演员之间的合作演出关系、科研文章之间 的引用关系和w w 中网页之间的超连接) 。这些真实网络的普遍存在，促使来自不同 学科领域的科学家共同致力于复杂网络的研究。复杂网络的研究不仅具有学术意义， 而且具有更重大的实际意义。复杂网络的研究可以更好的使人们了解现实世界的复杂 系统，为设计具有良好性能的网络提供理论依据。同时，复杂网络的理论结果将会广 泛的应用到生物、计算机等各个学科领域。 目前，复杂网络的研究工作主要集中在以下几个方面： 1 复杂网络拓扑结构的静态统计分析，包括更广泛的实证研究和更深入的理论刻 画，如给定度分布基础上的匹配模式、各种相关关系、加权网络的统计性质和描述方 式以及网络的聚类等； 2 复杂网络的生成机制和演化模型，即通过生成机制建立模型，模拟真实网络行 为； 3 复杂网络上的动力学研究，包括网络容错性和攻击鲁棒性，以及网络上的传播、 同步与共振等各种动力学过程； 4 复杂网络的社团结构，许多实际网络都具有一个共同的性质，即社团结构。揭 示网络中的社团结构，对于了解网络结构和分析网络特性具有极为重要的意义。 1 2 3 医学图像数据挖掘国内外研究现状 近年来，围绕医学图像的数据挖掘技术，美国、日本、加拿大等国家已经开展了 广泛而深入的研究，并已取得了一定的进展n8 1 。如美国爱荷华州立大学的a k u s i a k 等人提取了5 0 个肺癌病人的一般信息( 如年龄、性别等) 和x 光影像数据等1 8 个特征 数据，利用粗糙集理论进行挖掘，提高了肺癌病人早期诊断的正确率。日本合作研究 发展中心的m i 坫u r uk a k i m o t 等人提出了用逻辑回归分析算法( l o g i c a lr e g r e s s i o n a n a l y s 括e r a ) 提取关联规则，发现了脑部功能与手指活动和说话行为之间的关系。加 拿大a l b e r t a 大学计算机系的o s m a rr z a i y a n e 等人就神经网络和关联规则挖掘技术在 乳腺癌分类研究中的应用进行了分析对比，认为神经网络的方法对数据集不平衡性的 敏感程度低于关联规则挖掘方法。o r d o n e z 提出了一种不依赖特定应用领域知识的图 像关联规则算法，但是该算法只能产生图像对象共同出现的关联规则，仅仅适用于相 同类型且只包含少量对象的图像，在很大程度上受着海量数据库集在快速执行时常见 的算法问题的限制。 在国内数据挖掘研究方面，清华大学石纯一、陆玉昌教授、中科院计算所史忠植 6 基于复杂网络的数据挖掘分类问题研究与应用 研究员、中国科技大学王煦法教授等已取得了许多研究成果，但在医学图像的数据挖 掘方面的研究较少。上海交通大学生物医学工程系庄天戈教授采用当代乳腺疾病x 线诊断图谱中的2 3 0 个病例数据，应用决策树算法进行了数据挖掘的尝试。由中国 科学院自动化研究所田捷教授、北京大学包尚联教授、西北大学周明全教授合著的专 著医学影像处理与分析n 刚一书，系统地介绍了医学影像处理与分析技术，涵盖计 算机断层扫描成像技术、医学图像的分割、医学图像的配准、医学图像的三维重建与 可视化技术、虚拟内窥镜技术及p a c s 系统等内容。江苏大学朱玉全、杨鹤标等人在 所著数据挖掘技术啪1 中，对医学图像分类框架模型进行了分析，并利用关联规则 进行了挖掘研究。总之，国内在这方面的研究还处于起步阶段。 目前国内外学者对包括医学图像分类在内的医学图像挖掘的研究已经取得了一定 进展，但多数都是有导分类方法，基于复杂网络和聚类的方法还很少。因此迫切需要 研究医学图像分类的新技术和新方法，复杂网络领域的日渐成熟及其科研成果与已有 的聚类、分类方法相结合为其研究提供了广阔的发展空间，这是本文主要任务之一。 1 3 论文的创新点 本文在复杂网络的基础上，将复杂网络理论成果与已有的某些模式识别方法相结 合，对分类问题做了相关研究。本文创新点体现在以下几个方面： ( 1 ) 复杂网络的社团探测与数据挖掘中分类、聚类问题在本质上是一样的，因而 社团探测算法和分类问题的研究可以相互借鉴。本文基于f o r t u n a t o 等人提出的边的信 息中心度，定义了节点的关联度，并通过节点关联度矩阵来进行聚类中心的选择和节 点聚类，从而将复杂网络划分成k 个社团，然后通过模块度来确定网络理想的社团结 构。该算法具有很高的分类精度，而且时间复杂度为线性的，适合大型网络的社团发 现。丰富和发展了复杂网络社团探测理论和方法。 ( 2 ) 遗传算法作为一个成熟的理论，在分类方面有着很多优势。本章在分析了遗 传算法的优缺点后，结合复杂网络研究的部分新理论成果和遗传算法的思想，提出了 一种新的分类方法。该方法将数据集按给定的相似度公式构造出具有社团结构的网络， 在此网络的基础上用遗传算法的思想进行分类。算法引进社团模块度作为适应度函数， 并且提出了节点归类错误率c m 对每次迭代产生的解进行纠错，提高了分类质量和 速度。实验证明该方法在分类精度和分类速度方面都非常理想，该方法改进了遗传算 法的一些不足，同时充分利用了遗传算法的优点( 如可实现并行性) ，将遗传算法的优 点发挥到了极致。 ( 3 ) 医学图像分类是典型的分类挖掘问题之一，同时也是一个热点的应用研究课 题。本文结合复杂网络社团划分的部分理论成果和k - m e a n s 聚类算法的思想，提出了 基于加权复杂网络聚类的医学图像分类器。该分类器对医学图像进行预处理，建立图 7 基于复杂网络的数据挖掘分类问题研究与应用 片特征库，构建图片加权复杂网络，在此基础上根据网络节点的加权网络特征值和连 接度选取初始聚类中心进行聚类，有效地克服了传统k - m e a n s 聚类算法对初始化选值 敏感性的问题，从而大大提高了分类精度。 1 4 论文组织结构 本文的组织结构如下： 第一章绪论，简单的介绍了论文的研究意义、 组织结构。 第二章对数据挖掘分类算法做了简单的介绍， 算法。 研究现状、论文的创新点和论文的 介绍了目前国内外比较基本的分类 第三章对复杂网络进行的了概述，介绍了复杂网络的研究简史，基本概念等。 第四章中介绍了k - m e a n s 聚类算法，提出了一种基于k - m e a n s 聚类算法的复杂网 络社团发现新方法，在本章最后给出了例证和算法分析。 第五章首先介绍了遗传算法的基本理论和优缺点，最后结合复杂网络相关理论