wbreeze / acd_stats Goto Github PK

The following data given to the clustering call, prechi.cluster_neighbors causes the cluster process to run long with no sign of termination:

$range
[1] 42 47 52 57 62 67 72 77 82
$counts
[1] 1 0 0 0 0 0 0 0 0
$grades
 [1] 79 70 84 74 79 70 70 42 84 76 76 84 76 76

First, the counts aren't correct given the grades. (The ranges are correct.) Second, the cluster algorithm ought to spit that out as unsolvable more or less immediately.

The contest that raised this is #652, which is odd in that it has grades on tenths, not rounded to 0.5. This contest and contest #641 were manually added to the processed list in order to omit them.

The prechi algorithm currently fixes the minimum number of partitions at three. The ChiSq test we are using has n-3 degrees of freedom. Fixing three means doing tests with 3-3=0 degrees of freedom.

Parameterize the fixed number three, so that we can pass four or five and not be doing meaningless ChiSq tests. This will mean fewer distributions that can be tested with ChiSq; however, the tests aren't really useful with so few partitions.

Prechi does not terminate in a reasonable time given:

2, 0, 0, 0, 3, 0, 0, 0, 2, 3, 5, 1, 4, 2, 8

(on intervals of five from twenty up through ninety)

It arrives at 5, 5, 6, 6, 8 quite quickly, but then goes into forever trying the large number of unproductive combinations. "Forever" is hours or days. Haven't seen it terminate. Another solution is 5, 5, 5, 7, 8; however I think that's worse than the one first found.

There are two things that can be done:

1. strengthen the lower bound - half the number of items with value less than the target count (5, rounded up) can be added to the current solution length. That will cut-back all of the bad starts that occur after having made a good start with the heuristic.
2. strengthen the heuristic - after sorting by increasing value, add a secondary sort for the minimum sum after join. I'm not sure how much that will help, but it will ensure that the strings of zeros get merged together first.

If those don't help, I'll have to think of allowing it to be heuristic but not optimal.

The data contains many distributions with large runs of zero counts. This makes for an explosion of fruitless combinations. The prechi algorithm is timing-out frequently.

A zero run can be merged with the left or right neighbor (there are always both), whichever is smaller. Add a preprocessing step which does this.