王 念 彭政紅 崔 莉

1(中國(guó)科學(xué)院計(jì)算技術(shù)研究所 北京 100190)2(中國(guó)科學(xué)院大學(xué) 北京 100190)(wangnian@ict.ac.cn)

在物聯(lián)網(wǎng)應(yīng)用場(chǎng)景中，系統(tǒng)通常需要部署大量感知節(jié)點(diǎn)來(lái)獲取環(huán)境信息.為充分利用每個(gè)節(jié)點(diǎn)的傳感信息以支持后續(xù)精準(zhǔn)的識(shí)別與預(yù)測(cè)，實(shí)際應(yīng)用中系統(tǒng)通常會(huì)從每個(gè)節(jié)點(diǎn)的原始信息中提取大量特征，并通過(guò)串行融合[1]的方式對(duì)數(shù)據(jù)集進(jìn)行特征級(jí)多源信息融合，形成超級(jí)特征(super feature)，并進(jìn)行后續(xù)的機(jī)器學(xué)習(xí)模型訓(xùn)練和驗(yàn)證操作.但在每個(gè)傳感器的大量特征中，通常包含了與決策任務(wù)無(wú)關(guān)、弱相關(guān)或相互冗余的特征.此類(lèi)特征不但對(duì)于決策結(jié)果無(wú)明顯貢獻(xiàn)，而且會(huì)增加計(jì)算量，從而降低決策效率，進(jìn)而影響后續(xù)分類(lèi)或預(yù)測(cè)操作的性能.若可找出并去除此類(lèi)特征，則可提高系統(tǒng)實(shí)時(shí)性并減少所需傳感器的種類(lèi)及數(shù)量.因此在特征工程中，有必要在決策前對(duì)原始數(shù)據(jù)進(jìn)行降維操作.

目前常用的降維方法包括線性方法、相關(guān)性分析法、主成分分析法和基于鄰域粗糙集的特征約簡(jiǎn)方法等[2].其中，線性方法無(wú)法適用于非線性場(chǎng)景；相關(guān)性分析和主成份分析法會(huì)造成原屬性集中部分信息丟失；而基于粗糙集的方法能夠在無(wú)任何先驗(yàn)知識(shí)(如統(tǒng)計(jì)中的先驗(yàn)概隸屬度等)的情況下，保留數(shù)據(jù)集的基本知識(shí)和分類(lèi)能力，并消除重復(fù)和冗余的特征，是一種有效的特征約簡(jiǎn)算法.然而目前已有的基于鄰域粗糙集的特征約簡(jiǎn)算法[3-5]中存在較多冗余計(jì)算，嚴(yán)重限制了算法的執(zhí)行效率.約簡(jiǎn)效率會(huì)影響算法的整體實(shí)時(shí)性，尤其對(duì)于在線學(xué)習(xí)以及數(shù)據(jù)有較強(qiáng)時(shí)效性的場(chǎng)景中，頻繁或定期的模型重構(gòu)會(huì)要求較高的特征約簡(jiǎn)速度.針對(duì)上述問(wèn)題，本文提出了一種基于鄰域關(guān)系對(duì)稱性及決策值過(guò)濾策略的特征快速約簡(jiǎn)算法(Easi fast Hash feature reduction algorithm,EasiFFRA).

1 相關(guān)工作與背景知識(shí)

1.1 背景知識(shí)

粗糙集理論是Pawlak[6]提出的一種定量分析處理不精確、不一致和不完整信息的方法.目前該理論已被廣泛應(yīng)用于人工智能、模式識(shí)別和數(shù)據(jù)挖掘等領(lǐng)域[7-10].但作為一種有效的粒度計(jì)算模型，粗糙集理論只適用于名義型數(shù)據(jù)，無(wú)法直接應(yīng)用于現(xiàn)實(shí)中廣泛存在的連續(xù)型數(shù)據(jù).為處理連續(xù)性數(shù)據(jù)，研究人員往往需要對(duì)連續(xù)型數(shù)據(jù)進(jìn)行離散化，但這一轉(zhuǎn)換不可避免地帶來(lái)了信息損失，且計(jì)算結(jié)果受到了離散化的影響.為解決這一問(wèn)題，胡清華等人[3]基于拓?fù)淇臻g球形鄰域提出了鄰域粗糙集(neighborhood rough set,NRS)理論.其核心是使用鄰域近似代替經(jīng)典粗糙集中的等價(jià)關(guān)系，以使其既支持離散型數(shù)據(jù)又支持連續(xù)型數(shù)據(jù).鄰域粗糙集有效拓展了粗糙集的應(yīng)用范圍，使其在特征約簡(jiǎn)、模式識(shí)別等方面有著長(zhǎng)足的發(fā)展[11-14].

1.2 相關(guān)工作

特征約簡(jiǎn)是鄰域粗糙集最重要的也是核心內(nèi)容之一[4,8,15-16].通常，系統(tǒng)的特征相對(duì)約簡(jiǎn)結(jié)果不唯一，人們期望找到一種具有最少特征維度的約簡(jiǎn)方法，即最小約簡(jiǎn).但尋找最小約簡(jiǎn)已被證明是一種NP難問(wèn)題[17]，故而研究者們主要致力于用高效的約簡(jiǎn)算法找到一個(gè)較優(yōu)的屬性子集[4-5,16,18].胡清華等人[3,5]利用正域與屬性集的單調(diào)關(guān)系提出了基于前向貪心啟發(fā)式搜索策略(fast forward heterogeneous attribute reduction based on neighborhood rough sets,F2HARNRS)算法，該算法從空集開(kāi)始構(gòu)建約簡(jiǎn)集合，每一次迭代過(guò)程都將當(dāng)前特征集合中具有最大正域值的屬性加入約簡(jiǎn)集合，并過(guò)濾掉論域中已經(jīng)屬于正域的樣本.雖然通過(guò)去除正域樣本縮小了搜索空間，但整個(gè)約簡(jiǎn)算法時(shí)間復(fù)雜度仍為O(m||U|2)，其中m為屬性個(gè)數(shù)，|U|為樣本總個(gè)數(shù)，并且算法效率會(huì)受到數(shù)據(jù)分布情況的影響.為解決F2HARNRS算法鄰域計(jì)算的時(shí)間復(fù)雜度過(guò)高的問(wèn)題，Liu等人[4]在文獻(xiàn)[3,5]的基礎(chǔ)上提出了基于散列劃分桶縮小鄰域搜索空間的屬性快速約簡(jiǎn)算法(fast Hash attribute reduct algorithm,FHARA).該方法根據(jù)給定的鄰域決策系統(tǒng)NDS=〈U,C∪D,V,f〉及距離度量δ，利用散列映射將論域U中的樣本劃分到有限集合B0,B1,…,Bb中.樣本劃分情況如圖1所示：

Fig.1 The distribution of the buckets圖1 桶劃分示意圖

映射函數(shù)為Bk={xi|xi∈U∧┌f(x0,x1)/δ┐=k}，其中x0是由每個(gè)屬性的最小值組成的一個(gè)特殊樣本.以k作為散列鍵[4]組成的數(shù)據(jù)桶的空間分布類(lèi)似由多個(gè)大小不等的球嵌套而成的組合體,散列鍵k為映射后球的半徑.樣本分布在球面與球面之間，B0,B1,…,Bn就是以k作為半徑所得的n個(gè)數(shù)據(jù)桶.經(jīng)過(guò)桶劃分策略進(jìn)行樣本空間映射后，集合中的每個(gè)樣本的鄰域搜索范圍由原來(lái)的整個(gè)樣本空間減小到相鄰的3個(gè)數(shù)據(jù)桶，與F2HARNRS算法相比，F(xiàn)HARA明顯降低了樣本鄰域的搜索范圍，降低了算法的計(jì)算復(fù)雜度.

如圖1所示，在計(jì)算某個(gè)樣本xi的鄰域時(shí)，只需考慮xi所在桶以及相鄰2個(gè)桶內(nèi)的樣本.Liu等人[4]提出的散列分桶策略縮小了鄰域樣本存在的可能范圍，使得整個(gè)約簡(jiǎn)算法時(shí)間復(fù)雜度下降為O(m|U|2/k)，其中k為桶的個(gè)數(shù).然而，分析發(fā)現(xiàn)每個(gè)桶中依然存在大量不屬于xi鄰域的樣本，這意味著FHARA在計(jì)算樣本的鄰域時(shí)仍然存在很多冗余計(jì)算.以表1中的樣例數(shù)據(jù)為例，其中a,b,c,d為條件屬性，即特征(feature)；e為決策屬性，即標(biāo)簽(label).當(dāng)δ=0.1時(shí)，則有x0={0.17,0.11,0.27,0.33}，樣本的桶劃分情況為：B0={x7},B1={x1,x2,x3,x6},B2={x4},B3={x5,x8}.FHARA首先計(jì)算B0中樣本x7的鄰域.由桶劃分機(jī)制可知，在計(jì)算B0中樣本的鄰域時(shí)只需遍歷B1即可.記xi與xj之間的距離為D(xi,xj)，則D(x7,x1)=0.152，D(x7,x2)=0.148，D(x7,x3)=0.19，D(x7,x6)=0.093.當(dāng)計(jì)算出x7與x1的距離D(x7,x1)大于鄰域半徑δ時(shí)，系統(tǒng)可推斷x1不在鄰域范圍內(nèi).同理，x2,x3也不在鄰域范圍內(nèi).計(jì)算x7與x6的距離，發(fā)現(xiàn)D(x7,x6)小于鄰域半徑，但兩者擁有不同的決策值，可知x7為邊界區(qū)樣本；至此，B0中樣本的鄰域計(jì)算完畢.計(jì)算B1中樣本的鄰域，需要遍歷B0∪B1∪B2桶.首先計(jì)算樣本x1與x7的距離D(x1,x7).而D(x1,x7)與D(x7,x1)等價(jià)，故而沒(méi)有必要重復(fù)計(jì)算.可以看出，F(xiàn)HARA的鄰域計(jì)算過(guò)程中存在冗余計(jì)算.

Table 1 An Example Dataset表1 樣例數(shù)據(jù)

蔣云良等人[19]在文獻(xiàn)[3-5]的基礎(chǔ)上，采用迭代的方式求解樣本鄰域，即在每次迭代過(guò)程中只搜索Bk和Bk+1兩個(gè)桶，避免了FHARA中相鄰?fù)皟?nèi)樣本鄰域關(guān)系的重復(fù)計(jì)算問(wèn)題.但是該算法須計(jì)算Bk與Bk+1之間的完整鄰域關(guān)系，以便在下一次迭代過(guò)程中避免搜索Bk-1桶(即當(dāng)前迭代中的Bk桶).故而當(dāng)鄰域樣本分布在相鄰的多個(gè)桶中時(shí)，該算法的鄰域計(jì)算量較大.

文獻(xiàn)[3,5,19]均可利用鄰域粗糙集理論實(shí)現(xiàn)特征約簡(jiǎn).其中文獻(xiàn)[3,5]初步建立了特征約簡(jiǎn)的思路，即迭代貪心搜索并保留具有最大正域值的屬性；文獻(xiàn)[4]發(fā)現(xiàn)貪心搜索中正域計(jì)算時(shí)的鄰域搜索空間的遍歷具有盲目性，于是針對(duì)此提出了基于散列劃分桶的方法.該方法可以縮小鄰域搜索空間并避免部分冗余計(jì)算；文獻(xiàn)[19]也基于文獻(xiàn)[3,5]的算法框架，約束了正域計(jì)算過(guò)程中桶搜索的范圍，避免相鄰?fù)皟?nèi)樣本鄰域關(guān)系的重復(fù)計(jì)算問(wèn)題，從而進(jìn)一步提高了鄰域粗糙集特征約簡(jiǎn)的效率.但現(xiàn)有的特征約簡(jiǎn)算法中仍存在冗余計(jì)算.

針對(duì)當(dāng)前已有方法中存在的鄰域冗余計(jì)算問(wèn)題和鄰域計(jì)算量過(guò)大的問(wèn)題，本文提出基于鄰域?qū)ΨQ性及決策值過(guò)濾策略的屬性快速約簡(jiǎn)算法(EasiFFRA)，并在太湖實(shí)際采集的水質(zhì)監(jiān)測(cè)數(shù)據(jù)集合，以及多個(gè)UCI(University of California Irvine)國(guó)際標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，以驗(yàn)證本方法的有效性.本文的主要貢獻(xiàn)體現(xiàn)在3個(gè)方面：

1)通過(guò)散列表存儲(chǔ)鄰域計(jì)算過(guò)程中被判定為邊界區(qū)的樣本，減少了鄰域計(jì)算過(guò)程中的冗余計(jì)算量；

2)采用優(yōu)先搜索樣本所在桶的策略，提前發(fā)現(xiàn)鄰域樣本，從而加速正域的計(jì)算；

3)采用決策值過(guò)濾策略，減少了鄰域距離的計(jì)算次數(shù)，從而大幅降低算法的計(jì)算量；

對(duì)比實(shí)驗(yàn)表明：EasiFFRA在同等約束條件下有較大優(yōu)勢(shì)，可以在保持約簡(jiǎn)結(jié)果的情況下加快特征約簡(jiǎn)的速度.

2 鄰域粗糙集屬性約簡(jiǎn)機(jī)制

在已有的基于鄰域粗糙集的特征約簡(jiǎn)步驟中，算法通常需要遍歷并保留能夠引起最大正域樣本增量的特征，直到增加其他特征也無(wú)法引起正域集合的擴(kuò)大，算法停止.在該類(lèi)約簡(jiǎn)過(guò)程中，算法需要對(duì)所有未保留的特征進(jìn)行遍歷，并計(jì)算每種組合下的正域樣本集合.此過(guò)程是算法中計(jì)算量最大的步驟，存在計(jì)算冗余.本節(jié)介紹在文獻(xiàn)[4]的基礎(chǔ)上所提出的基于鄰域?qū)ΨQ性和決策值過(guò)濾策略的EasiFFRA特征快速約簡(jiǎn)算法.

2.1 基于鄰域?qū)ΨQ性的約簡(jiǎn)機(jī)制

鄰域具有對(duì)稱性[3]，該性質(zhì)可用于避免大量現(xiàn)有工作中的冗余正域計(jì)算操作即在度量空間和δ鄰域中，有：

δ(xi)≠?,?xi∈δ(xi),

(1)

xj∈δ(xi)?xi∈δ(xj),

(2)

(3)

也就是說(shuō)，如果xi是xj的鄰域樣本，那么xj也是xi的鄰域樣本，如圖2所示:

Fig.2 Neighborhood symmetry圖2 鄰域?qū)ΨQ性示意圖

在鄰域粗糙集理論中，數(shù)據(jù)集合可以分為3個(gè)區(qū)間，即A類(lèi)樣本正域、B類(lèi)樣本正域和邊界區(qū).其中正域樣本是在數(shù)據(jù)集中可以根據(jù)其自身特征分布明確分類(lèi)的樣本；而邊界區(qū)的樣本則是無(wú)法十分明確歸類(lèi)的樣本，即存在一定的混淆.在判斷某樣本xi是否為正域元素的過(guò)程中，需要遍歷xi鄰域范圍內(nèi)的所有樣本的標(biāo)簽值.若在xi鄰域范圍內(nèi)存在與其標(biāo)簽值不同的樣本，則xi為邊界區(qū)樣本；若xi鄰域內(nèi)所有的樣本均與其標(biāo)簽值相同，則xi為正域樣本.

不同類(lèi)別樣本正域和邊界區(qū)中樣本的并集即為整個(gè)數(shù)據(jù)集.邊界區(qū)數(shù)據(jù)集合和正域中數(shù)據(jù)集合不相交.

根據(jù)正域的定義及其計(jì)算規(guī)則，在同一屬性子集條件下計(jì)算樣本xi的鄰域時(shí)，如果xj在xi的鄰域范圍之內(nèi)，且xj與xi的決策屬性不同(不屬于同一類(lèi)別)，則xi不可能屬于正域集合.同理，由于對(duì)稱性xj也不可能屬于正域集合.根據(jù)這一特性，通過(guò)一個(gè)散列表Hs來(lái)存儲(chǔ)尚未計(jì)算過(guò)鄰域但已經(jīng)判定為邊界區(qū)的樣本子集.比如若判定xj導(dǎo)致xi為邊界區(qū)樣本，則將xj存入散列表Hs，在后序判斷xj是否為正域樣本時(shí)，將首先檢索散列表Hs中是否存在xj的記錄，如果存在則無(wú)需檢索任何桶中的樣本，可直接將xj判別為邊界區(qū)樣本，從而避免了大量冗余的鄰域計(jì)算.

由散列分桶映射函數(shù)可知，散列桶劃分策略使得距離相近的樣本以更大概率被劃分到同一個(gè)桶中，即樣本xi(xi∈Bk)的鄰域樣本出現(xiàn)Bk中的概率大于出現(xiàn)在Bk+1和Bk-1桶的概率.這也意味著B(niǎo)k桶內(nèi)出現(xiàn)由xi導(dǎo)致的邊界區(qū)樣本的概率大于Bk+1，Bk-1中出現(xiàn)由xi導(dǎo)致的邊界區(qū)樣本的概率.所以在改進(jìn)算法中，優(yōu)先檢索Bk桶.又因?yàn)锽k-1中的非鄰域樣本在上一輪迭代過(guò)程中已經(jīng)存儲(chǔ)在散列表Hs中，無(wú)需再次檢驗(yàn)存儲(chǔ)，所以可以在檢索Bk后直接檢索Bk+1桶.基于上述桶檢索順序，并結(jié)合鄰域的對(duì)稱性，可以盡早的發(fā)現(xiàn)盡可能多的邊界區(qū)樣本，減少不必要的檢索計(jì)算.在后續(xù)的實(shí)驗(yàn)部分中將對(duì)其進(jìn)行進(jìn)一步的論述與驗(yàn)證.

2.2 基于決策值過(guò)濾策略的約簡(jiǎn)機(jī)制

在已有鄰域粗糙集特征約簡(jiǎn)算法的正域計(jì)算步驟中，當(dāng)判斷樣本xi是否處于正域時(shí)，需遍歷樣本集中所有其他數(shù)據(jù)xj，并計(jì)算xi與所有xj之間的距離，而不論xj和xi的決策屬性類(lèi)別是否相同、是否處于同一個(gè)鄰域內(nèi).這種樸素的計(jì)算方法中存在若干冗余計(jì)算：

在樣本xi正域的求解過(guò)程中，若其δ鄰域中存在一個(gè)決策屬性不同的樣本，則xi將被判別為邊界區(qū)樣本.只有當(dāng)xi的δ鄰域中所有樣本都與其決策屬性相同時(shí)，xi才會(huì)被劃分為正域樣本.故而可以將樸素的遍歷過(guò)程簡(jiǎn)化為僅關(guān)注xi的δ正域內(nèi)是否存在異類(lèi)決策屬性的樣本即可.

在本文提出的算法中，僅遍歷與樣本xi決策屬性類(lèi)別不同的樣本子集，計(jì)算并考察該樣本子集中各樣本點(diǎn)xj與xi間的距離D(xi,xj)，此時(shí)有2種情況：

1)若D(xi,xj)>δ，則xj不會(huì)對(duì)xi的正域判別產(chǎn)生影響；

2)若D(xi,xj)<δ，則由于xj的影響，xi將無(wú)法被歸類(lèi)為正域元素，并被劃分入邊界區(qū).

綜上，在判斷xi是否為正域樣本時(shí)，只需考慮與xi決策屬性不同的樣本子集.該集合中與xi決策屬性相同的樣本不會(huì)對(duì)xi的正域?qū)傩耘袛喈a(chǎn)生影響，可以直接忽略，此方法即為決策值過(guò)濾策略.

例如在表1的樣例數(shù)據(jù)中，可以首先比較x7與x1,x2,x3的決策屬性，發(fā)現(xiàn)決策屬性均相等，便可直接省去x7與x1,x2,x3間的距離計(jì)算.雖然決策值過(guò)濾策略并未降低算法的時(shí)間復(fù)雜度，但是可以減少大量樣本間的距離計(jì)算，使得整個(gè)約簡(jiǎn)算法的計(jì)算開(kāi)銷(xiāo)大幅下降，正域的求解效率也就得以提高.

實(shí)驗(yàn)表明:對(duì)于決策屬性取值情況較少的數(shù)據(jù)集，尤其是二分類(lèi)的情況，通過(guò)決策值過(guò)濾策略帶來(lái)的計(jì)算效率提升十分明顯.

2.3 屬性約簡(jiǎn)改進(jìn)算法

結(jié)合鄰域?qū)ΨQ性和決策值過(guò)濾機(jī)制，下面給出正域求解算法的偽碼，如算法1所示.

算法1.基于對(duì)稱及決策過(guò)濾的快速約簡(jiǎn)算法.

輸入：U,P,D,δ；

輸出：F={F1,F2,…,F|U|}.

①Fi←0,1,…,|U|；

② for eachxi∈Udo

③ Hash(P(xi),Bk)；

④ end for

⑤ for eachxi∈Udo

⑥flag←0；

⑦ ifxi∈Non_Posthen

⑧flag←1；

⑨ else

⑩ for eachxi∈Bk∪Bk+1do

其中，由于Bk-1桶的處理與Bk∪Bk+1類(lèi)似，唯一區(qū)別是無(wú)需將Bk-1桶的邊界區(qū)樣本存入散列表Hs(因?yàn)檫@些邊界區(qū)樣本在上一輪迭代過(guò)程中已經(jīng)存入散列表Hs)，故而其操作過(guò)程在算法中省略.

算法1可判斷樣本是否為正域樣本，其流程如圖3所示，其中以xi,xj的單次比較為例.下面結(jié)合流程圖對(duì)算法1進(jìn)行闡述.

算法1首先判斷xi是否存在于記錄邊界區(qū)樣本的散列表Hs中，如果存在則說(shuō)明xi在前面的迭代過(guò)程中曾導(dǎo)致其他樣本成為邊界區(qū)樣本.根據(jù)鄰域?qū)ΨQ性，xi也不是正域樣本，故而被存入散列表Hs中.此時(shí)可直接判斷xi為邊界區(qū)樣本，并將xi的標(biāo)志位flag設(shè)置為1.其中標(biāo)志位為記錄該樣本是否為邊界區(qū)樣本的標(biāo)志位.

Fig.3 Positive region computation algorithm圖3 正域的計(jì)算流程圖

如果xi不在散列表Hs中則需要檢索鄰域空間的樣本.假設(shè)檢索到樣本xj，首先判斷xi和xj的決策值是否相等.如果相等則根據(jù)決策值過(guò)濾機(jī)制可無(wú)需繼續(xù)計(jì)算xi和xj之間的距離，可以直接轉(zhuǎn)向其他樣本的檢索；如果決策值不相等則繼續(xù)計(jì)算鄰域距離D(xi,xj)；

如果D(xi,xj)>δ，則說(shuō)明xi不是xj的鄰域樣本，它對(duì)xi是否為正域樣本的判斷無(wú)影響，所以無(wú)需修改標(biāo)志位；如果D(xi,xj)≤δ則說(shuō)明xi為邊界區(qū)樣本，則將標(biāo)志位置為1，根據(jù)鄰域?qū)ΨQ性可知，xj也為邊界區(qū)樣本，需將xj存入散列表Hs.

3 實(shí)驗(yàn)分析

為了驗(yàn)證本文提出的EasiFFRA算法的正確性與約簡(jiǎn)的高效性，本節(jié)將其與現(xiàn)有方法中特征約簡(jiǎn)時(shí)間效率最高的FHARA方法進(jìn)行對(duì)比實(shí)驗(yàn).實(shí)驗(yàn)內(nèi)容包括算法的正確性驗(yàn)證以及算法的高效性驗(yàn)證.實(shí)驗(yàn)數(shù)據(jù)包括本研究組實(shí)際部署與監(jiān)測(cè)的水質(zhì)監(jiān)測(cè)系統(tǒng)藻類(lèi)數(shù)據(jù)集blue green algae[20]，以及UCI公開(kāi)數(shù)據(jù)集中的12組樣本.實(shí)驗(yàn)中使用的數(shù)據(jù)集名稱、樣本數(shù)量、特征維度和決策屬性數(shù)量信息如表2所示.

實(shí)驗(yàn)中，所有算法均選取歐氏距離作為正域計(jì)算度量函數(shù)，測(cè)試運(yùn)行在相同的軟件和硬件環(huán)境下CPU為Intel Core i5-4590 CPU@3.30 GHz;RAM為8.00 GB;Windows 7 OS;python 2.7.10.為保證數(shù)據(jù)的有效性和結(jié)果的可重復(fù)性，結(jié)論中的約簡(jiǎn)結(jié)果以及特征約簡(jiǎn)速度數(shù)據(jù)均為10次相同環(huán)境下運(yùn)行結(jié)果的平均值.

Table 2 Datasets Used in Experiments表2 實(shí)驗(yàn)數(shù)據(jù)集

3.1 算法正確性驗(yàn)證

為驗(yàn)證EasiFFRA算法的正確性，實(shí)驗(yàn)同時(shí)在algea以及12個(gè)UCI數(shù)據(jù)集上同時(shí)執(zhí)行FHARA算法以及EasiFFRA算法，并比較它們的約簡(jiǎn)結(jié)果.約簡(jiǎn)結(jié)果如表3所示.

從表3可以看到，EasiFFRA和FHARA在所有數(shù)據(jù)集上的約簡(jiǎn)結(jié)果均相同，又因?yàn)槲墨I(xiàn)[4]中FHARA的正確性驗(yàn)證、可驗(yàn)證本文提出的EasiFFRA算法約簡(jiǎn)結(jié)果的一致性與正確性.為進(jìn)一步驗(yàn)證EasiFFRA約簡(jiǎn)結(jié)果的正確性，實(shí)驗(yàn)同時(shí)比較經(jīng)過(guò)EasiFFRA約簡(jiǎn)、經(jīng)過(guò)常用的隨機(jī)森林特征約簡(jiǎn)和未經(jīng)任何約簡(jiǎn)的數(shù)據(jù)集的5折交叉分類(lèi)精度，結(jié)果如圖4所示.其中使用SVM作為分類(lèi)器.

Table 3 Attributes Selected by Two Reduct Algorithms表3 2種算法約簡(jiǎn)結(jié)果

Fig.4 Classification accuracy of SVM in several datasets with EasiFFRA reduction,no-reduction and random forest reduction圖4 EasiFFRA與無(wú)約簡(jiǎn)及隨機(jī)森林約簡(jiǎn)后各數(shù)據(jù)集精度對(duì)比

從圖4可以看到，建立在經(jīng)過(guò)特征約簡(jiǎn)后的數(shù)據(jù)集上的分類(lèi)器的識(shí)別精度優(yōu)于未經(jīng)約簡(jiǎn)的原始數(shù)據(jù)集的精度.而在約簡(jiǎn)算法中，經(jīng)過(guò)EasiFFRA處理的分類(lèi)器精度普遍高于傳統(tǒng)的隨機(jī)森林約簡(jiǎn)算法的結(jié)果.這也從另一方面驗(yàn)證了本文提出的EasiFFRA特征約簡(jiǎn)算法的正確性.

3.2 算法約簡(jiǎn)效率對(duì)比實(shí)驗(yàn)

為驗(yàn)證EasiFFRA的特征約簡(jiǎn)的高效性，實(shí)驗(yàn)分別統(tǒng)計(jì)EasiFFRA以及對(duì)比方法執(zhí)行過(guò)程中的樣本間距離計(jì)算次數(shù)、整體算法運(yùn)行時(shí)間以及算法運(yùn)行時(shí)間隨樣本數(shù)量增加而延長(zhǎng)的計(jì)算耗時(shí).

1)計(jì)算EasiFFRA在不同桶搜索順序下樣本距離的計(jì)算總量，以及FHARA在相同數(shù)據(jù)集下的樣本間距離計(jì)算次數(shù).如表4所示.

表4表頭中EasiFFRA后跟隨的3位數(shù)字代表EasiFFRA算法在不同桶搜索順序下的算法，如012代表依次搜索Bk-1，Bk，Bk+1桶.從表4可知，在桶搜索順序的選擇中，優(yōu)先搜索Bk時(shí)的樣本距離計(jì)算次數(shù)與開(kāi)銷(xiāo)最少；對(duì)比EasiFFRA與FHARA的距離計(jì)算次數(shù)可知，EasiFFRA算法在6種桶搜索順序下的距離計(jì)算開(kāi)銷(xiāo)均少于FHARA算法.特別在wilt，magic，credit，shuttle等決策屬性種類(lèi)較少的數(shù)據(jù)集上的效率提升最多，在seg，pen等決策值種類(lèi)較多的數(shù)據(jù)集上計(jì)算量也有著明顯的降低.以EasiFFRA102的桶搜索順序?yàn)槔?，EasiFFRA在pen上的距離計(jì)算次數(shù)小于FHARA距離計(jì)算次數(shù)的1/3，在seg上的計(jì)算次數(shù)小于FHARA計(jì)算次數(shù)的 1/4，在algea上的距離計(jì)算次數(shù)不到 FHARA 距離計(jì)算次數(shù)的 1/19.

2)計(jì)算EasiFFRA 在相同條件下的算法執(zhí)行時(shí)間.為驗(yàn)證算法的普適性和有效性，按照鄰域半徑δ將實(shí)驗(yàn)分為0.08和0.15這2組.實(shí)驗(yàn)結(jié)果如圖5所示.

為直觀展示 EasiFFRA 的約簡(jiǎn)高效性，實(shí)驗(yàn)統(tǒng)計(jì)了2種方法的約簡(jiǎn)計(jì)算時(shí)間(單位為s)，如表5所示.

從表5看到，相對(duì)于現(xiàn)有的FHARA方法，不論在δ=0.08還是δ=0.15的情況下，本文提出的EasiFFRA算法在12個(gè)驗(yàn)證數(shù)據(jù)集上均具有更高的約簡(jiǎn)效率，且對(duì)于決策值種類(lèi)較少的數(shù)據(jù)集提升更為明顯.EasiFFRA在12個(gè)數(shù)據(jù)集上的平均約簡(jiǎn)時(shí)間僅為對(duì)比方法FHARA的24.45%.此外，在algae數(shù)據(jù)集中樣本不平衡問(wèn)題十分嚴(yán)重，其中決策值為0的樣本占整體數(shù)據(jù)量的92.34%，其他9個(gè)決策值的樣本共占整體數(shù)據(jù)量的7.66%，可見(jiàn)EasiFFRA在該類(lèi)決策值種類(lèi)多且分布不平衡的情況下也能夠達(dá)到很好的約簡(jiǎn)性能，驗(yàn)證了其良好的適用性.

Fig.5 Reduct calculation time cost of FHARA and EasiFFRA on 12 UCI datasets with δ equals 0.08 and 0.15圖5 δ=0.08和δ=0.15 時(shí)，EasiFARA和FHARA算法在12個(gè)UCI數(shù)據(jù)集上的約簡(jiǎn)時(shí)間

Table 5 Ratio of Reduct Calculation Time Cost of FHARA and EasiFFRA表5 EasiFFRA與FHARA約簡(jiǎn)時(shí)間比

3)實(shí)驗(yàn)在保持鄰域半徑不變的情況下，對(duì)比EasiFFRA和FHARA算法在隨樣本量增加而延長(zhǎng)的算法耗時(shí).在本實(shí)驗(yàn)中，除了用到的12個(gè)數(shù)據(jù)集外，實(shí)驗(yàn)還從UCI數(shù)據(jù)集中提取了含有250 000個(gè)樣本的susy數(shù)據(jù)子集來(lái)驗(yàn)證EasiFFRA在大數(shù)據(jù)集下的性能表現(xiàn).實(shí)驗(yàn)結(jié)果如圖6和表6～9所示.

Fig.6 Calculation time cost of EasiFFRA and FHARA on 9 datasets with increasing sample size圖6 FHARA和EasiFFRA在9個(gè)數(shù)據(jù)集上隨著樣本數(shù)量的增加所消耗的時(shí)間

Table 6 Calculation Time Cost of EasiFFRA and FHARA on algae表6 EasiFFRA和FHARA在algae數(shù)據(jù)集上的約簡(jiǎn)時(shí)間

Table 7 Calculation Time Cost of EasiFFRA and FHARA on magic表7 EasiFFRA和FHARA在magic數(shù)據(jù)集上的約簡(jiǎn)時(shí)間

Table 8 Calculation Time Cost of EasiFFRA and FHARA on white表8 EasiFFRA和FHARA在white數(shù)據(jù)集上的約簡(jiǎn)時(shí)間

從實(shí)驗(yàn)結(jié)果中可以看到，隨著樣本量的增加，EasiFFRA在這13個(gè)數(shù)據(jù)集上的約簡(jiǎn)效率均優(yōu)于FHARA.尤其在shuttle,susy等決策值種類(lèi)較少且數(shù)據(jù)量大的場(chǎng)景下，EasiFFRA的約簡(jiǎn)耗時(shí)明顯低于FHARA.上述現(xiàn)象說(shuō)明EasiFFRA算法能夠更好地適用于大數(shù)據(jù)應(yīng)用場(chǎng)景.

4 結(jié) 論

物聯(lián)網(wǎng)場(chǎng)景中的大量感知數(shù)據(jù)的特征具有高維、冗余、非線性等特點(diǎn).冗余特征和無(wú)關(guān)特征會(huì)導(dǎo)致分類(lèi)模型準(zhǔn)確率下降，也會(huì)造成計(jì)算資源浪費(fèi)，因此有必要對(duì)數(shù)據(jù)集進(jìn)行降維預(yù)處理.相對(duì)于其他降維算法，鄰域粗糙集特征約簡(jiǎn)算法能夠在保持?jǐn)?shù)據(jù)可分性的前提下刪除無(wú)關(guān)、弱相關(guān)和冗余特征，具有很大的應(yīng)用優(yōu)勢(shì)，但其較大的計(jì)算復(fù)雜性成為算法實(shí)際部署的瓶頸.本文針對(duì)鄰域計(jì)算時(shí)間復(fù)雜度過(guò)高、計(jì)算量過(guò)大的問(wèn)題，提出了基于鄰域關(guān)系對(duì)稱性及決策值過(guò)濾策略的特征約簡(jiǎn)算法EasiFFRA.該算法優(yōu)先檢索鄰域樣本分布相對(duì)集中的相鄰?fù)癇k，采用散列表存儲(chǔ)當(dāng)前屬性子集條件下不可能成為正域樣本的方法，縮小鄰域檢索范圍；并通過(guò)決策值過(guò)濾策略過(guò)濾掉與當(dāng)前樣本具有相同決策值的冗余樣本，減少了鄰域計(jì)算時(shí)的距離計(jì)算次數(shù)，從而降低算法的計(jì)算量.對(duì)比實(shí)驗(yàn)表明EasiFFRA避免了大量冗余計(jì)算，算法效率明顯優(yōu)于對(duì)比方法，能更好地適應(yīng)復(fù)雜的物聯(lián)網(wǎng)數(shù)據(jù)分析場(chǎng)景.