forum.alglib.net
http://forum.alglib.net/

k-Means infinite loop in extreme corner cases
http://forum.alglib.net/viewtopic.php?f=2&t=611		 Page 1 of 1
Author:  andreas [ Wed Sep 05, 2012 1:13 pm ]
Post subject:  k-Means infinite loop in extreme corner cases
I have a situation where kmeansgenerate seems to be stuck in an infinite loop (C# version of alglib 3.6.0). The parameters are as follows (copied from the debugger):

xy: {double[57, 1]}
[0, 0]: 12.244689632138986
[1, 0]: 12.244689632138982
[2, 0]: 12.244689632138986
[3, 0]: 12.244689632138982
[4, 0]: 12.244689632138986
[5, 0]: 12.244689632138986
[6, 0]: 12.244689632138986
[7, 0]: 12.244689632138986
[8, 0]: 12.244689632138986
[9, 0]: 12.244689632138986
[10, 0]: 12.244689632138989
[11, 0]: 12.244689632138984
[12, 0]: 12.244689632138986
[13, 0]: 12.244689632138986
[14, 0]: 12.244689632138989
[15, 0]: 12.244689632138986
[16, 0]: 12.244689632138986
[17, 0]: 12.244689632138986
[18, 0]: 12.244689632138986
[19, 0]: 12.244689632138989
[20, 0]: 12.244689632138972
[21, 0]: 12.244689632138986
[22, 0]: 12.244689632138986
[23, 0]: 12.244689632138986
[24, 0]: 12.244689632138984
[25, 0]: 12.244689632138982
[26, 0]: 12.244689632138986
[27, 0]: 12.244689632138986
[28, 0]: 12.244689632138986
[29, 0]: 12.244689632138986
[30, 0]: 12.244689632138986
[31, 0]: 12.244689632138986
[32, 0]: 12.244689632138986
[33, 0]: 12.244689632138986
[34, 0]: 12.244689632138986
[35, 0]: 12.244689632138982
[36, 0]: 12.244689632138989
[37, 0]: 12.244689632138986
[38, 0]: 12.244689632138986
[39, 0]: 12.244689632138986
[40, 0]: 12.244689632138986
[41, 0]: 12.244689632138986
[42, 0]: 12.244689632138986
[43, 0]: 12.244689632138986
[44, 0]: 12.244689632138986
[45, 0]: 12.244689632138986
[46, 0]: 12.244689632138986
[47, 0]: 12.244689632138986
[48, 0]: 12.244689632138986
[49, 0]: 12.244689632138986
[50, 0]: 12.244689632138984
[51, 0]: 12.244689632138986
[52, 0]: 12.244689632138986
[53, 0]: 12.244689632138986
[54, 0]: 12.244689632138986
[55, 0]: 12.244689632138986
[56, 0]: 12.244689632138986

nPoints: 57
nVars: 1
k: 4
restarts: 1

Can you reproduce this situation?

I understand that this doesn't really constitute "good data", but unfortunately, I don't have a lot of control on the input values, they can be as meaningless as in this case. Currently I'm just filtering when there are less distinct values than clusters. I'm probably changing this to require some higher minimum range between the values and hope to avoid such situations.

I'm running the program in Vista 64bit and use VS2010 and .Net 4.
Author:  Sergey.Bochkanov [ Thu Sep 06, 2012 5:51 am ]
Post subject:  Re: k-Means infinite loop in extreme corner cases
Hello!

Thanks for the report, I've added this issue to bug tracker, see http://bugs.alglib.net/view.php?id=487 for the record. You are right - your situation is degenerate, but you are also right when you report it as bug - good algorithm should work with any data. Or, at least, fail with error report.

I've not tried to reproduce it yet, I think that I will move to this issue at Friday. In my opinion, fix won't need too much time. There should be some easy solution to prevent infinite loops like this.
Author:  andreas [ Fri Sep 07, 2012 9:23 am ]
Post subject:  Re: k-Means infinite loop in extreme corner cases
Thank you Sergey! Just to let you know this fix is not time-critical for me as I have moved on and implemented Ckmeans.1d.dp by Wang and Song. Anyway, as you say, it would be good if this was fixed in a future version.
Page 1 of 1 All times are UTC
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/