This study discusses and compares grid proximity measures that use representative data points in grid cells and the average distance between the data points in grid cells. Basic theorems for the grid distance measure are formulated and proved. The grid distance measure is applied to the grid-based clustering problem where the number of clusters is dynamically determined by using a threshold value and by maximizing intra-similarity in a cluster and inter-dissimilarity between the clusters.
In this study, the grid-based clustering problem is illustrated and formulated using a 0-1 integer programming approach. We perform numerical experiments on randomly generated problems and also for a clustering problem concerning microarray data of human fibroblasts in varying serum concentrations, with the latter data having been taken from a prior study. The theorems are applicable to the grid-based clustering of any data set.
AminiA., WahT.Y., SaybaniM.R. and YazdiS.R.A.S., A study of density-grid based clustering algorithms on data streams, The 8Th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD) (2011).
2.
XuR. and Wunsch IID., Survey of clustering algorithms, IEEE Transactions of Neural Networks16(3) (2005), 645-678.
3.
CiosK.J., PedryczW., SwiniarskiR.W. and KurganL.A., Data Mining: A Knowledge Discovery Approach, Springer, (2007), 272-274.
4.
HanJ. and KamberM., Data mining concepts and techniques, Morgan Kaufman, 2nd edition, (2006), 398-434.
5.
LawlerE., LenstraJ., RinnoonyK.A. and ShimoysD., The traveling salesman problem: A guided tour of combinatorial optimization, John Wiley, New York, 1985.
6.
DutaR.O. and HartR.O., Pattern classification and scene analysis, chicheste, John Wiley and Sons, 1973.
7.
BlankenH., IjbemaA., MeekP. and AkkerB., The generalized grid files: Description and performance aspects, Pattern Recognition37(3) (1990), 503-514.
8.
LiaoW.-K., LiuY. and ChoudharyA., A grid-based clustering algorithm using adaptive mesh refinement, The 7th workshop on mining scientific and engineering data sets, 2004.
9.
MaE.W.M. and ChowT.W.S., A new shifting grid clustering algorithm, Pattern Recognition37(3) (2004), 503-514.
10.
YueS., WeiM., WangJ.-S. and WangH., A general grid-clustering approach, Pattern Recognition Letters29(9) (2008), 1372-1384.
11.
ZhaoY.C. and SongJ., GDILC: A grid-based density-isoline clustering algorithm, Proceedings of International Conference on Information-Network3 (2001), 140-145.
12.
BoudraaA.-O., Dynamic estimation of number of clusters in data sets, Electrics Letters35(19) (1999), 1606-1608.
13.
DembeleD. and KastnerP., Fuzzy C-means method for clustering microarray data, Bioinformatics19(8) (2003), 973-980.
14.
HalkidiM., BatistakisY. and VazirgiannisM., Clustering algorithms and validity measures, Proceedings of SSDBM Conference, Virginia, USA, July 2001.
15.
KwonS.H., Cluster validity index for fuzzy clustering, Electronic Letter34(22) (1998), 2176-2177.
16.
RayS. and TuriR.H., Determination of number of clusters in K-means clustering and application in color image segmentation, Proceedings of the 4th International Conference on Advances in Pattern Recognition and Digital Techniques (ICAPRDT'99), Calcutta, India, (27-29 Dec 1999).
17.
ShenJ., ChangS.I., LeeE.S., DengY. and BrownS.J., Determination of cluster number in clustering microarray data, Applied Mathematics and Computation169 (2005), 1172-1185.
18.
DunnJ.C., A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters, Journal of Cybernetics3(3) (1973), 32-57.
19.
PilevarA.H. and SukumarM., GCHL: A grid-clustering algorithm for high-dimensional very large spatial data bases, Pattern Recognition Letters26(7) (2005), 999-1010.
20.
PanditS. and GuptaS., A comparative study on distance measure approaches for clustering, International Journal of Research in Computer Science2(1) 92011, 29-31.
21.
SunH., WangS. and JiangQ., A new validation index for determining the number of clusters in a data set, IJCNN '01, International Joint Conference on Neural Networks (2001), 1852-1857.
22.
HsuC.-M. and ChenM.-R., Subspace clustering of high dimensional spatial data with noises, Lecture Notes in Computer Science3056 (2004), 31-40.
23.
SchrageL.E., Optimization modeling with LINDO, Duxbury Press, 1997.
24.
IyerV.R., EisenM.B., RossD.T., SchulerG., MooreT., LeeJ.C.F., TrentJ.M., StaudtL.M., Jr., HudsonJ., BogoskM.S. et al., The transcriptional program in the response of human fibroblast to serum, Science283 (1999), 83-87.
25.
AnandS.S., BellD.A. and HughesJ.G., The role of domain knowledge in data mining, Proc ACM CIKM '95, Baltimore MD USA, (1995), 37-43.
26.
PohleC., Integrating and updating domain knowledge with data mining, The 6th International Conference for Business Informatics 2003 (WI-2003), Dresden, Germany, (2003), 15-17.
27.
KopanasI., AvourisN.M. and DaskalakiS., The role of domain knowledge in a large scale data mining project, LNAI2308 (2002), 288-299.
28.
DembéléD. and KastnerP., Fuzzy C-means method for clustering microarray data, Bioinformatics19(8) (2003), 973-980.
