（计算机软件与理论专业论文）基于粒子群算法的模糊聚类研究.pdf

广西师范大学硕士学位论文 i 基于粒子群算法的模糊聚类研究 论文作者程灿 导师张超英 专业计算机软件与理论 研究方向数据挖掘与人工智能 年级2005 摘 要 在信息时代 大量信息给人们带来方便的同时 也带来了一系列问题 比如 信息量过大超过了人们掌握消化的能力一些信息真伪难辨给信息的正确 运用带来困难信息组织形式的不一致性增加了对信息进行有效统一处理的难 度等同时人们还意识到隐藏在这些数据后的更深层次更重要的信息能够描 述数据的整体特征可以预测发展趋势这些信息在决策生成的过程中具有重要 的参考价值面对海量数据库和大量繁杂信息人们迫切需要从中提取有价值的 知识进一步提高信息的利用率由此引发了新的研究方向那就是数据挖掘理 论和技术的研究目前数据挖掘已成为一个多学科交叉的研究领域涉及了数 据库技术人工智能机器学习统计学知识获取生物计算等许多跨行业学 科的理论和技术聚类分析是数据挖掘的一项基本任务是将物理或抽象的对象 聚集成不同的簇的过程并且要使相同簇内部的对象间尽可能相似而不同簇的 对象间差别尽可能大聚类是一个无监督的学习过程是数据挖掘中一项十分重 要的技术已经广泛应用于数据挖掘各研究领域中 传统的聚类分析是一种硬划分即每个待识别的对象只能非此即彼的被 划分到一类当中但在现实世界中有的事物没有明确的界限因此这样的硬划 分具有不合理性于是产生了基于模糊集理论的聚类算法即模糊聚类在众多 的模糊聚类算法中模糊 c - 均值算法( f c m ) 是应用较为广泛的一种算法它有着 深厚的数学基础且其收敛性已被证明同时还有着操作简单和运算速度快的特 点但是f c m 也有一些弱点如对噪声数据敏感容易陷入局部极小值算 法对初始值有较大的依赖性特别是在聚类样本数量较大的情况下这一情况更 为突出为了改善聚类算法的一些不足之处已有学者将一些全局寻优能力较强 的智能算法引入聚类过程中 如分别将遗传算法和粒子群算法引入到 k 均值算法 和模糊聚类算法中在一定程度上弥补了传统聚类算法的缺点并得到了较好的 聚类效果本文借鉴了前人的研究思想将具有全局寻优和快速收敛特点的粒子 群算法与 f c m 算法相结合不同的是本文对基本的粒子群算法进行了改进希 广西师范大学硕士学位论文 ii 望能得到更好的聚类效果在对基本粒子群算法的改进策略上本文做了如下考 虑由于基本的粒子群算法也有陷入局部极值点和在进化的后期收敛速度变慢 等缺点因此需要对它进行改进来防止粒子早熟跳出局部极值点比较有效的 方法就是增加粒子的多样性 为此 本文从两个角度来加强粒子间的多样性差异 分别是增加变异操作和将粒子群分成两个子群进行独立进化具体来说第一种 改进方法是在标准粒子群算法的基础上增加了变异操作而该变异操作内部又 包含了两种不同的变异操作这两种变异操作以不同的概率运行第二种改进方 法是将整个粒子群划分为二个数量不等的子种群 每个子种群内部又分别采用独 立的粒子群进化在对粒子群算法进行改进之后再用粒子群算法的进化过程去 替代 f c m 算法局部寻优的迭代过程其中在对粒子群算法中适应度函数的选取 上利用了 f c m 算法的聚类准则函数这样就使得整个算法过程具有很强的全局 搜索能力很大程度上改善了 f c m算法易陷入局部极小的缺陷同时相对于 f c m 算法粒子群算法对初始值不太敏感其中依据对粒子群算法的改进方法 的不同 将上述两种聚类算法分别命名为基于改进粒子群的模糊聚类算法 f c m p 和基于多种群粒子群的模糊聚类算法f c m s p 本文将这两种改进算法分别用于两个数据集中其中f c m p操作起来较简 单对第一个数据集的聚类效果较好f c m s p 在第二个数据集中也达到很好的聚 类效果但相对来讲操作过程较为复杂通过两个实验证明与基于基本遗传算 法的模糊聚类算法和基于基本粒子群算法的模糊聚类算法相比 本文中基于两种 改进粒子群算法的模糊聚类算法能够达到更好的聚类效果且加快了收敛速度 提高了工作效率在迭代的初期就能迅速找到全局最优点但是在降低出错率 方面还有待于进一步的改善 关键词 数据挖掘模糊聚类粒子群算法变异多种群 广西师范大学硕士学位论文 iii research of fuzzy clustering based on particle swarm optimization algorithm author: can cheng; tutor: chaoying zhang; specialty: computer software research direction: data mining and artificial intelligence grade: 2005 abstract in the information age, large amounts of information bring convenience to people, but it also bring about a series of problems. for example, the amout of information is too excessive to grip and digest; the true and false of some of the information is hard to distinguish, which brings difficult to correct use of information; and the inconsistency of information organization forms have increased difficulty to process information effectively and uniformly.at the same time, people realize that the concealed information of these datas which is more deep-seated and more important can describe whole characteristics of datas and forecast development trend, so the information has significant reference value in the decision-making process. in the face of vast databases and mass of miscellaneous information, people cry out to extract knowledge from them, and further improve the utilization of information, so the research about theory and technology of data mining, which is a new study direction has formed. at present, data mining has become a multi-subject crossed research field, it deal with theory and technology of database, artificial intelligence, machine learning, statistics, knowledge-acquisition, biological-computing, and many other cross-sectoral subjects. clustering analysis is a basic assignment of data mining,it is a course to partition physic or abstract objects into such clusters that objects within a cluster have high similarity in comparison to one another, but are very dissimilar to objects in other clusters. clustering is a kind of unsupervised learning, and it is a significant technology that has already apply to all study fields of data mining. conventional clustering analysis is a kind of forcible partition that every undiscriminating object can only be divided into one group or another. since some things has no specific limits in the real world, the forcible partition is unreasonable and fuzzy clustering is proposed. fuzzy c-means cluster algorithm (fcm) is a widespread and sensitive algorithm, it has many advantages such as profound mathematics base, astringency proved, work simply, and operate fast. however, it also has many shortcomings as the sensibility to noisy data, it usually leads to local minimum, and it depends on initial value, especially in the instance of large amounts 广西师范大学硕士学位论文 iv of clustering objects. to improve the deficiency of clustering algorithm, some scholars have import intelligent algorithms such as genetic algorithm and particle swarm optimization algorithm (pso) into clustering, that could make up defects of traditional clustering algorithm and have better effect. this paper has used above thinking for reference, and combined pso which is global optimum and converge fast with fcm, the pso which is modified could have better effect. due to the basic pso could get into local extremum and converge slowly at the end of evolving, it is effective to increase diversity of particles to avoid precocity and not to get into local converging. accordingly, this paper has modified pso from two aspects to intensify diversity of particles. one method is to increase mutation based on standard pso,and inside of the mutation include two different mutation operations with different probability. the other method is to partition the whole particle swarm to two subgroups which have different numbers of particles, each subgroup adopt independent particle swarm to evolve. after improved pso, the algorithms used pso instead of iterative course of fcm and used clustering rule function to form fitness function of pso. in this way, the algorithm has strong ability of global searching, it has amended the flaw of local optimizing of fcm to a great extent, and also, it has reduced the sensitivity to initial value of fcm. according to the idea upwards, this paper proposed two improved algorithms which are fuzzy clustering algorithm based on modified pso(fcmp) and fuzzy clustering algorithm based on multi-swarms pso(fcmsp). this paper has applied the modified algorithms to two groups of datas. fcmp work easily and has better effect to the first group of datas, and that fcmsp has better effect to the second group of datas but work complicatedly. the two experiments show that the effect of fuzzy clustering algorithm based on modified pso is much better compared with fuzzy clustering algorithm based on genetic algorithm and fuzzy clustering algorithm based on basic pso. they have accelerated convergence rate, advanced work efficiency, and achieved global optimum at the beginning, however, it still has to reduce rate of making mistakes. key words: data miningfuzzy clusteringparticle swarm optimization algorithm mutationmulti-group 声明 论文独创性声明 本人郑重声明 所提交的学位论文是本人在导师的指导下进行的研究工作及 取得的成果除文中已经注明引用的内容外本论文不含其他个人或其他机构已 经发表或撰写过的研究成果对本文的研究作出重要贡献的个人和集体均已在 文中以明确方式标明本人承担本声明的法律责任 研究生签名 日期 论文使用授权声明 本人完全了解广西师范大学有关保留 使用学位论文的规定 广西师范大学 中国科学技术信息研究所清华大学论文合作部有权保留本人所送交学位论文 的复印件和电子文档可以采用影印缩印或其他复制手段保存论文本人电子 文档的内容和纸质论文的内容相一致除在保密期内的保密论文外允许论文被 查阅和借阅可以公布包括刊登论文的全部或部分内容论文的公布包括 刊登授权广西师范大学学位办办理 研究生签名 日期 导 师签名 日期 第一章 绪论 1 第一章 绪 论 1.1 本文研究的背景及意义 计算机与信息技术经过半个世纪的发展 给人类社会带来了巨大的影响与变 化随着人类的活动范围逐步扩展科学技术不断进步人们能以更快速更廉价 的方式获得和存取数据这就使得数据及信息量以指数方式增长同时随着计算 机硬件和软件的飞速发展尤其是数据库技术与应用的普及人们面临的将是浩 瀚无垠的数据海洋如果没有有效的方法提取这些大量数据中有用的信息和知 识将会造成极大的浪费而目前在很多地方例如大型企业的数据库中只有 小部分数据得到了很好的应用这就使人们陷入了一个尴尬的境地即丰富的 数据和贫乏的知识如何才能从丰富的数据海洋中最大限度地提取有用的 知识 使之有效的为人类服务 已经成为广大信息技术工作者所关注的焦点之一 正是得益于目前全世界所拥有的巨大数据资源以及各行各业对将这些数据资源 转换为信息和知识的巨大需求自二十世纪 8 0年代开始数据挖掘技术逐步发 展起来 且成长迅速 数据挖掘可以视为是数据管理与分析技术的自然进化产物 简单地说数据挖掘就是从大量的数据中发现潜藏的用户感兴趣的知识和信息1 识别和分类是人类最基本的活动之一 人们通过分类来形成假设 建立概念 以及发现知识和总结规律因此分类问题的研究具有十分重要的意义聚类分 析是一种无教师监督的分类方法是用数学的方法研究分类问题的一门学科在 数据挖掘的研究中占有很大的比重它是多元分析的一个分支目前已被广泛应 用于信息检索机器学习模式识别图像处理等研究领域迄今为止聚类分 析已经经历了 2 0多年的发展历程并在很多方面得到了很好的应用但是聚类 算法仍存在许多不完善的地方为了使它得到更好的推广和应用对聚类算法进 一步的优化和改进还是非常迫切和必要的 在聚类分析中最初对对象的分类都是比较严格的是非此即彼的即 同一事物只属于所划定类别中的一类这种分类的类别界限清晰而明确属于普 通集合理论的范畴但是在实际应用中普通集合理论无法满足现实问题的分类 需要比如人的高矮胖瘦就没有明确的界限因此随着模糊集理论的提出 也就出现了模糊划分的概念用模糊集的方法来处理聚类问题就称之为模糊聚 第一章 绪论 2 类分析在模糊聚类中数据对象以一定的概率即隶属度隶属于某个类这样 的划分方式更能客观的反映现实世界从而成为聚类分析中重要的研究方向 粒子群算法是一种群智能算法它源于对鸟群捕食行为的研究一群鸟在飞 行过程中搜寻食物如果在活动区域中只有一块食物则搜寻目前离食物最近的 鸟的周围区域就是找到食物的简单而有效的策略 每只鸟所做的都是追踪它的有 限邻居 而最终得到的整体结果是整个鸟群都好像在一个中心的控制下完成相对 复杂的觅食活动 粒子群算法就是从这种模型中得到启示 并用来解决优化问题 由于该算法的收敛速度快需要设置的参数少且容易实现能有效的解决复杂 优化问题因此在函数优化模式识别神经网络等很多领域都得到了广泛的应 用粒子群算法已经显示出它强大的生命力和进一步发展的潜力并越来越受到 研究者们的关注不过对粒子群算法的应用研究虽然已进行了较长一段时间 但还存在着很大的拓展空间可以从很多方面对其进行改进 由于聚类问题在一定条件下也可归结为优化问题 因此为了克服一些传统聚 类算法易陷入局部极值搜索过程较慢等缺点有学者将智能优化算法引入聚类 分析中 如遗传算法 粒子群算法等 它们都有较强的全局寻优能力 收敛快速 将其与传统的聚类算法结合能获得更好的聚类效果 本文在拓展粒子群算法的应 用方面进行了一定的研究 将粒子群算法引用到数据挖掘中的聚类问题并在应用 过程中对粒子群算法做了一些改进提高了算法的效率因此本课题具有一定 的实用价值和理论意义 1.2 国内外研究现状及发展趋势 1.2.1 国内外研究现状 由于 数据丰富 知识贫乏 现象的出现 数据挖掘和知识发现 d a t a m i n i n g a n d k n o w l e d g e d i s c o v e r y d m k d 技术应运而生并得以蓬勃发展数据挖掘 是 k d d k n o w l e d g e d i s c o v e r y i n d a t a b a s e s 过程中最为关键的步骤在实际 应用中对数据挖掘和 k d d 这两个术语的应用往往不加区别 数据库中知识发现k d d k n o w l e d g e d i s c o v e r y i n d a t a b a s e s 一词第 一次出现是在 1 9 8 9 年 8 月在美国底特律召开的第 1 1届国际人工智能联合会 议的专题讨论会上1 9 9 1 1 9 9 3 和 1 9 9 4 年又分别举行过数据库知识发现专题讨 论会汇集来自各个领域的研究人员和应用开发者集中讨论了数据统计海量 数据分析算法知识表示知识运用等问题2从 1 9 9 5年开始每年都要举办 一次数据库知识发现国际会议规模由原来的专题研讨会发展到国际学术大会 第一章 绪论 3 研究重点也逐渐从发现方法转向到系统应用注重多种发现策略和技术的集成 以及多种学科之间的相互渗透1 9 9 9 年亚太地区在北京召开的第三届 p a k d d 会议空前热烈i e e e 的 k n o w l e d g e a n d d a t a e n g i n e e r i n g 会刊率先在 1 9 9 3 年 出版了数据库知识发现技术专刊所发表的论文代表了当时 k d d 研究的最新成 果和动态较全面的论述了 k d d 系统方法论发现结果的评价k d d 系统设计 的逻辑方法讨论了鉴于数据库的动态性冗余高噪声和不确定性k d d 系统与 其他传统的机器学习专家系统人工神经网络数理统计分析系统的联系和区 别以及相应的基本对策3此外还有这一主题的地区性国际大会相关的学 科 领 域特 别 是 机 器 学 习归 纳 逻 辑 程 序 设 计 ( i n d u c t i v e l o g i c p r o g r a m m i n g , i i p ) 医药数据处理分布式人工智能基于实例的推理 ( c a s e - b a s e d r e a s o n i n g , c b r ) 等关于 k d d 的学术交流也十分活跃4 与国外相比国内对数据挖掘的研究较晚没有形成整体力量1 9 9 3年国 家自然科学基金首次支持对该领域的研究项目目前国内的许多科研单位和高 等院校竞相开展知识发现的基础理论及其应用研究这些单位包括清华大学中 科院计算技术研究所空军第三研究所海军装备论证中心等其中北京系统 工程研究所对模糊方法在知识发现中的应用进行了较深入的研究 北京大学也在 开展对数据立方体代数的研究华中理工大学复旦大学浙江大学中国科技 大学中科院数学研究所吉林大学等单位开展了对关联规则开采算法的优化和 改造南京大学四川联合大学和上海交通大学等单位探讨研究了非结构化数 据的知识发现以及 w e b 数据挖掘5国内从事数据挖掘研究的人员主要在大学 也有部分在研究所或公司 所涉及的研究领域很多 一般集中于学习算法的研究 数据挖掘的实际应用以及有关数据挖掘理论方面的研究 目前进行的大多数研究 项目是由政府资助进行的如国家自然科学基金8 6 3 计划九五计划等 但还没有关于国内数据挖掘产品的报道6 对于数据挖掘中的聚类问题而言 传统的聚类算法大多应用在统计学和机器 学习领域而对大数据量和输入输出所需的开销问题考虑较少从而使将原有的 算法直接用于数据挖掘过程中就有些困难因此如何利用并改进传统的聚类算 法以便在大型数据库和数据仓库中发现有用的信息越来越受到人们的重视 群智能算法是通过模拟自然界生物的群体行为而产生的随机优化算法当 前 如何利用群智能算法来解决一些实际应用领域中的计算问题己成为新的研究 热点并且已经取得了突破性的进展通过对生物群体的观察和研究发现生物 群体内个体间的合作与竞争等复杂行为产生的群体智能往往能对某些特定的问 题提供高效的解决方法7典型的群智能方法有蚁群算法和粒子群算法群体智 能的研究在国外进行的比较早在 1 9 9 5 年美国的 e b e r h a t 博士和 k e n n d y 博士 第一章 绪论 4 受到鸟群觅食的启发提出了粒子群优化算法( p a r t i c l e s w a r m o p t i m i z a t i o n , p s o ) 最初的设想是仿真简单的社会系统研究并解释复杂的社会行为后来 发现粒子群算法可以用于复杂问题的求解8提出粒子群算法以来粒子群算法 已经在组合优化工程设计数据挖掘等领域取得了突出的成就受到了国际上 相关领域众多学者的关注和研究目前其研究现状大致有两个方面算法的改 进和算法的应用 越来越多的研究显示出该算法具有较强的鲁棒性和易于与其他 方法相结合的优点 在聚类方法的研究中 将智能优化算法与传统聚类算法相结合的方法已有一 些研究 例如文献9中 傅景广等人将遗传算法与传统的 k - 均值聚类算法相结合 利用遗传算法中的选择交叉和变异操作对聚类中心的编码进行优化得到了明 显优于传统 k - 均值算法的聚类划分效果在文献10中刘向东等人在基于遗传 算法的 k - 均值聚类算法基础上提出基于粒子群优化算法的聚类方法得到的 结果明显优于前者在文献11中王玲贺兴时将粒子群算法与模糊 c - 均值聚 类算法结合克服了传统模糊 c - 均值聚类算法的缺陷同时在收敛速度方面也 明显优于基于遗传算法的模糊 c - 均值聚类算法 1.2.2 发展趋势及面临的问题 虽然数据挖掘技术已经在各个方面得到了广泛的应用但是数据挖掘技术 还有很大的研究潜力以下几个方面将是未来主要的几个研究方向 1 处理更大规模的挖掘对象 2 知识的表达和解释机制即寻求更好的数据挖掘可视化方法使知识 发现的过程易于被用户理解 3 数据挖掘语言的标准化 4 网络与分布环境下的数据挖掘研究 5 多种形式的输入数据12即加强对文本图形声音视频等这些半 结构无结构的数据形式进行挖掘操作 6 知识的维护和更新 数据挖掘中的聚类算法也还存在一些需要解决的问题例如 1 算法要有可伸缩性能处理大规模的数据库对象 2 算法要能处理各种不同类型的属性 3 加强处理高维数据的能力 4 如何在没有预先设定的情况下确定最优的聚类数目 5 目前的聚类算法大多只能求得一个极小值也就是局部最优解如何 找到唯一的一个最小值还是要继续研究的问题 第一章 绪论 5 6 要有发现具有任意形状的聚类的能力 对于传统的模糊聚类算法而言则存在诸如对初始值噪声数据敏感不能 保证收敛到极小值点或只适于发现球状等凸面形状的类等问题 粒子群算法的应用范围十分广泛而且有很好的发展前景学者已对该算法 做了大量的研究 并取得很大的成效 但是还有很多问题值得进一步深入 比如 1 缺乏数学上的证明 2 粒子群的各种改进算法不具有通用性而且算法参数的设置对最终达 到的效果影响很大 3 可以将粒子群算法与进化算法如遗传算法更多的结合以达到更高 的效率和更好的效果 1.3 本文的内容安排 本文首先对数据挖掘及粒子群算法的研究现状进行了概述 接着在提出数据 挖掘基本概念的基础上对数据挖掘的过程对象任务等问题进行了详细的论 述 然后重点介绍了数据挖掘中的聚类分析技术和粒子群算法的原理及各种改进 算法在前三章综述的基础上将粒子群算法应用于聚类分析技术并进行了相 关的实验最后进行了总结及展望 本文的组织结构如下 第一章首先简要分析了本文的研究背景及意义 接着介绍了数据挖掘及粒子 群算法的国内外研究现状以及今后的发展趋势同时给出了本文的主要内容安 排 第二章首先介绍了数据挖掘的定义以及数据挖掘的过程功能分类和应 用接着详细讨论了数据挖掘中的聚类分析技术并介绍几种典型的聚类算法 第三章首先对群智能算法以及其中的蚁群算法做了简要介绍之后提出了 粒子群优化算法详细阐述了粒子群算法的原理过程及特点等方面同时介绍 了几种典型的改进算法 第四章对基于粒子群算法的聚类技术进行了研究探讨 给出了基于改进粒子 群的模糊聚类算法和基于多种群粒子群的模糊聚类算法并通过实验对比分析 两种算法相对于其它算法不仅能更快地达到收敛而且在收敛精度上也有所提 高 第五章主要是对研究工作的总结 并指出还需解决的问题和进一步的研究方 向 第二章 数据挖掘中的聚类问题 6 第二章 数据挖掘中的聚类问题 2.1 数据挖掘概述 2.1.1 数据挖掘的定义 数据挖掘是近几年来随着数据库和人工智能技术发展起来的一门新兴技术 13 数据挖掘简单地讲就是从大量数据中挖掘出有用知识数据挖掘概念的 定义描述有很多版本目前一种比较公认的版本是由 w . j . f r a w l e y g . p i a t e t s k y - s h a p i r o 等人提出的数据挖掘就是从大量的不完全的有噪声 的模糊的随机的数据中提取隐含在其中的人们事先不知道的但又是潜 在有用的知识和信息的过程14提取的知识可以表示为概念c o n c e p t s规则 r u l e s规律r e g u l a r i t i e s模式p a t t e r n s 等形式15 数据挖掘的定义可以从技术和应用两个方面来理解从技术方面来看数据 挖掘是基于数据库系统机器学习统计学神经网络等技术而发展的利用多 种分析工具从大量数据中发现数据间关系的过程从应用方面来看数据挖掘是 一个决策过程例如它可以分析企业数据库中的大量数据并根据分析结果为企 业做出正确的市场预测 数据挖掘的概念与数据库中知识发现 k d d k n o w l e d g e d i s c o v e r y i n d a t a b a s e具有很大的重合度 大部分学者认为数据挖掘和知识发现是等价概念 也有部分学者认为数据挖掘是整个知识挖掘过程中的一个主要步骤 只是由于目 前数据库领域中数据挖掘一词已被广泛使用和接受因此普遍使用数据挖 掘来表示整个知识发现过程无论是哪种解释我们在本文中都认为数据挖掘 就是数据库中知识发现 2.1.2 数据挖掘的过程 数据挖掘的整个过程可以分为三个阶段数据准备d a t a p r e p a r a t i o n 数据挖掘挖掘结果的解释与评估i n t e r p r e t a t i o n a n d e v a l u a t i o n具体过 程如下 第二章 数据挖掘中的聚类问题 7 1 数据准备 数据准备阶段的工作包括四个方面的内容数据净化数据集成数据的应 用变换和数据精简数据净化就是清除数据源中那些不完整或者不正确即冗余 的数据 比如说去掉重复的记录等 数据集成就是统一存储多个数据源中的数据 并消除其中的不一致性数据的应用变换就是用一定的方法对数据进行转换使 之适用于计算的需要数据精简就是缩减数据的数量或者减少数据的维数从 而提高数据挖掘算法的效率与质量 2 数据挖掘 数据挖掘阶段首先要确定挖掘的任务和目的 确定之后再考虑用哪种挖掘算 法决定具体算法的因素很多比如不同的数据有不同的特点因此要选择与 特点相关的算法来挖掘用户希望得到的知识类型也不同有的用户可能希望得 到容易理解的描述型知识有的用户则希望获取预测准确度高的预测型知识当 然这些都要建立在对各种挖掘算法的要求或前提假设有充分理解的基础上才 能获得好的挖掘结果 3 挖掘结果的解释与评估 数据挖掘阶段完成之后所发现的模式要经过用户的评估这时可能会存在 问题比如存在冗余或无关的模式这时要将其剔除也可能模式不满意用户要 求这时要再返回到挖掘阶段之前如重新进行数据选取数据变换设定新的 数据挖掘参数值或者换一种挖掘算法另外最后还要对发现的模式进行可视 化转换为用户易懂的表示形式 2.1.3 数据挖掘的功能 为了满足用户的期望和实际需要 一个好的数据挖掘系统应该能够同时发现 多种模式的知识和多种层次的模式知识 还应该容许用户指导挖掘有价值的模式 知识因此下面详细介绍数据挖掘的功能以及它所能挖掘的知识类型 1 概念描述 概念是对数据总体情况的概述 对含有大量数据的数据集合进行概述性的总 结并获得简明准确的描述这种描述就称为概念描述获得概念描述的方法有 两种一种是定性分析就是利用更广义的属性对所分析的数据进行概要总结 另一种是对比分析就是对所分析的两类数据进行对比并对结果进行概要性总 结 数据概要总结是利用数据描述属性中更广义的属性来对其进行归纳描述 比 如一个数据挖掘系统可以从我校的学生基本信息数据库中挖掘出研究生情况 的概要总结给出研究生概念描述其中一条获得的概念描述规则可以是7 8 % 第二章 数据挖掘中的聚类问题 8 a g e 2 2 a n d ( a g e 3 0 )这条规则表示我校百分之七十八以上的研究生年龄 都在 2 2 到 3 0 岁之间这就是一个关于我校研究生情况的概念描述 另一种是数据对比概要总结由于是对比总结因此要涉及到两类数据集 即目标数据集和对比数据集 对比概要总结就是利用描述这两类数据集特征的更 广义内容以及与对比数据集对比的情况 来对目标数据集进行概要总结并给出其 概念描述对比概要总结与前一种单一数据集概要总结使用的挖掘方法基本相 同结果输出的形式也类似只是第二种要使用对比描述来对目标数据集和对比 数据集进行比较区分比如一个数据挖掘系统可以针对我校学生基本信息数据 库中的本科学生与研究生两者的情况对研究生进行对比概要总结 并给出研究生 的对比概念描述 其中本科生数据作为对比数据集 研究生数据作为目标数据集 其中一条获得的对比概念描述规则可以是本科生8 5 % p r o j e c t = 1 )这表示相对于我 校本科生百分之八十五的人所做项目少于等于一个且没有发表论文的情况 研究 生有百分之八十的人做过一个或一个以上的项目并且发表了至少一篇论文 2 关联分析 关联分析是发现大量数据中项集之间的关联关系自从 1 9 9 3年 a g r a w a l 等 著名学者首次提出关联规则16的挖掘问题以来关联规则己成为数据库知识发 现领域的一个热点课题关联规则模式属于描述型模式发现关联规则的算法属 于无监督学习的算法目前关联规则挖掘已经成为一个具有普遍意义和实用价 值的数据挖掘技术 关联可以这样来定义若两个或多个变项的取值之间存在某种规律性则这 种规律性称为关联关联规则发现最初的形式是零售商的货篮分析即通过 发现顾客放入其货篮中的不同商品来分析顾客的购物习惯 货篮中的不同商品就 相当于是数据库中的不同项 像这样从大量的商务事务记录中找出隐藏在数据项 间的关联关系可以帮助许多商务决策的制定当然购物篮分析还只是关联规 则发现的最初形式实际上关联分析现在已经广泛应用到了很多领域 通常关联规则具有x = y 形式关联规则 x = y 表示数据库中的满足 x 中 条件的记录也一定满足y 中的条件 设 12 , , , n iiii=l是所有数据项的集合 (1) j ijn称为项 n 是项的总数 12 , , , m dttt=l是事务数据库(1) i tim 表示一条事务m 是事务的总条数 i t 是 i 的一个子集它与一个唯一的标识符 t i d相联系关联规则是一种蕴含关系x = y 其中 x i y i 且 x y = 关联分析中还有两个重要的概念支持度和可信度支持度描述了 x和 y 这两个项集在所有事务中同时出现的概率 可信度描述的是在出现项集 x 的事务 数据库 d 中项集 y 也同时出现的概率关联规则的支持度和可信度分别反映了 第二章 数据挖掘中的聚类问题 9 所发现规则的有用性和确定性一般由领域专家或用户定义两个阈值分别为最 小支持度阈值和最小可信度阈值 当挖掘出的关联规则的支持度和可信度都满足 这两个阈值时这个规则就是有效的否则就是无效的比如一个数据挖掘系 统可以在某商场的销售交易事务记录中挖掘出关联规则买牛奶的顾客中有 8 0 % 的人还会买面包如果将牛奶与面包放在一起销售将会提高它们的销量 3 分类与预测 分类与预测都属于有教师监督学习方法 即它们所使用的数据都是已知类别 归属的分类就是找出描述并区分数据类或概念的模型或函数以便能够使 用模型预测类标记未知的对象类通过分类函数也称分类器能把数据库中 的元组映射到给定类别中的某一个分类器的输入称为训练集通过分类挖 掘算法可以从训练集中获得分类模型并加以输出输出的形式主要有分类规则 决策树数学公式和神经网络预测可以利用历史数据或数据分布依据一定的模 型计算出数值数据或识别出未来分布趋势等目前时间序列预测方法有经典的 统计方法神经网络和机器学习等预测建模可以分为用于分类的预测和用于回 归的预测分类一般用于离散数值回归预测用于连续数值神经网络方法预测 既可以用于连续数值也可以用于离散数值 4 聚类分析 聚类分析属于无教师监督学习方法用于发现在数据库中未知的对象类聚 类是把整个数据库分成不同的组群划分的依据是物以类聚即考察个体或 数据对象间的相似性将满足相似性条件的个体或数据对象划分在一组内不满 足相似性条件的个体或数据对象划分在不同的组使组内的数据尽可能相似而 组间数据差别尽可能明显划分出来的组群称为类 聚类方法包括统计分析方法机器学习方法和神经网络方法等 在统计分析方法中聚类分析是基于距离的聚类如欧式距离等这种聚类 分析方法需要考察所有的个体再来决定类的划分 在机器学习中聚类是观察式学习而不是示例式学习它是根据概念描述 来确定不依赖预先定义的类和带标号的训练实例 在神经网络中自组织神经网络方法用于聚类这是一种无监督学习方法 比如 a r t 模型k o h o n e n 模型等各样本按照给定的距离阈值进行聚类 聚类分析的更多内容将在第二章的后面几节进行详细介绍 5 异类分析 异类分析也就是通常说的偏差检测对于一个数据库中的数据分类预测或 聚类分析所获得的模型不可能适合于所有的数据总有一部分不能符合这些不 符合大多数数据对象所构成规律的数据对象就被称为异类 许多数据挖掘方法在 第二章 数据挖掘中的聚类问题 10 数据准备阶段就将异类数据作为噪声排除但在有些特殊的应用场合根据异常 情况却可以得到很多有用的信息如各种商业欺诈行为的检测比如说一个给定 帐号的信用卡与平时所记录的正常付费情况相比某次的付款数额特别大就可 能发现正在进行的信用卡诈骗行为对异类数据的分析处理通常就称为异类挖 掘 6 序列模式分析 序列模式分析是从事务数据库中的所有细节数据和历史数据中通过时间序 列搜索出重复发生概率较高的模式序列模式分析和关联分析相似也是用来挖 掘数据之间的相互联系 而且也需要由用户输入最小置信度 c 和最小支持度 s 但序列模式分析侧重于分析数据之间的前后因果关系1718比如在某超市的交 易记录数据库中序列模式分析可以发现诸如顾客购买商品 a后就会购买商 品 b 这样的知识而对于股票市场的交易记录序列模式分析也可以用来发现 股票价格变化的先后关系如股票 a 上涨一定幅度后股票 b 也将上涨一定幅 度 2.1.4 数据挖掘分类19 数据挖掘是一个多学科交叉的领域 涉及到的学科主要包括数据库 统计学 机器学习和可视化几大主要技术数据库技术经过多年的发展从最初的关系数 据库发展到后来又陆续出现了面向对象数据库分布式数据库多媒体数据库 以及 w e b 数据库等数据库的应用也从一般查询到模糊查询和智能查询数据库 计算已趋向并行计算 从以上各类数据库中挖掘知识也成为数据挖掘的应用目标 之一统计学是门古老的学科现在已在社会各个方面得到广泛的应用成为社 会调查 了解民意以及制定决策的重要手段 机器学习则是人工智能的重要分支 它的很多方法和技术已经演变成数据挖掘的方法和技术 数据挖掘可以按数据库类型挖掘对象挖掘任务挖掘方法与技术等几个 方面进行分类 1 . 根据数据库的类型分类 数据挖掘系统可以按照其所挖掘的数据库类型进行分类 而数据库系统本身 就有很多不同的划分标准比如数据模型数据类型应用等因此数据挖掘系 统也可以按照数据库系统本身不同的类型来分类比如若根据数据模型分类有 关系类型事务类型面向对象类型对象关系类型和数据仓库类型等数据挖掘 系统如果根据所处理的数据类型划分有空间数据类型时序数据类型文本 类型多媒体类型和互联网挖掘等数据挖掘系统其他的系统类型还包括异构数 据挖掘系统和历史数据挖掘系统 第二章 数据挖掘中的聚类问题 11 2 . 根据所挖掘的知识类型进行分类 可根据数据挖掘系统所挖掘的多种知识类型即概念描述知识关联知识 分类知识聚类知识异类知识趋势与演化分析知识等进行划分一个成熟的 数据挖掘系统应该能够挖掘多种知识类型和多种抽象层次的知识 因此还可以根 据所挖掘知识的抽象水平对数据挖掘系统进行划分有广义知识挖掘基本层次 知识挖掘多层次知识挖掘等 3 . 根据数据挖掘的方法和技术分类 1 归纳学习类 归纳学习类又分为基于信息论方法挖掘类和基于集合论方法挖掘类 前者是 在数据库中寻找信息量大的属性来建立属性决策树 后者是对数据库中各属性的 元组集合之间的关系来建立属性间的规则各类中又包括多种方法主要用于分 类问题 2 仿生物技术类 仿生物技术类又分为神经网络方法类和遗传算法类 神经网络方法从结构上 模仿生物神经网络 是一种通过训练来学习的非线性预测模型 用于识别 预测 联想优化和聚类等实际问题遗传算法是模拟生物遗传过程中的选择交叉和 变异建立数学算法主要用于问题的优化和规则的生成 3 公式发现类 在科学实验与工程数据库中 用人工智能方法寻找和发现连续属性之间的关 系建立变