[發(fā)明專利]一種不完備數(shù)據(jù)集快速屬性約簡方法

在審

• 申請?zhí)枺?/td>: 201811574927.0
• 申請日: 2018-12-21
• 公開（公告）號(hào): CN109828996A
• 公開（公告）日: 2019-05-31
• 發(fā)明（設(shè)計(jì)）人: 閆濤;韓崇昭
• 申請（專利權(quán)）人: 西安交通大學(xué)
• 主分類號(hào): G06F16/2458
• 分類號(hào): G06F16/2458;G06K9/62
• 代理公司: 西安通大專利代理有限責(zé)任公司 61200
• 代理人: 徐文權(quán)

本發(fā)明公開了一種不完備數(shù)據(jù)集快速屬性約簡方法，本發(fā)明采用了IFSPA算法和IFSPA?IVPR算法，使本方法針對不完備數(shù)據(jù)集在保持其原有特征屬性分辨能力的情況下，能夠更高效的完成屬性約簡。本方法在時(shí)間復(fù)雜度、穩(wěn)定性等方面均優(yōu)于現(xiàn)有算法。同時(shí)使用該方法處理大規(guī)模數(shù)據(jù)集時(shí)的改進(jìn)效果也十分明顯。

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)挖掘技術(shù)領(lǐng)域，具體涉及一種不完備數(shù)據(jù)集快速屬性約簡方法。

背景技術(shù)

特征選擇，或者我們稱之為屬性約簡的數(shù)據(jù)處理方法是模式識(shí)別、數(shù)據(jù)挖掘以及機(jī)器學(xué)習(xí)等領(lǐng)域的一個(gè)共同的重要研究課題。近些年來，數(shù)據(jù)集中的元素的數(shù)量與維度都有了明顯的增長。例如，數(shù)量達(dá)到上百甚至上千的條件屬性存儲(chǔ)于許多現(xiàn)實(shí)應(yīng)用中的數(shù)據(jù)庫當(dāng)中。眾所周知，與識(shí)別或者分類任務(wù)無關(guān)的很多條件屬性會(huì)明顯降低相關(guān)算法的性能。換而言之，存儲(chǔ)和處理所有的條件屬性，包括相關(guān)的重要的以及不相關(guān)的不重要的屬性會(huì)帶來巨大的空間存儲(chǔ)成本與計(jì)算時(shí)間成本。為了解決這一問題，一些學(xué)者提出的方案是刪除那些不影響識(shí)別或者分類精度的條件屬性。因此，刪除部分條件屬性不僅是容許的，對于相關(guān)降低計(jì)算時(shí)間復(fù)雜度而言甚至是十分必要的。

在眾多的屬性約簡方法中，主要有兩種相關(guān)的策略，即包裝與過濾。前者使用一個(gè)學(xué)習(xí)算法對條件屬性子集進(jìn)行評價(jià)和選擇，后者則根據(jù)一些重要性度量，如信息增益、一致性、距離、依賴性等量測量對條件屬性進(jìn)行選擇。這些量測量可以分成兩個(gè)主要類別，即基于距離的度量與基于一致性的度量。粗糙集理論中的屬性約簡方法為基于一致性的屬性約簡方法提供了系統(tǒng)的理論框架，其目的并非是要將類的可分性最大化，而是試圖保證所選擇的條件屬性子集與原始的條件屬性全集具有相同的可分辨能力。

總的來說，我們通常會(huì)碰到兩類數(shù)據(jù)，即數(shù)值型數(shù)據(jù)和符號(hào)型數(shù)據(jù)。其中，對數(shù)值型數(shù)據(jù)而言，有兩種方法。一種是使用模糊粗糙集理論，另一種則是對數(shù)值型的條件屬性值進(jìn)行離散化處理。為了處理混合型的條件屬性值，相關(guān)學(xué)者也提出過很多方法。在經(jīng)典粗糙集理論中，屬性約簡算法將所有的屬性值作為符號(hào)型數(shù)據(jù)予以考慮。在對原始數(shù)據(jù)進(jìn)行過數(shù)據(jù)預(yù)處理過之后，我們可以使用經(jīng)典粗糙集理論選擇出條件屬性中最適合于識(shí)別或者分類任務(wù)的子集。

基于粗糙集理論的屬性約簡開始于一個(gè)數(shù)據(jù)表，我們也稱之為信息系統(tǒng)。它包含了關(guān)于我們感興趣的對象的所有數(shù)據(jù)，這些數(shù)據(jù)由一個(gè)有限的條件屬性集來描述。根據(jù)其是否存在缺失數(shù)據(jù)或者空數(shù)據(jù)，信息系統(tǒng)可以分為完備信息系統(tǒng)和不完備信息系統(tǒng)。一般來說，我們提到不完備信息系統(tǒng)，也就意味著該系統(tǒng)中間存在缺失數(shù)據(jù)或者空數(shù)據(jù)。對一個(gè)不完備信息系統(tǒng)而言，如果條件屬性與決策屬性彼此之間相互區(qū)分，則我們稱之為不完備決策系統(tǒng)或者不完備決策表。對不完備數(shù)據(jù)進(jìn)行屬性約簡通常開始于不完備決策表。

在近二十年里，關(guān)于粗糙集理論出現(xiàn)了很多新的屬性約簡方法。其中，具有代表性的就是Skowron提出的旨在獲取一個(gè)數(shù)據(jù)集的所有屬性約簡的可分辨矩陣方法。然而，該方法在處理大規(guī)模數(shù)據(jù)時(shí)會(huì)產(chǎn)生巨大的時(shí)間消耗。為了使屬性約簡變的更為高效，眾多學(xué)者根據(jù)粗糙集理論提出了各種不同的啟發(fā)式屬性約簡算法。這些算法各自都保留了給定信息系統(tǒng)的某種具體性質(zhì)。為了完成不完備決策表的屬性約簡任務(wù)，Kryszkiewicz將Skowron提出的可分辨矩陣方法擴(kuò)展為與其相似的廣義可分辨矩陣方法，以獲取不完備決策表的全部屬性約簡。Yang和Shu針對不完備決策表提出了一種應(yīng)用正區(qū)域?qū)傩约s簡思想的啟發(fā)式屬性約簡算法，該算法能夠保證目標(biāo)決策表的正區(qū)域在屬性約簡處理過后維持不變。Yan等人定義了一種新的信息熵以度量不完備信息系統(tǒng)的不確定性，并通過應(yīng)用對應(yīng)的條件信息熵減少冗余的條件屬性。正如通過引入Shannon的信息熵來尋找經(jīng)典粗糙集模型中的屬性約簡一樣，該方法通過引入條件信息熵的擴(kuò)展可以計(jì)算得出不完備決策表的相關(guān)屬性約簡。

但是，上述所有方法都不同程度存在處理速度慢，無法應(yīng)對處理大規(guī)模不完備數(shù)據(jù)時(shí)所產(chǎn)生的巨大時(shí)間消耗等問題。

發(fā)明內(nèi)容