This is an evolutionary algorithm and visualization of a clustering
algorithm that could be turned from O(n^4) to O(nlogn) with a few
judicious uses of constants. Later developments added other
interactive devices, including progress meters and mouse-and-click
behavior.
Contact
Ronald Loui
Email
r.p.loui@gmail.com
Description
The code is an excellent example of the power of Awk as a prototyping
tool: after getting the code running, with the least development time,
a quirk was observed in the code that allowed a reduction from O(n^4)
to O(nlogn).
Two of the n's are lost
(n^2) by noticing that when there is a swap, the delta in the scoring
function falls off by the squared distance from the point of a swap.
So if you just set a constant, such as 10 or 20, or 100, based on the
expected size of your clusters, then you can stop calculating the
scoring function when you get past that constant.
The other n comes
from either fixing the size of the matrix, and occasionally flushing
new candidates in and out, or else by sampling over a subset of the n
when you calculate the score.
The nlogn remains
because there is a sort every now and then.
Awk
Gawk
Platform
Intended for fast servers, 1+ ghz.
Uses
Html.
Lines
158.
Development Effort
One weekend.
Maintenance Effort
None.
Current
2=Evaluation.
Use
2=in-House use.
Users
5
DateDeployed
2004.
Dated
Feb 2009.
References
Streaming Hierarchical Clustering for Concept Mining
Looks, M.; Levine, A.; Covington, G.A.; Loui, R.P.; Lockwood, J.W.; Cho, Y.H.
Aerospace Conference, 2007 IEEE
Volume , Issue , 3-10 March 2007 Page(s):1 - 12
Digital Object Identifier 10.1109/AERO.2007.352792
