Comments and Ratings

this method produces empty clusters constantly, be careful dealing with these exceptions～

Yes, just call the litekmeans.m to get the clustering results. You cannot get a visualization in a simple way for the data whose dimensions are more than 3. The scatterd.m can only handle data of 2d or 3d.

This gave a simple implementation to the problem I had.
A couple of notes:
- Reduction of code is good, reduction of comments is not. "litekmeans" is without any header line or comments describing what this (very useful) function does, what kind of input it takes, what it produces etc. Things like the dimension to arrange the input points are necessary to use the function properly, but are not explained in a header. Whether or not the function handles 1D, 2D, 3D, etc data isn't written anywhere.
- Providing data as a data.mat file is useful for functions requiring custom made data, but it tends to obscure the format of the data. It would be simpler and easier to understand by providing equally simple sample code that makes the data.
- Providing brief sample code on the file exchange is fine, but it should be included as a header to the file, so that people can find it when they need it, rather than when they first download it.
Otherwise, thanks! Like I said, it solved my immediate problem.

By the way, reading you review reminds me some review comments of some of my papers. Some reviewers just like to focus on whether the formate is right, whether the citation is right even whether the spell is right but not the idea of the paper itself. That is realy a pity.

Improving. It now runs as claimed for the 1-d case, so the bug is removed. I also like that this is called sqdistance. The problem with calling it distance is that it was not a distance. Better is to make that clear, that this returns the square of the Euclidean distance. So this is also good.

There is now even an attempt at error checking, in that the author uses the assert function to flag problems. However, assert allows you to provide TWO arguments. See what happens when I call sqdistance with improperly sized arrays:

sqdistance(rand(3,4),rand(2))
??? Error using ==> sqdistance at 16
Assertion failed.

All it tells me is "Assertion failed". For gods sake, what assertion? Use the second argument! Allow the code to exit gracefully and descriptively. Tell the user that the arguments are incompatible in size for this operation. To just tell them "Assertion failed" is silly. Why bother to do so?

Obviously from the authors last comment, this is just a code for his own academic purposes. So apparently it needs not be any good, or do what he claims it does. I'll argue that he is wrong.

When you post something on a website like this, hundreds or even many thousands of MATLAB users may use your code, or try to do so. They may look at it, hoping to learn something from what you post. So I'm sorry, but it would be a disservice on my part to any MATLAB user or student for me NOT to tell them that I see a problem, and what is wrong, and if possible, how the problem should best have been resolved (in my opinion.) And if this author has improved his code or coding style because of what I show to be wrong, then I've helped him too.

Somewhat better now in ONE respect. However, just because you have never suffered from the extreme case I showed does not mean that you have never had the problem. You've just never noticed it, or even known to look.

There is still a problem. Perhaps my long comments before were not extensive enough. This is NOT actually a valid distance metric. NOT. NOT. Read the definition of a distance metric. Here are a few sites:

http://www.mathreference.com/top-ms,dm.html
http://en.wikipedia.org/wiki/Metric_space

See that one requirement for a valid distance metric is the triangle inequality. The triangle inequality states that

   D(x,y) <= D(x,z) + D(y,z)

Does distance satisfy that? TRY IT!

distance(1,5)
ans =
    16

distance(1,3) + distance(5,3)
ans =
     8

(distance(1,3) + distance(5,3)) > distance(1,5)
ans =
     0

So this function fails to satisfy one of the basic requirements for a distance metric. This does NOT compute a distance. Just because you call the function distance does not make it a distance. The failure to compute the sqrt makes this not a valid distance.

Next, this function fails to work properly in one dimension!

distance([1,2])
ans =
                    0.5 1.5
                    1.5 0.5

I would have expected to see the matrix [0 1;1 0] returned as the result. (Surely you will concede this fact.) Don't complain that it was my suggested change that caused it to fail, because the original code fails too here, and by a larger margin.

originaldistance([1,2])
ans =
     8 6
     6 2

Finally, the changes to the help made it more accurate, but still fail to describe the behavior of this code. The help now states that when when called with two arguments, it returns the square of the interpoint Euclidean distances between columns of the matrices. It does not state at all what happens when called with only one argument.

Looking slightly deeper at the code pointed out serious flaws still. My rating is verging closer to one star at this point.

The problem with this code is it is potentially inaccurate. It uses an identity that people are oh so impressed with, but squares the numbers unnecessarily. I'll talk about this problem eventually, but first, let me discuss another major flaw with this code.

It does not actually compute the Euclidean distance. It computes the square of that distance. As such, it has the wrong units. Don't forget that if your data has units miles, then all "distances" produced by this function will have units of miles squared.

Note that this code claims to produce the same numbers as does the pdist function. But it does not. pdist produces TRUE distances, not the square of the distance. There is a difference.

A = randn(3,5);
B = randn(3,4);

distance(A,B)
ans =
       2.6333 7.7299 4.5349 4.6107
       3.1854 4.636 9.1202 1.0953
        2.277 9.2126 3.9594 9.9298
       5.9439 1.416 6.8336 2.748
       3.1344 0.96642 7.4918 1.6271

The true interpoint distances, as one will normally see by any correct tool available to compute distance is closer to this:

sqrt(distance(A,B))
ans =
       1.6228 2.7803 2.1295 2.1472
       1.7848 2.1531 3.02 1.0466
        1.509 3.0352 1.9898 3.1512
        2.438 1.19 2.6141 1.6577
       1.7704 0.98306 2.7371 1.2756

I imagine the author will claim that by not computing the square root, it saves time. I suppose so, but to then claim that the result is a distance as most expect to see would be misleading. And surely to claim that it produces the same as other codes is very misleading.

A nice property for a distance measure to have is linearity. We would like to see that

distance(k*A,k*B) = k*distance(A,B)

It is something that pdist will give you. But this is not a property one will gain from distance.

On to the other problem, the one that I see as most damaging. Recall the results of the above experiment for distance(A,B). Now, try adding any fixed offset to both A and B. I'll add a large one to the matrices to show that complete trash is generated.

distance(A+1e8,B+1e8)
ans =
     8 8 8 8
     4 -4 4 4
     4 4 4 12
     8 0 8 0
     0 0 8 0

See that NO significant digits remain in the result.

A higher quality tool (like pdist for example) will survive even this extreme test quite nicely. As it turns out, this is not an extreme test for pdist. (Since pdist does only interpoint distances for a single matrix, these numbers will not be comparable. See only that adding 1e8 did not change any digits printed out.)

pdist(A'+1e8)
ans =
  Columns 1 through 8
       1.9891 1.8594 3.139 2.8911 2.7152 2.6316 1.5634 3.9224
  Columns 9 through 10
       3.1472 1.7458

pdist(A')
ans =
  Columns 1 through 8
       1.9891 1.8594 3.139 2.8911 2.7152 2.6316 1.5634 3.9224
  Columns 9 through 10
       3.1472 1.7458

I will point out that all of the above mentioned flaws could have been repaired with a few simple changes to the code. Had the code been written as follows, it would take only about 20% longer to execute in my quick test, but it would have worked properly and robustly.

if nargin == 1
    B = A;
    mu = mean(A,2);
else
    mu = (mean(A,2) + mean(B,2))/2;
end
A = bsxfun(@minus,A,mu);
B = bsxfun(@minus,B,mu);
D = full(-2*A'*B);
D = bsxfun(@plus,D,full(sum(B.^2)));
D = sqrt(bsxfun(@plus,D,full(sum(A.^2)')));

Finally, the help for this code is itself wrong. Here is what it says when you do "help distance".

Compute distances between all sample pairs
  X: d x n data matrix
  D: n x n pairwise distance matrix
  Written by Mo Chen (mochen@ie.cuhk.edu.hk). March 2009.

See that it tells you that X is a d by n matrix of data. Does it tell you that the function actually accepts TWO arguments? That if there are two arguments, then it computes distances between all pairs of columns of the two matrices?

No error checks to verify the data actually conforms for distance computation. I'll be generous and give this a 2 star rating.