基于离散Morse理论的数据挖掘研究

基于离散Morse理论的数据挖掘研究 单位代码 10445 学 号 2009021340 分 类 号 TP181 研究生类别 全日制 硕士学位论文 论文题目 基于离散Morse 理论的数据挖掘研究 学科专业名称 管理科学与工程 申请人姓名 刘 俊 指 导 老 师 刘希玉 教授 论文提交时间 2012 年6 月7 日 独 创 声 明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得 (注:如 没有其他需要特别声明的，本栏可空)或其他教育机构的学位或证书使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者签名: 学位论文版权使用授权书 本学位论文作者完全了解 学校 有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权 学校 可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文 在解密后适用本授权书) 学位论文作者签名: 导师签字: 签字日期:20 年 月 日 签字日期:20 年 月 日 山东师范大学硕士学位 论文 目 录 摘 要.............................................................................................................................I ABSTRACT .................................................................................................................III 第一章 绪 论.................................................................................................................. 1 1.1 课题研究的背景与意 义.................................................................................. 1 1.2 国内外应用研究现 状......................................................................................2 离散Morse 理 论...................................................................................2 数据挖 掘................................................................................................3 1.3 本文研究的主要内 容......................................................................................6 数据挖掘中的聚类分析和关联规则挖 掘............................................6 离散Morse 理论综 述...........................................................................6 基于离散Morse 理论的网格聚类算 法...............................................6 基于广义离散Morse 理论的超强关联规则挖 掘...............................7 1.4 本文的组织结构及创新 点..............................................................................7 论文组织结 构........................................................................................7 论文主要创新 点....................................................................................8 第二章 数据挖掘中的聚类分析和关联规则挖 掘......................................................9 2.1 聚类算法概 述..................................................................................................9 聚类的基本概 念....................................................................................9 主要的聚类算 法.................................................................................. 12 聚类算法的研究现 状.......................................................................... 16 聚类算法的应 用.................................................................................. 18 2.2 关联规则挖掘概 述........................................................................................ 19 关联规则的基本概 念.......................................................................... 19 关联规则挖掘算 法..............................................................................20 关联规则挖掘的应 用...........................................................................23 第三章 离散Morse 理论综 述...................................................................................25 3.1 离散Morse 理论的相关概 念........................................................................25 离散结 构..............................................................................................25 山东师范大学硕士学位 论文 代数拓扑的基本概 念..........................................................................26 3.2 离散Morse 理 论...........................................................................................28 离散Morse 函 数.................................................................................28 离散梯度向量 域..................................................................................31 二者构建算法及关 系..........................................................................32 3.3 离散Morse 理论的应 用...............................................................................36 第四章 基于离散Morse 理论的网格聚类算 法.......................................................39 4.1 网格聚类概 述................................................................................................39 网格的划分方 法..................................................................................39 网格聚类方法研究现 状......................................................................39 4.2 基于离散Morse 理论的新算 法....................................................................40 算法思 想..............................................................................................41 算法描 述..............................................................................................41 算法过 程..............................................................................................42 实例说 明..............................................................................................42 4.3 实验结果和分 析............................................................................................43 实验平 台..............................................................................................43 实验数 据..............................................................................................43 实验结 果..............................................................................................43 第五章 基于广义离散Morse 理论的超强关联规则挖 掘.......................................47 5.1 问题的提 出....................................................................................................47 5.2 基于广义离散Morse 理论的新算 法...........................................................47 相关定 义..............................................................................................48 算法思 想..............................................................................................49 算法过 程..............................................................................................49 5.3 仿真实 例........................................................................................................50 第六章 总结与展 望....................................................................................................55 6.1 本文主要工作总 结.........................................................................................55 6.2 研究展 望.........................................................................................................56 山东师范大学硕士学位论 文 参考文 献......................................................................................................................57 攻读硕士学位期间发表的论文及参与的项 目..........................................................63 致 谢..........................................................................................................................64 山东师范大学硕士学位论文 插图索引 图2.1 集合 a,b,c,d,e 上的分裂聚类和凝聚聚 类.................................................. 14 图2.2 Chameleon 算法的图例说 明........................................................................ 15 图2.3 Apriori 算法过 程...........................................................................................21 图3.1 包含4 个单元的圆环体的构 建....................................................................26 图3.2 单元复形K 的哈斯 图................................................................... ................27 图3.3 单元压 缩........................................................................................................28 图3.4 定义在单元复形K 上的 函数 excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载 f ....................................................................29 图3.5 离散向量 域.................................................................................................... 32 图3.6 离散向量域中的闭合V―路径(红色部 分)............................................ 32 图3.7 离散Morse 函数构建的例 子....................................................................... 34 图3.8 一个离散梯度向量域和其对应的离散Morse 函 数................................... 36 图3.9 复杂图形可视 化............................................................................................ 37 图4.1 算法关键点图 例............................................................................................43 图4.2 数据1 聚类结 果............................................................................................44 图4.3 网格单元变小时数据1 的聚类结 果............................................................44 图4.4 数据2 聚类结 果............................................................................................45 图4.5 网格单元变小时数据2 的聚类结 果............................................................46 图5.1 事务数据库D 中候选项集的树形 图........................................................... 51 图5.2 频繁1-项集的支持度计 数........................................................................... 51 图5.3 计算各个项集的支持度计 数........................................................................ 52 图5.4 根据树形图构造的单元复形 K .................................................................... 53 图5.5 将频繁项集的支持度计数标示于单元复形K 中....................................... 53 图5.6 单元复形K 各单元的权 重................................................................... ........ 53 图5.7 广义离散梯度向量 域................................................................... ................. 54 山东师范大学硕士学位论文 基于离散Morse 理论的数据挖掘研究 摘 要 数据挖掘技术是从大量的、随机的、有噪声的、无序的、模糊的数据中提 取隐含在其中有效的、有价值的、可理解的模式，进而发现有用的或是潜在有 用的信息，并得出事件之间的趋向和关联程度，为用户求解问题提供决策支持。 在数据泛滥的今天，数据挖掘对人们提取有效信息从而进行高效的知识管理 有 着重要的意义。本文重点介绍了数据挖掘中的两个重要技术――关联规则和聚 类分析，以及著名的离散Morse 理论，并将离散Morse 理论分别应用于聚类分 析和关联规则挖掘中，提出了基于离散Morse 理论的网格聚类算法和基于广义 离散Morse 理论的强关联规则挖掘两个新的算法。 Morse 理论是分析平滑流形的拓扑结构的一种工具，最初是由Marton Morse 提出，并分析了黎曼流形上Morse 函数的临界点和流形拓扑之间的关系。随后 Forman 将离散结构引入Morse 理论形成了应用更为广泛的离散Morse 理论，它 通过对单元复形建立其离散Morse 函数或离散梯度向量域并进行分析研究，从 而得到单元复形的拓扑信息和属性。离散Morse 理论将空间图形的拓扑结构转 化为数学函数进行计算分析，是一种强大的优化工具。 本文将离散Morse 理论应用于网格聚类中，提出了一种新的网格聚类算法 ――基于离散Morse 理论的网格聚类算法。该算法首先利用网格聚类将大量数 据分散到每个小网格中，并将每个稠密网格视为一个点同时舍弃稀疏网格，然 后相互连接各个点形成单元复形，以代表稠密网格的点作为单元复形的顶点， 点与点之间的链接作为单元复形的边，随后在该单元复形上构造离散Morse 函 数从而达到聚类的目的。实验表明该算法对于形状不规则的数据集有很好的聚 类效果。 此外，本文将离散Morse 理论和关联规则的概念扩展为广义离散Morse 理 论和强关联规则，给出了广义离散Morse 理论和强关联规则的定义，并将广义 离散Morse 理论应用到强关联规则的挖掘中，得到了基于广义离散Morse 理论 的强关联规则挖掘算法。该算法将事物数据库的每个项看做一个顶点并连接顶 点形成单元复形，然后在单元复形上构造广义离散梯度，根据离散梯度中箭头 的方向来表示置信度和支持度，从而得到超强关联规则，并通过仿真实验对 该 I 山东师范大学硕士学位论文 算法进行了分析验证。新算法使得对于特殊关联规则的挖掘变得更加简单、直 观。 本文最后对全文进行了总结，列举了该文的创新点和各章的内容，同时指 出了两个新算法存在的不足之处，给出了有待进一步研究的方向。 关键词:离散Morse 理论;数据挖掘;网格聚类;关联规则 中图分类号:TP181 II 山东师范大学硕士学位论文 RESEARCH OF DATA MINING BASED ON DISCRETE MORSE THEORY ABSTRACT Data-mining is a technique which can extract some effective, valuable and understandable patterns from abundant, random, noisy, disordered and fuzzy data, and then find some information that is useful or potentially useful, obtain the time trends and connections, and provide the decision support capability about the problem solving for users. Today, data is overrunning, data-mining technology has an important significance for us to refine effective information and manage knowledge efficiently. This paper introduces two important technologies in data-mining――association rules and cluster analysis, as well as the prominent discrete Morse Theory, and proposes two new algorithms which are the grid clustering algorithm based on discrete Morse Theory and a strong association rules mining algorithm based on generalized discrete Morse Theory by using discrete Morse Theory in association rules mining and cluster analysis. Morse Theory is a tool which analyzing the topological structure of smooth manifolds, which is put forward by Marton Morse firstly and analyzed the relationship between the critical point and the topology of manifold. Then Forman introduced the discrete structure into Morse Theory and got the discrete Morse Theory, which created discrete Morse function and discrete gradient vector field on CW-complex and conducted analysis and researching, so as to get the topological information and attribute of CW-complex. Discrete Morse Theory is an powerful optimization tool, which conducts calculating and analysis by translating the topological structure of the space graphics into mathematical functions. This paper applies the discrete Morse Theory to the grid clustering, brings forward a new grid clustering algorithm――a grid clustering algorithm based on the discrete Morse Theory. Firstly, this algorithm distributes large amounts of data to III 山东师范大学硕士学位论文 each grid by using grid clustering on the dataset, and regards every dense grid as a dot and gives up the sparse grids, and then connects the dots between each other to form a CW-complex, in which the dense grids are the vertexes and the links between dots are the edges. Constructing discrete Morse function on CW-complex, so as to achieve the purpose of clustering. The experiment shows that this algorithm has better clustering results for the datasets with irregular shapes. In addition, this paper extends the discrete Morse Theory and association rule to generalized discrete Morse Theory and strong association rule, gives the definition of generalized discrete Morse Theory and strong association rule, and uses generalized discrete Morse Theory in strong association rules, getting a strong association rule mining algorithm based on generalized discrete Morse Theory. In the algorithm, every item in transaction database is seen as a vertex and connecting the vertex to form a CW-complex, then constructing the generalized discrete gradient on the CW-complex and producing strong association rules according to the direction of arrows which stand for the confidence and support among items in discrete gradient field, and verifying the algorithm by simulation experiment. The new algorithm makes it more intuitive and simple to mine special association rules. In the end, the paper gives a summary of the whole text, listing the innovation points and the contents of each chapter, pointing the inadequacies of two new algorithms, and giving the direction of further study. KEY WORDS: Discrete Morse Theory; Data mining; Grid clustering; Association rule Classification: TP181 IV 山东师范大学硕士学位论文 第一章 绪论 1.1 课题研究的背景与意义 Jhon Naisbitt 曾在他的著作中提到:“人类正被数据淹没，却饥渴于知识”。 随着信息技术的迅猛发展，尤其是Internet 技术的出现及发展，使得现代社会充 满了大量的数据，数据库应用的规模、范围和深度空前发展。面对着一个规模空 前且不断扩大的数据仓库，人们迫切的需要一种能够自动的、准确的、智能的将 这些庞大的数据转化成有用的信息和知识的技术，以便为人们的决策服务。而数 据挖掘就是这样一种技术，它产生于人们迫切的需要中，也将在充满数据的环境 中不断发展。 所谓数据挖掘，就是从大量的、随机的、有噪声的、无序的、模糊的数据中 提取隐含在其中有效的、有价值的、可理解的模式，进而发现有用的或是潜在有 [1] 用的信息，并得出事件之间的趋向和关联程度，为用户求解问题提供决策支持 。 它能够处理规模庞大的数据集，对时效性很强的应用能够提供快速的决策，而且 实时性、与数据库的同步性很强，它是多种学科和领域的融合，包括人工智能、 数据库、统计学、并行计算、可视化等，因此面临的原始数据多种多样，其处理 方法也十分丰富，挖掘结果的用途也就比较全面，如用于决策支持、信息管理、 过程控制等。正因为数据挖掘能智能化的提取繁杂数据中所包含的有用知识的强 大功能，进行挖掘所使用方法的灵活性和应用领域的广泛性，使得它成为当前的 研究热点，这也是选择数据挖掘作为论文研究的应用背景的一个重要原因。 Morse理论首先由Marton Morse提出，他分析了黎曼流形上光滑Morse 函数的 临界点和流形拓扑之间的关系，是一种非常有用的优化工具，Morse证明了一个 流形的拓扑与定义在它之上的实值平滑映射的临界点紧密相关。之后，Forman将 离散结构加入到Morse理论中，建立了离散Morse理论，离散Morse理论由于不受 空间连续性的限制，有了更为广泛的应用，成为了一种更加强有力的优化工具。 目前离散Morse理论的研究主要集中于理论的研究，应用领域主要有图像分 割、图形的可视化、海洋特征结构的提取等方面，应用领域还有待于进一步的扩 展。本文将离散Morse理论应用于数据挖掘中聚类分析和关联规则的优化问题上， 1 山东师范大学硕士学位论文 从目前来看，其他论文中还没有提出过离散Morse理论在数据挖掘中的应用，这 也正是本文的创新点所在。 1.2 国内外应用研究现状 离散Morse 理论 目前国内外对于离散Morse 理论的研究基本上处于理论层面的研究，离散 Morse 理论是一种基于数学中几何拓扑学分支的理论，从拓扑学角度对其基本理 论的研究比较多，而对其具体应用的研究则相对较少。 1 T. Lewiner 等人在文献[3]、[4]和[5]中提出了将Forman 的离散Morse 理论 应用于图形可视化领域。该应用通过对单元复形的规则成分构造超图、超树，从 而实现复形单元上离散Morse 函数和离散梯度向量域的构造，对Moebius 带、Klein 瓶等图形在空间的翻转和扭曲的可视化非常有效。文献[3]中还结合Hasse 图对离 散Morse 函数进行了分析，将离散Morse 函数用Hasse 图的形式表示，更容易表 现单元复形的结构。T.Lewiner 等人的实验结果表明离散Morse 理论对于图形的可 视化能给出一个非常好的结果。文献[6]中也对离散Morse 理论应用于图形可视化 进行了研究，它采用了拓扑结构中比较具有代表性的Moebius 带和海螺，分别通 过应用离散梯度向量域和流形可视化的方法将二者的拓扑结构直观的展现出来， 给出了可视化的结果。 2 离散Morse 理论在几何和拓扑之间起了非常重要的桥梁作用，文献[7]中利 用离散Morse 理论分析了子复形M 的规避性。它以一个日常生活中常玩的小游戏 开篇，引出了M 的规避性定义，在使得规避性可量化的过程中利用了决策树算法， 并由此产生了梯度向量域，在梯度向量域中运用离散Morse 理论的知识来实现规 避性的可量化过程，这其中介绍了较多的拓扑学知识。 3 文献[8] 中利用离散Morse 理论来进行拓扑曲面重构，它通过将曲面的几何 信息转换为边、面和体的拓扑属性，以避免出现几何二义性。 4 离散Morse 理论是与拓扑学紧密相连的，而拓扑分析在图论方面应用非常 广泛，因此离散Morse 理论在图论领域也有所应用，文献[9]中分析了离散Morse 理论的相关数学知识以及它在欧拉图、同伦映射方面的应用，这涉及到拓扑分析， 难度比较大。同时文献[10]中将拓扑分析应用于海洋特征的提取，通过构造海洋 特征函数实现水团的划分。 2 山东师范大学硕士学位论文 数据挖掘 相比于离散Morse 理论而言，对于数据挖掘的研究已经较具有系统性，对于 数据挖掘所涉及到的各项技术以及应用领域都有非常多的研究。 1、定义:由于数据挖掘的应用领域非常广泛，因此关于其定义在不同的文献 或应用领域中都有不同的说法，文献[11]中总结了几种有关数据挖掘的几种定义: Fayyad 将数据挖掘定义为一个发现数据集中模式的过程，并且这些模式是潜 在的、好用的、容易让用户理解的; Zekulin 认为数据挖掘就是要从大规模数据库中获得潜在未知的、可以操作的 信息，目的是将这些信息用于商业决策活动; Ferruzza 认为数据挖掘是一种方法，用来提取数据中潜在的未知关系; Jonn 将数据挖掘定义为有益模式的发现过程; Parsaye 则将数据挖掘看做是一个进行决策支持的过程，在这个过程中需要研 究大规模的数据库以发现有用的、潜在未知的信息。 综合来讲，数据挖掘就是从大量的、随机的、有噪声的、无序的、模糊的现 实数据中发现隐含在其中的有效的、有价值的、可理解的模式和信息，并将其应 用于决策支持的过程，本身是一个“去粗取精，提取精华”的过程。 2 、主要功能:数据挖掘的目标就是将复杂的数据约简化、有效化，从而提取 有效的模式和信息，它具有的主要功能有以下几种: 1 概念描述[11,12] 概念描述是用综合的、简洁的、准确的方式描述每个概念可能是有用的，它 可以通过数据特征化或数据区分或数据特征化和比较等方式来得到，以便能够总 体把握数据。可以利用OLAP 技术实现数据的多维查询和计算;可以使用统计学 中的传统方法来计算各个数据项的均值、方差等;还可以利用面向属性的归纳技 术实现数据的泛化等。 2 关联分析[12,13] 关联规则挖掘是指从包含大量项集的事务数据库中提取关联关系的过程。关 联规则用于展现频繁出现的属性―值之间存在的关系以及同时出现所需要的条 件，被广泛的应用于对事务数据的分析中，关联规则最初在购物篮分析中得以应 用，啤酒和尿布的例子就是一个将关联规则应用于购物篮的成功范例。 3 山东师范大学硕士学位论文 3 分类和预测[11,12] 分类和预测都是数据分析的形式，用来提取数据集中存在的重要模型，并对 未来的趋势进行预测。目前已将该方法应用于对银行客户的分析，来预测客户贷 款风险;还可以应用于对工厂机器的分类，通过对其运转情况的分析来预测容易 发生故障的机器等。 4 聚类分析[12,14] 聚类是根据相似度度量，把包含大量数据的集合划分成多个簇，处于相同簇 中的数据对象彼此之间具有最大的相似度，而处在不同簇中的数据对象彼此之间 具有最大的相异度。聚类分析是一种统计分析方法，是一种非监督的模式识别， 目前已被广泛的应用于数据分析、模式识别以及市场研究等多个领域。 5 孤立点分析[11,12] 孤立点是指数据集中存在的行为或模式与其他的数据不太一致、表现异常的 数据对象。孤立点的产生可能起源于数据度量中的某些错误或操作中产生的某些 错误，因此最小化孤立点的影响甚至排除它们是许多数据挖掘算法中所要求的， 但是另一方面，孤立点在某些应用中可能具有非常重要的意义，比如信用卡使用 数据中的孤立点可能代表了欺诈行为，而这些正是数据挖掘算法所寻找的数据。 3、数据挖掘中的常用方法 [11,15] 1 模糊集(Fuzzy Set )方法 模糊集的中心内容是不确定性，它面对的研究对象为不确定的数据，即两个 数据领域之间没有明确的分隔，利用隶属度来表示两个不同数据之间的过渡，模 糊理论本身是一种精确的、明晰的数学语言，它对不确定性进行描述。目前模糊 集方法多用于基于规则的分类领域中，利用模糊逻辑来定义边界或模糊阈值，来 得到一个较合理的结果。 [11,15] 2 粗糙集(Rough Sets )理论 粗糙集理论是Z.Pawlak教授提出来的，它是一种理论方法，用来研究不明晰 的、含糊的知识或数据的学习、总结和表示。粗糙集理论的优点在于对要处理的 数据集，不需要事先了解与问题有关的任何先验知识，对于数据约简、数据意义 评估、相关性分析等有较好的应用。 [16] 3 遗传算法 (Genetic Algorithm，GA ) 遗传算法模拟的是生物进化的过程，根据“优胜劣汰”和“种群多样性”的 4 山东师范大学硕士学位论文 原则，通过一系列的选择、交叉和变异过程最终达到最优化的目的。在遗传算法 中，首先要对染色体(待求解的问题)编码以产生初始种群，然后根据适应度函 数计算个体的适应度，根据适应度实行染色体的选择、复制、交叉和变异操作从 而产生新的个体，该过程反复进行直到求得最佳个体。数据挖掘中所利用的就是 遗传算法所具有的强大搜索能力，用来找到最优解。 [17] 4 人工神经网络(Artificial Neural Networks ，ANN ) 人工神经网络是对人类大脑系统的一阶特性的一种描述，是模仿生物神经网 络的功能结构而 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 的信息处理系统。人工神经网络是一种非线性预测模型，在 结构和功能上实现了对生物神经网络的极大模拟，可以通过不断的训练来进行学 习，主要用于数据挖掘中的聚类、分类等操作。 5 统计学方法[11] 数据挖掘中经常会用到统计学的知识，包括数理统计、回归分析、概率论、 序列分析等，这些方法在聚类分析等领域被大量的应用，丰富了数据挖掘的内容。 4 、数据挖掘的应用[12] 数据挖掘最初的目的就是面向应用，因此其应用领域非常广泛: 1 医学领域的应用 数据挖掘在医学领域的应用最瞩目的算是对 DNA 序列的研究，在过去的十 多年间，生物医学迅猛发展，对人类基因图谱的研究达到了一个新的高度。人类 基因大约有100000 个，基因中所含的核苷数量不计其数，并按一定的次序排列而 成，基因数量的庞大已经超越了传统数据分析工具的能力，因此迫切的需要一种 更为强大、更为智能化的自动数据分析工具，这种迫切的需求推动了数据挖掘技 术在医学领域中的快速发展。利用数据挖掘技术对 DNA 序列进行分析挖掘，可 以发现许多疾病基因方面的原因，对于这些疾病的预防、诊断和治疗起了极大的 推动作用，同时也有助于对预防各种疾病的新药物的研究。 2 金融领域的应用 银行和金融机构提供专业的储蓄服务、投资服务、信用服务，以及股票服务 等，其产生的数据相对而言较为可靠、完整，质量也相对较高，这使得对数据进 行系统化的分析、挖掘变得比较方便，比如为多维数据分析和挖掘构建数据仓库 等。人们可能希望按照时间、部门等各个因素查看收入和负债的变化情况，同时 5 山东师范大学硕士学位论文 给出人们感兴趣的统计信息，特征和比较分析、数据仓库、孤立点分析等在金融 数据的分析中起到重要作用;通过对客户偿还贷款的数据进行挖掘分析来预测和 评定客户的信用，对不同的客户制定不同的信用政策;根据收集的客户信息对目 标市场的客户进行分类和聚类，发现他们彼此之间的共同特征等;同时还可以为 金融犯罪案件的侦破提供帮助。 3 商业领域的应用 商业领域能够积累大量的销售数据，顾客信息(如购买历史记录、客户基本 信息记录、消费服务记录等)，数据量不断膨胀，这使得商业领域成为数据 挖掘应 用的一个重要领域，文献[18]中给出了数据挖掘在CRM 中的应用，文中利用数据 挖掘技术对客户进行分类，识别客户的级别并有选择的采取一些保留措施，分析 客户的忠诚度和盈利率，对实施个性化营销提供决策辅助等，以达到对客户的科 学管理。另外，数据挖掘还可以应用于数据仓库的设计与构造，对顾客特征、产 品销售、消费时间和地点进行多维分析。 数据挖掘在模式识别、电信业、制造业、政府、公共设施、教育、软件开发、 运输、决策分析等多个领域都有非常广泛的应用，随着技术的不断创新与进步， 数据挖掘技术会有一个非常宽广的发展前景。 1.3 本文研究的主要内容 数据挖掘中的聚类分析和关联规则挖掘 本文第二章将详细介绍数据挖掘中聚类算法和关联规则的知识，包括主要的 聚类算法，聚类算法的研究现状以及应用情况，关联规则的基本概念，关联规则 经典算法以及应用等。 离散Morse 理论综述 本文第三章详细介绍了离散Morse 理论的基本思想，并分别从离散Morse 函 数和离散梯度向量域的角度介绍了各自的基本概念以及二者之间的对应关系，分 析了单元复形的拓扑结构以及如何在拓扑结构上构造离散Morse 函数和离散梯度 向量域。最后介绍了离散Morse 理论目前的一些应用。 基于离散Morse 理论的网格聚类算法 本文第四章首先介绍了目前现有的网格聚类方法以及网格的划分方法，然后 6 山东师范大学硕士学位论文 提出了一种将离散Morse 理论应用于网格聚类的新算法。网格聚类能将大量的数 据分散到有限的网格中，那么原来对大量数据进行聚类的问题就转化为对现有的 稠密网格进行聚类的问题，聚类对象的大量减少就极大的降低了运行时间。本文 中将每个稠密网格用一个点代表，并对这些点两两之间进行连接构造出单元复形， 确定单元复形的顶点和边的权值，并在单元复形上构造离散Morse 函数和离散梯 度域，利用离散Morse 理论的知识对该单元复形进行分析，以达到聚类的目的。 新算法改进了其他聚类算法需要事先确定聚类簇的个数的缺点，同时用实验验证 了新算法的有效性。 基于广义离散Morse 理论的超强关联规则挖掘 本文第五章提出了广义离散Morse 理论和超强关联规则的新概念，并提出将 广义离散Morse 理论应用于超强关联规则的挖掘，以此产生一种关联规则挖掘新 算法。该算法在事物数据库的各个项之间构建单元复形，并在单元复形上构造广 义离散梯度来产生超强关联规则，并通过仿真实验对该算法进行了分析验证。新 算法使得对于特殊关联规则的挖掘变得更加直观、简单。 1.4 本文的组织结构及创新点 论文组织结构 本论文分为六章，各章主要内容如下: 第一章 绪论 本章主要介绍了本论文的研究背景和主要的研究内容，并对论文的整体结构 和主要的创新点做一个大体的介绍。 第二章 数据挖掘中的聚类分析和关联规则挖掘 本章简单介绍了聚类分析和关联规则的研究状况，包括涉及到的基本概念，聚 类分析和关联规则领域目前已经比较成熟的算法以及各自的应用。 第三章 离散Morse 理论综述 本章详细介绍了离散Morse 理论的基本概念，离散Morse 函数和离散梯度向 量域的概念及构建算法，以及离散Morse 理论目前的一些应用等。 第四章 基于离散Morse 理论的网格聚类算法 7 山东师范大学硕士学位论文 本章提出了该论文的第一个创新点，即把离散Morse 理论应用到网格 聚类中形 成一种新的算法，具体描述新算法的思想、过程以及实验情况分析。 第五章 基于广义离散Morse 理论的超强关联规则挖掘 本章提出了该论文的第二个创新点，即把离散Morse 理论扩展为广义离散 Morse 理论，并将其应用到强关联规则的挖掘中，本章给出扩展的广义离散Morse 理论和强关联规则的定义，并具体描述基于广义离散Morse 理论的强关联规则挖掘 的算法过程，并进行仿真实例的说明。 第六章 总结与展望 本章对全文内容进行了总结，说明了存在的缺点和不足，并明确了以后的研究 方向。 论文主要创新点 一、提出一种基于离散Morse 理论的网格聚类算法 网格聚类将大量的数据分散到有限个网格中，能大大的降低聚类对象的个数， 极大地降低了聚类算法运行的时间。同时离散Morse 理论是一种非常好的优化工 具，通过将临界点减少到可能的最小值来获取最优的拓扑结构，本文通过在数据 集上划分网格将数据集转化成单元复形的问题，在单元复形上利用离散Morse 理 论来求得最优，以此达到聚类目的。 二、提出一种基于广义离散Morse 理论挖掘超强关联规则的新算法 定义了广义离散Morse 函数、广义离散梯度和超强关联规则等新概念，将事 物数据库中的项进行频繁集过滤后反映到单元复形中，并通过在得到的单元复形 上构造广义离散梯度得到各个项之间存在的超强关联规则。 三、利用实验验证新算法的可行性和有效性 在java 平台上编辑程序验证基于离散Morse 理论的网格聚类算法的可行性和 有效性，同时通过仿真实验，以一个实例的形式分析验证基于广义离散Morse 理 论挖掘超强关联规则这种新算法的过程。 8 山东师范大学硕士学位论文 第二章 数据挖掘中的聚类分析和关联规则挖掘 数据挖掘的任务是从大量的数据中发现模式，其主要的技术包括概念描述、 分类和预测、关联规则挖掘、聚类分析以及孤立点分析等，本文中涉及到的数据 挖掘技术包括聚类分析和关联规则挖掘，并在该部分对二者的基本内容做一个详 细的介绍。 2.1 聚类算法概述 聚类分析是数据挖掘中一种很重要的技术，它将数据对象按照彼此之间的相 似性划分成若干类，并利用聚类算法发现有意义的类，以此来进行决策的制定。 在实际应用中，面对大量的数据，可以利用聚类算法发现相似的数据，并提 取出 相似数据的共同特征，为管理者制定决策提高一个较好的参考。一个好的聚类结 果能够帮助用户准确的分析数据，真正挖掘出数据中隐藏的知识，帮助用户做出 正确的决策，而一个糟糕的聚类结果却正好相反，因此对于聚类算法的研究引起 了许多专家学者的兴趣，使得聚类分析成为一个热门的研究领域。 聚类的基本概念 1、聚类的定义 由于聚类分析是一种实际应用技术，所以它的定义与待处理数据的类型有关， [19] 目前聚类的定义根据不同的模型思想存在多种说法 : 1 基于距离的定义:聚类是将数据对象划分为不同的集合，使得同一集合内 的元素之间的最大距离小于不同集合中元素之间的最小距离。该方法对于复杂数 据的聚类能力较弱。 2 基于质心的定义:在要聚类的数据对象中事先确定多个质心，根据质心对 数据对象划分聚类，计算每个数据对象与质心的距离，并将其划分到与其具有最 小距离的质心所代表的数据集合中，最终形成聚类。 [20] 3 基于密度的定义 :一个关于参数ε和MinPts 的聚类C 是数据集合D 的 非空子集，它满足两个条件:对于任意的p 、q ，如果p ?C 且q 是从p 关于参数 ε和MinPts 密度可达的，那么q ?C ;对于任意的p 、q ?C，p 到q 是关于参数ε 和MinPts 密度连通的。也就是说，聚类是数据空间中由稀疏空间隔开的稠密区域 9 山东师范大学硕士学位论文 的集合。 4 基于相似度的定义:聚类是指将大量的数据对象划分到多个集合中，使得 集合内元素的相似性最大化，而集合间元素的相似性最小化。这里的相似性度量 通过相似系数确定，不同数据元素之间的相似系数大于相似阈值，则划分到同一 集合中，反之划分到不同集合中。 2 、对聚类分析算法的典型要求 作为数据挖掘中一个重要的技术，对聚类分析算法的研究已经成了一个非常 [12] 活跃的课题。数据挖掘对于聚类分析算法的典型要求有以下几方面 : 1 可伸缩性:有许多的聚类算法对于含有较少数量数据对象的数据集能够得 到较好的聚类结果，但是现代社会中存在的数据集都是含有成千上百万个数据对 象的大规模数据集，虽然可以通过抽样从中获得有代表性的较小数据集，但是对 样本的聚类会对真实的结果造成不可测量的偏差甚至错误，因此聚类算法需要具 有很高的可伸缩性。 2 可解释性和可用性:实际应用中，聚类结果所面对的对象是普通用户，因 此需要聚类结果是易解释的且易理解的，这样才能有效的应用于实践，因此要求 好的聚类算法具有较好的可解释性和可用性。 3 能够处理不同类型的数据:数据类型有多种，如标称变量、二元变量、序 数变量等，实际应用中所面临的数据可能有多种类型，因此要求一个好的聚类算 法可以对各种类型的数据对象执行聚类，而不是只能处理一种类型的数据。 4 对高维数据的处理能力:聚类对象的维度或属性可能很多，而且在高维空 间中的分布可能存在多种可能，有些聚类算法能够很好的处理低维数据，但是在 面对高维复杂数据时可能会得到扭曲的聚类结果，不能正确实现对高维数据的分 析，因此提高对高维数据的聚类能力是开发聚类算法要考虑的一个重要问题。 5 能够识别任意形状的簇:很多聚类算法在聚类时使用基于 Euclidean 距离 或Manhattan 距离的相似性度量，由于这两种度量方法存在的局限性使得这些聚 类算法只能发现具有规则形状的簇，但是实际生活中存在的簇可能是任意形状的， 如环形，因此能够识别任意形状簇是聚类算法的一个必要要求。 6 弱化对数据输入顺序的敏感性:一个好的聚类算法应该对聚类对象的输入 顺序具有较低的敏感性，同一组数据以不同的顺序输入时应该得到相同的或相似 10 山东师范大学硕士学位论文 的聚类结果。 7 对输入参数的弱依赖性:许多聚类算法在执行聚类之前要求用户输入必要 的参数，如簇的数目等，且聚类结果对这些输入参数具有很强的敏感性。由于用 户在面对大规模数据集时无法准确预测这些参数，使得聚类结果增大了对人 为因 素的依赖，导致聚类结果与实际情况存在一定的偏差，因此弱化对输入参数的依 赖性是聚类算法要考虑的一个重要方面。 8 噪声数据的处理能力:实际应用中的数据包含了大量的噪音数据(如异常 数据和错误数据)，如果聚类算法没有很好的噪音数据处理能力，可能会因为这些 数据的存在而不能得到想要的或正确的聚类结果。 9 满足约束的能力:聚类算法在实际应用中可能会受到一些实际问题的约 束，如为特定数目的地铁站选择位置时需要考虑城市的规划等，因此如何既能在 理论上满足最优的聚类结果又满足不可抗力的约束条件是开发聚类算法时 要考虑 的一个要求。 3、聚类的数据结构 本节中主要介绍聚类中比较有代表性的数据结构:对象-属性结构和对 象-对 象结构。 对象-属性结构:假设数据库中包含N 个数据对象，每个数据对象具 有P 个 属性，则该数据结构可以看成是一个N*P 维的矩阵: ?x11 x12 ? x1P ? ? ? x x ? x ? 21 22 2P ? ? ? ? ? ? ? ? ? x x ? x ? N 1 N 2 NP ? 其中 xij i 0,1, ?, N ,j 0,1, ?,P 表示第 i 个对象的第 j 个属性，向量 xi xi1,xi2 ,?,xiP 表示第i 个对象，xj x1j ,x2j ,?,xNj 表示具有属性j 的所有对 象。 对象-对象结构:该结构以矩阵的形式描述，存储的是包含 N 个对象的数据 库中每两个对象之间的相似性，以N*N 矩阵的形式表示: 11 山东师范大学硕士学位论文 ? 0 ? ? ? ?d 2,1 0 ? ? ? ? ? ? ? ? ?d N ,1 d N ,2 ? 0? d i, i 0 其中， 表示对象i 和对象j 之间的相 似性， d i,j i 0,1,?,N ,j 0,1，?,N 表示对象i 和其本身完全相同。 主要的聚类算法 韩家炜教授在其《数据挖掘:概念与技术》一书中总结了主要的聚类算法， 主要可以分为基于划分的方法、基于层次的方法、基于密度的方法、基于网格的 [12] 方法、基于模型的方法 。 1、基于划分的方法 给定包含N个对象的数据库和结果簇的数目k ，基于划分的方法将这N个对象 划分为k个集合，使得每个集合都必须包含对象而且每个对象只能存在于一个集合 中。k-means算法和k-medoids算法是基于划分的方法中的代表性算法，应用比较广 泛。 k-means算法的基本思想是首先在包含有N个数据对象的集合中任意选择k个 数据作为初始的聚类中心，依照设定的距离度量计算每个数据对象和这k个初始聚 类中心之间的距离，并按照最小距离原则将数据对象划分到k个聚类中心代表的簇 中，重新计算各个簇的平均值以确定新的聚类中心，然后不断重复执行该过程。 该算法的结束条件是平均值的变动最小时结束迭代。k-means算法的过程如 下: 输入:包含N个对象的数据库、指定的初始簇中心数k 输出:k个聚类数据集合 方法:1)任意选择k个数据对象作为初始的聚类中心; 2 )计算每个数据对象与k个初始聚类中心的距离，并根据最小距离原则 分配对象; 3 )重新计算k个簇的平均值以确定新的聚类中心; 4 若新的聚类中心变化不大，则结束该过程，若变化很大，则转2 。 k-means算法是一种非常重要的划分方法，对一般的数据集能产生很好的聚类 结果。但是该算法对噪音数据很敏感，当数据集中存在较多的孤立点时，容 易出 12 山东师范大学硕士学位论文 现对数据密集区的偏离，从而出现聚类结果的误差。另外初始簇中心需要事先指 定，使得该算法对聚类结果的控制性较弱。 由于k-means方法存在的缺点，目前有许多学者致力于对k-means算法的改进: 文献[21]中选择密度法进行初始簇中心的选择，在选择初始簇中心时不只考虑对象 之间的距离，同时也考虑了聚类对象的密度;文献[22]中提出了一种新的聚类算法 DBE Dark Block Extraction ，用于实现无 标识 采样口标识规范化 下载危险废物标识 下载医疗器械外包装标识图下载科目一标识图大全免费下载产品包装标识下载 数据集聚类结果簇数目的自动确定， 该算法是在现存算法VAT 的基础上借助图像知识实现的。 k-medoids算法与k-means算法类似，但是它用数据集中一个实际存在的数据对 象代替了k-means算法中虚拟存在的平均值点，因此相比k-means算法降低了对噪音 数据的敏感性，但是该算法的运行时间过长，不太适合对大型数据集进行聚类。 比较常用的k-medoids算法有PAM ，CLARA,CLARANS等。 2 、基于层次的方法 基于层次的聚类方法的基本思想是将聚类对象映射为一个树形结构，单个数 据对象作为树形结构的叶节点，所有数据对象的集合作为树形结构的根节点，对 数据对象聚类的每个阶段所出现的不同的聚类簇作为树形结构的中间节点。根据 聚类过程是从根节点向叶节点执行还是从叶节点向根节点执行，层次聚类算法可 以分为分裂聚类和凝聚聚类。 分裂聚类:从树形结构的根节点向叶节点执行的聚类。将所有聚类对象的集 合看成初始的簇，在预先设定的分解规则下对初始簇进行划分，当达到终止条件 (如预先指定的结果簇数目或满足限制条件)时，分裂聚类过程结束。 凝聚聚类:从树形结构的叶节点向根节点执行的聚类。首先将每一个聚类对 象看成一个簇，然后根据每两个簇之间的相似度进行合并，将具有最大相似度的 簇合并在一起，当达到终止条件(如预先指定的结果簇数目或满足限制条件)时， 凝聚聚类过程结束。 图2.1描述了在集合 a,b,c,d,e 上的分裂聚类和凝聚聚类: 13 山东师范大学硕士学位论文 分裂聚类 a a,b b a,b,c,d,e c c,d d c,d,e e 凝聚聚类 图2.1 集合 a,b,c,d,e 上的分裂聚类和凝 聚聚类 层次聚类的过程中常用的相似度度量有以下几种: 1 最小距离:d C , C min p ?p ' min i j p ?C ,p '?C i j 2 最大距离:d C , C p ?p ' i j p ?C ,p '?C i j 3 平均值的距离:d C , C m ?m mean i j i j 4 平均距离:d C , C ? ? p ?p ' avg i j p ?Ci p '?Cj 目前常用的基于层次的聚类算法主要有Chameleon 、BIRCH 、CURE 、 ROCK 等。 [23] Chameleon 变色龙 算法 是一种利用动态模型的层次聚类算法，它是基于 CURE和ROCK两种算法的缺点而产生的，CURE算法忽略了不同簇中对象之间的 互连性信息，而ROCK算法强调了对象之间的互连性却忽略了对象间的近似度信 息，因此Chameleon算法将二者结合起来，既考虑了对象间的互连性信息，又考虑 了对象间的近似度信息，综合了二者的优点，改进了缺点。Chameleon算法在k最 近邻图上执行聚类，图中每个点表示一个数据对象，带权重的边表示两个数据对 象之间的相似度，计算相似度时同时考虑了簇间的相对互连性和相对近似性。 Chameleon算法通过一个两阶段的算法来发现聚类，首先该算法利用图划分算法对 数据集合进行划分，将其聚类成几个相对小的子簇，然后利用一种算法通过反复 的合并这些子簇来得到真正的簇。图2.2展示了Chameleon算法的两个阶段。 14 山东师范大学硕士学位论文 数据集 K-最近邻图 最终簇 构筑一个稀疏图 划分图 合并划分 图2.2 Chameleon 算法的图例说明 从Chameleon算法的过程可以看出，该算法对任意形状的簇有较好的聚类结 果。 对于层次聚类算法也出现了一些新算法，文献[24]中提出了一种基于分裂和凝 聚的最小生成树法，该方法中利用最小生成树和基于最小生成树的图来指导分裂 和凝聚的过程。在分裂阶段，在基于最小生成树的图中具有较高度的顶点作为初 始聚类中心，然后利用k-means方法对数据集进行划分;在合并阶段，对生成的子 图对进行过滤并合并那些相邻的子图。该方法只需要簇的数目一个参数，这是其 优点所在。 3、基于密度的方法 大部分的聚类算法都是利用数据对象之间的距离来度量相似度，而基于密度 的聚类算法则利用密度代替距离来计算相似度，其基本思想是将数据分布空间中 的高密度区域看作簇，簇与簇之间分布的是低密度区域，并通过这些低密度区域 将高密度区域划分开。比较常用的密度聚类算法有OPTICS、DBSCAN 、 DENCLUE 等。 DBSCAN Density-Based Spatial Clustering of Applications with Noise 算法是一 [25] 种比较有代表性的密度聚类算法，算法的步骤 如下:首先选择一个核心对象p ， 检查其他对象是否是关于核心对象p直接密度可达的，如果是，则将该对象归入核 心对象p所代表的簇中，反复执行该过程直到没有对象到核心对象p是直接密度可 达的。其中核心对象是指在给定的领域内对象个数要大于指定的最小阈值;直接 密度可达是指如果一个对象在核心对象的领域内，则该对象到核心对象是密度可 达的。 DBSCAN算法能够发现任意形状的簇，但是该算法对密度阈值和邻域等较多的 输入参数具有较大的依赖性，文献[25]中对该算法进行了改进，利用 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 来确定密 度阈值等，大大减小了该算法聚类结果的不确定性。文献[26]提出了基于密度的最 15 山东师范大学硕士学位论文 小生成树聚类分析算法，通过构造、划分最小生成树实现数据空间的划分，利用 子树的特点产生密度参数，解决了对密度阈值和邻域等输入参数的依赖性。文献[27] 中提出了一个对空间数据集执行密度聚类的算法GDBSCAN且给出了其在地球科 学、分子生物学、天文学、地理学等四个方面的应用。文献[28]中提出了一种对多 边形进行密度聚类的算法。 4 、基于网格的方法 基于网格的聚类算法是将数据空间划分成一个网格结构，将数据分散到不同 的网格单元中，然后根据预设的密度阈值区分稠密网格单元和稀疏网格单元，并 把网格单元视为聚类对象进行聚类的算法。由于该算法将网格单元作为聚类对象， 因此大大减少了聚类对象的数量，对大规模数据集有较快的处理速度，极大的提 高了聚类算法的效率。STING算法、CLIQUE算法、WaveCluster算法是比较有代表 性的算法。 5、基于模型的方法 基于模型的聚类算法的基本点在于寻找数据对预先给定模型的最佳拟合，以 加强算法中数学模型的力量。主要的基于模型的聚类算法有人工神经网络方法、 有竞争学习方法、EM 方法等。 聚类算法的研究现状 聚类分析是数据挖掘中的一个重要技术，经过以上分析可以知道聚类分析发 展到现在已经成为一个庞大的体系，产生了很多聚类算法，但是大多数的聚类算 法都存在缺陷，如何改善聚类算法，提高算法性能，尽可能的弥补算法本身存在 的缺陷成为聚类分析领域的研究热点。 目前对聚类算法研究的努力方向有以下几点: 1、弱化对输入参数的依赖性 大多数的聚类算法都要求用户在执行聚类之前输入结果簇的数目，在执行密 度聚类或网格聚类时要求输入预先设定的密度阈值、邻域、网格单元大小等参数， 用户在没有任何先验知识的情况下确定这些参数是困难的，而且妨碍了聚类算法 对聚类结果的控制能力。 鉴于这种问题的存在，出现了很多解决办法:文献[29]提出了一种能够选择聚 类数目的凝聚模糊k均值聚类方法，该算法是对 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 模糊k均值算法的扩展，通过 16 山东师范大学硕士学位论文 对对象函数施加一个惩罚因子来减弱聚类过程对初始簇中心的敏感性，对不同的 初始聚类中心的集合产生更加一致的聚类结果;文献[22]提出的算法实现了无标识 数据集簇数目的自动确定;文献[30]对自组织特征映射聚类算法进行了改进，提出 了结构自适应的聚类神经网络，该方法不需要事先确定聚类数和输出神经元个数， 通过反复训练神经网络并依据聚类准则曲线函数来自动确定聚类数。 2 、增强对大数据集和高维数据集的处理能力 有些聚类算法在执行聚类时有较好的性能，但是良好的性能只适用于小数据 集或低维数据集，当数据集的规模增大或结构变得更加复杂时，算法的处理 性能 就会出现极大的下滑，比如k-medoids方法。 针对这个问题有不少学者对其进行了改善:文献[31]提出了一种使用加权的相 异度度量的聚类最优化方法，该算法中对聚类对象使用加权的相异度度量，并在 k-means-type算法的框架下为每个簇的每个属性产生一个权值，除了找出数据对象 所属的聚类，加权的相异度度量还给出了每个聚类的重要属性集，在区分不同聚 类中对象时利用带高权的属性集来描述具有最高能量的属性集，该算法能够对大 规模数据集进行有效的聚类;文献[32]中提出了一种映射聚类算法来解决高维数据 集的聚类问题，该算法首先通过检测数据空间的稠密和稀疏区域以及数据在属性 空间的位置进行属性相关性分析，然后消除孤立点，发现处于不同子空间的簇。 该算法是基于k-means算法的，对于覆盖在高维空间中的低维映射聚类的检测是有 效的，同时也避免了在高维空间中进行距离的计算。 3、对聚类质量的改善 聚类质量是聚类技术应用中很重要的问题，所有聚类算法的目标都是要得到 一个好的聚类结果，因此对高质量聚类结果的追求一直是聚类算法研究努力的方 向。 文献[33]提出了一种基于决策理论模糊集模型的有效的聚类质量指标 的算法， 基于决策理论，模糊聚类有效性指数可以看做是利用一个聚类算法聚集数据对象 的全部风险的函数，可以利用该指标来测度聚类算法的质量，同时该指标也可以 用于模糊聚类或明确聚类;文献[34]提出了基于点对称的聚类技术，该方法能够自 动的评价聚类数和对数据集的划分。 4 、增强聚类算法在实际应用中的能力 17 山东师范大学硕士学位论文 目前不少聚类算法只是进行了一个理论上的证明，在算法中加了很多限制条 件，如较少的孤立点等，但实际应用中的数据集是复杂的，存在各种可能和各种 实际问题的限制，因此增强聚类算法对实际应用问题的处理性能是聚类算法研究 的最终归宿。 5、将智能算法引入聚类分析中 智能算法是非常好的优化算法，将智能算法引入聚类分析中以优化聚类算法 的性能是当前的一个研究热点，遗传算法、蚁群算法、模拟退火算法、微粒群算 法、DNA计算等智能算法的引入，产生了大量新的聚类算法，极大的推动了聚类 算法的发展。 聚类算法的应用 虽然聚类算法在应用于实际问题时存在一些限制，但是作为最重要的数据挖 掘工具，聚类算法已经在不少问题中进行了应用，而且取得了较好的效果。 聚类分析最重要的一个应用就是在客户关系管理中的应用，文献[35]、[36]、 [37]、[38]都介绍了聚类分析在客户关系管理中的重要作用。企业中所存储的客户 数据是一个大型的数据库，对客户数据进行特征分析与整理等预处理，并将其作 为客户数据的属性，这样客户数据库就成为一个庞大的数据集，利用聚类算法对 该数据集进行聚类操作，可以识别出具有相同特征的客户，同时也便于将客户按 照他们的消费特征进行分类，对不同的客户群实行差异化管理，使客户能够容易 的实现各取所需，增加客户满意度，极大的提升客户的忠诚度;在农业工程中， 聚类可以用来对耕地进行评价:在决策树理论的支持下，利用聚类算法对影响土 [39] 地的各种因子进行分析，以便对耕地进行评价 ;在社会管理学方面，聚类分析 [40] 可以用于对居民的消费结构进行统计分析 ;在设计学中，可以通过分析消费者 的感性要求和产品设计要求实现产品的感性设计，使其最大程度地满足消费者的 [41] 要求 ;在互联网中，可以实现对网页或文本的分类，实现从海量网页中提取信 [42] 息的快速性和准确性 。 通过以上几个例子可以看出，聚类算法的应用领域非常广泛，已经深入到了 生活的方方面面，因此努力改善聚类算法的性能，提出新算法拓宽聚类的应用领 域，具有非常重要的意义。 18 山东师范大学硕士学位论文 2.2 关联规则挖掘概述 关联规则挖掘是数据挖掘中的一项重要技术，它通过分析项集的特征和彼此 之间存在的关系来提取大型数据库中存在的相关的、潜在的关联规则，有效的发 现两个看似毫无联系的事物之间存在的正相关关系并将其应用于生产决策，这就 是发展关联规则挖掘的动力所在。应用关联规则分析的一个著名成功案例就是啤 酒和尿布的例子。 关联规则的基本概念 关联规则挖掘是用来发现特定记录中各项目之间存在的关系，通过研究各项 目的特征以及一起发生的频率等来推断它们彼此之间可能存在的相关关系，发现 潜在的有价值的模式的过程。这种潜在的有价值的模式就是关联规则，其具体的 定义如下: 关联规则 Association rules [43] 项集I i , i , ?, i 是包含 m 个不同项的集 1 2 m 合;事务数据库D 是一组事务的集合，其中每个事务T 包含一个项集I 使得T ?I 。 给定一个项集X ?I ，当且仅当X ?T 时事务 T 包含X 。关联规则就是一个蕴涵 式X ?Y ，其中X ?I ，Y ?I 且X ?Y ?，其中X 、Y 分别称为关联规则的蕴 涵前式和蕴涵后式。 关联规则一个著名的例子就是购买了汉堡包的顾客中有90%的人也购买了可 乐，这里90%是该关联规则的置信度，意味着包含X 汉堡包 的事务中有90%也 [44] 包含 Y 可乐 。可以看出，支持度和置信度 是描述关联规则不可缺少的重要概 念: 支持度 Support 事务数据库D 中包含X 且包含Y 的事务的概率，由以下 公式计算: Support X ?Y Support X ?Y 置信度 Confidence 事务数据库D 中同时包含X 和Y 的事务在包含X 的事 务中的占比，由以下公式计算: Confidence X ?Y Support X ?Y Support X 19 山东师范大学硕士学位论文 公式中Support * 表示事务数据库D 中项集*的支持度，是D 中包含*的事务的概 率。 从支持度和置信度的定义可以看出，关联规则的支持度度量了项集之间关联 关系的权数，而关联规则的置信度则度量了项集之间关联关系的关联程度。挖掘 关联规则的过程就是要发现所有支持度不小于最小支持度阈值，置信度不小 于最 小置信度阈值的关联规则，即满足以下条件的关联规则: Support X ?Y ?minsupport Confidence X ?Y ?minconfidence [45] 与关联规则挖掘有关的其他概念 : 候选n-项集:如果项集X 中包含n 个项，则称项集X 为候选n-项集， 记为 C ; n 频繁 n-项集:支持度大于最小支持度阈值的 n-项集称为频繁 n-项集， 记为 L ; n 关联规则挖掘算法 [46] 由以上关联规则的基本概念可以看出，挖掘关联规则需要经历两个阶段 : 首先找出事务数据库中所有支持度大于最小支持度阈值的频繁n-项集，然后从频 繁n-项集中找出所有置信度大于最小置信度阈值的规则，即事务数据库中存在的 关联规则。由于第一阶段是提高关联规则挖掘速度的关键，因此目前绝大多数算 法都致力于对第一阶段的研究，这也是提高算法性能的突破口。目前最具有 代表 性的关联规