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

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

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

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

4、多維表快速排序的復(fù)雜度分析、基于Rough集的高效離散化方法、基于分治法的Rough集的知識(shí)約簡(jiǎn)方法的抽象控制過程、Rough集的快速知識(shí)約簡(jiǎn)方法等方面進(jìn)行了較為深入的研究。歸納起來，本文的主要研究工作和創(chuàng)新內(nèi)容表現(xiàn)在以下幾個(gè)方面：
　　(1)將多維數(shù)據(jù)快速排序的時(shí)間復(fù)雜度改進(jìn)為O(n×(m+log n))，提高了Rough集數(shù)據(jù)挖掘方法的海量數(shù)據(jù)處理能力。
　　基于分治法原理，將多維數(shù)據(jù)快速排序的時(shí)間復(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í)約簡(jiǎn)方法，在屬性核和知識(shí)約簡(jiǎn)研究中取得了很好效果。這一成果，對(duì)實(shí)現(xiàn)快速、高效的海量數(shù)據(jù)挖掘，具有重要作用。
　　(2)提出了一個(gè)兩步處理策略的高效離散化算法，解決了Rough集理論中海量數(shù)據(jù)的離散化問題。
　　在基于Rough理論的數(shù)據(jù)挖掘過程中，離散化是一個(gè)重要的環(huán)節(jié)，現(xiàn)有的全局離散化算法很難兼顧高精度的離散化效果和高效率

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

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

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