（计算机系统结构专业论文）基于蚁群算法的数据挖掘算法研究及其在网格平台上的实现.pdf

1 塑! ：! 盐塑! ! 兰堡 摘要 本文旨在研究蚁群算法原理的基础上，丌展包括基于蚁群算法的分类和聚类 问题的数据挖掘方法研究，并针对地震数据的特点，将所研究的方法在地震预测 上加以应用。为了提高算法的计算速度，本文还搭建了一个网格应用平台d m g r i d ( d a t a m i n i n g g r i d ) ，以使算法在实际中能够更广泛地得以应用。 本文首先总结了数据挖掘研究领域的发展现状及分类和聚类挖掘方法的特 点，并介绍了蚁群算法的原理以及基本嘲格技术。之后，阐述了基于蚁群算法的 分类挖掘的原理，针对算法本身所存在的问题提出相应的改进和优化方案，并通 过实验证明了优化后的算法能达到更好的实验效果。接着，本文还对基于蚁群算 法的聚类问题进行研究，阐述了蚁群聚类算法的原理，通过实验证明了理论的有 效性，并把它有效应地用于地震预测巾。最后，针对蚁群算法作为一种进化算法 本身所存在的速度较慢的问题，引入网格技术以充分利用网格的计算资源。为此， 本文介绍了我们搭建的网格平台d m g r i d 的框架以及操作界面，以期可以在实际 中更广泛地应用这些基于蚁群算法的各种数据挖掘算法。文章最后给出了全文的 总结并对下。步的研究工作重点提出展望。 关键词：数据挖掘、蚁群算法、分类、聚类、1 删格平台 v 拇人学计算机学院 a b s t r a c t t h ep u r p o s eo ft h et h e s i sw a st od ot h er e s e a r c ho na n tc o l o n ya l g o r i t h m ( a c a ) b a s e dc l a s s i f i c a t i o na n dc l u s t e r i n ga l g o r i t h m sa n da p p l yt h e mt ot h e e a r t h q u a k e f o r e c a s ta r e at h et h e s i sp r o p o s e da n dr e a l i z e dag r i da p p l i c a t i o np l a t f o r md m g r i d ( d a t am i n i n gg r i d ) t h a tw a ss e tu pt os p e e du pt h ep r o p o s e da l g o r i t h m s t h et h e s i sf i r s t l ys u m m a r i z e dt h ed e v e l o p i n gs i t u a t i o no fd a t am i n i n ga n dt h e f e a t u r e so fc l a s s i f i c a t i o na n dc l u s t e r i n ga l g o r i t h mi ta l s oi n t r o d u c e dt h ep r i n c i p l eo f a c aa n dg r i dt e c h n o l o g ya st h eb a s i ck n o w l e d g eo ft h er e s e a r c hw o r ks e c o n d l y , t h e t h e s i se x p a t i a t e dt h eb a s i ci d e ao ft h ea c ab a s e dc l a s s i f i c a t i o nm i n i n ga l g o r i t h m ，a n d p r o p o s e da ni m p r o v i n ga n do p t i m i z i n gm e t h o di no r d e rt oo v e r c o m et h ep r o b l e m s e x i s t e di nt h ea l g o r i t h m t h et h e s i sa l s ov a l i d a t e dt h ei m p r o v e m e n te x p e r i m e n t a l l y t h i r d l y , t h et h e s i sd i dt h er e s e a r c ho na c ab a s e dc l u s t e r i n ga l g o r i t h m ，e x p a t i a t e di t s b a s i ci d e a ，d e m o n s t r a t e dt h ev a l i d i t yo fi t sp r i n c i p l ee x p e r i m e n t a l l y , a n da p p l i e di tt o t h ee a r t h q u a k ef o r e c a s tp r o p e r l y f o u n h l y , p r o f i t i n gf r o mt h ef u l lu s a g eo f c o m p u t i n g r e s o u r c eo fg r i dt e c h n o l o g y , t h et h e s i s g a v et h es t r u c t u r ea n di n t e r f a c eo fg r i d p l a t f o r md m g r i dt or e s o l v et h el o ws p e e dp r o b l e mo fa l g o r i t h m s i nt h i sw a y , w e w i s ht h a tt h ea c ab a s e dm i n i n ga l g o r i t h m sw i l lb eo fw i d eu s ei np r a c t i c a l f i n a l l y t h et h e s i sc o n c l u d e dt h ew h o l es t u d ya n dm a d et h ep r o s p e c tt ot h ef u t u r er e s e a r c h k e y w o r d ：d a t am i n i n g ，a n tc o l o n ya l g o r i t h m ，c l a s s i f i c a t i o n ，c l u s t e r i n g ，g r i d v 原创性声明 本人声明：所呈交的论文是木人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一1 作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：蔓9j 叁墨日期：! 盟 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复e 件，允许论文被查阅和借阅；学校口j 以公布沦文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 繇牡新籀 靴：g 弓，击 海人学汁算机学院 1 1 研究背景 第一章引言 本文是在上海市教委的科研项目：“数据挖掘在地震数据网格中的应用研 究”的基础上所作的研究，硬件系统主要是上海大学的超级计算机自强3 0 0 0 。 数据挖掘就是从大量的数据中发现知识的过程，也称为知识发现。发现的 知识可以用于决策、过程控制、信息管理和查询处理等等。因此，数据挖掘被 信息产业界认为是数据库系统最重要的前沿之一，是信息产业最有前途的交叉 学科。 数据挖掘是一门具有广泛应用的新兴学科，目前它已涉猎许多科学和商业 应用领域。如针对生物医学和d n a 数据分析的数据挖掘，d n a 分析的研究成 果已经导致了对许多疾病和致残的基因成因的发现，以及对疾病的诊断、预防 和治疗的新药物、新方法的发现；在针对金融数据分析的数据挖掘领域，对贷 款偿还预测和客户信用政策分析、对目标市场客户的分类和聚类，对洗黑钱和 其他金融犯罪的侦破，都有典型的应用；在零售业中，数据挖掘可有助于识别 顾客购买行为，发现顾客购买模式和趋势，改进服务质量，取得更好的顾客保 持力和满意程度等：在电信、世中的数据挖掘领域，数据挖掘技术可以帮助理解 商业行为、确定电信模式、捕捉盗用行为、更好地利用资源和提高服务质量等。 数据挖掘任务一般可以分为两类：描述和预测。描述性挖掘任务刻画数据 库中数据的，一般特征。预测性挖掘任务在当前的数据l 进行推断，以进行预测。 数据挖掘功能以及他们呵以发现的模式类型主要包括以下几种：概念类描 述，用汇总的、简洁的、精确的方式描述每个类和概念：关联分析，发现关联 规则，展示属性一值在给定的数据集中一起出现的条件；分类和预测，找出描 述并区分数据类和概念类的模型( 或函数) ，以便能够使用模型预测类标记未知 的对象类；聚类分析，分析数据列象，而不考虑类标记，按照最大化类内的相 似性、最小化类间的相似性的原则进行聚类或分组，使得簇内的对象具有很高 的相似性，而与其他簇中的对象很不相似；孤立点分析，找出数据对象中与数 化问题，取得了较好的效果。虽然对蚁群算法研究的时间不长，但是初步研究 已显示出蚁群算法在求解复杂优化问题( 特别足离散优化问题) 方面具有一定 的优势，表明它是一砷很有发展前景的方法 1 8 。 对蚁群算法的研究表明，它不仅具有智能搜索、全局优化的功能，而且具 有稳健性、鲁棒性、f 反馈、分布式计算、易与其它算法结合等特点。利用f 反馈原理，蚁群算法能较快地发现问题的较好解；分布式计算使该算法易 i 并 行实现，个体之间不断进行信息交流和传递以找到较好的解，不容易陷入局部 最优；该算法易于与多种启发式算法结合，可改善算法的性能；由于鲁棒性强， 在基本蚁群算法模型的基础上进行修改，便可用于其它问题。因此，蚁群算法 的问世为诸多领域解决复杂优化问题提供了有力的工具 4 。 蚁群算法在动态环境f 也表现出高度的灵活性和健壮性，如其在电信路山 控制方面的应用被认为是目前较好的算法之一。此外，蚁群任务分工、打扫蚁 巢和分类蚁卵等行为也启发了相应的协作和聚类算法。 近年来，基于蚁群算法的各种数据挖掘方法不断提出，并不断有学者针列 其中的某种算法提出优化方案。因此，基_ ：r 蚁群算法的数掘挖掘研究目前已经 海人学汁算机学院。 被部分应用到实际应用中，并取得了不错的效果。这些基于蚁群算法的挖掘算 法的研究和成功表明蚁群算法在数据挖掘方面很有研究价值。 网格技术是近年来出现并迅速发展的技术模式，目前针对大数掘量分却式h 算问题，虽然有很多种解决办法，但与同类的技术相比，网格技术在资源动态管 理、系统安全性等方面，有很多优势。 在硬件方面，网格平台工具的发展也已同趋成熟，网格平台搭建工具g r i d t o o k i t ( g t ) 己推出了多个版本，从较甲的g t 2 0 ，丑 g t 30 、g t 3 ，1 、g t 3 2 ， 目1 1 1 g r i d t o o k i t 40 也己丌始发行，并被许多研究者接纳使用。 目前有很多国内知名高校都纷纷对网格进行深入研究，根据需要联合建越了 多个网格系统，如中国教育科研阀格c h i n a g r i d ，它是由华中科技大学、清华大 学、北京大学、上海交通大学等1 2 所高校参与的网格平台，其目的是充分利用中 国教育科研n c e r n e t $ 1 j 高校的大量计算资源，丌发相应的网格软件，配合网络汁 算机( n c ) 的使用，将分和在教育和科i j t n j 上自治的分布异构的海量信息资源 集合起来，实现c e t r n e t 环境下资源的有效共享，消除信息孤岛，提供有效的服 务，形成高水平低成本的计算服务，将高性能计算送到教育和科研用户的桌面i ： 口6 。 由上海大学计算机学院院长、首席研究员李三立院士主持的上海高校网格技 术e 研究院正在建设新一代的信息基础设施“上海高校网格平台”。上海高校网 格把分布在不同地点的、不同单位的、不同计算节点的各种计算和信息服务资源， 例如处理能力、存储能力和信息服务能力，整合为一个单，一的( 虚拟的) 系统， 创造跨学科、跨地区科研交流的合作环境，促进解决重大科技项目的攻关，解决 前沿学科领域的难题，推动基础理论研究进展与创新。 目前，上海高校网格平台由四个集群的分布汁算资源、基于网格o g s i 舰范 和网格核心中间件组成。这四个高性能计算集群为： 上海大学“自强3 0 0 0 ”： | ：_ 海大学“自强2 0 0 0 ”； 华东理工“s i m f a r m ”： 上海超级计算中心“曙光4 0 0 0 a ”。 泡人学计算。帆学院 陔计算网格已经在复杂材料分子模拟的计算中得到充分应用，为从事化学与 材料制备基础研究的人员提供了分子模拟与分析多种资源服务，使研究人员之洲f t 共享研究成果和服务，并使该领域的研究在固际上处于领先水1 王。 本课题将致力于基于蚁群算法的分类和聚类研究。基于蚁群算法的各种数据 挖掘算法虽然在实验中被证明是有效的，甚至比其他一些经典的数据挖掘算法能 达到更好的实验结果，但是由于其进化速度较慢，仍然得不到广。泛的应用。因此 本文还将探讨算法如何利用网络分散、闲置的训。算资源，在网格环境下，用灵活 的方式提高蚁群算法的进化速度，以达到实际应用的目的。 1 2 研究内容 本文的研究内容主要分为三大部分： 1 基于蚁群算法的蚁群分类的研究和优化； 2 基于蚁群算法的蚁群聚类的研究： 3 算法在网格平台上的实现研究。 其中，“基于蚁群算法的蚁群分类的研究和优化”的主要工作是：对现存的 基于蚁群算法的分类挖掘( a n t m i n e r ) 进行深入研究，阐述了蚁群分类的原理， 指出了在实验过程中发现的算法本身所存在的几个问题，并针对这些问题提出 相应的改进和优化方案，最后通过实验证明优化后的算法能达到更好的实验效 果。 基于蚁群算法的蚁群聚类研究的主要工作是：把蚁群算法的原理与数据挖 掘中的聚类原理相结合，找到它们的结合点，并通过实验证明这种结合的有效 性。 “算法在网格平台上的实现研究”这部分的主要工作是：利用当前的网格 技术，结合实际，搭建一个网格应用平台，通过网格系统提高资源利用率，确 保在大数掘量计算情况下的计算速度。同时，被授权用户可以从界面登录系统， 选择自己需要的算法，系统也提供一些算法参数接口，使用户可以按照自己的 需要在自己的数据集上进行数据挖掘。 海人学计算机学院 第二章基础知识 2 1 蚁群算法原理 蚁群算法的本质是模拟真实世界蚁群的行为，它最早是由意大利学者 m d o r i g o 等人提出的。蚂蚁属于群居昆虫，个体行为极其简单，而群体行为却 相当复杂。人们通过大量的研究发现，蚂蚁虽没有视觉，而且蚂蚁之间并没有 直接交互，但是蚂蚁群体却通过各自与环境进行交互而完成了相互协作，并最 终找到从食源到蚁穴的最短路径；同时，它们能适应环境的改变，当原先最短 的路径j 二出现障碍物时，能够再发现一条新的最短路径。 蚁群算法本来是生物学家为更好揭示昆虫的交互作用而提出的一种昆虫自 组织模式。尽管建立这种模式的初衷是为了帮助人们去理解这类昆虫的复杂行 为但是数学及训算机方面的专家和工程师却把这种超越生物本身的模型转化 成了一项有用的优化和控制算法一蚁群算法，也称蚁群系统。 该系统的原理可大致描述如下：蚂蚁个体之问是通过一种称为信息素 ( p h e r o m o n e ) 的物质进行信息传递的。蚂蚁在运动过程中，不但能够在它所经 过的路径上留下信息素，而且能够感知信息素的存在及其强度，并倾向于朝着 信息素强度高的方向移动，以此指导自己的运动方向。于是路径的长短及陔路 径卜通过的蚂蚁的多少就对残余信息素的强度产生影响，反过来信息素的强弱 又指导着其它蚂蚁的行动方向。因此，由大量蚂蚁组成的蚁群的集体行为表现 出种信息正反馈现象：某一路径越短，走过的蚂蚁数就越多，、而某一路径上 走过的蚂蚁越多，该路径上的信息素数量就越多，则后来的蚂蚁选择孩路径的 概率越大。蚂蚁个体之间就是通过这种信息的交流进行路径的最优选择，从而 达到搜索食物的目酐j 1 8 1 。基本蚁群算法的原理，如图2 1 所示。 海大学| 十算帆学院 剀2 1 蚁擀系统1 i 恿削 图21 中，设a 是蚁巢，e 是食物源，h 、c 为障碍物，距离为d 。由于障 碍物的存在，由a 外出觅食或由e 返回巢穴的蚂蚁只能经由h 或c 到达目的 地。假定：( a ) h , j 间t 是离散的；( b ) 在每1 个时问单位内，1 只蚂蚁运动l 堆位 距离，运动后释放1 单位的信息素；( c ) t = o 时，存任何路径上都没有信息素； ( d ) 蚂蚁在b 或d 点，以相同的概率选择下路径【4 。 假设蚂蚁往返于a 和e ，每经过一个单位时问各有3 0 只蚂蚁离开a 和e 到达b 和d ( 图2 1 一a ) 。初始时，各有3 0 只蚂蚁在b 和d 点遇到障碍物，丌 始选择路径。由于此时路径上无信息素，蚂蚁便以相同的概率随机地走两条路 中的任意一条，因而15 只选往c ，l5 只选往h ( 图21 - b ) 。经过一个单位时问 以后，路径b c d 被3 0 只蚂蚁爬过，而路径b h d 上则只被1 5 只蚂蚁爬过( 囡 b c d 距离为1 而b h d 距离为2 ) ，b c d 上的信息量是b h d 上信息量的两倍。 此时，又有3 0 只蚂蚁离丌b 和d ，于是2 0 只选择往c 方向，而另外1 0 只则 选往h ( 图2 1 一c ) 。这样，更多的信息素量被留在更短的路径b c d 上。随着时n j j 的推移和上述过程的重复，短路径上的信息量便以更快的速度增长，于是会有 越来越多的蚂蚁选择这条短路径，以致最终完全选择这条短路径。 由上述可见，蚁群算法的核心有三条。第一，选择机制：信息素越多的路 径，被选中的概率越大；第二，信息素更新机制：路径越短，信息素增加越陕： 第三，协作机制：个体之 u j 通过信息索进行交流。 2 2 数据挖掘中的分类与聚类 数据库内容丰富，蕴藏大量信息，譬如从数据库中进行知识发现可辅助作 出智能的商务决策。分类和聚类都是数据挖掘中重要的数据分析方法。其中分 类力法可以用于提取描述重要数据类的模型或预测未来的数据趋势，它找出拙 海人学计算：t - j c 学院 述区分数据类的模型，以便能够使用模型预测类标电未知的对象类。聚类分析 数据剥象，根据最大化类内的相似性、最小化类间的相似性的原则进行聚类或 分组。即对象的簇这样形成：使得在一个簇中的对象具有很高的相似性，而与 其他簇中的对象很不相似。所形成的每个簇可以看作一个对象类，由它可以导 出规则，把类似的事件组织在一起。f 边将介绍分类和聚类这两种数据挖掘技 术。 2 2 1 分类分析 数据分类的原理可描述如下，分两步来介绍。 第一步，建立一个模型，拙述预定的数据类集或概念集。通过分析用属性 描述的数据库元组来构造模型。 假定每个元组属于一个预定义的类，由 个称作类标号属性( c l a s sl a b e l a t t r i b u t e ) 的属性确定。对于分类，数据元组也称为样本、实例或对象。为建立 模型而被分析的数据元组形成的是训练数据集。训练数据集中的单个元组称作 训练样本，并随机地由样本群选取。由于提供了每个训练样本的类标号，对这 类样本的学习也称作有指导的学习( 即模型的学习在被告知每个训练样本属于 哪个类的“指导”下进行) 。 通常，学习模型用分类规则、判定树或数学公式的形式提出。例如，给定 一个顾客信用信息的数据库，可以学习分类规则，根据他们的信誉度等级，例 如“优良”或“相当好”来识别顾客。这些规则可以用来为以后的数据样本分 类，也能对数据库的内容提供更好的理解。 第二步，使用模型进行分类。首先评估模型( 分类法) 的预测准确率。随 机选取一批样本作为测试集，注意这批样本要独立于训练样本。对于每个测试 样本，将已知的类标号与陔样本的学习模型类预测比较。模型在给定测试集上 的准确率是被模型正确分类的测试样本的百分比。 如果认为模型的准确率可以接受，就可以用它对未知类标号的数据元组或 对象进行分类。例如，可以通过分析现有顾客数据，得到分类规则，再根据这 些规则预测新的或未来顾客的信誉度。 海人学计算：f j l 学院 数据分类具有广泛的应用，包括信誉证实、医疗诊断、性能预测和选择购 物。例如，可以建立一个分类模型，对银行贷款的安全或风险进行分类；同时 可以建立模型，对给定的潜在顾客的收入和职、峨预测他们在计算机设备k a d 花费。 日前，数据分类的基本技术主要包括：判定树归纳分类、贝叶斯分类和贝 n t , h 0 7 刚络、神经网络、源于自关联规则挖掘概念的分类，以及一些其他的分类 方法，如肛最临近分类、基于案例的推理、遗传算法和模糊逻辑技术等。 其中，判定树归纳分类的基本算法是贪心算法，它以自顶向下递归的各个 击破方式构造判定树。“1 0 3 ”是一种著名的判定树归纳算法。“c 4 5 ”算法是 “1 0 3 ”算法的后继版本。算法的基本策略如下： l ，树以代表训练样本的单个节点丌始； 2 如果样本都在同一个类，则该节点成为树叶，并用该类标记； 3 否则，算法使用称为信息增益的基于熵的度量作为启发信息，选择能够 最好地将样本分类的属性。该属性成为该节点的“测试”或“判定”属性； 4 对测试属性的每个已知的值，创建一个分支，并据此划分样本； 5 算法使用同样的过程，递归地形成每个划分上的样本判定树。一旦个 属性出现在一个节点上，就不会出现在该节点的任何后代上： 6 递归划分步骤仅当下列条件之一成立时停止： ( 1 ) 给定节点的所有样本属于同一类： ( 2 ) 没有剩余属性可以用来进一步划分样本。在此情况下，使用多数表决 的方法。这涉及将给定的节点转换成树叶，并用样本中的多数所在的类标记它。 换一种方式，可以存放节点样本的类分布。 ( 3 ) 分支中没有样本。在这种情况下，以样本中的多数类创建一个树叶。 其中，上面所提到的信息增益度量是一种属性选择度量方法，称作属性选 择度量或分裂的优良性度量 1 。即选择具有最高信息增益的属性作为当前节点 t i j ! l 试属性。该属性使得对结果划分中的样本分类所需的信息量最小，并反映 划分的最小随机性或“不纯性”。这种信息理论方法使得对一个对象分类所需的 期望测试数目达到最小，并确保找到一棵简单的树。 ￥阿凡学计算机学院 在本文中，将通过试验把c 4 5 算法与基于蚁群算法的分类算法进行比较。 2 2 2 聚类分析 聚类就是将物理或抽象对象的集合分组成为由类似的对象组成的各个类或 簇的过程。由聚类所产生的每个类( 簇) 是组数据对象的集合，在同一个簇 中的对象之间具有较高的相似度，而不同簇中的对象差别较大。在许多应用中， n r 以将一个簇中的数据对象作为一个整体来对待。在机器学习领域，与分类不 同的是，聚类是无指导学习的一个例子，要划分的类是未知的，就是每个训练 样本的类标号是未知的，要学习的类集合或数量也可能事先不知道。由于这个 原因，聚类是观察式学习 1 。 聚类分析是知识发现的重要方法，有着广泛的应用。在商务上，聚类已成 为客户关系管理c r m ( c u s t o m e r r e l a t i o n s h i pm a n a g e m e n t ) 中重要的分析手段。 它可以帮助市场分析人员从容户基本库中发现不同兴趣的客户群，由此来决定 相应的市场策略和操作方式。在生物学e ，聚类用于推导植物和动物的分类， 对基因进行分类，获得对种群固有结构的认识。聚类还应用于w e bf 1 志挖掘， 通过网页聚类和用户聚类，为网站设计人员提供有关用户兴趣的信息，合理调 整删页的结构和内容，而在推荐系统中，相似兴趣的用户聚类可以更好获取用 户的偏好，从而进行协作过滤，实现个性化的信息推荐服务。 1 算法描述 聚类的数学模型可描述如下。己知模式样本集 x 有n 个样本和k 个模式 分类 s j ，j = 1 ，2k ) ，咀每个模式样本到聚类中心的距离之和达到最小为准则， 其数学模型为： r a i n 肛一m j4 ( 2 1 ) j 2 1 爿c 一 式中k 为聚类数目，为，类样本的均值向量。若模式样本i 分配第j 聚类 中一0 ，则令y i j = l ，否则令y 。= 0 。y 口= l 表示模式样本i 只能分配到个聚类 i = 1 中心上。 1 翌查兰生塑型! 兰堕 一一 2 ，相似度 聚类分析按照样本在性质上的亲疏远近的程度进行分类。刻画样本点之叫 i t , jq 、目似性主要有以下两类函数： r 1 1 距离函数：样本用n 维特征变量来描述，每个样本都可以看成是 4 i s 空| 1 _ 1 j 中的一个点，使用某神距离来表示样本点之间的相似性。距离较近的样本 点性质相似，距离较远的样本点则差异较大。 距离函数具有以下特性： a 非负性d ( x ，y ) o ； b d ( x ，x 1 2 0 ： c 对称性d ( x ，y ) = d ( y ，x ) ； d 满足三角不等式d ( x ，y ) + d ( y ，z ) d ( x ，z ) 。 距离度量方法主要有欧几早德距离： 厂一：了 d ( f ，) = j i x 。一x ，l l2 十i x ! 一x ，! i ! + 。+ l x 。一x ，l 2 ( 22 ) 其中，u 。= ( x mx ，x 。) 和u j = ( x j l ，x j z ，x j n ) 是n + n 维数据对象。 如果对数掘对象的每个属性赋予一个权重，那么加权的欧几里德距离也称 为明考斯基距离，可以表示为： 删：瓜i 再瓦j 再i 蕊 ( 2s ， ( 2 1 相似系数：两个样本点越相似，相似系数愈接近1 ；两个样本点越不相 似，相似系数愈接近0 。 角度相异度度量：用向量夹角余弦公式度量样本x ( x y 2 ，y 。) z i 、司的角度相异度。夹角余弦公式为： ( 3 1 皮尔森相关系数 f 24 1 海人学汁算机学院 样本i 和样本j 的相关系数为 ( 一巧x v r i ，) i ：! ! ：； j 沙r e ) 2 莩k ，) 2 其中，巧为均值。e = 去喜v i ，= 去喜v “。 ( 25 ) 3 数据结构 聚类算法最常使用的两个有代表性的数据结构为数据矩阵和相异度矩阵。 数据矩阵：采用关系表的形式，是一个n * p 矩阵，表示具有p 个属性的n 个变量。 x ，。x ，。 相异度矩阵：矩阵中d ( i ，j ) 为对象i 和对象j 之问相异度的量化表示，它是 一个非负的数值。对象i 和对象j 越相似，d ( i ，j ) 的值越接近o ；对象i 和对琢j 越不同，d ( i ，j ) 的值越大，且d ( i ，i ) = o ，d ( i ，j ) = d o ，i ) 。相异度矩阵比较全面 地反映了各分类对象问i 拘* n p 3 , 程度，是进行聚类分析所依据的基础 1 。 o d ( 2 ，1 ) 0 d ( 3 ，1 ) d ( 3 ，2 ) 0 o o 4 已有的聚类技术 聚类分析作为统计学的一个分支和一种无教师监督的机器学习方法，已有 几十年的历史，并己取得了许多研究成果。在数据挖掘领域，研究工作己经集 中在为大型数据库的有效的和实际的聚类分析寻找适当的方法。活跃的研究主 海人学计算机学院 题集中在聚类方法的可伸缩性，方法对聚类复杂形状和类型的数据的有效性， 高维聚类分析技术，以及针对大型数据库中混合数值和分类数据的聚类方法。 4 i 同的聚类算法有各自的优缺点和应用的范围，研究各聚类算法的特性使我们 能够根据具体的应用领域扬长避短，选择最适当的聚类技术解决实际问题 1 。 ( 1 ) 划分方法( p a r t i t i o n i n g m e t h o d ) 划分方法是给定一个具有n 个对象或元组的数据库，一个划分方法构建数 据的k 个划分，每个划分表示一个聚簇，并且k - j 惯的 统一的形式访问和使用各种网格资源。网格计算能力可以通过网格系统输送到 任何角落，随处可得。换句话说，在网格上没有资源处在什么位置的概念，只 有“在网格上”和“不在网格上”的区别。无论你在什么地方，网格资源都在 海人学汁算。机学院 你的旁边。 网格费用的低廉性要求是网格能够被普遍接受和推广的前提，不管网格有 多少优点，如果大多数的使用者无法承受其费用，网格就不可能被普及，它的 各种优势也就根本无法得到体现。网格技术通过将资源充分共享，最大限度发 挥资源的使用价值，可以将原来闲置和浪费的资源搜集起来供网格用户使用， 而且可以避免以前由于地理位置限制所带来的各种额外开销，显然网格列使用 名存在着很大的降低开销的潜力。 这些要求，都是网格需要解决的问题，也是网格技术发挥作用的地方。网 格作为一种新型而重要的基础发施，不是一夜之间就能奇迹般的突然出现的， 需要各个方面联合起来，共同努力才可以实现。 g l o b u s 项目是目前国际上最有影响力的网格项目之一。它发起于九十年代 中期，其最初目的是希望把美国境内的各个高性能计算中一t l , 通过高性能网络连 接起柬，方便美国的大学和研究机构使用，提高高性能计算机的使用效率。 g l o b u s 对信息安仑、资源管理、信息服务、数据管理以及应用开发环境等网格 计算的关键理论和技术进行了广泛的研究，丌发出能在多种平台e 运行的网格 计算工具包软件( g l o b u st o o l k i t ) ，能够用来帮助规划和组建大型的网格试验和 应用平台，开发适合大型网格系统运行的应用程序。g l o b u s 工具包的源代码是 公丌的，遵循g l o b u st o o k i tp u b l i cl i c e n s e ( g t p l ) 协议，任何人都可以从其 网站上下载源代码并进行研究和修改。目的g l o b u s 工具包已经在n a s a 网格 ( n a s a i p g ) 、欧洲数据网格( d a t ag r i d ) 、美国国家技术网格( n t g ) 等众多 项目中得到应用。 网格概念的提出将从根本e 改变人们对“计算”的看法，因为网格提供的 是与以往根本不同的训算方式。r a n d yb r a m l e y 认为网格提供的计算能力是以前 所无法得到的，而且也是不能够通过其它的方式得到的。网格概念的核心就是 突破了以往强加在汁算资源之上的种种限制，使人们可以以一+ 种全新的、更自 由的、更方便的方式使用计算资源，解决复杂的问题 5 。 海人学科算机学院 2 3 2 网格体系结构 g l o b u s 项日对信启、安全、资源管理、信息服务、数据管理以及应用丌发环 境等网格计算的关键理论和技术进行了广泛的研究，r 发出能在多种平台匕运 行的网格计算工具包软件( g l o b u s t o o l k i t ) ，能够用束帮助规划和组建人型的网 格试验和应用平台，开发适合大型网格系统运行的应用程序。 回 厂i 翮 二匦二 固 幽2 2 网格计算协议与互联网协议的比较 g l o b u s 的网格计算协议建立在互联网协议之上，以互联网协议中的通信、 路由、名字解析等功能为基础。g l o b u s 的协议分为五层：构造层、连接层、资 源层、汇集层和应用层( 如图22 ) 。每层都有自己的服务、a p i 和s d k ，上层协 议调用下层协议的服务。网格内的全局应用都通过协议提供的服务调用操作系 统接口。 网格计算协议主要分为五层，各层次的主要功能如下： 1 构造层( f a b r i c ) 基本功能是控制局部的资源，向上提供访问这些资源的接口。构造层的资 源是非常广泛的，可以是计算资源、存储资源、目录、网络资源以及传感器等。 2 连接层( c o m e c t i v i t y ) 它是网格中网络事务处理通信与授权控制的核一0 协议。构造层提交的各种 资源问的数据交换都在这一层的控制下实现。各资源问的授权验证、安全控制 也在这单实现。在t o o l k i t 中，相应组什采用基1 i 公钥的网格安全基础协议 f g s i ) 。在此胁议中提供一次登录、委托授权、局域安全方案整合、基于用广， 的信任关系等功能。资源帕_ 】的数据交换通过传输、路由及名字解析实现。 3 资源层( r e s o u r c e ) 这一层的作用是对单个资源实施控制，与可用资源进行安全握手、对资源 做初始化、监测资源运行状况、统计与付费有关的资源使用数据。在t o o l k l t 中 有一系列组件用来实现资源注册、资源分配和资源监视。t o o l k i t 还在这层定 义了客户端的c 、j a v a 的a p i 和s d k 。 4 汇集层( c 0 1 1 e c t i v e ) 这层的作用是将资源层提交的受控资源汇集在一起，供虚拟组织的应用程 序共亨、调用。为了划来自应用的共享进行管理和控制，汇集层提供目录服务、 资源分配、同程安排、资源代理、资源监测诊断、网格启动、负荷控制、账户 管理等多种功能。 5 应用层( a p p l i c a t i o n s ) 这层是脚格上用户的应用程序。应用程序通过各层的a p i 调用相应的服 务，再通过服务调用网格上的资源来完成任务。应用程序的开发涉及大量库函 数。为便于网格应用程序的丌发，需要构建支持网格计算的库函数。 海人学汁算机学院 第三章基于蚁群算法的分类研究 基于蚁群算法的分类研究是一种新型的数掘挖掘算法，它最早是山 p a r p i n e l l i ，l o p e s , d f r e i t a s 等人首先提出的，他们最先把蚁群算法用于分类规则 发现。用蚁群算法训练分类规则库的过程实质上也是从大的数据集中发现知识 的过程，所以这种方法也称为a n t m i n e r ，他们提出了最早的“a n t m i n e r ”系 统。在以后的一个阶段中有学者对其提出多次优化对其中存在的一些问题提 出了改进的方法。 3 1 基于蚁群算法的分类挖掘的原理 用进化算法的原理来解决实际问题的关键之处就在于找到合适的结合点， 用蚁群算法的原理进行数据挖掘的重氯也在这罩，即如何找到合适的问题表示 方法。本节将详细介绍基于蚁群算法的分类规则库的构建原理。 3 1 1 问题描述 定义路径为属性节点和类标号节点的连线，其中每个属性节点最多只出现 一次且必须有类标号节点。图3 1 中给出了两个可能的路径。每个路径对应着 一条分类规则，分类规则的挖掘可以看成划路径的搜索。蚁群算法利用蚂蚁寻 找食物形成最短路径的原理，可以用来进行分类规则的挖掘，只不过这里搜索 的不是最短路径，而是最优路径。最优路径表示了最优的分类规则。可以用路 径对应规则的分类能力( 有效性) 和长短( 简洁性) 来衡量路径的优劣。蚂蚁 构造规则的过程体现为构造一条路径，分为三个阶段。首先从一条空路径开始， 莛复选择路径节点增加到路径上( 模仿蚂蚁的爬行过程) ，直到得到一条完整路 径，也即一条分类规则；然后进行规则的剪枝，以考虑分类规则列样例的过度 拟合问题；最后更新所有路径上的外激素浓度对f 一只蚂蚁构造规则施加影 响( 模拟蚂蚁问的信息交流) 。 蚂蚁可以看作是不断挖掘分类规则自, ， a g e n t ，而蚁群的最终目标就是构造 海人学| 十算机学院 个能尽量达到预定效果的规则库。最终挖掘到的规则的形式是： i f t h e n 其中规则的c o n d i t i o n s 部分的形式是：t e r m la n d t e r m 2a n d t e r m 3 ，每个t e r m 都 是一个元组( a t t r i b u t e ，o p e r a t o r ，v a l u e ) v a l u e 是属性a t t r i b u t e 值域中的某个 值，o p e r a t o r 可以为“= ”；c l a s s 部分则是预测满足该条规则c o n d i t i o n s 部分的记 录所属的类别。 犀性l属性2嚏蛀j 属性l共耩碍 亨含昌一一一一号y 龅1oo o 一一一o 、o ooooo 昌占3 昌l 雌：oo o o 、雌： i 厦性节点i 裳撂号节点 圈3 1 对应着分类规则的路径 每只蚂蚁都从一条空规则丌始，构造过程就是不断添加t e r m 到当前的部分 规则的过程，部分规则就是该蚂蚁所走过的所有路径的集合，同样，下一个要 添加到当前部分规则旱的t e r m 就相当于蚂蚁在当前所有可选路径中所选的下一 条路径。蚂蚁矸i 断添加t e r m 到部分规则罩一直到规则无法再延伸。规则无法再 延伸也即所有属性都已经在它的规则罩出现，或者它所构造的规则的c o n d i t i o n s 部分所覆盖的记录条数小于系统给的参数m i n c a s e s p e r r u l e ( 每条规则所覆 盖的记录数目的最小值) 。到此规则的c o n d i t i o n s 部分构造完成；然后需要找舰 则的c l a s s 部分，这是通过赋给规则不同的c l a s s ，选择使规则q u a l i t y 值最大的 c l a s s 作为规则最终的c l a s s ，至此，一条规则构造完成。 蚁群算法用于分类挖掘的整体流程为： t r a i n i n gs e t = a l lt r a i n i n gc a s e s ： w h i l e ( n o o fu n c o v e r e dc a s e si nt h et r a i n i n gs e t m a x u n c o v e r e d _ c a s e s ) i - 0 ： r e p e a t f = i + 1 ： 海人学计算机学院 a n t li n c r e m e n t a l l yc o n s t r u c t sac l a s s i f i c a t i o nr u l e ； p r u n et h ej u s t c o n s t r u c t e dr u l e ； u p d a t et h ep h e r o m o n eo f t h et r a i lf o l l o w e db y a n t i ； u n t i lr i = n oo fa n t s ) o r ( a n t ic o n s t r u c t e dt h es a m er u l et h a nt h e p r e v i o u sn o r u l e s c o n v e r g 一，a n t s ) s e l e c tt h eb e s tr u l ea m o n ga l lc o n s t r u c t e dr u l e s r e m o v et h ec a s e sc o r r e c t l yc o v e r e db yt h es e l e c t e dr u l ef r o mt h et r a i n i n g s e t ； e n dw h l i ，e 流程中涉及到几个系统参数。其中， m a xu n c o v e r e dc a s e s ：规定每条规则至少覆盖的记录数目； n oo fh ：( ) 的数目，也就是择路过程中循环的次数：_ a l s a g e n t a n t n or u l e sc o n v e r g ：判断构造规9 j , l jq ：t 敛的参数，a g e n t 构造的规则数目达到 n or u l e sc o n v e r g 后，即开始检查所构造的规则是否与前面的规则重复，如果 重复，则说明构造过程己收敛循环提前结束【8 ，9 1 。 3 1 2 路径选择策略 蚂蚁选择路径是根据路径上信息素的多少进行的，它总偏向于走信息素量 大的路径。而在分类挖掘过程中，a g e n t 选择下一个t e r m 时依据的是两个因素， 一是该t e r m 上与问题相关的启发函数值，这也是人工蚁群算法在具体应用中比 生物蚁群进化的地方，它考虑了各个属性对数据对象的类别影响的不同，所以 可以对类别起决定性作用的属性赋予更大的启发函数值。二是与路径选择历史 信，a d , + h 关的信息素，就是t e r m 以前被选择的越多，t e r m 上的信息素值越大。 女w t e r m ，、的形式为a = v 。a ，是第i 个属性，v i i 是第i 个属性的第j 个值域， 那么t e r 叭被选择加入当前的部分规则的概率出式( 31 ) 得到，每次都选择概率最 大的t e r m l j h 入当前的部分规则。 海人学计算帆学院 p i j ( f ) r ，l c l q ， i f 一 o ( f ) _ 。，v ，e ， i ， ( 31 ) 其中，珊是t e r m u 上与问题相关的启发函数值： t i y ( f ) 是陀“上的信息素( 叫 刻t ) ：d 是属性数目：6 。是属性f 的值域个数；，是当前的蚂蚁所有未用过的属性集 合。 1 启发函数 上式( 31 ) 中启发函数r o l 拘构造如式( 3 2 ) t l o g2 ( 女) 一i n f o t i i f 一 1 0 9 ：( ) - - - if o t 。 i ， ( 32 ) 其中，是类的数目，n 是分析对象中的属性个数；b i 是对应属性i 的值域个 数；式( 3 2 ) i n f o 的构造如式( 33 )