2

ネイティブ関数はあまり効率的ではないようで、完全に機能しているように見えるので、MATLAB で k-means スクリプトを作成しています。私が使用している小さなトレーニング セット (テキスト ファイル経由で供給される 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

そこにはたくさんのループがあるので、多くの最適化を行う必要があると感じています。ただし、私はこのコードをあまりにも長い間見つめていたと思うので、新鮮な目が役立つかもしれません. コードブロックで何か明確にする必要がある場合はお知らせください。

上記のコード ブロックが大規模なデータセットで (コンテキスト内で) 実行されると、MATLAB のプロファイラーによると、25 回の反復を完了するのに 3732.152 秒かかります (私の基準では、まだ「収束」していないと仮定しています)。 150 個のクラスターの場合、そのうちの約 130 個が NaN を返します (mu_k で 130 行)。

4

1 に答える 1