一種模糊認知圖分類器的研究

(1.北京科技大學 信息工程學院 北京 100083； 2.華北科技學院 計算機系 北京 101601)

摘 要：通過使用模糊認知圖來模擬分類過程，構造了一種模糊認知圖分類器，提出了它的兩種模糊認知圖分類模型，并在此基礎上給出了使用它進行分類的推理機制。實驗證明，該方法具有良好的分類性能。

關鍵詞：模糊認知圖; 數據挖掘; 分類; 模糊認知圖分類器

中圖分類號：TP391文獻標志碼：A

文章編號：1001-3695(2009)05-1757-03

Research on one fuzzy cognitive map classifier

PENG Zhen1，2 YANG Bingru1 LIU Chunmei2 TANG Zhigang1 YANG Jun1

(1.School of Information Engineering University of Science Technology Beijing Beijing 100083 China; 2.Dept. of Computer North China Institute of Science Technology Beijing 101601 China)

Abstract:The paper constructed a FC(FCM classifier) using FCM(fuzzy cognitive map) simulating classification system and proposed two FCM classification models (FCMI and FCMII) of the FC and inferenced mechanisms FC uses. The experiment demonstrates the efficacy of the two structures in classification task of data mining.

Key words：FCM(fuzzy cognitive map); data mining; classification; FC(FCM classifier)

1986年，Kosko在認知圖(cognitive map，CM)的基礎上提出的模糊認知圖FCM^[1，2]結合了模糊邏輯與神經網絡技術，其知識表示和推理能力更強。在模糊認知圖中，連接是存儲知識的基本單元，即知識存儲在概念節點及概念節點間的關系中。由于連接表達的關系是一種邏輯知識，而邏輯知識的使用過程就是一種推理過程，所以概念間的相互作用的過程可以看做是依據連接關系進行推理的過程，連接的作用就是表示關系和執行推理。分類^[3]屬于數據挖掘中的一種預測任務，它的目標是根據其屬性的值，預測其所屬的類。具體來講，就是根據已知訓練樣例建立分類模型，該模型能夠預知未知屬性集所屬的目標類。目前，分類建模的方法主要有決策樹歸納法、基于規則的分類法、貝葉斯分類器、人工神經網絡分類器等，它們都已得到很好的應用。

文獻[4]提出了一種使用模糊認知圖進行分類推理，但都沒有系統地提出模糊認知圖用于分類的構造模型、方法等。因此，本文構造一種模糊認知圖分類器，它是用模糊認知圖來模擬分類過程或分類系統，也就是說將分類過程看做是模糊認知圖的狀態轉換過程，提出了兩種模糊認知圖分類模型以及使用這種分類器進行分類的推理機制。

1 模糊認知圖

1.1 模糊認知圖模型

一個FCM的拓撲結構U是一個三元組即U=(C，E，W)。其中：C={C1，C2，…，Cn}表示FCM的概念節點集合；E={〈C1，C2〉｜C1，C2∈C}表示節點之間的因果關聯有向弧；W={Wij｜Wij是有向弧〈Ci，Cj〉的權值}，Wij表示節點Ci對Cj的關聯或影響程度。如果Wij＞0表示Ci對Cj有正的影響即Ci的狀態值增加(減少)將導致Cj狀態值增加(減少)；反之則有負的影響，如果Wij=0則表示Ci對Cj沒有影響。圖1是一個簡單的FCM。FCM的W是一個n×n階的鏈接矩陣如圖2所示。

FCM中每個節點在某個時刻都對應一個狀態值，如Aj(t)分別是Cj概念節點在t時刻的狀態值。相鄰時刻狀態值的轉換是依靠閾值函數f(x)來實現的，它能夠將概念的狀態值限制在[0 1]內。常用的函數有二值函數、三值函數及S型函數三類，S型函數見式(1)。

f(x)=1/（1+e-λx）(1)

其中：λ＞0是決定函數形狀的一個參數。FCM節點的初始狀態向量通過式(1)得到一個新的狀態空間，在數次轉換后，FCM可達到以下三種狀態：a)固定點；b)有限環；c)混沌狀態。當FCM達到a)b)狀態時，系統達到穩定/平衡狀態。

1.2 模糊認知圖的構造

一般來說，FCM的構造方法有兩種，即人工構造和計算構造。人工構造是利用專家知識和經驗建立FCM模型；計算構造是利用樣本數據訓練自動獲取FCM模型。

人工構造方式的建模過程包括三個步驟：a)識別問題域內的關鍵概念；b)識別這些概念間的有無因果關系；c)估計關系的值。人工構造系統的FCM在一些領域已經有了很好的應用^[5]，但它過分地依賴專家的主觀意識及其領域知識。由此，產生了計算構造FCM的方法。

當前，計算構造FCM主要有兩類分支：a)基于Hebbian的學習方式；b)基于進化論的學習方式。前者包括微分Hebbian學習DHL(differential Hebbian learning)、平衡微分算法BDA(balanced differential algorithm)、非線性Hebbian學習NHL(nonlinear Hebbian learning)和激活Hebbian學習AHL(active Hebbian learning)^[6~8]。后者是指遺傳策略GA(genetic strategy)、粒子群優化(particle swarm optimization，PSO)算法、面向目標的分析(goaloriented analysis，GA)方法、基于實數編碼的遺傳算法(real coded genetic algorithm，RCGA)^[9，10]。在這八種學習算法中，除了GA外，其他算法的學習目標都是得到FCM的鏈接矩陣，另外NHL和AHL需要部分的人工干預。文獻[11]在RCGA的基礎上提出了并行的RCGA。這些算法提出的目的都是為了能夠快速地從數據源中自動地構造出模擬系統動態行為的FCM。

2 模糊認知圖分類器

2.1 模糊認知圖分類器的工作原理

因為模糊認知圖能夠直觀地描繪一個復雜系統中的概念及概念之間的因果關系，并通過概念間相互關系模擬系統行為從而為系統作出決策，所以本文提出用模糊認知圖來模擬分類過程或分類系統，也就是說將分類過程看做模糊認知圖的狀態轉換過程。當模糊認知圖達到平衡狀態時的對應結果即為分類結果。由此，構造了基于模糊認知圖的分類器FC(FCM classifier)，如圖3所示。

FC的工作原理分為兩步：a)對訓練樣例數據進行初始化處理后，通過一定的學習算法獲取FCM分類模型，即確定其權值矩陣；b)對待分類的數據屬性通過初始化處理后就作用于FCM分類模型，從而得到其所屬類。以下主要從模糊認知圖分類器的分類模型和模糊認知圖分類器的分類機制兩個方面進行介紹。

2.2 模糊認知圖分類器的分類模型

用于分類的數據集系統中主要包括四類數據，即屬性、類、屬性值和類值。屬性和類對應FC中的概念節點，屬性值和類值代表概念節點的狀態值。根據屬性概念與類概念關系的不同構造出以下兩種模糊認知圖分類模型，如圖4和5所示。

FCMⅠ中的關系存在類節點C之間以及屬性F與類節點之間，形成了一個(n+m)×n的邊權矩陣，表示為系統主要是用類間的關系、屬性與類間的關系來模擬其分類動態行為。

FCMⅡ中的關系存在于屬性節點F之間以及屬性與類節點C之間，形成了一個m×(n+m)的邊權矩陣，表示為系統主要是用屬性間的關系、屬性與類間的關系來模擬其分類動態行為。

FCM分類模型的構造過程就是通過調整權值達到擬合訓練樣例的過程，也就是說通過有限次步驟使得FCM系統達到一種穩定狀態，這個穩定狀態應是類節點的狀態值接近于甚至等于實際值。具體學習步驟如下：

a)數據的初始化處理，即對P條訓練樣例中的屬性節點狀態值模糊歸一化，所屬的類節點狀態值賦予1，其他類節點狀態值賦予0。

b)p=1，c=1。

c)取出第p條初始化后的訓練樣例；。

d)初始化系統各參數。 

e)采用一定的學習算法，調整鏈接矩陣。

f)c=c+1，若c＜M(M是最大迭代次數)則執行g)；否則轉向d)。

g)判定鏈接矩陣是否能夠達到模擬前p條訓練樣例的效果，若能則p=p+1。

h)若p＜P則執行c)；否則訓練成功。

2.3 模糊認知圖分類器的分類機制

根據模糊認知圖分類模型結構的不同，相應給出兩種推理模型。

FCMI的推理機制見式(2)(3): 

Aj(t+1)=f(Aj(t)+∑n+mi=1Ai(t)Wij)；t=0(2)

Aj(t+1)=f(Aj(t)+∑ni=1Ai(t)Wij)；t≥1(3)

FCMⅡ的推理模型見式(4):

Aj(t+1)=f(Aj(t)+∑mi=1，i≠j Ai(t)Wij)(4)

因為在FCMⅠ中屬性節點只是原因節點，其狀態值并不受任何其他節點的影響，因此在t≥1時，i的取值是[1，n]，不再將屬性節點包括在內。

根據分類模型為待分類數據進行分類的過程是：對輸入數據經過FCM有限次動態迭代后，在系統達到穩定狀態時值最大的類節點，即為輸入數據所屬的類。這個穩定狀態是指系統中節點狀態值都達到固定點狀態即每次迭代狀態值差別不大甚至是一樣的。具體分類流程如圖6所示。

3 實驗分析

本實驗采用的是Fisher提出的Iris數據集，測試兩種模糊認知圖分類模型的性能。Iris數據集包括三個類(Setosa、Versicolor、Virginica)和四個屬性(petallength、petalwidth、septallength、septalwidth)，共有150條記錄。其中任意選出120條記錄用于訓練樣本，剩余的30條用于測試。模糊認知圖分類器采用實數編碼的遺傳算法進行訓練學習，經過200次的重復實驗，訓練和分類性能的統計結果如圖7所示。

在學習訓練階段，FCMⅡ模型要比FCMⅠ模型的收斂速度慢，在模型誤差方面FCMⅡ模型略高于FCMⅠ模型，并且在分類效率方面，FCMⅠ模型的性能要高于FCMⅡ模型的性能。結果如表1所示。

表1 FCMⅠ與FCMⅡ模型性能比較

比較項FCMⅠFCMⅡ

結構(structure)4-34-3

模型誤差(error_behavior)0.058 70.060 1

分類準確率(classification accuracy)/%89.2488.58

4 結束語

本文首先介紹了模糊認知圖模型的相關概念和當前比較流行的模糊認知圖的學習算法。根據模糊認知圖和分類的特點，本文提出使用模糊認知圖來模擬分類過程，由此構造了一種模糊認知圖分類器，它的工作主要包括：a）構造模糊認知圖分類模型；b）使用模糊認知圖分類器進行分類推理。根據FCM對分類系統結構模擬的不同，提出了兩種模糊認知圖分類模型及其構造步驟，以及推理模型和分類流程。最后根據實驗證明模糊認知圖分類器的分類性能良好。

參考文獻：

［1］AGUILAR J. A survey about fuzzy cognitive maps papers(invited paper)[J]. International Journal of Computational Cognition 2005，3(2):27-33.

[2]林春梅.模糊認知圖模型方法及其應用研究[D].上海:東華大學 2006.

[3]HAN Jiawei KAMBER M. Data mining: concepts and techniques[M].2nd ed.[S.l.]:Morgan Kaufmann 2007.

[4]張桂蕓，劉洋，王元元.基于模糊認知圖的文本分類推理算法[J].計算機工程與應用，2007，43( 12):155-159.

[5]SCHNEIDER M SHNAIDER E KANDEL A，et al. Automatic construction of FCMs[J]. Fuzzy Sets and Systems 1998，93(2): 161-172.

[6]HUERGA A V. A balanced differential learning algorithm in fuzzy cognitive maps technical report[R]. Spain:Universitat Politecnica de Catalunya(UPC) 2002.

[7]PAPAGEORGIOU E I STYLIOS C D GROUMPOS P P. Fuzzy cognitive map learning based on nonlinear Hebbian rule[C]//Proc ofAustralian Conference on Artificial Intelligence. 2003:256-268.

[8]PAPAGEORGIOU E I STYLIOS C D GROUMPOS P P. Active Hebbian learning algorithm to train fuzzy cognitive maps[J]. International Journal of Approximate Reasoning 2004，37(3):219-249.

[9]PARSOPOULOS K E PAPAGEORGIOU E I GROUMPOS P P et al. A first study of fuzzy cognitive maps learning using particle swarm optimization[C]//Proc of IEEE Congress on Evolutionary Computation 2003(CEC 2003). 2003: 1440-1447.

[10]STACH W KURGAN L PEDRYCZ W，et al. Genetic learning of fuzzy cognitive maps[J]. Fuzzy Sets and Systems 2005，153:371-401.

[11]STACH W. Parallel genetic learning of fuzzy cognitive maps[R]. [S.l.]: IEEECIS Walter Karplus Summer Research Grant 2006.