clusterstopping.pl - Predict the optimal number of clusters in a data set
clusterstopping.pl [OPTIONS] INPUTFILE
Predicts the optimal number of clusters for the given data. This script tries to find the optimal number of clusters for the given INPUTFILE.
Matrix file containing either:
* context vectors (in dense or sparse format) * similarity values between contexts
Specify a prefix to be used for the output filenames.
If prefix is not specified then prefix is created by concatenating time stamp to the string "expr".
Specify the cluster stopping measure to be used.
(Further details about the measures given below under the Section "DETAILS ABOUT THE CLUSTER-STOPPING MEASURES")
The possible option values: pk1 - PK1 measure pk2 - PK2 measure pk3 - PK3 measure [Default] gap - Adapted Gap Statistic pk - All the three PK measures all - All the four measures - PK1, PK2, PK3 and Gap
Specify if the clustering should be performed in vector or similarity space.
The possible option values: vector [Default] similarity
NOTE: Delta value can only be a positive integer value.
Specify 0 to stop the iterating clustering process when two consecutive crfun values are exactly equal. This is the default setting when the crfun values are integer/whole numbers.
Specify non-zero positive integer to stop the iterating clustering process when the diffference between two consecutive crfun values is less than or equal to this value. However, note that the integer value specified is internally shifted to capture the difference in the least significant digit of the crfun values when these crfun values are fractional. For example:
For crfun = 1.23e-02 & delta = 1 will be transformed to 0.0001 For crfun = 2.45e-01 & delta = 5 will be transformed to 0.005
The default delta value when the crfun values are fractional is 1.
However if the crfun values are integer/whole numbers (exponent >= 2) then the specified delta value is internally shifted only until the least significant digit in the scientific notation. For example:
For crfun = 1.23e+04 & delta = 2 will be transformed to 200 For crfun = 2.45e+02 & delta = 5 will be transformed to 5 For crfun = 1.44e+03 & delta = 1 will be transformed to 10
Specifies the clustering method.
The possible option values:
rb - Repeated Bisections [Default] rbr - Repeated Bisections for by k-way refinement direct - Direct k-way clustering agglo - Agglomerative clustering bagglo - Partitional biased Agglomerative clustering [Only in vector space]
For large amount of data, 'rb', 'rbr' or 'direct' are recommended.
Selects the criteria function for Clustering. The meanings of these criteria functions are explained in Cluto's manual.
i1 - I1 Criterion function i2 - I2 Criterion function [Default] h1 - H1 Criterion function h2 - H2 Criterion function e1 - E1 Criterion function
Specifies the similarity measure to be used
cos - Cosine [Default] corr - Correlation Coefficient
NOTE: This option can be used only in vector space.
The option is used to specify the model to be used to scale every column of each row. (For further details please refer Cluto manual)
none - no scaling is performed [Default] maxtf - post scaling the values are between 0.5 and 1.0 sqrt - square-root of actual values log - log of actual values
The option is used to specify the model to be used to (globally) scale each column across all rows. (For further details please refer Cluto manual)
none - no scaling is performed [Default] idf - scaling according to inverse-document-frequency
The threshold value that should be used by the PK1 measure to predict the k value.
Default = -0.7
Specifies the precision to be used.
Default: 4
The number of replicates/references to be generated.
Default: 1
Specifies whether to generate B replicates from a reference or to generate B references.
rep - replicates [Default] ref - references
The seed to be used with the random number generator.
Default: No seed is set.
Specifies the percentage confidence to be reported in the log file. Since Statistics::Gap uses parametric bootstrap method for reference distribution generation, it is critical to understand the interval around the sample mean that could contain the population ("true") mean and with what certainty.
Default: 90
Displays the quick summary of program options.
Displays the version information.
Displays to STDERR the current program status.
prefix.pk(1|2|3)
Contains the crfun values, (PK1, PK2, PK3) values and the predicted k.
prefix.gap
Contains the crfun values, delta values and the predicted k.
prefix.gap.log
Contains a table of values for Gap(k), Obs(crfun(k)), Exp(crfun(k)), sd(k), s(k) and Confidence interval. Also contains individual crfun values for each of the B replicates/references for every value of K.
The following files (*.dat) files are created to facilitate creation of plots if required.
prefix.cr.dat
Contains the crfun values.
prefix.pk(1|2|3).dat
Contains the PK1, PK2, or PK3 values.
prefix.exp.dat
Contains the Exp(crfun(k)) values generated for Gap Statistics.
prefix.gap.dat
Contains the gap(k) values.
Each of the four cluster-stopping measure PK1, PK2, PK3 and Gap try to predict the optimal number of clusters for the provided data (represented in the form of vectors or similarity values).
Following is a description about each of the measures and how they select a k value.
crfun[m] - mean(crfun[1...deltaM]) PK1[m] = ----------------------------------- std(crfun[1...deltaM]) where m = 2,...deltaM deltaM is a m value beyond which the crfun value does not change much.
k selection strategy: If m is the first value for which the PK1 score is greater than the threshold value then m-1 value is selected as the k value when using one of the maximization criterion functions like I2, H2 etc. While using minimization criterion functions like E1, if m the first value for which the PK1 score is less than the threshold value then m-1 is selected as the k value.
crfun[m] PK2[m] = ------------ crfun[m-1] where m = 2,...deltaM
k selection strategy: One standard deviation interval for the set of PK2[m] values id calculated and the m value for which the PK2 score is outside this interval but is still closest to the interval (from outside) is selected as the k value.
2 * crfun[m] PK3[m] = ------------------------- crfun[m-1] + crfun[m+1] where m = 2,...deltaM
k selection strategy: Similar to that of PK2. One standard deviation of the PK3[m] scores is computed and the m value for which the PK3 score is outside this interval but is still closest to the interval (from outside) is selected as the k value.
Adapted Gap tries to predict the optimal number of clusters by comparing the criterion function values that one gets for the observed/given data with the criterion function values that one gets for a random data. It uses hypothesis testing in this process where the null hypothesis is that the optimal number of clusters for the given data is 1 and the aim is to refute this null hypothesis if the given data exhibits enough pattern.
The plot of crfun values for given data is compared with the plot of crfun values for random or reference data. The m value corresponding to the first point of maximum difference between the two plots is chosen as the predicted k when using the maximization crfuns. While for the minimization crfuns, the m value corresponding to the first point of minimum difference between the two plots is choosen as the predicted k value.
We provide two methods for the generation of reference data:
Please refer to http://search.cpan.org/dist/Algorithm-RandomMatrixGeneration/ to learn more about generating random dataset over the observed distribution by holding the row and the column marginals fixed.
The input matrix can be in either dense or sparse format. The cell values can be integer or real. Depending upon the value specified for the space parameter the header in the input file (first line) changes.
Example of input matrix in dense format when space=vector:
The first line specifies the dimensions - #rows #cols
From the second line the actual matrix follows.
6 5 1.3 2 0 0 3 2.1 0 4 2.7 0 1.3 2 0 0 3 2.1 0 4 2.7 0 1.3 2 0 0 3 2.1 0 4 2.7 0
Example of input matrix in dense format when space=similarity:
The matrix, when in similarity space, is square and symmetric.
The first line specifies the dimensions - #rows/#cols
5 1.0000 0.3179 0.5544 0.2541 0.4431 0.3179 1.0000 0.1386 0.4599 0.5413 0.5544 0.1386 1.0000 0.5143 0.2186 0.2541 0.4599 0.5143 1.0000 0.5148 0.4431 0.5413 0.2186 0.5148 1.0000
Example of input matrix in sparse format when space=vector:
The first line specifies the dimensions & number of non-zero elements - #rows #cols #nonzeroElem
From the second line the matrix contents follow. Only non-zero elements are specified. Thus the elements are specified as pairs of - #col elem. The row number is implied by the (line number-1).
8 10 41 1 3 4 2 8 2 10 1 1 1 2 5 3 1 5 2 7 1 9 2 1 3 4 2 8 2 10 1 1 1 2 5 3 1 5 2 7 1 9 2 1 3 4 2 8 2 10 1 1 1 2 5 3 1 5 2 7 1 9 2 2 4 3 1 4 2 5 5 7 1 9 1 2 4 3 1 4 2 5 5 7 1 9 1
Example of input matrix in sparse format when space=similarity:
The first line specifies the dimensions & number of non-zero elements - #rows/#cols #nonzeroElem
The matrix format is same as explained above.
5 15 1 1.0000 3 0.5544 5 0.4431 2 1.0000 3 0.1386 4 0.4599 5 0.5413 1 0.5544 2 0.1386 3 1.0000 2 0.4599 4 1.0000 1 0.4431 2 0.5413 5 1.0000
Anagha Kulkarni, Carnegie-Mellon University Ted Pedersen, University of Minnesota, Duluth tpederse at d.umn.edu
Copyright (c) 2006-2008, Anagha Kulkarni and Ted Pedersen
This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with this program; if not, write to
The Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
To install Text::SenseClusters, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Text::SenseClusters
CPAN shell
perl -MCPAN -e shell install Text::SenseClusters
For more information on module installation, please visit the detailed CPAN module installation guide.