第1章 緒論 

1.1   課題研究的目的和意義 
近年來，隨著全球信息科技的飛速發(fā)展，尤其是數(shù)據(jù)挖掘技術(shù)和信息采集技術(shù)的不斷發(fā)展，利用這些技術(shù)可以快速收集大量的數(shù)據(jù)信息，并可以通過對數(shù)據(jù)的處理和分析獲得對人們有價值的信息和知識。對于采集的數(shù)據(jù)，往往存在大量缺失的屬性值，這就造成了數(shù)據(jù)的稀疏性[1]。盡管收集的數(shù)據(jù)量很大，但往往人們只關(guān)注其中一小部分數(shù)據(jù)，這又會導致數(shù)據(jù)失衡性[2]。而現(xiàn)實應用中兼具稀疏性和失衡性的數(shù)據(jù)普遍存在，也因此影響數(shù)據(jù)挖掘任務的準確性。因此面向失衡數(shù)據(jù)的稀疏性相關(guān)問題的研究具有重要的理論價值和現(xiàn)實意義。 對于類別分布均勻、結(jié)構(gòu)完整的數(shù)據(jù)分類問題，基于這些數(shù)據(jù)的分類器都具有良好的性能，而現(xiàn)實中絕大多數(shù)情況下會因數(shù)據(jù)集的復雜性而遇到分類難題，例如，海量數(shù)據(jù)、稀疏數(shù)據(jù)、失衡數(shù)據(jù)、高維數(shù)據(jù)、不完全數(shù)據(jù)，甚至兼具幾種特征的復雜數(shù)據(jù)，尤其失衡數(shù)據(jù)當遇到數(shù)據(jù)稀疏時，會造成分類準確度大幅度降低[3]。 失衡數(shù)據(jù)的稀疏性問題可以從預處理方面解決數(shù)據(jù)的稀疏性問題，也可以從算法改進方面解決數(shù)據(jù)集的失衡性和稀疏性問題。從數(shù)據(jù)預處理方面，對于稀疏性可以采用缺失值處理方法針對稀疏數(shù)據(jù)集中缺失的屬性值進行填充，傳統(tǒng)填充方法普遍存在填充結(jié)果不可靠甚至改變原有數(shù)據(jù)形態(tài)，造成數(shù)據(jù)挖掘任務準確性降低。如何能夠在保證數(shù)據(jù)原有形態(tài)的基礎(chǔ)上將稀疏數(shù)據(jù)集轉(zhuǎn)化成非稀疏數(shù)據(jù)集的問題受到研究人員的關(guān)注。針對數(shù)據(jù)失衡性從算法改進方面，由于數(shù)據(jù)集中類別分布極其不均勻且存在大量屬性值空缺，對于二分類問題，即小類別的樣本規(guī)模遠遠小于大類別，會使小類別的信息量極度匱乏，造成分類器功能失效，數(shù)據(jù)稀疏性和失衡性是分類模型建立中的兩個決定性因素，必須兩者兼顧才有可能得到比較理想的分類模型，因此面向稀疏失衡數(shù)據(jù)的分類問題目前正受到該領(lǐng)域研究人員的高度重視。 
.........

1.2 失衡數(shù)據(jù)的稀疏性問題的研究現(xiàn)狀及分析 
目前，從國內(nèi)外針對失衡數(shù)據(jù)的稀疏性相關(guān)問題所發(fā)表的高水平論文及研究成果來看，該研究方向正逐漸受到越來越多學者和研究人員的重視。從研究側(cè)重點角度，可分成兩個子問題：解決數(shù)據(jù)稀疏性問題，解決數(shù)據(jù)失衡性問題。近年來，微博作為網(wǎng)絡社交平臺備受人們的喜愛，也成為情感分析領(lǐng)域的研究熱點之一，英國學者 Saif 對微博數(shù)據(jù)在訓練分類器過程中經(jīng)常遇到數(shù)據(jù)稀疏問題進行研究，并提出使用兩個不同的特征集來緩解稀疏性問題：語義特征集和情感主題特征集，該方法可以在緩解數(shù)據(jù)稀疏性的同時提高數(shù)據(jù)分類的準確性[5]；為了解決協(xié)同過濾推薦算法實施過程中“用戶-項目”數(shù)據(jù)集的稀疏性問題，學者 Hoseini 采用“逐步分割法”對“用戶-項目”數(shù)據(jù)集進行分割操作，一級分割根據(jù)用戶、項目的潛在相似性對用戶和項目進行分別聚類，二級分割是在一級類簇的基礎(chǔ)上對用戶和項目進行聯(lián)合聚類，該方法不僅解決了傳統(tǒng)協(xié)同過濾推薦算法稀疏性問題，也同時提高了推薦算法的可擴展性[6]；同樣是在協(xié)同過濾算法中數(shù)據(jù)稀疏性問題上，印度學者 Devi 提出使用概率神經(jīng)網(wǎng)絡來計算用戶之間的信任值，并通過信任值矩陣來預測稀疏矩陣中的缺失屬性值，以此來平滑稀疏矩陣，再由平滑的矩陣計算其他用戶之間的信任值，以此克服數(shù)據(jù)集稀疏性問題[7]；日本學者 Abdelwahab 則使用迭代預測方法解決協(xié)同過濾算法相似性計算時由于數(shù)據(jù)稀疏性造成的參考信息不足的問題，將稀疏矩陣轉(zhuǎn)化為稠密矩陣，從而也克服了推薦算法的稀疏問題和冷啟動問題.
.........

第2章 數(shù)據(jù)稀疏性和失衡性問題 

2.1 數(shù)據(jù)稀疏性和失衡性問題描述
失衡數(shù)據(jù)集的稀疏性問題可以從概念上分為兩個子問題，首先是數(shù)據(jù)的稀疏性問題，也是本文重點要解決的關(guān)鍵問題，然后是失衡數(shù)據(jù)本身所存在的失衡問題，主要表現(xiàn)在失衡數(shù)據(jù)的分類問題上，因此要解決失衡數(shù)據(jù)集的稀疏性問題首先要從本質(zhì)上了解數(shù)據(jù)稀疏性和失衡性這兩個內(nèi)在因素，并將這兩個問題綜合考慮，才能提出完整的解決方案。稀疏數(shù)據(jù)(Sparse  Data)是指屬性值存在缺失的數(shù)據(jù)，其中缺失部分稱為缺失數(shù)據(jù)又稱缺失值。缺失數(shù)據(jù)分析問題在經(jīng)典統(tǒng)計學中已經(jīng)有很長的歷史，1976年，美國學者 Rubin 指出了基于缺失數(shù)據(jù)的統(tǒng)計推斷所存在的問題，并對造成這種缺失的原因進行了詳細分析與說明[36]。在此基礎(chǔ)上許多關(guān)于缺失值處理的模型策略、推論和詳細的課題定義也因此得到了開展，并吸引了很多世界范圍的學者進行研究。 描述稀疏數(shù)據(jù)的一個重要的度量指標是數(shù)據(jù)的稀疏度(Sparsity)，稀疏度是指數(shù)據(jù)中所有非缺失單元的數(shù)目占總單元數(shù)目的比例。數(shù)據(jù)集越稀疏，其稀疏度數(shù)值越小，，相應的缺失度數(shù)值就越大。按照缺失數(shù)據(jù)的缺失類型，還可以將其分為下面三種。 
............

2.2 數(shù)據(jù)稀疏問題的原因及解決辦法
稀疏數(shù)據(jù)最典型的特征就是屬性值的不完整性，通常是因為數(shù)據(jù)獲取限制、數(shù)據(jù)理解有誤或漏讀等方面的原因?qū)е碌�，而由于原因的不同�?shù)據(jù)缺失值表現(xiàn)出來的特征也不一樣，從而稀疏度也相差甚遠，如上文所述的三種不同類型的缺失值。在 UCI 數(shù)據(jù)庫中，很多數(shù)據(jù)集是不完整的，即存在一定程度的稀疏性，在數(shù)據(jù)挖掘中缺失值處理不恰當就會導致與缺失值相關(guān)的某些有價值的信息或知識被忽略，從而影響結(jié)果的可靠性。因此為了提高數(shù)據(jù)挖掘算法的性能，首先必須解決的是數(shù)據(jù)本身所存在的問題，即數(shù)據(jù)稀疏性問題�，F(xiàn)實中缺失數(shù)據(jù)產(chǎn)生的原因有多種，例如，調(diào)查問卷實施過程中，受訪者對問題的遺漏、拒絕，或調(diào)查員與調(diào)查問據(jù)卷本身存在的一些疏忽，在調(diào)研中不恰當?shù)厥占瘮?shù)據(jù)或者數(shù)據(jù)錄入錯誤等。總的來說，主要原因可以分為以下幾類情況：信息暫時無法獲取例如，對于醫(yī)療系統(tǒng)數(shù)據(jù)庫來說，在某一時間段內(nèi)，會存在大量的病人信息是不完整的甚至是完全空缺的，這是因為某些病人的檢查結(jié)果的獲取需要一定的時間間隔，導致沒有辦法將這些病人的數(shù)據(jù)及時錄入系統(tǒng)。信息被遺漏這種情況往往是由于錄入者本身的主觀因素所造成的，例如，忘填或者對要填寫的項目沒有理解而未錄入且系統(tǒng)無提示，或由于數(shù)據(jù)采集、傳輸、存儲設備故障或損壞導致的等。 
..........

第 3 章 基于稀疏數(shù)據(jù)聚類的缺失值填充方法 ......... 15 
3.1  缺失值填充 ....... 15 
3.1.1  數(shù)據(jù)缺失值填充與稀疏性的關(guān)系 ..... 15 
3.1.2  基于統(tǒng)計學的填充方法 ............ 16 
3.1.3  基于機器學習的填充方法 ........ 17 
3.2  基于聚類協(xié)同過濾的填充方法 ........... 20 
3.2.1  聚類分析技術(shù)概述 ........... 20 
3.2.2  協(xié)同過濾算法 .......... 21 
3.2.3 K-means CF 填充算法 ...... 22
3.3  基于遞歸增量式聚類的填充方法 ....... 25 
3.4  實驗結(jié)果與分析 ........ 28
3.5  本章小結(jié) ........... 34 
第 4 章 失衡數(shù)據(jù)集分類方法 .......... 35 
4.1  失衡數(shù)據(jù)集分類策略概述 .......... 35
4.2  基于隨機游走模型的失衡數(shù)據(jù)分類方法 .... 39 
4.2.1  隨機游走模型概述 ........... 39 
4.2.2 IRWM 分類算法 ....... 40 
4.3  實驗與分析 ....... 43
4.4  本章小結(jié) ........... 46 

第4章 失衡數(shù)據(jù)集分類方法 

如前文所述，稀疏失衡數(shù)據(jù)集具有兩個重要的因素，即稀疏性和失衡性，在第三章中，我們通過兩種策略解決了失衡數(shù)據(jù)集的稀疏性問題，即通過前面的缺失值填充過程我們得到了完整的非缺失的數(shù)據(jù)集，為了數(shù)據(jù)集最終能準確分類的目的，下一步要解決數(shù)據(jù)的失衡性問題。目前，解決數(shù)據(jù)集失衡的方法主要從兩個方面入手：數(shù)據(jù)重采樣方法和分類方法改進。其中，通過對現(xiàn)有的比較成熟的常規(guī)分類方法的改進，可以得到適應不同失衡程度的分類方法，是失衡數(shù)據(jù)集分類的主要方法和常用方法之一。我們選擇隨機游走模型作為失衡數(shù)據(jù)的分類模型，是因為隨機游走模型已經(jīng)在模式識別領(lǐng)域和數(shù)據(jù)多標簽分類領(lǐng)域有成熟的理論基礎(chǔ)，并得到了應用，并且隨機游走模型建模過程簡單，沒有眾多參數(shù)的影響。 

4.1 失衡數(shù)據(jù)集分類策略概述 

分類是按照數(shù)據(jù)集的特征構(gòu)建適合的分類模型或分類器，從而將未知類別的對象映射到已知的類別當中。分類之前通常要對數(shù)據(jù)集進行預處理，包括對數(shù)據(jù)集進行清理和數(shù)據(jù)變換操作，例如，對數(shù)據(jù)的缺失值進行處理、對噪聲數(shù)據(jù)進行消除，將連續(xù)性屬性值轉(zhuǎn)變成離散性屬性值等；分類建模是最重要也是最關(guān)鍵的步驟，一般包括訓練（又稱學習）和測試兩個階段，通常將數(shù)據(jù)集通過一定的方法分成訓練樣本和測試樣本，并分別應用到相應的階段。主要的分類方法如下： 決策樹算法是以實例為基礎(chǔ)的歸納學習算法。方法通過從樹的根節(jié)點自頂向下對樹的內(nèi)部節(jié)點屬性值的對比，若不相同則進行分支處理，最后形成葉子節(jié)點不能繼續(xù)向下分支，這時葉子節(jié)點則是最后要劃分的類別。其中，從根節(jié)點到葉節(jié)點的所有路徑均可作為一種合取規(guī)則。KNN 法的思想是若某個實例的 k個最近鄰居大部分歸為某組或某類，那么目標實例同樣應該歸到該組。采用KNN 法進行分類時，僅僅按照一小部分實例的信息進行分類決策，因此KNN 更適合有交集的組進行快速的分類。

.........

結(jié)論 

本文針對失衡數(shù)據(jù)的稀疏性問題進行了深入的研究，設計了一套解決稀疏性和失衡性問題的完整方案。在數(shù)據(jù)預處理階段，針對缺失值分別提出基于聚類協(xié)同過濾的單層填充方法和基于遞歸增量式聚類的填充方法。在數(shù)據(jù)的失衡性問題上提出基于隨機游走模型的失衡數(shù)據(jù)分類方法。本論文主要有以下幾方面的研究成果及創(chuàng)新： 
1. 本文對失衡數(shù)據(jù)的稀疏性問題的國內(nèi)外研究現(xiàn)狀進行了總結(jié)和分析，從而將復雜數(shù)據(jù)—失衡稀疏數(shù)據(jù)所帶來的綜合性問題分解成稀疏性問題和失衡性問題兩個子問題進行分別探討和研究，將稀疏性問題放在處理階段解決，而失衡性問題放在分類算法的改進上解決。 
2. 在預理階段，針對數(shù)據(jù)稀疏問題進行深入研究，介紹和分析了現(xiàn)存方法的不足，并創(chuàng)新性的提出了聚類協(xié)同過濾的缺失值填充方法。該方法既克服了基于統(tǒng)計學的方法中分布假設判定困難的局限性也不需要復雜的建模過程，并且通過對比實驗驗證了該方法確實可以有效地填充缺失值。這種先聚類再計算填補值的一次性填充方法容易因初始數(shù)據(jù)存在大量缺失值而造成對象的誤聚，從而影響填充效果。因此在此基礎(chǔ)上提出了遞歸增量式填充方法，引入初始化填充步驟以彌補一次性聚類填充的局限性，并采用遞歸方式聚類并替換填充值，直到結(jié)果收斂或達到最小誤差，并通過對比實驗驗證了遞歸增量式方法性能上的提高。 
3. 在失衡數(shù)據(jù)分類過程中，介紹和分析了現(xiàn)有解決數(shù)據(jù)失衡性問題的兩大類方法，即從數(shù)據(jù)端解決和從算法端解決。本文提出一種基于隨機游走模型的分類方法，試圖從算法端解決失衡數(shù)據(jù)分類問題，考慮到正反例比例相差較大，分別設計了正例和反例兩套游走圖，能夠更好地適應失衡數(shù)據(jù)。設計了對比實驗，驗證了該分類算法的有效性和分類性能的提升。 
.........
參考文獻(略)

本文編號：75997