改進K-means結合深度學習的不完備信息選取

宋新鵬，張彥波

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

1 引言

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

基于現有研究，本文結合基礎理論建立不完備信息系統的粗糙集，根據信息的決策域，求得不完備信息系統粗糙集的上近似值和下近似值。并將信息擴展到三個維度，通過對信息聚類，將相近度高的樣本劃分到正同域中，使樣本處在聚類的中心位置，并結合深度學習，通過對樣本的反復訓練，增強選取目標的有效性。

2 不完備信息選取

信息具備隨機性、有噪音、規模大等特性，信息選取是選擇出用戶敏感且有效的信息，決策管理者可以通過方法分析處理相關信息[7-9]。信息系統的另一種替代詞為知識表達系統，通常可描述為四元方程，用公式可表示為

S=(U，A，V，f)

(1)

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

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

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

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

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

(2)

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

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

(3)

根據貝葉斯公式，可以求得對于?xi∈U，應用動作集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)

根據最小化規則，當滿足如下條件時

(5)

可推導得出

α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的一種行為，根據以上信息的決策域，可以求得不完備信息系統粗糙集的上近似值和下近似值，用公式分別表示為

(8)

其中

(9)

3 改進K-means聚類算法的信息選取

測量樣本之間的距離是信息聚類中至關重要的過程，本文將信息樣本間的距離拓展到3個維度：正同度、負反度和差異度，這樣便可以有效的解決缺失值對不完備信息系統的影響。基于信息粒子中的正同度粒子集、負反度粒子集和差異度粒子集，本文采用正同域、負反域和邊界域來表示不完備信息的聚類結果。其中正同域表示樣本屬于這一類，用Yz表示；負反域表示樣本不屬于這一類，用Yf表示；邊界域表示樣本可能屬于這一類，用Yb表示。通過對信息聚類，將相近度高的樣本劃分到正同域中，使樣本處在聚類的中心位置；將相似度低的樣本劃分到邊界域；將相似度極低的樣本劃分到負反域。這三個域應滿足如下條件

(10)

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

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

(11)

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

(12)

通過對初步聚類的計算結果詳細劃分，可以分離正同域和邊界域。假設正同度的閾值和負反度的閾值分別為ε和μ，計算該樣本所在的類別中聚類中心的關聯性。通過比較正同度和負反度與閾值大小之間的關系，依次將樣本信息分配到其對應類簇的正同域和邊界域中，公式表示為

(13)

4 深度學習

深度學習是以當前的信息為依據，采取從信息系統中獲取相似度較高信息的過程。表示在當前信息狀態Ht下，信息系統采取行為Et，根據信息轉移函數P，信息狀態由Ht轉移到Ht+1，同時信息系統會根據當前狀態Ht下采取行為Et的情況，反饋回一個信號Gt。通過不斷訓練，求得最優策略。深度學習框架如圖1所示。

圖1 深度學習框圖

深度學習是一種經典的深度強化學習算法，可以感知不完備信息，根據深度學習部分提供的信息作出決策，從而完成信息的映射。雖然深度學習可以近似評估信息網絡值，然而它卻破壞了信息網絡值的無條件收斂性，因此本文從以下兩方面進行了優化。

一方面，在深度學習中由于智能體系與信息系統不斷迭代交互，上一個信息狀態與當前信息狀態相似度極高，導致神經網絡擬合時無法收斂。因此在深度學習中增加一個記憶庫，用來存儲這一段時間內的訓練數據。在每次學習過程中，深度學習算法都會從記憶庫中隨機選擇一些樣本數據，輸送到神經網絡中。為了提高訓練樣本的利用率，將每次產生的新訓練樣本與舊訓練樣本混合更新，從而混亂樣本間的關聯性。

另一方面，當在深度學習中建立了一個與當前評估網絡結構完全相同，而參數不同的目標神經網絡時，當前的目標值Q只能由評估網絡預測出來，這種方法可以有效的降低當前值與目標值的關聯性，損失函數用公式可表示為

(14)

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

(15)

5 仿真實驗與結果分析

(16)

式中，關于d和l項的計算分別為

(17)

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

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

(18)

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

圖2 正同域聚類結果隨參數α、β和γ變化的波動圖像

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

表1 正同域最優參數下的性能分析

表2 正同域和邊界域最優參數下的性能分析

6 結束語