應用定向搜索的後向粗糙集屬性約簡方法
2023-04-28 07:30:01
專利名稱：應用定向搜索的後向粗糙集屬性約簡方法
技術領域：
本發明涉及一種粗糙集屬性約簡方法，尤其涉及一種以互信息作約簡度量，採用了定向(Beam)搜索技術的後向粗糙集屬性約簡方法，為粗糙集知識獲取提供了良好途徑，屬於信息處理領域。
背景技術：
隨著信息技術的迅速發展以及資料庫管理系統的廣泛應用，人們積累的數據越來越多。激增的數據背後隱藏著許多重要的信息，人們希望能夠對其進行更高層次的分析，以便更好地利用這些數據。目前的資料庫系統可以高效地實現數據的錄入、查詢、統計等功能，但無法發現數據中存在的關係和規則，無法根據現有的數據預測未來的發展趨勢。缺乏挖掘數據背後隱藏的知識的手段，導致了「數據爆炸但知識貧乏」的現象。因此，研究能夠從大量信息中形成概括(歸納)的方法就顯得越來與重要，但是高級的智能數據分析技術還遠沒有成熟。
粗糙集理論是由Z.Pawlak提出的一種研究不確定、不完整知識和數據歸納、表達的理論方法，已被廣泛應用於數據挖掘，機器學習，人工智慧以及故障診斷等領域，成為近年的科學研究熱點。粗糙集理論通過屬性約簡和值約簡來得到分類規則，進而處理分類問題。屬性約簡是粗糙集理論分類規則獲取過程中的一個基本操作，它是指在保持初始屬性集的分類能力的前提下刪除不相關和冗餘的屬性。在屬性約簡的基礎上，再作進一步的值約簡，得到簡化的分類規則。
最小屬性約簡(也稱最優)是得到一個最小的屬性子集，使得它的分類能力與初始屬性集相同。粗糙集屬性約簡的目標就是最小屬性約簡，它已經被證明是非線性多項式困難(NP-hard)的。目前屬性約簡的方法可以歸結為兩大類(1)完全搜索方法，完全搜索方法是指評價每一種可能的屬性子集，來得到最小的屬性約簡結果。最直觀的完全搜索方法就是窮舉組合搜索，即評價每一種屬性組合。這種方法是最耗時間的一種辦法，如前向窮舉組合搜索方法。當搜索評價度量具有單調性性質時，可以採用分支界限方法來作完全搜索。採用互信息作為屬性約簡度量時，可以採用分支界限方法，如自動分支界限方法(ABB)和分支界限方法(BB)，它們都以初始屬性集的互信息作為屬性約簡的界。區別在於前者是寬度優先搜索方法，後者採用深度優先搜索方法。只有完全搜索方法可以保證實現最小屬性約簡，但是它的時間複雜度為指數形式，當屬性集過大時(通常是＞20)，完全搜索方法由於運行時間過長就變得不適用。
(2)啟發式搜索方法，啟發式搜索根據某個方向來確定搜索過程，最常見的是最好最先方法(Beet First)。通常的啟發式屬性約簡方法是逐個考察每個屬性看是否能被刪除，很顯然這種方法根據屬性被考察的先後順序而不同。再有就是基於互信息的Best First啟發式屬性約簡方法，它從核出發，以最大化互信息作為搜索方向進行屬性約簡。啟發式方法的缺點在於它是單方向的，即只有一個搜索前進的方向。運算時間相對於完全搜索方法被大大減少，但往往產生一個很差的屬性約簡結果。
發明內容
本發明的目的在於克服現有粗糙集屬性約簡方法的不足，提供一種新的粗糙集屬性約簡方法，實現高質量的屬性約簡和運算的快速性，滿足分類學習的實際需要。
為了實現這樣的目的，本發明利用屬性子集的互信息和冗餘協同係數(redundancy-synergy coefficient，RSC，RSC(A)=I(A;P)i=1aI(fi;P),A={fi|i=1,..,a}]]>)作為粗糙集屬性約簡的度量，從經過排序的初始屬性集F出發，從初始屬性集的孩子子集(所謂孩子是指刪除掉一個屬性得到的屬性子集)中選取M個冗餘協同係數最小的等價屬性子集(所謂等價屬性子集是指互信息相等)，存儲在定向存儲區；然後，再從這M個等價屬性子集出發，從它們的孩子子集中選取M個冗餘協同係數最小的等價屬性子集存儲到定向存儲區作進一步搜索；以此類推，直到沒有等價屬性子集能夠被找到為止，由此最後存儲在定向存儲區的屬性子集就是屬性約簡結果。
本發明方法的具體步驟如下1、初始化將初始屬性集F中的每個屬性按照互信息從小到大重新排列，並且將經過排序後的初始屬性集F存入定向存儲區(Beam)中。
2、定向搜索清空暫態存儲區(Queue)；對於定向存儲區中的每個屬性子集，根據冗餘協同係數特性可以通過依次從前往後刪除屬性來找到它的M個冗餘協同係數最小的孩子等價屬性子集，也就是前M個孩子等價屬性子集，存入暫態存儲區，其中，冗餘協同係數RSC(A)=I(A;P)i=1aI(fi;P),A={fi|i=1,..,a},]]>A表示屬性子集，fi表示屬性，I(A；P)表示A與分類屬性P的互信息，I(fi；P)表示fi與分類屬性P的互信息；如果某個屬性子集的孩子等價屬性子集個數小於M個，則取這個屬性子集的全部孩子等價屬性子集存入暫態存儲區。
3、定向搜索停止條件判別如果暫態存儲區包含屬性子集，則清空定向存儲區；從暫態存儲區中找出冗餘協同係數最小的M個屬性子集，存入定向存儲區，如果暫態存儲區中的屬性子集小於M個，則取暫態存儲區中的全部屬性子集存入定向存儲區，然後繼續進行第(2)步的定向搜索。如果暫態存儲區不包含屬性子集，則輸出定向存儲區中的所有屬性子集，由此得到屬性約簡結果。
本發明的方法可以通過靈活調節M值來保證運算的快速性和屬性約簡結果的質量。M取值可以根據初始屬性集的大小設定一個初始值，並可隨運算時間長短進行調整，運算時間過長，則減少M取值，反之，增大M取值，直到取得滿意的屬性約簡結果。初始屬性集越大，M取初始值越小；如果運算時間過長，則可減小M取值，反之，可增大M取值。由於可以擴大搜索範圍，因而可以得到更多更優的屬性約簡結果，但同時保證運算的快速性。本發明是一個啟發式屬性約簡方法，與一般的最優最先方法不同的是，它可以看作是最優最先方法的擴展，或者，最優最先方法是它的一個特例。
本發明利用屬性子集的互信息和屬性之間的信息冗餘性度量——冗餘協同係數作為屬性約簡度量，作一個後向搜索的屬性約簡。方法實現靈活簡單，針對性強，通用性強，具有多項式時間複雜度，可應用於所有粗糙集屬性約簡領域。
圖1為本發明方法中的定向搜索示意圖。
具體實施例方式
為了更好的理解本發明的技術方案，以下結合附圖和實施例作進一步描述。
(1)初始化將初始屬性集F中的每個屬性按照互信息I(fi；P)從小到大重新排列，並且將經過排序後的初始屬性集F存入定向存儲區(Beam)中。互信息從小到大排列就是為了方便找到定向存儲區中屬性子集的前M個冗餘協同係數最小的孩子等價屬性子集，這樣可以壓縮定向搜索空間，減少搜索時間。
注意冗餘協同係數從信息量商的角度來描述屬性子集的冗餘程度和組合協同能力。A(A＝{fi|fi∈A，i＝1，...，a})F，RSC(A)稱為屬性子集A的冗餘協同係數，其計算如式(1)，RSC(A)=I(A;P)i=1aI(fi;P)--(1)]]>冗餘協同係數是一個相對信息度量的概念。冗餘協同係數的取值範圍為(0，∞)。冗餘協同係數越小，屬性的組合能力越弱，說明屬性之間包含類信息的冗餘越大，越多的屬性能被刪除而保持互信息不減少。它具有以下兩個性質(1) 如果I(A；P)＝I(B；P)，且AB，則RSC(A)≥RSC(B)。
(2)對於屬性子集AF，A＝{f1，f2，…，fa}，如果I(f1；P)＜I(f2；P)＜…＜I(fa；P)，且I(A-(fi|i＝1，2，…，a}；P)＝I(A；P)，則RSC(A-{f1})＜RSC(A-{f2})＜…＜RSC(A-{fa})＜RSC(A)。
在本發明中首先將初始屬性集F中的屬性按照互信息從小到大排列。根據冗餘協同係數性質(2)，運用這個排列只需要通過從前往後依次刪除一個屬性來找到每個父屬性子集的前M個孩子等價屬性子集，而不需考慮這個父屬性子集所有的孩子屬性子集。因為對於定向存儲區Beam中的每個節點(即屬性子集)，前M個孩子等價屬性子集的冗餘協同係數最小，這大大節省了運算時間。所以初始化過程中將初始屬性集F中的屬性按照互信息從小到大排列。
(2)定向搜索最優最先搜索通常是一個評價度量最優節點作為下一步搜索的起點，而定向搜索則選取M個評價度量好的節點作為下一步搜索的起點。定向搜索可以是一個「樹有限寬度搜索」方法，其樹搜索寬度設為M，稱為定向寬度。定向搜索過程如圖1所示，圖中黑色節點表示用於作進一步搜索的節點，白色節點為搜索過程中被捨棄掉的節點，定向寬度M為2。每一層中有兩個最好的滿足優化條件的樹節點作為下一步搜索的出發點，來做進一步搜索，直到滿足搜索停止條件，最後結果為節點1和2。如果只能夠找到K(K＜M)個冗餘協同係數最小的等價屬性子集，則取這K個屬性子集作進一步搜索。
冗餘協同係數是屬性集的一個屬性協同表達類屬性的冗餘性和協同能力的度量，冗餘協同係數越小，冗餘度越大，越可能有多的冗餘屬性能被刪除，也即更可能找到一個更小的F的等價屬性子集，因此，可以將冗餘協同係數作為屬性子集選擇度量，結合定向搜索方法，進行後向刪除屬性約簡。
(3)定向搜索停止條件判別當暫態存儲區中為空，說明沒有找到等價屬性子集時，因此上一次找到的存儲在定向存儲區中的等價屬性子集被認為是找到的最小的等價屬性子集，因此定向搜索停止，得到屬性約簡結果。如果有，說明可以作進一步的定向搜索，從暫態存儲區中找出冗餘協同係數最小的M個屬性子集，存入定向存儲區，如果暫態存儲區中的屬性子集小於M個，則取暫態存儲區中的全部屬性子集存入定向存儲區，繼續第(2)步的搜索。
本發明屬性約簡方法的運行時間與兩個因素有關係(1)屬性子集互信息的計算；(2)搜索空間，即被評價的屬性子集的個數。一個屬性子集評價的時間取決於屬性子集對樣本集(樣本集包含p個屬性，m個樣本)的劃分，採用散列法來進行劃分，屬性子集評價的時間複雜度為O(m)。設r為約簡結果子集大小，本發明方法被評價的屬性子集個數不大於0.5*M*(p-r)*(p-1+r)+p+1，所以，本發明的時間複雜度為O(mMp2)。實際上，因為通過屬性排序和孩子屬性子集產生框架減少了多餘的屬性子集評價，因此本發明的搜索空間遠小於0.5*M*(p-r)*(p-1+r)+p+1。當M＝1時，本發明的時間複雜度為O(mp)。
實驗選取5個UCI標準數據集Corral、Monk1、Parity5+2、Vote、Mushroom。首先選用ABB方法作屬性約簡，結果和運算時間如表1所示。對於Mushroom數據集，運算時間超過2小時，認為ABB方法是不適合的，用「-」表示。本發明方法的屬性約簡結果分別如表2所示，M分別取1、p和2p。從表中可以看出它們幾乎能夠得到最有屬性約簡子集，但時間相對ABB方法卻大大下降。對於Mushroom數據集，本發明方法也得到了良好的屬性約簡結果，而ABB方法由於是一個完全搜索方法卻不能夠。
表1數據集信息與ABB方法屬性約簡結果數據集 樣本數初始屬性集大小 uABBAS t(ms)Corral 128 6 2 3{f1-f4}Monkl 432 6 2{f1，f2，f5} 19Parity5+2 1024102 650{f1-f5}(1){f1，f3-f5，f7}(2){f2-f6}(3){f3-f7}(4)Vote435 162{f1-f4，f9，f11，f13，f15，f16}2697Mushroom8124222 - -u為類別數，AS為屬性約簡子集，t為運算時間。
表2本發明方法屬性約簡結果數據集本發明(M＝2p) 本發明(M＝p) 本發明(M＝1)AS t(ms) AS t(ms) AS t(ms)Corral{f1-f4}2 {f1-f4} 2 {f1-f4} 2Monkl {f1，f2，f5} 13{f1，f2，f5}13 {f1，f2，f5} 4Parity5+2 {f3-f7}(1)403{f3-f7}(1)397 {f2-f5} 49{f1，f3-f5，f7}(2){f1，f3-f5，f7}(2){f2-f6}(3){f2-f6}(3){f1-f5)(4)Vote {f1-f4，f9，f11， 985 {f1-f4，f9，f11， 765 {f1-f4，f9，f11，42{f13，f15，f16} f13，f15，f16}f13，f15，f16}Mushroom {f5，f20，f21，f22}(1)65921915 369640 {f5，f8，f12，f19，f20} 2389{f4，f5，f12，f22}(2)
權利要求
1.一種應用定向搜索的後向粗糙集屬性約簡方法，其特徵在於包括如下步驟1)初始化將初始屬性集中的每個屬性按照互信息從小到大重新排列，並且將經過排序後的初始屬性集存入定向存儲區中；2)定向搜索清空暫態存儲區；對於定向存儲區中的每個屬性子集，根據冗餘協同係數特性可以通過依次從前往後刪除屬性來找到它的M個冗餘協同係數最小的孩子等價屬性子集，也就是前M個孩子等價屬性子集，存入暫態存儲區，其中，冗餘協同係數RSC(A)=I(A;P)i=1aI(fi;P),]]>A＝{fi|i＝1，...，a}，A表示屬性子集，fi表示屬性，I(A；P)表示A與分類屬性P的互信息，I(fi；P)表示fi與分類屬性P的互信息；如果某個屬性子集中的孩子等價屬性子集個數小於M個，則取這個屬性子集的全部孩子等價屬性子集存入暫態存儲區；其中M初始值根據初始屬性集的大小設定並可隨運算時間長短進行調整，初始屬性集越大，M初始值就取得越小，運算時間過長，則減少M取值，反之，增大M取值，直到取得滿意的屬性約簡結果；3)定向搜索停止條件判別如果暫態存儲區包含屬性子集，則清空定向存儲區，從暫態存儲區中找出冗餘協同係數最小的M個屬性子集，存入定向存儲區，如果暫態存儲區中的屬性子集小於M個，則取暫態存儲區中的全部屬性子集存入定向存儲區，然後繼續進行第(2)步的定向搜索；如果暫態存儲區不包含屬性子集，則輸出定向存儲區中的所有屬性子集，由此得到屬性約簡結果。
全文摘要
一種應用定向搜索的後向粗糙集屬性約簡方法，利用屬性子集的互信息和冗餘協同係數作為粗糙集屬性約簡的度量，從經過排序的初始屬性集出發，從初始屬性集的孩子子集中選取若干個冗餘協同係數最小的等價屬性子集，存儲在定向存儲區；然後再從這些等價屬性子集出發，從它們的孩子子集中選取若干個冗餘協同係數最小的等價屬性子集作進一步搜索，以此類推，直到不能夠找到等價屬性子集為止，最後存儲在定向存儲區的屬性子集就是屬性約簡結果。本發明方法實現靈活簡單，針對性強，通用性強，具有多項式時間複雜度，可應用於所有粗糙集屬性約簡領域。
文檔編號G06F17/30GK1588363SQ20041006715
公開日2005年3月2日 申請日期2004年10月14日 優先權日2004年10月14日
發明者楊勝, 施鵬飛 申請人:上海交通大學