梁紅碩, 劉云橋, 趙 理,2

(1. 石家莊職業(yè)技術(shù)學(xué)院，河北 石家莊 050081；2. 北京理工大學(xué)， 北京 100081)

?

知識進化算法及其在關(guān)聯(lián)分類中的應(yīng)用

梁紅碩1, 劉云橋1, 趙 理1,2

(1. 石家莊職業(yè)技術(shù)學(xué)院，河北 石家莊 050081；2. 北京理工大學(xué)， 北京 100081)

針對傳統(tǒng)的關(guān)聯(lián)分類算法在構(gòu)造分類器的過程中需要多次遍歷數(shù)據(jù)集從而消耗大量的計算、存儲資源的問題，該文提出了一種基于知識進化算法的分類規(guī)則構(gòu)造方法。該方法首先對數(shù)據(jù)集中的數(shù)據(jù)進行編碼；然后利用猜測與反駁算子從編碼后的數(shù)據(jù)中提取出猜測知識和反面知識；接著對提取出來的猜測知識進行覆蓋度、正確度的計算，并根據(jù)不斷變化的統(tǒng)計數(shù)據(jù)利用萃取算子將猜測知識與反面知識進行合理的轉(zhuǎn)換。當(dāng)?shù)玫降闹R集中的知識的覆蓋度達到預(yù)設(shè)的閾值時，該數(shù)據(jù)集中的知識被用來生成分類器進行分類。該方法分塊讀入待分類的數(shù)據(jù)集，極大地減少了遍歷數(shù)據(jù)集的次數(shù)，明顯減少了系統(tǒng)所需的存儲空間，提高了分類器的構(gòu)造效率。實驗結(jié)果表明，該方法可行、有效，在保證分類精度的前提下，較好地解決了關(guān)聯(lián)分類器構(gòu)造低效、費時的問題。

知識進化；猜測；反駁；關(guān)聯(lián)分類

1 引言

傳統(tǒng)的進化算法是建立在達爾文的自然選擇學(xué)說基礎(chǔ)上,對生物自然進化過程的模擬,是人們對從自然演化過程中抽象出來的概念、原則和機制的類比應(yīng)用,已被廣泛用來解決復(fù)雜的計算問題,目前的研究工作大多仍集中在生物自然選擇層面上[1-2]。然而,科學(xué)哲學(xué)家在研究科學(xué)發(fā)展的過程中發(fā)現(xiàn):科學(xué)發(fā)展過程也實際存在著類似的進化機制,但是這種機制更具有自身的特殊性。著名批判理性主義的創(chuàng)始人卡爾·波普爾指出[3]“科學(xué)理論的選擇是一個類似于達爾文所說的自然選擇過程, 我們的知識總是由假說構(gòu)成的,它通過在生存斗爭中存在下來而顯示它的相對適應(yīng)性, 競爭消除了那些不適應(yīng)的假說。……科學(xué)知識的獨特之處是對我們理論的自覺和系統(tǒng)的批判，使得生存斗爭更艱難。”

和其他分類方法相比，利用關(guān)聯(lián)規(guī)則構(gòu)造的關(guān)聯(lián)分類器取得了比較高的分類精度和分類效率[4-5]。然而，傳統(tǒng)的關(guān)聯(lián)分類方法(例如，CBA和CMAR)存在的一個主要的問題就是：在構(gòu)造關(guān)聯(lián)分類器時，需要消耗大量的時間掃描可能的規(guī)則空間。特別是在支持度閾值被設(shè)到一個很小的值時，這一現(xiàn)象更為明顯[6-7]。文獻[8]提出一種被稱為“CPAR”的分類方法，該方法聯(lián)合了關(guān)聯(lián)分類和傳統(tǒng)的基于規(guī)則分類的方法的優(yōu)點。該方法利用貪婪算法直接從訓(xùn)練數(shù)據(jù)中產(chǎn)生規(guī)則，而不像傳統(tǒng)的關(guān)聯(lián)分類方法那樣先產(chǎn)生大量的候選規(guī)則，再生成分類器。文獻[9]提出一種被稱為基于人工免疫算法的關(guān)聯(lián)分類算法(AIS-AC)，該算法只尋找能構(gòu)造有效分類器的規(guī)則的子集來生成分類器，提高了關(guān)聯(lián)分類的效率。楊廣飛等[10]提出了一種叫做“EvoCMAR”的進化的分類方法直接挖掘分類的關(guān)聯(lián)規(guī)則。

本文提出一種基于波普爾知識進化論的知識進化算法(KEA)來有效地生成關(guān)聯(lián)分類器。和以往的算法不同，該方法整合了分類規(guī)則的尋找和分類器的生成，利用猜測與反駁操作來代替?zhèn)鹘y(tǒng)的變異操作，克服了普通的進化算法在關(guān)聯(lián)分類規(guī)則搜索時，過度局部搜索的問題。同時，合理設(shè)計知識的覆蓋度閾值，使之符合構(gòu)造優(yōu)化分類器的要求。

本文剩余部分組織如下：我們首先回顧了關(guān)聯(lián)分類和知識進化的有關(guān)特點；然后提出了用于關(guān)聯(lián)分類的知識進化算法；接著利用實驗對該算法做了相應(yīng)的分析和比較；最后指出了該算法的優(yōu)勢與不足。

2 相關(guān)工作

2.1 關(guān)聯(lián)分類

Liu首先提出了一種關(guān)聯(lián)分類方法[11]，被稱為CBA方法。該方法基于發(fā)現(xiàn)的關(guān)聯(lián)分類規(guī)則來構(gòu)造分類器。關(guān)聯(lián)分類規(guī)則的挖掘和關(guān)聯(lián)規(guī)則的挖掘的不同之處就在于，前者可以同時挖掘用來表示不同分類的頻繁項集，而后者挖掘的是所有的頻繁項集。假設(shè)一個數(shù)據(jù)集是一個標(biāo)準的、由N個實例組成的關(guān)系表，每個實例可以用t個不同的屬性來描述。我們可以把每個實例當(dāng)做一個由若干屬性和一個類標(biāo)簽組成的集合。每個屬性被稱為一個項。

關(guān)聯(lián)分類的框架由以下兩步組成： (1)產(chǎn)生所有的關(guān)聯(lián)分類規(guī)則，形式如“iset=>c”，其中iset表示屬性的集合，c表示類。(2)基于關(guān)聯(lián)分類規(guī)則，構(gòu)造分類器。一般來說，關(guān)聯(lián)分類器的構(gòu)造是基于分類規(guī)則的可信度大小，由關(guān)聯(lián)分類規(guī)則的子集構(gòu)成。

2.2 知識進化的特點

知識的進化過程實質(zhì)上就是已確立的思想習(xí)慣與擴大了的觀察領(lǐng)域的矛盾的不斷消除和適應(yīng)的過程。新知識的產(chǎn)生是一種“識知”的過程，是人腦不斷與自然環(huán)境、社會環(huán)境進行信息交換的過程，是人類通過感覺器官，從外部環(huán)境中獲得各種數(shù)據(jù)、信息與頭腦中存儲的原有知識共同作用的結(jié)果。因此，知識的增長是歷史知識系統(tǒng)與當(dāng)前外部信息交互作用，通過系統(tǒng)內(nèi)部創(chuàng)新，不斷實現(xiàn)適應(yīng)外部環(huán)境的一個動態(tài)過程。該過程遵循著“實踐——認識——再實踐——再認識”的認識發(fā)展辯證途徑[12]。

知識的進化包括質(zhì)的發(fā)展和量的增長兩方面。所謂知識量的增長,是指一定歷史階段人類全部知識總量的增加,而知識質(zhì)的發(fā)展,是指人類知識相對于以前的某一歷史階段在深度和真理度方面的提高。知識的進化是一個歷史性的概念,知識的進化總是需要兩個特征相互對照才能顯現(xiàn)出來。知識無論在量方面的增長,還是在質(zhì)方面的發(fā)展,都應(yīng)包括內(nèi)容方面的進化、形式方面的進化、工具方面的進化等幾個方面同時呈現(xiàn)出上升性的變化趨勢,它們是構(gòu)成知識進化或知識增長的因素。

2.3 試錯法

試錯法與理論推導(dǎo)法相反，是一種常見的解決問題、獲取知識的方法。該方法通過間斷或連續(xù)地改變黑箱系統(tǒng)的參量、試驗黑箱所作應(yīng)答，來尋求達到目標(biāo)的途徑。其中，猜測與反駁是試錯法的兩個重要步驟。通過猜測，我們可以積極創(chuàng)造條件，在已經(jīng)掌握的部分事實材料的基礎(chǔ)上，通過猜測、審查使事物的本質(zhì)全部盡快暴露出來。通過反駁，我們可以在獲得的初步結(jié)論中尋找毛病，發(fā)現(xiàn)錯誤，使認識得到提高[13]。試錯法是猜測與反駁相結(jié)合的方法，該方法是對已有認識的試錯，通過尋找能推翻、駁倒已有認識的反例，并排除這些反例，從而使認識更加精確、科學(xué)。

3 知識進化算法及其在關(guān)聯(lián)分類中的應(yīng)用

3.1 知識的表示

事實： 每次實踐得到的真實結(jié)果。

假說： 是基于事實提出的、對系統(tǒng)相關(guān)特征、邏輯關(guān)系所做出的猜測，是未經(jīng)證實的知識。

反面知識： 是被事實證明錯誤的假說。

在知識進化算法中，一方面，隨著實踐的不斷向前推進，猜測算子不斷產(chǎn)生新的假說。這些假說必須滿足簡單、可獨立檢驗、盡可能長久地不被推翻替代等相關(guān)特性；另一方面，反駁算子不斷將以往產(chǎn)生的猜測知識與本次事實相對比。被證偽的猜測放入

反面知識集，與本次事實相符或無關(guān)的猜測知識，繼續(xù)留在猜測知識庫，等待進一步檢驗。

3.2 知識進化算法框架

知識進化算法的基本框架由以下三部分組成:假說集(Hypotheses Set)、反面知識集(Inaccurate Knowledge Set)和猜測反駁萃取法(Conjecture、Refutation and extraction Method),如圖1所示。

知識進化算法(KEA)的偽代碼如下：

Algorithm KEA-2 Begin t=1 Initialize H0Initialize I0While(the termination condition is not achieved) Ht=conjecture(It-1,Ht-1,Ft) It=refute(Ht-1,It-1,Ft) Ht= Ht+extract(It-1) t=t+1 end reduce end

其中，t為知識進化代數(shù)，H0為初始假說集，I0為初始反面知識集，Ht，It，分別為第t代假說集和反面知識集，F(xiàn)t為第t次事實，conjecture()為猜測函數(shù)，refute()為反駁函數(shù)。

3.3 基于知識進化算法的關(guān)聯(lián)分類

在本文提出的知識進化算法中，將數(shù)據(jù)集中每條記錄看作一個事實，將針對該數(shù)據(jù)集的關(guān)聯(lián)規(guī)則看作知識。算法利用提出的猜測與反駁算子代替?zhèn)鹘y(tǒng)進化算法中的選擇、交叉、變異等操作。

3.3.1 事實及知識的編碼

知識進化算法中的編碼方式包含實值編碼、二進制編碼和符號編碼，具體使用哪種編碼方式應(yīng)該由算法的應(yīng)用背景決定。本算法中考慮到關(guān)聯(lián)分類規(guī)則的復(fù)雜性，將知識進化算法的編碼原則定義為根據(jù)事實或知識個體中屬性值的不同，采用不同的編碼方式對屬性進行編碼，最后，將這些編碼按一定順序連接，組成個體。

如圖2所示，本文中按屬性不同，將事實分割為不同的基因段， Ui表示條件屬性，V表示決策屬性。

圖2 事實的編碼

規(guī)則知識，包含假說知識和反面知識，采用與事實類似的編碼方式，考慮到知識規(guī)則的簡單性，將規(guī)則知識中不包含的屬性所對應(yīng)的基因段的值為“O..O”(“O”的個數(shù)表示該基因段的長度)。具體情況見圖3。

圖3 知識的編碼

3.3.2 猜測算子

標(biāo)準進化算法中變異算子的基本內(nèi)容是對個體基因座上的基因值作相應(yīng)變動，其目的是提高算法的局部隨機搜索能力，并維持群體多樣性，其特點是隨機性、無邏輯性。知識進化算法中猜測算子其基本內(nèi)容也是對個體基因座上的基因值作相應(yīng)變動，然而這種變動本身強調(diào)的是知識體系之間的邏輯性和關(guān)聯(lián)性，因而，邏輯推理是猜測算子得以進行的主要手段。

域Di： 組成實例的某個條件屬性所對應(yīng)的所有屬性值與空值(用“O..O”表示)做并運算，就構(gòu)成了某個屬性的全域。

規(guī)則知識空間： 由條件屬性和決策屬性形成的一組域的迪卡爾積，可表示為式(1)。

(1)

其中，每條記錄被稱為一條規(guī)則知識。

猜測知識群： 將實踐產(chǎn)生的事實中每個條件屬性的值與空值做并運算，然后將所產(chǎn)生的不同條件屬性的域及決策屬性做迪卡爾積，就得到了某條事實所對應(yīng)的猜測知識群R0，可表示為式(2)。

R0=D1′×D2′×...×Dn′?D1×D2×...×Dn=R

(2)

猜測操作： 順序考察R0中每條知識ri(d1,d2,...,dn)，若ri∈Rd(Rd為反面知識庫)，則將Rd中該條反面知識ri的覆蓋數(shù)量Cri加1；若ri∈Rh(Rh為猜測知識庫), 則將Rh中該條猜測知識ri的覆蓋數(shù)量Cri加1；若ri?Rh且ri?Rh,則根據(jù)簡單性原則按猜測概率p(ri)產(chǎn)生猜測知識ri，并將其放入猜測知識庫Rh。

其中，猜測概率p(ri)可表示為p(ri)=1/L(ri),(L(ri)為該條知識ri所包含非空條件屬性的個數(shù))。

3.3.3 反駁算子

排除錯誤是知識進化的本質(zhì)，反駁算子通過與當(dāng)前實踐的對比，來減少猜測知識的錯誤，并確保理論的被接受及運用。

定義1 AND*運算符,表示將兩個二進制操作數(shù)按位進行邏輯與運算。

① 將當(dāng)前事實對應(yīng)分解為條件屬性組合ri1′和決策屬性組合ri2′；初始化猜測知識變化i(i=1)和最大猜測知識數(shù)量I。

② 若 i<=I, 則提取猜測知識庫Rh中第i條猜測知識ri(d1,d2,...,dn)，將其分解為條件屬性組合ri1和決策屬性組合ri2。

③ 反駁操作：

IF (ri1 AND* ri1′= ri1 AND ri2 <> ri2′) THEN (F(ri)= F(ri)+1； AND Rd=Rd ∪ ri)；

IF (ri1 AND* ri1′= ri1 AND ri2 = ri2′) THEN (C(ri)= C(ri)+1)；

IF (ri1 AND* ri1′ <> ri1) THEN (do nothing);

i=i+1；

轉(zhuǎn)步驟②。

3.3.4 萃取算子

算法中，萃取算子的主要作用是不斷統(tǒng)計反面知識庫中每條知識的反駁度F(ri)。當(dāng)反駁知識庫中某條知識的反駁度低于某個給定閾值時，將該條知識轉(zhuǎn)移到猜測知識庫中，繼續(xù)進行正確度判斷。

反駁度Re(ri): 一條知識規(guī)則ri的反駁度F(ri)是通過統(tǒng)計該條知識規(guī)則的反駁數(shù)量與覆蓋數(shù)量來衡量的,計算公式如式(3)。

(3)

其中，F(xiàn)(ri)表示記錄ri的反駁計數(shù)個數(shù)，C(ri)表示記錄ri覆蓋的元組數(shù)。

3.3.5 知識的覆蓋度與正確度

覆蓋度C(ri)： 猜測知識庫或反駁知識庫中知識規(guī)則ri的覆蓋度C(ri)，是指該規(guī)則的條件屬性部分所能覆蓋的數(shù)據(jù)集D中的實例個數(shù)。計算公式如式(4)所示。

(4)

其中，|D|表示數(shù)據(jù)集D中實例總數(shù)，N(ri)表示ri覆蓋的實例數(shù)。

正確度A(ri)： 知識規(guī)則ri的正確度A (ri)是指測試數(shù)據(jù)集D中， ri的所有非空條件屬性及決策屬性所能覆蓋的實例個數(shù)與所有非空條件屬性所能覆蓋的實例個數(shù)之比。計算公式如式(5)。

(5)

其中，N(ri)′表示ri正確分類的實例數(shù)，N(ri)表示ri覆蓋的實例數(shù)。

3.3.6 知識的約簡

知識約簡的目的是： 使最終得到的猜測知識集具有更少的規(guī)則知識條數(shù)。知識約簡的方法： 將猜測知識庫Rh中的每條猜測知識ri(d1,d2,...,dn)按支持度從大到小排序，當(dāng)前m條知識所覆蓋的記錄總數(shù)超過該數(shù)據(jù)集的覆蓋度閾值時，前m條知識就是本算法所求的精簡后的知識集，該集合用來生成分類器。

3.3.7 知識進化算法的實現(xiàn)步驟

知識進化算法的實現(xiàn)步驟如下：

步驟1 讀入一個數(shù)據(jù)塊的記錄(事實)，通過對該記錄塊的分析,將獲得的猜測知識加入到猜測知識庫；

步驟 2 讀入一個新的數(shù)據(jù)塊，利用反駁算子檢驗猜測知識庫中知識是否與新讀入數(shù)據(jù)塊中事實相矛盾。若矛盾，則將該知識投入反面知識庫。

步驟3 利用猜測算子產(chǎn)生針對該數(shù)據(jù)塊的新的猜測知識，將其加入到猜測知識庫中。

步驟4 判斷猜測知識庫中所有知識的覆蓋度，若超過預(yù)定的閾值，算法停止。否則，轉(zhuǎn)步驟2。

4 仿真實驗

我們在配置為： 主頻3.0 GHz、內(nèi)存512MB、操作系統(tǒng)Microsoft Windows XP的Pentium PC機上對提出的算法進行了實驗。實驗用到的數(shù)據(jù)集來自于UCI機器學(xué)習(xí)的專業(yè)數(shù)據(jù)集[34]。

4.1 不同參數(shù)的效果

我們對比了不同數(shù)據(jù)塊規(guī)模對分類精度及分類器中知識數(shù)目的影響，發(fā)現(xiàn)數(shù)據(jù)塊規(guī)模對分類器的分類精度影響很小，但是對分類規(guī)則(知識)的數(shù)目影響較大。從圖4可以看到，當(dāng)數(shù)據(jù)塊規(guī)模設(shè)置為1 000，2 000,3 000,4 000及6 000條規(guī)則，最小支持度門限設(shè)置為10%時，得到的分類器的分類精度極為類似。然而，在以上各種情況下，分類器中規(guī)則的數(shù)目差距是比較大的，且隨著數(shù)據(jù)塊規(guī)模的增大，發(fā)現(xiàn)的規(guī)則的數(shù)目越來越少。

圖4 數(shù)據(jù)塊大小對分類精度及分類規(guī)則數(shù)目的影響

我們進一步驗證了數(shù)據(jù)塊規(guī)模對算法運行時間的影響，發(fā)現(xiàn)： 對于相同的數(shù)據(jù)集(圖5中左圖)，算法的運行時間隨著數(shù)據(jù)塊的規(guī)模的增加而變的越來越長。對于不同的數(shù)據(jù)集(圖5中右圖)，算法的運行時間主要由記錄的屬性個數(shù)和數(shù)據(jù)集中項的個數(shù)總和來決定。從圖5中可以看到，四個不同的數(shù)據(jù)集Nursery、Krkopt、Poke和Adult的屬性的個數(shù)分別為： 8、6、10、14。它們的項的總數(shù)分別為： 27、

圖5 數(shù)據(jù)塊大小對算法運行時間的影響

圖6 不同支持度門限對算法的影響

40、85、127。盡管數(shù)據(jù)塊大小和支持度門限被設(shè)為相同的值，算法針對這四種數(shù)據(jù)集的運行時間的差距還是很大的。并且隨著項和屬性數(shù)目的增加，運行時間變的越來越長。

當(dāng)數(shù)據(jù)塊規(guī)模被設(shè)置為2 000條記錄時，我們測試了所提出算法的性能，并且發(fā)現(xiàn)： 隨著支持度門限的降低，分類器的分類精度越來越高；但是分類器中分類規(guī)則的數(shù)目也變的越來越多。

4.2 算法的比較

我們將所提出的知識進化算法KEA-1與文獻[8]中所提出的CBA算法做了比較。在CBA算法中，最小可信度被設(shè)置為50%，數(shù)據(jù)塊規(guī)模被設(shè)置為1 000條。兩種算法的支持度門限統(tǒng)一設(shè)置并被表示在表1中。其中第1列表示數(shù)據(jù)集名稱，第2列表示數(shù)據(jù)集屬性個數(shù)，第3列表示類個數(shù)，第4列表示支持度門限，第5～6列表示CBA算法的分類精度和該算法需要用到的內(nèi)存規(guī)模(容納記錄條數(shù))，第7～8列表示KEA算法的分類精度和需要用到的內(nèi)存規(guī)模。

表1 算法對比

續(xù)表

我們對來自UCI數(shù)據(jù)集中的六個標(biāo)準數(shù)據(jù)集作了對比分析，發(fā)現(xiàn)CBA算法的平均分類精度略高于KEA算法。然而，CBA算法需要用到的存儲空間要遠遠高于算法KEA。CBA算法是靜態(tài)分類算法，該算法需要多次掃描整個數(shù)據(jù)集來生成分類器。所以，為了加速分類器的構(gòu)造，需要將數(shù)據(jù)集中所有數(shù)據(jù)讀入內(nèi)存。而KEA算法是動態(tài)分類器構(gòu)造算法，該算法不需一次讀入所有數(shù)據(jù)集中記錄。只需分塊讀入該數(shù)據(jù)集，就可以掃描一次數(shù)據(jù)集進而構(gòu)造分類器。所以，其優(yōu)勢是顯而易見的。

4.3 算法的比較2

為了解決KEA算法的分類精度低于CBA算法的問題，我們將猜測與反駁過程中的統(tǒng)計數(shù)據(jù)引入到知識的正確程度的判定中來，提出算法KEA-2。當(dāng)猜測知識庫中的某條知識的正確度A(ri)低于某個閾值Ф1=0.9時，將其放入反面知識庫。隨著事實的不斷檢驗，當(dāng)反面知識庫中的某條知識的反駁度Re(ri)低于某個閾值Ф2=0.1時，將其放回猜測知識。我們對上節(jié)的六個標(biāo)準數(shù)據(jù)集重新做了對比分析，發(fā)現(xiàn)： 在計算速度變化不大的前提下，通過修改算法流程并引入兩個閾值Ф1、Ф2，KEA算法的分類精度得到了明顯的提升，這兩種算法的平均分類精度非常類似。然而，CBA算法需要用到的存儲空間要遠遠高于算法KEA。CBA算法是靜態(tài)分類算法，該算法需要多次掃描整個數(shù)據(jù)集來生成分類器。所以，為了加速分類器的構(gòu)造，需要將數(shù)據(jù)集中所有數(shù)據(jù)讀入內(nèi)存。而KEA算法是動態(tài)分類器構(gòu)造算法，該算法不需一次讀入所有數(shù)據(jù)集中記錄。只需分塊讀入該數(shù)據(jù)集，就可以掃描一次數(shù)據(jù)集進而構(gòu)造分類器。所以，其優(yōu)勢是顯而易見的。

表2 算法改進前后對比

5 結(jié)論

KEA-1算法在考慮是否是反面知識的過程中，一次判斷就確定知識的真?zhèn)?，可能會有一些偶然性。因此，在KEA-2算法中通過引入統(tǒng)計數(shù)據(jù)以及判定閾值Ф1來解決此類問題。實驗中將Ф1設(shè)為0.9時，得到了較為滿意的結(jié)果。

總之，該算法是建立在人類認識論的基礎(chǔ)之上的一種算法。該算法依靠邏輯推理和實踐驗證，使知識得到的進化，進而抽象出可全面描述某一復(fù)雜系統(tǒng)的知識體系。這一領(lǐng)域還有很多工作要做，從理論上證明該算法的完備性和正確性，對該算法的效率進行分析，增加該算法對時變系統(tǒng)的支持，對該算法的應(yīng)用領(lǐng)域的擴展等等,都是今后研究的重點。

[1] Das S, Suganthan P N. Differential Evolution: A Survey of the State-of-the-Art [J]. IEEE Transactions on Evolutionary Computation, 2011,15(1): 4-31.

[2] Ashlock D. Computational Intelligence in Bioinformatics [J]. Computational Intelligence Magazine, 2009,4(4): 60-61.

[3] 卡爾·波普爾. 猜測與反駁:科學(xué)知識的增長[M]. 上海:上海譯文出版社, 1986.

[4] R. Agrawal, R. Srikant, Fast algorithms for mining association rules[C]//Proceedings of the 20th International Conference Very Large Data Bases(VLDB),1994:487-499.

[5] J Han, J Pei, Y Yin. Mining frequent patterns without candidate generation[C]//Proceedings of 2000 ACM SIGMOD Intl. Conf. Manage Data, 2000:1-12.

[6] W Li, J Han, J Pei. CMAR: Accurate and efficient classification based on multiple class association rules[C]//Proceedings of the IEEE International Conference on Data Mining (ICDM01), 2001:369-376.

[7] B Liu, Y Ma, C K Wong. Classification using association rules: Weaknesses and enhancements[C]//Proceedings of the Data Mining for Scientific and Engineering Applications, Berlin,Germany:Springer-Verlag,2001

[8] X Yin, J Han. Cpar: Classification based on predictive association rules[C]//Proceedings of the 2003 SIAM International Conference Data Min.(SDM′03),2003.

[9] Tien Dung Do, Siu Cheung Hui, Bernard Fong. Associative classification with artificial immune system [J], IEEE Transactions on Evolutionary Computation, 2009,13(2), 2009: 217-228.

[10] Guangfei Yang, Shingo Mabu, Kaoru Shimada, et al. A New Associative Classification Method by Integrating CMAR and An Evolutionary Three-layers Structure[C]//Proceedings of ICCAS-SICE, 2009: 2920-2925.

[11] B Liu, H Hsu, Y Ma. Integrating classification and association rule mining[C]//Proceedings of the 4th International Conference Knowledge Discovery and Data Mining (KDD98), 1998: 80-86.

[12] 何云峰.從普遍進化到知識進化[M]，上海:上海教育出版社，2001.

[13] 嚴太山,崔杜武.知識進化算法研究[J].計算機工程與應(yīng)用，2008,44(26): 8-11.

梁紅碩(1979—),碩士,講師,主要研究領(lǐng)域為進化計算、人工智能。E-mail:lianghs_sjzpt@163.com劉云橋(1973—),碩士,講師,主要研究領(lǐng)域為數(shù)據(jù)挖掘、知識發(fā)現(xiàn)。E-mail:67465984@qq.com趙理(1974—),博士后,副教授,主要研究領(lǐng)域為智能計算、流挖掘。E-mail:zhaoli@bit.edu.cn

第二十一屆全國信息檢索學(xué)術(shù)會議(CCIR2015)在洛陽成功召開

8月22—25日，第二十一屆全國信息檢索學(xué)術(shù)會議(CCIR2015)在洛陽順利召開。本次會議由中國中文信息學(xué)會和中國計算機學(xué)會聯(lián)合主辦、洛陽外國語學(xué)院承辦。參加本次會議的代表來自全國從事信息檢索理論與應(yīng)用研究的近70所高校和科研機構(gòu)，共260余人，既有享譽國內(nèi)外學(xué)術(shù)界和產(chǎn)業(yè)界的資深專家，也有嶄露頭角的青年學(xué)者。

洛陽外國語學(xué)院的領(lǐng)導(dǎo)出席了會議開幕式并致辭。中國中文信息學(xué)會副理事長兼秘書長孫樂研究員、中國計算機學(xué)會理事長鄭緯民教授、中國中文信息學(xué)會信息檢索專委會主任白碩研究員出席了開幕式并致辭。

本屆會議共收到論文176篇。通過通信評審和程序委員會會議復(fù)審兩個階段，最終確定錄用論文122篇，錄用率約為69%，錄用的論文總體反映了國內(nèi)在信息檢索領(lǐng)域的最新成果。會議評出5篇優(yōu)秀學(xué)生論文，并頒發(fā)優(yōu)秀學(xué)生論文獎證書。

本次會議有幸邀請到中國科學(xué)院計算技術(shù)研究所倪光南院士、中國科學(xué)院自動化研究所王飛躍研究員、華為公司諾亞方舟實驗室主任李航教授、微軟研究院首席研究員周明博士作了大會特邀報告。微軟亞洲研究院林欽佑博士、史樹明博士和中國科學(xué)院計算技術(shù)研究所徐君博士分別作了大會專題講習(xí)班。中科院自動化所劉康副研究員、復(fù)旦大學(xué)邱錫鵬副教授作了青年學(xué)者論壇報告。由阿里UC移動

事業(yè)群技術(shù)總監(jiān)陳一寧博士、搜狗搜索研究部負責(zé)人許靜芳博士、復(fù)旦大學(xué)張奇副教授、中國科學(xué)院計算技術(shù)研究所徐君博士共同完成了主題為“移動搜索的產(chǎn)品與技術(shù)變革”的Panel。此外，本次會議還進行了信息檢索相關(guān)產(chǎn)品展示，舉辦了“第七屆中文傾向性分析評測”(COAE2015)。會議錄用的所有論文均在分組會上進行了宣讀和poster展示。

會議期間，圍繞信息檢索、文本分類、聚類及挖掘、多媒體檢索、社會媒體分析等學(xué)術(shù)前沿問題，與會代表們展開了熱烈深入的研討，大家各抒己見，暢所欲言，學(xué)術(shù)氣氛十分濃厚、活躍。

國雙公司、搜狗公司、百度公司、拓爾思公司、明略公司、捷通華聲語音技術(shù)公司為本次會議提供了必要的贊助支持，特此深致謝忱！經(jīng)過CCIR指導(dǎo)委員會與信息檢索專委會聯(lián)席會議討論決定，第二十二屆全國信息檢索學(xué)術(shù)會議(CCIR2016)由華南理工大學(xué)承辦。

全國信息檢索學(xué)術(shù)會議瞄準國家重大戰(zhàn)略需求，關(guān)注國內(nèi)外信息檢索研究領(lǐng)域的最新進展，對本領(lǐng)域面臨的種種挑戰(zhàn)性科學(xué)問題和關(guān)鍵性技術(shù)難題展開了深入研討，力爭為提升我國信息檢索學(xué)術(shù)研究的整體水平作出新貢獻。本次會議獲得了圓滿的成功，不僅促進了相關(guān)學(xué)科領(lǐng)域與IT界的學(xué)術(shù)交流，而且增進了同行之間的學(xué)術(shù)友誼。

Knowledge Evolutionary Algorithm and Its Application for Associative Classification

LIANG Hongshuo1, LIU Yunqiao1, ZHAO Li1,2

(1. Shijiazhuang Vocational Technology Institute, Shijiazhuang, Hebei 050081, China；2. Beijing Institute of Technology, Beijing 100081, China)

To avoid the repeated exhaustive search of the data in classical associative classification approaches, a knowledge evolutionary algorithm based on evolutionary epistemology is proposed. Firstly, data in the data set is encoded. Secondly, the hypotheses knowledge and inaccuracte knowledge are gained by conjecture and refutation operator. Thirdly, the coverage and accuracy of the hypotheses and inaccurate knowledge are calculated. Then, an extraction operator is used to extract rules from library of inaccurate knowledge and to put them into hypotheses library. Finally, the knowledge obtained with this method was used to build a classifier. In this way, the dataset can be read in a computer partly and the whole times used for read in and read out were reduced largely. The results have shown that knowledge evolution algorithm can speed up the calculation process under the guarantee of similar accuracy of classification.

knowledge evolution; conjecture; refutation; associative classification

1003-0077(2015)04-0126-08

2013-06-26 定稿日期： 2015-04-09

中國博士后科學(xué)基金(2013M530534); 河北省教育廳科學(xué)研究計劃(Z2014181);國家自然科學(xué)基金(61272283；60873035);河北省人社廳項目(JRS-2014-1103)

TP

A