錢卓昊

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

0 引 言

現(xiàn)實(shí)生活中，屬性值分類（AVT）又稱層次屬性值（Hierarchical Attribute Value），是廣泛存在的，如時(shí)間屬性上日、月、季、年等具有層次特征的屬性值［1］。可以利用概念層次將原始基礎(chǔ)數(shù)據(jù)抽象到不同層次，實(shí)現(xiàn)數(shù)據(jù)泛化。同時(shí)，基于多層次（Multiple Levels）數(shù)據(jù)挖掘，可能會(huì)從較高層次數(shù)據(jù)中發(fā)現(xiàn)更普遍或更重要的知識(shí)，且獲取的規(guī)則也更易于理解［2］。數(shù)據(jù)集中AVT樹型結(jié)構(gòu)可由相關(guān)領(lǐng)域?qū)＜姨峁?，也可根?jù)訓(xùn)練集自動(dòng)構(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的有效性已被證明，但針對(duì)構(gòu)建AVT的研究還比較少。涉及AVT時(shí)，大多是基于相關(guān)專家意見所構(gòu)建的AVT，這使得AVT具有主觀成分，且在研究高維度數(shù)據(jù)時(shí)其準(zhǔn)確度降低。在已有的從數(shù)據(jù)中構(gòu)建AVT研究中，都是將AVT直接與分類模型綜合在一起來處理數(shù)據(jù)，而沒有進(jìn)行屬性泛化約簡，這使得處理后的數(shù)據(jù)依舊可以進(jìn)一步泛化。如AVT-NBL模型，在構(gòu)建AVT時(shí)如何度量屬性值間的相似關(guān)系目前也沒有最佳標(biāo)準(zhǔn)，用JS散度來度量［1］。為了研究AVT在離散屬性中的應(yīng)用，本文采用VDM距離來度量。

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

1 基本概念

1.1 決策表

決策表（也可稱為決策信息系統(tǒng)）是一個(gè)四元組S＝（U，C∪D，V，f），其中U是非空有限對(duì)象集，稱為論域；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é)點(diǎn)相當(dāng)于屬性a在原始數(shù)據(jù)中的初始屬性值。內(nèi)部節(jié)點(diǎn)代表其相應(yīng)子節(jié)點(diǎn)的泛化屬性值，樹上的每段弧代表了相鄰且不同層次屬性值之間的粗化或細(xì)化關(guān)系。令L ea f（a）代表AV T（a）的葉節(jié)點(diǎn)，Ro ot（a）代表其根節(jié)點(diǎn)，Node（a）代表A V T（a）的所有節(jié)點(diǎn)，內(nèi)部節(jié)點(diǎn)（除葉節(jié)點(diǎn)以外的節(jié)點(diǎn)）相當(dāng)于屬性a的泛化值。C h i l d（v，a）是屬性值v在A V T（a）中的所有子節(jié)點(diǎn)集合，De pt h（a）是A V T（a）中從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的最大路徑長度。如圖1為本文利用VDM-AVT學(xué)習(xí)器處理UCI數(shù)據(jù)集Car Evaluation的maint屬性得到的A V T（mai n t）。

其中：

1.3 層次聚類

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

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

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

1.4 VDM（Value Difference Metric）

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

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

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

1.5 局部分割

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

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

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

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

1.6 屬性泛化約簡

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí) 驗(yàn)

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

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

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

分類準(zhǔn)確率反映了正確分類的實(shí)例數(shù)量占總實(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，同時(shí)AGRD的分類性能更好，因此其提取的規(guī)則可靠性也更大。

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

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

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

4 結(jié)束語

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