改進(jìn)K-means結(jié)合深度學(xué)習(xí)的不完備信息選取

宋新鵬，張彥波

(1.河南大學(xué)信息化管理辦公室，河南 開封，475004) 2.河南大學(xué)物理與電子學(xué)院，河南 開封，475004)

1 引言

隨著信息技術(shù)的高速發(fā)展，現(xiàn)實生活中的數(shù)據(jù)信息量越來越大。由于數(shù)據(jù)信息在獲取過程中的有限性，及測量過程中的誤差性等原因，導(dǎo)致數(shù)據(jù)理解不全面，所掌握的數(shù)據(jù)信息通常不完備[1-2]。同時很多信息常常具有屬性偏好，如學(xué)生成績、工作效率、產(chǎn)品質(zhì)量、投資回報等等，這些屬性值會導(dǎo)致偏好次序的形成[3]。傳統(tǒng)的粗糙集理論在數(shù)據(jù)分析方面起了很大的作用，然而該理論對噪聲數(shù)據(jù)處理效果不好，在多粒度的信息系統(tǒng)中，信息的多屬性值難以獲取或經(jīng)常丟失，因此對于不完備信息系統(tǒng)進(jìn)行研究具有重要的意義，大量學(xué)者也在傳統(tǒng)的粗糙集模型基礎(chǔ)上進(jìn)行了改進(jìn)。文獻(xiàn)[4]提出一種不完備鄰域決策粗糙集的最小化代價屬性簡約算法，該方法在連續(xù)型數(shù)據(jù)系統(tǒng)中引入不完備鄰域關(guān)系，利用二元關(guān)系對信息集進(jìn)行重新構(gòu)造，實驗結(jié)果表明，該方法具有較好的約簡性能，然后對于更加復(fù)雜的信息系統(tǒng)模型優(yōu)勢不明顯。文獻(xiàn)[5]提出一種基于信息熵的不完備數(shù)據(jù)特征選擇算法，該方法以不完備信息作為特征準(zhǔn)則，通過數(shù)據(jù)特征對熵值進(jìn)行分析，解決了數(shù)據(jù)間的特征相關(guān)問題。實驗結(jié)果表明，該算法具有較高的選擇速度和正確率，然而由于空值的影響，該方法不能直接對不完備信息進(jìn)行分析處理。文獻(xiàn)[6]提出一種面向不完備信息系統(tǒng)的集對K-means聚類算法，該方法通過集對度量方法，取得初步聚類數(shù)據(jù)，然后將其分到相應(yīng)域的邊界域，最后通過選取UCI數(shù)據(jù)庫的多個數(shù)據(jù)集進(jìn)行實驗評價。實驗結(jié)果表明，該方法具有較好的聚類性能，然而由于信息變化對聚類算法的影響較大，該方法不能更好的取得合適參數(shù)。

基于現(xiàn)有研究，本文結(jié)合基礎(chǔ)理論建立不完備信息系統(tǒng)的粗糙集，根據(jù)信息的決策域，求得不完備信息系統(tǒng)粗糙集的上近似值和下近似值。并將信息擴(kuò)展到三個維度，通過對信息聚類，將相近度高的樣本劃分到正同域中，使樣本處在聚類的中心位置，并結(jié)合深度學(xué)習(xí)，通過對樣本的反復(fù)訓(xùn)練，增強(qiáng)選取目標(biāo)的有效性。

2 不完備信息選取

信息具備隨機(jī)性、有噪音、規(guī)模大等特性，信息選取是選擇出用戶敏感且有效的信息，決策管理者可以通過方法分析處理相關(guān)信息[7-9]。信息系統(tǒng)的另一種替代詞為知識表達(dá)系統(tǒng)，通?？擅枋鰹樗脑匠?，用公式可表示為

S=(U，A，V，f)

(1)

其中，U表示信息非空有限樣本集；A表示信息非空有限屬性集；V表示U關(guān)于A的信息值域集合；f表示關(guān)于信息的函數(shù)；以上變量可具體描述為

U={x1，x2，x3，…，xn}

A={a1，a2，a3，…，am}

V={V1，V2，V3，…，Vm}

f：vis=f(xi，as)∈Vs

(2)

其中，n表示信息非空有限樣本集中數(shù)據(jù)樣本的個數(shù)；m表示信息非空有限屬性集中屬性值的個數(shù)；Vs表示屬性as(1≤s≤m)的值域；vis表示樣本xi通過信息函數(shù)f在屬性as上的計算結(jié)果。如果存在屬性值缺失，那么信息系統(tǒng)便是不完備的系統(tǒng)。

與傳統(tǒng)的粗糙集模型相似，不完備信息系統(tǒng)的粗糙集具有相同的表達(dá)形式，對于樣本中的xi，假設(shè)鄰域類為nφ(xi)、狀態(tài)集為Q={X，Xd}，其中X?U，Xd為X的補(bǔ)集，在不完備信息系統(tǒng)中，樣本xi的狀態(tài)集概率用公式可表示為

(3)

根據(jù)貝葉斯公式，可以求得對于?xi∈U，應(yīng)用動作集R={ap，ab，an}的三種行為決策公式為

Costp(xi)=αpp·p(X|nφ(xi))+αpn·p(Xd|nφ(xi))

Costb(xi)=αbp·p(X|nφ(xi))+αbn·p(Xd|nφ(xi))

Costn(xi)=αnp·p(X|nφ(xi))+αnn·p(Xd|nφ(xi))

(4)

根據(jù)最小化規(guī)則，當(dāng)滿足如下條件時

(5)

可推導(dǎo)得出

αpp·p(X|nφ(xi))+αpn·(1-p(Xd|nφ(xi)))

≤αbp·p(X|nφ(xi))+αbn·(1-p(Xd|nφ(xi)))

(6)

此時滿足

(7)

其中，T(X)表示樣本xi的一種行為，根據(jù)以上信息的決策域，可以求得不完備信息系統(tǒng)粗糙集的上近似值和下近似值，用公式分別表示為

(8)

其中

(9)

3 改進(jìn)K-means聚類算法的信息選取

測量樣本之間的距離是信息聚類中至關(guān)重要的過程，本文將信息樣本間的距離拓展到3個維度：正同度、負(fù)反度和差異度，這樣便可以有效的解決缺失值對不完備信息系統(tǒng)的影響?；谛畔⒘Ｗ又械恼攘Ｗ蛹⒇?fù)反度粒子集和差異度粒子集，本文采用正同域、負(fù)反域和邊界域來表示不完備信息的聚類結(jié)果。其中正同域表示樣本屬于這一類，用Yz表示；負(fù)反域表示樣本不屬于這一類，用Yf表示；邊界域表示樣本可能屬于這一類，用Yb表示。通過對信息聚類，將相近度高的樣本劃分到正同域中，使樣本處在聚類的中心位置；將相似度低的樣本劃分到邊界域；將相似度極低的樣本劃分到負(fù)反域。這三個域應(yīng)滿足如下條件

(10)

其中，Yi表示類簇。通過上式可以看出，每類簇的正同域Yz都不能為空集，任何一個樣本最多只能屬于一類簇的正同域。

針對數(shù)據(jù)缺失的不完備信息系統(tǒng)，對缺失的屬性值進(jìn)行集對分析。通過正同域、負(fù)反域和邊界域來表示一種聚類。針對這3種劃分關(guān)系，本文將K-means聚類分為兩個階段，第1階段：構(gòu)造正同域和邊界域的信息集合；第2階段：分離正同域和邊界域的信息集合。根據(jù)集對距離可以求得每個樣本最近的聚類中心，假設(shè)樣本xi已經(jīng)被劃分到最近的了類簇Yi=Yi∪{xi}，在迭代過程中，新聚類中心用公式可表示為

(11)

其中，x∈Yj，x={t1，t2，…，tn}，j=1，2，…，k，|Yj|表示類簇Yi的信息元素個數(shù)。通過以上過程聚類的初步結(jié)果計算完畢，可以將類簇的樣本分離成兩種類型，公式表示為

(12)

通過對初步聚類的計算結(jié)果詳細(xì)劃分，可以分離正同域和邊界域。假設(shè)正同度的閾值和負(fù)反度的閾值分別為ε和μ，計算該樣本所在的類別中聚類中心的關(guān)聯(lián)性。通過比較正同度和負(fù)反度與閾值大小之間的關(guān)系，依次將樣本信息分配到其對應(yīng)類簇的正同域和邊界域中，公式表示為

(13)

4 深度學(xué)習(xí)

深度學(xué)習(xí)是以當(dāng)前的信息為依據(jù)，采取從信息系統(tǒng)中獲取相似度較高信息的過程。表示在當(dāng)前信息狀態(tài)Ht下，信息系統(tǒng)采取行為Et，根據(jù)信息轉(zhuǎn)移函數(shù)P，信息狀態(tài)由Ht轉(zhuǎn)移到Ht+1，同時信息系統(tǒng)會根據(jù)當(dāng)前狀態(tài)Ht下采取行為Et的情況，反饋回一個信號Gt。通過不斷訓(xùn)練，求得最優(yōu)策略。深度學(xué)習(xí)框架如圖1所示。

圖1 深度學(xué)習(xí)框圖

深度學(xué)習(xí)是一種經(jīng)典的深度強(qiáng)化學(xué)習(xí)算法，可以感知不完備信息，根據(jù)深度學(xué)習(xí)部分提供的信息作出決策，從而完成信息的映射。雖然深度學(xué)習(xí)可以近似評估信息網(wǎng)絡(luò)值，然而它卻破壞了信息網(wǎng)絡(luò)值的無條件收斂性，因此本文從以下兩方面進(jìn)行了優(yōu)化。

一方面，在深度學(xué)習(xí)中由于智能體系與信息系統(tǒng)不斷迭代交互，上一個信息狀態(tài)與當(dāng)前信息狀態(tài)相似度極高，導(dǎo)致神經(jīng)網(wǎng)絡(luò)擬合時無法收斂。因此在深度學(xué)習(xí)中增加一個記憶庫，用來存儲這一段時間內(nèi)的訓(xùn)練數(shù)據(jù)。在每次學(xué)習(xí)過程中，深度學(xué)習(xí)算法都會從記憶庫中隨機(jī)選擇一些樣本數(shù)據(jù)，輸送到神經(jīng)網(wǎng)絡(luò)中。為了提高訓(xùn)練樣本的利用率，將每次產(chǎn)生的新訓(xùn)練樣本與舊訓(xùn)練樣本混合更新，從而混亂樣本間的關(guān)聯(lián)性。

另一方面，當(dāng)在深度學(xué)習(xí)中建立了一個與當(dāng)前評估網(wǎng)絡(luò)結(jié)構(gòu)完全相同，而參數(shù)不同的目標(biāo)神經(jīng)網(wǎng)絡(luò)時，當(dāng)前的目標(biāo)值Q只能由評估網(wǎng)絡(luò)預(yù)測出來，這種方法可以有效的降低當(dāng)前值與目標(biāo)值的關(guān)聯(lián)性，損失函數(shù)用公式可表示為

(14)

-Q(Ht，Et;θ))?Q(Ht，Et;θ)

(15)

5 仿真實驗與結(jié)果分析

(16)

式中，關(guān)于d和l項的計算分別為

(17)

其中，TWCi表示屬于樣本Ci，且正確聚類到這類信息的個數(shù)；FWCi表示不屬于樣本Ci，但錯誤聚類到這類信息的個數(shù)；FMCi表示屬于樣本錯誤聚類的其他類信息個數(shù)。

準(zhǔn)確率Acc：表示信息的聚類效果，準(zhǔn)確率越高，聚類效果越好。用公式可表示為

(18)

其中，φi表示類簇Yi中正確劃分的樣本信息個數(shù)；n表示樣本信息總數(shù)。

圖2 正同域聚類結(jié)果隨參數(shù)α、β和γ變化的波動圖像

圖3 正同域和邊界域的聚類結(jié)果隨參數(shù)α、β和γ變化的波動圖像

表1 正同域最優(yōu)參數(shù)下的性能分析

表2 正同域和邊界域最優(yōu)參數(shù)下的性能分析

6 結(jié)束語