知識發現系統框架及其理論體系的構造方法論

楊炳儒

(北京科技大學計算機與通信工程學院,北京 100083)

1 前言

數據庫中的知識發現(KDD,knowledge discovery in database)是一門新興的交叉學科。通過對現今各種KDD系統十幾年的跟蹤可見:不同領域學者對其研究的視角不同,主要包括從數據庫的角度進行研究,它強調知識發現的效率(efficiency)[1,2];從機器學習的角度進行研究,它強調知識發現的有效性(effectiveness)[3,4];從統計分析的角度進行研究,它強調知識發現的正確性(valid)[5,6];從微觀經濟學的角度進行研究[7],它強調的是知識發現的最大效用。2003年8月27日在華盛頓召開了第九屆知識發現與數據挖掘國際會議,參與討論的專家一致認為:“數據挖掘正面臨著巨大的機遇和挑戰”;“從科學發展的長遠來看,最大的絆腳石是基礎理論的缺乏以及所面臨的問題和挑戰的清晰明白的闡述”[8]。

目前,許多有關知識發現的研究或者沒有深入探討其理論基礎,或者沒有給出具體的實現方法。因此,無法從根本上明顯提高現有知識發現過程的性能,也無法解決KDD發展過程中極富挑戰性的一些問題。事實上,有關知識發現的研究成果只是提供了KDD的方法論基礎,而要真正構建其理論體系,必須抓住KDD的本質,形成與其本質相適應的理論基礎。KDD的本質何在?至少有兩個可信的路徑:一個是將KDD過程(系統)視為認知過程(系統),不是轉化為認知系統中;另一個是將KDD過程(系統)視為非線性動力系統中非平衡態轉化的過程(系統)。筆者從前者出發,經近十余年的研究得到如下結果。

2 基于認知沿機理—模型—算法線路構造的自主知識發現“系統框架”

現代研究表明:分層遞階結構是降低系統復雜度的最有效的處理手段,而有序的粒度空間理論是建立復雜系統的分層遞階結構最有效的手段之一。筆者構造了一類以內在機理為理論支柱、以過程模型與挖掘算法為上層建筑的多層遞階的知識發現“系統框架”MMAKDS—沿機理—模型—算法線路構造的自主知識發現“系統框架”,其根源是將認知科學(認知心理學等)的基本原理嫁接到知識發現領域中的結果;形成了以認知自主性為貫穿主線的帶有普遍意義的“系統框架”,其結構見圖1所示。

圖1 MMAKDS系統框架圖Fig.1 MMAKDS system framework

2.1 內在認知機理

認知心理學興起于20世紀50年代中期,它是以信息加工觀點為核心的心理學,其核心是揭示認知過程的內部心理機制,即信息是如何獲取、貯存、加工和使用的。在知識發現系統中,模擬“創建意象”和“心理信息修復”這兩項認知心理特征進而提高系統的認知自主性,正是研究的出發點。

利用認知心理學的兩個重要特征(即“創建意象”與“心理信息修復”)來研究知識發現的兩個重要主題,從而對知識發現的過程模型進行創新。具體而言:a.通過模擬“創建意象”來實現系統自主發現知識短缺,實施啟發式的聚焦(除用戶感興趣式的聚焦外)。為此,筆者構造了啟發型協調器來模擬“創建意象”,從而實現系統自主地發現知識短缺;該協調器由啟發型協調算法來實現[9]。b.通過模擬“心理信息修復”來實現知識庫的實時維護。為此,構造了維護型協調器來模擬“心理信息修復”,從而實現知識庫的實時維護;該協調器由維護型協調算法來實現[9]。

實現上述兩個協調器(算法)的核心技術是要采取“定向搜索”和“定向挖掘”;從而,等效地縮小搜索空間、降低算法的復雜度。為此,在幾類布爾代數及其關系的理論基礎之上,在數據庫和知識庫的特定構造下,構建了挖掘數據庫中數據子類結構的層與挖掘知識庫中知識素結點間的一一對應關系(見圖2),稱之為“雙庫協同機制”[9]。“雙庫協同機制”從一個特定角度揭示知識發現的潛在規律與復雜性。至今這種深入到其系統內部探索規律(內在機理)的研究,實屬罕見。

2.2 新過程模型——KDD*

將雙庫協同機制及其支持下的兩個協調器的構造,融入經典的KDD過程中,形成筆者獨立提出的KDD*新過程模型,從根本上改變了原有的知識發現進程與運行機制。KDD*過程模型見圖3所示。

1)原有的知識發現過程模型KDD在如下技術與功能方面存在著不足之處:a.領域知識不能實質性地介入到數據挖掘(知識發現)過程中。b.系統不能自主地實現對短缺知識需求和挖掘。c.僅根據用戶的興趣度產生聚焦,確立挖掘方向,會導致大量重復、冗余規則的產生;與系統自身挖掘的短缺知識不能較好地吻合。d.不能對知識庫進行動態實時維護。e.模型的實現是基于語義層面的。

圖2 數據子類結構的層與知識素結點之間的對應關系Fig.2 Mapping between the layer of data sub-class structure of the database and primitive knowledge node of knowledge base

圖3 KDD*過程模型Fig.3 KDD*process model

2)KDD*過程模型針對上述各種不足給出了具體的創新方法和實現技術,具體列下:a.在挖掘的過程中,領域知識通過兩個協調器直接地、具體地介入到挖掘過程中,其主要思想來源是借用同步進化和協同計算的思想。b.系統能通過有向超圖[10]的鄰接矩陣產生定向聚焦,自主地實現對短缺知識需求和挖掘。c.聚焦問題:定向挖掘的方向與進程當且僅當在用戶“感興趣點”與系統自主發現的“短缺知識點”相吻合的情況下才能產生。這樣,不至于挖掘出大量重復、冗余的知識,大大減少規則評價量。這樣做的主要目的是減少搜索空間,提高了算法的效率,為算法能通過處理少量數據而達到挖掘效率提供了必要的技術支持。d.隨著知識的積累,知識庫的知識也會越來越多,為了能快速地對應用問題做出反映,在新模型中加入了維護協調器,有效地、動態地、實時地處理了知識的重復、冗余、矛盾、循環與從屬。e.新模型是基于認識心理學的“創建意象”與“心理信息修復”兩個認知特征的,故新的模型有堅實的理論基礎;模型的實現是基于理論層面的。

3)KDD*相對于 KDD而言,是 KDD與雙庫協同機制相融合的一種知識發現的新結構,它具有以下特征:a.KDD*有機地溝通與融合了KDD*新發現的知識與基礎知識庫中固有的知識,使它們成為一個有機的整體,即實現了“用戶的先驗知識與先前發現的知識可以耦合到發現過程中”。b.在知識發現過程中,KDD*對于冗余性的、重復性的、不相容的信息做出了實時處理,有效地減少了由于過程積累而造成的問題的復雜性,同時為新舊知識的融合提供了先決條件,實現了“知識與數據庫同步進化”[11]。c.在數據庫的數據積累過程中,雖然知識庫結構具有一定的穩定性,但它也是隨著數據的積累而不斷進化的,并且這種進化的能力是雙庫協同機制本身所具有的,無須領域專家的干預。d.KDD*改變與優化了知識發現的過程與運行機制,實現了“多源頭”聚焦與減少評價量。e.從認知科學的角度看,KDD*強化并提供了知識發現的智能化程度,提高了認知自主性(這將是今后相當長的一階段內保持的研究基調),較有效地克服領域專家的自身局限性,實現了“采用領域知識輔助初始發現的聚焦”[12]。f.作為KDD*的核心技術——雙庫協同機制的研究,揭示了在一定的建庫原則下,知識子庫與數據子類結構之間的對應關系,為實現“限制性的搜索”而減小搜索空間、提高挖掘效率提供了有效的技術保證[13,14]。g.雙庫協同機制與其誘導的新結構模型KDD*,對知識發現的主流發展有著重要的作用,由此派生出新的關聯規則與數據聚類規則的挖掘算法,與目前流行的算法對比,具有更好的可擴展性與有效性。

在KDD*的基礎上,還誘導出 KD(D&K)過程模型[15]以及針對復雜類型數據挖掘的DFSSM過程模型[16]等,此不贅述。

2.3 新挖掘算法——Maradbcm

在雙庫協同機制與KDD*的基礎之上,提出了挖掘關聯規則的Maradbcm算法(以下簡稱M算法)[17],具體流程與步驟不再贅述。現僅將M算法與挖掘關聯規則的權威算法Apriori算法及其改進型在理論上作一典型的對比分析:

1)基于的學術思想不同:M算法是基于雙庫協同機制的內在認知機理研究,具體而論是基于“知識短缺”(利用有向超圖)進行“定向挖掘”以及知識庫的實時維護;而Apriori算法及其改進型是基于組合論的數據庫全局搜索。

2)基本流程(或基于的過程模型)不同:M算法是一條一條短缺知識的挖掘;而Apriori算法及其改進型是所有的規則一并挖掘。

3)基礎不同:M算法是基于規則強度,它考慮了主觀和客觀兩個方面;涵蓋了Apriori算法及其改進型的支持度閾值。

4)發現知識的量不同:在M算法中知識庫直接參與挖掘過程,從而能真正發現新穎的、用戶感興趣的知識,這正是符合了KDD定義;而Apriori算法及其改進型是把滿足條件的規則全部挖掘出來;另外,由于M算法中的支持度可以設置得比較小(因為該算法主要是由規則強度來聚焦的),即對短缺知識的刪除是比較謹慎的,因此M算法部分地克服了Apriori算法及其改進型的一個缺陷——遺漏重要規則。

5)M算法可融入KDD中形成新的開放型的過程模型——KDD*,整個算法實現的運算背景是KDD*結構;而 Apriori算法及其改進型是原有的KDD過程模型。

3 基于內在認知機理的知識發現理論體系——KDTICM 的構造

這種“系統框架”的研究是構造知識發現理論體系的有效路徑。事實上,從縱向研究:筆者從認知心理學、認知物理學、認知生物學等不同的角度出發,先后發現了4條機制,即雙庫協同機制(如前)、雙基融合機制(揭示了基于數據庫的知識發現模型與基于知識庫的知識發現模型的邏輯等價)、信息擴張機制(揭示了動態挖掘進程中規則參數的演變規律)、免疫進化機制(揭示了動態挖掘進程中人工免疫與進化演算的協同性),從而對應于每個機制構建了相互獨立的4類”系統框架”。再從橫向研究:對4類“系統框架”進行整合集成,交叉融合,在此過程中誘導出8個新過程模型,派生出17種新技術方法,最終構建了見圖4所示的一類基于內在認知機理的知識發現理論體系KDTICM。

4 理論體系有效性與先進性的佐證

以上述的KDTICM理論體系及其構造為指導,筆者針對蛋白質二級結構預測——生物信息學領域中的國際性難題,提出了具有普適性的智能預測系統模型——復合金字塔模型。它采取了逐步求精、多層遞階的4層架構,各個層次各有側重、功能相對獨立且通過智能接口無縫對接,其模型架構見圖5所示。

圖4 KDTICM理論體系圖Fig.4 KDTICM theoretical system

圖5 復合金字塔模型Fig.5 Compound pyramid model(CPM)

綜合分析層綜合了改進的同源性分析方法與優化的SVM類化方法,即綜合了物化屬性分析與結構序列分析結果,是整個模型的基礎層,可以完成50%以上的特征明顯的待測氨基酸二級構象的預測,其中同源序列[18]分析采用Apssp2方法,是一種較為成熟的基于多序列匹配的蛋白質二級結構預測方法;SVM多分類(SVM multiple classification)[19]模塊是將懲罰性因子與隨機采樣引入到SVM方法中,采用屬性與結構相結合“輪換式”多分類方法。

核心判定層的原理基于二級結構間的關聯影響,也即二級結構之間構象影響信息,其核心理論基礎為前述基于內在認知機理的知識發現理論KDTICM,工具為該理論下的KDD*過程模型及其Maradbcm算法。通過與相關關聯規則方法的比較,可以發現Maradbcm算法在相同的支持度與可信度下,通常可以獲得更多的規則。SAC方法依據蛋白質二級結構的臨近信息以及KDD*挖掘得到的蛋白質知識庫,利用CMAR(classification based on multiple association rules)算法進行蛋白質二級結構的多分類預測。CMAR[20]作為經典關聯分類預測方法CBA的改進類型,突破了使用單一規則進行預測的方法,而是使用了多條滿足條件的關聯規則進行聯合預測。

輔助判定層的核心同SAC一樣是筆者獨立提出的 AAC(attribute association classifier)[21]模塊。通過對氨基酸物化屬性的關聯分析,建立精化規則庫,然后利用改進的CBA算法,對下兩層無法判斷數據進行預測。

優化層主要設計傾向性因子、位能函數及合情推理3類方法。前兩類方法屬于生物信息學的固有方法,其主要利用生物信息背景知識進行結構預測。合情推理方法是建立在各種二級結構具備的不同物化屬性規律基礎上的。3種方法從不同角度對其下3層的結果加以優化,以最大程度提高整體預測精度。

筆者使用了3種不同的數據集,以開發和測試CPM及其新方法。所選擇的測試集為RS126[22]數據集、CB513[23]數據集和 CASP8[24]數據集。同時采用Q3標準作為評價指標,其定義為預測正確的氨基酸數與氨基酸總數的比值,見式(1)。這個評分只依賴三個狀態(螺旋/折疊片/卷),因此它的名字取為Q3。在整個的三態預測正確的殘基準確度的定義(Q3)是測量預測性能的。

二級結構的每個類型的殘基的準確性(QH,QE,QC,,,)的計算公式為(2)、(3):

這里的i分別代表H,E或 C。

CPM的每一層的結果顯示在表1和表2中。同時,筆者與最好的6個二級結構預測的方法(包括PSIPRED[19],SSPRO[25],SAM-T02[26],PHD Expert[27],PROF[28],JPRED[29])在 RS126和 CB513數據集上進行對比實驗。實驗結果顯示見圖6。對于數據集CASP8,筆者選擇預測結果最好的4個方法作為對比對象,實驗結果顯示見圖7。

表1 每個層預測的準確性和在RS126數據集上的CPM的范圍Table 1 Each layer pridiction accuracy and scale of CPM on the RS126 data set

表2 每個層預測的準確性和在CB513數據集上的CPM的范圍Table 2 Each layer pridiction accuracy and scale of CPM on the CB513 data set

圖6 在RS126和CB513數據集上CPM與其他研究結果的Q3準確度比較Fig.6 Q3 accuracy comparison with other research results seperately on the RS126 and CB513 data set

對典型的研究文獻回顧:Hu使用SVM方法[31]使準確度達到78.8%(在RS126數據集上);Xie[32]使用神經網絡得到了79.65%和69.11%(分別在RS126和CB513數據集上);Chen[33]使用層次的神經網絡得到74.38%的準確度(在 RS126數據集上);Chopra[34]使用細胞自動機方法得到了58.21%和56.51%的準確度(分別在 RS126和CB513上);Liu[35]使用文章分析的方法分別在RS126和CB513數據集上得到了69.8%和69.6%的準確度,Guo[36]使用了雙層SVM方法在CB513數據集上得到了75.2%準確度;Wang[37]使用了優化的SVM方法在CB513數據集上得到了78.44%的準確度。實驗結果見圖8和圖9。

可以看到:CPM的預測精度比其他方法都要高。需要指出的是,筆者可以進一步優化和改善CPM方法,使得預測結果更準確。此國際性難題的典型實例充分佐證了KDTICM理論體系及其構造方法的有效性,并體現了它的科學價值與實用價值。

圖7 在CASP8數據集上CPM與其他4種方法的預測結果對比Fig.7 Comparison with the results of 4 methods on the CASP8 data set

圖8 RS126數據集上Q3準確率比較Fig.8 Q3 accuracy comparison with typical literature on RS126

圖9 CB513數據集上Q3準確率比較Fig.9 Q3 accuracy comparison with typical literature on CB513

5 結語

經過十余年的研究,在對雙庫協同機制的內涵、知識庫及其結構、數據庫及其結構、兩庫間在本質上的對應關系研究的基礎上,提出了在知識發現系統與過程中,兩個用于模擬認知心理特征從而實現系統自主地發現知識短缺和進行知識庫的實時維護的兩個協調器構造的理論基礎與技術實現方法;作為前者的邏輯必然,誘導出KDD*新過程模型;由雙庫協同機制與KDD*派生出新的M算法,由此提出了一類由機理—模型—算法構造線路經融合與集成而構造的自主知識發現系統框架MMAKDS,進而構建出基于內在認知機理的知識發現理論體系KDTICM。最后,在蛋白質二級結構預測實踐中,驗證了自主知識發現系統框架MMAKDS及知識發現理論體系KDTICM的有效性與先進性。

理論分析與實驗證實:基于內在認知機理的自主知識發現系統框架及知識發現理論體系的研究,對KDD的主流發展將起到重要的推動作用,對“從科學發展的長遠來看,最大的絆腳石是基礎理論的缺乏以及所面臨的問題和挑戰的清晰明白的闡述”問題的解決產生深刻影響;基于內在認知機理自主知識發現系統框架及知識發現理論體系具有一般性。筆者的研究成果已在國家級重點科研項目的資助下,有效地應用于農業、現代遠程教育網、氣象、國際商務、鋁電解生產、稅務、數字資源整合、醫學信息學與生物信息學9個領域。特別是對新興交叉學科,已深刻地驗證了理論體系KDTICM的有效性與先進性,并解決了一批領域中的典型問題,這類理論體系的構造方法論對其他學科領域具有重要的示范作用。

[1]Chen M S,Han J,Yu P S.Data mining:an overview from a database perspective[J].IEEE Transactions on Knowledge and Data Engineering,1996,8(6):866-883.

[2]Han J,Kamber M.Data Mining:Concepts and Techniques[M].San Francisco:Morgan Kaufmann,2001.

[3]Indranil Bose,Mahapatra R K.Business data mining-a machine learning perspective[J].Information&Management,2001,39:211-225.

[4]Witten I H,Frank E.Data Mining:Practical Machine Learning Tools and Techniques with Java Implementations[M].San Francisco:Morgan Kaufmann,2000.

[5]Friedman H.Data mining and statistics:what is the connection?[C]//Keynote Speech of the 29th Symposium of the Interface:Computing Sciences and Statistics,Houston,TX,1997.

[6]Hand D,Mannila H,Smyth P.Principles of Data Mining[M].Cambridge:MIT Press,2001.

[7]Kleinberg J,Papadimitriou C,Raghavan P.A microeconomic view of data mining[J].Data Mining and Knowledge Discovery,1998,2(4):311-324.

[8]楊炳儒.知識發現進展中的兩大核心問題[J].中國科學技術前沿:中國工程科學版,2006(9):205-269.

[9]楊炳儒.基于內在認知機理的知識發現[M].北京:國防工業出版社,2009.

[10]Wang J F,Lee T T.An invariant for hypergraphs[J].Chinese ACTA Mathematical Application Sinica,1996,2(2):113-120.

[11]Piatetsky-shapiro G,Matheus C J.Knowledge discovery workbench for exploring business databases[J].International Journal of Intelligent Systems,1992,7:668-675.

[12]Yang Bingru.KDK based double-basis fusion mechanism and its structural model[J].International Journal of Artificial Intelligence Tools,2005,14(3):399-423.

[13]楊炳儒,李晉宏,宋 威,等.面向復雜系統的知識發現過程模型KD(D&K)及其應用[J].自動化學報,2007,33(2):151-155.

[14]楊炳儒,宋 威,,徐章艷.基于知識發現創新技術的專家系統新構造[J].中國科學(E輯),2007,37(6):738-747.

[15]Yang Bingru,Xiong Fanlun.KD(D&K)and double-bases cooperating mechanism[J].Journal of Systems Engineering and Electronics,1999,10(2):48-54.

[16]Yang Bingru,Tang Jing.Research of discovery feature sub-space model(DFSSM)based on complex type data[C]//Proceedings of 2002 International Conference on Machine Learning and Cybernetics,2002,1:256-260.

[17]Yang Bingru,Sun Haihong,Xiong Fanlun.Mining quantitative association rules with standard SQL queries and its evaluation[J].Journal of Computer Research and Development,2002,39(3):307-312.

[18]Kevin Karplus,Barrett C,Hughey R,et al.Sequence comparisons using multiple sequences detect twice as many remote homologues as pairwise methods[J].Journal of Molecular Biology,1998,284:1201-1210.

[19]David T,Jones.Protein secondary structure prediction based on position-specific scoring matrices[J].J Mol Biol,1999,292:195-202.

[20]Li Wenmin,Han Jiawei,Pei Jian.CMAR:accurate and efficient classification based on multiple class-association rules[C]//Proc of the 2001 IEEE International Conference on Data Mining,San Jose,California,2001:369-376.

[21]Yang Bingru,Hou Wei,et al.KAAPRO:an approach of protein secondary structure prediction based on KDD*in the compound pyramid prediction model[J].Expert Systems with Applications,2009,36(5):9000-9006.

[22]Rost B,Sander C.Prediction of secondary structure at better than 70%accuracy[J].J Mol Biol,1993,232(2):584-599.

[23]Cuff J A,Barton G J.Evaluation and improvement of multiple sequence methods for protein secondary structure prediction[J].Proteins:Structure,Function and Genet,1999,34:508-519.

[24]Protein Structure Prediction Center.http://predictioncenter org/.

[25]Baldi P,Brunak S,Frasconi P,et al.Bidirectional dynamics for protein secondary structure prediction[C]//Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence(IJCAI99),Stockholm,Sweden,1999.

[26]Karplus K,Karchin R,Draper J,et al.Combining local-structure,fold-recognition,and new-fold methods for protein structure prediction[J].Proteins,2003,53:491-496.

[27]Rost B,Sander C,Schneider R.PHD-an automatic mail server for protein secondary structure prediction[J].Comput Appl Biosci,1994,10:1153-1160.

[28]Ouali M,King R.Cascaded multiple classifiers for secondary structure prediction[J].Protein Science,2000,9:1162-1176.

[29]Cuff J,Clamp M,Siddiqui A,et al.JPRED:a consensus secondary structure prediction server[J].Bioinformatics,1998,14:892-893.

[30]Hyunsoo Kim,Haesun Park.Protein secondary structure prediction based on an improved support vector machines approach[J].Protein Engineering,2003,16(8):553-560.

[31]Hu H J,Pan Yi,Robert Harrison,et al.Improved protein secondary structure prediction using support vector machine with a new encoding scheme and an advanced tertiary classifier[J].IEEE Transactions on NanoBioscience,2004,3(4):265-271.

[32]Xie Xiao,Yang Bo,Chen Yuehui.Protein secondary structure prediction based on nerve network[J].Journal of University of Jinan(Science and Technology),2008,(2):111-115.

[33]Chen Jfinmiao,Narendra S Chaudhari.Cascaded bidirectional recurrent neural networks for protein secondary structure prediction[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2007,4(4):572-582.

[34]Paras Chopra,Andreas Bender.Evolved cellular automata for protein secondary structure prediction imitate the determinants for folding observed in nature[J].Silico Biol,2007,7(1):87-93.

[35]Liu Yan,Jaime Carbonel,Judith Klein-Seetharaman,et al.Context sensitive vocabulary and its application in protein secondary structure prediction[C]//Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval,Sheffield,United Kingdom,ACM,2004,538-539.

[36]Guo Jian,Chen Hu,Sun Zhirong,et al.A novel method for protein secondary structure prediction using dual-layer SVM and profiles[J].Proteins,2004,54(4):738-743.

[37]Wang Longhui,Liu Juan,Li Yanfu,et al.Predicting protein secondary structure by a support vector machine based on a new coding scheme[J].Genome Informatics,2004,15(2):181-190.