CAN与PCAN自适应邻居聚类算法：从原理到MATLAB代码实现

1次阅读

没有评论

共计 1453 个字符，预计需要花费 4 分钟才能阅读完成。

在数据挖掘中，聚类算法常用于发现数据的内在结构。传统算法如 k -means 存在明显局限：

需要预先指定簇数量 k
对初始中心点敏感
假设簇呈球形分布
无法处理流形数据

自适应邻居聚类通过动态确定每个点的邻居关系，能更好地捕捉复杂数据结构。下面我们重点解析 CAN 和 PCAN 算法。

CAN 的目标是学习一个最优的邻居矩阵 S，使得：

数据点与其邻居尽可能相似
邻居分配尽可能均衡

其目标函数为：

\min_S \sum_{i,j=1}^n (\|x_i-x_j\|_2^2 s_{ij} + \gamma s_{ij}^2)

其中 $s_{ij}$ 表示点 i 与点 j 的邻居关系强度，γ 是正则化参数。

PCAN 在 CAN 基础上引入投影矩阵 P，处理高维数据：

\min_{S,P} \sum_{i,j=1}^n (\|P^Tx_i-P^Tx_j\|_2^2 s_{ij} + \gamma s_{ij}^2)

通过交替优化 S 和 P，同时实现特征选择和聚类。

function X_normalized = preprocess_data(X)
    % 数据标准化：每维 0 均值 1 方差
    X_normalized = zscore(X);
    % 可选：PCA 降维
    % [coeff,score] = pca(X_normalized);
    % X_normalized = score(:,1:d);
end

function S = compute_similarity(X, k)
    [n,~] = size(X);
    S = zeros(n,n);
    D = pdist2(X,X); % 欧氏距离矩阵

    for i = 1:n
        [~, idx] = sort(D(i,:),'ascend');
        neighbors = idx(2:k+1); % 除自身外的 k 近邻
        S(i,neighbors) = 1; % 二值化邻居关系
    end
end

function [S, obj] = CAN(X, gamma, max_iter)
    [n,~] = size(X);
    D = pdist2(X,X).^2; % 平方距离矩阵
    S = ones(n,n)/n; % 初始化 S
    obj = zeros(max_iter,1);

    for iter = 1:max_iter
        % 更新 S 的每一行
        for i = 1:n
            d_i = D(i,:);
            % 闭式解（推导见论文）s_i = max(-d_i/(2*gamma) + 1/(n*gamma), 0);
            S(i,:) = s_i/sum(s_i); % 归一化
        end

        % 计算目标函数值
        obj(iter) = sum(sum(D.*S)) + gamma*sum(sum(S.^2));

        % 收敛判断
        if iter>1 && abs(obj(iter)-obj(iter-1))<1e-6
            break;
        end
    end
end