運用自適應(yīng)?；Ｐ偷囊环N數(shù)據(jù)分類方法

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

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

1 引 言

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

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

本文基于屬性-值對塊(attribute-value block)技術(shù),通過利用數(shù)值數(shù)據(jù)之間的相容關(guān)系和數(shù)據(jù)對象的粒化方法構(gòu)建數(shù)據(jù)的自適應(yīng)?；Ｐ?然后基于該模型設(shè)計面向數(shù)據(jù)的、完全由數(shù)據(jù)驅(qū)動的自適應(yīng)分類算法.

2 相容關(guān)系下的屬性-值對塊及其性質(zhì)

屬性-值對塊(attribute-value pair block)是美國著名學(xué)者Grzymala-Busse教授提出的用于處理不完備信息的一種數(shù)據(jù)分析技術(shù)[15,16].本節(jié)先介紹屬性-值對塊的概念及有關(guān)性質(zhì),在下一節(jié)中將用這種技術(shù)來對數(shù)值數(shù)據(jù)進行建模,進而構(gòu)造自適應(yīng)?；Ｐ秃蛿?shù)據(jù)分類方法.

對給定的訓(xùn)練集T,其對應(yīng)的數(shù)據(jù)模型表示為(U,A=C∪D),不妨記為T=(U,A=C∪D),其中U表示訓(xùn)練集中數(shù)據(jù)對象的集合,A是所有數(shù)據(jù)屬性的集合,C和D分別稱為條件屬性集和決策屬性集,且C∩D=?;對a∈C,用Va表示屬性a的值域.不失一般性,假設(shè)D=j5i0abt0b,即假設(shè)決策屬性集D僅由一個屬性d組成.對任意x∈U和a∈C,用函數(shù)fa(x)表示對象x在屬性a上的取值,f稱為信息函數(shù).對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的關(guān)于屬性a和值v的屬性-值對塊(attribute-value pair block)[15].屬性-值對塊的特點是將一個概念的內(nèi)涵(屬性-值對)和外延(塊)有機地結(jié)合起來,用于表示粒計算[18]中的基本積木塊,為問題的?；峁┓椒ㄖ?可以看到,屬性-值對塊的物理意義和邏輯意義都很明顯.例如,屬性-值對塊[(a,fa(x))]表示所有與對象x在屬性a上取值相同的對象的集合,用屬性a是無法區(qū)分集合中的這些對象,因而它們構(gòu)成了基本的積木塊,而(a,fa(x))是這個塊的一個描述,是解釋分類器的一個原子公式.

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

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

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

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

如果δ= 0,則這種相容關(guān)系就變?yōu)榈葍r關(guān)系.

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

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

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

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

如果說Ka,δ(x)是原子積木塊,那么KB,δ(x)就是由Ka,δ(x)構(gòu)成的復(fù)合積木塊.復(fù)合積木塊有一個重要的單調(diào)性質(zhì).

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

3 基于屬性-值對塊的自適應(yīng)?；Ｐ?/h2>

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

3.1 理論模型

以數(shù)據(jù)對象為中心的處理方法可以利用屬性-值對塊技術(shù)來實現(xiàn).以屬性-值對塊替換對應(yīng)的數(shù)據(jù)對象,于是得到一個新的?；Ｐ汀趯傩?值對塊的?；Ｐ?granulation model),記為GM=(Ka,δ(U),C∪D)a∈C,其中,Ka,δ(U)={Ka,δ(x) |x∈U}.Ka,δ(x)是這個模型中的基本積木塊.對任意y∈Ka,δ(x),fa(x)被認為與fa(y)相等.

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

定義4.對給定的?；Ｐ虶M=(Ka,δ(U),C∪D)a∈C,D=j5i0abt0b,如果存在x∈U,使得|fd(KC,δ(x))| > 1,則該?；Ｐ褪遣灰恢碌?否則是一致的;相應(yīng)地,令ρ(GM,δ)=|{x‖fd(KC,δ(x))|>1}|/|U|,ρ(GM,δ)稱為?；Ｐ虶M的不一致程度,其中fd(KC,δ(x))表示塊KC,δ(x)在信息函數(shù)fd下的像.

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

該定義的直觀意義是,|fd(KC,δ(x))| > 1就意味著塊KC,δ(x)至少跟兩個決策類相交,因而是不一致的.對數(shù)值系統(tǒng)來說,初始的數(shù)據(jù)模型一般都是一致的.如果相容半徑δ=0,?；Ｐ屯嘶癁樵瓉淼某跏紨?shù)據(jù)模型,都是一致的;如果δ逐漸增大,各個基本塊也逐步增大,從而ρ(GM,δ)逐漸變大,粒化模型也隨之逐步趨向不一致;當(dāng)δ=1時,ρ(GM,δ)達到最大值1,?；Ｐ妥兊猛耆灰恢?當(dāng)然這種?；Ｐ蜎]有任何研究價值,一般不考慮.我們有下面的性質(zhì).

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

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

性質(zhì)3說明,在區(qū)間[0,1]中必存在一點δ0,使得當(dāng)δ<=δ0時,ρ(GM,δ)=0(?；Ｐ鸵恢?;當(dāng)δ>δ0時,ρ(GM,δ)>0(?；Ｐ筒灰恢?.我們引入如下定義.

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

對于給定的原始數(shù)據(jù)模型T=(U,A=C∪D),當(dāng)構(gòu)造其?；Ｐ蜁r,最為關(guān)鍵的問題是如何選擇相容半徑？過大或過小的相容半徑都會導(dǎo)致不好的分類結(jié)果.在多次的實驗中我們發(fā)現(xiàn),當(dāng)相容半徑約等于一致臨界點的兩倍值時,分類準確率達到最大值或近似最大值.根據(jù)性質(zhì)3,我們可以利用折半查找方法,完全依賴于數(shù)據(jù)之間的相容關(guān)系,快速找到?；Ｐ偷囊恢屡R界點,從而實現(xiàn)對相容半徑的自適應(yīng)優(yōu)化,這個優(yōu)化過程是完全由數(shù)據(jù)驅(qū)動的,不需要任何先驗知識.假設(shè)δ0表示找到的一致臨界點,其二倍值2δ0記為δ″,即δ″=2δ0,則由此構(gòu)造的?；Ｐ涂梢员硎緸?Ka,δ″(U),C∪D)a∈C,稱為自適應(yīng)?；Ｐ?一種理論模型).

3.2 存儲模型

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

在?；Ｐ?Ka,δ(U),C∪D)a∈C中,任意一屬性a∈C,數(shù)據(jù)間的關(guān)系Tol(a,δ)都是相容關(guān)系(性質(zhì)1),于是可以引入下面的一些概念并導(dǎo)出有關(guān)性質(zhì).

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

性質(zhì)4.在?；Ｐ虶M=(Ka,δ(U),C∪D)a∈C中,Ka,δ(x)=∪MCa,δ[x],即Ka,δ(x)={y|y(TC,TC∈MCa,δ[x]},其中x∈U.

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

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

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

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

最大相容類空間ψ(δ)及其位置索引結(jié)構(gòu)ψ(δ)共同構(gòu)成了?；Ｐ偷拇鎯Y(jié)構(gòu)(模型),記為[Rψ(δ),ψ(δ)].

我們的目標是找到一致臨界點δ0.根據(jù)性質(zhì)3,這個目標可以用折半查找的方法來實現(xiàn).假設(shè)計算δ0的精度要求是λ∈(0,1),則最多需要找1/λ個點.而根據(jù)折半查找算法的復(fù)雜度,總共只需要進行l(wèi)og2(1/λ)次查找操作即可找到λ0(精度λ下的一致臨界點),從而形成自適應(yīng)粒化模型(Ka,δ″(U),C∪D)a∈C的存儲結(jié)構(gòu)[R(δ″),ψ(δ″)],其中δ″=2δ0.因此,建立[R(δ″),ψ(δ″)]的計算復(fù)雜度約為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 基于自適應(yīng)?；Ｐ偷姆诸愃惴?/h2>

在生成自適應(yīng)?；Ｐ?Ka,δ″(U),C∪D)a∈C后,可以通過數(shù)據(jù)對象的約簡和對象規(guī)則的簡化來構(gòu)造分類器.為此,先引入相關(guān)概念,然后分別討論這兩個過程.

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

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

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

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

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

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

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

一種途徑是利用有效覆蓋度來構(gòu)造啟發(fā)信息.方法是,先計算RuleSet中每條規(guī)則r的有效覆蓋度,并按照有效覆蓋度對U中的數(shù)據(jù)對象進行降序排列,然后利用這個序列來選擇規(guī)則,最終構(gòu)造分類器.這樣,結(jié)合上述的自適應(yīng)?；Ｐ?我們可以給出一個完整的分類算法,算法描述如下:

分類算法的描述:

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

輸出:分類器RS(由規(guī)則構(gòu)成)

Begin

Step1. 建立自適應(yīng)?；Ｐ?Ka,δ″(U),C∪D)a∈C及

存儲結(jié)構(gòu)[R(δ″),ψ(δ″)];

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

設(shè)結(jié)果為RuleSet;

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

保存R[x],其中r為x導(dǎo)出的規(guī)則;

Step4. 據(jù)RuleSet中相應(yīng)規(guī)則的覆蓋度,對U中對象

降序排序,設(shè)結(jié)果為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中,建立存儲結(jié)構(gòu)[R(δ″),ψ(δ″)]的計算復(fù)雜度為O(log2(1/λ)|C‖U|log|U|),如果精度(比較大時(精度要求不高),O(log2(1/λ)|C‖U|log|U|)≈O(|C‖U|log|U|).此后,算法的計算都依賴于存儲結(jié)構(gòu)[R(δ″),ψ(δ″)].

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

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

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

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

5 實驗分析

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

表1 數(shù)據(jù)集的基本信息
Table 1 Main information of data sets

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

相容半徑(對?；Ｐ偷挠绊懽顬殛P(guān)鍵,也是構(gòu)建自適應(yīng)?；Ｐ秃驼麄€分類算法唯一需要優(yōu)化的參數(shù)(數(shù)據(jù)驅(qū)動的自動優(yōu)化),其取值對后面分類性能的影響是至關(guān)重要的.我們在4種數(shù)據(jù)集上分別測試不一致程度和相容半徑之間的關(guān)系,結(jié)果如圖1所示.

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

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

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

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

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

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

根據(jù)圖3中所示的一致臨界點與最大分類準確率的關(guān)系以及圖1中所示的單調(diào)性和圖2所示的“單峰”性,我們可以估計當(dāng)相容半徑大約為一致臨界點的兩倍值時,本文算法能夠獲得近似最大準確率.這樣,我們先利用折半查找來尋找一致臨界點,然后以臨界點的兩倍值作為相容半徑的值,從而實現(xiàn)完全由數(shù)據(jù)驅(qū)動來構(gòu)造自適應(yīng)?；Ｐ?并基于該模型利用本文提出的分類算法可以獲得近似最大分類準確率.

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

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

圖4 C4.5準確率在不同數(shù)據(jù)集上隨參數(shù)M的變化情況(M為葉子結(jié)點上的最小對象數(shù))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在這些數(shù)據(jù)集上獲得的分類準確率受到參數(shù)的影響較大,不同的參數(shù)設(shè)置可能導(dǎo)致完全不同的分類結(jié)果;換句話說,不同的數(shù)據(jù)集可能需要設(shè)置不同的參數(shù).實際上,這些算法涉及的參數(shù)不只這些,比如在SVM算法中核函數(shù)的選擇就有多種.因此,如何有效地設(shè)置分類算法中涉及的參數(shù)、保證算法在具體的數(shù)據(jù)集上能夠獲取較高的分類準確率是分類算法研究的一個重要問題.遺憾的是,對參數(shù)的這種優(yōu)化設(shè)置目前尚無有效的指導(dǎo)理論,很多是憑經(jīng)驗設(shè)置的,受主觀因素影響大.

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

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

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

圖6 SVM準確率在不同數(shù)據(jù)集上隨參數(shù)C的變化情況(使用線性核函數(shù),C為權(quán)重參數(shù))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 結(jié) 論

在現(xiàn)今復(fù)雜數(shù)據(jù)環(huán)境下,往往難以事先獲得有關(guān)數(shù)據(jù)的先驗知識,這限制了帶有許多參數(shù)的分類方法的應(yīng)用范圍.本文研究了一種面向數(shù)值數(shù)據(jù)的自適應(yīng)分類問題,提出了一種基于自適應(yīng)?；Ｐ偷臄?shù)據(jù)分類方法.在該方法中,通過?；椒▉順?gòu)造數(shù)據(jù)的自適應(yīng)?；Ｐ?然后基于此模型,通過數(shù)據(jù)對象的約簡和對象規(guī)則的簡化來構(gòu)造分類器.自適應(yīng)?；Ｐ偷奶攸c在于,不割裂數(shù)據(jù)之間蘊含的關(guān)系,而是以數(shù)據(jù)對象為中心,充分考慮了數(shù)據(jù)之間的關(guān)系——相容關(guān)系,并基于這種關(guān)系,通過相容半徑的自動優(yōu)化來構(gòu)造自適應(yīng)?；Ｐ?提出的整個分類方法完全是由數(shù)據(jù)驅(qū)動的,不需要任何先驗知識,實現(xiàn)了對數(shù)據(jù)的自適應(yīng)分類,并且表現(xiàn)出相對較好的分類效果.從工程應(yīng)用的角度看,本文算法具有更好的實際應(yīng)用價值.

[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] 馬安香,張長勝,張 斌,等.一種自適應(yīng)蟻群分類算法[J].東北大學(xué)學(xué)報(自然科學(xué)版),2014,35(8):1102-1106.

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

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

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

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

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

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

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