數(shù)據(jù)挖掘與數(shù)據(jù)庫知識發(fā)現(xiàn)

數(shù)據(jù)挖掘與數(shù)據(jù)庫知識發(fā)現(xiàn)

1數(shù)據(jù)庫知識發(fā)現(xiàn)與核心數(shù)據(jù)挖掘數(shù)據(jù)庫技術的快速發(fā)展和數(shù)據(jù)庫管理系統(tǒng)的廣泛應用導致了更多的數(shù)據(jù)積累。巨增的數(shù)據(jù)背后蘊藏著豐富的知識,而目前的數(shù)據(jù)庫技術雖可以高效地實現(xiàn)數(shù)據(jù)的查詢、統(tǒng)計等功能,但卻無法發(fā)現(xiàn)數(shù)據(jù)中存在的關系和規(guī)則,無法根據(jù)現(xiàn)有的數(shù)據(jù)預測未來的發(fā)展趨勢。數(shù)據(jù)庫中存在著大量的數(shù)據(jù),卻缺乏挖掘數(shù)據(jù)背后隱藏的知識的手段,出現(xiàn)了“數(shù)據(jù)爆炸而知識貧乏”的現(xiàn)象。在此背景下,數(shù)據(jù)庫知識發(fā)現(xiàn)(KDD)及其核心技術—數(shù)據(jù)挖掘(DM)便應運而生了。KDD的研究內(nèi)容是,能自動地去處理數(shù)據(jù)庫中大量的原始數(shù)據(jù),從中挖掘搜索出具有規(guī)律、富有意義的模式。它的發(fā)現(xiàn)過程主要有三個步驟:定義要發(fā)現(xiàn)的問題;根據(jù)問題進行數(shù)據(jù)搜索、模式抽取;評價所發(fā)現(xiàn)的知識的好壞。三者之中,核心技術是第二步,即數(shù)據(jù)搜索及模式抽取方法。KDD=問題處理+DM+解釋評價。由于問題處理和解釋評價的研究較成熟,所以目前KDD的研究和實現(xiàn)難點重點都集中在核心的DM上。DM的核心技術算法主要有統(tǒng)計分析方法、神經(jīng)元網(wǎng)絡、決策樹方法,遺傳算法等。其中,決策樹是一種常用于預測模型的算法,它通過將大量數(shù)據(jù)有目的地分類,從中找到一些具有商業(yè)價值的,潛在的信息。2有待生長的決策樹決策樹的結構,顧名思義,就像一棵樹。它利用樹的結構將數(shù)據(jù)記錄進行分類,樹的一個葉結點就代表某個條件下的一個記錄集,根據(jù)記錄字段的不同取值建立樹的分支;在每個分支子集中重復建立下層結點和分支,便可生成一棵決策樹。例如,我們要分析一個網(wǎng)站的用戶接受某項新服務的情況,可以從中選取100個用戶,其中50個接受這項新服務的,50個拒絕這項新服務的,然后通過建立決策樹來分析用戶的情況,尋找一些潛在的規(guī)則信息。利用決策樹進行分析,可以容易地找到一些具有商業(yè)價值的潛在的規(guī)則信息。如在上例中,從決策樹結構圖可以看出:在接受這項新服務的用戶中有60%是使用新帳號的,在拒絕這項新服務的用戶中有100%是使用舊帳號的;也就是說,如果用戶是使用新帳號的,那么他就有60%的可能接受這項新服務,如果用戶是使用舊帳號的,那么他就有100%的可能拒絕這項新服務。當然,還可以從決策樹中找到其它的規(guī)則信息,這里就不再舉例說明了。3子集中在預測內(nèi)容上的一致性建決策樹,就是根據(jù)記錄字段的不同取值建立樹的分支,以及在每個分支子集中重復建立下層結點和分支。建決策樹的關鍵在于建立分支時對記錄字段不同取值的選擇。選擇不同的字段值,會使劃分出來的記錄子集不同,影響決策樹生長的快慢以及決策樹結構的好壞,從而導致找到的規(guī)則信息的優(yōu)劣?？梢?決策樹算法的技術難點也就是選擇一個好的分支取值。利用一個好的取值來產(chǎn)生分支,不但可以加快決策樹的生長,而且最重要的是,產(chǎn)生的決策樹結構好,可以找到較好的規(guī)則信息。相反,如果根據(jù)一個差的取值來產(chǎn)生分支,不但減慢決策樹的生長速度,而且會使產(chǎn)生的決策樹分支過細,結構性差,從而難以發(fā)現(xiàn)一些本來可以找到的有用的規(guī)則信息。怎樣的取值才算一個好的取值呢?一個好的取值,就是決策樹根據(jù)此值來分裂時,產(chǎn)生的分支子集中的記錄在預測內(nèi)容上盡可能一致。何謂子集中的記錄在預測內(nèi)容上盡可能一致呢?舉個例子,我們對學生的思想品德情況進行分析,預測內(nèi)容是在思想品德上是優(yōu)或良,抽取10個學生記錄,其中5個學生的思想品德是優(yōu),另5個的是良,那么我們可以得到以下兩個不同的劃分:在(A)方案中,劃分后的左分支子集的記錄的思想品德都是優(yōu),右分支子集的記錄的思想品德都是良,即左分支100%優(yōu)、0%良,右分支100%良、0%優(yōu),子集中的記錄在預測內(nèi)容上已盡可能一致。我們就可以從兩個分支中尋找記錄的共性,以得到和學生思想品德情況有關的信息。在(B)方案中,劃分后的左分支子集中3條記錄的思想品德是優(yōu),2條記錄的思想品德是良,右分支子集中2條記錄的思想品德是優(yōu),3條記錄的思想品德是良,即左分支60%優(yōu)、40%良,右分支60%良、40%優(yōu),子集中的記錄在預測內(nèi)容上的一致性差,還不能有效地總結出和學生思想品德情況有關的信息。怎樣找到好的取值呢?從上例,可以看出,好的取值分支后子集的記錄的一致性好,也就是記錄的有序性好。通常,在系統(tǒng)學上,經(jīng)常使用“熵”來表示事物的無序度。所以在這里,也可以引用“熵”來估量分支后子集有序性的好壞。熵H=Σ(-Pi)×lg(Pi)其中Pi是指分支子集中記錄取某值的可能性。如果子集的熵值越小,則子集記錄的有序性越好;如果熵值越大,則有序性越差。因此,我們可以對根據(jù)不同取值進行分裂后的左右分支的子集分別計算各自的熵值,選擇熵值最小所對應的記錄字段的取值,這就是好的取值。如上例中,Ha左,右=(-5/5)×lg(5/5)+(-0/5)×lg(0/5)=0.0Hb左,右=(-3/5)×lg(3/5)+(-2/5)×lg(2/5)=0.3要提出注意的是,如果左右分支子集的記錄數(shù)相差太遠,則可能導致新的情況,此時只用熵值來判斷可能選擇不到好的取值。如上例,也可以得到以下兩個劃分:選擇小值,可能就選擇(C)方案,但從例子可以看出,(D)方案才是較好的,因為它把同類的基本劃分到一起了,而且如果像(C)方案那樣,每次都只把一個數(shù)據(jù)劃分出去,只會導致決策樹結構的層次變得復雜,同類型的記錄無法有效地歸到一起,不利于從中發(fā)掘潛在的信息。要解決這個問題,可以利用“加權和”的思想,根據(jù)分支子集所占的比重來給它一個權值,然后計算加權熵,通過比較加權熵的大小來選擇取值。加權熵H加=ΣXi×Hi其中Xi是指分支子集所占的比重,Hi是指分支子集的熵,則4加權熵算法的比較在實驗事例中,我們構造一個包括10條記錄的學生總評成績的模型,以分析學生總評成績在85分以上與何因素有關。我們提出兩個方案,(Ⅰ)方案每次選擇第一個取值來產(chǎn)生分支;(Ⅱ)方案利用加權熵算法選擇取值來產(chǎn)生分支。通過對兩個方案產(chǎn)生的決策樹進行比較,可以了解加權熵算法的優(yōu)點。在圖4中,Y表示學生的總評成績在85分以上;N表示學生的總評成績在85分以下。由圖4可見,方案(Ⅱ)構造的決策樹結構好,基本上將總評成績在85分以上或以下的同類學生劃分到一起,容易得出“如果學生的平時成績在85分以上,他的總評成績就有100%的可能在85分以上”、“如果學生的平時成績在85分以下,他的總評成績就有5/6即83.3%的可能在85分以下”等規(guī)則信息。實驗中兩個方案的比較表明,利用加權熵算法來選擇決策樹的分支取值,不但可以加快決策樹的生長,而且最重要的是可以得到結構好的決策樹,便于從中挖掘好的規(guī)則信息。雖然計算加權熵需要一定的時間開銷,但隨著記錄數(shù)據(jù)的增大,這點開銷不但因為決策樹的快速生長得到彌補,而且會使總的運算時間減少,從而提高算法的效率和性能。5利用規(guī)則信息來選擇算法為了在數(shù)據(jù)挖掘的決策