基于概念層次樹(shù)的數(shù)據(jù)挖掘算法及應(yīng)用研究-

1、收稿日期:2004-01-08;修返日期:2004-05-12基金項(xiàng)目:浙江省自然科學(xué)基金資助項(xiàng)目(602096基于概念層次樹(shù)的數(shù)據(jù)挖掘算法及應(yīng)用研究*肖 娟1,葉 楓2(1.浙江工業(yè)大學(xué)之江學(xué)院經(jīng)貿(mào)管理系,浙江杭州310024; 2.浙江工業(yè)大學(xué)經(jīng)貿(mào)管理學(xué)院,浙江杭州310014摘 要:概念層次樹(shù)在大規(guī)模數(shù)據(jù)挖掘中已得到廣泛應(yīng)用。在介紹基于概念層次樹(shù)的數(shù)據(jù)挖掘算法的基礎(chǔ)上,針對(duì)已有數(shù)值型數(shù)據(jù)概念提升算法的不足,提出了改進(jìn)后的算法,并通過(guò)數(shù)據(jù)測(cè)試給出兩種算法的比較效果和應(yīng)用實(shí)例。關(guān)鍵詞:概念層次;數(shù)據(jù)挖掘;閾值中圖法分類號(hào):TP391 文獻(xiàn)標(biāo)識(shí)碼: A 文章編號(hào):1001-3695(20050

2、3-0061-03Research on Dat a M ining Algor it hm Based on Con cept ion Hierar chy Tree and Its Applica tionXIAO J ua n 1,YE Feng 2(1.Dep t.of Economic Management,Zhejiang College,Zhejiang University of Technology,H angz hou Zhejiang 310024,China;2.College of Eco-nomic Management,Zhejiang Univer sity o

3、f Technology,H angz hou Zhejiang 310014,ChinaAbst ract :Concept ion hierarchy t ree clas sifiers hav e found t he widest applica bilit y in larg e-sca le da ta m ining env ironm ent s.Aft er introduced a da ta m ining a lg orit hm bas ed on conception hierarchy tree.This pa per,in the light of the l

4、im itat ions of exist ed concept ass ension a lg orithm to num erical a tt ributes in dat abase,int roduces an im proved a lg orit hm .Moreover,the result of two a lg orithm t es ting on a ct ua l dat a is prov ided in t his paper.Key words:Concept ion Hierarchy ;Da ta M ining;Threshold 目前常用的各類數(shù)據(jù)挖掘算

5、法,主要用于特征規(guī)則、關(guān)聯(lián)規(guī)則、分類規(guī)則、序貫?zāi)Ｊ降陌l(fā)現(xiàn),但將這些算法用于實(shí)際的大型數(shù)據(jù)庫(kù)進(jìn)行知識(shí)發(fā)現(xiàn),卻不能取得很好的效果。概念層次樹(shù)作為數(shù)據(jù)分類的方法,可以將大量詳細(xì)的細(xì)節(jié)數(shù)據(jù)總結(jié)上升到較高的概念層,為數(shù)據(jù)挖掘的各個(gè)步驟提供背景知識(shí),提高知識(shí)的準(zhǔn)確性和可理解性。適合用戶需要較高層次的、能反映一定關(guān)系的規(guī)則來(lái)支持決策的實(shí)際應(yīng)用,此外可用于對(duì)數(shù)據(jù)預(yù)處理得到清潔的元數(shù)據(jù)及知識(shí)表示。本文試圖對(duì)基于概念層次樹(shù)的數(shù)據(jù)挖掘算法有所改進(jìn),如實(shí)現(xiàn)層次自動(dòng)提取與概念提升同步的數(shù)據(jù)挖掘算法,非均勻分布下數(shù)據(jù)的概念層次的自動(dòng)提取等功能。1 概念層次及概念層次樹(shù)所謂概念層次H 就是部分有序集(h,;,其中h 是有限

6、概念集合,;是h 上的部分有序關(guān)系。概念層次能夠以層次的形式和偏序的關(guān)系組織數(shù)據(jù)和概念。如我們?nèi)∫话闾厥獾年P(guān)系為;,可以表示城市、省份的關(guān)系,如杭州;浙江省;中國(guó)。通常我們以層次樹(shù)來(lái)表示一個(gè)概念層次,即概念層次樹(shù)(Concept Hierarchy Tree,樹(shù)的節(jié)點(diǎn)表示概念,樹(shù)枝表示偏序。圖1是客戶年齡的概念層次樹(shù)。概念層次樹(shù)可由領(lǐng)域內(nèi)的專家提供,但在實(shí)際評(píng)估中,因?yàn)閿?shù)據(jù)規(guī)模很大,協(xié)調(diào)專家之間的意見(jiàn)非常困難,人工定義大型的概念層次樹(shù)亦不合理、不現(xiàn)實(shí),且提供的概念層次樹(shù)可能是最一般的概念層次樹(shù),常包含全部可能的屬性值以及它們對(duì)應(yīng)的全部可能的父概念。這種概念樹(shù)對(duì)于特定的數(shù)據(jù)庫(kù)顯得偏大,并且影響到

7、概念提升的速度,因而缺乏一定的靈活性和針對(duì)性。通常,無(wú)論是領(lǐng)域?qū)＜叶x還是自動(dòng)生成概念層次樹(shù),概念層次樹(shù)的構(gòu)造有自頂向下和自底向上兩種方式1。所以對(duì)于數(shù)據(jù)庫(kù)中常常存在各種數(shù)值型屬性的情況,一般采用自動(dòng)生成數(shù)值型概念層次的概念化方法:由用戶指定期望的分段數(shù),由機(jī)器自學(xué)習(xí),將屬性值分成若干個(gè)區(qū)間。該方法可滿足大型數(shù)據(jù)庫(kù)中特殊挖掘任務(wù)的要求,它能針對(duì)特殊挖掘任務(wù)的要求構(gòu)造專門的概念層次,反映特殊數(shù)據(jù)集合中的數(shù)據(jù)分布。本文正是對(duì)面向數(shù)值型數(shù)據(jù)構(gòu)建概念層次樹(shù)的數(shù)據(jù)挖掘方法提供一些建議和改進(jìn)。2 基于概念層次樹(shù)的數(shù)據(jù)挖掘算法基于概念層次樹(shù)的數(shù)據(jù)挖掘方法的基本思想2是:首先,一個(gè)屬性的較具體的值被該屬性和概

8、念層次樹(shù)中的父概念所代替;然后,對(duì)知識(shí)基表中出現(xiàn)的相同記錄進(jìn)行合并,構(gòu)成更宏觀的記錄,并計(jì)算宏記錄所覆蓋的記錄數(shù)目,如果數(shù)據(jù)庫(kù)中記錄生成的宏記錄數(shù)目仍然很大,那么用這個(gè)屬性的概念層次樹(shù)中更一般的父概念去替代,或者根據(jù)另一個(gè)屬性進(jìn)行概念層次樹(shù)的提升操作,最終生成覆蓋面更廣,數(shù)量更少的宏記錄;最16第3期 肖 娟等:基于概念層次樹(shù)的數(shù)據(jù)挖掘算法及應(yīng)用研究 圖1年齡概念層次樹(shù)17183550穴少年雪穴中后,將所得的結(jié)果轉(zhuǎn)換為邏輯規(guī)則。一般的,基于概念層次樹(shù)的數(shù)據(jù)挖掘算法在進(jìn)行概念提升時(shí)需要兩個(gè)重要前提:一是具有相關(guān)屬性、元組的預(yù)分析數(shù)據(jù)集;二是包含相關(guān)屬性的概念層次樹(shù)。通常在得到完整的概念層次樹(shù)后,

9、再對(duì)初始數(shù)據(jù)集中的屬性進(jìn)行概念提升。3 數(shù)值型數(shù)據(jù)自動(dòng)提取概念層次的算法對(duì)數(shù)值型字段數(shù)據(jù)的概念化,就是將字段中的所有數(shù)據(jù)進(jìn)行概念分段,將每一段用一個(gè)概念值表示,然后將原字段中的所有數(shù)據(jù)用它所對(duì)應(yīng)的概念段的概念值來(lái)代替,產(chǎn)生概念表。例如,對(duì)某一個(gè)數(shù)值型字段進(jìn)行概念分段得到如下的概念段: 2,12K,12,16K16K,23K,23-90K,這一字段中的每一個(gè)值用對(duì)應(yīng)的概念段或指定的概念段值來(lái)代替,就完成了對(duì)這一字段的概念化。一般的數(shù)值型概念層次生成算法都是通過(guò)將數(shù)值型屬性的值域區(qū)間離散化,形成多個(gè)子區(qū)間作為概念層次的葉節(jié)點(diǎn),基本方法有等距離區(qū)間法和等頻率區(qū)間法。其中等頻率區(qū)間法3,4實(shí)現(xiàn)簡(jiǎn)單,且

10、效率較高。這種算法假定數(shù)據(jù)的取值呈現(xiàn)均勻分布,即各分段內(nèi)的記錄數(shù)較為接近。算法先用相同的小間隔Int erva l=(Hig h-Low/(K×T將數(shù)值字段中的數(shù)據(jù)分段,其中Hig h和Low表示字段的最大值和最小值,K表示將數(shù)值型區(qū)間分段的合理性即分段頻度,T 指屬性值在數(shù)據(jù)庫(kù)中出現(xiàn)的不同值的個(gè)數(shù)的界限即區(qū)段數(shù),接著對(duì)落在每一數(shù)據(jù)段中的數(shù)據(jù)量進(jìn)行計(jì)數(shù)及記錄總數(shù)Tota l-Count;然后利用合并分段算法5從第一個(gè)數(shù)據(jù)段開(kāi)始累計(jì)數(shù)據(jù)的總計(jì)數(shù),如果大于期望覆蓋數(shù)(Tot alCount/T,則將其合并成一個(gè)概念段,對(duì)其賦予概念值。用同樣的方法直至到達(dá)最后一個(gè)數(shù)據(jù)段。將數(shù)據(jù)段合并成期望

11、(T個(gè)概念段,其中每個(gè)概念段中的數(shù)據(jù)個(gè)數(shù)是基本相同的。從本質(zhì)上講,這種算法先用相同的小間隔將數(shù)值字段中的數(shù)據(jù)分段,然后將數(shù)據(jù)段合并成期望(T個(gè)概念段,其中每個(gè)概念段中的數(shù)據(jù)個(gè)數(shù)是基本相同的。而這只是針對(duì)數(shù)據(jù)取值均勻分布的情況,其概念分段的標(biāo)準(zhǔn)只有數(shù)據(jù)個(gè)數(shù),沒(méi)有考慮數(shù)據(jù)的分布情況。所以,當(dāng)數(shù)據(jù)取值分布雜亂不均勻時(shí),此算法就顯得不足。由于用于劃分?jǐn)?shù)據(jù)段的Int erv al是一個(gè)不變的量,顯然,這種情況下每一數(shù)據(jù)段中的數(shù)據(jù)個(gè)數(shù)不完全相同,如果字段中的數(shù)據(jù)分布在某一取值范圍內(nèi)非常集中的話,那么在一些數(shù)據(jù)段中的數(shù)據(jù)量就會(huì)接近期望覆蓋數(shù)或者可能會(huì)使概念段中的數(shù)據(jù)量遠(yuǎn)大于期望覆蓋數(shù),并且使實(shí)際求出的概念段

12、數(shù)可能小于期望的概念段數(shù)。當(dāng)然通過(guò)增大值K,使Int erv al 變小,去增加數(shù)據(jù)段數(shù),可以減少每一數(shù)據(jù)段的數(shù)據(jù)個(gè)數(shù),但這并不是本質(zhì)的解決方法。4 改進(jìn)的基于概念層次樹(shù)的數(shù)據(jù)挖掘算法通過(guò)分析知道,算法的主要缺陷在于用于分割的Int erv al 是一個(gè)不變的量,不適于數(shù)據(jù)取值分布不均勻的情況,對(duì)于此缺陷,本文提出一種用于面向數(shù)值型數(shù)據(jù)的概念層次自動(dòng)提取與概念提升同步的數(shù)據(jù)挖掘算法。4.1 算法設(shè)計(jì)的基本思想(1構(gòu)建概念層次樹(shù)與概念提升同步?；趯?duì)數(shù)值型數(shù)據(jù)自動(dòng)提取概念層次的算法,在自底向上逐層構(gòu)建概念層次時(shí),同步進(jìn)行概念提升和規(guī)則挖掘。為每個(gè)屬性構(gòu)建概念層次的第一層,便根據(jù)該層概念對(duì)數(shù)據(jù)集進(jìn)

13、行概念提升,若提升后的宏元組數(shù)目小于用戶指定的閾值要求,則停止概念層次自動(dòng)建樹(shù),獲得挖掘規(guī)則;若提升后的宏元組數(shù)目大于閾值要求,則繼續(xù)構(gòu)建上一層概念層次。這種同步挖掘尤其適于用戶以獲得規(guī)則為目的的情況,即只要能得到滿足閾值要求的宏元組集合,便能得到有用的規(guī)則。特別是對(duì)屬性值分布比較集中的情況,無(wú)須再向上構(gòu)建父概念,即可滿足概念提升的閾值要求。此時(shí),該算法概念層次停止向上構(gòu)建,獲得所需的宏元組。這樣也節(jié)省了構(gòu)建和存儲(chǔ)概念層次樹(shù)所需的空間。(2變間隔分割數(shù)值型數(shù)據(jù)。一般的,由于自動(dòng)構(gòu)建概念層次樹(shù)的最后目的是使每個(gè)分段內(nèi)的記錄數(shù)基本接近,概念層次自動(dòng)提取算法假定數(shù)值分布均勻,提取出的概念分段的取值是

14、連續(xù)的。而對(duì)于數(shù)據(jù)取值分布不均勻的情況,若仍采用這種等間隔分割數(shù)值型數(shù)據(jù)的方法,就只能通過(guò)增大數(shù)值K來(lái)解決問(wèn)題,卻使算法的效率降低。針對(duì)此,本文的改進(jìn)算法中引入變間隔分割數(shù)值型數(shù)據(jù)的概念化方法4提取概念層次。該算法基本思想是:考慮概念分段時(shí)的數(shù)據(jù)個(gè)數(shù)和數(shù)據(jù)分布。對(duì)選定字段中的數(shù)據(jù)進(jìn)行分割時(shí),依次判斷一個(gè)Interv al 間隔內(nèi)的數(shù)據(jù)量的多少,采用變間隔進(jìn)行分割。如判斷數(shù)據(jù)量過(guò)大,則縮小Interva l值并將其作為分割間隔,將數(shù)據(jù)分成數(shù)據(jù)段。這種方法提取出的概念分段的取值也是連續(xù)的。(3通過(guò)方差與用戶交互指定參數(shù)值。方差是通過(guò)計(jì)算偏離總均數(shù)的平方和再除以n-1(樣本量減1而得到的。這樣,給定

15、n值的情況下,方差就是離均差平方和。由于k值的改變可能會(huì)影響算法的最終結(jié)果。如前所述,若增大k值,可使Interva l值變小,增加初始數(shù)據(jù)段數(shù),減少每一數(shù)據(jù)段的數(shù)據(jù)個(gè)數(shù),從而改變合并分段后概念段的取值范圍,最終可能改變概念層次提取的結(jié)果。此外,由于算法中最后一個(gè)概念分段的合并標(biāo)準(zhǔn)是概念節(jié)點(diǎn)數(shù)目,而不是期望覆蓋數(shù),就可能使這個(gè)分段的記錄數(shù)與平均記錄數(shù)有較大的偏離。所以本改進(jìn)算法中引入方差計(jì)算,采用與用戶交互的方式指定k值,對(duì)得到的記錄分布與期望平均記錄比較計(jì)算方差,通過(guò)對(duì)方差值的觀察,更便于用戶在試驗(yàn)中指定合理的k值。4.2 算法流程輸入:訓(xùn)練集、預(yù)分析條件和配置信息(提升概念層次的閾值、噪音

16、閾值、區(qū)段數(shù)、粒度;輸出:數(shù)據(jù)的概念層次。(1準(zhǔn)備預(yù)分析的初始數(shù)值型屬性數(shù)據(jù)集;(2指定約束條件(參數(shù);(3For所有屬性do(4利用變間隔分割算法構(gòu)建上一層概念層次;(5For所有元組do(6For each屬性do(7概念提升(用父概念替換原屬性值;(8合并屬性值均相同的元組構(gòu)成宏元組集合;(9If宏元組記錄數(shù)大于期望分段數(shù)Then繼續(xù)構(gòu)造高層概念節(jié)點(diǎn);(10計(jì)算方差。其中的概念提升算法根據(jù)本層概念節(jié)點(diǎn),對(duì)初始數(shù)據(jù)庫(kù)進(jìn)行概念提升:為每個(gè)元組的每個(gè)屬性找到其對(duì)應(yīng)的高一層父概念,將該屬性替換為其父概念。For each tuple in R;For all attr ibute A doFor

17、 ea ch seg=low+h*interval,low+i*intervaldo26計(jì)算機(jī)應(yīng)用研究2005年if tA<=low+i*inter val then將屬性A的值用父概念代替;同時(shí),建立一個(gè)Cust_Tot alU p表,用于存放當(dāng)前處理層的概念節(jié)點(diǎn)值,節(jié)點(diǎn)值采用區(qū)間的形式。且概念值被進(jìn)一步提升時(shí),直接在表中對(duì)原屬性值進(jìn)行替換。然后,合并表中屬性值均相同的元組,計(jì)算覆蓋數(shù),由它們構(gòu)成提升后的宏元組集合(其中增加一個(gè)屬性覆蓋數(shù)。下一步瀏覽提升后的宏元組集合,若滿足于閾值Thresh-old(或泛化閾值且沒(méi)有更高的概念用于提升,則根據(jù)宏元組的數(shù)目及每個(gè)宏元組的覆蓋數(shù)計(jì)算各宏元

18、組權(quán)值T-w eight=覆蓋數(shù)/覆蓋數(shù),剔除覆蓋度低的宏元組(低于剪枝閾值N oisethreshold,將剩余的每個(gè)宏元組轉(zhuǎn)換成一個(gè)規(guī)則。若不滿足閾值要求,則繼續(xù)構(gòu)造高一層的概念節(jié)點(diǎn)。4.3 數(shù)據(jù)分析若將上述算法對(duì)以SQL S erver形式的外貿(mào)企業(yè)業(yè)務(wù)數(shù)據(jù)庫(kù)進(jìn)行測(cè)試,可看出改進(jìn)后算法在面對(duì)大規(guī)模數(shù)據(jù)庫(kù)時(shí)具有的優(yōu)勢(shì)。數(shù)據(jù)分布結(jié)果由直方圖作出,圖2和圖3是分別為原算法和改進(jìn)后算法在34條記錄上測(cè)試得到的結(jié)果。概念段的范圍由細(xì)線分割的區(qū)域表示。參數(shù)T和K分別是4和7,為了便于比較分段的效果,閾值和噪聲閾值為4和一較小值,即不考慮由于閾值控制的進(jìn)一步概念提升和刪減,而只是對(duì)變間隔和等間隔分割的

19、效果進(jìn)行比較。實(shí)驗(yàn)分析的字段的最大值是4730200,最小值Low是10140,由參數(shù)T和K可以求出平均覆蓋度是8.5,初始間隔Int erva l=(high-low/(K×T放大為143574。由圖2可以看出,由于平均覆蓋度和固定初始間隔的影響,原算法將字段內(nèi)的數(shù)據(jù)分為四個(gè)概念段內(nèi),最后一個(gè)分段的覆蓋度僅為3,遠(yuǎn)遠(yuǎn)小于平均覆蓋度,計(jì)算方差為17.0。產(chǎn)生這種情況的原因就是因?yàn)樗鶞y(cè)試的數(shù)據(jù)分布極不均勻,使得原算法不再適用。由于前兩個(gè)初始分段間隔內(nèi)的數(shù)據(jù)分布過(guò)密,均大于9,已遠(yuǎn)遠(yuǎn)超出平均覆蓋度,從而使合并分段后的最終分段也失去平衡。而利用改進(jìn)算法后,可以得到38個(gè)經(jīng)過(guò)調(diào)整后的初始分段

20、(圖3。其中的覆蓋數(shù)都在15之間,其分布均比在原算法的初始間隔中的要均勻得多。從圖3可以看出,改進(jìn)的算法對(duì)數(shù)據(jù)分布過(guò)密的初始間隔進(jìn)行縮小調(diào)整,得到的各概念段都與平均覆蓋度接近,經(jīng)計(jì)算方差為3.7。相比原算法對(duì)其缺陷給予了改進(jìn)。如果為了得到更加理想的分段結(jié)果,可以調(diào)整T,K值。對(duì)數(shù)據(jù)庫(kù)中需處理的數(shù)據(jù)表的所有數(shù)值型字段進(jìn)行概念分段后,就可以將原數(shù)據(jù)表中的數(shù)據(jù)以它的概念值表示,產(chǎn)生一個(gè)新的概念表,對(duì)這個(gè)概念就可以運(yùn)用聚類、關(guān)聯(lián)規(guī)則等各種方法進(jìn)行進(jìn)一步數(shù)據(jù)挖掘。5外貿(mào)企業(yè)客戶關(guān)系管理中的應(yīng)用實(shí)例本實(shí)例以某外貿(mào)企業(yè)的客戶數(shù)據(jù)庫(kù)為研究對(duì)象,學(xué)習(xí)任務(wù)是通過(guò)改進(jìn)的數(shù)值型數(shù)據(jù)自動(dòng)提取概念層次法,概念化客戶合同金

21、額,在一定高度上發(fā)現(xiàn)指定時(shí)間內(nèi)各地區(qū)外貿(mào)企業(yè)客戶的外銷模式。由于廣大企業(yè)后臺(tái)一般以MS SQL S erv er7.0數(shù)據(jù)庫(kù)為基礎(chǔ)構(gòu)建的,考慮數(shù)據(jù)庫(kù)的轉(zhuǎn)換和系統(tǒng)運(yùn)行環(huán)境的一致性,為避免不必要的麻煩,開(kāi)發(fā)環(huán)境的后臺(tái)采用相同的數(shù)據(jù)庫(kù)。對(duì)于前端開(kāi)發(fā)工具的選擇,因?yàn)閿?shù)據(jù)挖掘技術(shù)本身需要大量的計(jì)算,為節(jié)省時(shí)間,采用執(zhí)行效率高的系統(tǒng)存儲(chǔ)過(guò)程(S tored Procedure作為開(kāi)發(fā)工具,通過(guò)單獨(dú)設(shè)計(jì)存儲(chǔ)過(guò)程以達(dá)到專門的目的。用戶交互界面設(shè)計(jì)采用Pow er Builder8.0為開(kāi)發(fā)工具,可很好地保證兩者的完美結(jié)合,只需寫(xiě)一個(gè)語(yǔ)句就可利用參數(shù)傳遞在服務(wù)器端調(diào)用存儲(chǔ)過(guò)程,比在本地編程再傳送到服務(wù)器端可以減少許多負(fù)載。6總結(jié)本文分析了原有基于概念層次樹(shù)的數(shù)據(jù)挖掘算法的局限性,提出了一種改進(jìn)的基于概念層次樹(shù)的數(shù)據(jù)挖掘算法,并將改進(jìn)算法應(yīng)用于實(shí)際的外貿(mào)企業(yè)業(yè)務(wù)數(shù)據(jù)庫(kù)上。由于時(shí)間原因和客觀條件所限,筆者認(rèn)為在如下幾個(gè)方面仍需完善:(1由于所能獲得的客戶數(shù)據(jù)庫(kù)的限制,用于實(shí)驗(yàn)的客戶數(shù)據(jù)不夠多,實(shí)例分析過(guò)程中選取的屬性個(gè)數(shù)也較少,因而在充分體現(xiàn)該算法的優(yōu)勢(shì)中受到一些限制。(2在該算法中,仍未能對(duì)已有算法中存在的不足之處做全面改進(jìn)。對(duì)于原算法的合并分段