鄭存芳，洪文學(xué)，李少雄，任蘊麗,3

(1. 燕山大學(xué) 電氣工程學(xué)院，河北 秦皇島 066004； 2. 燕山大學(xué) 里仁學(xué)院，河北 秦皇島 066004； 3. 河北科技師范學(xué)院 數(shù)學(xué)與信息科技學(xué)院，河北 秦皇島 066004)

?

數(shù)據(jù)偏序結(jié)構(gòu)關(guān)系中的知識發(fā)現(xiàn)可視化方法

鄭存芳1,2，洪文學(xué)1，李少雄1，任蘊麗1,3

(1. 燕山大學(xué) 電氣工程學(xué)院，河北 秦皇島 066004； 2. 燕山大學(xué) 里仁學(xué)院，河北 秦皇島 066004； 3. 河北科技師范學(xué)院 數(shù)學(xué)與信息科技學(xué)院，河北 秦皇島 066004)

在形式概念分析與偏序結(jié)構(gòu)理論基礎(chǔ)上，針對決策模式信息表，提出一種基于認知原理的規(guī)則提取與知識發(fā)現(xiàn)的可視化新方法——屬性偏序決策圖。該方法在將決策問題轉(zhuǎn)化為決策模式信息表的基礎(chǔ)上，通過研究對象的屬性特征，將其表現(xiàn)在可視化圖形上，介紹了屬性偏序結(jié)構(gòu)圖的原理、生成算法及應(yīng)用實例。實驗表明，屬性偏序結(jié)構(gòu)圖可以將數(shù)據(jù)中蘊含的知識和規(guī)則得以形象地表示，通過對屬性偏序決策圖支路、節(jié)點、簇集的分析可以有效地發(fā)現(xiàn)數(shù)據(jù)中蘊含的決策規(guī)則。

屬性偏序決策圖；偏序結(jié)構(gòu)；形式概念分析；可視化；知識發(fā)現(xiàn)

中文引用格式：鄭存芳，洪文學(xué)，李少雄，等. 數(shù)據(jù)偏序結(jié)構(gòu)關(guān)系中的知識發(fā)現(xiàn)可視化方法[J]. 智能系統(tǒng)學(xué)報， 2016, 11(4): 475-480.

英文引用格式：ZHENG Cunfang, HONG Wenxue, LI Shaoxiong， et al. A novel knowledge discovery visualization method based on data partial ordered structure[J]. CAAI Transactions on Intelligent Systems, 2016, 11(4): 475-480.

隨著信息技術(shù)的發(fā)展，數(shù)據(jù)的獲取變得越來越簡單，如何有效地利用數(shù)據(jù)，從數(shù)據(jù)海洋中獲取有價值的規(guī)律、知識、信息成為擺在人們面前的突出問題。一些不依賴于先驗知識，單純以數(shù)據(jù)驅(qū)動的理論和方法在這一背景下產(chǎn)生和發(fā)展，如形式概念分析[1]、粗糙集[2]、模糊集[3]、商空間[4]等理論，這些理論雖然只有30多年甚至更短的時間，但是顯示出其強大的生命力，并有相互融合，共同快速發(fā)展的趨勢[5]。

形式概念分析(formal concept analysis，F(xiàn)CA)理論由德國數(shù)學(xué)家Will.R教授于1982年提出。FCA以形式背景為研究對象，通過研究對象和屬性之間的二元關(guān)系，發(fā)現(xiàn)形式背景中蘊含的知識和規(guī)則，并通過Hasse圖的形式形象地表示出來。因在知識發(fā)現(xiàn)、規(guī)則提取等領(lǐng)域的優(yōu)勢，使得FCA理論在知識工程、信息檢索等領(lǐng)域有效地被利用[6]。

洪文學(xué)等[7-8]在形式概念分析的基礎(chǔ)上，以人類認知機理為出發(fā)點，通過對形式背景中屬性的屬性、對象的對象的研究，提出了偏序結(jié)構(gòu)理論，創(chuàng)新性地提出異于Hasse圖的形式背景知識可視化表示方法——偏序結(jié)構(gòu)圖。偏序結(jié)構(gòu)圖與Hasse圖相比，其突出優(yōu)勢表現(xiàn)在支路之間相互無交叉，可以有效解決Hasse圖在對象和屬性關(guān)系復(fù)雜時可視化效果變差，失去可視化知識發(fā)現(xiàn)利用價值的問題。偏序結(jié)構(gòu)理論已在中醫(yī)診療知識發(fā)現(xiàn)[9]、英語語言學(xué)[10]等領(lǐng)域得以應(yīng)用。

本文在將決策數(shù)據(jù)轉(zhuǎn)化為決策模式的基礎(chǔ)上，將偏序結(jié)構(gòu)理論的思想應(yīng)用于決策模式信息表，提出一種完全不依賴先驗知識、以數(shù)據(jù)(決策模式信息表)為驅(qū)動的決策知識發(fā)現(xiàn)和規(guī)則提取可視化新方法——屬性偏序決策圖(decision diagram of attribute partial ordered structure，DDAPOS)，介紹其生成原理和算法，通過實例分析其使用方法、特點及有效性。

1　基礎(chǔ)定義

定義1形式背景。稱三元組(U,A,I)為一個形式背景。其中U是有限非空對象集合，每個xi∈U為形式背景的一個對象；A為有限非空屬性集合，每個ai∈A為形式背景的一個屬性；I表示U與A之間的二元關(guān)系，I?U×A。

定義2決策信息表。稱五元組(U,C,I,D,J)為一個決策信息表。其中U是有限非空對象集合，即論域，C為有限非空條件屬性集合，D為決策屬性，I表示論域U與條件屬性C之間的映射關(guān)系，J表示論域U與決策屬性D之間的映射關(guān)系。其中三元組(U,C,I)為一形式背景。表1所示為決策信息表的例子。

表1　決策信息表

在決策信息表中，如存在若干個對象其對應(yīng)條件屬性與決策屬性完全相同，稱其為同模式對象，同模式對象的個數(shù)，稱為該模式的度。如表1中，x7與x8即為一組同模式對象，決策信息表中的一個模式記為m，所有的模式構(gòu)成模式集M。

定義3決策模式信息表。決策信息表(U,C,I,D,J)對應(yīng)的六元組(M,C,I′,D,J′, De)稱為決策模式信息表。其中M是模式集合，C為條件屬性集合，D為決策屬性，De為模式的度。I′表示模式集合M與條件屬性C之間的映射關(guān)系，J′表示模式集合M與決策屬性D之間的映射關(guān)系。表1所對應(yīng)的決策模式信息表如表2所示。

表2　表1對應(yīng)的決策模式信息表

在決策模式信息表中，若任意兩個模式條件屬性完全相同時，決策屬性亦相同，則此決策模式信息表稱決策模式一致信息表。反之，此決策信息表稱為決策模式不一致信息表。在決策模式不一致信息表中，條件屬性相同的模式是無法區(qū)分的，因此需要對決策不一致模式的結(jié)果按某種規(guī)則進行判別而轉(zhuǎn)化為決策模式一致信息表。

定義4最大共有條件屬性。在決策模式信息表(M,C,I′,D,J′, De)所對應(yīng)的形式背景(M,C,I′)中，如果條件屬性c∈C滿足g(c)=U，則稱屬性c是形式背景(M,C,I′)的最大共有條件屬性。

定義5共有條件屬性。在決策模式信息表(M,C,I′,D,J′, De)所對應(yīng)的形式背景(M,C,I中，如果屬性c0,c1,…,ck∈C滿足g(ci)?g(c0)，其中i=1,2,…,k, k≥2，則稱在形式背景(M,C,I′)中，條件屬性c0是條件屬性集合{c1,c2,…,ck}的共有條件屬性。

2　屬性偏序決策圖

2.1屬性偏序決策圖生成原理

由認知心理學(xué)可知：在一定情景和經(jīng)驗的背景下，人類是通過客觀事物具有的屬性特征來認知事物的?；镜恼J知原理可以描述為：特征相同靠近相同，特征不同遠離相同，在相同特征中找出不同，在不同特征中找出相同。這樣的描述蘊含著：相似性原理(相同靠近相同)，相異性原理(不同遠離相同)，自上而下感知原理(相同之中找不同)，自下而上感知原理(不同之處找相同)。圖1給出了一般化認知機理模型示意圖[11]。

圖1　一般化認知機理模型示意圖Fig.1　Schematic diagram of general cognitive mechanism model

屬性是各類事物特征的表達，屬性間的關(guān)系表達了研究問題的概念之間的關(guān)系。共有屬性表達的一定是事物普遍存在的現(xiàn)象，是共性的表達，具有較大的外延和較淺的內(nèi)涵。從人類認識模式知識的角度來看，可以構(gòu)造出以屬性特征和對象相似性為指標的層次結(jié)構(gòu)圖。

2.2屬性偏序決策圖生成算法

根據(jù)屬性偏序決策圖的生成原理，構(gòu)建屬性偏序決策圖的算法描述如下所示。

構(gòu)建屬性偏序決策圖

輸入決策一致模式信息表(M,C,I′,D,J′, De)；

輸出屬性偏序決策圖(N,E,R)；

1) 提取決策模式一致信息表(M,C,I′,D,J′, De)中的(M,C,I′)構(gòu)成形式背景；

2) 生成屬性偏序結(jié)構(gòu)圖[12]；

3) 根據(jù)屬性偏序結(jié)構(gòu)圖每一分支對應(yīng)的模式標注其決策屬性，形成決策層；

4)從根節(jié)點由上至下檢索各支路，當檢索至某節(jié)點覆蓋之下各支路模式完全一致時，停止檢索此節(jié)點之下的支路和節(jié)點，并將此節(jié)點下各支路上的節(jié)點標記為隱藏節(jié)點；

5) 直至檢索完所有支路，所得結(jié)果即為屬性偏序決策圖。

表2所示決策模式信息表對應(yīng)的屬性偏序決策圖如圖2所示。由圖可見，屬性偏序決策圖在結(jié)構(gòu)上分為決策規(guī)則表示層和決策規(guī)則輸出層兩個層次。圖中虛線表示的節(jié)點為隱藏節(jié)點，不參與知識發(fā)現(xiàn)和規(guī)則提取過程。決策表示層是一個典型的樹結(jié)構(gòu)，其中每一個節(jié)點表示一個條件屬性，圖中最頂層為最大共有條件屬性。樹中根據(jù)條件屬性的偏序關(guān)系由上而下形成若干個節(jié)點和邊構(gòu)成的支路，其中每一條支路即為一種決策模式。根據(jù)屬性偏序決策圖中支路聚類形成的群結(jié)構(gòu)、子群結(jié)構(gòu)及每條支路對應(yīng)的決策屬性即可完成決策規(guī)則的輸出。

圖2　表2所示決策模式信息表對應(yīng)屬性偏序決策圖Fig.2　DDAPOS of table2

2.3基于屬性偏序決策圖的規(guī)則提取方法

基于屬性偏序決策圖自頂向下的構(gòu)圖原則，條件屬性中普遍性強在上層，可以從集群結(jié)構(gòu)、集子群結(jié)構(gòu)、支路和節(jié)點等不同角度對原始數(shù)據(jù)進行知識發(fā)現(xiàn)。支路條件屬性集合表達的一條決策模式，即一個決策模式具有什么屬性。圖中同一子群結(jié)構(gòu)表達的為模式間相似性；不同子群結(jié)構(gòu)表達決策模式之間的差異性。綜合屬性偏序決策圖條件屬性偏序關(guān)系及決策屬性，即可得出最終的規(guī)則提取。圖2所示的屬性偏序決策圖決策結(jié)果輸出可表示為表3。

表3　圖2所示屬性偏序決策圖決策結(jié)果輸出

3　實例實驗結(jié)果與分析

下面通過一個醫(yī)學(xué)診斷的實例介紹屬性偏序決策圖的具體使用方法，并驗證其規(guī)則提取的有效性。

3.1實驗數(shù)據(jù)

選用UCI數(shù)據(jù)庫的Breast Cancer Wisconsin Data Set(BCWD)數(shù)據(jù)集驗證屬性偏序決策圖的有效性，數(shù)據(jù)集屬性組成如表4所示。該數(shù)據(jù)集共有699個樣本(其中有16個樣本存在屬性缺失)，9個屬性，2個類(良性、惡性)。本實驗剔除了這些有屬性缺失的樣本，因此實際使用了數(shù)據(jù)集中樣本683個。實驗采用10折交叉驗證的方式對所述方法的可行性進行驗證，并與主流的模式分類算法進行了對比分析。

表4　乳腺癌數(shù)據(jù)集屬性構(gòu)成

3.2實驗過程

1)原始數(shù)據(jù)特征(屬性)選擇。根據(jù)原始數(shù)據(jù)分布，利用lasso算法完成特征子集選擇，特征相關(guān)序列為：BN、Ucsh、Ucsi、CT、BC、NN、MA、SECS、M[13]。本例選取其中3個屬性：BN、Ucsh、Ucsi參與決策生成。

2)原始數(shù)據(jù)?；?，生成決策形式信息表。以數(shù)據(jù)驅(qū)動的決策規(guī)則生成中，數(shù)據(jù)的形式可能是數(shù)值型、名義型、布爾型、區(qū)間型等。所有的原始數(shù)據(jù)需根據(jù)不同粒化規(guī)則，轉(zhuǎn)換為布爾型規(guī)則。根據(jù)原始數(shù)據(jù)分布，按表5規(guī)則完成數(shù)據(jù)?；蓻Q策信息表如表6所示。

表5　乳腺癌數(shù)據(jù)集?；?guī)則

表6　乳腺癌數(shù)據(jù)決策信息表

3)根據(jù)決策形式信息表生成決策模式信息表。檢索決策信息表中的模式，得到乳腺癌數(shù)據(jù)決策模式信息表如表7所示。

表7　乳腺癌數(shù)據(jù)決策模式信息表

表8為決策模式不一致信息表，對條件屬性相同但決策屬性不同的模式中，按照模式度較小的模式的決策屬性服從模式度較大模式的原則進行修正，得到表8所對應(yīng)的決策模式一致信息表如表8。

表8　乳腺癌數(shù)據(jù)決策模式一致信息表

4)生成屬性偏序決策圖。根據(jù)表8決策一致模式信息表生成屬性偏序決策圖如圖3所示。

圖3　乳腺癌診斷屬性偏序決策圖Fig.3　DDAPOS of BCWD

5)根據(jù)屬性偏序決策圖，完成決策規(guī)則提取任務(wù)。由圖3所示屬性偏序決策圖提取的規(guī)則如表9所示。

3.3結(jié)果分析

應(yīng)用上述診斷規(guī)則對數(shù)據(jù)集進行診斷，同時與主流模式分類算法(kNN、Naive Bayes、SVM、C5.0、Random Forests)對比結(jié)果見表10。通過對比可以發(fā)現(xiàn)，本文所述屬性偏序決策圖在只有3個屬性參與規(guī)則提取的條件下，提取的診斷規(guī)則在各項指標上均較理想，達到了主流模式分類和知識發(fā)現(xiàn)方法的水平。通過增加參與規(guī)則提取的屬性，改善?；?guī)則等措施，各項指標仍有提高的空間。與常規(guī)模式識別方法(如kNN、SVM等)相比，屬性偏序決策圖可以將決策規(guī)則以圖形的方式進行明確地表示，這一特性可以有效地溝通領(lǐng)域?qū)＜遗c數(shù)據(jù)分析專家，降低其在具體領(lǐng)域的應(yīng)用門檻。

表9　乳腺癌診斷規(guī)則

表10　乳腺癌診斷靈敏度、特異度和準確率

4　結(jié)束語

本文以決策模式信息表為研究對象，提出一種基于屬性偏序關(guān)系的、不依賴于先驗知識完全以數(shù)據(jù)驅(qū)動的規(guī)則提取可視化方法——屬性偏序決策圖。屬性偏序決策圖通過屬性的聚類完成事物“類內(nèi)緊，類間松”的聚類，并以直觀圖形的形式進行表示，從中發(fā)現(xiàn)事物之間相區(qū)別的屬性，從而達到提取事物共同特征的目的。屬性偏序決策圖因不需要進行復(fù)雜的浮點運算，其算法運算速度快。另外，該方法在實際應(yīng)用中還有若干問題有待解決，如如何根據(jù)原始屬性生成決策模式信息表、如何處理決策過程中的不確定性問題、如何提供人機交互方式完成專家知識與機器學(xué)習(xí)的融合等，都有待進一步研究。

[1]POELMANS J, KUZNETSOV S O, IGNATOV D I, et al. Formal concept Analysis in knowledge processing: a survey on models and techniques[J]. Expert systems with applications, 2013, 40(16): 6601-6623.

[2]王國胤, 姚一豫, 于洪. 粗糙集理論與應(yīng)用研究綜述[J]. 計算機學(xué)報, 2009, 32(7): 1229-1246.

WANG Guoyin, YAO Yiyu, YU Hong. A survey on rough set theory and applications[J]. Chinese journal of computers, 2009, 32(7): 1229-1246.

[3]YAO Yiyu. A comparative study of fuzzy sets and rough sets[J]. Information sciences, 1998, 109(1/2/3/4): 227-242.

[4]ZHANG Ling, ZHANG Bo. The quotient space theory of problem solving[J]. Fundamenta informaticae, 2004, 59(2/3): 287-298.

[5]于洪, 王國胤, 姚一豫. 決策粗糙集理論研究現(xiàn)狀與展望[J]. 計算機學(xué)報, 2015, 38(8): 1628-1639.

YU Hong, WANG Guoyin, YAO Yiyu. Current research and future perspectives on decision-theoretic rough sets[J]. Chinese journal of computers, 2015, 38(8): 1628-1639.

[6]POELMANS J, IGNATOV D I, KUZNETSOV S O, et al. Formal concept analysis in knowledge processing: a survey on applications[J]. Expert systems with applications, 2013, 40(16): 6538-6560.

[7]HONG Wenxue, LI Shaoxiong, YU Jianping, et al. A new approach of generation of structural partial-ordered attribute diagram[J]. ICIC express letters, part B: applications, 2012, 3(4): 823-830.

[8]洪文學(xué), 欒景民, 張濤, 等. 基于偏序結(jié)構(gòu)理論的知識發(fā)現(xiàn)方法[J]. 燕山大學(xué)學(xué)報, 2014, 38(5): 394-402.

HONG Wenxue, LUAN Jingmin, ZHANG Tao, et al. A new method for knowledge discovery based on partial ordered structure theory[J]. Journal of Yanshan university, 2014, 38(5): 394-402.

[9]劉超男, 徐筍晶, 李賽美, 等. 基于多層次復(fù)雜概念網(wǎng)絡(luò)表示方法的《傷寒論》方藥按治法分類的知識發(fā)現(xiàn)[J]. 北京中醫(yī)藥大學(xué)學(xué)報, 2014, 37(7): 452-457.

LIU Chaonan, XU Sunjing, LI Saimei, et al. Knowledge discovery of formula classification according to therapies in Shanghanlun based on representation method of multi-layer complex concept network[J]. Journal of Beijing university of traditional Chinese medicine, 2014, 37(7): 452-457.

[10]YU Jianping, LI Chen, HONG Wenxue, et al. A new approach of rules extraction for word sense disambiguation by features of attributes[J]. Applied soft computing, 2015, 27: 411-419.

[11]GALOTTI K M. 認知心理學(xué)[M]. 吳國宏, 譯. 3版. 西安: 陜西師范大學(xué)出版社, 2005.

GALOTTI K M. Cognitive Psychology[M]. WU Guohong, Trans. 3rd ed. Xi’an: Shaanxi Normal University Press, 2005.

[12]李少雄, 閆恩亮, 宋佳霖, 等. 偏序結(jié)構(gòu)圖的一種計算機生成算法[J]. 燕山大學(xué)學(xué)報, 2014, 38(5): 403-408.

LI Shaoxiong, YAN Enliang, SONG Jialin, et al. Computational generation algorithm of partial ordered structure diagram[J]. Journal of Yanshan university, 2014, 38(5): 403-408.

[13]TIBSHIRANI R. Regression shrinkage and selection via the lasso: a retrospective[J]. Journal of the royal statistical society, 2011, 73(3): 273-282.

鄭存芳，男，1979年生，講師，博士研究生，CAAI粗糙集與軟計算專委會會員、CCF會員，主要研究方向為可視化模式識別、偏序結(jié)構(gòu)理論、中醫(yī)工程學(xué)等。先后參與國家自然科學(xué)基金3項、河北省自然科學(xué)基金3項。

洪文學(xué)，男，1953年生，教授，博士生導(dǎo)師，燕山大學(xué)生物醫(yī)學(xué)工程研究所所長，CAAI粗糙集與軟計算專委會委員，主要研究方向為大數(shù)據(jù)偏序結(jié)構(gòu)理論、復(fù)雜概念網(wǎng)絡(luò)、混合數(shù)據(jù)信息融合與模式識別和中醫(yī)工程學(xué)。所帶領(lǐng)的學(xué)術(shù)團隊近年來主持省部級科研項目20余項。

李少雄，男，1987年生，博士研究生，主要研究方向為偏序結(jié)構(gòu)理論、可視化模式識別、中醫(yī)工程學(xué)等。參與國家自然科學(xué)基金項目4項。

A novel knowledge discovery visualization method based on data partial ordered structure

ZHENG Cunfang1,2, HONG Wenxue1, LI Shaoxiong1, REN Yunli1,3

(1. School of Electrical Engineering, Yanshan University, Qinhuangdao 066004, China; 2. Liren College, Yanshan University, Qinhuangdao 066004, China; 3. College of Mathematics and Information Technology, Hebei Normal University of Science and Technology, Qinhuangdao 066004, China)

In this paper, the formal concept is first analyzed and partial order structure theory introduced. The decision diagram of attribute partial ordered structure (DDAPOS), a visualization method of rule extraction and knowledge discovery based on cognitive principles, is then proposed. After the decision problem is transformed into a decision pattern information table, the attributes of a research object can be presented in the visualized diagram. This paper introduces the principles, generation algorithm, and application examples of DDAPOS. Experimental results show that the knowledge and rules contained in the data can be represented graphically, and the decision-making rules in the data can be found effectively through analysis of the graph branches, nodes and clusters.

decision diagram of attribute partial ordered structure; partial ordered structure; formal concept analysis; visualization; knowledge discovery

10.11992/tis.201606019

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160808.0831.032.html

2016-06-06. 網(wǎng)絡(luò)出版日期：2016-08-08.

國家自然科學(xué)基金項目(61273019，61473339，61501397)；河北省自然科學(xué)基金重點項目(F2016203443)；燕山大學(xué)青年教師自主研究計劃課題(13LGB033).

洪文學(xué). E-mail：hongwx@ysu.edu.cn.

TP182

A

1673-4785(2016)04-0475-06