相似度分析任務：

實驗室實習期間，要做一個基於相似度的句子無監督聚類。所有句子一共有130w個，從一開始讀資料就遇到了一些問題，以此記錄整個流程。

一開始很無知的建立了一個130萬*130萬的矩陣，結果我的小電腦就直接終止了這個程序，還好不是在實驗室的gpu上跑的，於是需要考慮如何有效的構建這樣的矩陣。

在學長的建議下，先進行小規模測試，即選出和3000個以上句子都有相似度的句子，這樣經過過濾整個句子就從130w變成了僅有4000多個句子，減少了很大的計算量，可以在自己的小電腦上跑一下驗證，再在實驗室的gpu上跑結果，也算是學到了。

由於矩陣形式是兩個句子之間的jaccard相似度即，例 第一個句子與第1000個句子相似度為0。5，與第二個句子相似度為0。3等等。

首先這些不是一個距離度量，因此直接基於距離kmeans演算法並不能直接使用，如果要使用kmeas演算法必須得把這個矩陣轉換成一個距離的問題。

基於相似度矩陣的話，可以利用譜聚類進行聚類分析，譜聚類原本是一種基於圖結構的聚類方法，其在圖中的使用相當於一個切分子圖的方法，在子圖中其相當於兩個圖之間的邊的權重值，在這裡就對應了兩個事件之間的相似度。

簡介寫一下相關原理：

首先考慮這是一個無向圖，即1和2與2和1之間的相似度是相同的。

定義一個nxn矩陣

D=\left\{\begin{matrix}d_1 &0&0\\0&d2&0\\0&0&d3 \end{matrix}\right\}

以這個作為一個3x3矩陣的例子，其中的d是與其它節點相似度的合，沒有相似度的為0，有的則為對應的值。

而任意兩個點之間的權值又可以構成我們的鄰接矩陣

W

，比如

w_{12}

就是1和2的相似度。由於我們手裡就已經有了每個資料之間的相似度關係，也就相當於我們已經有了鄰接矩陣，因此此處不再介紹如何根據一個圖構造鄰接矩陣的方法。

Laplace矩陣：

定義非常的簡單：

L=D-W

，由於

D

是對角陣，

W

是對稱鄰接矩陣，因此經過這個操作之後的拉普拉斯矩陣依舊是一個對稱陣。

而對稱陣具有很多良好的性質：首先特徵值沒有虛數，然後對於任意的對稱矩陣我們都可以對其進行分解，同時該矩陣是正定陣。

無向圖切圖方法：

如若考慮為一個無向圖，我們要把該圖切為合適大小。

相似度聚類

子圖切割

我們可以看到smallest cut是不合理切圖，best cut是一個合理切圖。

為了研究切圖我們定義如下：

假定有N個子圖

A_1,A_2,...A_N

，子圖之間沒有交集，並集構成全圖。

對於圖

A

和圖

B

，我們定義圖的切圖權重為：

W(A,B)=\sum_{i\in A,j\in B}w_{ij}

可以看到這個權重的計算方法，i在A中j在B中，假設圖A包括點k和點o，圖b包括點l，那麼就是

w_{kl}+w_{ol}

而當是N個子圖的時候：

cut(A_1,A_2,....,A_k)=\frac{1}{2}\sum_{i=1}^{k}W(A_i,\hat A_i)

其中

\hat A_i

是除開集合A以外其它子集的並集。

那麼我們切圖無非就是要做到以下任務：

子圖間的cut值很小，而圖內的權值合很高

然而單純只考慮這一點會就會造成無法最好切割，我們注意到smallest cut是不合理的，合理的cut子圖不應該只包含一個節點，因此我們對節點進行約束，有以下兩種方案：

RatioCut和Ncut

RatioCut，我們切圖的時候不僅需要考慮cut的值，同時還要考慮到切圖之後的子圖內節點數量問題。

定義

| A|

為子圖內的節點個數。

將這個函式表示為：

RatioCut(A_1,A_2,...,A_k)=\frac{1}{2}\sum_{i=1}^{k}\frac{W(A_i,\hat A_i)}{|A_i|}

那麼無非就是要最小化這個函式就對了，最小化這個函式我們就可以得到一個合理的圖分割，該分割中還考慮的分割後的子圖大小。

但是問題是如何表示這樣一個函式呢，我們要的表示已經有了，如何轉化成代數的或者數學的方法來表示呢。為此我們要引入指示向量

h_j \in {h_1,h_2...,h_k }

對於其中任意一個向量其長度與我們的資料樣本個數相同而k是要聚類的樣本個數是一個超引數。那麼任意一個

h_{ij}

的意思就是，在第i個子圖中的第k的節點的h值，當k節點不屬於i圖時為0，當k節點屬於i圖時值為

\frac{1}{\sqrt{|A_i|}}

那麼

h_i^TLh_i=\frac{cut(A_i,\hat A_i)}{|A_i|}

為對於子圖i的RatioCut那麼我們就成功的找到了一個數學表示。

那麼對於所有的圖的表示呢：

RatioCut(A1,A2,....Ak)=tr(H^TLH)

可知RatioCut就是該矩陣的跡，那麼我們就是要最小化這個跡值即可。

瞭解到，對於其中的每一個子圖的最佳化目標

h_i^TLh_i

，由h定義可知其為正交的，而L又是對稱矩陣，而由矩陣乘法中，最大的特徵值將主導矩陣乘法的值，而矩陣特徵值所構成的特徵向量是相互正交的，而特徵值最小的代表了最無關的分量，那麼對於兩個圖而言，最無關的分量就代表了一個最優的割集，那麼n個最小的特徵值就構成了n個最優割之後的子圖。而對於130萬的資料而言，我們要聚類的數目是遠遠小於130萬這個值的，因此還可以藉此方法對資料進行大量的降維。而由這個n特特徵值重建的n個特徵向量就是我們的

H

，隨後對h進行標準化，然後對矩陣

H

進行聚類。

看原理介紹的時候，對其中的一個東西產生了疑惑，我們adajency matrix即我們事件的成對相似度，即我們還需要再adajency matrix的基礎上構建affinity matirx。（錯誤）

相似度矩陣就是affinity matrix，不需要進行任何的改動。只有我們尚且沒有對資料的距離，相似度進行度量的時候，我們才需要構建affinity matrix，比如在二維座標中，我們只有各個座標的點，因此我們需要在資料上構建affinity matrix，而當我們有了成對相似度之後，成對相似度就相當於一個距離度量，因此我們也就不用構建affinitiy matrix了。

但是在資料很大的時候，譜聚類往往是一個很爛的選擇，而且當圖聚類不是全連線或者不是稠密圖形的時候，譜聚類的效果也不是特別的理想。實驗室130萬條資料，非常的稀疏，要找到一個合適的聚類數目難於登天，如果真要除錯聚類數目的話可以除錯一輩子。這個時候就需要能夠自適應聚類數目的聚類方法，例如affinity clustering，至少在這種方法上可以不用手動調聚類數目了，有時間再繼續寫affinity clustering的方法。