運用自適應粒化模型的一種數據分類方法

蒙祖強,沈亮亮,甘秋玲,覃 華

(廣西大學 計算機與電子信息學院,南寧 530004)

1 引 言

數據分類是一種重要的數據分析技術[1-4].在大數據時代,數據的復雜性和異構性呈多元化、多樣化趨勢,一般難以事先從數據中獲取面向特定應用的先驗知識.對數據分類而言,由于缺乏先驗知識,往往需要不斷調試算法的有關參數來提高分類性能,而這種調試過程大多是經驗性和探試性的,缺乏有效的指導理論,從而極大地降低了分類方法的應用價值和應用范圍.因此,構造自適應于復雜數據環境而無需先驗知識、具有較高分類準確率的數據分類算法是數據分類研究領域中追求的目標之一[5].在構造自適應數據分類方法研究方面,學者們做了大量的工作.文獻[6]研究了最大散度差分類算法的識別率隨參數C變化特征,提出了基于最大散度差鑒別準則的自適應分類算法,該算法可以根據訓練樣本的類內散布矩陣特性自動選擇恰當的參數C.文獻[7]提出一種自適應的支持向量機分類算法,其優點在于它可以在局部與全局之間保持較好的平衡性,從而在一定條件下提高分類準確率,但它缺乏考慮訓練樣本之間的關系,其適應性受到限制[8].文獻[8]則針對漸變概念漂移的分類問題提出一種自適應近鄰投影均值差支持向量機算法,該算法在全局優化中融入數據自身的分布特征,從而提高算法的自適應性.文獻[9]亦針對漸變概念漂移的分類問題進行了研究,但其重點研究的是針對概念漂移數據流的一種自適應分類算法.文獻[10]針對可拒絕一類分類問題,提出基于最小生成樹的多分辨率覆蓋模型,實現了在多分辨尺度下對數據流形的自適應緊致覆蓋.文獻[11]針對kNN分類算法選擇參數k難的問題,將k值引入到目標函數設定中,通過計算屬于每一類的損失函數值來選擇擁有最小函數值的類作為測試樣本的類別,從而提出自適應大間隔近鄰分類算法.文獻[1]通過構造與不同數據集自動相適應的規則評價函數來提高分類準確性,從而提出一種自適應蟻群分類算法.透過這些研究成果可以發現,在自適應數據分類研究方面,目前大多數研究工作主要是面向特定問題對分類算法中某些重要參數的設置和選擇進行自適應優化,但在研究自適應于數據集的自適應分類算法方面,相關工作還很少,特別是在利用數據之間存在的關系(如相容關系)來構造自適應分類算法方面的研究,相關工作還很缺乏.

所謂數值數據間的相容關系,是指數值型屬性中基于近似相等關系而形成的屬性值之間的一種關系,它滿足自反性和對稱性,因而是相容關系.現有的方法往往“割裂”這種相容關系而未能加以利用,如流行的離散化方法、C4.5中對數值數據的“二分法”等方法都采用類似的處理方式.另外,現有分類算法一般都涉及到許多參數,這些參數的設置和優化尚無有效的指導理論,多憑經驗來選擇[12,13],受主觀因素影響較大,導致現有許多分類方法在不同數據集上表現出來的分類性能差別很大,即它們受到數據集的影響很大[14].因此,如何構造針對數據集的、實現完全數據驅動的自適應分類方法是現今復雜數據環境下數據分析研究面臨的一個重要任務.

本文基于屬性-值對塊(attribute-value block)技術,通過利用數值數據之間的相容關系和數據對象的粒化方法構建數據的自適應粒化模型,然后基于該模型設計面向數據的、完全由數據驅動的自適應分類算法.

2 相容關系下的屬性-值對塊及其性質

屬性-值對塊(attribute-value pair block)是美國著名學者Grzymala-Busse教授提出的用于處理不完備信息的一種數據分析技術[15,16].本節先介紹屬性-值對塊的概念及有關性質,在下一節中將用這種技術來對數值數據進行建模,進而構造自適應粒化模型和數據分類方法.

對給定的訓練集T,其對應的數據模型表示為(U,A=C∪D),不妨記為T=(U,A=C∪D),其中U表示訓練集中數據對象的集合,A是所有數據屬性的集合,C和D分別稱為條件屬性集和決策屬性集,且C∩D=?;對a∈C,用Va表示屬性a的值域.不失一般性,假設D=g0gggggg,即假設決策屬性集D僅由一個屬性d組成.對任意x∈U和a∈C,用函數fa(x)表示對象x在屬性a上的取值,f稱為信息函數.對v∈Va,(a,v)便是決策邏輯語言[17]中的一個原子公式;令[(a,v)]={y∈U|fa(y)=fa(x)},其中v=fa(x),(a,v)稱為對象x的屬性-值對(attribute-value pair),[(a,v)]稱為對象x的關于屬性a和值v的屬性-值對塊(attribute-value pair block)[15].屬性-值對塊的特點是將一個概念的內涵(屬性-值對)和外延(塊)有機地結合起來,用于表示粒計算[18]中的基本積木塊,為問題的粒化提供方法支撐.可以看到,屬性-值對塊的物理意義和邏輯意義都很明顯.例如,屬性-值對塊[(a,fa(x))]表示所有與對象x在屬性a上取值相同的對象的集合,用屬性a是無法區分集合中的這些對象,因而它們構成了基本的積木塊,而(a,fa(x))是這個塊的一個描述,是解釋分類器的一個原子公式.

根據上面的定義,屬性-值對塊[(a,fa(x))]實際上就是關于等價關系Ra的一個等價類[x]a,其中Ra={|fa(y)=fa(x),x,y(U}.也就是說,這種定義是根據屬性值是否相等來構建的:如果兩個對象在屬性a上的取值相等,就將它們放在一個關于a的等價類里面.但在某些應用中,不能簡單地通過判斷它們的屬性值是否相等來決定它們是否屬于同一個類.例如,就數值數據而言,由于測量誤差、噪音等主客觀因素的影響,本來是相同的屬性值在獲取的數值上卻呈現出一定的差異.如果嚴格按照相等與否來判斷,我們就無法把它們歸為一類,這不符合實際情況.對此,我們可以采用近似相等的方法來判斷.不妨假設數據模型T中的每一列屬性值都已經歸一化,進而引入如下定義.

定義1.令δ為閉區間[0,1]中的一個小實數,對于兩個對象x,y∈U,稱對象x和y在屬性a上關于δ近似相等,記為x≈a,δy,如果|fa(y)-fa(x)| ≤δ.

這種近似相等關系≈a,δ實際上是一種相容關系,δ稱為相容半徑.

性質1.給定δ∈ [0,1],令Tol(a, δ)={|x≈a,δy,x,y∈U},則Tol(a,δ)滿足自反性和對稱性,因而是一種相容關系.

如果δ= 0,則這種相容關系就變為等價關系.

下面給出關于δ的相容關系下有關屬性-值對塊的概念.

定義2.在相容關系Tol(a,δ)下,令[(a,fa,δ(x))]={y(U|x≈a,(y},[(a,fa,δ(x))]稱為對象x的關于屬性a的屬性-值對塊,其中a∈C.

為了方便起見,[(a,fa,δ(x))]通常記為Ka,δ(x),即Ka,δ(x)=[(a,fa,δ(x))].如無特別說明,下文討論的屬性-值對塊都是在相容關系Tol(a,δ)意義下進行的.

為了方便起見,如果B僅由一個屬性組成,如B={a},則KB,δ(x)可寫為Ka,δ(x).

如果說Ka,δ(x)是原子積木塊,那么KB,δ(x)就是由Ka,δ(x)構成的復合積木塊.復合積木塊有一個重要的單調性質.

性質2.對任意B1,B2?C,如果B1?B2,則KB2,δ(x)?KB1,δ(x).

3 基于屬性-值對塊的自適應粒化模型

目前,自適應分類方法主要是針對算法中的一些重要參數進行自適應優化.實際上,在復雜數據環境下針對數據集的自適應優化同樣很重要.對于數值型數據,現有預處理方法和分類算法往往是人為“割裂”了數值數據之間本來蘊含的一些關系,或者說它們蘊含的關系不能很好地利用到算法當中、為提高分類性能提供幫助.例如,假設有一屬性a,其屬性值都已經歸一化:fa(1)=0.000,fa(2)=0.099,fa(3)=0.100,fa(4)=0.110,fa(5)=1.000.對此屬性,如果采用區間原理來離散化,可能得到如下的離散化結果:[0,0.1),[0.1,0.2),…,[0.9,1.0](這些區間是不相交的).這存在許多不合理的地方,例如,根據這種離散化結果,fa(2)和fa(3)被認為是不相等的,而fa(4)和fa(3)是相等的.但直覺告訴我們,fa(2)比fa(4)更接近fa(3);C4.5在分類過程中采用的“二分法”同樣有可能造成類似的問題,其根本原因在于離散化后或分裂后形成的區間是不相交的.實際上,一個屬性值應該允許它等于其“附近的”數(排序后),這在許多場合中更為合理.比如,fa(3)應該“等于”其附近的fa(2)和fa(4).這種思路是以數據對象為中心來考慮數據之間的關系,或者說,以對象為中心來考慮數據之間的“相等”問題能夠更好地利用數據之間本來蘊含的關系,這種關系就是數據之間的相容關系.本小結將對此進行形式化描述并探討更深層次的問題.

3.1 理論模型

以數據對象為中心的處理方法可以利用屬性-值對塊技術來實現.以屬性-值對塊替換對應的數據對象,于是得到一個新的粒化模型——基于屬性-值對塊的粒化模型(granulation model),記為GM=(Ka,δ(U),C∪D)a∈C,其中,Ka,δ(U)={Ka,δ(x) |x∈U}.Ka,δ(x)是這個模型中的基本積木塊.對任意y∈Ka,δ(x),fa(x)被認為與fa(y)相等.

這個模型與原來的數據模型T=(U,A=C∪D)相比,其基本數據積木塊由原來的數據對象變成了數據對象的屬性-值對塊.顯然,相容半徑δ決定著屬性-值對塊Ka,δ(x)的大小:δ越大則Ka,δ(x)越大,δ越小則Ka,δ(x)越小.當相容半徑δ等于0的時候,粒化模型GM就退化為原來的數據模型T.到底相容半徑δ取多大合適呢？這是本文討論的重點內容之一.為此,先引入相關的概念.

定義4.對給定的粒化模型GM=(Ka,δ(U),C∪D)a∈C,D=g0gggggg,如果存在x∈U,使得|fd(KC,δ(x))| > 1,則該粒化模型是不一致的,否則是一致的;相應地,令ρ(GM,δ)=|{x‖fd(KC,δ(x))|>1}|/|U|,ρ(GM,δ)稱為粒化模型GM的不一致程度,其中fd(KC,δ(x))表示塊KC,δ(x)在信息函數fd下的像.

也就是說,粒化模型GM是不一致的當且僅當ρ(GM,δ) > 0.

該定義的直觀意義是,|fd(KC,δ(x))| > 1就意味著塊KC,δ(x)至少跟兩個決策類相交,因而是不一致的.對數值系統來說,初始的數據模型一般都是一致的.如果相容半徑δ=0,粒化模型退化為原來的初始數據模型,都是一致的;如果δ逐漸增大,各個基本塊也逐步增大,從而ρ(GM,δ)逐漸變大,粒化模型也隨之逐步趨向不一致;當δ=1時,ρ(GM,δ)達到最大值1,粒化模型變得完全不一致,當然這種粒化模型沒有任何研究價值,一般不考慮.我們有下面的性質.

性質3.對給定的粒化模型GM=(Ka,δ(U),C∪D)a∈C,不一致程度ρ(GM,δ)會隨相容半徑δ呈非嚴格單調遞增.

證:對任意兩個相容半徑δ1,δ2([0,1],假設δ1<δ2,我們只需要證明ρ(GM,δ1)≤ρ(GM,δ2).

性質3說明,在區間[0,1]中必存在一點δ0,使得當δ<=δ0時,ρ(GM,δ)=0(粒化模型一致);當δ>δ0時,ρ(GM,δ)>0(粒化模型不一致).我們引入如下定義.

定義5.令δ0=max{δ∈[0,1]|ρ(GM,δ)=0},則δ0稱為粒化模型的一致臨界點.

對于給定的原始數據模型T=(U,A=C∪D),當構造其粒化模型時,最為關鍵的問題是如何選擇相容半徑？過大或過小的相容半徑都會導致不好的分類結果.在多次的實驗中我們發現,當相容半徑約等于一致臨界點的兩倍值時,分類準確率達到最大值或近似最大值.根據性質3,我們可以利用折半查找方法,完全依賴于數據之間的相容關系,快速找到粒化模型的一致臨界點,從而實現對相容半徑的自適應優化,這個優化過程是完全由數據驅動的,不需要任何先驗知識.假設δ0表示找到的一致臨界點,其二倍值2δ0記為δ″,即δ″=2δ0,則由此構造的粒化模型可以表示為(Ka,δ″(U),C∪D)a∈C,稱為自適應粒化模型(一種理論模型).

3.2 存儲模型

根據上述自適應粒化模型的理論描述,模型中每一個屬性值實際上一個屬性-值對塊.這樣,其存儲空間會就是原來訓練集規模的多倍,極大浪費存儲開銷,限制模型的實際應用范圍.因此,需要尋找一種有效的存儲結構.

在粒化模型(Ka,δ(U),C∪D)a∈C中,任意一屬性a∈C,數據間的關系Tol(a,δ)都是相容關系(性質1),于是可以引入下面的一些概念并導出有關性質.

定義6[19].在相容關系Tol(a,δ)下,對子集TC?U,如果對任意x,y∈TC,均有(Tol(a,δ),則稱TC為關于Tol(a,δ)的一個相容類;對任意子集TC′?U,如果TC?TC′,TC′都不是相容類,則稱TC為關于Tol(a,δ)的一個最大相容類.

性質4.在粒化模型GM=(Ka,δ(U),C∪D)a∈C中,Ka,δ(x)=∪MCa,δ[x],即Ka,δ(x)={y|y(TC,TC∈MCa,δ[x]},其中x∈U.

根據屬性-值對塊以及最大相容類的定義,我們不難證明此性質,具體證明過程在此省略.

性質4表明,屬性-值對塊的計算可以通過合并對應最大相容類來實現,而在數值條件下的最大相容類則可以通過先排序,然后一遍掃描數據集即可快速產生[20],其時間復雜度為O(|U|log|U|);對整個模型而言,建立最大相容類空間ψ(δ)的復雜度為O(|C‖U|log|U|).如果相容程度不是很高,ψ(δ)需要的存儲空間略大于O(|C‖U|);如果相容關系退化為等價關系,則其需要的存儲空間恰好是O(|C‖U|).

在建立了最大相容類空間ψ(δ)之后,再建立各最大相容類的索引結構,以便實現快速訪問.

定義8.對于給定的最大相容類空間ψ(δ),令loc(TC)表示最大相容類TC在ψ(δ)中的位置索引,令R(δ)={ga(x)|ga(x)={loc(TC)|TC(MCa,δ[x]},x(U,a∈C},ψ(δ)稱為ψ(δ)的位置索引結構.

最大相容類空間ψ(δ)及其位置索引結構ψ(δ)共同構成了粒化模型的存儲結構(模型),記為[Rψ(δ),ψ(δ)].

我們的目標是找到一致臨界點δ0.根據性質3,這個目標可以用折半查找的方法來實現.假設計算δ0的精度要求是λ∈(0,1),則最多需要找1/λ個點.而根據折半查找算法的復雜度,總共只需要進行log2(1/λ)次查找操作即可找到λ0(精度λ下的一致臨界點),從而形成自適應粒化模型(Ka,δ″(U),C∪D)a∈C的存儲結構[R(δ″),ψ(δ″)],其中δ″=2δ0.因此,建立[R(δ″),ψ(δ″)]的計算復雜度約為O(log2(1/λ)|C‖U|log|U|).例如,如果精度λ=0.01,則log2(1/λ)=log2100 ≈6.6 ≈ 7,即需要7次計算可找到δ0.如果精度λ要求不是很高時,O(log2(1/λ)|C‖U|log|U|)約等于O(|C‖U|log|U|).

4 基于自適應粒化模型的分類算法

在生成自適應粒化模型(Ka,δ″(U),C∪D)a∈C后,可以通過數據對象的約簡和對象規則的簡化來構造分類器.為此,先引入相關概念,然后分別討論這兩個過程.

任何一條基本規則都是通過刪除訓練集T中某一條數據對象的若干條件屬性(包括屬性值)后得到的,不妨稱為由該數據對象導出的基本規則.為方便,我們用r或r1,r2等來表示一條基本規則.任何一條基本規則實際上都是決策邏輯語言中的一條公式.對任意給定的公式φ,用set(φ)表示公式φ中出現的條件屬性的集合(不含決策屬性).例如,如果r=(a,0.11)∧(c,0.93) → (d,yes),則set(r)={a,c}.

顯然,一條有意義的規則必須滿足ant_cover(r)?(con_cover(r),這稱為規則的有效性;對于有效規則r,|ant_cover(r)|稱為規則r的有效覆蓋度.有效覆蓋度是一條規則所能覆蓋的數據對象的數目.

為獲得泛化能力強的規則,需要提高規則的支持度,這意味著要盡可能地刪除規則的條件屬性.這樣,隨著條件屬性的減少,ant_cover(r)逐步變大.但為保證有效性,規則必須滿足條件ant_cover(r)?con_cover(r).因此,對于給定的一條數據對象,保留哪些條件屬性來構造規則是一個關鍵問題,這就是數據對象的約簡問題.

定義11.對于基本規則r,令B=set(r),如果滿足下面兩個條件,則稱B是規則r的一個約簡:(1)ant_cover(r)?con_cover(r);(2)從規則r中刪除任何一個條件屬性,得到的新規則r′都不滿足ant_cover(r′)?con_cover(r′).

已有研究結果表明[20],尋找最優約簡是NP難問題.因此,本文不追求最佳的約簡,而是尋找近似約簡.主要思路是,對給定的數據對象(記錄),按照某一種既定順序對對象中的條件屬性進行逐一檢測:如果刪除某屬性后沒有破壞上述條件(1),則將之刪除,否則保留.雖然這種方法只是得到近似約簡,但其可操作性強,具有實際意義,已為許多工作所采用[12,13,21].

另外一個影響效率的問題是,在循環檢測過程中如何檢查是否滿足條件(1).直接用集合的方法會比較耗時.我們注意到,|con_cover(r)|=1,因此也有|ant_cover(r)|=1.利用這一點,可以加速對條件(1)的判斷.

對數據對象的約簡是逐一進行的,每一條數據對象都會導出一條基本規則.假設RuleSet是訓練集T=(U,A=C∪D)經過約簡后形成的規則集,則|RuleSet|=|U|,且RuleSet中的規則和U中的對象是一一對應的.但RuleSet中的規則會大量出現功能重復的情況.例如,可能會產生這樣的兩條后件一樣的有效規則r和r′:ant_cover(r′)?ant_cover(r).顯然,規則r在功能上完全能夠替代規則r′,因此規則r′是冗余的,應予以刪除.此外,我們還要保證訓練集中的每一條數據對象都必須存在能夠覆蓋它的規則.這樣,如何刪除這些功能上冗余的規則以及保留必要的規則(以覆蓋整個訓練集)是構造分類器的另一個關鍵問題.

一種途徑是利用有效覆蓋度來構造啟發信息.方法是,先計算RuleSet中每條規則r的有效覆蓋度,并按照有效覆蓋度對U中的數據對象進行降序排列,然后利用這個序列來選擇規則,最終構造分類器.這樣,結合上述的自適應粒化模型,我們可以給出一個完整的分類算法,算法描述如下:

分類算法的描述:

輸入:訓練集T=(U,A=C∪D)

輸出:分類器RS(由規則構成)

Begin

Step1. 建立自適應粒化模型(Ka,δ″(U),C∪D)a∈C及

存儲結構[R(δ″),ψ(δ″)];

Step2. 基于[R(δ″),ψ(δ″)],對U中的對象進行約簡,

設結果為RuleSet;

Step3. 對所有r∈RuleSet,計算ant_cover(r),同時

保存R[x],其中r為x導出的規則;

Step4. 據RuleSet中相應規則的覆蓋度,對U中對象

降序排序,設結果為U={x1,x2,…,xn};

Step5. 令RS=?;

Step6. 令i=1;

Step7. while(U≠?)

{

Step8. 令U=U-xi;

Step9. if?r1∈RS,r1?(R[xi]then

{

Step11. 令RS=RS∪{r0};

}

Step12.i++;

}

Step13. returnRS;

End

步驟1中,建立存儲結構[R(δ″),ψ(δ″)]的計算復雜度為O(log2(1/λ)|C‖U|log|U|),如果精度(比較大時(精度要求不高),O(log2(1/λ)|C‖U|log|U|)≈O(|C‖U|log|U|).此后,算法的計算都依賴于存儲結構[R(δ″),ψ(δ″)].

步驟2中,計算屬性-值對塊KB,δ″(x)的復雜度略大于O(|B|m),其中m為涉及的最大相容類規模的平均值.因此,計算所有數據對象的約簡的復雜度略大于O(|U‖C|m′),其中為m′所有最大相容類規模的平均值.

在步驟3中,假設RuleSet={r1,r2,…,rn},ri為對象xi導出的規則,則該步驟的計算復雜度為O(|set(r1)|m1+set(r2)|m2+…+|set(rn)|mn)<

步驟7-12為一個循環體,循環次數為|U|.循環體中,步驟10是在覆蓋規則集R[xi]中選擇一條覆蓋度最大的規則,R[xi]是在步驟3中已經形成的中間結果;耗時的是步驟9,它每次都需要判斷RS中每一條規則是否屬于R[xi].RS是在不斷增加的,|RS|在循環開始時為0,其后逐步增加,但最后也遠遠小于|U|.我們用RSi表示第i次循環時所形成的規則集,并假設c為各覆蓋規則集的規模的平均值,則循環體的計算復雜度為:O(|RS1|c+ |RS2|c+…+ |RS|U||c)=O((|RS1|+ |RS2|+…+ |RS|U||)c)<

綜合以上分析,決定算法效率的部分主要是步驟1、步驟2以及步驟7-12(循環體),它們的計算復雜度分別為O(|C‖U|log|U|)、O(|U‖C|m′)和O(|U‖RS|c).這三部分的復雜度表達式不一樣,我們難以直接從形式上去判斷它們的優劣,但從實驗中我們發現,步驟2是最耗時的,因此O(|U‖C|m′)代表了算法的復雜度,其中為m′所有最大相容類規模的平均值.

5 實驗分析

為驗證所提出算法的有效性,本文以C++為開發語言,在CPU為Intel(R) Core(TM) i7-4510U CPU @ 2.00GHz,內存8GB,以Win7為操作系統的計算機上,從多角度對算法的性能進行了驗證和對比分析.實驗方法采用十折交叉驗證,實驗用到的數據是來自機器學習研究領域中廣泛使用的UCI數據集*Ucirvine Machine Learning Repository., 2015.,一共用了5種數值型數據集,其基本信息如表1所示.

表1 數據集的基本信息
Table 1 Main information of data sets

序號數據集(縮寫)規模條件屬性個數決策類個數1Sonar2086022Wdbc5693023Wine1781334Iono3513425Statlog6435366

相容半徑(對粒化模型的影響最為關鍵,也是構建自適應粒化模型和整個分類算法唯一需要優化的參數(數據驅動的自動優化),其取值對后面分類性能的影響是至關重要的.我們在4種數據集上分別測試不一致程度和相容半徑之間的關系,結果如圖1所示.

圖1 不一致程度隨相容半徑變化的趨勢Fig.1 Variation of inconsistency degree with tolerance radius

由圖1可以看出,不一致程度隨相容半徑的增加而呈現單調遞增的變化趨勢,這個結果和性質2是吻合的.這個結論的成立為我們利用折半查找來尋找一致臨界點提供了理論依據.

為進一步觀察相容半徑對最終分類性能的影響,分別就上述4種數據集用不同的相容半徑來構造不同的粒化模型,然后基于構造的粒化模型分別運行本文提出的分類算法,以觀察分類準確率隨相容半徑的變化趨勢.結果如圖2所示.

圖2 分類準確率隨相容半徑變化的趨勢Fig.2 Variation of classification accuracy with tolerance radius

由圖2,當相容半徑從0向1逐漸增加時,分類準確率在各個數據集上大致呈現先逐步升高后逐步下降的趨勢,是一種相對的“單峰”變化趨勢.也就是說,在相容半徑的取值區間[0,1)中,分類準確率的最大值大致位于此“峰頂”上,這為我們尋找最大值提供了啟發信息.

再仔細分析圖1和圖2涉及的實驗數據,我們發現數據集Sonar,Wdbc,Wine和Iono對應粒化模型的一致臨界點大約分別是0.1797,0.0938,0.1750和0.1094;當容半徑大約取值在這些一致臨界點的兩倍值上時,分類準確率達到最大值或近似最大值.例如,上述一致臨界點的二倍值分別為0.360,0.188,0.350,0.219,它們分別接近0.35,0.20,0.35,0.20.在我們測試的結果中,當相容半徑分別為0.30,0.15,0.35,0.20時,算法在數據集Sonar,Wdbc,Wine,Iono上分別獲得最大的分類準確率,它們是0.78,0.94,0.94,0.91.上述的對應關系如圖3所示.

根據圖3中所示的一致臨界點與最大分類準確率的關系以及圖1中所示的單調性和圖2所示的“單峰”性,我們可以估計當相容半徑大約為一致臨界點的兩倍值時,本文算法能夠獲得近似最大準確率.這樣,我們先利用折半查找來尋找一致臨界點,然后以臨界點的兩倍值作為相容半徑的值,從而實現完全由數據驅動來構造自適應粒化模型,并基于該模型利用本文提出的分類算法可以獲得近似最大分類準確率.

圖3 一致臨界點與最大分類準確率的近似關系Fig.3 Relation between consistent critical point and the best classification accuracy

為進一步對比本文算法在自適應方面的性能,在四種數據集Sonar,Wdbc,Statlog和Iono上,我們測試了C4.5、Cart、SVM三種著名分類算法在不同參數下的分類性能,測試結果分別如圖4、下頁圖5和圖6所示.

圖4 C4.5準確率在不同數據集上隨參數M的變化情況(M為葉子結點上的最小對象數)Fig.4 Variation of C4.5′s accuracy with parameter M on different data sets (M denotes the minimum number of instances per leaf)

從圖4-圖6可以看出,C4.5、Cart、SVM在這些數據集上獲得的分類準確率受到參數的影響較大,不同的參數設置可能導致完全不同的分類結果;換句話說,不同的數據集可能需要設置不同的參數.實際上,這些算法涉及的參數不只這些,比如在SVM算法中核函數的選擇就有多種.因此,如何有效地設置分類算法中涉及的參數、保證算法在具體的數據集上能夠獲取較高的分類準確率是分類算法研究的一個重要問題.遺憾的是,對參數的這種優化設置目前尚無有效的指導理論,很多是憑經驗設置的,受主觀因素影響大.

圖5 Cart準確率在不同數據集上隨參數M的變化情況(M為葉子結點上的最小對象數)Fig.5 Variation of Cart′s accuracy with parameter M on different data sets (M denotes the minimum number of instances per leaf)

本文提出的基于自適應粒化模型的數據分類算法不涉及人工參數設置,它完全由數據驅動,可直接用于對數值數據進行分類,并且獲得較好的分類結果.為驗證本文算法的分類準確率,我們進一步將本文算法與C4.5、Cart和SVM在表1中所示的4數據集上進行對比,其中本文算法不需要任何的手工參數設置,完全由數據驅動,而其他算法則經過了一系列的手工參數選擇,以選擇最好的結果.實驗結果如表2所示.

從表2中可以看出,總體上本文算法表現出了較好實驗效果——準確率和召回率都相對比較高,但在數據集Wdbc和Wine上略比SVM算法低.實際上,我們對算法C4.5、Cart和SVM進行了大量的參數調整,從中選擇最好的結果,這本身是一個繁雜的過程,有時候是不可實現的;而本文算法則是自適應地在這些數據集上運行,不做任何的參數調整和設置就能表現出相對較高的分類性能,實現了自適應的數據分類效果.

圖6 SVM準確率在不同數據集上隨參數C的變化情況(使用線性核函數,C為權重參數)Fig.6 Variation of SVM′s accuracy with parameter C on different data sets (linear kernel function is used and C denotes the weight in SVM)

表2 分類準確率和召回率Table 2 Accuracy and recall of classification algorithms

6 結 論

在現今復雜數據環境下,往往難以事先獲得有關數據的先驗知識,這限制了帶有許多參數的分類方法的應用范圍.本文研究了一種面向數值數據的自適應分類問題,提出了一種基于自適應粒化模型的數據分類方法.在該方法中,通過粒化方法來構造數據的自適應粒化模型,然后基于此模型,通過數據對象的約簡和對象規則的簡化來構造分類器.自適應粒化模型的特點在于,不割裂數據之間蘊含的關系,而是以數據對象為中心,充分考慮了數據之間的關系——相容關系,并基于這種關系,通過相容半徑的自動優化來構造自適應粒化模型.提出的整個分類方法完全是由數據驅動的,不需要任何先驗知識,實現了對數據的自適應分類,并且表現出相對較好的分類效果.從工程應用的角度看,本文算法具有更好的實際應用價值.

[1] Ma An-xiang,Zhang Chang-sheng,Zhang Bin,et al.An adaptive ant colony classification algorithm[J].Journal of Northeastern University (Natural Science),2014,35(8):1102-1106.

[2] Mao Guo-jun,Hu Dian-jun,Xie Song-yan.Models and algorithms for classifying big data based on distributed data streams[J].Chinese Journal of Computers,2016,39(72):1-16.

[3] Nieto P J G,García-Gonzalo E,Fernández J R A,et al.A hybrid wavelet kernel SVM-based method using artificial bee colony algorithm for predicting the cyanotoxin content from experimental cyanobacteria concentrations in the trasona reservoir (Northern Spain)[J].Journal of Computational & Applied Mathematics,2016,309:587-602.

[4] Barkana B D,Saricicek I,Yildirim B.Performance analysis of descriptive statistical features in retinal vessel segmentation via fuzzy logic,ANN,SVM,and classifier fusion[J].Knowledge-Based Systems,2017,118:165-176.

[5] Wu X,Zhu X Q,Wu G Q,et al.Data mining with big data[J].IEEE Transactions on Knowledge and Data Engineering,2013,26(1):97-107.

[6] Song Feng-xi,Zhang Da-peng,Yang Jing-yu,et al.Adaptive classification algorithm based on maximum scatter difference discriminant criterion[J].Acta Automatica Sinica,2006,32(4):541-549.

[7] Grinblat G L,Uzal L C,Ceccatto H A,et al.Solving nonstationary classification problems with coupled support vector machines[J].IEEE Trans on Neural Networks,2011,22(1):37-51.

[8] Zhang Jing-xiang,Wang Shi-tong,Deng Zhao-hong.Adaptive classification algorithm for gradual concept-drifting data[J].Pattern Recognition & Artificial Intelligence,2013,26(7):623-633.

[9] Guo Gong-de,Li Nan,Chen Li-fei.A self-adaptive classification method for concept-drifting data streams[J].Journal of Shandong University (Engingeering Science),2012,42(4):1-7.

[10] Hu Zheng-ping,Feng Kai.An cdaptive one-class classification algorithm based on multi-resolution minimum spanning tree model in high-dimensional space[J].Acta Automatica Sinica,2012,38(5):769-775.

[11] Yang Liu,Yu Jian,Jing Li-ping.An adaptive large margin nearest neighbor classification algorithm[J].Journal of Computer Research and Development,2013,50(11):2269-2277.

[12] Hu Q H,Yu D R,Xie Z X.Neighborhood classifiers[J].Expert Systems with Applications,2008,34(2):866-876.

[13] Hu Q H,Liu J F,Yu D R.Mixed feature selection based on granulation and approximation[J].Knowledge-ased System,2008,21(4):294-304.

[14] Cervantes J,García-Lamont F,Rodriguez-Mazahua L,et al.PSO-based method for SVM classification on skewed data sets[J].Neurocomputing,2017,228:187-197.

[15] Grzymala-Busse J W,Clarka P G,Kuehnhausen M.Generalized probabilistic approximations of incomplete data[J].International Journal of Approximate Reasoning,2014,55 (1):180-196.

[16] Grzymala-Busse J W.Generalized parameterized approximations[C].Proceedings 6th International Conference on Rough Sets and Knowledge Technology (RSKT 2011),2011:136-145.

[17] Pawlak Z.Rough Sets-theoretical aspects of reasoning about data[M].Kluwer Academic Publishers,1991.

[18] Pedrycz W.Granular computing:an alysisand design of intelligent systems[M].CRCPress,Francis Taylor,BocaRaton,2013.

[19] Meng Zu-qiang,Shi Zhong-zhi.A fast approach to attribute reduction in incomplete decision systems with tolerance relation-based rough sets[J].Information Sciences,2009,179(16):2774-2793.

[20] Liu Shao-hui,Sheng Qiu-jian,Wu Bin,et al.Research on efficient algorithms for rough set methods[J].Chinese Journal of Computers,2003,26(5):524-529.

[21] Jia X Y,Liao W H,Tang Z M,et al.Minimum cost attribute reduction in decision-theoretic rough set models[J].Information Sciences,2013,219(1):151-167.

附中文參考文獻:

[1] 馬安香,張長勝,張 斌,等.一種自適應蟻群分類算法[J].東北大學學報(自然科學版),2014,35(8):1102-1106.

[2] 毛國君,胡殿軍,謝松燕.基于分布式數據流的大數據分類模型和算法[J].計算機學報,2016,39(72):1-16.

[6] 宋楓溪,張大鵬,楊靜宇,等.基于最大散度差鑒別準則的自適應分類算法[J].自動化學報,2006,32(4):541-549.

[8] 張景祥,王士同,鄧趙紅.適于漸變概念漂移數據的自適應分類算法[J].模式識別與人工智能,2013,26(7):623-633.

[9] 郭躬德,李 南,陳黎飛.一種適應概念漂移數據流的分類算法[J].山東大學學報(工學版),2012,42(4):1-7.

[10] 胡正平,馮 凱.高維空間多分辨率最小生成樹模型的自適應一類分類算法[J].自動化學報,2012,38(5):769-775.

[11] 楊 柳,于 劍,景麗萍.一種自適應的大間隔近鄰分類算法[J].計算機研究與發展,2013,50(11):2269-2277.

[20] 劉少輝,盛秋戩,吳 斌,等.Rough 集高效算法的研究[J].計算機學報,2003,26(5):524-529.