I need to combine my affinity matrices for a project using the Affinity Aggregation Spectral Clustering (AASC) algorithm. I have implemented the AASC Algorithm 1 proposed in this paper (link below) to calculate the weight parameters of individual affinity matrices in Python code. However, I am having trouble updating the weighting parameters (vk values) in the loop that was suggested in the paper.
The paper can be found at here and a screenshot of the proposed algorithm in the paper here
In step 12 of the algorithm, I expected to obtain a scalar as the weight parameter for an individual affinity matrix (vk[k]). However, I always receive a vector instead. Unfortunately, I have not been able to identify the problem in any of the previous algorithm steps.
Below, you will find my used python code and a fictitious example of data and affinity matrices. The step numbers correspond to the steps in the paper/algorithm 1.
Can someone please tell me where I made a mistake in my code implementation or the mathematical misinterpretation? Thanks a lot.
import numpy as np
from scipy.linalg import eigh
from scipy.optimize import minimize
def affinity_aggregation_spectral_clustering(data, affinities, C):
# Step 1
n = data.shape[0]
m = len(affinities)
# Step 2
vk = np.ones(m) / m # vk = array([0.5, 0.5])
# Step 3
max_iter = 100
epsilon = 1e-5
for _ in range(max_iter):
# Step 4
W = np.zeros((n, n))
# Step 5
for k, affinity in enumerate(affinities):
W += np.dot(vk[k]**2, affinity)
D = np.diag(np.sum(W, axis=1))
# Step 6
L = D - W
_, eigenvectors = eigh(L, D)
# Step 7
indicators = eigenvectors[:, 1:C+1]
# Step 8
# Step 9
alpha_k = np.dot(np.dot(indicators.T, D), indicators)
beta_k = np.dot(np.dot(indicators.T, (D-W)), indicators)
gamma_k = beta_k/alpha_k
# Step 10
def objective_function(lambda_1, gammas, alphas):
numerator = np.sum([1 / ((gamma_k - lambda_1) * alpha_k) for gamma_k, alpha_k in zip(gammas, alphas)])
denominator = np.sum([1 / ((gamma_k - lambda_1) ** 2 * alpha_k) for gamma_k, alpha_k in zip(gammas, alphas)])
expression_value = numerator ** 2 / denominator
return abs(expression_value - 1)
initial_guess = 0.01
result = minimize(objective_function, initial_guess, args=(gamma_k, alpha_k))
lambda_1 = result.x[0]
# Step 11
denominator = np.sum([1 / ((gamma_k - lambda_1) * alpha_k) for gamma_k, alpha_k in zip(gamma_k, alpha_k)])
lambda_2 = 1 / denominator
# Step 12
vk = lambda_2 / ((gamma_k - lambda_1) * alpha_k) # vk = array([[-1.94517448e-13 -1.81958962e+05], [ 1.81959962e+05 -1.65511496e-13]]) which is not the correct format, see step 2
# Step 13
if np.linalg.norm(vk - np.ones(m) / m) < epsilon:
break
# Step 14
# I need only the weight values for my project. Therefore, I have not implemented this step.
# Step 15
return vk
# -------------------------------------------------------
# Test example
data = np.array([[-1, -3], [1, 1], [0, 3], [6, 4], [4, -5]])
affinity_1 = np.array([[1, 0.5, 0.4, 0.1, 0.2],
[0.5, 1, 0.3, 0.2, 0.4],
[0.4, 0.3, 1, 0.5, 0.5],
[0.1, 0.2, 0.5, 1, 0.3],
[0.2, 0.4, 0.5, 0.3, 1]])
affinity_2 = np.array([[1, 0.2, 0.2, 0.9, 0.4],
[0.2, 1, 0.6, 0.4, 0.5],
[0.2, 0.6, 1, 0.1, 0.6],
[0.9, 0.4, 0.1, 1, 0.8],
[0.4, 0.5, 0.6, 0.8, 1]])
affinities = [affinity_1, affinity_2]
C = 2 # number of clusters
vk = affinity_aggregation_spectral_clustering(data, affinities, C)
print("Weights vk:", vk)