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 ]

我很确定我的问题出在 nlapl 中，因为如果我使用未归一化的拉普拉斯 D - W，则特征值为[-4.96328563e-15 5.94245930e-03 1.15181852e-02 1.51614560e-01]. 但是，我无法弄清楚我的计算错误的地方。我错过了一些明显的东西吗？提前感谢您的任何建议。

编辑：由于我的玩具数据集有 4 个分离良好的集群，因此 L 的零特征值的理论重数应该是 4。但是，对于未归一化的拉普拉斯算子，显然零重数是 1。诚然，一些紫色数据点（在 True集群）非常接近其他集群，所以这可能不是完全出乎意料吗？

4

0 回答 0