基于信息熵的粗糙集屬性應急數據去重挖掘算法研究

曾維佳 秦放 李琳 徐鵬

摘 要：主動學習已經被證明是一種成功的機器學習算法，最主要的缺點是它只注重樣本的標簽信息而忽略了樣本的分布信息。因此帶來的后果就是穩定性差，容易陷入局部最優解，同時對初始樣本的選擇非常敏感。論文將稀疏子空間聚類與主動學習相結合，首先利用稀疏子空間聚類找到原始數據的分布信息，然后利用該信息指導主動學習選取初始樣本，使樣本標注更加有效，提高了主動學習的效率，同時降低了主動學習對初始樣本的敏感度。最后通過多組仿真實驗證明，本方法可以有效的改善主動學習的性能。

關鍵詞：主動學習;稀疏子空間;聚類

中圖分類號：TP391.9 ? ? ?文獻標識碼：A

主動學習作為一種成功的機器學習，已經廣泛的應用于生物、醫學和材料等領域。例如研究細胞蛋白質的相互作用，通過實驗驗證的代價非常大，利用主動學習，可以在有限的樣本基礎上進行訓練，然后有效的預測蛋白質間是否具有相互作用，從而大大降低了實驗代價。

但是傳統的主動學習對初始值比較敏感。選擇不同的樣本作為初始樣本集，最終通過學習得到的分類模型可能會有很大的差異。有的效果非常好，有的雖然經過多次的迭代但效果仍然很差，表現很不穩定。導致這種現象的一個主要原因是，主動學習在選擇樣本時沒有考慮數據集本身的結構分布特點。

主動學習要進行第一次迭代之前，需要建立一個初始分類模型，用于選擇信息含量最大的樣本。所以，傳統的主動學習在迭代之前，首先要隨機選取一定量無標簽樣本，提交給專家標注。這些標注好的樣本就構成了初始有標簽樣本集L（0）。在實際應用中，要選擇合適的L（0）非常困難，為了降低主動學習對初值的敏感性，增強主動學習的魯棒性，許多學者提出了一些降低對初始值敏感程度的主動學習方法。2012年Swarnajyoti等人提出了一種基于預聚類的主動學習方法SPLB[1][2]。SPLB算法與傳統的主動學習方法不同，它優先選取稀疏區域的樣本進行標注。實驗證明，該方法可以提高樣本的使用效率，加快了主動學習的收斂速度。但是上述算法仍存在問題，該算法只能處理簡單、線性可分的數據集，沒有考慮到現實生活中大量高維非線性數據集的情況，處理復雜數據集的效果并不理想。

受上述思想的啟發，結合稀疏子空間算法的優點，提出了一種改進的主動學習算法，同時結合了樣本的標簽信息和分布信息。首先在迭代之前，采用基于稀疏子空間聚類，找到嵌入高維空間的低維結構，并利用此結構信息來指導主動學習選擇需要標注的樣本，提高標記樣本的利用率。同時，由于掌握了數據集的整體分布信息，降低了陷入局部最優的概率，提高了主動學習的效率。

1 稀疏子空間聚類

稀疏子空間聚類[3]是近幾年來研究熱點，它的主要思想是現實生活中的高維空間，由于數據間存在的內在聯系，在本質上是屬于多個低維子空間并集，可以用低維空間的線性組合來表達，這種線性表達還可以用來刻畫不同低維子空間的相似度。然后利用拉普拉斯特征映射根據相似度矩陣進行聚類。

2 稀疏子空間聚類與主動學習的結合

本節的核心是將稀疏子空間聚類和主動學習結合在一起。為了最大限度的降低主動學習中標注樣本的代價，我們需要盡量挖掘主動學習中各部分的信息。本節的核心就是挖掘無標簽樣本的結構信息，為主動學習的初始化提供指導，從而提高主動學習的效率和效果。

在主動學習的初始化階段，先用稀疏子空間聚類找到原始數據集的子空間結構，然后對子空間進行聚類，再挑選到兩個聚類中心距離差最小的樣本來標記，作為主動學習的初始樣本集。由于利用了數據集的結構信息，因此能有效的找到全局最優解。

下面以主動學習中最常用的SVM算法為例，處理二分類問題。具體的算法如下表1所示：

3 算法有效性驗證

為了評估論文算法的性能，作者在不同的標準數據集上進行了對比仿真實驗。論文所需的數據都是來自公開數據集LIBSVM[5]。為了測試論文算法的有效性，文中與多種學習算法進行比較：

Passive：被動學習支持向量機：該方法在每次迭代時，隨機選取k個樣本進行標注，并用來更新模型。

ALSVM：傳統的主動學習支持向量機算法：該方法選擇k個不確定性最強的樣本進行標注，作為支持向量來更新模型。

SPLB：由Swarnajyoti等人提出的方法。在主動學習迭代之前，先對數據集進行預聚類處理，然后在數據稀疏的區域建立初始分類超平面。該算法與文中算法類似，因此作為文中算法的主要比較對象。

Proposed：基于稀疏子空間聚類的主動學習算法。

3.1 USPS數據集驗證

為了驗證基于稀疏子空間的拉普拉斯特征映射算法的有效性，將該算法應用到目前比較流行的公開數據集LIBSVM。以其中的USPS數據集為例，通過這個數據集來仿真驗證論文算法的效果。

USPS是一個被廣泛使用的手寫字符識別數據集，里面包含七千多個數字字符（數字0-數字9）。

為了構成一個二分類的問題，本次實驗隨機選取一個數字6來進行驗證。為了構成能使用支持向量機處理的二分類問題，將數字6的類別標簽設為+1，其余的圖片樣本標簽設為-1。這種策略經常用來處理多分類問題。

支持向量機超參數C=100，高斯核的超參數γ=0.01。

實驗選擇10個樣本作為初始有標簽樣本，每次迭代20次。同時，為了進一步驗證論文算法的效果，排除隨機噪聲干擾，作者進行了100次重復實驗，最終將每次迭代的實驗結果取平均值。

下圖2是USPS中將數字6與其他手寫數字進行分類的效果：

從上圖2可以看出，利用作者提出的基于稀疏子空間的拉普拉斯特征映射算法的準確率要高于傳統的主動學習算法，最終的誤分率比傳統算法的低了50%左右。該算法也優于SPLB算法。SPLB方法在支持向量機的輸出空間中尋找稀疏區域，而在主動學習的前期，支持向量機的分類精度比較低，所以數據在輸出空間的分布并不能完整反映整個數據集的分布情況。而作者的算法是根據流形假設，建立在圖論中的譜圖理論的基礎上的，其本質是將聚類問題轉化為圖的最優劃分問題，因此，比簡單的聚類效果更好。所以該算法有效的提高了主動學習的效率，同時改善了主動學習算法的魯棒性。

為了進一步證明論文算法的效果，表2中列出了在100次仿真實驗基礎上得到的最終誤分率的統計指標。其中：

MAX代表100次仿真結果中的最大誤差;

MIN代表100次仿真結果中的最小誤差;

MEAN代表100次仿真結果的均值;

STDEV代表100次仿真結果的標準差。

這四項指標中，最主要的參考指標是MEAN和STDEV，前者反映多次仿真實驗的平均精度，后者反映了與均值的偏離程度。MAX和MIN指標僅供參考，主要用于了解某算法的波動范圍。

四項指標中，每一項中最低的值均用黑色粗體表示。從表2中可以看出，除了最小誤差的指標MIN，論文算法在其他三個指標方面都由于其他算法，說明該算法具有很好的性能，能有效的降低樣本的標注成本。同時，該算法有最低的標準差說明算法的魯棒性很好，受初始狀態的影響很小。

3.2 其他數據集驗證

為了進一步驗證論文算法的有效性，除了上述數據集之外，我們還使用其他數據集進行了廣泛的驗證，每組仿真實驗均進行100次，最終的驗證結果在下表3中給出。這些數據集都轉化為二分類問題。在表中我們給出了每組實驗的超參數，每次迭代所選擇的樣本數和迭代次數。在表3中，每種算法都給出兩個指標，上面一個指標是多次實驗后的平均誤分率MEAN，下面一個指標是多次實驗的標準差STDEV。

從表3中我們可以看出，論文所提出的算法在總計18組實驗數據中取得了12次最好的分類成績，并且具有最低的標準差。足以體現本算法的優勢。

4 結 論

所提出算法比其他的主動學習算法體現出了更高的分類精度和更快的收斂速度。這是因為，傳統的主動學習算法在開始執行時并沒有考慮數據集的結構信息，只依靠樣本的標簽信息不斷的迭代，這種逐步挖掘信息的方法效率比較低，而且對初始值比較敏感。而論文的算法除了考慮到數據樣本的標簽數據之外，還充分考慮了無標簽樣本所包含的結構信息，并利用這些信息來指導主動學習的樣本選擇。從而使主動學習在初始階段的樣本選取就位于全局最優解附近，再逐步選擇對分類作用最大的支持向量進行迭代，因此分類的精度更高，而且效率高，節約了大量的樣本標注成本。同時，因為掌握了整體的結構，使得初始樣本的選擇更加合理，有效的降低了主動學習陷入局部最優的概率，增加了穩定性。同時，仿真實驗表明論文算法具有較低的標準差，說明算法的魯棒性較好，受初始值的影響小。

同時，該算法也有不足之處，該算法的時間復雜度為On3級別，說明論文算法的時間消耗比較大。因此，需要在進一步提升計算效率上進行研究。

參考文獻

[1] PATRA S， BRUZZONE L. A fast cluster-assumption based active-learning technique for classification of remote sensing images [J]. Geoscience and Remote Sensing， IEEE Transactions on， 2011， 49（5）： 1617-1626.

[2] PATRA S， BRUZZONE L. A cluster-assumption based batch mode active learning technique [J]. Pattern Recognition Letters， 2012， 33（9）： 1042-1048.

[3] ELHSMIFSR E， VIDAL R. Sparse subspace clustering： algorithm， theory and applications [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2013， 35（11）：2765-2781.

[4] GLOWINSKI R. ADMM and non-convex variational problems [M]. Splitting Methods in Communication， Imaging， Science， and Engineering， Springer International Publishing， 2016.

[5] CHANG Chih-chung， LIN Chih-jen. LIBSVM： a library for support vector machines[C]. ACM Transactions on Intelligent Systems and Technology， 2011， 2：1-27.