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

1次阅读

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

传统聚类算法如 K -means 和 DBSCAN 在处理高维稀疏数据时常常表现不佳。K-means 假设数据呈球形分布，而 DBSCAN 依赖全局密度参数，这在社交网络或基因表达数据等场景中往往难以满足。CAN（Common Neighbor）和 PCAN（Parametric Common Neighbor）算法通过动态调整邻居关系，能够更好地捕捉数据的局部结构。

CAN 基于公共邻居的概念定义节点间的相似度：

$$ sim(u,v) = |N(u) \cap N(v)| $$

其中 $N(u)$ 表示节点 $u$ 的邻居集合。通过设定阈值 $\tau$，当 $sim(u,v) \geq \tau$ 时，认为 $u$ 和 $v$ 属于同一簇。

PCAN 引入参数 $\alpha$ 改进相似度计算：

$$ sim_{pcan}(u,v) = \frac{|N(u) \cap N(v)|}{|N(u) \cup N(v)|^\alpha} $$

这个参数化形式可以更好地适应不同密度的数据分布。当 $\alpha=0$ 时，PCAN 退化为 CAN；当 $\alpha=1$ 时，相当于 Jaccard 相似度。

function S = compute_similarity(adj, alpha)
    % adj: 邻接矩阵
    % alpha: PCAN 参数

    degrees = sum(adj, 2);
    n = size(adj, 1);
    S = zeros(n);

    for i = 1:n
        for j = i+1:n
            common = sum(adj(i,:) & adj(j,:));
            union = degrees(i) + degrees(j) - common;
            S(i,j) = common / (union^alpha);
            S(j,i) = S(i,j);
        end
    end
end

function [labels] = adaptive_clustering(S, min_neighbors)
    % S: 相似度矩阵
    % min_neighbors: 最小公共邻居数

    n = size(S,1);
    labels = zeros(n,1);
    current_label = 0;

    for i = 1:n
        if labels(i) == 0
            current_label = current_label + 1;
            labels(i) = current_label;

            neighbors = find(S(i,:) >= min_neighbors);
            queue = neighbors;

            while ~isempty(queue)
                v = queue(1);
                queue(1) = [];

                if labels(v) == 0
                    labels(v) = current_label;
                    new_neighbors = find(S(v,:) >= min_neighbors);
                    queue = [queue, setdiff(new_neighbors, neighbors)];
                    neighbors = union(neighbors, new_neighbors);
                end
            end
        end
    end
end