中心概念及其在規則提取中的應用*

溫 馨，閆心怡，陳澤華+

1.太原理工大學 大數據學院，太原 030024

2.太原理工大學 電氣與動力工程學院，太原 030024

1 引言

規則提取是數據挖掘的研究熱點。粗糙集理論[1]與概念格理論[2]是數據處理與知識發現[3-6]的重要工具。近年來，眾多學者致力于兩種理論的研究并提出了不少決策規則提取算法[7-15]，文獻[7]將決策信息系統分層粒化，在不同的粒度空間下求取粒關系矩陣，并從中獲取啟發式信息去除冗余屬性，設定終止條件實現決策規則的挖掘，但當冗余屬性較多或者樣本集較大時，規則約簡難度增加；文獻[8]提出了一種從決策形式背景生成概念，進而推導無冗余規則的算法，該算法在一定程度上降低了算法復雜度，在某些情況下，獲取的決策規則仍然存在冗余屬性；文獻[11]主要研究決策形式背景的規則獲取和屬性約簡問題，基于面向對象概念和面向屬性概念，提出了面向對象決策規則和面向屬性決策規則的概念，并利用條件概念格與決策概念格外延集合的等價類關系進行決策規則提??；文獻[13]為解決傳統的決策規則只能判斷對象是否具有某種決策屬性，以及無法準確判斷決策知識的內在性質的問題，提出含有多個決策屬性且決策屬性取值為多值的序決策形式背景及其序決策概念格，并實現了基于規則不變的屬性約簡；文獻[14]利用正向尺化與反向尺化實現信息系統與形式背景之間的相互轉化，定義了多粒度標記形式背景，并實現了多粒度標記決策形式背景的規則提取；文獻[15]提出介粒度標記形式背景的概念，之后基于此，給出多粒度標記決策形式背景的介粒度知識發現方法，得到粗細介粒度標記形式背景之間的決策蘊涵誘導關系。

本文針對決策信息系統，基于形式概念分析理論，將決策信息系統通過轉化為決策形式背景進行決策規則提取，并提出一種基于中心概念的最簡規則提取算法，該方法的提出將概念生成的過程與規則提取進行有效融合。不必生成所有概念，即決策規則提取完畢時概念生成過程也將結束。該算法避免了傳統基于決策形式背景的決策規則提取算法[7，10-11]需要同時生成條件形式概念及決策形式概念的計算復雜性。決策規則的提取是本文研究的重點，而概念的生成僅是一個條件，沒有絕對必要將所有概念全部生成。理論分析和實驗證明體現出本文方法的有效性。

2 預備知識

定義1[1]（決策信息系統）設DIS={U，C?D，V，f}是信息系統，其中U為對象集，C為條件屬性，D為決策屬性，用V表示屬性集C?D的值域；f：U×（C?D）→V是信息函數，它指定U中每個對象的屬性值。若C?D=?，則稱該信息系統為決策信息系統，也稱為決策表。

定義2[1]（等價類）在決策信息系統DIS中，?B?（C?D），定義等價關系ind（B）={（x，y）∈U×U|?b∈B，f（x，b）=f（y，b）}，其中ind（B） 為屬性子集B導出的劃分，而產生的等價類記作[x]ind（B）或[x]B。

定義3[2]（形式背景）形式背景可以用一個三元組T=（U，A，I）來表示，其中U表示非空有限對象集，稱為論域；A表示非空有限屬性集；I滿足I?U×A，表示形式背景的一種二元關系，（u，a）∈I（其中u∈U，a∈A）表示對象u擁有屬性a，否則（u，a）?I表示u沒有屬性a。在形式背景T=（U，A，I）中，令2U、2A分別為對象集U和屬性集A的冪集，對于任意對象集合X（X?U）和任意屬性集合B（B?A），Wille 定義了兩個映射X↑：2U→2A和B↓：2A→2U[2]：

定義4[2]（形式概念）三元組T=（U，A，I）為一個形式背景，令X?U，B?A，若X↑=B且B↓=X，則稱二元組（X，B）為一個形式概念，其中X被稱為這個概念的外延，B被稱為這個概念的內涵。為方便敘述，可將形式背景T下的所有概念存入L（T）中。記L（T）中的兩個概念為（X1，B1）、（X2，B2），若滿足條件X1?X2（或B2?B1）時，則稱概念（X1，B1） 是（X2，B2） 的子概念，概念（X2，B2）是（X1，B1）的父概念?？啥xL（T）中的任意兩個概念間的邏輯運算：

為了便于理解上述邏輯運算過程，下面將通過具體實例（例1）來詳細說明：

例1如表1 所示，形式背景T=（U，A，I），其中U={x1，x2，x3，x4}，A={a1，a2，a3，a4}。

Table 1 Formal context表1 形式背景

其中概念（124，a1）與（14，a1a3）為表1 所示的形式背景中可求得的兩個概念。

針對式（3）而言有：

針對式（4）而言有：

定義5[8]（決策形式背景）五元組S=（U，A，I，D，J）為一個決策形式背景，其中（U，A，I）和（U，D，J）為形式背景，U為對象集，A為條件屬性集，D為決策屬性集。

定義6[16]（協調決策表）在決策信息系統DIS中，如果ind（C）?ind（D），則稱S為協調決策表，否則稱為不協調決策表。本文討論的是協調決策表。

3 中心概念與決策規則

3.1 概念定義

中心概念是本文提出的定義，也是本文的核心內容，本文所做的工作都將圍繞中心概念展開。中心概念同時考慮了條件屬性與決策屬性之間知識的關聯性，且具有豐富的知識內涵。

定義7（外延）任一決策信息系統S可轉化成決策形式背景T=（U，A，I，D，J），記Z=A?D，對于?Z′?Z，有以下關系：

定義8（綜合概念）在一個決策形式背景S=（U，A，I，D，J）中，對于一個概念（X，B），其中X?U，B=C?d（C?A，d∈D） 且滿足C≠?，d≠?，同時X↑=B，B↓=X，此時稱（X，B）為綜合概念。

定義9（中心概念）對于一個綜合概念（X，B），其中B=C?d且滿足C↓?d↓，此時稱（X，B）為一個中心概念，中心概念包含了綜合概念中最簡單的邏輯關系，直接蘊含了決策信息系統中的規則信息。

定理1在決策形式背景S=（U，A，I，D，J）中（X，B）為一個中心概念，若?（X，B）∈L（T），此時可以確定一條決策規則記C→d。對于決策規則C→d，C={c1，c2，…，cn}，若?ck∈{c1，c2，…，cn}s.t.{C-ck}↓?X，則稱決策規則C→d中存在冗余屬性ck。

定理2若（X，B）為一個中心概念，其中B=C?d，C={c1，c2，…，cn}且有決策規則C→d，?ci∈C，c′={c-ci}，如果滿足c′↓?X，則稱決策規則C→d為最簡決策規則。

證明反證法。若?ci∈C，c′={c-ci}，如果滿足c′↓?X，C→d不是最簡決策規則，則?cj∈C={c1，c2，…，cn}使得{C-cj}↓?X，顯然與前提相矛盾，故C→d為最簡規則。

3.2 中心概念與傳統概念

本文針對決策信息系統規則抽取的問題提出了一種新的概念——中心概念，中心概念是概念，但內涵更加豐富。內涵中不僅包含決策信息系統中的條件屬性C，也包含了決策屬性d，同時這兩種屬性之間存在一種邏輯關系即C↓?d↓，而這種關系成為進行規則提取的充要條件。故一個中心概念不單滿足概念定義，且其內涵中內部屬性之間體現了決策規則。

4 基于中心概念的最簡規則提取算法

4.1 算法描述

中心概念體現出條件屬性與決策屬性之間的蘊含關系，本文提出了基于中心概念的決策信息系統最簡規則提取算法（記作算法1），其具體算法流程描述如下所示：

算法1基于中心概念的最簡規則提取算法

輸入：決策信息系統DIS=（U，C?D，V，f）。

輸出：最簡決策規則。

步驟1對完備決策表DIS進行預處理，將其轉換成決策形式背景S=（U，A，I，D，J），記Z=A?d。

步驟2初始化n=1，Rules=?，Concept=?，Exten=?，Del=?。//Exten為外延集合，Del為被剔除概念的集合

步驟3對于z∈Z，計算n=1 次的形式概念（z↓，z↓↑），并將第一次求得的概念存入Concept。

步驟4依次判斷第n層時的概念（X，B），若C?B，d∈B，C↓?d↓且X?Exten，則Rules=Rules?{C→d}，Exten=Exten?X，同時對提取完規則的概念（X，B）進行標記并存入Del中。

步驟5對概念集Concept進行更新：Concept=Concept-Del。

步驟6判斷Exten是否等于U：若相等，則轉至步驟9；否則，轉至步驟7。

步驟7此時n=n+1，對當前Concept中的所有概念按照式（3）進行兩兩相交邏輯運算，并記錄新產生的概念。

步驟8將新產生的概念重復步驟4～6，若Exten與U相等，則轉至步驟9；否則，轉至步驟7。

步驟9輸出Rules中的最簡決策規則。

算法1 主要分為兩部分：第一步將輸入的決策信息系統轉化成決策形式背景，決策屬性也參與第一層形式概念的生成，根據定義9 選擇滿足條件的中心概念，并由定理1 進行決策規則的提??；第二步判斷Exten中的元素是否覆蓋整個論域，若沒有覆蓋，則在下一層概念生成之前將前一層的中心概念剔除，剩余概念集作為基概念再參與下一層的生成運算，然后重復第一步中的規則提取過程，否則重復第二步繼續提取規則，直到Exten中的元素覆蓋整個論域。

4.2 算法復雜度分析

在完備決策信息系統DIS=（U，C?D，V，f） 中將DIS轉化成決策形式背景S=（U，A，I，D，J），對于?u∈U，?p∈A?D在決策形式背景S中滿足（u，p）∈I的屬性值共有|U||A+D|個。求概念每一層的時間復雜度的基數為O（|U|2|A+D|2），共有lb（|U||A+D|）層。假設算法共產生N條決策規則即N個中心概念，而該算法生成概念的過程中要剔除提取完規則的中心概念，其復雜度為O（N-1）。并且如果Exten已經覆蓋整個論域，算法執行完畢，但實際上有可能并沒有將所有的概念全部生成出來。故整個算法的復雜度要小于等于O（|U||A+D|）+O（|U|2|A+D|2lb（|U||A+D|））+O（N-1）。

5 實驗分析

5.1 實例說明

下面通過實例來詳細說明算法1 的執行流程。

例2決策信息系統DIS=（U，C?D，V，f），其中論域U={x1，x2，…，x8}，條件屬性集C={a，b，c}，決策屬性集D=g0gggggg。如表2 所示。

Table 2 Decision information system表2 決策信息系統

將表2 的決策信息系統轉化為決策形式背景S=（U，A，I，D，J），如表3 所示。

Table 3 Decision formal context表3 決策形式背景

對于?z∈Z，由（z↓，z↓↑）可求取第一層概念（其中外延元素簡寫為數字，例如概念（x1x3x7，a1） 簡寫為（137，a1））：（137，a1），（24，a2），（568，a3），（15，b0c0），（3478，b2），（26，b1d3），（278，c1），（13456，c0），（58，a3d1），（14，c0d2），（2367，d3）。從第一層概念中選取滿足定義9 的中心概念并進行規則提取，如表4 所示，其中（26，b1d3）滿足條件，此時可進行決策規則提取，此時Exten中的元素為{2，6}，沒有覆蓋整個論域元素，因此需計算下一層概念。

Table 4 Rule list of the first layer of central concept表4 第一層中心概念的規則列表

生成第二層概念時，其所需的概念是將（26，b1d3）從第一層剔除后得到的概念（137，a1），（24，a2），（568，a3），（15，b0c0），（3478，b2），（278，c1），（13456，c0），（58，a3d1），（14，c0d2），（2367，d3）。對上述概念進行相交運算可得到第二層概念（1，a1b0c0d2），（37，a1b2d3），（5，a3b0c0d1），（13，a1c0），（4，a2b2c0d2），（8，a3b2c1d1），（7，a1b2c1d3），（2，a2b1c1d3），（78，b2c1），（56，a3c0），（34，b2c0），（6，a3b1c0d3），（27，c1d3），（36，c0d3）。從 第二層中選取滿足定義9 的中心概念并進行規則提取，如表5 所示，其中（1，a1b0c0d2），（5，a3b0c0d1），（37，a1b2d3），（4，a2b2c0d2），（8，a3b2c1d1）這5 個概念滿足條件，此時可進行規則提取，此時在Exten集合中可添加元素集{1，3，4，5，7，8}，故此時Exten={1，2，3，4，5，6，7，8}。至此，Exten中的元素覆蓋整個論域，規則提取完畢。

Table 5 Rule list of the second layer of central concept表5 第二層中心概念的規則列表

下面將分析算法產生的規則中是否存在冗余屬性：

（1）對于規則b1→d3，根據定義7，?↓={1，2，3，4，5，6，7，8}?{2，3，6，7}，故規則b1→d3不存在冗余屬性。

（2）對于規則a1b0c0→d2，根據定義7，故屬性c0為冗余屬性，因此規則a1b0c0→d2可化簡為a1b0→d2。

（3）對于規則a3b0c0→d1，根據定義7，（a3b0）↓={5}?{5，8}，，故屬性c0為冗余屬性，因此規則a3b0c0→d1可化簡為a3b0→d1。

（4）對于規則a1b2→d3，根據定義7，{2，3，6，7}，，故規則a1b2→d3不存在冗余屬性。

（5）對于規則a2b2c0→d2，根據定義7，（a2b2）↓={4}?{1，4}，因此規則a2b2c0→d2可化簡為a2b2→d2。

（6）對于規則a3b2c1→d1，根據定義7，（a3b2）↓={8}?{5，8}，因此規則a3b2c1→d1可化簡為a3b2→d1。

本文算法實現了在生成概念的同時能夠進行決策規則提取，直到外延集合可覆蓋整個論域為止。在此過程中可能不需要生成所有概念就可將全部決策規則提取完畢。生成下一層概念時需剔除上一層概念中的中心概念，這樣可減少冗余概念的生成，同時降低了算法復雜性。本算法所生成的中心概念能夠直觀體現出決策規則，相較傳統方法中生成的單一形式概念涵蓋的內容更加豐富。如圖1 所示，圖中圓圈為例2 中的全體概念，其中L1～L12淺灰色標注的概念為無法進行規則提取的一般概念（不包括決策內涵的概念），L13～L26的深灰色圓圈為內涵中既包括條件屬性又包括決策屬性的綜合概念，其中用網狀節點標注的概念是決策規則的中心概念，而用黑色標注的則為實際進行規則提取過程中無需生成的概念。6 個網狀中心概念可代表生成的6 條決策規則。

圖2 為表2 按照傳統方法需分別得到條件形式概念與決策形式概念的Hasse 圖，黑色虛線相連的概念體現出了條件概念與決策概念之間的包含關系，紅色實線則體現出得到的決策規則。

從圖1 可以看出，本文提出的綜合概念、中心概念以及所要提取的決策規則都可以在一張Hasse圖中清晰地表現出來，概念節點能夠體現出條件與決策知識的關聯性。符合人類綜合考慮處理問題的特性。針對傳統基于決策形式背景規則提取的方法，其構造出的Hasse圖所描述的相關信息則會復雜很多。

5.2 實驗測試

Fig.1 Hasse diagram of formal decision context圖1 決策形式背景概念Hasse圖

Fig.2 Hasse diagram of conditional concept and decision concept and their relationship圖2 條件概念與決策概念及其關系Hasse圖

通過選取以下8 組UCI 數據集來測試該算法的正確性以及有效性。利用Rosetta 軟件對數據集進行離散化處理。然后，分別應用本文算法、文獻[7]中的算法、文獻[8]中的算法和文獻[9]中的算法對數據集進行測試，以上算法均將數據集作為輸入，提取到的所有規則作為輸出，記錄各算法所得到的約簡規則個數和規則長度。其中對于文獻[8]中的算法需要先將決策信息系統轉化為決策形式背景來處理。最終實驗對比結果如表6～表8 所示。

正確識別率[17]是由獲取的規則集對每個數據集進行整體識別的正確概率。具體過程：每個數據集中各隨機選取50%作為訓練樣本，分別應用各算法對訓練樣本進行規則獲取并記錄各自的規則集，然后利用獲取到的規則集對各數據集整體進行識別。

實驗分析：由上表能夠看出，該算法在相同數據集上較其他算法而言，所提取到的決策規則個數更少，同時規則長度較其他算法更短，對于識別率，本文算法與文獻[7]中的算法相當，略高于文獻[8]、文獻[9]中的算法。這可說明該算法所得到的規則集具有更強的表示能力，本文算法所得到的中心概念所涵蓋的知識更加豐富，其不僅體現出了條件屬性與決策屬性之間的邏輯關系，同時中心概念還是形式概念與決策規則緊密結合的綜合體。

Table 6 Comparison of rule number表6 規則個數對比

Table 7 Comparison of rule length表7 規則長度對比

Table 8 Comparison of recognition rate表8 識別率對比

6 結束語

本文將決策信息系統作為研究對象，將決策信息系統轉化成決策形式背景，決策形式背景中的決策屬性參與概念的生成，內涵中包含決策屬性的概念被定義為綜合概念，其中滿足C↓?d↓的綜合概念被定義為中心概念。中心概念蘊含了決策信息系統中最簡規則的關鍵信息。并且包含中心概念的Hasse圖具有更加豐富且明確的意義。因此，一個決策信息系統的規則提取過程將轉化為中心概念的生成以及選擇的過程。此時中心概念具有豐富的研究意義。最后通過實驗分析與對比說明該算法的正確性與有效性。本文算法有以下特點：（1）提出的中心概念直接蘊含了最簡決策規則，較經典形式概念所表達的知識更加豐富。（2）該算法相較于其他算法來說具有較高的識別率且所提取到的規則具有較強的表示能力。并且針對協調決策信息系統而言，通過求取中心概念提取的決策規則具有完備性，能夠覆蓋信息系統中所有非冗余規則。文獻[18]將粒計算與概念格相結合，提出了粒概念，從認知計算的角度研究了基于粒計算的認知概念學習。所有經典形式概念能通過粒概念全部求得，同時這種求取概念的方法將極大降低計算復雜性。在今后工作當中可嘗試通過將粒概念與中心概念相結合，進一步優化本文算法。同時，可將本文算法拓展到不協調不完備決策信息系統的知識獲取中，今后也可將其應用于語義表示及其推理，信息檢索及智能推薦，以上相關研究正在進行中。