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

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

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