Лапласова матрица имеет отрицательные собственные значения - PullRequest
Новая
       80

Лапласова матрица имеет отрицательные собственные значения

1 голос
/ 01 мая 2020

Я пытаюсь реализовать простую версию спектральной кластеризации с использованием нормализованной (случайной блуждания) матрицы Лапласа в 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. По общему признанию, некоторые фиолетовые точки данных (в Истинных Кластерах) довольно близки к другим кластерам, так что, может быть, это не совсем неожиданно?

...