基于粒度計算的數據分類建模研究

摘 要：基于粒度計算在理論上對數據分類問題進行建模研究。引入全粒度空間的概念，給出了集合的粒度表示、概念學習在粒度計算理論中的解釋，從而得到數據分類問題的機理分析；最后導出了基于數據分類的知識發現模型，為知識發現面臨的問題提供解決的理論依據，也為進一步研究奠定了重要的理論基礎。

關鍵詞：數據分類； 粒度計算； 數據庫中的知識發現； 建模

中圖分類號：TP311.13文獻標志碼：A

文章編號：1001-3695(2007)03-0037-04

0 引言

粒度計算是信息處理的一種新的概念和計算范式，它覆蓋了所有有關粒度的理論、方法、技術和工具的研究[1]，現已成為人工智能領域研究的熱點之一。這種計算理論符合人類解決問題的智力思維特征。人類正是采用這種由粗到細不斷求精的多粒度分析法避免了計算復雜度高的困難，使得原來看似非多項式難解的問題迎刃而解[2]。

目前，研究得較多且較成熟的一種粒度計算理論是商空間理論 [3]。在該模型中，用三元組(X， f，T)來描述一個問題。其中X是論域； f：X→Y表示論域上元素的屬性；Y可以是n維空間，也可以是一般的集合；T是論域的結構，它表示論域中各元素之間的關系，將論域中的子集當做新的元素（粒度）進行研究。用數學術語來講，就是先對X進行劃分而得到商集[X]后，再對[X]進行研究。該計算理論的優點是，它使得對問題的解決擺脫了一些煩瑣而非關鍵的過程，抓住問題的本質，以便從適當的層次（粒度）來研究問題的解，從而可以快速獲得問題的精確解或近似解。

知識發現研究領域中尚存在許多理論問題有待解決 [4，5]。粒度計算為其中某些問題的解決提供了一種新的途徑。知識發現的過程實際上就是粒度計算的過程，知識的形成過程本質上是在知識空間中搜索信息粒度的過程。不同領域的應用在期待著從歷史數據中得到自己的答案，將信息粒度（的語義）變為知識。然而，不同的應用目的對信息粒度的層次和大小有不同的需求，其解釋（語義）也因此存在差異。例如，在數據挖掘中對數據倉庫處理時提出分層（Hie￣rarchy）概念，從不同的粒度中得到不同層次的信息和知識，以滿足人們對不同層次知識的要求[6]，即發現用戶真正感興趣的知識。更重要的是，粒度計算可以在不同層次粒度的研究中提供深入的數學分析理論，是研究不同粒度世界的一種新型的數學工具，具有完備的理論基礎。

數據分類（Data Classification）是數據挖掘的一個重要任務。它可以分為兩個過程：①根據給定的樣本數據集或概念集（在粒度計算中通常又稱為信息系統、決策系統等），用設計的算法創建一個模型；②使用模型進行分類、預測等。顯然，后一過程屬于應用，關鍵是前一過程，即算法的設計。當前的研究主要集中于算法的效率和準確率，但對此并未取得根本性的突破，而更多的是針對算法的技巧性改進，不具一般指導意義。本文的研究是希望從知識發現的代數和幾何理論體系中去探討，尋求對問題解決的一般性原則。本文主要是基于粒度計算的有關理論和方法對數據分類問題進行建模，為進一步研究奠定重要的理論基礎。

1 基本概念

在信息系統〈U， A〉中，利用信息函數f_a在論域U上構造一個關于屬性集B_A的關系R_B，定義為

易知，U上的任一等價關系均可以形成U的相應等價劃分。把等價關系B形成的等價劃分記為P_B，或記為商集的形式U/B。

本文主要是研究基于數據分類的知識發現，從全局的高度對知識所在的空間進行分析，以找出獨立于具體算法的一般性規律。所以，與本文中提到的信息系統對應的論域U是指實際系統在其生命周期內所有可能的全部數據的集合，也稱為問題全域。

2 集合的粒度表示及概念學習

2.1 集合的粒度表示

如果信息系統〈U， A〉的所有基本元都是一元基本元，那么對任意XU，X均可精確粒度表示。因為對任意s∈X，{s}都是粒度，從而∪_s∈X{s}是X的極小精確粒度表示。但是，這些粒度的支持度都是1/|U|，為最小值。一般地，采用基本元來構造一個集合的精確粒度表示，這在實際應用中是沒有意義的。實際上，在精確粒度表示中，粒度的支持度越大越好，這會使粒度表示更具一般性和適應性。但是對于大粒度，相應的表示可能無法保證精確，這也是粒度產生的原因之一。因此，需要考慮集合近似的極小粒度表示，這往往更具實際應用價值。

通常，X的精確粒度表示是難以建立的，而建立其近似粒度表示往往就顯得較為實際，即在可接收的誤差范圍內以近似粒度表示的描述作為X的描述。

2.2 概念學習

概念包括內涵和外延，如果知道一個未知概念的外延X的粒度表示，那么由定理2就可以得到該概念的內涵DES(X)，從而形成對該未知概念的一個完整認識——（DES(X)， X）。很多情況下，把一個外延為X的未知概念稱為目標概念X。實際上，作為理論分析，本文考慮的是問題全域，上述的X是代表目標概念在問題全域U中的實際外延。而在實際應用中，能觀察得到的只是未知概念的部分外延，即得到X的一個可能的子集（一些對象的集合，這些對象可能還含有誤差，所以有些對象并不屬于X）。訓練集就是直接由該子集來構造，或是基于該子集間接構造起來的（通過數據預處理等）。為便于討論，在此可直接認同該子集為訓練集，記為U_train，問題全域U、目標概念的外延X和訓練集U_train的關系即可用圖1來表示。那么，概念學習的過程就是先通過利用訓練集U_train所包含的信息逐步建立X的近似粒度表示，然后以粒度描述的析取式作為目標概念的內涵。但是對于不同的學習算法，建立近似粒度表示的方法也不一樣。例如，決策樹方法是從大的粒度開始，依據訓練集提供的信息逐步切分，直到形成可接受的粒度表示；對于超樹而言，這種方法則是從上到下進行粒度搜索的過程，當然，也可以從下往上搜索。對于圖1所示的情況，通過訓練集建立起來的X粒度表示的示意圖如圖2所示。

由上述分析可知，概念學習可以歸結為：由給定的對象（實例）集構成訓練集，由訓練集建立目標概念的描述。在具體算法設計時，其任務是從已有的訓練集通過粒度搜索等方法逐步逼近目標概念的外延，最終形成外延的近似粒度表示，而粒度的內涵（描述）是已知的，由定理2可得到目標概念的內涵，完成概念學習過程。所以，目標概念X的學習可以轉換為基于全粒度空間的粒度計算問題，即在全粒度空間中尋找若干個粒度以形成X的精確粒度表示。粒度越大，則其描述的支持度越高，形成的知識或規則集越簡單，可理解性就越強，所以對發現的知識，總是希望其描述長度盡可能小，即最小長度原理。但是粒度越大則越易造成粒度越界，導致目標概念無法用粒度精確表示。所以粒度精確表示和描述長度、支持度等往往是矛盾的，實際操作時只能在誤差允許的范圍內采用近似粒度表示，并以近似粒度表示的描述作為目標概念的描述，從而達到概念學習的目的。這種近似粒度表示的建立過程就是一種基于粒度計算的優化過程。

3 基于數據分類的知識發現模型

從機器學習的角度來看，數據分類是一種特殊的多目標概念學習。但它不是單目標概念學習的簡單疊加，而是在每個目標概念的學習過程中彼此相互影響、相互關聯的。其特點是，每一個目標概念（實際上是目標概念的外延）之間不相交，而且它們的并等于問題全域U。

決策系統是分類模型中通常采用的信息表達方式。實際上，決策系統也可看作是由信息系統〈U， A〉和信息系統〈U， D〉組成的?！碪， D〉中的概念是目標概念，那么分類模型中的知識發現的任務就是尋找〈U， A〉中的概念到〈U， D〉中的概念之間關聯的一般性描述，而且這些描述對用戶來說是有趣的。這兩個不同系統中的概念是通過它們的外延得以關聯，因此一般都是通過發現兩個概念的外延包含關系來找出其內涵的關聯，并建立這種關聯的描述，將其作為知識向用戶提供。在分類模型中，〈U， D〉中的概念是固定的（這些概念的內涵最后形成規則的后件），知識發現的具體任務就是從〈U， A〉中尋找與這些固定概念有關聯的概念，最后這些概念的內涵（公式）的析取式就形成了規則的前件。如果〈U， D〉中的概念不固定，則屬于依賴模型中的知識發現問題；如果A和D是動態改變的，則屬于關聯模型中的知識發現問題，如關聯規則的發現。（不過這些已超出了本文的研究范圍）

D可包含多個屬性，但是為便于敘述，且又不失一般性，假設D只包含一個屬性d，即D=g0gggggg（因為多個決策屬性可以轉換為單個決策屬性來研究）。這樣，U/D中的任一個集合（等價類）都具有(d， v)形式的描述公式，其中v∈V_d。對任意X∈U/D={X₁， X₂， …， X_g}（g=|U/D|），為避免與信息系統〈U，A〉中的描述相混淆，可將X的描述記為DES_D(X)。

對實際應用系統進行觀察而得到的訓練集只是X₁∪X₂∪…∪X_g的部分數據（有一些甚至不是，因為可能含受污染數據）。KDD算法的作用就是通過設計的方法產生各X_i（i=1， 2， …，g ）的近似粒度表示，然后由這些粒度的描述產生各X_i在〈U， A〉系統中的描述，最后由這些描述以及各X_i在〈U， D〉系統中的描述即可得到兩個不同概念之間的關聯描述，即知識。這個過程如圖3所示。

雖然KDD算法采用的方法一般是不一樣的，但是對于數據級操作而言，對不同的KDD算法，其目的都是一樣的，即本質上都是形成各目標概念的近似粒度表示，都可以利用超樹及其性質得到解釋。例如，決策樹方法是利用訓練集提供的信息，從大的粒度開始，以屬性的信息增益(Information Gain)作為啟發信息，沿超樹自頂向下地搜索，當某一目標概念形成可接受的近似粒度表示時，面向該目標概念的搜索停止；當所有的目標概念都形成可接受的近似粒度表示時，算法停止。啟發信息的作用是引導算法搜索的走向（即當有很多條路可走，確定應該選擇哪一條），啟發函數的設計是根據具體應用而定的。

該定義是一種理想情況。從上述討論看，很難保證構成X粒度表示的粒度G均滿足GX。實際情況是，X的粒度表示對應的極小粒度集MGSet（見定義3）中存在很多粒度G，使得G-X≠ 。所以，針對實際應用，對基本規則的定義作一定的修改，即得到定義9′。

這樣，可以把基于分類模型的知識發現問題轉換為一種優化問題，得到如下的優化模型：

模型中應保證知識的全局性、適應性和簡潔性，減少冗余信息；還應保證知識的一致性。

由此可見，知識發現在本質上可歸結為在全粒度空間中尋找各目標概念的最佳粒度表示，而各粒度描述的析取即構成了決策規則的前件。

該模型基本上把分類問題的主要特征勾畫出來了，在應用中可根據具體的問題對其進行有效的拓展。 

4 結束語

數據分類是知識發現的一個重要任務之一。目前的研究主要集中于算法效率，而對如何發現用戶真正感興趣的知識則探討得較少。本文利用粒度計算的有關理論和方法，在理論上對數據分類問題進行建模與分析。為此，論述了集合的粒度表示、概念學習在粒度計算理論中的解釋，最后導出基于數據分類的知識發現模型，為知識發現面臨的一些問題提供解決的理論基礎。今后將基于這些工作進一步研究個性化知識發現的理論體系，尋找知識發現的一般理論指導方法。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。