matlab - 在 MATLAB 中优化手动编码的 k 均值？

Question

所以我正在 MATLAB 中编写 k-means 脚本，因为 native 函数似乎效率不高，而且似乎可以完全运行。它似乎适用于我正在使用的小型训练集(这是一个通过文本文件输入的 150x2 矩阵)。但是，对于我的目标数据集(3924x19 矩阵)来说，运行时间呈指数增长。

我不是最擅长矢量化，所以任何建议将不胜感激。到目前为止，这是我的 k-means 脚本(我知道我将不得不调整我的收敛条件，因为它正在寻找精确匹配，并且对于这么大的数据集，我可能需要更多迭代，但我希望它在我提高这个数字之前，首先能够在合理的时间内完成):

clear all;

%take input file (manually specified by user
disp('Please type input filename (in working directory): ')
target_file = input('filename: ', 's');

%parse and load into matrix
data = load(target_file);

%prompt name of output file for later) UNCOMMENT BELOW TWO LINES LATER
% disp('Please type output filename (to be saved in working directory): ')
% output_name = input('filename:', 's')

%prompt number of clusters
disp('Please type desired number of clusters: ')
c = input ('number of clusters: ');

%specify type of kmeans algorithm ('regular' for regular, 'fuzzy' for fuzzy)
%UNCOMMENT BELOW TWO LINES LATER
% disp('Please specify type (regular or fuzzy):')
% runtype = input('type: ', 's')

%initialize cluster centroid locations within bounds given by data set

%initialize rangemax and rangemin row vectors
%with length same as number of dimensions
rangemax = zeros(1,size(data,2)); 
rangemin = zeros(1,size(data,2));

%map max and min values for bounds
for dim = 1:size(data,2)
    rangemax(dim) = max(data(:,dim));
    rangemin(dim) = min(data(:,dim));
end

% rangemax
% rangemin

%randomly initialize mu_k (center) locations in (k x n) matrix where k is
%cluster number and n is number of dimensions/coordinates

mu_k = zeros(c,size(data,2));

for k = 1:size(data,2)
    mu_k(k,:) = rangemin + (rangemax - rangemin).*rand(1,1);
end

mu_k

%iterate k-means

%initialize holding variable for distance comparison
comparisonmatrix = [];

%initialize assignment vector
assignment = zeros(size(data,1),1);

%initialize distance holding vector
dist = zeros(1,size(data,2));

%specify convergence threshold
%threshold = 0.001;

for iteration = 1:25

    %save current assignment values to check convergence condition
    hold_assignment = assignment;

    for point = 1:size(data,1)

        %calculate distances from point to centers
        for k = 1:c
            %holding variables
            comparisonmatrix = [data(point,:);mu_k(k,:)];

            dist(k) = pdist(comparisonmatrix);
        end

        %record location of mininum distance (location value will be between 1
        %and k)
        [minval, location] = min(dist);

        %assign cluster number (analogous to location value)
        assignment(point) = location;

    end

    %check convergence criteria

    if isequal(assignment,hold_assignment)
        break
    end

    %revise mu_k locations

    %count number of each label
    assignment_count = zeros(1,c);

    for i = 1:size(data,1)
        assignment_count(assignment(i)) = assignment_count(assignment(i)) + 1;
    end

    %compute centroids
    point_total = zeros(size(mu_k));

    for row = 1:size(data,1)
        point_total(assignment(row),:) = point_total(assignment(row)) + data(row,:);
    end

    %move mu_k values to centroids
    for center = 1:c
        mu_k(center,:) = point_total(center,:)/assignment_count(center);
    end
end

里面有很多循环，所以我觉得还有很多需要优化的地方。然而，我认为我已经盯着这段代码太久了，所以一些新的眼光可能会有所帮助。如果我需要澄清代码块中的任何内容，请告诉我。

当在大型数据集上执行上述代码块(在上下文中)时，根据 MA​​TLAB 的分析器，需要 3732.152 秒才能完成完整的 25 次迭代(根据我的计算，我假设它尚未“收敛”)对于 150 个簇，但其中大约 130 个返回 NaN(mu_k 中的 130 行)。

Answer 1

分析会有所帮助，但需要重新编写代码的地方是避免数据点数量的循环(for point = 1:size(data,1))。将其矢量化。

在您的 for iteration 循环中，这里是一个快速的部分示例，

[nPoints,nDims] = size(data);

% Calculate all high-dimensional distances at once
kdiffs = bsxfun(@minus,data,permute(mu_k,[3 2 1])); % NxDx1 - 1xDxK => NxDxK
distances = sum(kdiffs.^2,2); % no need to do sqrt
distances = squeeze(distances); % Nx1xK => NxK

% Find closest cluster center for each point
[~,ik] = min(distances,[],2); % Nx1

% Calculate the new cluster centers (mean the data)
mu_k_new = zeros(c,nDims);
for i=1:c,
    indk = ik==i;
    clustersizes(i) = nnz(indk);
    mu_k_new(i,:) = mean(data(indk,:))';
end

这不是唯一(或最好)的方法，但它应该是一个不错的例子。

其他一些评论:

1. 不要使用input，而是将此脚本制作成一个函数来有效处理输入参数。
2. 如果您想要一种简单的方法来指定文件，请参阅 uigetfile。
3. 使用许多 MATLAB 函数，例如 max、min、sum、mean 等，您可以可以指定函数应在其上运行的维度。这样您就可以在矩阵上运行它并同时计算多个条件/维度的值。
4. 获得不错的性能后，请考虑延长迭代时间，特别是直到中心不再发生变化或改变簇的样本数量变少。
5. 每个点距离最小的簇 ik 将与平方欧氏距离相同。