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

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

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