（管理科学与工程专业论文）基于J2EE的数据挖掘框架与节点设计方法.pdf

摘要 作为一种新的数据分析工具，数据挖掘的发展十分迅速。各种类型的数据集 都可以作为数据挖掘的对象。面对现今越来越多的数据源和越来越大的数据量， 数据挖掘能够有效地从中获取有价值的信息，并可以使人们更好地预测未来可能 出现的数据信息，从而提高工作效率。随着挖掘算法研究的日益成熟，对数据挖 掘应用的研究自然成为当前的新兴热点。然而当前对数据挖掘应用的研究大部分 集中在整体的框架设计及基于新技术的数据挖掘应用上，而几乎没有探讨独立组 件的设计方式。本文在对数据挖掘的一般过程及相关算法进行分析的基础上，提 出了一种基于j 2 e e 组件技术的通用的数据挖掘系统框架。在此框架各模块对应 组件的设计思路上，提出了一种扩展性更好、耦合度更低的设计方式。文中借鉴 并扩展了s p s sc l e m e n t i n e 中节点的设计形式，并对挖掘过程进行了有效的分解 与重组，从而将整个过程良好地节点化。在挖掘流程的表达上，通过使用x m l 组合若干挖掘节点为节点链的方式有效地降低了系统的耦合性，并在此基础上提 出了基于挖掘主题的组织方式。最后，文中还较深入地研究了数据挖掘中经验和 知识的复用，并提出了几种逐次过渡的复用方式。 关键词：数据挖掘，节点，节点链，组件 a b s t r a c t a sa wk i n do f d a t aa n a l y s i st e c h n i q u e ，d a t am i n i n gd e v e l o p sf a s t m a n yk i n d s o fd a t a s e t sc a l lb et h eo b j e c t sofd a t am i n i n g n o w a d a y s ，d a t am i n i n gc a t l ld i s c o v e r s o m ev a l u a b l ei n f o r m a t i o nf r o mt h ei n c r e a s i n gd a t ai nt h ef a c eo f t h em o r ea n dm o r e d a t as o u r c e b yd o i n gt h i s ，w ec a nf o r e c a s tt h et r e n do f d a t ai i l o l e x a c t l ya n di m p r o v e t h ee f f i c i e n c ya c c o r d i n g l y w i t ht h ei n c r e a s i n gm a t u r i t yo ft h es t u d yo fd a t am i n i n g a l g o r i t h m , t h es t u d yo f t h ea p p l i c a t i o no f d a t am i n i n gn a t u r a l yb e c o m e st h ee m e r g i n g h o ts p o t s h o w e v e r , t h es t u d yo ft h ea p p l i c a t i o no fd a t am i n i n ga r em o s t l y c o n c e n l r a t e di nt h eo v e r a l lf r a m e w o r kc l e s i g na n d a p p l i c a t i o n sb a s e d0 1 1 l l e w t e c h n o l o g i e s ，a n ds e l d o mf o c u s e d0 1 3t h ed e s i g no ft h ei n d e p e n d e n tc o m p o n e n t s i n t h i sp a p e r , b a s e d0 1 3t h ea n a l y s i so ft h eg e n e r a lp r o c e s so fd a t am i r i i n g ，ac o m m o n f r a m e w o r kf o rd a t am i n i n gs y s t e mb a s e d0 1 3j 2 e ec o m p o n e r 吐st e c h n o l o g yi sp r o p o s e d a sf o rt h ed e s i g no f c o m p o n e n t sc o r r e s p o n d i n gt oc e r t a i nm o d u l e si nt h i sf r a m e w o r k ， t h ep a p e rp r e s e n t sal l e wd e s i g nm e t h o dw h i c hh a sb e t t e rs c a l a b i l i t ya n dl o w e r c o u p l i n gd e g r e e t h i sp a p e rm i l t o r sa n de x p a n d st h ec l e s i g nf o r m o f t h en o d eo fs p s s c l e m e n t i n e ，a n de f f e c t i v e l yd e c o m p o s ea n dr e c o n s t r u c t t h ep r o c e s so fd i g g i n g ， m a k i n gg o o dn o t e so ft h ew h o l ep r o c e s s i ne x p r e s s i o no f t h ee x c a v a t i o np r o c e s s ，b y t h ex m lm i n i n gn o d e ，t h i sp a p e re f f e c t i v e l yr e d u c e st h ec o u p l i n go f t h es y s t e m , a n d t h e n c e ，i tp r o p o s e st h eo r g a n i z a t i o nw a yb a s e d0 1 1 e x c a v a t i o nt h e m e f i n a l l y , t h e a r t i c l ea l s od e e p l yd i s c u s s e st h er e u s eofe x p e r i e n c ea n dk n o w l e d g ei nd a t am i n i n g ， a n dp u t sf o r w a r ds e v e r a lg r a d u a lt r a n s i t i o n a r yr e u s em o d e k e yw o r d s ：d a t a m i n i n g ，n o d e ，n o d el i n k ，c o m p o n e n t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫鲞态鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：勿l 遥砷 签字日期：) 叼年多月j 曰 学位论文版权使用授权书 本学位论文作者完全了解叁鲞盘堂有关保留、使用学位论文的规定。 特授权丕鲞盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：参l 逢力 导师签名： 签字日期：力帕7 年多月 1 日 签字日期： 年月日 第一章绪论 1 1 选题背景及研究意义 第一章绪论 随着信息技术的日益发展，人类己经具有了前所未有的收集数据和存储数据 的能力。数据以各种方式产生并堆积起来：企业中的关系数据库记录着企业的所 有日常业务；零售企业的p o s ( p o i n to f s a k e s ) 系统用以g b 计的数据记录人们 的每一笔购买记录；w e b 网站记录了访问者的每一次点击；人们在日常生活中 形成的大量文本( 文档、邮件) 和媒体数据( 声音和图像) ；股票交易系统每时 每刻都在生成的大量的交易信息和价格信息；气象卫星传回的图像数据规模甚至 达到t b 级。为此己经开始建立巨大的数据仓库来把所有数据进行整合并集中存 储起来。 然而面对日益膨胀的数据，人们越来越失去了对数据的理解能力巨大的 数据量使人们无从下手，大量信息在带来方便的同时也带来了一大堆问题【l 】。“数 据丰富而知识贫乏”的情况日益凸显。 随着数据库技术【2 】、人工智能f 3 1 和数理统计h 1 等技术的发展与融合，数据挖掘 ( d a t am i n i n g ，简称d m ) 技术【5 。7 1 应运而生。它通过“智能地”和“自动地”分 析数据，找到隐藏在数据表面下的知识，力图使人们摆脱“知识瓶颈”的困境。 从1 9 8 9 年数据挖掘概念提出到目前为止，数据挖掘技术在理论和应用上都 己经得到了巨大的发展。目前数据发掘能够从关系数据、对象关系数据、文本数 据、多媒体数据、时间序列、空间数据、异质数据等多种数据源中挖掘知识。数 据挖掘知识有特征、区分、关联、分类、聚集、趋势、偏差和异常监测等多种类 型。数据挖掘采用的技术包括数据库、数据仓库和o l a p 、统计、机器学习、可 视化、神经网络等不同领域的技术，并且在诸如零售、通信、银行、保险、基因 分析、股票市场分析、w e b 挖掘等不同行业得到了应用。 随着数据挖掘算法研究的日益成熟，对数据挖掘应用的研究日益成为研究的 热点。目前，已经有不少学者对数据挖掘框架及特殊领域的应用作了相关研究， 主要有基于服务的框架【8 】、面向对象的框架【9 1 、w e b 挖掘框架【1 0 1 等。此外，随着 计算机新技术的发展，在网格方面也有关于数据挖掘的诸多研究 1 l - t 4 】，在s o a ( s e r v i c e o r i e n t e da r c h i t e c t u r e ) t l s 及多级代理【1 6 】上也有较大进展。然而这些研究 均是针对数据挖掘的整个过程进行的，较少涉及到其中组件的设计思路，本文就 是由此出发进行研究的。 第一章绪论 通过对数据挖掘的通用框架进行研究，可以更加深入地了解数据挖掘的过程 及功能；文中提出的新的组件设计思路、节点化设计方式及挖掘过程的节点链表 达形式对于构建通用框架有很强的指导意义与实践意义；而且本文提出的基于挖 掘主题的组织形式及挖掘复用的过渡方式符合数据挖掘智慧金字塔的表现形式。 此外，本文所做的研究也可与其他研究成果融合在一起共同构建强健的通用的数 据挖掘工具，在实际应用上有较大的发展前景。 1 2 本文的内容及组织结构 本文共分六章，主要内容如下： 第一章绪论，阐述了选题背景及研究意义，并简述了论文的组织结构。 第二章数据挖掘技术，对数据挖掘技术进行整体性的介绍主要包括了数据挖 掘的研究内容、主要算法、处理过程及知识发现模型等。 第三章基于j 2 e e 的数据挖掘体系框架，根据j 2 e e 的组件机制，结合数据 挖掘过程提出一种体系框架，并对其各组件的功能作了较详细阐述。 第四章组件模块中的节点理论，基于体系框架及知识发现处理模型的共同点 抽取出节点这样一种可扩展的设计方式，并对节点的相关方面作了详尽的阐述。 第五章使用节点链定义数据挖掘过程，详细分析了节点链对挖掘过程的描 述，并探索性的提出挖掘主题与节点链复用的相关应用。 第六章总结与展望，首先总结全文，接着指出了进一步研究的方向。 2 第二章数据挖掘技术 第二章数据挖掘技术 2 1 数据挖掘技术基础 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数 据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的 过程町1 。其提取的知识表示为概念( c o e p t s ) 、规则( r u l e s ) 、模式( p a t t e r n s ) 等形式。 2 1 1 数据挖掘的一般流程 数据挖掘的主要过程分为下面5 个步骤j ： ( 1 ) 确定业务对象 清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步。挖掘 的最后结构是不可预测的，但要探索的问题应是有预见的，为了数据挖掘而数据 挖掘则带有盲目性，是不会成功的。 ( 2 ) 数据准备 数据的选择 搜索所有与业务对象有关的内部和外部数据信息，并从中选择出适用于数据 挖掘应用的数据。 数据的预处理 通常现实世界中的数据一般是脏的、不完整的和不一致的。因此，这一步就 是要研究数据的质量，为进一步的分析做准备，如对空缺值的处理、识别孤立点、 消除噪声数据、纠正数据中的不一致，并确定将要进行的挖掘操作的类型。 数据的转换 将数据转换成一个分析模型。这个分析模型是针对挖掘算法建立的。建立一 个真正适合挖掘算法的分析模型是数据挖掘成功的关键。该分析模型需要将数据 变换或统一成适合挖掘的形式，它往往涉及平滑、聚集、规范化等操作。 ( 3 ) 进行挖掘 对所得到的经过转换的数据进行挖掘。除了完善和选择合适的挖掘算法外， 其余一切工作都能自动地完成。这是使用智能方法提取数据模式的过程。 ( 4 ) 结果分析 第_ 章数据挖掘技术 根据某种兴趣度度量，识别表示知识的真正有趣的模式，解释并评估结果。 其使用的分析方法一般应视数据挖掘操作而定。 ( 5 ) 知识的表示 使用可视化和知识表示技术，向用户提供挖掘的知识，并将分析所得到的知 识集成到业务信息系统的组织结构中去。 2 1 2 数据挖掘的研究内容 随着d m k d 研究逐步走向深入，数据挖掘和知识发现的研究已经形成了三 根强大的技术支柱：数据库、人工智能和数理统计。目前d m k d 的主要研究内 容包括基础理论、发现算法、数据仓库、可视化技术、定性定量互换模型、知识 表示方法、发现知识的维护和再利用、半结构化和非结构化数据中的知识发现以 及网上数据挖掘等。 数据挖掘所发现的知识最常见的有以下四类： ( 1 ) 广义知识【1 9 】( g c n c r a l i z a t i o n ) 广义知识指类别特征的概括性描述知识。根据数据的微观特性发现其表征 的、带有普遍性的、较高层次概念的、中观和宏观的知识，反映同类事物共同性 质，是对数据的概括、精炼和抽象。 广义知识的发现方法和实现技术有很多，如数据立方体、面向属性的归约等。 数据立方体还有其他一些别名，如“多维数据库”、“实现视图”、“o l a p ” 等。该方法的基本思想是实现某些常用的代价较高的聚集函数的计算，诸如计数、 求和、平均、最大值等，并将这些实现视图储存在多维数据库中。既然很多聚集 函数需经常重复计算，那么在多维数据立方体中存放预先计算好的结果将能保证 快速响应，并可灵活地提供不同角度和不同抽象层次上的数据视图。另一种广义 知识发现方法是加拿大s i m o n f r a s e r 大学提出的面向属性的归约方法。这种方法 以类s q l 语言表示数据挖掘查询，收集数据庠中的相关数据集，然后在相关数 据集上应用一系列数据推广技术进行数据推广，包括属性删除、概念树提升、属 性阈值控制、计数及其他聚集函数传播等。 ( 2 ) 关联知识【2 0 】( a s s o c i a t i o n ) 它反映一个事件和其他事件之间依赖或关联的知识。如果两项或多项属性之 间存在关联，那么其中一项的属性值就可以依据其他属性值进行预测。最为著名 的关联规则发现方法是r a g r a w a l 提出的a p r i o r i 算法。关联规则的发现可分为 两步。第一步是迭代识别所有的频繁项目集，要求频繁项日集的支持率不低于用 户设定的最低值：第二步是从频繁项目集中构造可信度不低于用户设定的最低值 4 第二章数据挖掘技术 的规则。识别或发现所有频繁项目集是关联规则发现算法的核心，也是计算量最 大的部分。 ( 3 ) 分类知识( c l a s s i f i c a t i o n & c l u s t e r i n g ) 它反映同类事物共同性质的特征型知识和不同事物之间的差异型特征知识。 最为典型的分类方法是基于决策树的分类方法。它是从实例集中构造决策树，是 一种有指导的学习方法。该方法先根据训练子集( 又称为窗口) 形成决策树。如 果该树不能对所有对象给出正确的分类，那么选择一些例外加入到窗口中，重复 该过程一直到形成正确的决策集。最终结果是一棵树，其叶结点是类名，中间结 点是带有分枝的属性，该分枝对应该属性的某一可能值。最为典型的决策树学习 系统是i d 3 【2 1 1 ，它采用自项向下的回溯策略，能保证找到一个简单的树。算法 c 4 5 和c 5 o 【2 3 1 都是i d 3 的扩展，它们将分类领域从类别属性扩展到数值型属 性。 数据分类还有统计、粗糙集( r o u g hs e t ) ( 2 4 1 等方法。线性回归和线性辨别 分析是典型的统计模型。为降低决策树生成代价，人们还提出了一种区间分类器。 最近也有人研究使用神经网络方法在数据库中进行分类和规则提取。 ( 4 ) 预测型知识( p r e d i c t i o n ) 它根据时间序列型数据，由历史的和当前的数据去推测未来的数据，也可以 认为是以时间为关键属性的关联知识。 目前，时问序列预测方法有经典的统计方法、神经网络和机器学习等。1 9 6 8 年b o x 和j e n k i n s 提出了一套比较完善的时间序列建模理论和分析方法，这些经 典的数学方法通过建立随机模型，如自回归模型、自回归滑动平均模型、求和自 回归滑动平均模型和季节调整模型等，进行时间序列的预测。由于大量的时间序 列是非平稳的，其特征参数和数据分布随着时间的推移而发生变化。因此，仅仅 通过对某段历史数据的训练，建立单一的神经网络预测模型，还无法完成准确的 预测任务。为此，人们提出了基于统计学和基于精确性的再训练方法，当发现现 存预测模型不再适用于当前数据时，对模型重新训练，获得新的权重参数，建立 新的模型。也有许多系统借助并行算法的计算优势进行时间序列预测。 ( 5 ) 偏差型知识( d e v i a t i o n ) 此外，还可以发现其他类型的知识，如偏差型知识( d e v i a t i o n ) ，它是对差 异和极端特例的描述，揭示事物偏离常规的异常现象，如标准类外的特例，数据 聚类外的离群值等。所有这些知识都可以在不同的概念层次上被发现，并随着概 念层次的提升，从微观到中观、到宏观，以满足不同用户不同层次决策的需要。 第二章数据挖掘技术 2 1 3k d d 处理过程模型 ( 1 ) 多处理阶段过程模型 多处理阶段模型将数据库中的知识发现看做是一个多阶段的处理过程，在整 个知识发现的过程中包括很多处理阶段。这里我们主要介绍两种面向多阶段处理 过程的k d d 处理过程摸型。一是u s a m a m f a y y a d 等人给出的处理模型。在此 处理模型中，k d d 处理过程共分为九个处理阶段，这九个处理阶段分别是数据 准备、数据选择、数据预处理、数据缩减、k d d 目标确定、挖掘算法确定、数 据挖掘、模式解释及知识评价。 另一种是g e o r g el i j o h n 给出的，虽然在某些地方与上面给出的处理模型有 些区别，但这种区别上要表现在对整个处理过程的组织和表达力式上，在内容上 两者并没有非常本质的区别。 这两种模型都强调由数据挖掘人员和领域专家共同参与k d d 的全过程。领 域专家对该领域内需要解决的问题非常消楚，在问题的定义阶段由领域专家向数 据挖掘人员解释，数据挖掘人员将数据挖掘采用的技术及能解决问题的种类介绍 给领域专家。双方经过互相了解，对要解决的问题有一致的处理意见，包括问题 的定义及数据的处理方式。 在数据挖掘人员得到准确的问题定义和分析后，开始收集需要使用的数据， 进行再加工以使得数据更适合挖掘算法。根据解决问题的需要选择合适的挖掘算 法。提取出来的知识需要向领域专家进行解释，以对知识及整个过程进行评价。 这里主要强调k d d 需要领域专家的参与。由领域的专业知识指导数据库中 的知识发现的各个阶段，并对发现知识进行评价。这种模型主要是根据实际应用 的需要而提出的。 ( 2 ) 以用户为中心的处理模型【2 5 1 b r a c h m a n & a n a n d 从用户的角度对k d d 处理过程进行了分析。他们认为数 据库中的知识发现应该更着重于对用户进行知识发现的整个过程的支持，而不是 仅仅限于在数据挖掘的一个阶段上。通过对很多k d d 用户在实际工作中遇到的 问题的了解，他们发现用户的很人一部分工作量是与数据库的交互上。所以他们 在开发数据挖掘系统i m a c s ( i n t e r a c t i v em a r k e t i n ga n a l y s i sa n dc l a s s i f i c a t i o n s y s t e m ) 时特别强调对用户与数据库交互的支持。 用户根据数据库中的数据，提出一种假设模型，然后选择有关数据进行知识 的挖掘，并不断对模型的数据进行调整优化。该处理过程模型以用户为中心，通 过对用户在进行数据挖掘过程时的工作方式的分析，在设计k d d 系统时更注重 于对用户进行数据挖掘的全过程提供支持。 6 第= 章数据挖掘技术 2 2 数据挖掘的常用算法 数据挖掘的相关算法按照其实现的功能划分主要包括分类、聚类、关联规则、 预测等。以下主要对分类与聚类算法进行相关阐述，并借由此归结出算法的相同 之处。 2 2 1 分类分析 分类与预测是两种数据分析模式，可以用于提取描述重要数据类的模型或未 来的数据趋势。其中，分类主要适宜预测分类标号或离散值，而预测则用于建立 连续值函数模型【2 6 1 。 数据分类一般有两个基本过程。第一步，建立一个模型，描述预定的数据类 集或概念集，通过分析数据库元组来构造模型。第二步，使用模型进行相关分类， 首先要对模型的准确率进行基本评估，如果模型的准确率可以接受，就可以用该 模型来对类标号未知的数据元组进行分类操作。分类模型的构造方法有决策树、 统计方法、机器学习方法、神经网络方法等【2 7 1 。 ( 1 ) 决策树( d e c i s i o nt r e e ) 分类算法 决策树又称判定树。判定树是一个类似流程图的树结构，其中每个内部节点 表示在一个属性上的测试，每个分支代表一个测试输出，而每个树叶节点代表类 或类分布。树的最顶层节点是根节点。由判定树可以很容易得到“i f t h e n ”形 式的分类规则。方法是沿着由根节点到树叶节点的路径，路径上的每个属性值 对形成“”部分的一个合取项，树叶节点包含类预测，形成“t h e n ”部分。 一条路径创建一个规则。它采用自项向下的递归方式，判定树的最顶节点是根节 点，树的内部节点表示在一个属性上的测试，从该节点向下的每个分支代表一个 测试输出，在树的叶节点得到分类预测。从根到叶节点的一条路径就对应着一条 合取规则，整棵判定树就对应着一组析取表达式规则。判定树的优点在于它的直 观性和易理解性，判定树方法不仅能做出分类和预测，而且它的生成过程、分类、 预测以及从判定树所提取的分类规则都具有很强的可理解性。 ( 2 ) 贝叶斯( b a y e s ) 分类算法 贝叶斯分类是统计学分类方法，它是一类利用概率统计知识进行分类的算 法。在许多场合，朴素贝叶斯( n a i v e b a y e s ，简称n b ) 分类算法可以与决策树 和神经网络分类算法相媲美，该算法能运用到大型数据库中，且方法简单、分类 准确率高、速度快。由于贝叶斯定理假设一个属性值对给定类的影响独立于其它 属性的值，而此假设在实际情况中经常是不成立的，因此其分类准确率可能会下 降。为此，就出现了许多降低独立性假设的贝叶斯分类算法，如t a n ( t r e e 7 第二章数据挖掘技术 a u g m e n t e db a y e sm t w o r k ) 算法。 ( 3 ) 基于关联规则的分类算法 c b a ( c l a s s i f i c a t i o n b a s e do na s s o c i a t i o n ) 算法分两个步骤构造分类器。第 步：发现所有形如麓l 八一c i 的关联规则，即右部为类别属性值的类别关联规 则( c l a s s i f i c a t i o na s s o c i a t i o nr u b s ，c a r ) 。第二步：从已发现的c a r 中选择高 优先度的规贝i j 来覆盖训练集，也就是说，如果有多条关联规则的左部相同，而右 部为不同的类，则选择具有最高置信度的规则作为可能规则。对该过程进行分析， 不难发现，可以改进算法，从而在此步骤不需要对训练数据集进行过多的扫描。 ( 4 ) 基于数据库技术的分类算法 一 虽然数据挖掘的创始人主要是数据库领域的研究人员，然而提出的大多数算 法则没有利用数据库的相关技术。在分类算法中，致力于解决此问题的算法有 m i n d ( m i n i n gi nd a t a b a s e ) 和g a c r d b ( g r o u p i n ga n dc o u n t i n g - r e l a t i o n a l d a t a b a s e ) 。 ( 5 ) 其他分类算法 l b 算法：l b ( l a r g eb a y e s ) 算法是一种基于概率统计和关联规则的分类 算法。在算法的训练阶段，利用挖掘关联规则的a p r i o r i 算法找出训练集中所有 的频繁且有意义的项目集，存放于集合f 中。对于一个未知类别的样本a ，可以 从f 中找出包含在a 中的最长的项目集来计算a 属于各个类别的概率，并且选 择其中概率最大的类别为其分类。l b 算法的分类准确度比现有的其他分类算法 的准确度好。但该算法仍有与贝叶斯类算法和c b a 算法相同的缺点。 c a e p 算法：c a e p ( c l a s s i f i c a t i o nb ya g g r e g a t i n ge m e r g i n gp a t t e r n s ) 算法 使用项目集支持度挖掘显露模式( e m e r g i n gp a t t e r n ，简称e p ) ，再用e p 构造分 类器。一个e p 是一个项目集，其支持度由一个类到另一个类显著增加，两个支 持度的比称作e p 的增长率。 除上述多种分类算法之外，还有一些其他分类算法，比如后向传播分类、k - 最临近分类、基于案例的推理、遗传算法、粗糙集和模糊集方法等。 2 2 2 聚类分析 聚类就是按照事物的某些属性，把事物聚集成类，使类间的相似性尽可能小， 类内相似性尽可能大【2 引。聚类是一个无监督的学习过程，它同分类的根本区别在 于：分类是需要事先知道所依据的数据特征，而聚类是要找到这个数据特征。因 此，在很多应用中，聚类分析作为一种数据预处理过程，是进一步分析和处理数 据的基础。例如在商务中，聚类分析能够帮助市场分析人员从客户基本库中发现 不同的客户群，并且用购买模式来刻画不同的客户群的特征。聚类分析也能用于 第二章数据挖掘技术 分类w e b 文档来获得信息。作为数据挖掘的功能，聚类分析可以作为一个获得数 据分布情况、观察每个类的特征和对特定类进一步分析的独立工具。通过聚类， 能够识别密集和稀疏的区域，发现全局的分布模式，以及数据属性之间的相互关 系等。 把数据库中的对象分类是数据挖掘的基本操作，其准则是使属于同一类的个 体间距离尽可能小，而不同类个体间距离尽可能大，为了找到效率高、通用性强 的聚类方法人们从不同角度提出了近百种聚类方法，典型的有k i l l e a n s 方法、 k m e d o i d s 方法、c l a r a n s 方法、b i r c h 方法等口9 1 。这些算法适用于特定的问 题及用户。 ( 1 ) b i r c h 算法 b i r c h ( b a l a n c e di t e r a t i v er e d u c i n ga n dc l u s t e r i n gu s i n gh i e r a r c h i e s ) 算法使 用了一种叫做c f 树( 聚类特征树，臣o c l u s t e r i n gf e a t u r et r e e ) 的分层数据结构， 来对数据点进行动态、增量式聚类。c f 树是存储了层次聚类过程中的聚类特征 信息的一个加权平衡树，树中每个节点代表一个子聚类，并保持有一个聚类特征 向量c f 。每个聚类特征向量是一个三元组，存储了个聚类的统计信息。聚类 特征向量c f = f n ，l s ，s s l 中包含了一个聚类的三个统计信息：数据点的数目n ， 这n 个数据点的线性和l s ，以及这n 个数据点的平方和s s 。一个聚类特征树是用 于存储聚类特征c f 的平衡树，它有两个参数：每个节点的最大子节点数和每个 子聚类的最大直径。当新数据插入时，就动态地构建该树。与空间索引相似，它 也用于把新数据加入到正确的聚类当中。 聚类特征树可以动态构造，因此不要求所有数据读入内存，而可以在外存上 逐个读入。新的数据项总是插入到树中与该数据距离最近的叶子中。如果插入后 使得该叶子的直径大于类直径t ，则把该叶子节点分裂。其它叶子节点也需要检 查是否超过分枝因子来判断其分裂与否，直至该数据插入到叶子中，并且满足不 超过类直径，而每个非叶子节点的子女个数不大于分枝因子。算法还可以通过改 变类直径修改特征树大小，控制其所占的内存容量。 b i r c h 算法通过一次扫描就可以进行较好的聚类，由此可见，该算法适合于 大数据量。对于给定的m 兆内存空间，其空间复杂度为o ( m ) ，时间复杂度为 0 ( d n b l n b ( m p ) ) 。其中d 为维数，n 为节点数，p 为内存页的大小，b 为由p 决定的分枝因子。i o 花费与数据量成线性关系。b i r c h 算法只适用于类的分布 呈凸形及球形的情况，并且由于b i r c h 算法需提供正确的聚类个数和簇直径限 制，对不可视的高维数据不可行。 ( 2 ) c u r e - 算法 c u r e ( c l u s t e r i n gu s i n gr e p r e s e n t a t i v e ) 算法选择基于质心和基于代表对象 第一二章数据挖掘技术 方法之间的中间策略。它不用单个质心或对象来代表一个簇，而是选择数据空间 中固定数目的具有代表性的点。该算法先把每个数据点看成一类，然后合并距离 最近的类直至类个数为所要求的个数为止。c u 】迮算法将传统对类的表示方法进 行了改进，回避了用所有点或用中心和半径来表示一个类，而是从每一个类中抽 取固定数量、分布较好的点作为描述此类的代表点，并将这些点乘以一个适当的 收缩因子，使它们更靠近类的中心点。将一个类用代表点表示，使得类的外延可 以向非球形的形状扩展，从而可调整类的形状以表达那些非球形的类。另外，收 缩因子的使用减小了嗓音对聚类的影响。c u r e 算法采用随机抽样与分割相结合 的办法来提高算法的空间和时间效率，并且在算法中用了堆和k d 树结构来提高 算法效率。 ( 3 ) d b s c a n 算法 d b s c a n ( d e n s i t y - b a s e ds p a t i a l c l u s t e r i n g o f a p p l i c a t i o n w i t h n o i s e ) 是一个 基于高密度连接区域的密度聚类方法。该算法利用类的密度连通性可以快速发现 任意形状的类。其基本思想是：对于一个类中的每个对象，在其给定半径的领域 中包含的对象不能少于某一给定的最小数目。在d b s c a n 算法中，发现一个类的 过程是基于这样的事实：一个类能够被其中的任意一个核心对象所确定。为了发 现一个类，d b s c a n 先从对象集d 中找到任意一对象p ，并查找d e 关于半径e p s 和最小对象数m i n p t s 的从p 密度可达的所有对象。如果p 是核心对象，即半径为e p s 的p 的邻域中包含的对象不少于m i n p t s ，则根据算法，可以找到一个关于参数e p s 和m i n p t s 的类。如果p 是一个边界点，那么半径为e p s 的p 邻域包含的对象就少于 m i n p t s ，p 被暂时标注为噪声点。然后，d b s c a n 处理d 中的下一个对象。 密度可达对象的获取是通过不断执行区域查询来实现的。一个区域查询返回 指定区域中的所有对象。为了有效地执行区域查询，d b s c a n 算法使用了空间查 询r - 树结构。在进行聚类前，必须建立针对所有数据的”树。另外，d b s c a n 要求用户指定一个全局参数e p s ( 为了减少计算量，预先确定参数m i n p t s ) 。为 了确定取值，d b s c a n 计算任意对象与它的第k 个最临近的对象之间的距离。然 后，根据求得的距离由小到大排序，并绘出排序后的图，称做k d i s t 图。k d i s t 图中的横坐标表示数据对象与它的第k 个最近的对象间的距离；纵坐标为对应于 某一k d i s t 距离值的数据对象的个数。对树的建立和k d i s t 图的绘制非常消耗时 间。此外，为了得到较好的聚类结果，用户必须根据k - d i s t 图，通过试探选定一 个比较合适的e p s 值。d b s c a n 算法不进行任何的预处理而直接对整个数据集进 行聚类操作。当数据量非常大时，就必须有大内存量支持，i o 消耗也非常大。 其时间复杂度为o ( n l o g n ) ( n 为数据量) ，聚类过程的大部分时间用在区域查 询操作上。d b s c a n 算法对参数e p s 及m i n p t s t 常敏感，且这两个参数很难确定。 1 0 第二章数据挖掘技术 ( 4 ) k - p o t o t y p e s 算法 k p o t o t y p e s 算法结合了k 浅a 璐方法和根据k i n e a n s 方法改进的能够处理符 号属性的k m o d e s 方法，同k 1 i i g a l l s 方法相比，k p o t o t y p e s 算法能够处理符号属 性。 ( 5 ) c l a r a n s 算法 c l a r a n s 算法即随机搜索聚类算法，是一种分割聚类方法。它首先随机选 择一个点作为当前点，然后随机检查它周围不超过参数m a x n e i g h b o r 1 的一些邻 接点，假如找到一个比它更好的邻接点，则把它移入该邻接点，否则把该点作为 局部最小量。然后再随机选择一个点来寻找另一个局部最小量，直至所找到的局 部最小量数目达到用户要求为止。该算法要求聚类的对象必须都预先调入内存， 并且需多次扫描数据集，这对大数据量而言，无论时间复杂度还是空间复杂度都 相当大。虽通过引入r 树结构对其性能进行改善，使之能够处理基于磁盘的大型 数据库，但对树的构造和维护代价太大。该算法对脏数据和异常数据不敏感， 但对数据存放顺序异常敏感，且只能处理凸形或球形边界聚类。 ( 6 ) l i q u e 算法 c l i q u e ( c l u s t e r i n g l n q u e s t ) 算法综合了基于密度和基于网格的聚类方法， 它的中心思想是：首先，给定一个多维数据点的集合，数据点在数据空间中通常 不是均衡分布的。c l i q u e 区分空间中稀疏的和“拥挤的”区域( 或单元) ，以 发现数据集合的全局分布模式。接着，如果一个单元中包含的数据点超过了某个 输入模型参数，则该单元是密集的。在c l i q u e 中，簇定义为相连的密集单元的 最大集合。c l i q u e 算法能自动发现最高维中所存在的密集聚类：它对输入数据 元组顺序不敏感；也不需要假设( 数据集中存在) 任何特定的数据分布：它与输 入数据大小呈线性关系；并当数据维数增加时具有较好的可扩展性。但是，在追 求方法简单化的同时往往就会降低聚类的准确性。 基于上述分析，由于每个方法都有其特点和不同的适用领域，在数据挖掘中， 用户应该根据实际需要选择恰当的适合自己的聚类算法。 2 3 各类算法的共同特征 毫无疑问，当我们按照数据挖掘的功能对算法进行分类时，其同类算法间的 相似性是不容置疑的，这里主要探讨分类后的算法在设计上的相似性。 首先，在对收集的数据进行挖掘时，我们希望处理后的数据不仅能够进行预 测分析，而且也能够用于分类分析，从这个角度讲，各类算法所接受的数据输入 第二章数据挖掘技术 格式是相同的。反映到设计上就是需要保证各算法接受的数据类型是彼此一致 的，只有这样才能更好的利用数据。 其次，在各类算法的设计上，其都是遵循统一的结构设计方式，这一点可以 在第三章数据建模组件看出。这样的设计不仅能清晰明了地表述出数据挖掘的功 能，而且也能在最大程度上保证所实现的系统是可扩展的、易维护的。 再次，各类算法均或多或少的需要设定些参数值，这些参数的设定方式是 相似的，完全有理由将参数的设定归结到个模板来进行。 最后，在算法的输出上，不管使用何种挖掘算法挖掘出何种形式的知识，在 知识的表达与展示方面总是与一定的可视化组件相联系。 经过上面的分析，为之后的节点化设计方法奠定了基础。 1 2 第三章基于j 2 e e 的数据挖掘体系框架 第三章基于j 2 e e 的数据挖掘体系框架 3 1j 2 e e 组件机制介绍 3 1 1 组件的概念 所谓组件就是一些可重用的对象，开发人员可以方便地将这些对象组合到更 大的程序中而不用考虑对象本身的实现细节【3 0 。某些类型在运行时才被操作系统 处理，从而提供了额外的能力。 基于组件的开发( c o m p o n e n tb a s e dd e v e l o p m e n t ，简称c b d ) 是从第1 代 ( 2 层) 和第2 代( 3 层) 的客户机服务器发展起来的，它能改变软件开发过程中 的被动局面，使得开发者所希望的到组件市场购买所需组件，便可组装成应用程 序的梦想成为现实，这将使软件产业发生革命性变化。 c b d 与面向对象和客户服务器等有着本质的区别，它不只是一种分布计算 的新方法，而是一种广泛的体系结构。c b d 可以提高软件的可重用性，使软件 开发摆脱小作坊的工作方式，按照大规模的工业化方式进行。c b d 是软件开发 方法发展的必然结果，组件由于组件自身固有的特性，目前人们对组件这一概念 还没有一个统一的定义，下面是关于组件的一些具有代表性的观点：组件是一 个独立的可传递的操作的集合；组件是软件开发中一个可替换的软件单元，它 封装了设计决策，并作为一个大单元的一部分和其它组件组合起来；组件是由 一些对象类组成的物理意义上的包：组件是具有特定功能，能够跨越进程的边 界实现网络、语言、应用程序、开发工具和操作系统的“即插即用”的独立的 对象；组件在通常意义上是指任何可被分离出来，具有标准化的和可重用性的 公开接口的软件( 子) 系统。 3 1 2 组件技术的特点 与结构化软件开发技术相比较，组件技术有些显著的特征【3 0 1 。 ( 1 ) 真正的软件重用和高度的互操作性：组件是完成通用或特定功能的一些 可互操作的和可重用的模块，应用开发者可以利用它们在不同应用领域的知识来 自由组合生成合适的应用系统。 ( 2 ) 接口的可靠性：组件接口是不变的，一旦被发表，它们就不能被修改。 也就是说，一旦组件使用者通过某接口获得某项服务，则总可从这个接口获得此 1 3 第三章基于j 2 e e 的数据挖掘体系框架 项服务。因此组件封装后，只能通过已定义的接口来提供合理的、一致的服务。 这种接口定义的稳定性使客户应用开发者能构造出坚固的应用。 ( 3 ) 可扩充服务：每个组件都是自主的，有其独自的功能，只能通过接e l 与 外界通信。通过消息传送互相提供服务，基本组件的互操作是交互服务的。当一 个组件需要提供新的服务时，可通过增加新的接口来完成，不会影响原接口己存 在的用户。用户也可重新选择新的接口来获得服务。 ( 4 ) 具有强有力的基础设施：为了使组件有机地胶合在一起，实现无缝连接， 需要功能很强的基础设施。这些基础设施是获得重用性、可移植性和互操作性的 有效工具。这样就可知道如何找到组件提供的服务，并能在应用程序编译时进行 静态联编，用户必须在编译时就知道要访问的服务器接口，或在应用程序执行时 进行动态联编。在动态机制中，客户可以不知道可用的服务器和接口信息，而是 在运行时间内搜索可用服务器，找到服务器接口，构造请求并发送，最后收到应 答。 ( 5 ) 具有构建和胶合组件的工具：在设计与其它应用软件的接口时，利用构 建和胶合组件的工具，可以方便地增加和替换应用中的组件，充分发挥可重用的 优势，实现客户应用程序的组装和升级。 3 13j a v a b e a n s 组件技术 j a v a b e a n s 是s u n 公司针对j a v a 语言在i n t e r n e t 上潜伏问题的解决而提出的 一种新型技术。它是j a v a s o t i 对综合性软件组件技术的回答。j a v a s o f t 在j a v a b e a n s 的任务说明书中简单明白地表达了技术的要求“w r i t eo n c e ，r u na n y w h e r e ， r e u s ee v e r y w h e r