動機
數據群可以沿彎曲形狀伸展,單一質心未必能代表它。圖提供另一種描述:相近觀測以強邊連接,合理分組應盡量少切斷強邊。這沒有消除建模選擇,而是把選擇放到距離、鄰域與相似度尺度之中。
只最小化切斷的總權重,可能把一個弱連接觀測單獨分出。正規化割把每群的向外割權重除以群的總加權度數,減少這種偏好。但離散問題仍難解。譜方法先把指示向量放寬成實數座標,以特徵向量精確解鬆弛問題,再把座標轉回標籤。這些步驟各自回答不同問題,不能合併成一個未經證明的最優性聲明。
本節處理直接分成多群的版本。特別要先檢查圖,才做矩陣正規化;有孤立點時,某些常見公式根本沒有定義。完整算法必須包含這些決定,以及最後的離散化規則。
定義
定義 5.1.1
(相似度、度數、體積與正規化割)
設 對稱,、。定義 、、。對不交集合 ,令 ,以及 。把頂點分為正體積的非空群 ,定義
兩群情形,同一跨群權重在兩項出現,但分母不同,這是定義的一部分。體積不是頂點數:內部邊兩端皆在群內,所以計入兩次。正規化割平衡的是圖體積,不是強制每群人數相同。
所有度數皆正時,定義對稱正規化拉普拉斯(Laplace)與隨機遊走矩陣
與 相似,但其右特徵向量要把對稱矩陣的向量乘以 。這些向量的正交性用 內積表達,並非普通歐氏(Euclid)正交。先說明正在使用哪一個矩陣,才能避免正規化錯配。
體積分母還有概率意義。遊走由 到 的概率是 ,度數比例分佈為平穩分佈,因對稱性使每點流入量恰等於其度數除以總體積。在此分佈下條件於目前位於 ,下一步離開 的概率,正是向外割除以體積。正規化割把各群這種條件逃逸概率相加。這個解釋不需要非週期性;若要聲稱任意初始分佈最終收斂到平穩分佈,則還需要其他假設。
定義 5.1.2
(建圖也是模型的一部分)
一種選擇是對 設 , 固定。稀疏版本可只保留半徑內或近鄰間的邊。若近鄰關係有方向,就要選擇對稱化規則:任一方向成立便留邊,或兩個方向都成立才留邊。兩者會產生不同的圖。
不同單位的座標應按明確度量處理,不能讓數值較大的單位自動主宰距離。高斯(Gauss)帶寬太小,圖在數值上可能近乎斷開;太大則各邊近乎一樣。互為近鄰的稀疏圖更可能產生孤立點。特徵值求解器不能判斷這些現象代表真實結構,還是相似度選得不合適。
定理/命題
定理 5.1.3
(正規化割的跡形式)
假設度數皆正。對一個分割,若 ,設 ,否則為零。則 ,而
令 ,目標就是 ,限制有 ,也有 特有的離散指示結構。
定理 5.1.4
(多路譜鬆弛與理想分量恢復)
假設每個度數均為正且 。設 的特徵值為 。在所有滿足 的實 矩陣中,
由最小 個特徵值對應的正交特徵向量可達到此值,因此它是每個離散正規化割的下界。若圖恰有 個連通分量且沒有孤立點,任意正交零空間基的每行除以自身範數後,同一分量映到同一單位向量,不同分量映到互相正交的向量。
最後一句是精確的理想情形,不表示只要有小特徵值,就存在唯一有意義的分組。若第 與第 特徵值很接近,所選子空間可對擾動敏感;最後分組的距離若接近並列,標籤也可能在子空間穩定時仍改變。
證明思路或證明
證明
(由邊能量推到特徵值下界)
對稱性給 。取 ,只有跨界邊留下,得 。指示列支撐互不重疊,故 ;把各列二次型相加,便得到跡恆等式。代入 即得正規化形式。
對角化 ,令 ,則 。記 為 第 行範數平方。 是正交投影,所以 ,且 。因此
因為兩組質量 與 相等,前組特徵值皆不小於 ,後組皆不大於它。選前 個特徵向量便達等號。證明只放寬指示結構,沒有直接產生標籤。
證明
(行正規化為何找回分量)
邊能量恆等式說明, 的核由各連通分量上常數的向量組成。故 的一組正交基是 。恰有 個分量時,其他正交基皆可寫成 ,其中 正交。若 ,第 行就是 第 行乘正數 。行正規化消去此倍數,同群所有點完全重合,不同群內積為零、距離平方為二。
證明透視
鬆弛與離散化有不同責任
把指示矩陣換成所有正交列矩陣,得到精確可解的特徵值問題及下界。行正規化後再作 k-means,是額外的離散化程序。離散標籤轉回的指示矩陣,通常不再是原鬆弛問題的最小矩陣。要保證某種離散化品質,必須有額外假設與證明,不能只引用 Rayleigh 論證。
實際算法先建立對稱圖,再處理度數為零的孤立點:可標為未指派、另列單點群,或重建圖,但要明示政策。直接在每個度數加小常數會改變算子,不能稱為原圖的精確正規化。
在其餘正度數圖上數連通分量 。若 ,必須合併互不連接的分量,而圖沒有跨分量邊去支持某個優先合併。應記錄歧義或加入其他資訊。以下取 :計算 最小 個特徵值的正交向量,包含完整零空間,組成 。第 行限於完整零空間各列的平方範數為其所屬分量 的 ,即零空間投影矩陣相應的對角項。因此整行非零。設 ,在這些行上以明確初始化和重啟政策作 k-means,再把標籤交還原頂點。最後計算原圖割值,檢查圖參數與重啟的敏感性。這給出一份結果,不是全域最優證書。
例題詳解
例題 5.1.5
(邊權差一百倍的兩個分量)
頂點一、二間有權重一的邊;三、四間有權重一百的邊,其他皆零。度數為 ,正規化鄰接矩陣有兩個相同區塊 。可取零空間基,使第一分量兩行皆為 ,第二分量皆為 。行正規化後成 與 ,即使體積差很大也能恢復兩群。基向量整體旋轉不改變距離或此結論。
例題 5.1.6
(三點路徑的真實鬆弛間隙)
單位權重路徑 的度數為 ,正規化特徵值為 。前兩向量可取 與 ,故兩群鬆弛值為一。分割 的割為一,體積為一與三,正規化割為 ;對稱分割亦然,單獨分出中心則為二。因此連最好的離散分割也嚴格高於鬆弛值。行正規化所得點為 、、,對稱性容許任一端點與中心同群。
例題 5.1.7
(孤立點使原比值失去定義)
在兩條邊的例中加入第五個孤立頂點。其度數為零,故單點割比值是 ,沒有定義。可以移除它,把其他四點分兩群,再報它未指派;也可另定一種延伸目標,把它列作單點群。不能直接把比值當零,再宣稱原定義已決定它的標籤。加自環是另一張圖,也沒有提供它與其他觀測的相似資訊。
常見錯誤
反例模式
所有邊乘同一正數不改變分組問題
把 換成 ,,每個割與體積都乘 ,正規化割不變。同時 ,故嵌入不變,僅容許基的慣例差異。因此把全部相似度乘大,並不會令本算法發現更強群組。改高斯帶寬則通常改變相對邊權,與共同倍數不同。
常見錯誤
(最大或最小必須連同矩陣說明)
的最小特徵向量對應正規化鄰接矩陣按代數值排序的最大特徵向量,並非按絕對值排序。二頂點分量的鄰接特徵值是一與負一;負向量表示交替符號,不是第二個連通分量。混淆排序會把不同幾何資訊放進嵌入。
思想史
多特徵向量與獨立行正規化
Ng、Jordan 與 Weiss 的 2001 年原論文 指定正規化相似度的特徵向量、行正規化及其後的分組。它同時使用多個向量,而非只反覆二分。原文稱作 的矩陣是正規化鄰接矩陣;本節以 表示拉普拉斯,閱讀時要辨清。
總結
正規化割以群體積比較向外權重。拿掉指示限制,跡問題可由最小特徵向量解出。完整零空間加行正規化能精確識別斷開分量;一般圖則還要交代建圖、孤立點、群數及離散化。特徵值下界與最終標籤品質始終是不同結論。
練習
快速檢查
(對三頂點單位路徑,把兩端放同群、中心另成一群,計算正規化割,並與端點分割和譜下界比較。)
用度數體積,而不是群的頂點數。
解答 · 答案
端點集合體積二,中心體積亦二;兩條邊都跨界,割為二。因此正規化割為 。端點分割為 ,而前兩特徵值和為一。 分別是鬆弛下界、最佳離散值及較差分割。
快速檢查
(直接證明各元素為度數平方根的向量,是正規化拉普拉斯的零特徵向量。為何它通常不是常數?)
先乘正規化鄰接矩陣。
解答 · 答案
令 ,有 ,故 。元素是 ,只有度數相同時才相等。單位化除以 。換到隨機遊走座標,,解釋兩算子的平凡方向為何外觀不同。
快速檢查
(將正交嵌入 U 右乘正交矩陣 R,證明行正規化及任意兩點距離只隨同一旋轉改變。)
正交映射保留範數及內積。
解答 · 答案
非零行 滿足 ,所以其正規化行成為 。差向量範數 不變。每個群均值亦同時旋轉,故任意指定分割的 k-means 目標不變;座標可不同,幾何分組問題相同。
快速檢查
(三個正度數連通分量只要求兩群,為何兩個零特徵向量可能產生全零行?要唯一合併還缺甚麼資訊?)
選只支撐在前兩個分量的基向量。
解答 · 答案
零空間是三維。若只取第一、二分量的正規化指示向量,第三分量的每行皆零,不能除以其範數。其他選基可能避開零行,但仍是任意的同值解。跨分量權重全零,圖沒有偏好哪兩群合併;需要外加距離、領域規則,或明確承認任意政策。求解器輸出的基不是額外的科學證據。