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

《cabpm基于模式匹配的聚類算法》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、http://www.paper.edu.cnCABPM:基于模式匹配的聚類算法方應飛北京郵電大學計算機科學與技術學院，北京(100876)E-mail：jiajiafyf0775@sina.com摘要：本文通過研究一種快速前向模式匹配算法Rete算法，從一個新的角度重新分析設計了聚類算法－基于模式匹配的聚類算法（AClusteringAlgorithmBasedonPatternMatching）。該算法通過對原始Rete算法概念的修改與拓展，詳細描述了數據對象在CABPM算法中的表現(xiàn)形式和聚類完成過程，并給出了具體的算法描述，為傳統(tǒng)聚類算法的優(yōu)化改進提供了一個新的思路。關鍵詞：Ret

2、e算法模式匹配聚類算法中圖分類號：TP3111.引言數據挖掘的主要任務是從海量數據中找出有效、實用的數據，并分析數據間的相關性。[1]聚類(clustering)是數據挖掘任務的重要實現(xiàn)手段，其主要目標是將數據對象集劃分為若干組(class)或類(cluster)，并使得同一個組內的數據對象具有較高的相似度，而不同組中的數據對象則是相似度較低。相似度高低的度量是基于數據對象描述的取值來確定的，通常利用(各對象間)距離來進行描述。[2]目前，聚類方法代表性算法有分層方法(hierarchicalmethod)、劃分方法(partitioningmethod)、基于密度分布函數的方法(den

3、sity-basedmethod)、基于網絡方法(grid-basedmethod)和基于模型的方法(model-basedmethod)。絕大部劃分方法都是基于對象之間的距離進行聚類，這樣的方法或者不能發(fā)現(xiàn)任意形狀的簇(只能發(fā)現(xiàn)球狀的簇，而不能發(fā)現(xiàn)其他形狀的簇)，或者對輸入參數和數據對象輸入順序敏感。本文從研究Rete算法的基本思想著手，根據Rete網絡算法前項快速匹配的特點，結合聚類分析的基本要求，通過構建基于模式的匹配網絡，將聚類分析過程描述為模式的匹配過程，并定義數據對象和模式間的相似度（μ）來發(fā)現(xiàn)聚簇，從而完成聚類過程。由于算法避免了對數據對象的反復遍歷并基于模式定義之上，因而

4、算法具有較好的性能和分類能力。文章較為詳細的討論了Rete網絡的構建過程，并在對Rete網絡基本概念的拓展之上討論了如何使數據對象在Rete網絡中的流動來完成數據對象的聚類過程。在文章的最后給出了算法的具體描述和性能評價。2.Rete算法的基本理論和概念拓展為了達到通過構建Rete匹配網絡來進行數據對象的模式匹配實現(xiàn)聚類過程，需要從下面兩個方面來考慮，并分別在接下來的兩個章節(jié)中討論：1）如何構建Rete匹配網絡；2）數據對象在Rete匹配網絡上的表現(xiàn)形式及聚簇的產生方式；2.1Rete算法基本概念[3]Rete算法是美國卡耐基·梅隆大學的CharlesL.Forgy為解決商務規(guī)則引擎于1

5、982年提出的一種前項推理（Forward-Chaining）算法，其核心思想是將分離的匹配項根據內容動態(tài)構造有效的辨別網絡，以達到顯著降低計算量的效果。為了在后面的聚類分析中引用算法，對算法中的有關概念做了重新定義。-1-http://www.paper.edu.cn定義2.1.1(事實：Fact）數據對象及對象屬性之間的多元關系，一個事實可以用一個三元組來表示：F：(Data，Attributes，Values)其中Data表示數據對象集，有若干個數據對象組成，Attributes是Data中的屬性集，Values是屬性集對應的值的集合；定義2.1.2(規(guī)則：Rule）由條件和結論構

6、成的推理語句，具有可表達能力、可理解性和可訪問性。在聚類分析中“條件”就是數據對象滿足某一分類的約束屬性，“結論”就是將[3]事實加入該分類。一條規(guī)則可以用一個二元組來表示：R：（LHS，RHS）其中LHS（LeftHandSide）是規(guī)則的所有約束條件集合，可以包括多個數據對象的不同約束條件，因此每條規(guī)則隱含了某種數據對象。如果用ΔObj來表示LHS中的第k個事k實對象，∑ΔLHSk來表示第k個事實對象的所有約束條件，則LHS可定義為：LHS=∑f(ΔObjk,∑ΔLHSk,)k∈N,k>=1RHS（RightHandSide）是規(guī)則的結論部分，也就是事實滿足LHS后進行的處理動作(A

7、ction)。規(guī)則的形式化自然語言可表示為："IF"condition"THEN"action規(guī)則的結構描述為：LogicalconstrainActionConditionValueconstrainKeywordconstrain。。。圖2.1.1規(guī)則結構Fig2.1.1Structureofrules定義2.1.3(模式：Pattern)規(guī)則的LHS部分，已知事實的泛化形式，未實例化的多元關系。模式可以用以下二元組表示為：P：