一種多數(shù)據(jù)融合的空間特征選擇方法

一種多數(shù)據(jù)融合的空間特征選擇方法

資源選擇廣泛應(yīng)用于模式識別和挖掘挖掘領(lǐng)域。同時，它也是一個必須有效解決的重要問題。資源選擇是指根據(jù)給定規(guī)范選擇具有良好區(qū)分特征的資源收集，或根據(jù)特定規(guī)范對特征進(jìn)行分類，以便高效地設(shè)計分類器的優(yōu)化設(shè)計。當(dāng)前的資源選擇方法主要是傳統(tǒng)的模式識別方法。這些方法主要集中在空間數(shù)據(jù)的資源提取問題上，并在空間數(shù)據(jù)環(huán)境下討論資源提取問題。文獻(xiàn)中顯示了這些方法，但總體研究還不夠深入。當(dāng)應(yīng)用程序中包含空間數(shù)據(jù)時，傳統(tǒng)的資源選擇方法沒有充分考慮空間數(shù)據(jù)的特性，因此資源選擇的結(jié)果和性能會降低。因此，空間資源選擇問題非常復(fù)雜。本文從空間數(shù)據(jù)特性的角度出發(fā),提出一種新的特征選擇方法MEFS(maximumentropyfeatureselection),并應(yīng)用到我們研制的空間數(shù)據(jù)挖掘原型系統(tǒng)SpatialMiner中.MEFS基于最大熵原理,運用互信息和Z-測試技術(shù),采用兩步方法進(jìn)行空間特征選擇:首先是空間謂詞選擇,然后選擇與每個空間謂詞對應(yīng)的相關(guān)屬性集.最后對MEFS方法和RELIEF方法以及基于MEFS的分類方法與ID3算法分別進(jìn)行了實驗比較,結(jié)果表明,MEFS方法不僅可以節(jié)約特征提取和分類時間,而且也極大地提高了分類質(zhì)量.1最大熵模型的建立最大熵原理在文獻(xiàn)中給出了詳細(xì)的描述,其基本思想是:給定訓(xùn)練樣本,選擇一個與訓(xùn)練樣本一致的模型.最大熵模型應(yīng)選擇與這些觀察相一致的概率分布,而對于除此之外的情況,模型賦予均勻的概率分布.1.1yy決策屬性對pyyxpyyxp假設(shè)特征選擇的分類屬性值構(gòu)成隨機(jī)過程P所有輸出值Y.對于每個y∈Y,其出現(xiàn)均受與之相關(guān)的決策屬性值x的影響.已知與Y相關(guān)的所有決策屬性值組成的集合為X,則模型的目標(biāo)是:對給定的所有決策屬性x∈X,計算輸出為y∈Y的條件概率,即對p(y|x)進(jìn)行估計,其中y∈Y且x∈X.因此,特征選擇的目的就是從眾多決策屬性中選擇出對分類屬性具有明顯表征作用的特征.1.2概率分布特征特征選擇過程是在抽樣數(shù)據(jù)的基礎(chǔ)上,抽樣數(shù)據(jù)來自采樣數(shù)據(jù)庫,對空間而言還包含空間數(shù)據(jù)信息,表示為(x1,y1),(x2,y2),…,(xi,yi),…,(xn,yn).其中,xi表示決策屬性,或為空間數(shù)據(jù),或為非空間數(shù)據(jù),yi是分類屬性,是由專家提供的類標(biāo)號.在訓(xùn)練數(shù)據(jù)的基礎(chǔ)上,可以用概率分布的極大似然對訓(xùn)練樣本進(jìn)行表示.即其中freq(x,y)表示(x,y)在樣本中出現(xiàn)的次數(shù).1.3特征與表征函數(shù)定義1(特征).設(shè)x∈X且x=w1w2…wn,設(shè)c是x的子串(長度≥1),若c對y∈Y具有表征作用,則稱(c,y)為模型的一個特征.特征分為原子特征和復(fù)合特征.若串c的長度為1,則稱(c,y)為原子特征,否則,稱(c,y)為復(fù)合特征.定義2(特征函數(shù)).特征函數(shù)是一個二值表征函數(shù),表示(x′,y′)是否與特征(c,y)有關(guān).定義(x′,y′)關(guān)于特征(c,y)的特征函數(shù)為1.4最大熵法解決足約束條件模型假設(shè)存在n個特征fi(i=1,2,…,n),則模型屬于約束所產(chǎn)生的模型集合,即而滿足約束條件的模型有很多,模型的目標(biāo)是產(chǎn)生在約束集下具有最均勻分布的模型,而條件概率p(y|x)均勻性的一種數(shù)學(xué)測量方法為條件熵,定義為其中0H(p)log|y|.最大熵原理.若在允許的概率分布C中選擇模型,具有最大熵的模型p*∈C即為所選模型.即2空間屬性選擇方法利用最大熵原理求取空間特征包含特征選擇和參數(shù)估計.特征選擇是選出對分類對象有明顯表征作用的屬性;參數(shù)估計是用最大熵原理對每一個特征進(jìn)行參數(shù)估值,使每個特征對應(yīng)于一個特征參數(shù).特征參數(shù)用來反映決策屬性與分類屬性之間的關(guān)聯(lián)強(qiáng)度.本文基于空間數(shù)據(jù)特性,提出了兩步方法進(jìn)行空間特征選擇:謂詞提取和相關(guān)屬性選擇.謂詞提取選出能夠以某種空間謂詞(或函數(shù))表征分類對象的數(shù)據(jù)集.相關(guān)屬性選擇在已選擇謂詞的基礎(chǔ)上,選出依附于該謂詞而且能夠表征分類對象的非空間屬性.2.1基于最優(yōu)模型的相對熵模型(1)互信息.互信息是測量搭配強(qiáng)度的一個物理量.若某一變量x對y有表征意義,則y與該x的互信息較大計算如下式:(2)Z-測試.我們可以求取變量間的關(guān)聯(lián)強(qiáng)度,但如果特征選擇直接確定選擇互信息大于某一閾值的上下文信息為特征時,則對于不同互信息的分布,閾值也不相同,這樣算法難以操作.我們需要一種方法來進(jìn)行變換,使得所有變量互信息的分布服從統(tǒng)一的準(zhǔn)則.Z-測試正是這樣的一個測度,它可以將互信息的分布進(jìn)行標(biāo)準(zhǔn)變換將其變?yōu)闃?biāo)準(zhǔn)的正態(tài)分布.這樣,不論互信息如何進(jìn)行分布,都可以從一個統(tǒng)一的閾值開始進(jìn)行求解.計算如下式:其中Ey表示互信息均值,表示為表示均方差,表示為(3)IIS.建立最大熵模型的關(guān)鍵是要選出具有預(yù)期作用的特征,只有這樣才能保證得到的解是對模型最有用的解.IIS算法較好地解決了這一問題.算法假設(shè)滿足最大熵條件的概率p(x,y)具有Gibbs分布的形式:其中Z?(x)為歸一常量,保證對所有(4)模型質(zhì)量度量.利用特征選擇算法得到特征集確定的模型p.p與由訓(xùn)練集確定的概率模型之間的距離作為度量所求模型質(zhì)量的尺度,這里采用相對熵來度量.相對熵被用于衡量兩個隨機(jī)分布的差距,定義為2.2.3特征提取Koperski在文獻(xiàn)中給出了一種謂詞提取方法.提取過程分為兩步:首先進(jìn)行粗略計算,然后在概念層次的基礎(chǔ)上只對有希望的模式進(jìn)行細(xì)化計算.簡單而言,謂詞提取就是發(fā)現(xiàn)滿足某種謂詞關(guān)系的、可以用于描述分類對象的對象.但該方法提取的結(jié)果都是對象類(如鐵路),而不是具體的某類對象(長鐵路).但在實際的分類過程中,不同的分類屬性可能與不同的某類對象而不是與對象類相關(guān).所以,特征提取不僅應(yīng)該考察對象類的提取,更重要的是提取能夠標(biāo)識分類對象的某類對象.2.2.1稱謂詞提取算法空間謂詞和空間函數(shù)作為謂詞提取的對象,用來描述分類對象.為了利用最大熵原理進(jìn)行提取,首先要將空間謂詞和函數(shù)轉(zhuǎn)化為樣本形式S=(P1(x1),y1),…,(Pi(xj),yk),…,(Pl(xm),yn).其中,(Pi(xj),yk)表示分類對象yk與決策對象屬性xj滿足關(guān)系Pi.求取的最終結(jié)果是滿足特征參數(shù)閾值的謂詞集及其參數(shù)估計值.具體算法描述如下:算法1.謂詞提取(predicate_selection).輸入:樣本集S,特征參數(shù)閾值t,質(zhì)量度量閾值?.輸出:特征集C和特征參數(shù)集P.步驟描述如下:2.2.2算法的計算復(fù)雜度算法的計算量由互信息、特征參數(shù)及相對熵的計算量3部分組成.互信息的計算量與空間關(guān)系數(shù)據(jù)集的規(guī)模線性相關(guān).假設(shè)P=|Y|,N=|X|,則互信息的計算復(fù)雜度為O(P×N).由于特征求取和參數(shù)估計的過程是一個迭代的過程,而且由互信息的正態(tài)分布特性可知,算法必將在有限步內(nèi)收斂,假設(shè)為k次循環(huán).假設(shè)第k次循環(huán)中參數(shù)估計時間量為IISk(也為最大量,因為隨著迭代的進(jìn)行,特征數(shù)目有所增加).同樣,相對熵的最大計算量為Dk,則它們的時間復(fù)雜度為O(k×IISk×Dk).所以總的時間復(fù)雜度為O(P×N)+O(k×IISk×Dk).2.3空間決策屬性的預(yù)處理決策屬性包括空間和非空間兩種.經(jīng)過上述謂詞提取之后,得到空間決策屬性集合C及特征參數(shù)集P.從謂詞提取結(jié)果可知,某些空間決策屬性對于所有的分類對象可能都具有較強(qiáng)的關(guān)聯(lián)程度,但這對分類無用,需要一種方法將這些空間決策屬性剔除,僅保留對分類具有明顯作用的部分.我們引入如下定義:定義4(特征強(qiáng)度(featurestrength)).假設(shè)D是決策屬性集,d是D中的一個元素,F是一個空間分類對象對應(yīng)的空間決策屬性集.sigs(d)表示決策屬性d在集合s中的特征參數(shù)和.card(s)表示集合s中元素的特征參數(shù)總和,則決策屬性d在F中相對于D的特征參數(shù)強(qiáng)度可表示為sigFD(d),定義如下:假設(shè)significance表示特征參數(shù)強(qiáng)度閾值,那么滿足如下條件的決策屬性為具有分類作用的決策屬性:2.3.1算法的基本思想非空間決策屬性依附于某類空間對象,與不同分類對象對應(yīng)的具有不同謂詞關(guān)系的空間決策對象具有不同的相關(guān)屬性.如與某一分類對象具有close_to關(guān)系的中等發(fā)達(dá)城市和與具有contain關(guān)系的發(fā)達(dá)城市就有不同的非空間決策屬性對應(yīng).因此,需要對空間決策屬性集合C中的元素逐個進(jìn)行考慮,選取與之對應(yīng)的非空間決策屬性(原子屬性或者合成屬性).在進(jìn)行非空間決策屬性選擇前后,需要利用定義4所定義的特征強(qiáng)度過濾無用的空間決策屬性和非空間決策屬性.算法2.相關(guān)屬性選擇(relevent_property_selection)輸入:空間決策屬性集C,特征參數(shù)集P,特征強(qiáng)度閾值significance.輸出:非空間決策屬性集non_C,特征參數(shù)集non_P.步驟描述如下:注:在本算法中利用算法1進(jìn)行非空間決策屬性的選擇是合理的,因為轉(zhuǎn)化為關(guān)系型之后無差別.時間復(fù)雜性分析.本算法時間復(fù)雜性由兩部分組成:特征強(qiáng)度和算法1的時間復(fù)雜性.由于計算特征強(qiáng)度的時間復(fù)雜性較低,故忽略不計.算法1的復(fù)雜性分析在第2.2.2節(jié)已經(jīng)給出,這里不再贅述.假設(shè)|C′|=m,則本算法的時間復(fù)雜性為O(m×P×N)+O(m×k×IISk×Dk).2.3.2生成非空間決策屬性非空間決策屬性選擇結(jié)果是特征集和與之對應(yīng)的特征參數(shù).其中特征集不僅包含非空間決策屬性,而且也包含產(chǎn)生它的空間決策屬性(謂詞集).如對于一空間決策屬性(Pi(xj),yk)經(jīng)過算法2中的步驟5),可以得到如下形式的樣本元素:(Pi(xj)p1…pi…pn,yk),其中pi或者是原子屬性或者是合成屬性.因此,非空間決策屬性選擇的結(jié)果不僅代表非空間的意義,還包含了空間決策屬性的全部內(nèi)容.3結(jié)果3.1基于特征集的方法設(shè)計在本文中,我們將基于最大熵理論進(jìn)行空間特征選擇,并將結(jié)果根據(jù)人均儲蓄情況對全國的縣進(jìn)行分類.模型輸入:已知全國縣的人均儲蓄分布及其鄰居關(guān)系,分類對象Y為按人均儲蓄分類的縣,決策屬性為縣本身的屬性以及與縣具有空間謂詞關(guān)系的對象以及屬性.模型輸出:影響縣人均儲蓄的特征集S以及表征參數(shù)λ.根據(jù)特征選擇結(jié)果,基于抽樣數(shù)據(jù)集,首先進(jìn)行RELIEF特征抽取方法和MEFS方法在選擇時間上的比較,然后進(jìn)行基于MEFS的分類方法和ID3算法在分類時間和質(zhì)量上的比較.3.2實驗過程(1)實驗數(shù)據(jù)及方法采用IBM公司數(shù)據(jù)庫DB2和空間環(huán)境SpatialExtender作為數(shù)據(jù)操作環(huán)境,Java為開發(fā)平臺.數(shù)據(jù)取自國家地理信息系統(tǒng)中國地圖數(shù)據(jù),實驗中涉及的圖層有:分類對象是全國2500左右個縣,預(yù)測對象包括鐵路、公路以及對象自身包括面積、人均消費、糧食產(chǎn)量以及收入等屬性,分類對象按人均儲蓄屬性分為5個類t1~t5,謂詞關(guān)系為contain.從每個分類對象集合中選取400個對象用于訓(xùn)練集,余下的500個對象用于測試.(2)鐵路與公路、公路、公路長度成正比按本文提出的特征選擇算法和參數(shù)估計算法,結(jié)果見表1.由此得出如下結(jié)論:縣人均儲蓄與contain(x,rail)/area,contain(x,road)/area(單位面積鐵路和公路長度)成正比,與縣面積成反比,與avgconsume(人均消費),avgfinance(人均財政收入),avgcorp(人均糧食產(chǎn)量)成正比.(3)分類比較過程空間分類是空間數(shù)據(jù)挖掘的一個重要研究分支,ID3算法是經(jīng)典的也是高效的算法之一.下面在上述數(shù)據(jù)集的基礎(chǔ)上,采用ID3算法并基于本文的MEFS方法進(jìn)行分類比較.比較過程如下:基于MEFS的分類過程描述如下:對于給定的抽樣樣本集,經(jīng)過空間特征提取過程可以得到特征和參數(shù)集?S,λ?.對于待識別的樣本集合的每個元素,用分類特征公式計算各個不同分類對象對應(yīng)的特征公式的值,最后取特征值最大者對應(yīng)的類為得到的類.下面分別對特征選擇時間、分類時間和分類準(zhǔn)確度進(jìn)行實驗比較,結(jié)果如下:(1)效率補償原則圖1是在上述數(shù)據(jù)集之上對MEFS特征選擇方法和RELIEF方法進(jìn)行比較之后的時間變化曲線.由圖1可知,本文的MEFS方法在提取過程中沒有RELIEF算法的效率高.這是因為RELIEF算法進(jìn)行的是模式選擇,也就是說它選出的特征是對象和屬性類的集合,而不是表征分類對象的某類對象.而本文的MEFS方法考察的是表征分類對象的對象和屬性類,得出了真正表征分類對象的對象和屬性,因此在效率上有所降低.但是,效率的降低在如下方面得到補償:(1)特征選擇精度得到提高;(2)分類過程不需要構(gòu)造決策樹,免去這部分時間的消耗,而且對于一棵大決策樹而言,這個消耗也是很大的.因此,如果特征選擇時間總和與決策樹的構(gòu)造時間總和進(jìn)行比較,可以得到如圖2所示的性能比較結(jié)果.圖2的對比說明,就總體特征提取和構(gòu)造決策樹的代價總體而論,MEFS算法在時間上還是優(yōu)于RELIEF算法的.這是因為MEFS方法的分類規(guī)則是以分類特征公式而表達(dá)的,而RELIEF算法必須構(gòu)造一棵決策樹,構(gòu)造該樹的時間耗費是隨著特征集規(guī)模的大小而呈正比變化的.(2)分類精度分析實驗結(jié)果表明,采用本文的基于MEFS的方法進(jìn)行空間分類與采用ID3決策樹算法相比,時間復(fù)雜度要低一些.這是因為決策樹判定的過程就是與當(dāng)前分類屬性和樹的當(dāng)前分支比較,每進(jìn)行一個分支,需要掃描一遍當(dāng)前抽樣集合的元組,掃描遍數(shù)為當(dāng)前所沿路徑的深度.但是基于MEFS的方法只需進(jìn)行一遍掃描,將當(dāng)前抽樣元組含有的決策特征屬性映射到各個分類對象對應(yīng)的特征公式即可.由表2可知,基于MEFS方法的分類的精度也比ID3有所提高,這是因為基于MEFS的分類方法所基于的分類特征是經(jīng)過過濾的,每個分類屬性都對應(yīng)于自己本身的特征對象和屬性,這樣不但提高了分類的準(zhǔn)確度和時間消耗,而且也避免了ID3在建造決策樹時對噪聲的干擾.對ID3算