不完備多視圖的在線反向圖正則化聚類*

鄧萬宇 耿美娜 李建強(qiáng)

（西安郵電大學(xué)計(jì)算機(jī)學(xué)院 西安 710121）

1 引言

現(xiàn)今，隨著信息技術(shù)、計(jì)算機(jī)技術(shù)以及互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展，獲取數(shù)據(jù)的方式越來越多，人們已經(jīng)進(jìn)入了大數(shù)據(jù)時(shí)代。大數(shù)據(jù)在國內(nèi)外已經(jīng)如火如荼的發(fā)展起來，在各個(gè)領(lǐng)域都在滲透，近年來，人們對(duì)于數(shù)據(jù)信息價(jià)值性和可靠性都有著較高的要求，在大數(shù)據(jù)的時(shí)代背景下，每天都會(huì)產(chǎn)生各種形式的數(shù)據(jù)，包括文字、圖片、視頻以及音頻，這些數(shù)據(jù)優(yōu)勢(shì)是規(guī)模大、種類多、要求實(shí)時(shí)性強(qiáng)。

在當(dāng)今大數(shù)據(jù)時(shí)代，同一數(shù)據(jù)對(duì)象往往可以在不同的視圖下進(jìn)行描述，所獲取的數(shù)據(jù)常?？梢杂啥鄠€(gè)特征集合進(jìn)行表示，不同視圖下的觀測(cè)揭示了事物的不同屬性，這類數(shù)據(jù)通常被稱為多視圖數(shù)據(jù)［2］。多視圖數(shù)據(jù)的學(xué)習(xí)主要是在聚類這個(gè)背景下被研究，對(duì)于此類多視圖的研究被稱為多視圖學(xué)習(xí)［3］，目前，多視圖學(xué)習(xí)在機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、人工智能等不同領(lǐng)域得到了廣泛的研究［4～6］。在這些視圖中，每一個(gè)視圖可以滿足于特定的數(shù)據(jù)分析任務(wù)需求，不同視圖之間通常包含互補(bǔ)的信息。類似于我們所倡導(dǎo)的多視圖看問題的思維，機(jī)器學(xué)習(xí)如何綜合利用多視圖數(shù)據(jù)建立性能更為有效的學(xué)習(xí)模型，從而服務(wù)于人類的生活和工業(yè)生產(chǎn)，具有重要的理論意義和廣泛的應(yīng)用前景。

在多視圖的聚類中，存在一些實(shí)際問題，往往假設(shè)這個(gè)數(shù)據(jù)是完整的，然而在實(shí)際應(yīng)用中，可用的多視圖數(shù)據(jù)是不完備的，即意味著缺少某些視圖的功能，這對(duì)多視圖聚類帶來了很大的困難。如何處理不完全多視圖數(shù)據(jù)并從中挖掘到該類數(shù)據(jù)的共享信息，利用多視圖數(shù)據(jù)的一致原則以及互補(bǔ)原則完成多視圖聚類任務(wù)，已經(jīng)引起機(jī)器學(xué)習(xí)領(lǐng)域研究人員的廣泛關(guān)注。如果對(duì)于這類不完備多視圖數(shù)據(jù)直接進(jìn)行聚類分析，則會(huì)丟失很多的信息，因此，首先要對(duì)不完備多視圖數(shù)據(jù)進(jìn)行分析處理，再對(duì)數(shù)據(jù)進(jìn)行聚類。顯然，現(xiàn)有的多視圖聚類方法無法將不完備視圖的多視圖數(shù)據(jù)聚類，因?yàn)闊o法學(xué)習(xí)通用相似圖或者所有視圖的低維表示。此外，多個(gè)視圖之間由于缺少配對(duì)視圖可用的補(bǔ)充信息，因此視圖非常有限。這些因素使得不完備多視圖數(shù)據(jù)的研究成為一個(gè)挑戰(zhàn)。對(duì)這類不完備多數(shù)圖數(shù)據(jù)集上進(jìn)行聚類稱為不完備多視圖聚類［7～12］。因此，本文的研究對(duì)象是不完備的多視圖數(shù)據(jù)，關(guān)注如何能夠更好地處理的不完備的多視圖數(shù)據(jù)，聚焦不完備多視圖技術(shù)的相關(guān)技術(shù)。

同樣，在上述中解決的不完備多視圖數(shù)據(jù)都是離線的，沒有考慮到大規(guī)模的一些數(shù)據(jù)問題，其不能直接存放在內(nèi)存中，并且很難離線處理。對(duì)于這個(gè)問題的處理，到目前為止，針對(duì)此問題已經(jīng)提出了兩種解決方法［13～14］。

對(duì)于處理這種大規(guī)模的不完備多視圖數(shù)據(jù)，本文提出了一種基于非負(fù)矩陣分解［15～20］的在線反向圖正則化算法（Nonnegative matrix factorization algorithm based on online inverse graph regularization：IMC_OIRG）方法。

本文提出的IMC_OIRG 算法，主要具有以下優(yōu)點(diǎn)：

1）當(dāng)數(shù)據(jù)太大而不能放入內(nèi)存中時(shí)，依舊可以處理不完備多視圖數(shù)據(jù)，即可以最小化不完備多視圖數(shù)據(jù)對(duì)聚類結(jié)果的影響。

2）對(duì)于這種數(shù)據(jù)過大的數(shù)據(jù)，依舊可以將不同特征空間的各種視圖進(jìn)行組合，根據(jù)其一致性和互補(bǔ)性，能夠使得可以獲得更好的聚類結(jié)果。

3）將非負(fù)矩陣分解與反向圖正則化進(jìn)行結(jié)合，保證多視圖局部結(jié)構(gòu)的一致性，使得不完備多視圖數(shù)據(jù)能夠進(jìn)一步對(duì)齊，使得能夠得到更好的公共潛在特征表示。

2 相關(guān)工作

2.1 問題描述

對(duì)于不完備多視圖聚類，簡要描述問題的表述，假定給出一個(gè)有N個(gè)樣本nv個(gè)視圖的數(shù)據(jù)集，在本文中定義一個(gè)指示矩陣B∈Rnv×N。

其中，B的每一行代表一個(gè)視圖的存在。若多視圖數(shù)據(jù)是完備的，每個(gè)視圖包含所有的實(shí)例，則B為一個(gè)全1矩陣，即=N，k=1，2，…，nv。若多視圖數(shù)據(jù)是不完備的，數(shù)據(jù)矩陣X(k)將有許多行缺失，即指示矩陣表示為＜N，k=1，2，…，nv。本文的目標(biāo)為將不完備多視圖數(shù)據(jù)的N個(gè)實(shí)例聚類成K個(gè)聚類。

2.2 相關(guān)工作

OPIMC［14］為解決不完備多視圖聚類問題提出了一個(gè)框架，借助于正則化矩陣分解和加權(quán)矩陣分解，將數(shù)據(jù)矩陣X(k)∈Rdk×N分解為兩個(gè)矩陣G(k)∈RDk×K和F(k)∈RN×K，同時(shí)令，為了考慮到不同視圖之間的一致性信息，假設(shè)不同的矩陣，共享相同的矩陣F。同時(shí)還考慮到實(shí)例的缺失信息，借助加權(quán)矩陣分解來處理每個(gè)視圖的不完備性。對(duì)于大量的不完備多視圖數(shù)據(jù)，假設(shè)每個(gè)視圖都是通過塊獲得的，并且塊的大小為s，最終目標(biāo)函數(shù)表示為是第k個(gè)視圖的第t個(gè)數(shù)據(jù)塊，F(xiàn)t是第t個(gè)對(duì)角數(shù)權(quán)據(jù)重塊矩的陣聚。類權(quán)指重示矩矩陣陣，被是定第義為t個(gè)數(shù)據(jù)塊的

3 算法模型

在本節(jié)中，提出了IMC_OIRG 算法，處理大規(guī)模的不完備多視圖數(shù)據(jù)，利用動(dòng)態(tài)權(quán)重學(xué)習(xí)推斷缺失的視圖，同時(shí)，利用反向圖正則化進(jìn)一步對(duì)齊視圖，學(xué)習(xí)局部特征，來實(shí)現(xiàn)有效的公共表示學(xué)習(xí)。

3.1 算法提出與模型構(gòu)建

給定nv個(gè)視圖，N個(gè)樣本的不完備多視圖數(shù)據(jù)，使用非負(fù)矩陣分解的模型進(jìn)行分解，將X(k)∈分解為兩個(gè)矩陣G(k)∈和F(k)∈，分別表示為第k個(gè)視圖的基矩陣和潛在特征矩陣。其中，K表示為聚類的目標(biāo)數(shù)，目標(biāo)函數(shù)可以寫成如式（4）所示。

在此基礎(chǔ)上，由于不完備多視圖數(shù)據(jù)的特點(diǎn)，目標(biāo)函數(shù)無法直接進(jìn)行優(yōu)化，簡單的填充實(shí)例不能很好地解決這個(gè)問題。因此，本文利用加權(quán)非負(fù)矩陣分解的思想，引入一個(gè)對(duì)角權(quán)重矩陣P(k)∈RN×N，其中，表示為第k個(gè)視圖的第i個(gè)實(shí)例，同時(shí)，對(duì)于在視圖中出現(xiàn)的實(shí)例權(quán)重賦予1，對(duì)于視圖中缺失的實(shí)例賦予較低的權(quán)重。因此，目標(biāo)函數(shù)式（5）表示為

本節(jié)的目標(biāo)為找到每個(gè)視圖的潛在特征矩陣和一個(gè)共同的共識(shí)，這個(gè)共識(shí)矩陣表示了所有的視圖的綜合信息。因此，目標(biāo)函數(shù)式（6）可以被重新寫為

其中，λ1(k)表示為重建誤差與學(xué)習(xí)到的第k個(gè)視圖的共識(shí)一致性不一致之間的權(quán)衡參數(shù)。

在上述式（6）中，不僅對(duì)于不同的視圖分配了不同的權(quán)重，而且表示出了一致的共識(shí)矩陣，對(duì)于不完備視圖的性質(zhì)，為了加強(qiáng)潛在特征矩陣的稀疏性，仍添加一項(xiàng)l1范數(shù)。同時(shí)對(duì)潛在特征矩陣添加范數(shù)限制后，對(duì)于噪聲和異常值是魯棒的。

其中，‖ · ‖1表示l1范數(shù)，λ2(k)表示為第k個(gè)視圖重建的稀疏性和準(zhǔn)確性之間的折衷參數(shù)。

對(duì)于不完備多視圖數(shù)據(jù)，由于所有視圖的可用實(shí)例數(shù)都小于總樣本數(shù)，獲取數(shù)據(jù)的局部流行結(jié)構(gòu)是不可能的，因此，使用反向圖進(jìn)行學(xué)習(xí)，如式（8）所示。

其中，其中，1 是一個(gè)全1 的向量。其次，令Pi，:1=1，是為了防止任何實(shí)例與其鄰居不相連的平凡解。rank(LW)表示為LW的秩。通過反向圖正則化，保證了多視圖間的一致性流形結(jié)構(gòu)，進(jìn)一步對(duì)齊所有恢復(fù)的不完整視圖。

3.2 目標(biāo)函數(shù)

最終，對(duì)于不完備多視圖數(shù)據(jù)，根據(jù)上述學(xué)習(xí)，形成了一個(gè)學(xué)習(xí)模型，得出解決不完備多視圖數(shù)據(jù)的算法的目標(biāo)函數(shù)，如下。

在實(shí)際的應(yīng)用過程中，數(shù)據(jù)矩陣由于過大，因而無法直接放入內(nèi)存中。對(duì)于此問題，本章采用以低計(jì)算和存儲(chǔ)復(fù)雜性的在線方式來解決此問題。將輸入的數(shù)據(jù)在時(shí)間t時(shí)分成塊，s表示為數(shù)據(jù)塊的大小，也就是實(shí)例的大小。因此，輸入的數(shù)據(jù)矩陣為，最終的目標(biāo)函數(shù)表示為式（10）。

對(duì)于目標(biāo)函數(shù)式（10）中引入的權(quán)重矩陣，和之前用平均特征值進(jìn)行直接填充的方法不同，不完備多視圖數(shù)據(jù)，本節(jié)研究的多視圖數(shù)據(jù)太大而不能放入內(nèi)存，平均特征值不能直接進(jìn)行計(jì)算，對(duì)此，引入一個(gè)動(dòng)態(tài)權(quán)重矩陣，即當(dāng)讀入一個(gè)新的數(shù)據(jù)塊時(shí)，采用動(dòng)態(tài)（最新）平均值來填充，不是采用全局的平均特征值來填充缺失的實(shí)例。

可利用的實(shí)例中可以被動(dòng)態(tài)設(shè)置為

3.3 優(yōu)化

對(duì)于目標(biāo)函數(shù)式（10）的求解問題，可以發(fā)現(xiàn)，對(duì)于每一個(gè)t，需要對(duì)和{T}，然而，目標(biāo)函數(shù)不是聯(lián)合凸的，因此采用交替迭代的方法來更新求解。

1）更新G(k)，固定其他變量，關(guān)于G(k)的最小化目標(biāo)函數(shù)為

對(duì)G(k)取 一 階，?導(dǎo)(t)對(duì)數(shù)于G，(k其)的 梯中度，為令

因此，?(t)(G(k))相對(duì)于G(k)的Hessian矩陣為

使用二階的投影矩陣下降法，在時(shí)間t更新G(k)的方程為

其中，z表示迭代的次數(shù)，γz表示步長，??(t)(G(k))表示目標(biāo)函數(shù)對(duì)G(k)的一階導(dǎo)數(shù)。對(duì)于選取合適的步長γz，本章考慮使用簡單而有效的Armijo的投影規(guī)則，令γz=ηφz，φz是第一個(gè)非負(fù)整數(shù)。

3）更新W，固定其他變量，關(guān)于W 的最小化目標(biāo)函數(shù)為

對(duì)式（21）進(jìn)一步進(jìn)行簡化：

式（22）的封閉形式可以通過(Nie et al.2016)提出的有效算法來實(shí)現(xiàn)。

4）更新T，固定其他變量，關(guān)于T的最小化目標(biāo)函數(shù)為

其可以通過對(duì)應(yīng)于最小二乘的前c個(gè)最小特征值的一組特征向量來優(yōu)化。

在式（24）中，假設(shè)λ1(k)為正，對(duì)其求一階導(dǎo)數(shù)并使其為0：

在算法1 中總結(jié)了IMC_OIRG 的整個(gè)優(yōu)化過程：

算法1：IMC_OIRG

Input：不完備多視圖數(shù)據(jù){X(k)} ，聚類數(shù)K，數(shù)據(jù)塊大小s，參數(shù){λ1(k)，λ2(k)，λ3(k)，λ4(k)} .

為不完備多視圖實(shí)例設(shè)置權(quán)重；repeat

for k=1:nv do

根據(jù)式（16）更新G(k).

根據(jù)式（22）更新W.

根據(jù)式（23）更新T.

直至收斂

3.4 收斂性分析

如算法1 所示，提出的IMC_OIRG 方法是通過交替迭代的來求解最優(yōu)解的，通過此方法，可以收斂到一個(gè)局部最優(yōu)解。

4 實(shí)驗(yàn)

4.1 數(shù)據(jù)集

數(shù)據(jù)集介紹如下，我們選取四個(gè)數(shù)據(jù)集，Handwritten Dutch Digit Recognition（Digit）、Web Knowledge Base（WebKB）、Reuters Multilingual Text Data（Reuters）、YouTube Multiview Video Games（You-Tube）。數(shù)據(jù)集總結(jié)見表1。

表1 所用基準(zhǔn)數(shù)據(jù)采集系統(tǒng)的描述

4.2 對(duì)比試驗(yàn)

我們將本文提出的方法與幾種之前的方法進(jìn)行比較：IMC_OIRG 是本文提出的在線多視圖聚類方法，為了便于比較，將所有視圖的參數(shù)設(shè)置為相同。OPIMC 利用正則化矩陣分解和加權(quán)矩陣分解的單趟在線聚類方法；MIC 是OMVC 的線下情況，基于聯(lián)合非負(fù)矩陣分解的聚類方法；OMVC 是提出的在線不完備多視圖聚類方法；Multi NMF 是提出的一種經(jīng)典的離線多視圖聚類方法；ONMF 是一個(gè)在線的單視圖文檔聚類算法，為了應(yīng)用ONMF，將所有規(guī)范化的視圖連接在一起，形成一個(gè)大的單一視圖。另外，由于MIC 和MultiNMF 都是離線方法，因此將所有的數(shù)據(jù)都考慮在內(nèi)，通?？梢垣@得比在線方法更好的性能。

4.3 實(shí)驗(yàn)設(shè)置

在本次實(shí)驗(yàn)中，采用兩個(gè)廣泛使用的評(píng)估指標(biāo)，準(zhǔn)確性（AC）和歸一化互信息（NMI），用來橫量聚類性能。同時(shí)，對(duì)于每個(gè)數(shù)據(jù)集掃描十遍（Pass）并匯報(bào)每一次的NMI和AC。實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 實(shí)驗(yàn)結(jié)果

本文選取的四個(gè)數(shù)據(jù)集都是完整的，為了模擬不完備多視圖的情況，在每個(gè)視圖中令缺失度為0.4。對(duì)于數(shù)據(jù)塊的設(shè)計(jì)，將小數(shù)據(jù)集s 為50，大數(shù)據(jù)集為2000。由于在對(duì)比方法中，除ONMF以外所有方法都有幾個(gè)參數(shù)設(shè)置，因此對(duì)比較方法中的所有參數(shù)進(jìn)行網(wǎng)格搜索，并且給出最佳結(jié)果。另外，MultiNMF、ONMF-I 和ONMF-DA 無法處理不完備多視圖的視圖，為了應(yīng)用這些方法，本文用平均特征值填充缺失實(shí)例。在評(píng)價(jià)中，本文采用K-means從一致性潛在特征矩陣中得到聚類解。

4.4 結(jié)果分析

圖1（a）～（d）顯示了本文提出的方法在數(shù)據(jù)集Digit 和WebKB 的性能，從圖中可以觀察到，對(duì)于Digit 數(shù)據(jù)集，在第六次之后，算法達(dá)到了相似的結(jié)果，同時(shí)，比其他的方法效果要好一點(diǎn)。對(duì)于Web-KB數(shù)據(jù)集，前幾次的效果不是很好，造成這個(gè)現(xiàn)象的主要原因可能是因?yàn)樵O(shè)置的缺失度與設(shè)定的塊的尺寸不合適，導(dǎo)致公共潛在特征矩陣學(xué)出較難，經(jīng)過多次Pass之后，聚類性能提升。

圖1（e）～（h）顯示了本文提出的方法在數(shù)據(jù)集Reuters 和Youtube 的性能，從圖中可以觀察到，對(duì)于Reuters數(shù)據(jù)集，第五次Pass之后，慢慢達(dá)到了較好的結(jié)果，對(duì)于Youtube數(shù)據(jù)集，直接就能看出來比較其他方法比較有效，聚類性能明顯有效。

4.5 復(fù)雜性分析

在本文提出的算法中，使用平均損失來進(jìn)行IMC_OIRG方法的收斂性實(shí)驗(yàn)，在每次讀取數(shù)據(jù)塊t之后，平均損失被定義為

圖2 平均損失值

圖3 Digit參數(shù)

4.6 參數(shù)敏感度分析

在本文中利用Digit 數(shù)據(jù)集對(duì)四個(gè)參數(shù){λ1(k)，λ2(k)，λ3(k)，λ4(k)} 進(jìn)行分析，當(dāng)參數(shù)分別位于范圍［10-6，10-1］，［10-8，10-2］，［10-8，10-2］，［10-10，10-3］內(nèi)時(shí)，可以看到有一個(gè)好的效果，在實(shí)驗(yàn)中，利用網(wǎng)格搜索策略來尋找四個(gè)最佳的參數(shù)。從圖中3 可以看出，當(dāng){λ1(k)=10-3，λ2(k)=10-7，λ3(k)=10-7，λ4(k)=10-8}時(shí)效果是最佳的。

4.7 數(shù)據(jù)塊分析

在本文所提出的方法中，設(shè)定的數(shù)據(jù)塊s是一個(gè)重要的參數(shù)，為了學(xué)習(xí)不同s對(duì)于聚類結(jié)果的影響，選取Digit 數(shù)據(jù)集，缺失度為{1 ，0.2，0.4} ，令s={2 ，10，50，250} ，在表2 中，給出實(shí)驗(yàn)結(jié)果?？梢杂^察出，本文所提出的方法，效果性能優(yōu)于其他的方法，并且可以看出，當(dāng)數(shù)據(jù)塊大的比數(shù)據(jù)塊小的效果好一些，原因在于，當(dāng)數(shù)據(jù)塊越大，其中可以利用的數(shù)據(jù)信息就會(huì)越多，其中，當(dāng)s=50 或者s=250 時(shí)，效果更好。

表2 Digit對(duì)于不同缺失率和不同數(shù)據(jù)塊

5 結(jié)語

本文提出了一種解決不完備多視圖數(shù)據(jù)的方法——不完備多視圖的在線反向圖正則化聚類（Online Reverse Graph Regularized Clustering for Incomplete Multi-view）。在加權(quán)非負(fù)矩陣分解的前提下，最小化潛在特征矩陣和共識(shí)之間的不一致，給缺失實(shí)例賦予動(dòng)態(tài)權(quán)重，減少缺失實(shí)例的影響，學(xué)習(xí)反向圖正則化，利用視圖的局部信息，進(jìn)一步對(duì)齊視圖。同時(shí)，對(duì)于大數(shù)據(jù)的數(shù)據(jù)集，對(duì)其進(jìn)行逐塊處理。通過實(shí)驗(yàn)證明了本文所提出方法IMC_OIRG的有效性。