Re: K-Means Clustering

[Mehmet Hakan Satman]

Hi John,

1. In the case of no variable definition, cmd_quick_cluster returns a CMD_FAILURE now.
2. By the now, default number of clusters and the mxiter are both set to 2.
3. Your test strategy is very well, but multi-dimensionality is also a problem. I tried this with your code:

______________________________________________________________
input program.
        loop #i = 1 to 50000.
                compute x = rv.uniform (0, 1).
                compute y = rv.uniform (0, 1).
                compute z = rv.uniform (0, 1).
                end case.
        end loop.
        loop #i = 1 to 50000.
                compute x = rv.uniform (0, 1)+1.
                compute y = rv.uniform (0, 1)+1.
                compute z = rv.uniform (0, 1)+1.
                end case.
        end loop.
          loop #i = 1 to 50000.
                compute x = rv.uniform (0, 1)+2.
                compute y = rv.uniform (0, 1)+2.
                compute z = rv.uniform (0, 1)+2.
                end case.
        end loop.      
        loop #i = 1 to 50000.
                compute x = rv.uniform (0, 1)+3.
                compute y = rv.uniform (0, 1)+3.
                compute z = rv.uniform (0, 1)+3.
                end case.
        end loop.
        end file.
end input program.


QUICK CLUSTER ALL
        /CRITERIA = CLUSTER(4) MXITER (100).
______________________________________________________________

The expected cluster centers are
(0.5, 0.5, 0.5)
(1.5, 1.5, 1.5)
(2.5, 2.5, 2.5)
(3.5, 3.5, 3.5)

and the actual output is

Result:
Number of cases: 200000
Number of variables: 3
Number of groups: 4
Number of trials: 1
Number of iterations at last trial: 5
Centers:
Center of Group 1: 1.498 1.501 1.502
Center of Group 2: 3.500 3.500 3.501
Center of Group 3: 2.498 2.499 2.499
Center of Group 4: 0.501 0.502 0.502

which is nearly same as the expected one. I think its ok. It is also be tried that generating some big data with R and using kmeans command to calculate centers and comparing one-or-two samples with pspp. But as in your simulation study, cluster centers map to correct quantiles of uniform distribution.


4. I re-formatted the code using indent with --gnu-style parameter.

5. This is the part what i didn't understand. Which part of code must be labeled as "static"? If the answer is "All methods must be defined as static", what i must do for "struct Kmeans* kmeans_create(...." ?

6. I changed malloc 's to xmalloc 's. I think this is why we didn't control the null pointer in memory allocations.

7. I used the gsl_rng_* things instead of standard library.

8) this link (http://www.norusis.com/pdf/SPC_v13.pdf) and googling "kmeans spss" may help for the output of quick cluster. I haven't got a copy of SPSS too. 

Ben has sent me the form about fsf. I answered the questions and re-sent the given address.

I hope corrections are suitable for the project.

Best.

 

Mehmet Hakan Satman
http://www.mhsatman.com

---

From: John Darrington <address@hidden>
To: Mehmet Hakan Satman <address@hidden>
Cc: John Darrington <address@hidden>; address@hidden
Sent: Tue, March 15, 2011 11:23:34 AM
Subject: Re: K-Means Clustering

On Mon, Mar 14, 2011 at 12:22:36PM -0700, Mehmet Hakan Satman wrote:
    Hi John,
   
    1) I renamed the file as "quick-cluster.c"
   
    2. I added an entry to? "src/language/stats/automake.mk" for quick-cluster
   
    3. I removed the entry "UNIMPL_CMD ("QUICK CLUSTER", "Fast clustering")" from command.def file.

Thanks.  I tried some experiments with it.  It looks promising.  But there are some improvements
which can be made.
   
    4. Now cmd_quick_cluster can parse a command line like:
   
    QUICK CLUSTER x y z
    ? ? ? /CRITERIA = CLUSTER(5) MXITER (100).
   
I inadvertently ran it with the wrong syntax (I typed just "QUICK CLUSTER." without any variables),
and it caused PSPP to crash.  You should check the return value of parse_variables_const
and return an error if it fails.  See the code for the other procedures to see how to do this.

It also crashed if I omitted the /CRITERIA subcommand because your algorithm expects
the number of groups is greater than 0.  The spss documentation says that
the CLUSTER and MXITER parameters both default to 2.  So you should initialise them accordingly.

    As
      I mentioned, i test my results with random data with uniform
    distributed random values. It can not be considered as a comprehensive
    work and should be tested with simulations.

It's not my field of expertise, but I ran it with the following syntax:

input program.
        loop #i = 1 to 100000.
                compute x = rv.uniform (0, 1).
                end case.
        end loop.
        end file.
end input program.


QUICK CLUSTER ALL
        /CRITERIA = CLUSTER(3) MXITER (100).

and got :

Centers:
Center of Group 1: 0.499
Center of Group 2: 0.833
Center of Group 3: 0.165

   
which is close to what I would expect (the centres are 1/6, 3/6 and 5/6).  Can you
suggest some more comprehensive tests?


I have some general suggestions about the quick-cluster.c file:

1. The formatting style doesn't really fit the GNU way of doing things.  I recommend
  that you run the command "indent --gnu-style quick-cluster.c" to make it more consistent
  with the rest of the code.  You might want to read the information at
  http://www.gnu.org/prep/standards/standards.html which explains how GNU software is
  normally written and why we do it that way.

2. When compiling, I get a number of warnings.  Most of these are due to missing "static"
  qualifiers from the functions.

3. In PSPP we don't use the stdlib "malloc".  Instead we use "xmalloc" from gnulib.

4. Similarly, we don't use the srand and rand functions.  Use the gsl_rng_* functions.
  These are supposed to be better random number generators.
  See the file src/language/xforms/sample.c and/or the gsl manual for an example.


I'm looking forward to seeing the QUICK CLUSTER command integrated into PSPP.  I tried
to find some examples of how spss presents its output for this command but I couldn't
find any.  Do you have any such examples or do you have access to a copy of pspp so that
we can see how users might expect to see the results?

Regards,


John




--
PGP Public key ID: 1024D/2DE827B3
fingerprint = 8797 A26D 0854 2EAB 0285  A290 8A67 719C 2DE8 27B3
See http://pgp.mit.edu or any PGP keyserver for public key.

quick-cluster.c
Description: Text document