沈 杰 許高建 楊 陽 李紹穩(wěn)

(安徽農(nóng)業(yè)大學(xué)信息與計(jì)算機(jī)學(xué)院， 合肥 230036)

不確定性數(shù)據(jù)的分類方法研究綜述

沈 杰 許高建 楊 陽 李紹穩(wěn)

(安徽農(nóng)業(yè)大學(xué)信息與計(jì)算機(jī)學(xué)院， 合肥 230036)

傳統(tǒng)的數(shù)據(jù)挖掘分類方法能夠成功地應(yīng)用于確定性數(shù)據(jù)分類，但卻無法滿足絕大多數(shù)領(lǐng)域中復(fù)雜的不確定性數(shù)據(jù)的分類需求，由此出現(xiàn)了一系列針對(duì)不確定性數(shù)據(jù)的分類方法。通過大量研究，目前經(jīng)典的分類算法及針對(duì)不確定數(shù)據(jù)分類的改進(jìn)方法得到了很大發(fā)展，如改進(jìn)后的支持向量機(jī)算法、樸素貝葉斯算法、決策樹算法等日漸成熟。

不確定性數(shù)據(jù)； 分類； 支持向量機(jī)； 樸素貝葉斯； 決策樹

面臨海量的、復(fù)雜的不確定性數(shù)據(jù)，針對(duì)不確定性數(shù)據(jù)的數(shù)據(jù)挖掘成為智能分析數(shù)據(jù)并獲取知識(shí)的重要手段，分類算法成為其主要的研究方向之一。2006年，第六屆IEEE數(shù)據(jù)挖掘國(guó)際會(huì)議(ICDM)評(píng)選了最具影響的10個(gè)數(shù)據(jù)挖掘算法，其中分類算法占據(jù)了6個(gè)：k-NN、Naive Bayes、C4.5、CART、SVM、AdaBoost[1]。分類的任務(wù)就是通過分析來建立區(qū)分對(duì)象的分類模型，即分類器。傳統(tǒng)的分類算法通常將精確數(shù)據(jù)作為研究背景，只考慮了精準(zhǔn)數(shù)據(jù)的輸入和分類，因而不能直接應(yīng)用于不確定性數(shù)據(jù)分類，如支持向量機(jī)(SVM)、決策樹、樸素貝葉斯算法等。針對(duì)此現(xiàn)象，基于這些算法的原有經(jīng)典模式加以改進(jìn)，加入不確定性數(shù)據(jù)分析，可使得不確定知識(shí)數(shù)據(jù)挖掘技術(shù)更加成熟。

1 不確定性數(shù)據(jù)

1.1 不確定性數(shù)據(jù)的產(chǎn)生

數(shù)據(jù)的不確定性源于數(shù)據(jù)本身。數(shù)據(jù)不確定性分以下幾種情況：采集數(shù)據(jù)時(shí)出現(xiàn)缺省值、干擾值等；在實(shí)驗(yàn)時(shí)受周圍環(huán)境的影響而導(dǎo)致數(shù)據(jù)不確定；在數(shù)據(jù)傳輸過程中的失真導(dǎo)致不確定性。

1.2 不確定性數(shù)據(jù)的表示

不確定性一般可分為存在(元組級(jí))不確定性和值(屬性級(jí))不確定性[2]。其中，存在(元組級(jí))不確定性是指一個(gè)對(duì)象即有出現(xiàn)的可能性，也有不出現(xiàn)的可能，如某天可能會(huì)下雨或者可能不會(huì)下雨；而值(屬性級(jí))不確定性是指這個(gè)對(duì)象取值的不確定性。在高維空間中，確定性數(shù)據(jù)對(duì)象表現(xiàn)為某些具體的點(diǎn)，而不確定數(shù)據(jù)對(duì)象的表現(xiàn)形式為滿足某種分布的一個(gè)范圍。

2 常見的不確定性數(shù)據(jù)分類方法

2.1 支持向量機(jī)算法

Vapnik等人提出的傳統(tǒng)支持向量機(jī)是一種基于統(tǒng)計(jì)學(xué)理論、以結(jié)構(gòu)風(fēng)險(xiǎn)最小化為原則的判別式分類器[3-5]。其基本思想是，在n維數(shù)據(jù)空間中尋找一個(gè)超平面，可以極大化地將空間屬于不同類別的樣本點(diǎn)分開，對(duì)于精確的小樣本數(shù)據(jù)有很好的分類效果。孫喜晨等人對(duì)不確定數(shù)據(jù)作了預(yù)處理，在屬性均值聚類(AMC)與支持向量機(jī)(SVM)的基礎(chǔ)上，提出基于(屬性)聚類的屬性支持向量機(jī)(AMC-ASVM)算法[6]。該算法對(duì)樣本進(jìn)行屬性均值聚類，然后將各個(gè)聚類中心及其屬性作為新的樣本點(diǎn)來訓(xùn)練，進(jìn)而得到分類器[7]。但該方法本質(zhì)上是將數(shù)據(jù)的不確定性轉(zhuǎn)化為確定性來處理，對(duì)不確定性考慮得不夠充分。

Jianqiang Yang等人在SVM中引入多維高斯分布模型來描述不確定數(shù)據(jù)的，提出USVC、 AUSVC及MPSVC支持向量機(jī)分類算法[8]。USVC的原始問題通過引入約束得到，將機(jī)會(huì)約束的規(guī)劃問題轉(zhuǎn)化為二次規(guī)劃問題來求解。而AUSVC以及MPSVC是由USVC算法改進(jìn)而來，即通過調(diào)整USVC中的機(jī)會(huì)約束的置信參數(shù)來減小不確定性對(duì)構(gòu)造分類器的負(fù)面影響。但該算法由于二次規(guī)劃問題而導(dǎo)致計(jì)算過程復(fù)雜、難以理解。

相對(duì)于區(qū)間的不確定，李文進(jìn)等人提出了區(qū)間不確定性超球支持向量機(jī)(IUHSVM)[9]。該方法的基本思想是：將不確定數(shù)據(jù)表示為球體凸集區(qū)域，形成區(qū)間，找到一個(gè)超平面使得各類球體區(qū)域之間的間隔盡可能大，使其能正確劃分。建立超球支持向量機(jī)模型，將該模型轉(zhuǎn)化為2層嵌套約束規(guī)劃問題，使得其在尋找最優(yōu)超平面的計(jì)算過程中，降低計(jì)算難度。大量的實(shí)驗(yàn)結(jié)果表明，IUHSVM算法相比其他算法有較強(qiáng)的多分類處理能力，其球體凸集模型能較好地描述不確定性。

2.2 貝葉斯分類算法

貝葉斯分類算法是基于貝葉斯定理的一種算法統(tǒng)稱。在統(tǒng)計(jì)資料的基礎(chǔ)上，依據(jù)某些特征，計(jì)算各個(gè)類別的概率，以后驗(yàn)條件概率來判斷是否屬于該類，從而實(shí)現(xiàn)分類。樸素貝葉斯(Naive Bayes)法是是基于貝葉斯定理和特征條件獨(dú)立假設(shè)的分類方法。對(duì)于給定的訓(xùn)練數(shù)據(jù)集，首先基于特征條件獨(dú)立假設(shè)學(xué)習(xí)輸入輸出的聯(lián)合分布概率；然后基于此模型，對(duì)給定的輸入x，再利用貝葉斯定理求出其后驗(yàn)概率最大的輸出y[10]。

對(duì)不確定性數(shù)據(jù)進(jìn)行貝葉斯分類時(shí)，會(huì)使用概率分布函數(shù)來表示該不確定區(qū)域[11]。當(dāng)數(shù)值型數(shù)據(jù)屬性是不確定的時(shí)候，稱之為不確定性數(shù)值屬性(UNA)[12]。有3種擴(kuò)展的貝葉斯方法可以解決不確定性數(shù)據(jù)分類，分別是均值的方法、基于分布的方法及基于公式的方法[13]。

均值的方法是最為簡(jiǎn)單直接的一種方法。用平均值(期望)代替概率密度函數(shù)，從而使其變?yōu)辄c(diǎn)值，實(shí)際上也是將不確定性數(shù)據(jù)轉(zhuǎn)化為確定性數(shù)據(jù)，再使用原本的貝葉斯模型和核密度函數(shù)實(shí)現(xiàn)分類。這個(gè)方法最大的優(yōu)勢(shì)就是簡(jiǎn)單明了，不需要使用新的不確定性數(shù)據(jù)分類算法。但其缺點(diǎn)也很明顯：用平均值代替區(qū)間同樣對(duì)不確定性考慮得不夠充分；基于分布的方法重點(diǎn)在于對(duì)不確定性數(shù)據(jù)的類條件分布進(jìn)行估計(jì)，用概率密度函數(shù)來表示不確定數(shù)據(jù)，再將原本的核密度估計(jì)函數(shù)進(jìn)行擴(kuò)展，來進(jìn)行不確定性數(shù)據(jù)的分類。相對(duì)而言，基于分布的方法對(duì)不確定性數(shù)據(jù)的處理更完善；而基于公式的方法是通過這些不確定性數(shù)據(jù)來確定新的核密度估計(jì)公式，再利用這個(gè)核密度估計(jì)公式完成分類。該方法的關(guān)鍵在于正確地生成核密度估計(jì)函數(shù)的公式，但該方式僅僅適用于一些密度函數(shù)和概率分布函數(shù)的聯(lián)合。

2.3 決策樹算法

決策樹，是一種用某種策略篩選條件而建立起來的樹，利用遞歸的方式和分治的思想，自頂向下的分類方法。決策樹學(xué)習(xí)的目的是為了產(chǎn)生一顆范化能力強(qiáng)，即處理未見示例能力強(qiáng)的決策樹，其基本流程遵循簡(jiǎn)單且直觀的分而治之策略。

針對(duì)不確定性數(shù)據(jù)，目前有Dempste和Shafe提出的“證據(jù)理論”和經(jīng)典決策樹結(jié)合的D-S決策樹算法[14]。D-S決策樹在不確定環(huán)境中(即目標(biāo)所在的類和屬性的值是不確定的)，通過證據(jù)理論決策樹分類模型中的置信度和似然函數(shù)來表達(dá)這個(gè)不確定的值[15-16]。在該算法中利用不確定測(cè)量函數(shù)(稱為D-S熵)來選擇劃分屬性，用經(jīng)典決策樹方法生成決策樹。首先計(jì)算全集D的不確定測(cè)量，假設(shè)用E(D)表示；然后求不確定區(qū)間的中心，即全集的信任函數(shù)與全集的最大似然函數(shù)和的二分之一，假設(shè)用N(D)表示，最后求出的總不確定度測(cè)量函數(shù)是兩者之和，H(D)=E(D)+N(D)。若要選擇屬性A作為劃分屬性，且有V個(gè)可能取值，則要計(jì)算A屬性的D-S熵，最終求出平均互信息量[14]。具有最大互信息量的屬性將作為劃分屬性。在該算法中，主要運(yùn)用了置信度和最大似然函數(shù)來表達(dá)不確定性，建樹的過程參考經(jīng)典決策樹。

DTU[17]也是一種利用決策樹處理不確定性數(shù)據(jù)的算法，主要是通過擴(kuò)展傳統(tǒng)的信息熵和信息增益來建立不確定性的決策樹分類模型，當(dāng)元組的概率密度函數(shù)(probability density function，PDF)所在的域跨越分裂點(diǎn)時(shí)，PDF通過分?jǐn)?shù)元組技術(shù)將元組分裂到子集中[18-19]。

3 不確定性數(shù)據(jù)的組合分類算法

上述幾種分類算法最終形成的分類器也只是單一的分類器，每一種分類器都有各自適用的場(chǎng)合。在實(shí)際應(yīng)用中，單一的分類器很難使其具有穩(wěn)定性。組合分類器可通過參考多個(gè)分類信息來提高分類精度，優(yōu)化單一分類器的穩(wěn)定性。

3.1 基于期望值的AUG算法

AUG(Average)算法處理不確定性問題的一般思路是，將不確定性輸入轉(zhuǎn)化為確定性的輸入。在高維空間中，不確定性表現(xiàn)為集中的一團(tuán)數(shù)據(jù)。在這一團(tuán)數(shù)據(jù)中有一個(gè)期望值，那么取這個(gè)期望值作為新的樣本，如此問題可轉(zhuǎn)化為確定性分類，繼而直接使用傳統(tǒng)的分類算法即可。但該算法的嚴(yán)重缺點(diǎn)在于，損失了大量的不確定信息，使得其分類結(jié)果不夠準(zhǔn)確。

3.2 基于采樣的USM算法

在上述AUG算法中，只取了一團(tuán)數(shù)據(jù)樣本中的期望值作為一個(gè)確定的樣本點(diǎn)，其結(jié)果導(dǎo)致分類不準(zhǔn)確。為此，USM(Uniform Sampling Method)算法在取樣的時(shí)候并不再只取期望值一個(gè)樣本，而是在期望值的附近采樣，這樣一些樣本也都接近期望值?？梢钥闯?，這樣的算法效率依賴于取樣規(guī)模的大小，規(guī)模過大，消耗大，效率低，且規(guī)模過小也會(huì)出現(xiàn)分類結(jié)果不準(zhǔn)確。

3.3 基于采樣的EUS算法

對(duì)于上述USM算法，規(guī)模大小影響分類結(jié)果，可以采用一種組合分類器策略：即對(duì)不確定性數(shù)據(jù)進(jìn)行規(guī)模大小一致的采樣，但采樣的點(diǎn)各不相同。在若干次采樣之后得到n個(gè)采樣結(jié)果，對(duì)每一個(gè)采樣結(jié)果構(gòu)建分類器，使得出現(xiàn)了n個(gè)分類器，將這n個(gè)分類器組合起來形成EUS(Ensemble Uniform Sampling)算法。該算法從原來的單一分類器變成多分類器的組合，分類精度提高了，但與此同時(shí)也增加了更多的消耗，效率問題仍有待解決。

3.4 基于權(quán)重采樣的EWS算法

在上述EUS算法中，每個(gè)子分類器采樣的規(guī)模是相同的。但在現(xiàn)實(shí)情況下，很多數(shù)據(jù)都會(huì)存在重要性的問題，也就是權(quán)重大小的問題。進(jìn)行數(shù)據(jù)采樣時(shí)，應(yīng)多采集權(quán)重大的數(shù)據(jù)，運(yùn)用EWS(Ensemble Weight Sampling)算法。這就需要考慮，如何定義權(quán)重的大小。Schapire于1996年提出了AdaBoost算法，旨在通過尋找僅僅比隨機(jī)猜測(cè)略好一些的弱學(xué)習(xí)算法，就可以將其提升為強(qiáng)學(xué)習(xí)算法[20]。該算法的核心思想是，每分類一次得到一個(gè)分類器，每次都會(huì)出現(xiàn)一些錯(cuò)分的情況。將錯(cuò)分的點(diǎn)權(quán)值變大，迭代上述步驟，將這些分類器組合起來，會(huì)有很好的分類效果。

4 不確定性數(shù)據(jù)分類算法在各領(lǐng)域的研究

上述分類算法在各領(lǐng)域經(jīng)過了實(shí)驗(yàn)驗(yàn)證與應(yīng)用。嚴(yán)信等人針對(duì)遙感影像數(shù)據(jù)的具有邊界模糊和解譯過程不確定性的特點(diǎn)，將遙感影像數(shù)據(jù)作為實(shí)驗(yàn)對(duì)象，通過將云模型和模糊支持向量機(jī)結(jié)合來提高分類精度[21]。王超等人提出了3類不確定性支持向量機(jī)算法的數(shù)值驗(yàn)證以及用于人臉識(shí)別的應(yīng)用[22]。李芳等人利用美國(guó)加州大學(xué)Irvine分校用于分類算法開發(fā)和測(cè)試的標(biāo)準(zhǔn)數(shù)據(jù)集bollon仿真和分析D-S證據(jù)理論決策樹，仿真結(jié)果表明，D-S證據(jù)理論決策樹能有效地對(duì)不確定性數(shù)據(jù)進(jìn)行分類，有較好的分類精度[14]。趙大雷等人利用不確定性貝葉斯分類模型有效刻畫了降雨量這一屬性級(jí)不確定性，并利用黃土滑坡不確定性特征集數(shù)據(jù)設(shè)計(jì)了不確定性貝葉斯分類模型和樸素貝葉斯分類模型的對(duì)比試驗(yàn)[23]。實(shí)驗(yàn)結(jié)果表明，不確定性貝葉斯分類器更具分類精度。黃凱等人利用不確定性貝葉斯模型解決水質(zhì)評(píng)價(jià)中檢測(cè)數(shù)據(jù)、水質(zhì)級(jí)別、水質(zhì)標(biāo)準(zhǔn)所蘊(yùn)含的不確定性數(shù)據(jù)[24]。

5 結(jié) 語

傳統(tǒng)的分類方法針對(duì)確定性數(shù)據(jù)有很好的分類效果，很多基于傳統(tǒng)分類算法上的改進(jìn)，使得這些算法越來越成熟。然而這些算法仍然不能將不確定性數(shù)據(jù)正確分類，于是將不確定性數(shù)據(jù)考慮到這些分類算法中，成為數(shù)據(jù)挖掘的研究熱點(diǎn)。在支持向量機(jī)中，使用超球凸集數(shù)學(xué)模型來表示不確定性；在樸素貝葉斯理論中使用概率分布函數(shù)來表示不確定性；在決策樹算法中使用分類模型中的置信度和似然函數(shù)來表達(dá)不確定性數(shù)據(jù)。

[1] WU X，KUMAR V，QUINLAN J R，et al.Top 10 algorithms in data mining[J].Knowledge & Information Systems，2007，14(1):1-37.

[2] 陳紅梅.不確定性數(shù)據(jù)的分類研究[D].昆明：云南大學(xué)，2012:10-20.

[3] 丁世飛，齊丙娟，譚紅艷.支持向量機(jī)理論與算法研究綜述[J].電子科技大學(xué)學(xué)報(bào)，2011，40(1):2-10.

[4] 褚洪波.支持向量機(jī)理論與算法研究[J].和田師范專科學(xué)校學(xué)報(bào):漢文綜合版，2012(5):104-106.

[5] 范昕煒.支持向量機(jī)算法的研究及其應(yīng)用[D].杭州：浙江大學(xué)，2003：1-20.

[6] 孫喜晨，賀仁亞，封舉富.一種新的分類方法：屬性均值聚類屬性支持向量機(jī)(AMC-ASVM)[J].北京大學(xué)學(xué)報(bào)(自然科學(xué)版)，2007，43(1):82-84.

[7] 高華.基于聚類分塊支持向量機(jī)的入侵檢測(cè)算法[D].南京：南京理工大學(xué)，2007：1-20.

[8] YANG J，GUNN S.Iterative Constraints in Support Vector Classification with Uncertain Information [G].Constraint-Based Mining and Learning，2007：49.

[9] 李文進(jìn)，熊小峰，毛伊敏.不確定性數(shù)據(jù)的超球支持向量機(jī)分類方法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2015(7):1778-1783.

[10] 陳旋，劉健，馮新淇,等.基于樸素貝葉斯的差分隱私合成數(shù)據(jù)集發(fā)布算法[J].計(jì)算機(jī)科學(xué)，2015，42(1):236-238.

[11] REN J，LEE S D，CHEN X，et al.Naive Bayes Classification of Uncertain Data[C]// Ninth IEEE International Conference on Data Mining.IEEE Computer Society.2009:944-949.

[12] CHENG R，KALASHNIKOV D V，PRABHAKAR S J，et al.A fast decision tree learning algorithm[C]// National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference.2006.

[13] 馬愷.不確定數(shù)據(jù)的樸素貝葉斯分類[J].洛陽師范學(xué)院學(xué)報(bào)，2016(2):20-21.

[14] 李芳，李一媛，王沖.不確定數(shù)據(jù)的決策樹分類算法[J].計(jì)算機(jī)應(yīng)用，2009，29(11):3092-3095.

[15] 徐洪文.關(guān)于“置信度”選取問題的討論[J].大學(xué)化學(xué)，1998，13(5):46-47.

[16] 王家驥.求最大似然函數(shù)參數(shù)估值的一種對(duì)分法[J].中國(guó)科學(xué)院上海天文臺(tái)年刊，1997(18):45-48.

[17] QIN B，XIA Y，LI F.DTU：A Decision Tree for Uncertain Data[C]// Advances in Knowledge Discovery and Data Mining，Pacific-Asia Conference，PAKDD 2009，Bangkok，Thailand.2009:4-15.

[18] TSANG S，KAO B，YIP K Y，et al.Decision Trees for Uncertain Data[C]// International Conference on Data Engineering，ICDE 2009 .2009:441-444.

[19] 張潮，李晨，王勇,等.uPOSC4.5:一種針對(duì)不確定數(shù)據(jù)的PU學(xué)習(xí)決策樹算法[J].計(jì)算機(jī)研究與發(fā)展，2010，47(增刊1):316-324.

[20] 曹瑩，苗啟廣，劉家辰,等.AdaBoost算法研究進(jìn)展與展望[J].自動(dòng)化學(xué)報(bào)，2013，39(6):745-758.

[21] 嚴(yán)信.基于云模型的模糊支持向量機(jī)分類方法研究[D].太原：太原理工大學(xué)，2013：10-20.

[22] 王超.三類不確定支持向量機(jī)及其應(yīng)用[D].石家莊：河北大學(xué)，2013：1-20.

[23] 劉大雷.基于不確定貝葉斯算法在滑坡危險(xiǎn)性預(yù)測(cè)的應(yīng)用研究[D].南昌：江西理工大學(xué)，2015：1-20.

[24] 黃凱，張曉玲.貝葉斯方法在水環(huán)境系統(tǒng)不確定性分析中的應(yīng)用述評(píng)[J].水電能源科學(xué)，2012(9):47-49.

Research on Classification Methods of Uncertain Data

SHENJieXUGaojianYANGYangLIShaowen

(School of Information and Computer, Anhui Agriculture University, Hefei 230039, China)

Traditional classification method has a successful application in various fields for the classification of determined knowledge; however, it cannot satisfy the demand for classification of complex uncertain knowledge. Hence, a series of classification methods for uncertain knowledge have emerged. Based on extensive research in this paper, it is proved that at present, classic classification algorithms and improved methods for classifying uncertain data have been greatly developed, such as the improved classification methods about Support Vector Machines, Naive Bayes and Decision Tree.

uncertain data; classification; support vector machines; Naive Bayes; Decision Tree

2017-03-23

國(guó)家自然科學(xué)基金項(xiàng)目“農(nóng)業(yè)領(lǐng)域(茶學(xué))云本體建模與方法研究”(31271615)

沈杰(1990 — )，女，合肥人，在讀碩士研究生，研究方向?yàn)槿斯ぶ悄芎蛿?shù)據(jù)挖掘。

TP301

A

1673-1980(2017)04-0096-04