基于矩陣信息熵的形式背景動(dòng)態(tài)屬性約簡(jiǎn)方法

關(guān)鍵詞：形式概念分析，粒約簡(jiǎn)，動(dòng)態(tài)屬性約簡(jiǎn)，信息熵，對(duì)角矩陣條件熵，對(duì)象粒對(duì)角矩陣

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A

在大數(shù)據(jù)時(shí)代，數(shù)據(jù)集規(guī)?？焖贁U(kuò)張，從海量數(shù)據(jù)中挖掘有價(jià)值的信息并轉(zhuǎn)化為知識(shí)顯得非常必要. 1982 年，數(shù)學(xué)家Wille［1］對(duì)哲學(xué)中的“概念”一詞給出數(shù)學(xué)化表達(dá)，提出形式概念分析理論（Formal Concept Analysis，F(xiàn)CA）. FCA通過(guò)挖掘概念和構(gòu)建格結(jié)構(gòu)為知識(shí)發(fā)現(xiàn)提供了強(qiáng)有力的理論依據(jù)，其中屬性約簡(jiǎn)通過(guò)去除不重要的屬性，不僅提高了數(shù)據(jù)分析結(jié)果的質(zhì)量，還減少了計(jì)算過(guò)程中的資源需求和時(shí)間消耗. 但在真實(shí)應(yīng)用場(chǎng)景下數(shù)據(jù)集往往會(huì)發(fā)生變化，如數(shù)據(jù)集的屬性隨時(shí)間的推移增加或減少，亟待一種屬性約簡(jiǎn)算法來(lái)處理數(shù)據(jù)呈現(xiàn)的動(dòng)態(tài)特征，因此基于較大規(guī)模數(shù)據(jù)集研究快速高效的屬性約簡(jiǎn)算法具有重要的意義.

在現(xiàn)有的FCA 理論中，屬性約簡(jiǎn)可以在靜態(tài)和動(dòng)態(tài)兩種環(huán)境下進(jìn)行. 靜態(tài)屬性約簡(jiǎn)算法最早由Ganter and Wille［2］建立基于對(duì)象集或?qū)傩约募s簡(jiǎn)框架. Zhang et al［3］保持概念格的結(jié)構(gòu)和層次不變，提出一種基于辨識(shí)矩陣的屬性約簡(jiǎn)方法.為了進(jìn)一步簡(jiǎn)化Zhang et al［3］的工作，Qi et al［4］提出一種新的辨識(shí)矩陣，然而利用辨識(shí)矩陣來(lái)計(jì)算約簡(jiǎn)將導(dǎo)致高時(shí)間消耗，是難以直接求解的非確定性多項(xiàng)式難（Non?deterministic Polynomial?hard，NP?hard）問(wèn)題. 因此，張清新［5］提出基于布爾矩陣的概念格屬性約簡(jiǎn)方法. Wu et al［6］首次提出概念格的粒約簡(jiǎn)，討論粒結(jié)構(gòu)及其在知識(shí)約簡(jiǎn)中的應(yīng)用，引起了研究者們的注意. Shao et al［7-8］從向量的線性相關(guān)性的角度來(lái)考慮屬性約簡(jiǎn)和屬性特征，針對(duì)模糊形式背景進(jìn)行粒約簡(jiǎn)，給出了不需要構(gòu)造格結(jié)構(gòu)的基于辨識(shí)矩陣約簡(jiǎn)方法.Huang et al［9］提出信息熵和條件信息熵來(lái)衡量屬性的顯著性并開發(fā)了一種啟發(fā)式算法. Lin et al［10］定義矩陣來(lái)表示形式概念的外延和內(nèi)涵，在此基礎(chǔ)上研究不可約元，為形式概念分析中的粒約簡(jiǎn)提供了新的框架. Zhang et al［11］進(jìn)一步將基于矩陣的粒約簡(jiǎn)方法推廣到協(xié)調(diào)決策形式背景. 陳東曉等［12］從信息粒角度提出形式背景上基于信息熵的屬性約簡(jiǎn)方法. 賀青青等［13］在陳東曉等［12］的基礎(chǔ)上從信息熵和布爾矩陣的角度研究了形式背景的屬性約簡(jiǎn)，提出高效的屬性約簡(jiǎn)的新方法.Chen et al［14-15］基于圖論框架提出FCA 的啟發(fā)式粒約簡(jiǎn)算法.

在真實(shí)的應(yīng)用場(chǎng)景下，數(shù)據(jù)集往往不斷地變化更新，勢(shì)必對(duì)原形式背景的粒約簡(jiǎn)結(jié)果產(chǎn)生一定的影響，因此，不少研究者探討了動(dòng)態(tài)屬性約簡(jiǎn)算法，例如，黃桃林等［16］討論了形式背景的逐個(gè)對(duì)象增加之后原粒約簡(jiǎn)的變化規(guī)律，通過(guò)構(gòu)造粒辨識(shí)屬性矩陣來(lái)更新相應(yīng)的約簡(jiǎn). Li et al［17］結(jié)合了認(rèn)知算子，研究對(duì)象和屬性同時(shí)增加時(shí)形式背景的新粒約簡(jiǎn)更新算法. Niu and Chen［18］討論了屬性集在形式背景中更新時(shí)的粒約簡(jiǎn)更新機(jī)制，并進(jìn)一步開發(fā)了相應(yīng)的增量算法.

形式背景靜態(tài)屬性約簡(jiǎn)方法往往需要從頭開始計(jì)算而不能充分利用已有約簡(jiǎn)結(jié)果，缺乏適應(yīng)真實(shí)應(yīng)用場(chǎng)景的增量更新機(jī)制. 動(dòng)態(tài)屬性約簡(jiǎn)方法雖然利用已有的約簡(jiǎn)結(jié)果設(shè)計(jì)相應(yīng)的更新機(jī)制，但缺乏快速更新的運(yùn)算方法，也不適合較大規(guī)模的數(shù)據(jù)集，需進(jìn)一步提高計(jì)算效率. 本文受賀青青等［13］和Xu and Yang［19］的啟發(fā)，利用矩陣快速運(yùn)算特性，在定義對(duì)象粒對(duì)角矩陣后，研究形式背景屬性集更新時(shí)基于矩陣信息熵的粒約簡(jiǎn)更新機(jī)制，并進(jìn)一步設(shè)計(jì)動(dòng)態(tài)快速屬性約簡(jiǎn)算法.

本文的主要貢獻(xiàn)如下.

（1）定義對(duì)象粒對(duì)角矩陣，引入對(duì)象粒對(duì)角矩陣信息熵、對(duì)象粒對(duì)角矩陣條件熵、DMCE （Di?agonal Matrix Conditional Entropy）屬性內(nèi)外重要性度量，討論基于矩陣信息熵的形式背景屬性約簡(jiǎn)算法MEAR （Matrix Entropy Attribute Redcu?tion）.

（2）探討動(dòng)態(tài)形式背景下屬性增加和屬性刪除兩種情況下對(duì)象粒對(duì)角矩陣的動(dòng)態(tài)更新機(jī)制，并給出對(duì)應(yīng)的基于矩陣信息熵屬性約簡(jiǎn)算法MEAR_add 和MEAR_del.

（3）在UCI 六個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)驗(yàn)證. 結(jié)果表明在面對(duì)較大規(guī)模數(shù)據(jù)集時(shí)，提出的屬性約簡(jiǎn)算法比其他算法在運(yùn)行時(shí)間上更具優(yōu)勢(shì).

命題4 和命題5 主要依賴于對(duì)角矩陣條件熵分別計(jì)算DMCE 屬性內(nèi)重要度和DMCE 屬性外重要度，與定義6 和定義7 的計(jì)算結(jié)果是一致的.

推論2 給定矩陣信息熵屬性約簡(jiǎn)集的判定方法，主要依賴于對(duì)角矩陣信息熵和對(duì)角矩陣條件熵的計(jì)算，與定理3一致.

2. 2矩陣信息熵約簡(jiǎn)算法MEAR 矩陣信息熵約簡(jiǎn)算法為靜態(tài)約簡(jiǎn)算法，為動(dòng)態(tài)形式背景的矩陣信息熵約簡(jiǎn)算法奠定基礎(chǔ)，步驟如算法1 所示. 步驟2計(jì)算對(duì)象粒矩陣和對(duì)象粒對(duì)角矩陣，步驟3～8獲得核心屬性集，步驟9～16 以核心屬性集作為初始約簡(jiǎn)子集，主要是從非核心屬性集中找出相對(duì)必要屬性，直至確定剩下的屬性都是不必要屬性.

3動(dòng)態(tài)形式背景上的快速屬性約簡(jiǎn)方法

在形式背景中，當(dāng)屬性發(fā)生變化后，往往需要重新計(jì)算，不能充分利用已有的約簡(jiǎn)結(jié)果，并且需要耗費(fèi)大量的時(shí)間. 數(shù)據(jù)集的屬性變化分為增加屬性和刪除屬性，因此，提出了兩種動(dòng)態(tài)形式背景上的快速屬性約簡(jiǎn)方法，它們利用矩陣快速運(yùn)算的特性，在先前獲得的約簡(jiǎn)結(jié)果的基礎(chǔ)上對(duì)屬性進(jìn)行更新，這將在很大程度上降低算法的時(shí)間復(fù)雜度.

3. 1動(dòng)態(tài)形式背景上增加屬性時(shí)的矩陣信息熵屬性約簡(jiǎn)方法

3. 1. 1增加屬性時(shí)的矩陣信息熵屬性約簡(jiǎn)方法的動(dòng)態(tài)更新機(jī)制 形式背景添加屬性時(shí)矩陣條件熵的動(dòng)態(tài)更新方法的更新機(jī)制的關(guān)鍵是添加屬性后，對(duì)象粒矩陣和對(duì)象粒對(duì)角矩陣如何更新.

步驟2 使用定義5和命題9分別計(jì)算約簡(jiǎn)屬性集的對(duì)象粒對(duì)角矩陣、更新后的對(duì)象粒對(duì)角矩陣.

步驟4～12，當(dāng)新屬性集的矩陣信息熵大于等于原約簡(jiǎn)屬性集的矩陣信息熵時(shí)，在可選屬性集中選出DMCE屬性外重要度最大的屬性加入新約簡(jiǎn)集.

步驟13～19，刪除不必要屬性.

4實(shí)驗(yàn)

4. 1實(shí)驗(yàn)設(shè)置 為了構(gòu)建實(shí)驗(yàn)所需的形式背景，從UCI 機(jī)器學(xué)習(xí)庫(kù)中下載六個(gè)數(shù)據(jù)集，其詳細(xì)信息如表2 所示. 構(gòu)建形式背景只考慮條件屬性，因此首先刪除標(biāo)簽信息，同時(shí)鑒于所選數(shù)據(jù)集的屬性值不滿足0 或1，需對(duì)數(shù)據(jù)集進(jìn)行離散化處理來(lái)生成形式背景. 若屬性值是實(shí)值或整數(shù)數(shù)據(jù)時(shí)，將該屬性劃分為n 個(gè)不相交的區(qū)間，如果它們屬于相應(yīng)的區(qū)間，就會(huì)被n 替代. 若屬性值是類別數(shù)據(jù)，不做特殊處理. 然后，使用獨(dú)熱編碼（one?hot encod?ing）方式為每個(gè)屬性編碼，再將所有屬性的獨(dú)熱編碼拼接得到新的形式背景.

所有算法基于Pycharm 環(huán)境由Python語(yǔ)言編程實(shí)現(xiàn)，并在Intel i7?10510U 1. 80 GHz CPU、16. 0 GB 內(nèi)存和64 位Windows 10操作系統(tǒng)的計(jì)算機(jī)環(huán)境下運(yùn)行.

4. 2MEAR_add算法的時(shí)間性能對(duì)比與分析

為了驗(yàn)證本文提出的算法的性能，從運(yùn)行時(shí)間角度對(duì)提出的MEAR_add 算法與現(xiàn)有兩種屬性約簡(jiǎn)算法進(jìn)行對(duì)比，包含靜態(tài)屬性約簡(jiǎn)算法MEAR 和動(dòng)態(tài)屬性約簡(jiǎn)算法FC_IGR［13］. 此外，為了更好地驗(yàn)證增加屬性數(shù)量對(duì)算法的影響，對(duì)表2 中的每個(gè)數(shù)據(jù)集構(gòu)建五個(gè)測(cè)試集，分別隨機(jī)選擇10%，20%，30%，40% 和50% 的屬性數(shù)量作為新增屬性數(shù)據(jù)集，剩余屬性構(gòu)成初始數(shù)據(jù)集.

圖1 為三種算法在不同數(shù)據(jù)集上運(yùn)行時(shí)間的結(jié)果對(duì)比，顯示了不同的變化趨勢(shì). 由圖1 可見，隨著屬性集比例的不斷增加，F(xiàn)C_IGR 和MEAR_add算法的計(jì)算時(shí)間呈上升趨勢(shì)，基于矩陣的MEAR和MEAR_add 算法的運(yùn)行時(shí)間明顯比FC_IGR 算法短. 從子圖可以看出，MEAR_add 算法的計(jì)算時(shí)間最短. 特別地，對(duì)于小規(guī)模數(shù)據(jù)集Zoo，Car 和Wine，MEAR_add 算法的時(shí)間消耗僅是FC_IGR算法的幾分之一. 對(duì)于較大規(guī)模數(shù)據(jù)集如Abalo?ne，Clave 和Bean，MEAR_add 算法的時(shí)間消耗僅是FC_IGR 算法的幾十分之一，具有顯著的優(yōu)勢(shì).三種算法所取得的屬性約簡(jiǎn)結(jié)果一致，因此，MEAR_add 算法的計(jì)算效率更高.

4. 3MEAR_del 算法的對(duì)比與分析 為了驗(yàn)證本文提出的算法的性能，從運(yùn)行時(shí)間的角度對(duì)提出的MEAR_del 和MEAR 算法與FC_DGR［13］算法進(jìn)行對(duì)比分析. 此外，為了更好地驗(yàn)證刪除屬性數(shù)量對(duì)算法的影響，對(duì)表2 中的每個(gè)數(shù)據(jù)集構(gòu)建五個(gè)測(cè)試集，分別隨機(jī)選擇10%，20%，30%，40% 和50%的屬性數(shù)量作為刪除屬性數(shù)據(jù)集，全部屬性構(gòu)成初始數(shù)據(jù)集.

圖2顯示了不同數(shù)據(jù)集屬性變化時(shí)算法的變化趨勢(shì). 由圖2 可見，隨著刪除屬性集的不斷增加，F(xiàn)C_IGR 算法的計(jì)算時(shí)間增加. 從子圖可以看出，除Zoo 數(shù)據(jù)集外，其他數(shù)據(jù)集上MEAR_del 算法的計(jì)算時(shí)間明顯低于其他算法. 特別是對(duì)于較大規(guī)模數(shù)據(jù)集Abalone，Clave 和Bean，MEAR_del算法的時(shí)間優(yōu)勢(shì)更加明顯. 三種算法所取得的屬性約簡(jiǎn)結(jié)果是一致的，因此，MEAR_del 算法的計(jì)算效率更高.

5結(jié)論

本文提出一種動(dòng)態(tài)形式背景下基于矩陣信息熵的屬性特征約簡(jiǎn)算法. 首先定義對(duì)象粒對(duì)角矩陣、對(duì)角矩陣信息熵、對(duì)角矩陣條件熵等概念，在此基礎(chǔ)上探討形式背景下屬性增加和屬性刪除時(shí)對(duì)象粒對(duì)角矩陣的動(dòng)態(tài)更新機(jī)制；其次，設(shè)計(jì)相應(yīng)的基于矩陣信息熵的屬性約簡(jiǎn)算法MEAR_add 和MEAR_del；最后通過(guò)實(shí)驗(yàn)驗(yàn)證提出的算法的高效性.

面對(duì)較大規(guī)模的動(dòng)態(tài)數(shù)據(jù)環(huán)境時(shí)，本文方法還存在一定局限，例如，對(duì)象和屬性同時(shí)更新時(shí)的對(duì)象粒更新機(jī)制未被建立，以及對(duì)三支概念格的屬性粒約簡(jiǎn)方法未探討. 因此，未來(lái)將對(duì)上述問(wèn)題進(jìn)行深入研究.

（責(zé)任編輯 高善露）