bugGNU Octave - Bugs: bug #47871, [octave forge] (statistics)...

 
 

bug #47871: [octave forge] (statistics) optimized kmeans.m for speed and modified convergence criterion

Submitter:  None
Submitted:  Sat 07 May 2016 03:03:31 PM UTC
   
 
Category:  Octave Package Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Fixed Assigned to:  None
Originator Name:  cuantiar Originator Email:  -email is unavailable-
Open/Closed:  * Closed Release:  * dev
Operating System:  * GNU/Linux Fixed Release:  None
Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Thu 25 Nov 2021 12:05:31 AM UTC, comment #4: 

These proposed performance improvements are already taken care of by Andrew Lachlan's revision of kmeans:
http://hg.code.sf.net/p/octave/statistics/rev/dcf16d7cf4d4

Nir Krakauer <nir_krakauer>
Mon 04 Mar 2019 12:51:32 AM UTC, comment #3: 

Is someone working on the statistics package willing to look at the attached patch and merge it into the package repository?

Mike Miller <mtmiller>
Group Member
Tue 17 May 2016 03:05:34 AM UTC, comment #2: 

By email, the original poster wrote:

I cloned the latest version of statistics package and in that: a) the loop was for the data points (instead for the classes), b) the objCost function was calculated twice and c) certainly I did notice negative err values of huge absolute value and for that reason I apply the abs(). Thank you.

Please reply via the bug tracker rather than email, so that others can see the posts.

You are right that the latest version in the statistics package is quite poor.  I spent a long time fixing it for bug #43959, but my initial attempts were so buggy that people's patience wore thin.  I think that the latest version is ready to commit, however.

If you want prepare a patch relative to the patch at bug #43959, you can see how much improvement your changes give.

Lachlan Andrew <lachlan>
Sat 14 May 2016 01:11:39 AM UTC, comment #1: 

Thanks, cuantiar.

Note that kmeans produces a decreasing sequence of costs (ignoring numerical errors).  Have you observed cases where  err  was a large negative value?  I think that the  abs()  is just an unnecessary function call.

The patch at bug #43959 already avoids the double call to obj_cost.

On a quick reading, I think it also loops over centroids instead of over data sets.


This is the second patch within a few weeks that tries to improve on kmeans.m, with changes that seem to be already in my patch from about a year ago.  Could the package maintainer please apply my patch (or point out remaining flaws), to save all of this duplicated effort?  Thanks!

Lachlan Andrew <lachlan>
Sat 07 May 2016 03:03:31 PM UTC, original submission:  

modifications:
1. optimized the function objCost in kmeans.m for CPU speed (depending on the data-set size, 2 orders of magnitude faster)
2. calling the function objCost once instead of twice
3. modified the convergence criterion "err" to "abs(err)"

Attached the changes as they reported by hg.

Anonymous

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #37097:  kmeans_differences.diff added by None (4KiB - text/x-patch)

 

Carbon-Copy List
  • -email is unavailable- added by nrjank (Updated the item)
  • -email is unavailable- added by nir_krakauer (Posted a comment)
  • -email is unavailable- added by jwe (Updated the item)
  • -email is unavailable- added by lachlan
  • -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 group members can vote.

     

    Follow 14 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2021-12-16 nrjank StatusPatch Submitted Fixed
        Open/ClosedOpen Closed
    2019-03-04 mtmiller StatusDuplicate Patch Submitted
        Release4.0.2 dev
    2017-08-13 jwe Summaryoptimized kmeans.m for speed and modified convergence criterion [octave forge] (statistics) optimized kmeans.m for speed and modified convergence criterion
    2016-05-17 lachlan Carbon-Copy- Added -email is unavailable-
    2016-05-14 lachlan StatusNone Duplicate
    2016-05-07 jordigh DependenciesRemoved dependency to bugs #42122 -
    2016-05-07 jordigh Dependencies- Depends on bugs #43959
        Dependencies- Depends on bugs #42122
        Dependencies- Depends on patch #8959
    2016-05-07 rik5 Carbon-CopyRemoved 72865 -
    2016-05-07 rik5 CategoryOctave Function Octave Package
    2016-05-07 None Attached File- Added kmeans_differences.diff, #37097

    Back to the top

    Powered by Savane 3.13-02a9.
    Corresponding source code