patchGNU Octave - Patches: patch #8959, [octave forge] (statistics)...


patch #8959: [octave forge] (statistics) Replace kmeans with more efficient implementation

Submitted by:  None
Submitted on:  Tue 29 Mar 2016 02:03:18 AM UTC
Category:  Forge : other Priority:  5 - Normal
Status:  Need Info Privacy:  Public
Assigned to:  None Originator Email:  -email is unavailable-
Open/Closed:  Open
* Mandatory Fields

Add a New Comment (Rich Markup)

Comment Type & Canned Response:


Tue 23 Nov 2021 08:45:33 PM UTC, comment #5: 

seeing that bug #43959 was applied and closed in 2016, with most of the final work happening a month after Andrew' he'd look at how to merge them (no comment over there on if he borrowed any of this), it may be worth someone familiar with kmeans looking at the current version of the function and this patch, and determining if this patch can/would improve the current version.

Nicholas Jankowski <nrjank>
Project Member
Wed 20 Apr 2016 03:17:22 AM UTC, comment #4: 

That's certainly an improvement worth pursuing.

If I get the time, I'll try to see why yours is so much faster, and then have a think about how to merge them.

Lachlan Andrew <lachlan>
Tue 19 Apr 2016 05:23:51 PM UTC, comment #3: 

Also of note, I have some timing data if people want to see how much this is improved.

| k | Mine in Octave | Octave's   | Mine in Matlab | Matlab's  |
| 3 | 0.197 sec      | 12.268 sec | 0.313 sec      | 0.245 sec |
| 4 | 0.578 sec      | 17.961 sec | 0.629 sec      | 0.475 sec |
| 5 | 0.458 sec      | 25.572 sec | 0.614 sec      | 0.402 sec |
| 6 | 1.026 sec      | 50.141 sec | 1.160 sec      | 0.739 sec |
| 7 | 1.237 sec      | 41.985 sec | 1.418 sec      | 0.534 sec |
| 8 | 1.077 sec      | 21.745 sec | 1.289 sec      | 0.929 sec |

This timing experiment was done on a grid of 128x128 elements, each one having 16 channels.  I call it with

    [m,n,p] = size(params);
    [elements, clusters] = kmeans(reshape(params, [m*n, p]), k);
    elements = reshape(elements, [m,n]);

Michael Bentley <mikebentley15>
Tue 19 Apr 2016 05:14:56 PM UTC, comment #2: 

I did not make an attempt to improve the current one, but rather rewrote it entirely.  I basically had written this replacement for some homework for one of my classes, and thought that since Octave's implementation is so inefficient, I could contribute it back.

So since it is a rewrite, I think you would be better off implementing your patches to my version.  If you are able to do that, it would be great.  If it's up to me, then it will be some time before I have any free cycles.

Alternatively, if you want to take the approach I took in my implementation and do a more minimal patch to the current implementation, that could work too.  But I think this approach will take more time.

Michael Bentley <mikebentley15>
Tue 19 Apr 2016 11:26:48 AM UTC, comment #1: 

Michael, as Jordi mentioned, I submitted a patch (actually, a long series -- but the last one is usable) a while back in bug #43959.  It would be good if we could merge your changes with mine.

Do you think it would be easier to apply your changes to my patch or vice versa?

Lachlan Andrew <lachlan>
Tue 29 Mar 2016 02:03:18 AM UTC, original submission:  

The current implementation of kmeans() is incredibly inefficient.  I reimplemented it and it runs much faster and gives the same results (as much as can be expected with randomization involved).



(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:

Attached Files
file #36789:  kmeans.diff added by None (8KiB - text/x-patch)
file #36788:  kmeans.diff added by None (8KiB - text/x-patch - Replace kmeans)


Depends on the following items: None found

   bug dependencies.


Carbon-Copy List
  • -email is unavailable- added by nrjank (Posted a comment)
  • -email is unavailable- added by mikebentley15 (Posted a comment)
  • -email is unavailable- added by lachlan (Posted a comment)
  • -email is unavailable- added by None (Submitted the item)

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.





    Follow 6 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2021-11-23 nrjank StatusNone => Need Info
    2019-03-07 mtmiller Summarypkg-statistics: Replace kmeans with more efficient implementation => [octave forge] (statistics) Replace kmeans with more efficient implementation
    2016-07-07 lachlan CategoryNone => Forge : other
    2016-05-07 jordigh Dependencies- => bugs #47871 is dependent
    2016-03-29 None Attached File- => Added kmeans.diff, #36789
    2016-03-29 None Attached File- => Added kmeans.diff, #36788

    Back to the top

    Powered by Savane 3.9