基本概念
定义无向图$G={V,E,W}$，其中，$V$为图的顶点，$E$为图的边，$W$为图中边的权值矩阵。
定义顶点的度 为该顶点与其他顶点连接权值之和：
d i = ∑ j = 1 N w i j d_i = \sum_{j=1}^N w_{ij} d i = j = 1 ∑ N w ij 度矩阵 $D$为：
D = [ d 1 d 2 ⋱ d N ] D = \left [ \begin{matrix} d_1&&& \\ &d_2&& \\ &&\ddots& \\ &&&&d_N \end{matrix} \right ] D = d 1 d 2 ⋱ d N 图的邻接矩阵（相似矩阵）$W$：
W = [ w i j ] ， 1 ≤ i , j ≤ N W=[w_{ij}]，1\leq i,j\leq N W = [ w ij ] ， 1 ≤ i , j ≤ N 对于$V$的一个子集$A\subset V$：
V = ∪ k = 1 K A k A i ∩ A j = ⊘ ， ∀ i , j ∈ { 1 , 2 , ⋯ , N } v o l ( A ) = ∑ i ∈ A d i \begin{align} &V = \cup_{k=1}^K A_k\\ &A_i \cap A_j = \oslash，\forall i,j \in \{1,2,\cdots,N\} \\ &vol(A) = \sum_{i\in A} d_i \end{align} V = ∪ k = 1 K A k A i ∩ A j = ⊘ ， ∀ i , j ∈ { 1 , 2 , ⋯ , N } v o l ( A ) = i ∈ A ∑ d i 相似矩阵
邻接矩阵 $W$：由任意两点之间的权重值$w_{ij}$组成的矩阵。通常手动输入权重，但是在谱聚类中，只有数据点的定义，并没有直接给出这个邻接矩阵，那么如何构造邻接矩阵？
基本思想 ：距离较远 的两个点之间的边权重值较低 ，而距离较近 的两个点之间的边权重值较高 ，不过这仅仅是定性，需要定量的权重值。一般来说，我们可以通过样本点距离度量的相似矩阵$S$来获得邻接矩阵$W$。
构造方法 ：这里采用全连接法 进行构造邻接矩阵。可以采用不同的核函数来定义边权重，这里采用高斯核函数RBF ：
拉普拉斯矩阵
拉普拉斯矩阵定义 ：
其中，$D$为度矩阵，$W$为邻接矩阵。
拉普拉斯矩阵的性质 ：
f T L f = 1 2 ∑ i , j = 1 n w i j ( f i − f j ) 2 f^TLf = \frac{1}{2} \sum_{i,j=1}^n w_{ij}(f_i-f_j)^2 f T L f = 2 1 i , j = 1 ∑ n w ij ( f i − f j ) 2 于是，可以得知：
f T L f = f T D f − f T W f = ∑ i = 1 N d i f i 2 − ∑ i , j = 1 N w i j f i f j = 1 2 ( ∑ i = 1 N d i f i 2 − 2 ∑ i , j = 1 N w i j f i f j + ∑ j = 1 N d j f j 2 ) = 1 2 ∑ i , j = 1 N w i j ( f i − f j ) 2 \begin{align} f^TLf &= f^TDf - f^TWf \\ &= \sum_{i=1}^N d_i f_i^2 - \sum_{i,j=1}^N w_{ij}f_if_j \\ &= \frac{1}{2}(\sum_{i=1}^N d_i f_i^2 - 2\sum_{i,j=1}^N w_{ij}f_if_j+\sum_{j=1}^N d_j f_j^2) \\ &= \frac{1}{2}\sum_{i,j=1}^N w_{ij}(f_i-f_j)^2 \end{align} f T L f = f T D f − f T W f = i = 1 ∑ N d i f i 2 − i , j = 1 ∑ N w ij f i f j = 2 1 ( i = 1 ∑ N d i f i 2 − 2 i , j = 1 ∑ N w ij f i f j + j = 1 ∑ N d j f j 2 ) = 2 1 i , j = 1 ∑ N w ij ( f i − f j ) 2 拉普拉斯矩阵是半正定的，且对应的n个实数特征值都大于等于0$(0=\lambda_1\leq \lambda_2 \leq \cdots \leq \lambda_N)$，且最小的特征值为0，对应的特征向量是单位向量。
由图分割问题到谱聚类问题
对于无向图$G$的切割图，目标是将图$G$切分成相互没有连接的$k$个子图，每个子图点的集合为：
V = ∪ k = 1 K A k A i ∩ A j = ⊘ ， ∀ i , j ∈ { 1 , 2 , ⋯ , N } \begin{align} &V = \cup_{k=1}^K A_k\\ &A_i \cap A_j = \oslash，\forall i,j \in \{1,2,\cdots,N\} \\ \end{align} V = ∪ k = 1 K A k A i ∩ A j = ⊘ ， ∀ i , j ∈ { 1 , 2 , ⋯ , N } 对于任意两个子图点的集合$A,B \subset V,A\cap B = \oslash$，定义$A$和$B$之间的切图之间的权重为：
W ( A , B ) = ∑ i ∈ A , j ∈ B w i j W(A,B) = \sum_{i\in A,j\in B} w_{ij} W ( A , B ) = i ∈ A , j ∈ B ∑ w ij 对于k个子图点的集合，定义切图$cut$为：
c u t ( V ) = c u t ( A 1 , A 2 , ⋯ , A k ) = ∑ k = 1 K W ( A k , A k ˉ ) = ∑ k = 1 K W ( A k , V ) − W ( A k , A k ) \begin{align} cut(V) &= cut(A_1,A_2,\cdots,A_k) \\ &= \sum_{k=1}^K W(A_k,\bar{A_k}) \\ &= \sum_{k=1}^K W(A_k,V) - W(A_k,A_k) \end{align} c u t ( V ) = c u t ( A 1 , A 2 , ⋯ , A k ) = k = 1 ∑ K W ( A k , A k ˉ ) = k = 1 ∑ K W ( A k , V ) − W ( A k , A k ) 其中，$\bar{A_i}$为$A_i$的补集（除去$A_i$子集以外其他的属于$V$的结点的集合）。
为了让切图可以让子图内的点权重和高(内部连接强)，子图间的点权重和低(外部连接弱)，需要使$cut$达到最小化。
优化目标：
m a x { A k } k = 1 K c u t ( V ) = ∑ i = 1 K W ( A i , A i ˉ ) \begin{align} \mathop{max}\limits_{\{A_k\}^K_{k=1}} cut(V) = \sum\limits_{i=1}^K W(A_i,\bar{A_i}) \end{align} { A k } k = 1 K ma x c u t ( V ) = i = 1 ∑ K W ( A i , A i ˉ ) 为了避免最小切图导致的切图效果不佳，需要对每个子图的规模做出限定。这里得到了一个新的优化目标：
N c u t ( A 1 , A 2 , ⋯ , A k ) = 1 2 ∑ i = 1 K W ( A i , A i ˉ ) v o l ( A i ) = 1 2 ∑ i = 1 K W ( A i , A i ˉ ) ∑ i ∈ A k d i ， d i = ∑ j = 1 N w i j Ncut(A_1,A_2,\cdots,A_k) = \frac{1}{2} \sum\limits_{i=1}^K \frac{W(A_i,\bar{A_i})}{vol(A_i)} = \frac{1}{2} \sum\limits_{i=1}^K \frac{W(A_i,\bar{A_i})}{\sum\limits_{i\in A_k}d_i}，d_i=\sum_{j=1}^Nw_{ij} N c u t ( A 1 , A 2 , ⋯ , A k ) = 2 1 i = 1 ∑ K v o l ( A i ) W ( A i , A i ˉ ) = 2 1 i = 1 ∑ K i ∈ A k ∑ d i W ( A i , A i ˉ ) ， d i = j = 1 ∑ N w ij 由上可知，算法的目标函数为：
{ A k ^ } k = 1 K = a r g m i n { A k } k = 1 K ∑ k = 1 K W ( A k , v ) − W ( A k , A K ) ∑ i ∈ A k ∑ j = 1 N w i j \{\hat{A_k} \}_{k=1}^K = \mathop{argmin}_{\{A_k\}^K_{k=1}} \sum\limits_{k=1}^K\frac{W(A_k,v)-W(A_k,A_K)}{\sum\limits_{i\in A_k}\sum\limits_{j=1}^Nw_{ij}} { A k ^ } k = 1 K = a r g min { A k } k = 1 K k = 1 ∑ K i ∈ A k ∑ j = 1 ∑ N w ij W ( A k , v ) − W ( A k , A K ) 由于求解的时候，不方便计算，于是设法将目标函数转换为矩阵的形式表达。
引入指示向量
令
其中，$y_i$是一个$k$维的向量，每一个维度的值为0或者1；$y_{ij}$表示第$i$个样本属于第$j$个类别，并且每个样本只能属于一个类别。
由上，可知目标函数为：
Y = ( y 1 , y 2 , ⋯ , y N ) N × K T Y ^ = a r g m i n Y N c u t ( V ) = a r g m i n Y ∑ k = 1 K W ( A k , A k ˉ ) ∑ i ∈ A k d i \begin{align} &Y = (y_1,y_2,\cdots,y_N)_{N\times K}^T \\ &\hat Y = \mathop{argmin}\limits_{Y} Ncut(V) = \mathop{argmin}\limits_Y \sum\limits_{k=1}^K \frac{W(A_k,\bar{A_k})}{\sum\limits_{i \in A_k}d_i} \end{align} Y = ( y 1 , y 2 , ⋯ , y N ) N × K T Y ^ = Y a r g min N c u t ( V ) = Y a r g min k = 1 ∑ K i ∈ A k ∑ d i W ( A k , A k ˉ ) 又，
∑ k = 1 K W ( A k , A k ˉ ) ∑ i ∈ A k d i = t r [ W ( A 1 , A 1 ˉ ) ∑ i ∈ A 1 d i W ( A 2 , A 2 ˉ ) ∑ i ∈ A 2 d i ⋱ W ( A K , A K ˉ ) ∑ i ∈ A K d i ] = t r [ W ( A 1 , A 1 ˉ ) W ( A 2 , A 2 ˉ ) ⋱ W ( A K , A K ˉ ) ] K × K ⏟ O ⋅ [ [ ∑ i ∈ A 1 d i ∑ i ∈ A 2 d i ⋱ ∑ i ∈ A K d i ] K × K ⏟ P ] − 1 = t r ( O P − 1 ) \begin{align} \sum\limits_{k=1}^K \frac{W(A_k,\bar{A_k})}{\sum\limits_{i \in A_k}d_i} &= tr \left [ \begin{matrix} \frac{W(A_1,\bar{A_1})}{\sum\limits_{i \in A_1}d_i}&&& \\ &\frac{W(A_2,\bar{A_2})}{\sum\limits_{i \in A_2}d_i}&& \\ &&\ddots& \\ &&&&\frac{W(A_K,\bar{A_K})}{\sum\limits_{i \in A_K}d_i} \end{matrix} \right ] \\ &= tr \underbrace{\left [ \begin{matrix} W(A_1,\bar{A_1})&&& \\ &W(A_2,\bar{A_2})&& \\ &&\ddots& \\ &&&&W(A_K,\bar{A_K}) \end{matrix} \right ]_{K\times K}}_{O} \cdot \left[\underbrace{\left [ \begin{matrix} \sum\limits_{i \in A_1}d_i&&& \\ &\sum\limits_{i \in A_2}d_i&& \\ &&\ddots& \\ &&&&\sum\limits_{i \in A_K}d_i \end{matrix} \right ]_{K\times K}}_{P}\right]^{-1} \\ = tr(OP^{-1}) \end{align} k = 1 ∑ K i ∈ A k ∑ d i W ( A k , A k ˉ ) = t r ( O P − 1 ) = t r i ∈ A 1 ∑ d i W ( A 1 , A 1 ˉ ) i ∈ A 2 ∑ d i W ( A 2 , A 2 ˉ ) ⋱ i ∈ A K ∑ d i W ( A K , A K ˉ ) = t r O W ( A 1 , A 1 ˉ ) W ( A 2 , A 2 ˉ ) ⋱ W ( A K , A K ˉ ) K × K ⋅ P i ∈ A 1 ∑ d i i ∈ A 2 ∑ d i ⋱ i ∈ A K ∑ d i K × K − 1 现在已知$W$，$Y$，求$O$，$P$，注意$Y$矩阵是$N\times K$维的，行代表结点标号，列代表属于的类别，其中$y_{ij}$表示第$i$个样本属于第$j$个类别。
有，
y i y i T = [ 0 , 0 , ⋯ , y i j = 1 , ⋯ , 0 ] ⋅ [ 0 0 ⋯ y i j = 1 ⋯ 0 ] = [ 0 ⋯ 0 ⋯ 0 ⋮ ⋱ ⋮ ⋱ ⋮ 0 ⋯ y j j = 1 ⋯ 0 ⋮ ⋱ ⋮ ⋱ ⋮ 0 ⋯ 0 ⋯ 0 ] \begin{align} y_iy_i^T&= \left[\begin{matrix}0,0,\cdots,y_{ij}=1,\cdots,0\end{matrix}\right]\cdot \left[\begin{matrix}0\\0\\\cdots\\y_{ij}=1\\\cdots\\0\end{matrix}\right] \\ &= \left[ \begin{matrix} 0&\cdots&0&\cdots&0 \\ \vdots&\ddots&\vdots&\ddots&\vdots\\ 0&\cdots&y_{jj}=1&\cdots&0 \\ \vdots&\ddots&\vdots&\ddots&\vdots\\ 0&\cdots&0&\cdots&0 \\ \end{matrix} \right] \end{align} y i y i T = [ 0 , 0 , ⋯ , y ij = 1 , ⋯ , 0 ] ⋅ 0 0 ⋯ y ij = 1 ⋯ 0 = 0 ⋮ 0 ⋮ 0 ⋯ ⋱ ⋯ ⋱ ⋯ 0 ⋮ y jj = 1 ⋮ 0 ⋯ ⋱ ⋯ ⋱ ⋯ 0 ⋮ 0 ⋮ 0 于是，
Y T Y = ( y 1 , y 2 , ⋯ , y N ) ⋅ ( y 1 T , y 2 T , ⋯ , y N T ) = ∑ i = 1 N y i y i T = [ N 1 N 2 ⋱ N K ] K × K \begin{align} Y^TY &= (y_1,y_2,\cdots,y_N)\cdot (y_1^T,y_2^T,\cdots,y_N^T) \\ &=\sum\limits_{i=1}^N y_iy_i^T \\ &= \left[ \begin{matrix} N_1&&&&\\ &N_2&&&\\ &&\ddots&\\ &&&&N_K\\ \end{matrix} \right]_{K\times K} \end{align} Y T Y = ( y 1 , y 2 , ⋯ , y N ) ⋅ ( y 1 T , y 2 T , ⋯ , y N T ) = i = 1 ∑ N y i y i T = N 1 N 2 ⋱ N K K × K 其中，$N_K$表示在$N$个样本中，属于类别$k$的样本个数，且$\sum\limits_{k=1}^KN_k = N$，$N_k = |A_k|=\sum\limits_{i\in A_k} 1_N$，$1_N$表示元素全为$1$的$N\times 1$维向量。
有，
P = ∑ i = 1 N y i T d i y i = Y T D Y = Y T ( W ⋅ 1 N ) Y P = \sum\limits_{i=1}^Ny_i^Td_iy_i = Y^TDY = Y^T(W\cdot1_N)Y P = i = 1 ∑ N y i T d i y i = Y T D Y = Y T ( W ⋅ 1 N ) Y 使用拉普拉斯矩阵的性质，简化$O$矩阵，如下：
O = [ W ( A 1 , A 1 ˉ ) W ( A 2 , A 2 ˉ ) ⋱ W ( A K , A K ˉ ) ] = [ W ( A 1 , V ) W ( A 2 , V ) ⋱ W ( A K , V ) ] − [ W ( A 1 , A 1 ) W ( A 2 , A 2 ) ⋱ W ( A K , A K ) ] = [ ∑ i ∈ A 1 d i ∑ i ∈ A 2 d i ⋱ ∑ i ∈ A K d i ] − [ W ( A 1 , A 1 ) W ( A 2 , A 2 ) ⋱ W ( A K , A K ) ] \begin{align} O &= \left [ \begin{matrix} W(A_1,\bar{A_1})&&& \\ &W(A_2,\bar{A_2})&& \\ &&\ddots& \\ &&&&W(A_K,\bar{A_K}) \end{matrix} \right ] \\ &= \left [ \begin{matrix} W(A_1,V)&&& \\ &W(A_2,V)&& \\ &&\ddots& \\ &&&&W(A_K,V) \end{matrix} \right ] - \left [ \begin{matrix} W(A_1,A_1)&&& \\ &W(A_2,A_2)&& \\ &&\ddots& \\ &&&&W(A_K,A_K) \end{matrix} \right ] \\ &= \left [ \begin{matrix} \sum\limits_{i \in A_1} d_i&&& \\ &\sum\limits_{i \in A_2} d_i&& \\ &&\ddots& \\ &&&&\sum\limits_{i \in A_K} d_i \end{matrix} \right ] - \left [ \begin{matrix} W(A_1,A_1)&&& \\ &W(A_2,A_2)&& \\ &&\ddots& \\ &&&&W(A_K,A_K) \end{matrix} \right ] \\ \end{align} O = W ( A 1 , A 1 ˉ ) W ( A 2 , A 2 ˉ ) ⋱ W ( A K , A K ˉ ) = W ( A 1 , V ) W ( A 2 , V ) ⋱ W ( A K , V ) − W ( A 1 , A 1 ) W ( A 2 , A 2 ) ⋱ W ( A K , A K ) = i ∈ A 1 ∑ d i i ∈ A 2 ∑ d i ⋱ i ∈ A K ∑ d i − W ( A 1 , A 1 ) W ( A 2 , A 2 ) ⋱ W ( A K , A K ) 由于，
Y T W T = [ y 1 y 2 ⋯ y N ] [ w 11 ⋯ w 1 N ⋮ ⋱ ⋮ w N 1 ⋯ w N N ] [ y 1 T y 2 T ⋯ y N T ] = [ ∑ i = 1 N y 1 w i 1 ∑ i = 1 N y 2 w i 2 ⋯ ∑ i = 1 N y N w i N ] [ y 1 T y 2 T ⋯ y N T ] = ∑ i = 1 N ∑ j = 1 N y i w i j y j T = ∑ i = 1 N ∑ j = 1 N y i y j T w i j = [ ∑ i ∈ A 1 , j ∈ A 1 w i j ∑ i ∈ A 1 , j ∈ A 2 w i j ⋯ ∑ i ∈ A 1 , j ∈ A N w i j ⋮ ⋮ ⋱ ⋮ ∑ i ∈ A N , j ∈ A 1 w i j ∑ i ∈ A N , j ∈ A 2 w i j ⋯ ∑ i ∈ A N , j ∈ A N w i j ] \begin{align} Y^TWT &= \left[ \begin{matrix} y_1 &y_2&\cdots&y_N \end{matrix} \right] \left[ \begin{matrix} w_{11}&\cdots&w_{1N} \\ \vdots&\ddots&\vdots \\ w_{N1}&\cdots&w_{NN} \\ \end{matrix} \right] \left[ \begin{matrix} y_1^T\\y_2^T\\\cdots\\y_N^T \end{matrix} \right] \\ &= \left[ \begin{matrix} \sum\limits_{i=1}^N y_1w_{i1} &\sum\limits_{i=1}^N y_2w_{i2}&\cdots&\sum\limits_{i=1}^N y_Nw_{iN} \end{matrix} \right] \left[ \begin{matrix} y_1^T\\y_2^T\\\cdots\\y_N^T \end{matrix} \right] \\ &=\sum\limits_{i=1}^N \sum\limits_{j=1}^N y_iw_{ij}y_j^T = \sum\limits_{i=1}^N \sum\limits_{j=1}^N y_iy_j^Tw_{ij} \\ &= \left[ \begin{matrix} \sum\limits_{i\in A_1,j\in A_1}w_{ij}&\sum\limits_{i\in A_1,j\in A_2}w_{ij}&\cdots& \sum\limits_{i\in A_1,j\in A_N}w_{ij} \\ \vdots&\vdots&\ddots&\vdots \\ \sum\limits_{i\in A_N,j\in A_1}w_{ij}&\sum\limits_{i\in A_N,j\in A_2}w_{ij}&\cdots& \sum\limits_{i\in A_N,j\in A_N}w_{ij} \end{matrix} \right] \end{align} Y T W T = [ y 1 y 2 ⋯ y N ] w 11 ⋮ w N 1 ⋯ ⋱ ⋯ w 1 N ⋮ w NN y 1 T y 2 T ⋯ y N T = [ i = 1 ∑ N y 1 w i 1 i = 1 ∑ N y 2 w i 2 ⋯ i = 1 ∑ N y N w i N ] y 1 T y 2 T ⋯ y N T = i = 1 ∑ N j = 1 ∑ N y i w ij y j T = i = 1 ∑ N j = 1 ∑ N y i y j T w ij = i ∈ A 1 , j ∈ A 1 ∑ w ij ⋮ i ∈ A N , j ∈ A 1 ∑ w ij i ∈ A 1 , j ∈ A 2 ∑ w ij ⋮ i ∈ A N , j ∈ A 2 ∑ w ij ⋯ ⋱ ⋯ i ∈ A 1 , j ∈ A N ∑ w ij ⋮ i ∈ A N , j ∈ A N ∑ w ij 令，
O ′ = Y T D Y − Y W Y O^{'} = Y^TDY - Y^WY O ′ = Y T D Y − Y W Y 由$trace$性质可知，
t r ( O ′ P − 1 ) = t r ( O P − 1 ) tr(O^{'}P^{-1}) = tr(OP^{-1}) t r ( O ′ P − 1 ) = t r ( O P − 1 ) 其中，$O^{'}$与$O$的对角元素一样。
于是，有
Y ^ = a r g m i n Y t r ( O P − 1 ) = a r g m i n Y t r [ Y T L Y ⋅ ( Y T D Y ) − 1 ] \hat Y = \mathop{argmin}_{Y} \ tr(OP^{-1}) = \mathop{argmin}_{Y} \ tr[Y^TLY\cdot (Y^TDY)^{-1}] Y ^ = a r g min Y t r ( O P − 1 ) = a r g min Y t r [ Y T L Y ⋅ ( Y T D Y ) − 1 ] 定义$H$为新的指示向量：
有，
于是，
H ^ = a r g m i n H t r ( H T L H ) ， s . t . H T D H = I \hat H = \mathop{argmin}_{H}\ tr(H^TLH)，s.t.H^TDH=I H ^ = a r g min H t r ( H T L H ) ， s . t . H T DH = I 记，$H=D^{-\frac{1}{2}}F$，有$F^TF=I$，
F ^ = a r g m i n F t r ( F T D − 1 2 L D − 1 2 F ) \hat F = \mathop{argmin}_F \ tr(F^T{D^{-\frac{1}{2}}}L{D^{-\frac{1}{2}}}F) F ^ = a r g min F t r ( F T D − 2 1 L D − 2 1 F ) 注意$Y^TY$与$H^TH$表示的含义，两者的主对角线的值是相反的。
谱聚类实现
复制 import warnings
import numpy as np
import matplotlib.pyplot as plt
from sklearn import preprocessing
from sklearn.cluster import KMeans
from sklearn.metrics import accuracy_score,recall_score
from sklearn.datasets.samples_generator import make_blobs
warnings.filterwarnings('ignore')
复制 class SpectralClustering:
def __init__(self,n_clusters=None,sigma=None,normalize=0):
"""
"""
self.n_clusters = n_clusters
self.W = None
self.N = None # 样本数量/结点数量
self.D = None # 度矩阵
self.L = None # 拉普拉斯矩阵
self.sigma = sigma # 高斯函数的sigma
self.score = None
self.normalize = normalize
if self.n_clusters == None:
self.n_clusters = 2
if self.sigma == None:
self.sigma = 3
def init_params(self,X,y):
self.X,self.y = X,y
self.N = X.shape[0]
self.W = self.similaryMatrix(X)
self.D = self.diagMatrix()
self.L = self.laplacianMatrix()
def diagMatrix(self,):
"""
对角矩阵
"""
diag = np.sum(self.W,axis=1)
diag = np.squeeze(diag)
return np.diag(diag)
def kernel(self,num,x,y):
if num == 1: # 选择高斯核函数
distance = ((x - y)@(x - y))
return np.exp(-distance/(2*self.sigma*self.sigma)) # 高斯函数
def similaryMatrix(self,data):
"""
相似矩阵/邻接矩阵/权值矩阵，权重值为距离的平方的倒数，表示越近的结点权重越大，越远的结点权重越小
"""
S = np.zeros((self.N,self.N))
for i in range(self.N):
for j in range(self.N):
S[i,j] = S[j,i] = self.kernel(1,data[i],data[j])
S = S - np.diag(np.diag(S))
return S
def laplacianMatrix(self):
L = self.D - self.W
if self.normalize == 1:
return np.sqrt(np.linalg.pinv(self.D)).dot(L).dot(np.sqrt(np.linalg.pinv(self.D)))
return L
def getEigenvectors(self,):
eigenvalue,eigenvector = np.linalg.eig(self.L)
index = np.argsort(eigenvalue)[:self.n_clusters]
eigenvector = eigenvector[:,index]
if self.normalize == 1:
# eigenvector = preprocessing.StandardScaler().fit(
eigenvector).transform(eigenvector) # 正则化
eigenvector = preprocessing.normalize(eigenvector, norm='l2')
return eigenvector
def fit(self,X,y):
self.init_params(X,y)
vector = self.getEigenvectors()
self.kmeans = KMeans(n_clusters=self.n_clusters)
self.kmeans.fit(vector)
self.y_pred = self.prediction()
self.score = self.calc_score()
self.plot()
def prediction(self,):
return self.kmeans.labels_
def plot(self,):
plt.scatter(X[:,0],X[:,1],c=self.y_pred)
def calc_score(self,):
a = accuracy_score(1-self.y_pred,self.y)
b = accuracy_score(self.y_pred,self.y)
return a if a>b else b
复制 def create_data():
X,y = make_blobs(n_samples=500,centers=2,random_state=4)
return X,y
X,y = create_data()
plt.scatter(X[:,0],X[:,1],c=y)
复制 sc = SpectralClustering(n_clusters=2,normalize=1)
sc.fit(X,y)
sc.score 
