home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2501 < prev    next >
Encoding:
Text File  |  1992-08-27  |  1.8 KB  |  37 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!gatech!rpi!uwm.edu!csd4.csd.uwm.edu!markh
  3. From: markh@csd4.csd.uwm.edu (Mark)
  4. Subject: Re: clustering algorithm wanted
  5. Message-ID: <1992Aug27.164656.10905@uwm.edu>
  6. Sender: news@uwm.edu (USENET News System)
  7. Organization: Computing Services Division, University of Wisconsin - Milwaukee
  8. References: <1992Aug27.103332.16604@nuscc.nus.sg>
  9. Date: Thu, 27 Aug 1992 16:46:56 GMT
  10. Lines: 25
  11.  
  12. In article <1992Aug27.103332.16604@nuscc.nus.sg> tmp16@nuscc.nus.sg (temporary account for courses) writes:
  13. >I am working on some numerical data and I wish to obtain an algorithm
  14. >for clustering these data into discrete groups ( i.e a pattern ). I've
  15. >considered using multivariate analysis but can't get a workable method.
  16. >So if anyone knows of such an algorithm or has a reference, I would
  17. >appreciate it if one could post it to me.
  18.  
  19. Well, here's an idea.  Suppose you want to cluster the objects into a pre-
  20. determined number of clusters (N).  For a given clustering, define the
  21. cluster error to be the sum of the square deviations of each item from it's
  22. cluster's average.  The task is to minimize this -- which defines the optimum
  23. clustering.
  24.  
  25. So start with all objects in one cluster, and with N - 1 empty clusters.  At
  26. each step choose a random object and random cluster.  Move the object to this
  27. cluster if and only if the error value mentioned above decreases as a result.
  28.  
  29. Stop when the error value become stationary long enough.  The result should be
  30. a good approximation of the optimal clustering.
  31.  
  32. Do obvious things to minimize the computation, such as maintaining cluster
  33. sums and sum-of-squares for each cluster.  Then when an object is moved,
  34. you only need to update 4 items and you only need to perform a test to see if
  35. the total square deviation of those two clusters decreases, instead of
  36. computing the square deviation for all the clusters.
  37.