馮興華，劉曉東＊，劉亞清

（1.大連理工大學(xué) 控制科學(xué)與工程學(xué)院，遼寧 大連 116024；2.大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院，遼寧 大連 116026）

0 引 言

利用IF－THEN 規(guī)則的分類(lèi)方法的優(yōu)勢(shì)在于給出分類(lèi)結(jié)果的同時(shí)還能夠給出分類(lèi)的語(yǔ)義解釋?zhuān)?］.為了克服數(shù)據(jù)中存在的不確定性和含糊性等，基于模糊規(guī)則的分類(lèi)方法被提出，并被大量研究［2］.例如，Wang等［3］提出了基于關(guān)聯(lián)規(guī)則的模糊分類(lèi)器，而Alcala等［4］提出了針對(duì)高維數(shù)據(jù)的模糊關(guān)聯(lián)規(guī)則分類(lèi)方法；Huhn等［5］提出了名為FURIA 的分類(lèi)方法，此方法先產(chǎn)生經(jīng)典分類(lèi)規(guī)則集，然后用梯形模糊集對(duì)分類(lèi)規(guī)則進(jìn)行模糊化，最后用得到的模糊規(guī)則集對(duì)數(shù)據(jù)進(jìn)行分類(lèi).最近，一種由支持向量機(jī)誘導(dǎo)分類(lèi)規(guī)則的方法［6］被提出，該方法主要考慮了支持向量機(jī)的分類(lèi)邊界及訓(xùn)練樣本的分布.很多利用模糊規(guī)則分類(lèi)的方法都是基于模糊概念的.然而，恰當(dāng)?shù)卮_定模糊概念的隸屬函數(shù)是非常困難的，即使是領(lǐng)域內(nèi)專(zhuān)家也很難做到［7］.采用不同的隸屬函數(shù)對(duì)最終分類(lèi)結(jié)果影響很大；而用不同的隸屬函數(shù)，相同的分類(lèi)算法也會(huì)給出不同的分類(lèi)結(jié)果.這在一定程度上影響了模糊分類(lèi)器的設(shè)計(jì).

基于上述分析，本文在AFS（axiomatic fuzzy set）理論框架下提出一種基于模糊概念相似性與模糊熵度量的分類(lèi)算法；并在8組來(lái)自UCI［8］數(shù)據(jù)庫(kù)的實(shí)驗(yàn)數(shù)據(jù)上和其他7 種分類(lèi)算法進(jìn)行比較，以證明該算法的可靠性和優(yōu)越性.

1 AFS理論相關(guān)知識(shí)

設(shè)X是一個(gè)數(shù)據(jù)集，即X＝｛x1，x2，…，xN｝.其中xi＝｛xi，1，xi，2，…，xi，n｝，xi，j表示樣本xi在第j個(gè)屬性上的取值，i＝1，2，…，N，j＝1，2，…，n.在每個(gè)屬性上，取定若干個(gè)簡(jiǎn)單的模糊概念形成模糊概念集合M.

文獻(xiàn)［9］證明了如果如下定義EM上的運(yùn)算∧和∨，則（EM，∧，∨）是完全分配格：任意

其中U是指標(biāo)集I與J的不交并.

設(shè)X為數(shù)據(jù)集，M是X上的概念集，對(duì)于任意的概念集合AM及x∈X，定義X的子集A≥（x）：

式中：x≥Ay表示對(duì)于任意的模糊概念m∈A，x隸屬于m的程度大于或者等于y隸屬于m的程度；A≥（x）完全由概念集合A中的概念的語(yǔ)義及樣本集合X的分布決定.

定義1［9－10］設(shè)集合M是一個(gè)概念集合，（EM，∧，∨）是完全分配格，則對(duì)于任意的x∈X，模糊概念的隸屬函數(shù)定義為

上面定義的模糊概念的隸屬函數(shù)完全由概念的語(yǔ)義及樣本數(shù)據(jù)的分布決定.因?yàn)楦瘢‥M，∧，∨）對(duì)邏輯運(yùn)算∧、∨封閉，所以對(duì)于EM中的任何概念的隸屬函數(shù)都可以由上述定義得到.

2 基于模糊規(guī)則的分類(lèi)算法

首先描述指導(dǎo)概念聚合過(guò)程的模糊概念選擇函數(shù)，然后給出產(chǎn)生模糊IF－THEN 規(guī)則集的聚合算法，最后介紹模糊規(guī)則集的剪枝算法及利用模糊規(guī)則集對(duì)樣本的分類(lèi)過(guò)程.

2.1 選擇函數(shù)

（1）模糊概念的相似性

設(shè)α、β是兩個(gè)模糊概念，Jaccard相似性［11］在AFS理論框架下表示為

其中∨、∧分別由式（1）和（2）給出.μα∧β（x）和μα∨β（x）分別表示樣本x隸屬于模糊概念α∧β和α∨β的隸屬度，由式（4）給出.

（2）模糊熵

α是一個(gè)模糊概念，Λ是一個(gè)模糊概念集合，Λ＝｛β1，β2，…，βk｝.Λ對(duì)α的一個(gè)劃分記為Λ｜α，定義為Λ｜α＝｛β1 ∧α，β2 ∧α，…，βk∧α｝.信息熵是衡量一個(gè)集合的混亂程度的常用度量.為了衡量劃分Λ｜α中βi∧α與其他部分的相異程度，定義βi∧α與其他部分之間的模糊熵為

（3）選擇函數(shù)

如下定義選擇函數(shù)f（α，βi）：

式（6）所示的選擇函數(shù)評(píng)價(jià)模糊概念α對(duì)模糊概念βi的描述能力.一方面考慮了α與βi的相似性，另一方面考慮在用Λ對(duì)α劃分時(shí)，βi∧α與其他部分的相異性.一般而言，α與βi越相似，并且模糊劃分Λ｜α中βi∧α與其他部分的相異性越大，選擇函數(shù)f（α，βi）的值越大.

在分類(lèi)問(wèn)題中，Λ＝｛β1，β2，…，βk｝可以表示決策屬性上的類(lèi)別概念集，βi表示第i類(lèi).這種情況下，式（6）就可以用來(lái)衡量模糊概念α對(duì)類(lèi)別βi的描述能力.而基于規(guī)則的分類(lèi)方法就是要找到條件屬性上的概念α來(lái)描述決策屬性上的類(lèi)別概念βi.也就是說(shuō)，α不但要和βi相似，又要使βi∧α和βj∧α（j≠i）較好地區(qū)分開(kāi).

下面用圖1所示的例子來(lái)例證所定義的選擇函數(shù)的合理性.圖1所示的是一個(gè)兩類(lèi)別分類(lèi)問(wèn)題，包含100個(gè)樣本，兩類(lèi)的決策概念分別用β1、β2表示，即決策屬性上的決策概念集為Λ＝｛β1，β2｝.α1、α2、α3、α4是4個(gè)條件屬性上的模糊概念.表1給出了α1、α2、α3、α4分別對(duì)β1 的選擇函數(shù)值.

在圖1中，與α3相比，第一類(lèi)的50個(gè)樣本在α2上的隸屬度與β1 更為相似，但是α2對(duì)第一類(lèi)樣本與第二類(lèi)樣本的區(qū)分度并不大.從與β1 的相似性與對(duì)兩類(lèi)樣本的區(qū)分程度兩方面來(lái)考慮的話(huà)，α3對(duì)β1 的描述能力更強(qiáng).也就是說(shuō)，α3比α2更適合作為β1 的規(guī)則前件.從表1中的數(shù)據(jù)可以看到f（α3，β1）＝－0.10，f（α2，β1）＝－0.22，這說(shuō)明本文定義的選擇函數(shù)給出的選擇結(jié)論與本文的直觀(guān)分析完全一致.

圖1 模糊概念的隸屬度函數(shù)Fig.1 The membership functions of fuzzy concepts

表1 選擇函數(shù)在不同模糊概念上的取值Tab.1 The selection index values on different fuzzy concepts

比較α1與α4的隸屬度函數(shù)可以看到，雖然α1與α4都可以將兩類(lèi)樣本很好地區(qū)分開(kāi)，但是α4與目標(biāo)類(lèi)別β1 相似性非常小.這說(shuō)明與α4相比，α1能更好描述β1.

從表1給出的各個(gè)模糊概念對(duì)β1 的選擇函數(shù)值可以看到，f（α1，β1）＞f（α3，β1）＞f（α2，β1）＞f（α4，β1）.這與從圖1中得到的直觀(guān)分析結(jié)果一致.

2.2 分類(lèi)算法

本文提出的分類(lèi)算法利用IF－THEN 規(guī)則對(duì)樣本進(jìn)行分類(lèi)，其中每一條分類(lèi)規(guī)則都具有如下形式：IFα，THENβ.α表示條件屬性上的模糊概念，β表示決策屬性上的概念（模糊或非模糊）.每一條IF－THEN 規(guī)則都是前件和后件之間的關(guān)系的體現(xiàn).

一般情況下，如果分類(lèi)規(guī)則集的前件過(guò)于簡(jiǎn)單，往往不能得到較好的分類(lèi)精度；如果過(guò)于復(fù)雜，則意味著有可能發(fā)生了過(guò)度訓(xùn)練.本文通過(guò)簡(jiǎn)單概念的聚合得到恰當(dāng)?shù)囊?guī)則前件.通過(guò)概念聚合［12］，簡(jiǎn)單概念被聚合為復(fù)雜概念，以便更好地描述規(guī)則后件，從而提高分類(lèi)精度.

概念聚合包含3 個(gè)部分：目標(biāo)概念、候選概念，以及邏輯算子.模糊概念的聚合是通過(guò)概念的邏輯運(yùn)算完成的.如前文所述，在AFS理論中定義了兩種模糊概念的邏輯算子，分別是“or”∨（如式（1）所示）和“and”∧（如式（2）所示）.通過(guò)邏輯算子將目標(biāo)概念與候選概念聚合為新的模糊概念，聚合得到的模糊概念的隸屬度由式（4）給出.

分類(lèi)問(wèn)題涉及的數(shù)據(jù)可以規(guī)范為如下形式：設(shè)X＝｛x1，x2，…，xN｝表示樣本集合，A1，A2，…，An表示樣本集上的n個(gè)條件屬性，C表示決策屬性.在條件屬性Ai上取ki個(gè)簡(jiǎn)單模糊概念，用T（Ai）＝｛mi1，mi2，…，miki｝表示Ai上的簡(jiǎn)單概念集合，T（C）＝｛β1，β2，…，βc｝表示決策屬性上的決策概念集合，即T（C）中的每一個(gè)概念表示樣本集的一個(gè)類(lèi)別.

模糊分類(lèi)規(guī)則構(gòu)建算法為每一個(gè)類(lèi)別通過(guò)聚合找到最合適的描述概念.以第一類(lèi)為例的算法如圖2所示.由圖2給出的算法可以得到一個(gè)規(guī)則集，其中的每一條規(guī)則的前件是輸出Result中的一個(gè)模糊概念，后件是第一類(lèi)的決策概念β1.

在圖2中，Ξ表示目標(biāo)概念集；Θ表示待候選概念集；Ω表示簡(jiǎn)單概念集；Ψ表示算子集；Θ#Ω表示候選概念集.

算法的時(shí)間復(fù)雜度為O（N｜Ω0｜），其中N為訓(xùn)練樣本的個(gè)數(shù)，｜Ω0｜為初始簡(jiǎn)單概念的個(gè)數(shù).算法的最大計(jì)算量來(lái)自于聚合過(guò)程（見(jiàn)圖2），在每次循環(huán)過(guò)程中，用L個(gè)目標(biāo)概念和至多｜Ω0｜＋T個(gè)候選概念進(jìn)行聚合，聚合過(guò)程循環(huán)length次.而L、T和length三個(gè)參數(shù)由用戶(hù)給出，是固定的數(shù)值，在下一節(jié)的實(shí)驗(yàn)中分別設(shè)置為3、2和5.所以時(shí)間復(fù)雜度為O（N｜Ω0｜）.

2.3 推理過(guò)程

從圖2所示算法直接得到的模糊規(guī)則集可能包含冗余和分類(lèi)能力差的規(guī)則.因此，需要將這樣的規(guī)則從規(guī)則集中剔除以提高規(guī)則集的分類(lèi)準(zhǔn)確率和分類(lèi)效率.這里采用一種剪枝方法來(lái)修剪規(guī)則集，這種方法只需要規(guī)則集和訓(xùn)練樣本集的參與.具體過(guò)程如下：

步驟1 對(duì)規(guī)則集中的每一條規(guī)則進(jìn)行如下過(guò)程：刪除該規(guī)則，用剩余規(guī)則對(duì)訓(xùn)練樣本進(jìn)行分類(lèi)并記錄分類(lèi)準(zhǔn)確率及該條規(guī)則.

步驟2 找到步驟1中得到的準(zhǔn)確率中的最高準(zhǔn)確率對(duì)應(yīng)的規(guī)則，真正將之刪除.

步驟3 重復(fù)步驟1及步驟2直到如果要真正刪除某條規(guī)則，規(guī)則集對(duì)訓(xùn)練樣本的分類(lèi)準(zhǔn)確率將出現(xiàn)下降為止.

剪枝后的規(guī)則集就是最終用于分類(lèi)的規(guī)則集.當(dāng)需要對(duì)新樣本x進(jìn)行分類(lèi)時(shí)，用式（4）計(jì)算該樣本在每一條規(guī)則的前件上的隸屬度.樣本x將被分配到規(guī)則r所表示的類(lèi)，如果x在規(guī)則r的前件上取得最大的隸屬度值.

3 實(shí)驗(yàn)結(jié)果及分析

用8組來(lái)自UCI的數(shù)據(jù)對(duì)提出的分類(lèi)算法進(jìn)行驗(yàn)證.表2給出了這8組數(shù)據(jù)的基本信息.在這8組數(shù)據(jù)上，對(duì)本文分類(lèi)方法和其他7種分類(lèi)方法做了比較.這7 種方法是C4.5［13］、Decision Table （DTable）［14］、Fast Effective Rule Induction （JRip）［15］、 Nearest－neighbor－like Algorithm（NNge）［16］、OneR［17］、PART Decision List （PART）［18］，以 及 Ripple－down Rule Learner（Ridor）［19］.上述7種分類(lèi)方法由分類(lèi)工具箱Weka［20］實(shí)現(xiàn)且各個(gè)分類(lèi)器均采用工具箱指定的默認(rèn)參數(shù).在本文提出的分類(lèi)方法中，3個(gè)參數(shù)分別為L(zhǎng)＝3，T＝2，length＝5.另外，為簡(jiǎn)單起見(jiàn)在每個(gè)數(shù)據(jù)集的各個(gè)條件屬性上取3個(gè)簡(jiǎn)單模糊概念，每一個(gè)簡(jiǎn)單模糊概念都有一個(gè)明確的含義：離第i個(gè)分割點(diǎn)較近.第一個(gè)分割點(diǎn)取為屬性的最小值；第二個(gè)分割點(diǎn)取為屬性均值；第三個(gè)分割點(diǎn)取為屬性的最大值，所有概念的隸屬函數(shù)由式（4）給出.

在實(shí)驗(yàn)中，對(duì)每一個(gè)分類(lèi)數(shù)據(jù)均采用10折交叉驗(yàn)證法來(lái)評(píng)估分類(lèi)算法分類(lèi)準(zhǔn)確率.實(shí)驗(yàn)得到的分類(lèi)準(zhǔn)確率如表3所示.由表3可以看出，本文提出的分類(lèi)算法（在表3中用AFS表示）能給出最好的分類(lèi)結(jié)果，8組數(shù)據(jù)上的平均準(zhǔn)確率最高.為了進(jìn)一步分析本文提出的算法與其他7種分類(lèi)算法之間的差異，采用統(tǒng)計(jì)分析的方法對(duì)這8種分類(lèi)算法得到的結(jié)果做出分析.

表2 來(lái)自UCI數(shù)據(jù)庫(kù)的8組數(shù)據(jù)的基本信息Tab.2 The descriptions of datasets from UCI repository

首先，用Friedman檢驗(yàn)法［21］來(lái)檢驗(yàn)這8 種分類(lèi)器在8組實(shí)驗(yàn)數(shù)據(jù)上得到的分類(lèi)結(jié)果是否存在顯著差異；如果這些分類(lèi)結(jié)果存在顯著差異，進(jìn)一步采用Holm 檢驗(yàn)法［21］來(lái)檢驗(yàn)本文提出的算法是否和其他方法存在顯著差異.

表3 不同分類(lèi)方法的比較分析Tab.3 A comparative analysis of different classification methods

Friedman檢驗(yàn)法的零假設(shè)為多個(gè)分類(lèi)方法得到的分類(lèi)結(jié)果不存在顯著差異.在每一個(gè)數(shù)據(jù)集上，按照各個(gè)分類(lèi)方法得到的分類(lèi)準(zhǔn)確率將其排序，每一個(gè)分類(lèi)方法將得到一個(gè)序數(shù)值（如果分類(lèi)準(zhǔn)確率一樣，則均分序數(shù)值）.以下假設(shè)有k個(gè)分類(lèi)方法，實(shí)驗(yàn)數(shù)據(jù)有N組.用rji表示第j種分類(lèi)方法在第i個(gè)數(shù)據(jù)上的序數(shù)值，則Rj＝（1／N）∑irji表示第j種分類(lèi)方法在N組實(shí)驗(yàn)數(shù)據(jù)上的平均序數(shù)值.Friedman檢驗(yàn)的統(tǒng)計(jì)量為

該統(tǒng)計(jì)量服從自由度為k－1的卡方分布.如果k和N比較小，則使用下面的統(tǒng)計(jì)量：

統(tǒng)計(jì)量FF服從自由度為（k－1）和（k－1）·（N－1）的F分布.

本文所做的實(shí)驗(yàn)中k＝8，N＝8，F(xiàn)F＝2.57，在顯著性水平α＝0.05下統(tǒng)計(jì)量的值超過(guò)了臨界值.所以，可以拒絕零假設(shè)，即這8種方法在8組數(shù)據(jù)上得到的分類(lèi)結(jié)果存在顯著差異.然后，用Holm 測(cè)試來(lái)分析本文方法和其他7種方法之間是否存在顯著差異.分析的結(jié)果顯示，在顯著水平α＝0.1時(shí)，本文方法在8組實(shí)驗(yàn)數(shù)據(jù)上的分類(lèi)結(jié)果顯著好于DTable方法和OneR 方法.雖然本文的方法不是顯著好于其他5種方法，但是表3列出的序數(shù)值說(shuō)明，本文的方法取得了最小的均序值，即本文提出的分類(lèi)算法能得到最好的分類(lèi)準(zhǔn)確率.

4 結(jié) 語(yǔ)

本文提出了一種產(chǎn)生模糊分類(lèi)規(guī)則的方法.該方法通過(guò)簡(jiǎn)單模糊概念的聚合產(chǎn)生模糊分類(lèi)規(guī)則的前件.一個(gè)基于模糊概念相似性與模糊熵的選擇函數(shù)指導(dǎo)概念的聚合過(guò)程.用AFS理論來(lái)處理模糊概念的邏輯運(yùn)算，并給出其隸屬函數(shù).在AFS理論框架下，模糊概念的隸屬函數(shù)完全由概念的語(yǔ)義和樣本數(shù)據(jù)的分布決定，不需要背景知識(shí)的參與.

在8組來(lái)自UCI數(shù)據(jù)庫(kù)的數(shù)據(jù)上和7 種經(jīng)典分類(lèi)方法做了比較.實(shí)驗(yàn)結(jié)果顯示，本文提出的分類(lèi)算法能得到最好的分類(lèi)精度，其分類(lèi)準(zhǔn)確率顯著地高于DTable方法和OneR 方法.

在以后的工作中，將研究概念聚合的過(guò)程，設(shè)計(jì)新的算法以提高規(guī)則集的分類(lèi)效果.另一個(gè)可以擴(kuò)展的工作是對(duì)規(guī)則集的結(jié)構(gòu)的分析，這也可幫助改進(jìn)聚合算法.

［1］ Alsabti K，Ranka S，Singh V.CLOUDS：A decision tree classifier for large datasets ［C］／／Conference of Knowledge Discovery and Data Mining.New York：AAAI Press，1998：2－8.

［2］ Cano J，Herrera F，Lozano M.Evolutionary stratified training set selection for extracting classification rules with trade off precision interpretability ［J］.Data and Knowledge Engineering，2007，60（1）：90－108.

［3］ WANG Xin，LIU Xiao－dong，Pedrycz W.Mining axiomatic fuzzy set association rules for classification problems ［J］.European Journal of Operational Research，2012，218（1）：202－210.

［4］ Alcala F J，Alcala R，Herrera F.A fuzzy association rule－based classification model for highdimensional problems with genetic rule selection and lateral tuning ［J］.IEEE Transactions on Fuzzy Systems，2011，19（5）：857－872.

［5］ Huhn J，Hullermeier E.FURIA：An algorithm for unordered fuzzy rule induction［J］.Data Mining and Knowledge Discovery，2009，19（3）：293－319.

［6］ ZHU Peng－fei，HU Qing－h(huán)ua.Rule extraction from support vector machines based on consistent region covering reduction［J］.Knowledge－Based Systems，2013，42（1）：1－8.

［7］ Chandra B，Varghese P P.Fuzzy SLIQ decision tree algorithm ［J］.IEEE Transactions on Systems，Man and Cybernetics，Part B：Cybernetics，2008，38（5）：1294－1301.

［8］ Merz C J，Murphy P M.UCI repository for machine learning data－bases ［Z］.Irvine：Department of Information and Computer Science，University of California，1996.

［9］ LIU Xiao－dong.The fuzzy theory based on AFS algebras and AFS structure ［J］.Journal of Mathematical Analysis and Applications，1998，217（2）：459－478.

［10］ LIU Xiao－dong，WANG Wei，CHAI Tian－you.The fuzzy clustering analysis based on AFS theory［J］.IEEE Transactions on Systems，Man and Cybernetics，Part B：Cybernetics，2005，35（5）：1013－1027.

［11］ Tan P N，Steinbach M，Kumar V.Introduction to Data Mining［M］.MA：Addison－Wesley，2005.

［12］ HUANG Zhi－h(huán)eng，Gedeon T D，Nikravesh M.Pattern trees induction：A new machine learning method［J］.IEEE Transactions on Fuzzy Systems，2008，16（4）：958－970.

［13］ Quinlan J R.C4.5：Programs for Machine Learning［M］.San Mateo：Morgan Kaufmann，1993.

［14］ Kohavi R.The power of decision tables ［C］／／European Conference on Machine Learning.Heraclion：Springer，1995：174－189.

［15］ Cohen W W.Fast effective rule induction［C］／／The Twelfth International Conference on Machine Learning.California：Morgan Kaufmann，1995：115－123.

［16］ Roy S.Nearest Neighbor with Generalization［M］.Christchurch：University of Canterbury，2002.

［17］ Holte R C.Very simple classification rules perform well on most commonly used datasets［J］.Machine Learning，1993，11（1）：63－91.

［18］ Frank E，Witten I H.Generating accurate rule sets without global optimization ［C］／／The Fifteenth International Conference on Machine Learning.Wisconsin：Morgan Kaufmann，1998：144－151.

［19］ Gaines B R，Compton P.Induction of ripple－down rules applied to modeling large databases ［J］.Journal of Intelligent Information Systems，1995，5（3）：211－228.

［20］ Witten I H，F(xiàn)rank E.Data Mining：Practical Machine Learning Tools and Techniques［M］.San Mateo：Morgan Kaufmann，2005.

［21］ Demsar J.Statistical comparisons of classifiers over multiple data sets ［J］.Journal of Machine Learning，2006，7（1）：1－30.