基于分治法的Rough集高效數(shù)據(jù)挖掘方法研究.pdf

1、在諸多數(shù)據(jù)挖掘方法中，Rough集理論是一種新型的智能信息處理方法，它采用確定的方法處理不確定問題，已是處理模糊、不精確和不完備問題的重要數(shù)學(xué)工具。Rough集通過數(shù)據(jù)預(yù)處理、離散化、知識約簡(屬性約簡、屬性值約簡)等過程，對數(shù)據(jù)進(jìn)行去粗取精、去偽存真，逐步地從原始數(shù)據(jù)集中獲取知識。使用Rough集，可以對原始數(shù)據(jù)進(jìn)行離散化、降維和知識約簡等處理，逐步降低問題的復(fù)雜性，它是進(jìn)行數(shù)據(jù)挖掘的一條有效途徑。
　　但是，作為數(shù)據(jù)挖掘研究中

2、的一個重要課題，現(xiàn)有的Rough集與方法仍然存在著一些沒有解決好的問題。例如，基于Rough集的高效數(shù)據(jù)挖掘方法、基于Rough集的海量數(shù)據(jù)挖掘理論與方法、基于Rough集的動態(tài)數(shù)據(jù)處理方法、Rough集的強(qiáng)泛化能力問題、云計算環(huán)境下的Rough集數(shù)據(jù)挖掘方法等。這些問題的存在，有待于我們對Rough集理論與方法進(jìn)行更深入地研究，并提出更好的解決方案。
　　分治法是一種有效處理復(fù)雜問題的方法，它也是一種簡單的粒計算方法。分治法的思

3、想就是將整個問題分成若干個問題后分而治之。當(dāng)求解的問題規(guī)模較大時，直接求解往往是非常困難的，有的甚至根本沒法直接求出，采用分治法可以將規(guī)模較大的問題分解為多個規(guī)模較小的問題，然后分別遞歸求解，最后將解合并，從而實(shí)現(xiàn)對原問題的求解。如果能將分治法應(yīng)用到Rough集數(shù)據(jù)挖掘方法的研究中，則有可能設(shè)計出高精度、高效率的數(shù)據(jù)挖掘方法。
　　本文分析了現(xiàn)有的Rough集理論與應(yīng)用研究現(xiàn)狀，以基于分治法的Rough集數(shù)據(jù)挖掘方法為研究主線，對

4、多維表快速排序的復(fù)雜度分析、基于Rough集的高效離散化方法、基于分治法的Rough集的知識約簡方法的抽象控制過程、Rough集的快速知識約簡方法等方面進(jìn)行了較為深入的研究。歸納起來，本文的主要研究工作和創(chuàng)新內(nèi)容表現(xiàn)在以下幾個方面：
　　(1)將多維數(shù)據(jù)快速排序的時間復(fù)雜度改進(jìn)為O(n×(m+log n))，提高了Rough集數(shù)據(jù)挖掘方法的海量數(shù)據(jù)處理能力。
　　基于分治法原理，將多維數(shù)據(jù)快速排序的時間復(fù)雜度從O(n×m×l

5、ogn)降低到O(n×(m+logn))(其中，m為數(shù)據(jù)維數(shù)，n為數(shù)據(jù)記錄數(shù))，并應(yīng)用于改進(jìn)傳統(tǒng)的知識約簡方法，在屬性核和知識約簡研究中取得了很好效果。這一成果，對實(shí)現(xiàn)快速、高效的海量數(shù)據(jù)挖掘，具有重要作用。
　　(2)提出了一個兩步處理策略的高效離散化算法，解決了Rough集理論中海量數(shù)據(jù)的離散化問題。
　　在基于Rough理論的數(shù)據(jù)挖掘過程中，離散化是一個重要的環(huán)節(jié)，現(xiàn)有的全局離散化算法很難兼顧高精度的離散化效果和高效率

6、，它已成為使用Rough集處理海量數(shù)據(jù)的一個瓶頸，其主要原因在于候選斷點(diǎn)太多造成了計算量和輔助存儲空間太大。為克服這一問題，本文提出了“先在單個屬性上進(jìn)行候選斷點(diǎn)的動態(tài)聚類；然后在所有屬性上進(jìn)行斷點(diǎn)選擇”的兩步處理思路，實(shí)驗結(jié)果表明，使用本方法得到的離散化結(jié)果和Skowron教授提出的貪心算法接近，但是運(yùn)行效率更高。本文提出的離散化算法更適合海量數(shù)據(jù)的處理，特別是樣本數(shù)量大的浮點(diǎn)決策表的離散化處理。
　　(3)提出了基于分治法的高

7、效屬性約簡算法和值約簡算法，有效地解決了海量數(shù)據(jù)的知識約簡問題。
　　分治法是一種有效處理復(fù)雜問題的方法，在Rough集知識約簡算法的設(shè)計過程中，如果能有效結(jié)合分治法，則有可能設(shè)計出高效的算法。針對此問題，本文首先介紹了等價關(guān)系下基于分治法的決策表分解方法，該方法可用于正區(qū)域、屬性核、屬性約簡的計算以及分辨矩陣的操作；其次，介紹了容差關(guān)系下基于分治法的決策表分解方法，該方法可用于決策表的值約簡；再次，提出了基于分治法的Rough集

8、知識約簡方法的抽象控制過程，該控制過程對于設(shè)計高效的知識約簡方法具有一定的參考意義。在此基礎(chǔ)上，通過在屬性空間上對論域?qū)ο筮M(jìn)行快速分解和操作分辨矩陣，給出了基于分治法的知識約簡方法。首先，改進(jìn)了王玨教授提出的屬性約簡算法，提出了一個新的快速屬性約簡算法，其次，提出了一個基于分治法的高效值約簡算法。實(shí)驗結(jié)果表明，采用文中提出的基于分治法的Rough集高效數(shù)據(jù)挖掘方法，可以在普通PC機(jī)上進(jìn)行300萬網(wǎng)絡(luò)入侵檢測數(shù)據(jù)(KDDCUP99)的數(shù)據(jù)