利用關聯矩陣探究屬性約簡方法

毛 華，武振宇

(河北大學數學與信息科學學院，河北保定071002)

E-mail:hbdxwzy@126.com

1 引言

1982年，德國的Wille教授將哲學中概念的思想引入形式背景的探究中，并結合序理論、完備格等建立了概念格理論［1］，該理論現已廣泛地應用于信息提取［2，3］、知識挖掘［4］等方面.概念作為一種知識表達方式，在信息采集與提取的過程中，為了提取更加有效的概念，需要對形式背景進行約簡.目前，許多研究人員從不同的角度進行約簡已取得很大突破，如張文修等［5］通過辨識矩陣來進行屬性約簡，魏玲等［6］利用協調集來進行屬性約簡等.近年來，又有很多研究人員從圖論的角度出發，對概念格進行研究，例如張濤［7］利用屬性拓撲來表示形式背景并對概念進行計算，毛華［8］利用圖論將有向圖與概念格相結合對屬性進行約簡，文獻［9］是用圖論討論模糊背景的約簡問題，毛華等［9］利用改進的屬性拓撲圖對形式背景進行約簡等.

在結合圖論研究概念格的方法中，張濤的屬性拓撲圖是一種比較常用的方法.但是，在尋找到屬性拓撲圖之前，需要對所有的屬性進行兩兩比較，并且需要找出每兩個屬性之間的權值，還要進一步地將找出的權值之間進行比較，由于每次比較之后都必須將此比較的結果加以保留，從而導致這個算法的存儲空間太大;另外，由于必須將所有屬性都進行考慮，使得找到屬性拓撲圖的時間復雜度也大.毛華［8，9］等人對此進行了改進尋找屬性拓撲圖的過程，提出首先進行屬性的約簡，但是這些成果理論性較強，實際完成不是一件容易之事.本文結合圖論中有關有向圖的點和邊之間的關聯矩陣思想，利用關聯矩陣覆蓋關系和屬性特征可以快速地將屬性進行分類，完成屬性約簡并生成算法.由于所生成的關聯矩陣已經包含了兩兩屬性之間的關聯關系，可直接通過觀察由關聯矩陣與屬性所構成的表的每一列得出，從而達到對屬性進行分類與約簡.與已有成果相比，算法的復雜度降低.此外，通過實例驗證了本算法的有效性.

2 預備知識

本節將給出形式概念分析以及圖論中的一些基本知識，更多具體相關內容，形式概念分析參考文獻［11］、圖論見文獻［12］.

2.1 形式概念分析

定義 1［10］.

若滿足 A'=B，B'=A，則稱(A，B)為一個概念，其中(A，B)的外延、內涵分別為A、B，(G，M，I)中的概念全體記為 L(G，M，I).

2)稱一個形式背景(G，M，I)為凈化的是指:合并具有相同內涵的對象和相同外延的屬性，即在形式背景(G，M，I)，若對于任意地滿足a'=b'的兩元素a，b∈G都有a=b，對偶地，若對于任意地滿足m'=n'的兩元素m，n∈M 都有m=n，則稱該形式背景為凈化的.對于這樣的a，b與m，n可進行刪減保留其一.如下面例題所示.

表1 形式背景(G，M，I)Table 1 Formal context(G，M，I)

例1.設形式背景(G，M，I)如表1 所示，G={1，2，3，4，5，6，7}，M={a，b，c，d，e，f，i}.由于 c'=a'，所以根據定義 1 只需保留a，c中的一員，這里保留c.因為根據定義1，除去a，c之外的其他的屬性都必須保留，再根據定義1，所有的對象滿足:x'=y'當且僅當x=y.所以(G，M，I)經過凈化后的形式背景如表2所示.

定義2［6］.形式背景(G，M，I)的所有約簡為{Di|Di是約簡，i∈τ}(τ為一個指標集)，可將屬性M劃分為三種類型:

表2 凈化表1后的形式背景Table 2 Clarified table 1 formal context

為了表述方便，在下文中，將定義2的③中給出的絕對不必要屬性，以及定義1的2)中在凈化過程中被刪除掉的相對必要屬性，統一稱為不必要屬性.這樣就將核心屬性以及經過定義1的2)中在凈化過程中被保留下來的相對必要屬性，統一稱為必要屬性.

2.2 圖論

定義 3［11］.

1)有向圖的定義:將 G={V(G)，E(G)，ψ(G)}這種數學結構稱為一個圖，其中V(G)為一個非空集合，ψ(G)表示一個映射從集合E(G)到V(G)×V(G)，則稱G是一個以V(G)為頂集合.以V(G)為邊集合的有向圖，V(G)中的元素稱為圖G的頂點，E(G)稱為G的邊，ψ(G)稱為G的關聯函數.若 ψG(e)=(u，v)，e∈E(G)，(u，v)∈V(G) × V(G)則簡寫成e=uv，其中u表示有向邊e的尾，v表示有向邊e的頭.

2)若 G 是一個有向圖，V(G)={v1，v2，v3，…，vv}，E(G)={e1，e2，e3，…，eε}為有向弧集，則稱矩陣 B(G)=(bij)v×ε為有向圖G的關聯矩陣，其中

3 基于關聯矩陣的形式背景屬性約簡

本節給出基于關聯矩陣的屬性約簡的算法及相關定理.

3.1 屬性約簡

根據定義3能夠將形如表2這種凈化的形式背景轉化為形如表3的形式.其中列表示兩兩屬性之間具有覆蓋關系所形成的邊，行表示單個屬性，表中的-1，0，1是根據有向圖中弧的頭與尾的性質寫出的.例如，根據上面的描述可以將表2形式背景轉化為如表3所示.

表3 由關聯矩陣生成的表Table 3 Table generated by an association matrix

在表3中第二行表示與屬性b有覆蓋關系的屬性所形成的邊ebe和 ebf，屬性 b分別是邊 ebe和ebf的尾，用1表示;屬性b與其它剩余屬性沒有覆蓋關系，即在第二行與 ece，ecd，ede對應出分別用0進行表示;在表3中第三行表示與屬性c有覆蓋關系的屬性所形成的邊ece和edc，屬性c分別為ece和 edc的尾與頭，并分別用1和-1表示，屬性c與其它剩余屬性沒有覆蓋關系，即在第二行與ebe，ebf，ede對應出分別用0進行表示.

通過對表3觀察可以看出:根據關聯矩陣得到的兩兩屬性間與每個屬性的關聯關系，通過-1，0，1的形式反映在所生成表的每一行中，因此，只需要觀察比較每一行就可以對屬性進行分類.

在形式背景中，屬性之間又有著一定的關聯關系，對這種屬性間的關系給出下面定義:

定義 4.在形式背景(G，M，I)中，其中，G={1，2，3，…，n}，M={a，b，c，…，m}存在 g(mi)所包含的對象都可以在 g(mj)中找到，并且g(mi)≠g(mj)，就稱g(mj)與g(mi)是覆蓋關系.

例 2.在形式背景(G，M，I)中，其中 G={1，2，3，4，5}，M={a，b，c，d}.a'={1，5}，b'={1，2，5}，c'={2，4}，d'=(3，5).

解:由于 a'={1，5}，b'={1，2，5}，a'所包含的對象都可以在b'中找到，因此a'與b'是覆蓋關系.

由關聯矩陣生成的表中，每一行的構成情況不同，若這一行全為0或全為-1給出如下定理1、定理2.

定理1.在凈化后的形式背景(G，M，I)中，在M中任取一個 mi∈M，如果對({M － mi}都有 G(mi，eij)=0，則(m'i，mi)∈L(G，M，I).

證明:在(G，M，I)中，任取 mi∈M，如果對{M －mi}都有G(mi，eij)=0，那么由定義4可知，mi與{M －mi}中任一屬性都沒有覆蓋與被覆蓋的關系，由概念格的定義可得(m'i，mi)∈L(G，M，I).

定理3.在凈化后的形式背景中(G，M，I)，任取mi∈M如果G(mi，eij)=1，且{M－mi}中至少存在一元僅與mi有邊相連當且僅當mi為不必要屬性.

證明:必要性:在(G，M，I)中，任取 mi∈M，如果對{M －mi}有G(mi，eij)=1，由定義4可知 mi與{M －mi}中任一屬性都有被覆蓋的關系，即mi∩{M－mi}=mi，又因為{M－mi}中至少存在一元僅與mi有邊相連，即在{M－mi}中存在mj，i≠j，mj僅與 mi有覆蓋關系且 mi∩mj=mi，有定義 1 知mi不是概念的內涵，因此mi為不必要屬性.

充分性:mi為不必要屬性，即mi不是該背景概念的內涵.有定義3知對{M －mi}有 G(mi，eij)=1，mi與{M － mi}中任一屬性都有被覆蓋的關系，若{M－mi}中不存在一元僅與mi僅有邊相連，則mi與為不必要屬性矛盾.

推論1.根據給出的不必要屬性和必要屬性的定義，得知mi為核心屬性的充分必要條件是:在凈化后的形式背景中(G，M，I)，任取mi∈M 如果mi對{M －mi}中任意一元都有G(mi，eij)= －1 或都有 G(mi，eij)=0，或有 G(mi，eij)= －1或 G(mi，eij)=0.

證明:必要性:在(G，M，I)中，任取 mi∈M，對{M －mi}中任意一元都有G(mi，eij)=－1，由定義4可知，mi與{M －mi}中任一屬性都有覆蓋關系，有定義1知，mi必為該背景的內涵，再由定理2得mi是核心屬性.同理可得，任取mi∈M，對{M－mi}中任意一元都有G(mi，eij)=0，由定義4可知，mi與{M－mi}中任一屬性都沒有覆蓋關系，若去掉則會造成概念的確實，有定義1、定理1知，mi必為該背景的內涵，故mi是核心屬性.任取mi∈M，對{M－mi}中任意一元都有 G(mi，eij)= －1 或 G(mi，eij)=0.結合上述兩種情況易得 mi是核心屬性.

充分性:根據必要屬性的定義以及定理3，mi必為該背景的內涵，可以證得mi為核心屬性.

對形式背景(G，M，I)的屬性約簡過程中，由于對于同一形式背景，由于兩兩屬性之間的覆蓋關系是唯一的，所以根據G(mi，eij)所得到的表是唯一的.以下這幾種情況對于任一個mi∈M一定滿足且僅滿足如下情況a，b，c中的一個.

a.如果mi是核心屬性，則mi行有且只有以下三種情況a.1，a.2，a.3 之一發生.

a.1如果mi對{M －mi}中任意一元都有G(mi，eij)= －1，即這一行全為-1時，則mi是核心屬性.

a.2如果 mi對{M －mi}中的任意屬性，都有 G(mi，eij)=0，即這一行全為0時，則mi是核心屬性.

a.3如果 mi對{M －mi}中的任意屬性，都有 G(mi，eij)=－1或G(mi，eij)=0，即這一行由0和-1構成時，則 mi是核心屬性.

事實上，在(G，M，I)中，在 M 中任取一個 mi，mi∈M，如果對{M －mi}都有G(mi，eij)= －1，由定義4 可知，mi與{M －mi}中任一屬性都有覆蓋關系，由概念格同構的定義可得(m'i，mi)∈L(G，M，I)，a.2、a.3 情況同理可得.故 mi是核心屬性.

b.如果mi是絕對不必要屬性，則mi行有且只有以下兩種情況 b.1、b.2 之一發生.

b.1若第i行全為1，且{M－mi}中至少存在一元僅與mi有邊相連，則mi是不必要屬性.

b.2若第i行由0，1組成，且{M－mi}中至少存在一元僅與mi有邊相連，則mi是不必要屬性.

事實上，在(G，M，I)中，在 M 中任取一個 mi，mi∈M，如果對{M －mi}都有G(mi，eij)=1，由定義4可知，mi被{M －mi}中任一屬性都有覆蓋關系，由概念格同構的定義，去掉mi后不影響格的結構，即(m'i，mi)L(G，M，I)，情況二同理可得，故mi是不必要屬性.

c.對于形式背景中的某一屬性如果不滿足a，也不滿足b時，則該屬性歸為相對必要屬性.

事實上，由定義2可知，在一個形式背景中，屬性分為三類絕對必要屬性、相對必要屬性、絕對不必要屬性，如果屬性mi不滿足a同時也不滿足b時，即屬性mi既不滿足必要屬性的條件也不滿足絕對不必要屬性的條件，則必有mi是相對必要屬性的結果.

3.2 算法步驟

在凈化后的形式背景(G，M，I)，結合圖論以及上面的情況分析，給出計算出形式背景的屬性約簡算法.

算法1.

輸入:凈化形式背景(G，M，I)，其中 G=(1，2，3，…，n)，M={m1，m2，m3，…，mn}.

2.2若第i行由0，1組成，且{M－{mi}}中至少存在一元僅與mi有邊相連，則D3=D3∪ {mi}，轉Step 4;否則，轉Step 3;

Step 3.D2=D2∪ { mi}，轉Step 4;

Step 4.若 i＜n+1，則 i=i+1，轉 Step 1;

若 i≥n+1，算法停止.

3.3 算法正確性分析

在凈化形式背景(G，M，I)中，由于屬性的個數是M={m1，m2，m3，…，mn}有限的，即 n 是有限的，因此可以得到 i≥n+1，即在有限步內算法一定會結束.當算法結束時，根據推論1，輸出的D1為核心屬性，根據3.1中c的分析，輸出的D2是相對必要屬性，根據推論1，輸出的D3是不必要屬性，故而，當算法結束時，輸出的D1、D2、D3三個集合就是所需要的屬性分類結果.

3.4 算法復雜度分析

根據算法1可以看出:Step 1對凈化后的形式背景(G，M，I)中屬性M進行處理，首先根據關聯矩陣生成G(mi，eij).觀察第i行每一個eij對應數值，對其后續進行判斷是否滿足1.1、1.2 或者 1.3 的條件，若滿足其一則并入 D1，若不滿足轉至Step 2，再進行判斷是否滿足2.1或者2.2的條件，若滿足則并入D3，否則轉入Step 3并入D2.所以Step 1的復雜度為O(3|M|)，Step 2的復雜度為O(6|M|)，Step 3的復雜度為O(6|M|).所以算法1的復雜度為O(|M|)，其中|M|為該形式背景中屬性的個數.

通過此算法，可以清楚地看到屬性之間的關聯關系，并可以方便地求出該形式背景在凈化后的屬性約簡.

文獻［7］是在建立好的樹圖上進行屬性約簡，這時文獻［7］的求屬性約簡的算法的時間復雜度為O(|M|2)，然而，根據文獻［7］建立樹的過程，僅僅樹的根節點的(a'，a)，就需要遍歷屬性集M中所有的元，對于M中的每一個元a求取a'的復雜度為|G|，這樣僅僅求得根節點一項，文獻［7］的復雜度為O(|G||M|);再從根節點向下的第一步，必須考慮除去根節點之外的其他屬性對應的一些性質，如此，文獻［7］的時間復雜度至少為O(|G||M|+|M|2).與算法1的復雜度O(|M|)，文獻［7］受|G|、|M|的影響，當|G|和|M|趨于很大時，O(||G||M|+|M|2|)遠大于O(|M|)，因此算法1相比較文獻［7］的算法更高效.

文獻［8］求屬性約簡的算法的時間復雜度為O(||G||M|+8|M|2|)，與算法1的復雜度O(|M|).相比，當M的數量增大時，O(8|M|2)大于O(|M|).因此，總體而言，算法1較文獻［8］的算法更快捷.

文獻［9］的求屬性約簡的算法的時間復雜度為O(|M|2)，當|M|趨于很大時，O(|M|2)遠遠大于O(|M|)，所以算法1更為方便有效.

從上面的分析可以看出，較已有的用圖論方法求取屬性約簡，特別是對凈化后的形式背景進行圖論方法求得屬性約簡，算法1時間復雜度低，因此快捷和方便.

4 實例

下面給出實例對算法1的有效性進行驗證.

例3.某學校為及時了解學生對不同學科的學習掌握程度，定期會對學生的測試成績進行分析，用以掌握整體學習狀況，同時便于教師及時對各個班授課內容的難易程度，根據各班學生掌握程度做出調整.近期對初一年級七個班的數學成績分布情況進行了統計，并對各個班成績中較為集中的區間標記出來.下面以表格的形式給出初一年級7個班數學成績的形式背景(G，M，I)，其中G表示班級，M表示成績區間，記G={1，2，3，4，5，6，7}，M={a，b，c，d，e，f，g，h，i，k}.具體為 a到 k分別代表分數段:a:0-10，b:10－20，c:20－30，d:30－40，e:40 －50，f:50 －60，g:60 －70，h:70 －80，i:80 －90，k:90 －100，具體情況如表4所示.

表4 形式背景(G，M，I)Table 4 Formal context(G，M，I)

首先由定義1可以看出，形式背景(G，M，I)是可以凈化的.屬性a與屬性k是可以合并保留其一，此處保留屬性a.再根據定義3寫出關聯矩陣G(mi，eij)，如表5所示.

表5 通過表4轉化關聯矩陣Table 5 Transform the incidence matrix through table 4

a所在的行既不全為-1也不全為0，不滿足算法1中步驟1.1和步驟1.2的條件，同樣地，也不是由-1和0構成，故轉至Step 2.a所在的行由-1和0組成，同時通過表5可以看出在{M－{a}}中僅存在h與a有一條邊相連，滿足算法1中步驟2.2的條件，因此a為不必要屬性，即

同理，d所在的行經判斷也滿足算法1中的步驟2.2的條件，因此d也為不必要屬性即

b所在的行既不全為-1也不全為0不滿足算法1中的步驟1.1和1.2的條件，這一行也不是由-1和0構成，同樣地，也不滿足算法1中步驟1.3的條件，故之轉至Step 2.b所在的行由1和0構成不滿足算法1中步驟2.1，轉到算法1中的步驟2.2，但是在{M －{a}}中 c與 b，d，e都有邊相連，不滿足算法1中的步驟2.2，{M－{a}}中存在c僅與b有一條邊相連這一條件，故轉至Step 3.因此D2=D2∪{a}.同理，c所在的行經判斷也為相對必要屬性，即D2=D2∪{c}.

d所在的行既不全為-1也不全為0不滿足算法1中步驟1.1和1.2的條件，但是第d行由-1和0構成，滿足算法1中步驟1.3，因此 D1=D1∪g0gggggg.同理，e，h，g 所在的行分別也屬于 D1即 D1=D1∪{e，h，g}.

i不全為-1組成，不滿所在的行全為-1算法1中步驟1.1，但i所在的行全為0滿足步驟1.2，因此D1=D1∪{i}.

綜上所述，可將該形式背景(G，M，I)劃分為三類:必要屬性:e，f，h，i，g;相對必要屬性:b，c;不必要屬性:a，d.因此該形式背景(G，M，I)的約簡掉不必要屬性屬性后為{b，e，f，h，i，g}或{c，e，f，h，i，g}.

通過分析不難發現，初一數學成績整體上服從正態分布曲線，成績主要集中在50-70分之間.1班成績分布比較兩極分化，表明學生掌握情況相對較差，授課內容應以基礎知識為主，使學生更容易接受;2班、3班成績分布較為分散，表明學生掌握情況比較差，授課內容應當也以基礎知識為主;4班、5班、6班成績分布較為平均，學生掌握情況較好，授課內容適當增加習題練習;7班成績比較優異，說明在七個班中學生掌握程度最好，授課內容時可適當增加難題的聯系.

在本實例中，|G|=7，|M|=9，根據分析可知，算法1的時間復雜度為O(|M|)=O(9).而利用文獻［7］上面的表4的算法時間復雜度為.O(|G||M|+|M|2)=O(7×9+92)=O(|144)利用文獻［8］對上面的表4的形式背景進行約簡的算法時間復雜度為O(|G||M|+8|M|2)=O(7×9+8×92)=O(711)，利用文獻［9］的上面的表4的求屬性約簡的算法的時間復雜度為O(|M|2)=O(92)=O(81)，經比較算法1時間復雜度更低.因此，本算法更加簡單便捷.

5 結束

在凈化后的形式背景中，利用關聯矩陣并結合有向圖中弧的頭與尾之相關性質，以生成屬性關聯關系表，不僅可以直接地觀察到兩兩屬性間的關聯關系，而且還能快速、高效地對屬性進行劃分，并完成屬性約簡，由此得到屬性約簡算法.還通過實例對算法的可行性進行了驗證.通過本文給出的算法，不僅可以對屬性進行約簡，而且還可以通過關聯矩陣生成的表觀察出兩兩屬性之間的關聯關系;同時本文的算法還適用于很多情況，例如數據處理、動態教學分析、用戶喜好分析等.此外，本算法為數據分析以及關聯規則的提取也提供了一種新的思考角度，進一步擴充了屬性約簡方法.今后，對于關聯矩陣的屬性約簡仍需進一步研究，提高對數據處理以及應用的效率.