CAN与PCAN自适应邻居聚类算法在MATLAB中的高效实现与优化

1次阅读

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

在处理高维数据聚类问题时，传统方法如 K -means 存在明显的局限性。K-means 需要预先指定聚类数目，且对噪声和异常值敏感，容易陷入局部最优。此外，高维数据中的 ” 维度灾难 ” 问题使得距离度量变得不可靠，进一步降低了聚类质量。

CAN（Clustering by Affinity Propagation）和 PCAN（Probabilistic CAN）算法通过自适应邻居选择和概率优化，能够有效解决这些问题。这两种算法不需要预先指定聚类数目，且对噪声数据具有更强的鲁棒性。

CAN 基于信息传递机制，通过迭代更新两个关键矩阵：

责任度矩阵 (R)：反映样本 k 适合作为样本 i 的聚类中心的程度
可用度矩阵 (A)：反映样本 i 选择样本 k 作为其聚类中心的适合程度

更新公式如下：

$$R(i,k) \leftarrow S(i,k) – \max_{k’ \neq k} {A(i,k’) + S(i,k’)}$$

$$A(i,k) \leftarrow \min \left(0, R(k,k) + \sum_{i’ \notin {i,k}} \max(0, R(i’,k)) \right)$$

PCAN 在 CAN 基础上引入了概率化改进，主要变化在于：

将确定性的消息传递变为概率性的
增加了对不确定性的建模

关键改进公式：

$$P(k \rightarrow i) = \frac{\exp(R(i,k))}{\sum_{k’} \exp(R(i,k’))}$$

$$P(i \Rightarrow k) = \frac{\exp(A(i,k))}{\sum_{i’} \exp(A(i’,k))}$$

function [idx, centers] = pcan_cluster(X, pref, damping, max_iter, tol)
    % 输入参数:
    % X: 数据矩阵 (n_samples x n_features)
    % pref: 偏好参数
    % damping: 阻尼系数 (通常 0.5~0.9)
    % max_iter: 最大迭代次数
    % tol: 收敛阈值

    % 1. 计算相似度矩阵
    S = -pdist2(X, X, 'squaredeuclidean');  % 使用欧式距离平方
    S(1:size(S,1)+1:end) = pref;  % 对角线设为偏好值

    % 2. 初始化消息矩阵
    R = zeros(size(S));  % 责任度矩阵
    A = zeros(size(S));  % 可用度矩阵

    % 3. 迭代更新
    for iter = 1:max_iter
        % 更新责任度 (对数域计算防止数值下溢)
        old_R = R;
        AS = A + S;
        [Y, I] = max(AS, [], 2);
        for i = 1:size(AS,1)
            AS(i,I(i)) = -inf;
        end
        Y2 = max(AS, [], 2);
        R = S - repmat(Y, 1, size(S,2));
        for i = 1:size(R,1)
            R(i,I(i)) = S(i,I(i)) - Y2(i);
        end
        R = (1-damping)*R + damping*old_R;  % 阻尼更新

        % 更新可用度
        old_A = A;
        Rp = max(R, 0);
        Rp(1:size(Rp,1)+1:end) = R(1:size(R,1)+1:end);
        A = repmat(sum(Rp, 1), size(Rp,1), 1) - Rp;
        dA = diag(A);
        A = min(A, 0);
        A(1:size(A,1)+1:end) = dA;
        A = (1-damping)*A + damping*old_A;  % 阻尼更新

        % 检查收敛
        if norm(A-old_A, 'fro') < tol && norm(R-old_R, 'fro') < tol
            break;
        end
    end

    % 4. 确定聚类中心
    E = A + R;
    [~, centers] = max(E, [], 2);
    [~, ~, idx] = unique(centers);
end

对于大规模数据集，相似度矩阵计算是主要瓶颈。可以使用 MATLAB 并行计算工具箱加速：

% 启用并行池
if isempty(gcp('nocreate'))
    parpool;
end

% 并行计算相似度矩阵
parfor i = 1:n
    for j = 1:n
        S(i,j) = -sum((X(i,:)-X(j,:)).^2);
    end
end

我们测试了不同距离度量对聚类质量的影响 (NMI 指标)：