拉普拉斯矩阵具有负特征值

Question

我试图用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')

True ClustersSpectral 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。然而，0与非正规拉普拉斯算子的明显多重性为1。诚然，一些紫色数据点（在真正的集群中）与其他集群非常接近，所以这可能不是完全出乎意料的