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

 
 

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

Submitted by:  None
Submitted on:  Sat 07 May 2016 03:03:31 PM UTC  
 
Category: Octave Forge PackageSeverity: 3 - Normal
Priority: 5 - NormalItem Group: Performance
Status: DuplicateAssigned to: None
Originator Name: cuantiarOriginator Email: -unavailable-
Open/Closed: OpenRelease: 4.0.2
Operating System: GNU/Linux

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

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>
Project Member
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>
Project Member
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 File(s):
   
   
Comment:
   

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

 

Digest:
   bug dependencies, patch dependencies.

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by jwe (Updated the item)
  • -unavailable- added by lachlan
  • -unavailable- added by lachlan (Posted a comment)
  • -unavailable- added by None (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 10 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Sun 13 Aug 2017 12:55:15 PM UTCjweSummaryoptimized kmeans.m for speed and modified convergence criterion=>[octave forge] (statistics) optimized kmeans.m for speed and modified convergence criterion
    Tue 17 May 2016 03:05:34 AM UTClachlanCarbon-Copy-=>Added -unavailable-
    Sat 14 May 2016 01:13:00 AM UTClachlanStatusNone=>Duplicate
    Sat 07 May 2016 03:44:23 PM UTCjordighDependenciesRemoved dependancy to bugs #42122=>-
    Sat 07 May 2016 03:43:06 PM UTCjordighDependencies-=>Depends on bugs #43959
      Dependencies-=>Depends on bugs #42122
      Dependencies-=>Depends on patch #8959
    Sat 07 May 2016 03:35:42 PM UTCrik5Carbon-CopyRemoved 72865=>-
    Sat 07 May 2016 03:35:29 PM UTCrik5CategoryOctave Function=>Octave Forge Package
    Sat 07 May 2016 03:03:31 PM UTCNoneAttached File-=>Added kmeans_differences.diff, #37097

    Back to the top


    Powered by Savane 3.1-cleanup1