Effiziente Implementierung eines spektralen Clustering-Algorithmus in MATLAB für große Datensätze mit Lanczos-Verfahren und sparsamer Ähnlichkeitsmatrix.
% Effiziente Implementierung des spektralen Clusterings für große Datensätze
% Autor: Senior Software Engineer + Dozent
% Datum: 2024
function labels = spectral_clustering_large(X, k, sigma, dist_thresh)
% X: NxD Datenmatrix
% k: Anzahl der Cluster
% sigma: Parameter des Gaußschen Kernels
% dist_thresh: Distanzschwelle für Sparsität der Ähnlichkeitsmatrix
N = size(X,1);
% Berechnung der spärlichen Ähnlichkeitsmatrix W
% Vorallokation für Indizes und Werte
max_neighbors = 20; % maximale Nachbarn pro Punkt zur Begrenzung der Sparsität
idx_i = zeros(N*max_neighbors,1);
idx_j = zeros(N*max_neighbors,1);
vals = zeros(N*max_neighbors,1);
count = 0;
% Aufbau der Ähnlichkeitsmatrix mit approximativer Nachbarschaftssuche
% Zur Effizienz wird knnsearch mit k=max_neighbors verwendet
[idxs, dists] = knnsearch(X,X,'K',max_neighbors+1); % +1 für sich selbst
for i=1:N
for nn=2:max_neighbors+1 % ersten (sich selbst) überspringen
j = idxs(i,nn);
dist = dists(i,nn);
if dist < dist_thresh
count = count + 1;
idx_i(count) = i;
idx_j(count) = j;
vals(count) = exp(-dist^2/(2*sigma^2));
end
end
end
% Arrays auf tatsächliche Werte kürzen
idx_i = idx_i(1:count);
idx_j = idx_j(1:count);
vals = vals(1:count);
% Aufbau der symmetrischen spärlichen Ähnlichkeitsmatrix W
W = sparse([idx_i; idx_j],[idx_j; idx_i],[vals; vals],N,N);
% Berechnung der Gradmatrix D
d = sum(W,2);
D_inv_sqrt = spdiags(d.^(-0.5),0,N,N);
% Normalisierte Laplace-Matrix L = I - D^{-1/2} * W * D^{-1/2}
L = speye(N) - D_inv_sqrt * W * D_inv_sqrt;
% Berechnung der ersten k+1 Eigenvektoren von L (der erste ist Null-Eigenvektor)
opts.isreal = true;
opts.issym = true;
[U,~] = eigs(L,k+1,'smallestabs',opts);
% Ersten Eigenvektor ausschließen (assoziiert mit Eigenwert 0)
U = U(:,2:k+1);
% Zeilen von U normalisieren
U = bsxfun(@rdivide,U,sqrt(sum(U.^2,2)));
% k-means Clustering auf spektralen Vektoren
labels = kmeans(U,k,'MaxIter',1000,'Replicates',10);
end
% Beispiel zur Verwendung:
% load fisheriris
% X = meas;
% k = 3;
% sigma = 0.5;
% dist_thresh = 1.5;
% labels = spectral_clustering_large(X,k,sigma,dist_thresh);
% scatter(X(:,1),X(:,2),50,labels,'filled');% Beispiel für die Verwendung der Funktion spectral_clustering_large
% Dieses Skript lädt einen Beispieldatensatz, führt das spektrale Clustering durch und visualisiert die Ergebnisse.
% Originalfunktion aus der Datenbank
% Effiziente Implementierung des spektralen Clusterings für große Datensätze
% Autor: Senior Software Engineer + Dozent
% Datum: 2024
function labels = spectral_clustering_large(X, k, sigma, dist_thresh)
% X: NxD Datenmatrix
% k: Anzahl der Cluster
% sigma: Parameter des Gaußschen Kernels
% dist_thresh: Distanzschwelle für Sparsität der Ähnlichkeitsmatrix
N = size(X,1);
% Berechnung der spärlichen Ähnlichkeitsmatrix W
% Vorallokation für Indizes und Werte
max_neighbors = 20; % maximale Nachbarn pro Punkt zur Begrenzung der Sparsität
idx_i = zeros(N*max_neighbors,1);
idx_j = zeros(N*max_neighbors,1);
vals = zeros(N*max_neighbors,1);
count = 0;
% Aufbau der Ähnlichkeitsmatrix mit approximativer Nachbarschaftssuche
% Zur Effizienz wird knnsearch mit k=max_neighbors verwendet
[idxs, dists] = knnsearch(X,X,'K',max_neighbors+1); % +1 für sich selbst
for i=1:N
for nn=2:max_neighbors+1 % ersten (sich selbst) überspringen
j = idxs(i,nn);
dist = dists(i,nn);
if dist < dist_thresh
count = count + 1;
idx_i(count) = i;
idx_j(count) = j;
vals(count) = exp(-dist^2/(2*sigma^2));
end
end
end
% Arrays auf tatsächliche Werte kürzen
idx_i = idx_i(1:count);
idx_j = idx_j(1:count);
vals = vals(1:count);
% Aufbau der symmetrischen spärlichen Ähnlichkeitsmatrix W
W = sparse([idx_i; idx_j],[idx_j; idx_i],[vals; vals],N,N);
% Berechnung der Gradmatrix D
d = sum(W,2);
D_inv_sqrt = spdiags(d.^(-0.5),0,N,N);
% Normalisierte Laplace-Matrix L = I - D^{-1/2} * W * D^{-1/2}
L = speye(N) - D_inv_sqrt * W * D_inv_sqrt;
% Berechnung der ersten k+1 Eigenvektoren von L (der erste ist Null-Eigenvektor)
opts.isreal = true;
opts.issym = true;
[U,~] = eigs(L,k+1,'smallestabs',opts);
% Ersten Eigenvektor ausschließen (assoziiert mit Eigenwert 0)
U = U(:,2:k+1);
% Zeilen von U normalisieren
U = bsxfun(@rdivide,U,sqrt(sum(U.^2,2)));
% k-means Clustering auf spektralen Vektoren
labels = kmeans(U,k,'MaxIter',1000,'Replicates',10);
end
% Hauptskript zur Demonstration
% Laden des Fisher Iris Datensatzes
load fisheriris
X = meas; % Messdaten
k = 3; % Anzahl der Cluster
sigma = 0.5; % Parameter für Gaußschen Kernel
dist_thresh = 1.5; % Distanzschwelle für Sparsität
% Aufruf der spektralen Clustering-Funktion
labels = spectral_clustering_large(X,k,sigma,dist_thresh);
% Visualisierung der Clusterergebnisse
figure;
scatter(X(:,1),X(:,2),50,labels,'filled');
title('Spektrales Clustering der Iris-Daten');
xlabel('Merkmal 1');
ylabel('Merkmal 2');
grid on;Datensatz: Datenmatrix der Größe NxD (N Proben, D Dimensionen)
Aufbau der Ähnlichkeitsmatrix W: spärliche NxN-Matrix, berechnet mit Gaußschem Kernel und Distanzschwelle für Sparsität
Normalisierte Laplace-Matrix L = I - D^{-1/2} W D^{-1/2}, mit D diagonaler Gradmatrix
Berechnung dominanter Eigenvektoren von L mittels Lanczos-Verfahren (MATLAB eigs-Funktion)
k-means Clustering auf den ersten k Eigenvektoren (spektrale Einbettung)
Software-Konfiguration: MATLAB R2020b oder höher mit Sparse Matrix und Statistics and Machine Learning Toolbox
Abhängigkeiten: keine externen, alles mit nativen MATLAB-Funktionen implementiert
Parameter-Konfiguration: Anzahl der Cluster k, Sigma-Parameter für Gaußschen Kernel, Distanzschwelle für Sparsität
Optimierung: Verwendung spärlicher Matrizen für W und L, Eigenvektorberechnung mit eigs auf die ersten k+1 Eigenwerte beschränkt
Ausgabe: Cluster-Label-Vektor für jeden Punkt