杜科君

（中國(guó)礦業(yè)大學(xué)徐海學(xué)院計(jì)算機(jī)系 江蘇省徐州市 221000）

簡(jiǎn)單來(lái)說(shuō)，奇異值分解（SVD）是一種矩陣分解方法，用于將矩陣簡(jiǎn)化為其組成部分，以使某些后期矩陣計(jì)算更容易。特征分解從半正定矩陣擴(kuò)展到任意 m×n 矩陣。

SVD 能夠提供具有最大奇異值的單位奇異向量，它解釋了數(shù)據(jù)點(diǎn)的最大方差，這符合我們的要求。這里，令M為m×n數(shù)據(jù)矩陣，其行可以代表樣本，列可以代表變量。U是m×m正交矩陣，∑是m×n對(duì)角矩陣。V是一個(gè)n×n正交矩陣，U和V分別稱為左奇異向量和右奇異向量。

這里滿足UU=VV=I，Σ=diag(σ,…,σ), σ≥σ≥…≥σ，σ是 M 的奇異值，按照慣例以非遞增順序排列。奇異值 σ與特征值相似，σ 減小得很快，因此大矩陣 M 被分解為三個(gè)矩陣。

此外，如果向量 v 是矩陣 A 的特征向量，它可以寫(xiě)成Aν=λν。此處λ是特征向量v的特征值，矩陣的特征向量集合由正交向量組成。根據(jù)典型公式，兩邊同時(shí)平方，當(dāng)矩陣為二維時(shí)，由于M向量矩陣由行向量組成，指的是每一個(gè)行向量，可以進(jìn)一步寫(xiě)成：

幾何上也可以理解成SVD分解的過(guò)程，通過(guò)單位圓半徑的變換，認(rèn)為是橢圓的橢圓的兩個(gè)半軸。如圖1所示。

圖1：奇異值分解過(guò)程

通過(guò)數(shù)據(jù)的 SVD 處理，可以用一個(gè)小得多的數(shù)據(jù)集來(lái)表示原始數(shù)據(jù)集，從噪聲數(shù)據(jù)中提取相關(guān)特征，這實(shí)際上是去除了噪聲和冗余信息，從而實(shí)現(xiàn)了優(yōu)化。

1 目標(biāo)

在此項(xiàng)目中，筆者提出了一種基于SVD和k-means的聚類方法，用于單位超球面上的數(shù)據(jù)條目，以解決兩個(gè)問(wèn)題，即

（1）找到同一單位球面上的集群代表；

（2）將相對(duì)于超球面中心對(duì)稱的數(shù)據(jù)條目分組到同一個(gè)簇。

確定項(xiàng)目需求后，我將球面上的點(diǎn)可視化，展示了一個(gè)二維球面上的對(duì)稱點(diǎn)之間的關(guān)系，并在此基礎(chǔ)上進(jìn)行擴(kuò)展。

本次指導(dǎo)性研究的主要目的是研究降維聚類算法在球體上的具體應(yīng)用，可歸納如下：給定歐幾里得L空間中單位(L-1)超球面上的一組點(diǎn)X，將X劃分為K個(gè)簇，使得：每個(gè)簇有一個(gè)同一個(gè)超球面的質(zhì)心來(lái)表示簇，滿足(a)；每個(gè)點(diǎn)被分類到最合適的簇，滿足(b)。

2 現(xiàn)有的樣本點(diǎn)聚類算法

如今，聚類分析已廣泛應(yīng)用于多種應(yīng)用，包括模式識(shí)別、數(shù)據(jù)分析、圖像處理和市場(chǎng)研究。現(xiàn)有的聚類方法有很多，如層次聚類、k-means聚類、基于密度的聚類等。在大多數(shù)情況下，這些方法能夠有效地執(zhí)行聚類。

但是，當(dāng)數(shù)據(jù)空間的維度很高（例如，數(shù)百甚至數(shù)千）時(shí)，其中一些方法可能效率低下甚至失敗。在這種情況下，通常使用基于 SVD 的主成分分析對(duì)數(shù)據(jù)集進(jìn)行降維，然后才能進(jìn)行聚類。

除了區(qū)分和分組數(shù)據(jù)條目之外，聚類分析還可以幫助在每個(gè)集群中尋找具有代表性的條目來(lái)代表該集群中的所有條目，可以通過(guò)選擇從所有數(shù)據(jù)條目的每個(gè)維度的平均值計(jì)算的質(zhì)心來(lái)完成。

但是，它可能無(wú)法在特定情況下找到合適的代表，例如所有數(shù)據(jù)條目都位于超球面上，并且代表也必須位于同一個(gè)球面上。

此外，當(dāng)考慮到數(shù)據(jù)對(duì)稱性并且期望彼此對(duì)稱的條目屬于同一個(gè)簇時(shí)，經(jīng)典聚類無(wú)法進(jìn)行聚類。本報(bào)告的目的是選擇 SVD 對(duì)數(shù)據(jù)點(diǎn)進(jìn)行聚類。

2.1 層次聚類

層次聚類是一種聚類算法，它通過(guò)計(jì)算不同類別數(shù)據(jù)點(diǎn)之間的相似度來(lái)創(chuàng)建層次嵌套的聚類樹(shù)。層次聚類算法可以是凝聚的也可以是分裂的，這取決于層次劃分是“自下而上”還是“自上而下”。

優(yōu)點(diǎn)之一是數(shù)據(jù)集的聚類可以在不同的尺度（層次結(jié)構(gòu)）上顯示。層次聚類試圖將樣本數(shù)據(jù)集劃分為不同的“層次”，并將它們逐層聚類。

在建立過(guò)程中，可以通過(guò)第二步設(shè)置閾值。當(dāng)最近的兩個(gè)類之間的距離大于閾值時(shí)，認(rèn)為迭代終止。

然而，層次聚類的局限性是顯而易見(jiàn)的。計(jì)算復(fù)雜度太高，算法的執(zhí)行時(shí)間大大延長(zhǎng)，無(wú)法追溯處理。因此，當(dāng)解決大量數(shù)據(jù)時(shí)，不推薦使用這種聚類算法。

2.2 基于K-means的聚類

K-means 的空間要求適中，因?yàn)橹淮鎯?chǔ)數(shù)據(jù)點(diǎn)和質(zhì)心。得到N個(gè)待聚類的樣本和待聚類的數(shù)量K（K

因此，第一次結(jié)束迭代，下一步就是看本次迭代能否達(dá)到你設(shè)定的目標(biāo)（即迭代終止條件），如果達(dá)到則集群結(jié)束，否則繼續(xù)下一次迭代。

下一次迭代是重新計(jì)算聚類中心點(diǎn)（可能是樣本數(shù)據(jù)點(diǎn)），然后計(jì)算其他點(diǎn)與新聚類中心的距離并重新選擇類別。這將依次迭代，直到達(dá)到設(shè)定的終止條件。

這種方法快速且易于實(shí)施，但缺點(diǎn)也很明顯。首先，你需要設(shè)置其中的幾個(gè) k 值，但是你不知道應(yīng)該確定多少 k 值，而不知道數(shù)據(jù)。雖然這里K-means導(dǎo)出的目標(biāo)形式和上面SVD介紹的表達(dá)式是一樣的，但是K-means實(shí)際上并沒(méi)有做 SVD。

K-means要求誤差分布，即誤差服從標(biāo)準(zhǔn)正態(tài)分布。傳統(tǒng)的K-means算法在聚類過(guò)程中，聚類數(shù)K的取值難以確定，聚類結(jié)果受初始中心的影響，它具有對(duì)噪聲敏感和不穩(wěn)定的弱點(diǎn)。

因此，K-means在處理非標(biāo)準(zhǔn)正態(tài)分布數(shù)據(jù)集時(shí)會(huì)產(chǎn)生較差的聚類效果。此外，每次迭代后都要重新計(jì)算每個(gè)點(diǎn)到質(zhì)心的距離，然后進(jìn)行排序，時(shí)間成本很高。

3 系統(tǒng)建模與結(jié)構(gòu)

通過(guò)比較三種數(shù)據(jù)聚類方法，我選擇了SVD算法。SVD作為一種非常基礎(chǔ)的算法，在很多機(jī)器學(xué)習(xí)算法中都有自己的形象，尤其是在當(dāng)前大數(shù)據(jù)時(shí)代。因?yàn)镾VD可以實(shí)現(xiàn)并行化，所以功能更加強(qiáng)大。

3.1 SVD算法的廣泛應(yīng)用

現(xiàn)在SVD有很多應(yīng)用，可以說(shuō)SVD是矩陣分解、降維、壓縮、特征學(xué)習(xí)的基礎(chǔ)工具。因此，SVD在機(jī)器學(xué)習(xí)領(lǐng)域非常重要。此外，SVD 是一種具有明顯物理意義的方法。它可以通過(guò)乘以更小更簡(jiǎn)單的子矩陣來(lái)表示更復(fù)雜的矩陣。

3.1.1 SVD在推薦系統(tǒng)中的應(yīng)用

基于 SVD 的推薦系統(tǒng)應(yīng)該結(jié)合向量相似度的計(jì)算方法，找到與被推薦用戶相似的用戶項(xiàng)目分?jǐn)?shù)進(jìn)行推薦或找到比被推薦用戶評(píng)分更高的項(xiàng)目。

推薦系統(tǒng)的簡(jiǎn)單版本可以計(jì)算物品或相似度。假設(shè)可以使用矩陣A中的維度來(lái)表示某用戶的相關(guān)信息。通過(guò)SVD計(jì)算機(jī)，可以生成U、S、V三個(gè)矩陣。

此時(shí)，先來(lái)簡(jiǎn)單選擇k=2來(lái)降低U、S、V的維數(shù)。如果k=2，說(shuō)明數(shù)據(jù)集中包含兩個(gè)不可見(jiàn)的因素：

將降維后的U、S、V相乘得到A'。通過(guò)矩陣A和A'的比較，可以直觀地看出這兩個(gè)矩陣非常相似，可以看作是一種數(shù)據(jù)有損壓縮。

首先我用公式p'=p*U'*S'*V'推導(dǎo)出用戶的二維向量，然后計(jì)算余弦相似度得到用戶評(píng)分向量與新用戶最相似。這樣就可以根據(jù)向量q填充向量p，也就是預(yù)測(cè)。

將SVD用于推薦系統(tǒng)可以使推薦結(jié)果準(zhǔn)確，而且模型的擴(kuò)展性也很強(qiáng)，可以應(yīng)用于各種場(chǎng)景。然而，SVD模型的可解釋性較差，隱性因素?zé)o法對(duì)應(yīng)現(xiàn)實(shí)生活中的具體概念。模型的訓(xùn)練速度還有待提高。

3.1.2 SVD在圖像處理中的應(yīng)用

這些較小數(shù)量的奇異值（奇異向量）用于表示可能比較大的事物，因此在圖像壓縮等方向上有很多應(yīng)用。在圖像處理領(lǐng)域，奇異值不僅可以應(yīng)用于數(shù)據(jù)壓縮，還可以應(yīng)用于圖像去噪。

如果圖像包含噪聲，我們有理由相信較小的奇異值是由噪聲引起的。當(dāng)這些較小的奇異值被強(qiáng)制為0時(shí)，它們可以去除圖片中的噪聲。

比如說(shuō)一張 25*15 的圖片，通過(guò)奇異值分解，可以發(fā)現(xiàn)矩陣的奇異值分別為：14.15, 4.67, 3.00, 0.21, ..., 0.05。除前三個(gè)奇異值外，其他奇異值彼此相比都很小。將這些小的奇異值強(qiáng)制為0，然后只用前3個(gè)奇異值構(gòu)造新矩陣，可以得到噪聲減少后的圖片。

3.2 SVD算法的考慮

通過(guò)以上兩個(gè)應(yīng)用的介紹，SVD算法具有很好的適用性，所以我把它應(yīng)用在自己的問(wèn)題：“在計(jì)算中使用矩陣的SVD，而不是原始矩陣，具有對(duì)數(shù)值誤差更穩(wěn)健的優(yōu)勢(shì)。”

SVD將一個(gè)復(fù)雜的變換分解為三個(gè)簡(jiǎn)單的基本變換（旋轉(zhuǎn)、縮放、投影），奇異值的大小代表對(duì)應(yīng)奇異向量的縮放程度。奇異值越大，這個(gè)奇異向量對(duì)最終空間的影響就越大。因此，SVD可用于壓縮圖像或去噪。

因此，我借用了SVD算法來(lái)求基。另外，與之前的模型相比，SVD更適合這個(gè)主題的需求。此外，每個(gè)堿基在生成列時(shí)的權(quán)重也不相同。通常情況下，某些基本權(quán)重特別大，而另一些則特別小，使用SVD時(shí)可以獲得該值。

對(duì)于現(xiàn)在要解決的問(wèn)題，特點(diǎn)是對(duì)稱點(diǎn)也可以組合在一起，可以找到代表點(diǎn)。使用我之前介紹的方法也無(wú)法滿足此要求。

但是，SVD也存在一些問(wèn)題。矩陣Σ只有對(duì)角元素從大到小排列。在科學(xué)和工程領(lǐng)域，一直有一個(gè)普遍的事實(shí)，即在一定數(shù)量的奇異值r之后，其他奇異值都被設(shè)置為零。這意味著數(shù)據(jù)集中只有r個(gè)重要特征，其余都是噪聲或冗余數(shù)據(jù)。

在這個(gè)項(xiàng)目中，我想對(duì)球體上的樣本點(diǎn)進(jìn)行聚類。上一篇文章中提到了很多聚類方法，但是其中SVD方法可以找到代表點(diǎn)。在繪圖過(guò)程中，我可以清楚地看到對(duì)稱點(diǎn)的關(guān)系。這一優(yōu)勢(shì)是基于其強(qiáng)大的應(yīng)用性能。

具體來(lái)說(shuō)，當(dāng)數(shù)據(jù)很多時(shí)，奇異值分解的計(jì)算量會(huì)很大，而矩陣的大小只與屬性的個(gè)數(shù)有關(guān)。

對(duì)比這幾種算法，前三種不能反映樣本點(diǎn)的對(duì)稱性。SVD很好地解決了這個(gè)問(wèn)題。

4 方法論和算法

從這部分開(kāi)始，我將討論處理單位球面上點(diǎn)的聚類問(wèn)題的項(xiàng)目概要和方法論。

基于前面的目標(biāo)，我們的分析步驟如下：

（1）使用SVD算法得到每個(gè)樣本的類別號(hào)。

（2）結(jié)合第一步得到樣本數(shù)最多的類號(hào)。

（3）根據(jù)第二步得到的類號(hào)提取該類的樣本數(shù)據(jù)。

（4）對(duì)第三步得到的樣本數(shù)據(jù)，進(jìn)行SVD分析，得到最大特征向量模的指標(biāo)。

4.1 仿真數(shù)據(jù)的確定

在實(shí)現(xiàn)算法之前，我首先導(dǎo)入一個(gè)模擬數(shù)據(jù)包。在這里，我指定 m=3 并假設(shè) k≥3。

在程序開(kāi)始時(shí)，我定義了一個(gè) m×n 矩陣 x，其中 n 表示維度，m 表示樣本數(shù)。

首先，我將球面上需要聚類的點(diǎn)簇分為兩種情況，一種是非對(duì)稱的，一種是對(duì)稱的。我將數(shù)據(jù)訓(xùn)練分為兩個(gè)階段。在第一階段，我選擇了 3*20 的數(shù)據(jù)進(jìn)行模擬。

在對(duì)少量數(shù)據(jù)的代碼進(jìn)行了模擬測(cè)試后，我隨機(jī)生成了100個(gè)數(shù)據(jù)并繪制出來(lái)。

4.2 對(duì)應(yīng)樣本數(shù)據(jù)的提取

第一步，我定義了一個(gè)標(biāo)簽來(lái)表示數(shù)據(jù)的類別號(hào)。我需要獲取每個(gè)樣本的類別號(hào)。這里我對(duì)矩陣x中的數(shù)據(jù)進(jìn)行歸一化，然后將所有樣本的類別標(biāo)簽初始化為-1。初始迭代次數(shù)為 1。

當(dāng)所有的樣本都分類后，就停止迭代，因?yàn)槿绻€有該類的樣本，肯定有標(biāo)簽-1<0。在這里，我使用了循環(huán)語(yǔ)句。然后我得到樣本數(shù)據(jù)和沒(méi)有類別的數(shù)據(jù)的列數(shù)。如果樣本數(shù)小于1，直接退出。

從而得到?jīng)]有標(biāo)簽的樣本索引號(hào)，繼續(xù)進(jìn)行 SVD 并返回到三個(gè)矩陣。其中，u矩陣的數(shù)據(jù)依次集中、轉(zhuǎn)置、標(biāo)準(zhǔn)化。

得到類別總數(shù) k 和中心點(diǎn) c。類號(hào)設(shè)置好以后，值一樣的時(shí)候就可以直接跳出。

對(duì)樣本數(shù)最多的簇中包含的所有樣本數(shù)據(jù)進(jìn)行SVD，得到最大特征向量模的索引。

4.3 繪制3D圖形

在對(duì)數(shù)據(jù)進(jìn)行聚類后，我添加了繪圖代碼并繪制了立體圖像。

5 初步性能分析

收集閱讀相關(guān)文章后，成功運(yùn)行代碼。并驗(yàn)證了項(xiàng)目要求。該部分主要展示最終結(jié)果，并對(duì)結(jié)果進(jìn)行分析，指出不足之處。

5.1 結(jié)果簡(jiǎn)要分析

在整個(gè)代碼中，我兩次使用了 SVD 算法。第一次是對(duì)分散的數(shù)據(jù)進(jìn)行聚類，得到每個(gè)樣本的類別號(hào)。第二次是獲取樣本數(shù)據(jù)后的計(jì)算。得到對(duì)應(yīng)的數(shù)據(jù)后，我對(duì)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化，得到最終的矩陣。

值得一提的是，在計(jì)算聚類點(diǎn)時(shí)，我選擇了一個(gè)高斯擬合，b1,b2代表擬合模型的平均浮動(dòng)范圍。此外，方程可以列為Xμ=μ+ε其中εi為噪音。

代碼運(yùn)行成功后，得到最大迭代次數(shù)為2以及如圖2所示。

圖2：生成的圖像

在第一張圖中，我嘗試將 100 個(gè)模擬數(shù)據(jù)分成一個(gè)簇，圖形不是很明顯。

在第二張圖片中，三種顏色代表三個(gè)不同的集群?？梢钥闯?，在單位球面上，樣本點(diǎn)分為三類。對(duì)稱性也可以體現(xiàn)出來(lái)。以圓心為球心，球面上各點(diǎn)對(duì)稱。

5.2 假設(shè)算法的局限性和潛在優(yōu)化

該算法的局限性在于，由于兩個(gè)集群相對(duì)于所選擇的奇異向量對(duì)稱的可能性，集群可能是不明確的。由于只分析了100個(gè)模擬數(shù)據(jù)，結(jié)果圖像看聚類情況不是很清楚。

如果有機(jī)會(huì)，我會(huì)添加更多數(shù)據(jù)進(jìn)行驗(yàn)證（例如，大于1000）。此外，在數(shù)據(jù)處理過(guò)程中會(huì)產(chǎn)生一些噪聲，這可能會(huì)導(dǎo)致結(jié)果不準(zhǔn)確。此外，算法的性能也需要優(yōu)化，目前的算法效率不高。

6 結(jié)語(yǔ)

通過(guò)這篇論文，我意識(shí)到了自己對(duì)機(jī)器學(xué)習(xí)理解膚淺的缺點(diǎn)。本人對(duì)算法理解有一定障礙，相關(guān)知識(shí)點(diǎn)存在很多盲點(diǎn)。在下一階段，我將學(xué)習(xí)更多關(guān)于機(jī)器學(xué)習(xí)和數(shù)據(jù)分析的知識(shí)。