2

Python で正規化された (ランダム ウォーク) ラプラシアン行列を使用して、単純なバージョンのスペクトル クラスタリングを実装しようとしています。おもちゃのデータセットで関数をテストした後、ラプラシアン行列に負の固有値があることがわかりました。ここに私のスペクトルクラスタリングコードがあります:

import numpy as np
from sklearn.cluster import KMeans
from sklearn.metrics.pairwise import pairwise_kernels, euclidean_distances, pairwise_distances
from sklearn.neighbors import NearestNeighbors

def nlapl(W):
    Dinv = 1 / np.sum(W, axis=1)
    Id = np.eye(W.shape[0])
    W = np.multiply(Dinv, W.T).T
    return Id - W

def sc(X, n_clusters, gamma):
    W = pairwise_kernels(X, metric='rbf', gamma=gamma)
    L = nlapl(W)

    lambdas, vs = np.linalg.eigh(L)
    lambdas = lambdas[:n_clusters]
    vs = vs[:,:n_clusters]

    print("lambdas:")
    print(lambdas)

    kmeans = KMeans(n_clusters=n_clusters, init='k-means++', max_iter=300, n_init=20, random_state=0).fit(vs)
    return vs, kmeans

ここに私のテストコードがあります:

from sklearn.datasets.samples_generator import make_blobs

X, y = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=0)
vs, kmeans = sc(X, 4, 2)

関数はクラスターを正常に識別します。

plt.figure()
plt.scatter(X[:,0], X[:,1], c=y, alpha=0.7)
plt.title('True Clusters')

plt.figure()
plt.scatter(X[:,0], X[:,1], c=kmeans.labels_, alpha=0.7)
plt.title('Spectral Clustering')

真のクラスター スペクトル クラスタリング

ただし、ラプラシアン行列には負の固有値があります。

lambdas:
[-0.03429643 -0.02670478 -0.01684407 -0.0073953 ]

正規化されていないラプラシアン D-W を使用すると固有値が[-4.96328563e-15 5.94245930e-03 1.15181852e-02 1.51614560e-01]. しかし、計算のどこが間違っているのかわかりません。明らかな何かが欠けていますか？アドバイスをよろしくお願いします。

編集: 私のおもちゃのデータセットには 4 つの十分に分離されたクラスターがあるため、L のゼロ固有値の理論上の多重度は 4 である必要があります。ただし、正規化されていないラプラシアンでのゼロの見かけ上の多重度は 1 です。クラスター) は他のクラスターにかなり近いので、これは完全に予想外ではないでしょうか?

4

0 に答える 0