0

背景

我有一大组向量（轴角表示中的方向数据......轴是向量）。我想应用聚类算法。我尝试了 kmeans，但计算时间太长（从未完成）。因此，我尝试实现更快的 KFCG 算法（Kirke 2010）：

最初，我们有一个包含整个训练向量和质心的码向量 C1 的集群。在算法的第一次迭代中，通过将训练向量 Xi 的第一个元素与代码向量 C1 的第一个元素进行比较来形成集群。如果 xi1< c11 则向量 Xi 被分组到集群 1 中，否则向量 Xi 被分组到集群 2 中，如图 2(a) 所示，其中代码向量维度空间为 2。在第二次迭代中，通过比较第二个元素将集群 1 分成两个属于簇 1 的向量 Xi 的 Xi2 与码向量的第二个元素的向量。通过比较属于簇 2 的向量 Xi 的第二个元素 Xi2 与码向量的第二个元素的元素，将簇 2 分成两个，如图 2(b) 所示。

我不确定什么比例适合码本，但这对代码优化无关紧要。另请注意，我的是 3-D，因此对第 3 维执行相同的过程。

我的代码尝试

我已经尝试在 Matlab 2013（学生版）中实现上述算法。这是我尝试过的一些不同的结构 - 但需要的时间太长（从未见过它完成）：

%training vectors:
Atgood = Nx4 vector (see test data below if want to test);
vecA = Atgood(:,1:3);
roA = size(vecA,1);

%Codebook size, Nsel, is ratio of data
remainFrac2=0.5;
Nseltemp = remainFrac2*roA; %codebook size
%Ensure selected size after nearest power of 2 is NOT greater than roA
if 2^round(log2(Nseltemp)) < roA
    NselIter = round(log2(Nseltemp));
else
    NselIter = ceil(log2(Nseltemp)-1);
end
Nsel = 2^NselIter; %power of 2 - for LGB and other algorithms

主要优化块：

%KFCG:
%%cluster = cell(1,Nsel); %Unsure #rows - Don't know how to initialize if need mean...
codevec(1,1:3) = mean(vecA,1);
count1=1;
count2=1;
ind=1;
for kk = 1:NselIter
    hh2 = 1:2:size(codevec,1)*2;
    for hh1 = 1:length(hh2)
        hh=hh2(hh1);
%        for ii = 1:roA
%            if vecA(ii,ind) < codevec(hh1,ind)
%                cluster{1,hh}(count1,1:4) = Atgood(ii,:); %want all 4 elements
%                count1=count1+1;
%            else
%                cluster{1,hh+1}(count2,1:4) = Atgood(ii,:); %want all 4
%                count2=count2+1;
%            end
%        end
        %EDIT: My ATTEMPT at optimizing above for loop:
        repcv=repmat(codevec(hh1,ind),[size(vecA,1),1]); 
        splitind = vecA(:,ind)>=repcv; 
        splitind2 = vecA(:,ind)<repcv;
        cluster{1,hh}=vecA(splitind,:); 
        cluster{1,hh+1}=vecA(splitind2,:);
    end
    clear codevec
    %Only mean the 1x3 vector portion of the cluster - for centroid
    codevec = cell2mat((cellfun(@(x) mean(x(:,1:3),1),cluster,'UniformOutput',false))');
    if ind < 3
        ind = ind+1;
    else
        ind=1;
    end 
end
if length(codevec) ~= Nsel
    warning('codevec ~= Nsel');
end

或者，我认为 3D 矩阵会更快，而不是单元格？我尝试过，但使用我的每次迭代附加下一行的方法速度较慢（temp=[]; for...temp=[temp;new];）

另外，我不确定什么是最好的循环，for 或 while：

%If initialize cell to full length
while length(find(~cellfun('isempty',cluster))) < Nsel

好吧，无论如何，第一种方法对我来说是最快的。

问题

是逻辑标准吗？不是说它与所描述的算法相匹配，而是从编码的角度来看，我采用的任何奇怪的方法（尤其是那些多个内部循环）都会减慢它的速度？我在哪里可以加快速度（您可以指向我的资源或以前的问题）？

我的数组大小 Atgood 是 1,000,000x4 NselIter=19;- 我只需要找到一种方法来减小这个大小还是可以优化代码？

这应该在 CodeReview 上问吗？如果是这样，我会移动它。

测试数据

以下是一些可用于测试的随机向量：

for ii=1:1000 %My size is ~ 1,000,000
    omega = 2*rand(3,1)-1;
    omega = (omega/norm(omega))';
    Atgood(ii,1:4) = [omega,57];
end
4

1 回答 1

1

您最大的问题是重新迭代所有 vecA FOR EACH CODEVECTOR，而不仅仅是属于相应集群的那些。您应该在其代码向量上拆分每个集群。事实上，您的集群结构不断增长，每次迭代都在处理越来越多的样本。

您的第二个问题是围绕比较的循环，以及附加样本以建立集群。这两个都可以通过向量化比较操作来解决。哦，我刚刚看到你的编辑，这是优化的。好多了。但是codevec(hh1,ind)只是一个标量，所以你甚至不需要 repmat。

试试这个版本：

% (preallocs added in edit)
cluster = cell(1,Nsel);
codevec = zeros(Nsel, 3);

codevec(1,:) = mean(Atgood(:,1:3),1);
cluster{1} = Atgood;

nClusters = 1;
ind = 1;
while nClusters < Nsel
    for c = 1:nClusters
        lower_cluster_logical = cluster{c}(:,ind) < codevec(c,ind);
        cluster{nClusters+c} = cluster{c}(~lower_cluster_logical,:);
        cluster{c} = cluster{c}(lower_cluster_logical,:);
        codevec(c,:) = mean(cluster{c}(:,1:3), 1);
        codevec(nClusters+c,:) = mean(cluster{nClusters+c}(:,1:3), 1);
    end
    ind = rem(ind,3) + 1;
    nClusters = nClusters*2;
end
于 2013-07-18T19:53:38.510 回答