cabpm基于模式匹配的聚类算法

《cabpm基于模式匹配的聚类算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、http://www.paper.edu.cnCABPM:基于模式匹配的聚类算法方应飞北京邮电大学计算机科学与技术学院，北京(100876)E-mail：jiajiafyf0775@sina.com摘要：本文通过研究一种快速前向模式匹配算法Rete算法，从一个新的角度重新分析设计了聚类算法－基于模式匹配的聚类算法（AClusteringAlgorithmBasedonPatternMatching）。该算法通过对原始Rete算法概念的修改与拓展，详细描述了数据对象在CABPM算法中的表现形式和聚类完成过程，并给出了具体的算法描述，为传统聚类算法的优化改进提供了一个新的思路。关键词：Ret

2、e算法模式匹配聚类算法中图分类号：TP3111.引言数据挖掘的主要任务是从海量数据中找出有效、实用的数据，并分析数据间的相关性。[1]聚类(clustering)是数据挖掘任务的重要实现手段，其主要目标是将数据对象集划分为若干组(class)或类(cluster)，并使得同一个组内的数据对象具有较高的相似度，而不同组中的数据对象则是相似度较低。相似度高低的度量是基于数据对象描述的取值来确定的，通常利用(各对象间)距离来进行描述。[2]目前，聚类方法代表性算法有分层方法(hierarchicalmethod)、划分方法(partitioningmethod)、基于密度分布函数的方法(den

3、sity-basedmethod)、基于网络方法(grid-basedmethod)和基于模型的方法(model-basedmethod)。绝大部划分方法都是基于对象之间的距离进行聚类，这样的方法或者不能发现任意形状的簇(只能发现球状的簇，而不能发现其他形状的簇)，或者对输入参数和数据对象输入顺序敏感。本文从研究Rete算法的基本思想着手，根据Rete网络算法前项快速匹配的特点，结合聚类分析的基本要求，通过构建基于模式的匹配网络，将聚类分析过程描述为模式的匹配过程，并定义数据对象和模式间的相似度（μ）来发现聚簇，从而完成聚类过程。由于算法避免了对数据对象的反复遍历并基于模式定义之上，因而

4、算法具有较好的性能和分类能力。文章较为详细的讨论了Rete网络的构建过程，并在对Rete网络基本概念的拓展之上讨论了如何使数据对象在Rete网络中的流动来完成数据对象的聚类过程。在文章的最后给出了算法的具体描述和性能评价。2.Rete算法的基本理论和概念拓展为了达到通过构建Rete匹配网络来进行数据对象的模式匹配实现聚类过程，需要从下面两个方面来考虑，并分别在接下来的两个章节中讨论：1）如何构建Rete匹配网络；2）数据对象在Rete匹配网络上的表现形式及聚簇的产生方式；2.1Rete算法基本概念[3]Rete算法是美国卡耐基·梅隆大学的CharlesL.Forgy为解决商务规则引擎于1

5、982年提出的一种前项推理（Forward-Chaining）算法，其核心思想是将分离的匹配项根据内容动态构造有效的辨别网络，以达到显著降低计算量的效果。为了在后面的聚类分析中引用算法，对算法中的有关概念做了重新定义。-1-http://www.paper.edu.cn定义2.1.1(事实：Fact）数据对象及对象属性之间的多元关系，一个事实可以用一个三元组来表示：F：(Data，Attributes，Values)其中Data表示数据对象集，有若干个数据对象组成，Attributes是Data中的属性集，Values是属性集对应的值的集合；定义2.1.2(规则：Rule）由条件和结论构

6、成的推理语句，具有可表达能力、可理解性和可访问性。在聚类分析中“条件”就是数据对象满足某一分类的约束属性，“结论”就是将[3]事实加入该分类。一条规则可以用一个二元组来表示：R：（LHS，RHS）其中LHS（LeftHandSide）是规则的所有约束条件集合，可以包括多个数据对象的不同约束条件，因此每条规则隐含了某种数据对象。如果用ΔObj来表示LHS中的第k个事k实对象，∑ΔLHSk来表示第k个事实对象的所有约束条件，则LHS可定义为：LHS=∑f(ΔObjk,∑ΔLHSk,)k∈N,k>=1RHS（RightHandSide）是规则的结论部分，也就是事实满足LHS后进行的处理动作(A

7、ction)。规则的形式化自然语言可表示为："IF"condition"THEN"action规则的结构描述为：LogicalconstrainActionConditionValueconstrainKeywordconstrain。。。图2.1.1规则结构Fig2.1.1Structureofrules定义2.1.3(模式：Pattern)规则的LHS部分，已知事实的泛化形式，未实例化的多元关系。模式可以用以下二元组表示为：P：