數(shù)據(jù)驅(qū)動的屬性值分類法及其在屬性泛化中的應(yīng)用

錢卓昊

（西安石油大學(xué) 計算機學(xué)院，西安710065）

0 引 言

現(xiàn)實生活中，屬性值分類（AVT）又稱層次屬性值（Hierarchical Attribute Value），是廣泛存在的，如時間屬性上日、月、季、年等具有層次特征的屬性值［1］?？梢岳酶拍顚哟螌⒃蓟A(chǔ)數(shù)據(jù)抽象到不同層次，實現(xiàn)數(shù)據(jù)泛化。同時，基于多層次（Multiple Levels）數(shù)據(jù)挖掘，可能會從較高層次數(shù)據(jù)中發(fā)現(xiàn)更普遍或更重要的知識，且獲取的規(guī)則也更易于理解［2］。數(shù)據(jù)集中AVT樹型結(jié)構(gòu)可由相關(guān)領(lǐng)域?qū)＜姨峁部筛鶕?jù)訓(xùn)練集自動構(gòu)建而成。

具有層次結(jié)構(gòu)的數(shù)據(jù)已被廣泛應(yīng)用，Han等提出了一種利用概念分類法和自頂向下遞進(jìn)深化方法在不同層次上尋找概念之間的關(guān)聯(lián)規(guī)則的算法XLT2L1［3］；如Hong等基于粗糙集理論提出一種獲取跨層次確定性規(guī)則和可能性規(guī)則的方法［4］；研究了具有層次結(jié)構(gòu)的模糊粗糙集［5］；Feng等利用層次結(jié)構(gòu)提出一種自上向下的挖掘?qū)哟螞Q策規(guī)則的方法［6］。

雖然AVT的有效性已被證明，但針對構(gòu)建AVT的研究還比較少。涉及AVT時，大多是基于相關(guān)專家意見所構(gòu)建的AVT，這使得AVT具有主觀成分，且在研究高維度數(shù)據(jù)時其準(zhǔn)確度降低。在已有的從數(shù)據(jù)中構(gòu)建AVT研究中，都是將AVT直接與分類模型綜合在一起來處理數(shù)據(jù)，而沒有進(jìn)行屬性泛化約簡，這使得處理后的數(shù)據(jù)依舊可以進(jìn)一步泛化。如AVT-NBL模型，在構(gòu)建AVT時如何度量屬性值間的相似關(guān)系目前也沒有最佳標(biāo)準(zhǔn)，用JS散度來度量［1］。為了研究AVT在離散屬性中的應(yīng)用，本文采用VDM距離來度量。

本文利用VDM度量樣本屬性值間的距離，進(jìn)而利用層次聚類設(shè)計了一種依據(jù)數(shù)據(jù)自動構(gòu)建AVT的VDM-AVT學(xué)習(xí)器。為了驗證這種學(xué)習(xí)器的有效性，本文構(gòu)建了VDM-AVT-AGR模型，該模型在處理數(shù)據(jù)集時，會基于VDM-AVT學(xué)習(xí)器對數(shù)據(jù)構(gòu)建的AVT層次模型來進(jìn)行屬性泛化約簡，使得數(shù)據(jù)集在屬性個數(shù)和屬性域兩個層面實現(xiàn)降維。

1 基本概念

1.1 決策表

決策表（也可稱為決策信息系統(tǒng)）是一個四元組S＝（U，C∪D，V，f），其中U是非空有限對象集，稱為論域；C∪D是非空有限屬性集；C為條件屬性集；D＝｛d｝為決策屬性集，且C∩D＝?；V為屬性a的值域；f：U×A→V為信息函數(shù)［7］。

1.2 屬性值分類法（Attribute value taxonomy）

VDM-AVT學(xué)習(xí)器所構(gòu)建的AVT中，Va是包含屬性a的所有初始值的有限集，屬性a的屬性值分類A V T（a）是基于Va內(nèi)元素間的相似性構(gòu)建的一種樹形概念層次結(jié)構(gòu)。

A V Ts（C）＝｛A V T（a1），AV T（a2），...，A V T（a m）｝是關(guān)于C＝｛a1，a2，...，a m｝的屬性值分類集合。A V T（a）中，葉節(jié)點相當(dāng)于屬性a在原始數(shù)據(jù)中的初始屬性值。內(nèi)部節(jié)點代表其相應(yīng)子節(jié)點的泛化屬性值，樹上的每段弧代表了相鄰且不同層次屬性值之間的粗化或細(xì)化關(guān)系。令L ea f（a）代表AV T（a）的葉節(jié)點，Ro ot（a）代表其根節(jié)點，Node（a）代表A V T（a）的所有節(jié)點，內(nèi)部節(jié)點（除葉節(jié)點以外的節(jié)點）相當(dāng)于屬性a的泛化值。C h i l d（v，a）是屬性值v在A V T（a）中的所有子節(jié)點集合，De pt h（a）是A V T（a）中從根節(jié)點到葉節(jié)點的最大路徑長度。如圖1為本文利用VDM-AVT學(xué)習(xí)器處理UCI數(shù)據(jù)集Car Evaluation的maint屬性得到的A V T（mai n t）。

其中：

1.3 層次聚類

AVT的構(gòu)建可看作一個層次聚類的過程。層次聚類法（hierarchical methods）是遞歸地對數(shù)據(jù)對象進(jìn)行合并或者分裂，直到某種終止條件滿足為止。根據(jù)層次的分解的方式，具體又可分為“自底向上”和“自頂向下”兩種方案。在“自底向上”方法當(dāng)中，初始時將每個對象作為單獨的一個聚類，相繼地合并相互鄰近的聚類，合并一次之后，聚類總數(shù)減一，直到所有的聚類合并成一個聚類或是滿足一個終止條件［8-9］。

圖1 AVT（maint）Fig.1 AVT（maint）

VDM-AVT學(xué)習(xí)器采用“自底向上”的層次聚類思路對屬性不斷進(jìn)行抽象。先計算樣本之間的距離，每次將距離最近的點合并到同一個類；再計算類與類之間的距離，將距離最近的類合并為一個大類；不停的合并，直到合成了一個類。最短距離法是將類與類的距離定義為類與類之間樣本的最短距離［10］。而VDM-AVT學(xué)習(xí)器將VDM作為距離度量，同時每次選擇距離最短的類進(jìn)行合并。

1.4 VDM（Value Difference Metric）

現(xiàn)實生活中存在許多類似交通工具（火車，汽車）這樣的無序?qū)傩裕疚闹饕槍@類型數(shù)據(jù)進(jìn)行研究，VDM距離在處理離散屬性時的有效性已經(jīng)被廣泛驗證，比如Zhang等在處理異構(gòu)數(shù)據(jù)的離散部分時使用VDM距離度量數(shù)據(jù)相似程度［11］。本文亦選擇將VDM作為層次聚類的距離定義。

令mu，x表示屬性u上取值為x的樣本數(shù)；mu，x，i表示在第i個樣本簇中在屬性u上取值為x的樣本數(shù)；k為樣本簇數(shù)，則屬性u上兩個離散值x與y之間的VDM距離為式（1）：

其中，i簇在決策表中對應(yīng)決策屬性的屬性值，i簇所包含的對象即是決策屬性值為i的對象；k為決策屬性的屬性值種類數(shù)；則可計算屬性u上兩個離散值x與y之間的VDM距離。

1.5 局部分割

對于屬性a的屬性值分類A V T（a），其局部分割γ定義為No d e（a）的子集，且γ滿足以下性質(zhì)：

（1）對于任意p∈L ea f（a），則p∈γ，否則，存在q∈γ，p是q的祖先；

（2）對于γ中任意二個結(jié)點p和q，p既不是q的祖先，也不是q的后代［7］。

對于屬性a中任何給定的一個局部分割γ，其抽象屬性值域形成一個較低層次局部分割中屬性值的一個劃分，也給出屬性a的所有初始值的一個劃分。局部分割將一個屬性a的不同初始值抽象到不同層次，形成該屬性在其概念層次A VT（a）上不同層次的值域［12］。

1.6 屬性泛化約簡

屬性約簡可有效降低單尺度數(shù)據(jù)的維度，但其只能減少屬性的數(shù)量，不適用于具有層次結(jié)構(gòu)的屬性。

屬性泛化可以利用屬性值分類法（AVTs）將原始屬性的屬性值轉(zhuǎn)換為更粗的粒度。具體來講，即在AVT中查找一個局部分割，使得在用這個分割所包含屬性域來代替原始數(shù)據(jù)屬性域后，數(shù)據(jù)集所包含的信息量并未改變。以信息量不變?yōu)榍疤幔贏VT中查找盡可能粗的分割，就可以使數(shù)據(jù)集在分類能力不變?nèi)醯耐瑫r，屬性泛化程度最大化。如基于香農(nóng)熵提出了一種屬性泛化約簡算法AGRSCE［7］。

2 VDM-AVT學(xué)習(xí)器及其評估

2.1 VDM-AVT學(xué)習(xí)器實現(xiàn)方法

VDM-AVT學(xué)習(xí)器對決策表的每個條件屬性分別構(gòu)造AVT，最后得到一個由各個條件屬性樹形層次結(jié)構(gòu)組成的AVT集合。單個屬性AVT的構(gòu)建可以看作是一個層次聚類過程，層次聚類的實現(xiàn)可分為“自底向上”和“自頂向下”兩種方案，由于VDMAVT學(xué)習(xí)器所研究的決策表一般是給出屬性的初始屬性值，也即屬性值分類的葉子節(jié)點，AVT的其它內(nèi)部節(jié)點均為未知，因此選擇“自底向上”方案作為VDM-AVT學(xué)習(xí)器構(gòu)造AVT的方法。VDM-AVT學(xué)習(xí)器在構(gòu)造單個條件屬性AVT時，先將該條件屬性的原始值域中的元素作為葉子節(jié)點，然后分別計算各個葉子節(jié)點兩兩間的VDM距離，得出各葉子節(jié)點的概率分布，VDM距離越小，表明對應(yīng)的兩個葉子節(jié)點的概率分布越相似，即對應(yīng)葉子節(jié)點的相似性越大，因此將所有葉子節(jié)點中VDM距離最小的兩個抽象為一個內(nèi)部節(jié)點，這個內(nèi)部節(jié)點是所抽象節(jié)點的父節(jié)點，再在新的節(jié)點集合中找出VDM距離最小的兩個節(jié)點抽象為一個新的內(nèi)部節(jié)點，重復(fù)此步驟直到所有葉子節(jié)點被抽象到只剩一個節(jié)點，此節(jié)點即為AVT的根節(jié)點，由此得出該條件屬性的樹形層次結(jié)構(gòu)。具體構(gòu)造過程見VDM-AVT學(xué)習(xí)器實現(xiàn)算法。

VDM-AVT學(xué)習(xí)器實現(xiàn)算法：

Step 1輸入：決策表S＝（U，C∪D，V，f），其中，C為條件屬性集，D為決策屬性集；

Step 2遍歷所有條件屬性，并對當(dāng)前遍歷到的屬性A i做Step 3至Step 8處理；

Step 3計算該屬性下各類屬性值相互間的VDM距離，選取VDM距離最小的一對屬性值和

Step 4將合并為新的屬性值的父節(jié)點；

Step 5更新數(shù)據(jù)，將對應(yīng)對象在A i屬性的值改為，方便后續(xù)VDM計算；

Step 6更新Ai屬性值種類，刪除，并添加

Step 7如果此時Ai的屬性值種類數(shù)量不為1，從Step 3開始繼續(xù)運行，否則運行Step 8；

Step 8得到Ai屬性的AVT層次樹T i；

Step 9輸出：T＝｛T1，T2，...，T n｝。

2.2 VDM-AVT學(xué)習(xí)器的評估

VDM-AVT學(xué)習(xí)器的功能僅僅是構(gòu)造出數(shù)據(jù)的樹形層次結(jié)構(gòu)，很難直接去評估所構(gòu)建層次結(jié)構(gòu)的好壞，但如果將AVT用于數(shù)據(jù)的泛化約簡，所構(gòu)造的AVT會直接影響泛化約簡的結(jié)果，泛化約簡結(jié)果的好壞也就反映了所構(gòu)建AVT的有效性。也即如果AVT構(gòu)造不合理，泛化約簡的結(jié)果也很可能不合理，甚至導(dǎo)致出現(xiàn)數(shù)據(jù)不存在泛化約簡的情況，用分類器對這樣的泛化約簡處理后的數(shù)據(jù)進(jìn)行分類和規(guī)則提取，得出的分類準(zhǔn)確率與用原始數(shù)據(jù)分類得到的分類結(jié)果相比是更低的，所提取的規(guī)則與從原始數(shù)據(jù)提取的規(guī)則相比也會更不合理或者所提取規(guī)則的數(shù)量不會減少；相反如果AVT構(gòu)造合理，基于此進(jìn)行泛化約簡后的數(shù)據(jù)的分類性能相比原始數(shù)據(jù)會更好，所提取規(guī)則也具有更好的泛化性，具體量化表現(xiàn)為所提取規(guī)則的數(shù)量更少。為了評估VDM-AVT學(xué)習(xí)器的有效性，將VDM-AVT學(xué)習(xí)器所構(gòu)建的AVT應(yīng)用到泛化約簡中，基于此提出VDM-AVTAGR模型。

AGR代表屬性泛化約簡，相關(guān)研究已有很多，AGR-SCE算法對數(shù)據(jù)集進(jìn)行泛化約簡，并用仿真實驗驗證了算法效果，證明了AGR-SCE算法可以實現(xiàn)數(shù)據(jù)條件屬性的泛化約簡，AVT是基于相關(guān)領(lǐng)域知識構(gòu)造的，具有主觀性，且普適性不強［7］。VDM-AVT-AGR模型將AGR-SCE算法中的AVT改為利用VDM-AVT學(xué)習(xí)器構(gòu)造，使得算法可以應(yīng)用于各種數(shù)據(jù)集而不需要學(xué)習(xí)相關(guān)領(lǐng)域知識。

3 實 驗

通過對比利用VDM-AVT-AGR模型處理后的數(shù)據(jù)和原始數(shù)據(jù)的分類性能和所能提取的規(guī)則數(shù)，來驗證VDM-AVT-AGR模型的有效性，進(jìn)而證實VDM-AVT學(xué)習(xí)器的有效性。

從機器學(xué)習(xí)UCI數(shù)據(jù)庫中選取了4個數(shù)據(jù)集進(jìn)行研究，數(shù)據(jù)集中的非離散屬性利用spss的分箱功能做離散化處理，數(shù)據(jù)集中包含缺失值的對象做刪除處理。利用VDM-AVT-AGR模型對預(yù)處理后的數(shù)據(jù)集進(jìn)行泛化約簡得出泛化約簡后的數(shù)據(jù)AGRD（Attribute-generalization reduced data）。表1～表4描述了將各數(shù)據(jù)輸入VDM-AVT學(xué)習(xí)器后，利用各數(shù)據(jù)集生成的每個屬性的AVT層次深度。

表1 Breast Cancer Wisconsin（Original）屬性描述Tab.1 Description of the attribute of Breast Cancer Wisconsin（Original）

表2 Car Evaluation屬性描述Tab.2 Description of the attribute of Car Evaluation

表3 Iris屬性描述Tab.3 Description of the attribute of Iris

表4 Wine屬性描述Tab.4 Description of the attribute of Wine

實驗中，利用Weka軟件，使用其中6種分類模型構(gòu)建方法分別對各個數(shù)據(jù)集的AGRD和原始數(shù)據(jù)集OD（the Original Data）進(jìn)行分類，6種模型分別是：樸素貝葉斯分類器（NB）、增強算法（AB）、兩種決策樹（J48和NBT）和兩種基于規(guī)則的分類器（PART和Prism），所有分類器都使用Weka默認(rèn)參數(shù)進(jìn)行訓(xùn)練。最后通過十字交叉驗證，即將實驗數(shù)據(jù)隨機分成10組，依次將其中的9組作為訓(xùn)練集，剩余的1組作為測試集，最后將10次實驗結(jié)果的均值作為最終的驗證結(jié)果，獲得分類精度。同時利用J48、NBT、PART、Prism4種模型得出所提取的規(guī)則數(shù)目。

分類準(zhǔn)確率反映了正確分類的實例數(shù)量占總實例數(shù)量的百分比，準(zhǔn)確率越大分類性能越好。圖2描述了各數(shù)據(jù)集在幾種分類器下AGRD和OD的分類準(zhǔn)確率比較，從中可以得出，AGRD的分類性能是高于OD的。

規(guī)則數(shù)量決定了模型的復(fù)雜度，圖3描述了各數(shù)據(jù)集分別在幾種模型下可提取出的規(guī)則數(shù)量，可以看出從AGRD中提取的規(guī)則數(shù)量總體上明顯少于OD，同時AGRD的分類性能更好，因此其提取的規(guī)則可靠性也更大。

通過以上實驗分析，可以看出將VDM-AVTAGR模型用于層次泛化約簡可以有效提高數(shù)據(jù)分類性能，可以使數(shù)據(jù)在屬性數(shù)量和屬性值數(shù)量方面都變得更加簡潔，從而實現(xiàn)更好的分類性能，提取出更可靠的分類規(guī)則。

圖2 AGRD與OD分類準(zhǔn)確率對比Fig.2 Comparison of classification accuracy between AGRD and OD

圖3 AGRD與OD提取規(guī)則數(shù)對比Fig.3 Comparison of extraction rule number between AGRD and OD

4 結(jié)束語

現(xiàn)實世界中屬性值分類是普遍存在的，其在層次決策規(guī)則獲取中具有重要作用。利用VDM-AVT學(xué)習(xí)器處理數(shù)據(jù)可以生成AVT集合，將其用于泛化約簡的VDM-AVT-AGR模型可以有效提高決策表的分類性能，可以使數(shù)據(jù)在屬性數(shù)量和屬性值數(shù)量方面都變得更加簡潔，相比利用原始數(shù)據(jù)提取的規(guī)則，利用泛化約簡后提取的規(guī)則復(fù)雜程度更低、規(guī)則數(shù)量更少，同時規(guī)則支持度更高，進(jìn)而說明VDMAVT學(xué)習(xí)器是有效的。