數據驅動的屬性值分類法及其在屬性泛化中的應用

錢卓昊

（西安石油大學 計算機學院，西安710065）

0 引 言

現實生活中，屬性值分類（AVT）又稱層次屬性值（Hierarchical Attribute Value），是廣泛存在的，如時間屬性上日、月、季、年等具有層次特征的屬性值［1］。可以利用概念層次將原始基礎數據抽象到不同層次，實現數據泛化。同時，基于多層次（Multiple Levels）數據挖掘，可能會從較高層次數據中發現更普遍或更重要的知識，且獲取的規則也更易于理解［2］。數據集中AVT樹型結構可由相關領域專家提供，也可根據訓練集自動構建而成。

具有層次結構的數據已被廣泛應用，Han等提出了一種利用概念分類法和自頂向下遞進深化方法在不同層次上尋找概念之間的關聯規則的算法XLT2L1［3］；如Hong等基于粗糙集理論提出一種獲取跨層次確定性規則和可能性規則的方法［4］；研究了具有層次結構的模糊粗糙集［5］；Feng等利用層次結構提出一種自上向下的挖掘層次決策規則的方法［6］。

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

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

1 基本概念

1.1 決策表

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

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

VDM-AVT學習器所構建的AVT中，Va是包含屬性a的所有初始值的有限集，屬性a的屬性值分類A V T（a）是基于Va內元素間的相似性構建的一種樹形概念層次結構。

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

其中：

1.3 層次聚類

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

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

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

1.4 VDM（Value Difference Metric）

現實生活中存在許多類似交通工具（火車，汽車）這樣的無序屬性，本文主要針對這類型數據進行研究，VDM距離在處理離散屬性時的有效性已經被廣泛驗證，比如Zhang等在處理異構數據的離散部分時使用VDM距離度量數據相似程度［11］。本文亦選擇將VDM作為層次聚類的距離定義。

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

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

1.5 局部分割

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

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

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

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

1.6 屬性泛化約簡

屬性約簡可有效降低單尺度數據的維度，但其只能減少屬性的數量，不適用于具有層次結構的屬性。

屬性泛化可以利用屬性值分類法（AVTs）將原始屬性的屬性值轉換為更粗的粒度。具體來講，即在AVT中查找一個局部分割，使得在用這個分割所包含屬性域來代替原始數據屬性域后，數據集所包含的信息量并未改變。以信息量不變為前提，在AVT中查找盡可能粗的分割，就可以使數據集在分類能力不變弱的同時，屬性泛化程度最大化。如基于香農熵提出了一種屬性泛化約簡算法AGRSCE［7］。

2 VDM-AVT學習器及其評估

2.1 VDM-AVT學習器實現方法

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

VDM-AVT學習器實現算法：

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

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

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

Step 4將合并為新的屬性值的父節點；

Step 5更新數據，將對應對象在A i屬性的值改為，方便后續VDM計算；

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

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

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

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

2.2 VDM-AVT學習器的評估

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

AGR代表屬性泛化約簡，相關研究已有很多，AGR-SCE算法對數據集進行泛化約簡，并用仿真實驗驗證了算法效果，證明了AGR-SCE算法可以實現數據條件屬性的泛化約簡，AVT是基于相關領域知識構造的，具有主觀性，且普適性不強［7］。VDM-AVT-AGR模型將AGR-SCE算法中的AVT改為利用VDM-AVT學習器構造，使得算法可以應用于各種數據集而不需要學習相關領域知識。

3 實 驗

通過對比利用VDM-AVT-AGR模型處理后的數據和原始數據的分類性能和所能提取的規則數，來驗證VDM-AVT-AGR模型的有效性，進而證實VDM-AVT學習器的有效性。

從機器學習UCI數據庫中選取了4個數據集進行研究，數據集中的非離散屬性利用spss的分箱功能做離散化處理，數據集中包含缺失值的對象做刪除處理。利用VDM-AVT-AGR模型對預處理后的數據集進行泛化約簡得出泛化約簡后的數據AGRD（Attribute-generalization reduced data）。表1～表4描述了將各數據輸入VDM-AVT學習器后，利用各數據集生成的每個屬性的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種分類模型構建方法分別對各個數據集的AGRD和原始數據集OD（the Original Data）進行分類，6種模型分別是：樸素貝葉斯分類器（NB）、增強算法（AB）、兩種決策樹（J48和NBT）和兩種基于規則的分類器（PART和Prism），所有分類器都使用Weka默認參數進行訓練。最后通過十字交叉驗證，即將實驗數據隨機分成10組，依次將其中的9組作為訓練集，剩余的1組作為測試集，最后將10次實驗結果的均值作為最終的驗證結果，獲得分類精度。同時利用J48、NBT、PART、Prism4種模型得出所提取的規則數目。

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

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

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

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

圖3 AGRD與OD提取規則數對比Fig.3 Comparison of extraction rule number between AGRD and OD

4 結束語

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