Using Pattern Search Methods for Minimizing Clustering Problems
Clustering is one of an interesting data mining topics
that can be applied in many fields. Recently, the problem of cluster
analysis is formulated as a problem of nonsmooth, nonconvex optimization,
and an algorithm for solving the cluster analysis problem
based on nonsmooth optimization techniques is developed. This
optimization problem has a number of characteristics that make it
challenging: it has many local minimum, the optimization variables
can be either continuous or categorical, and there are no exact
analytical derivatives. In this study we show how to apply a particular
class of optimization methods known as pattern search methods
to address these challenges. These methods do not explicitly use
derivatives, an important feature that has not been addressed in
previous studies. Results of numerical experiments are presented
which demonstrate the effectiveness of the proposed method.
[1] A. K. Jain, M. N. Murty and P. J. Flynn, Data clustering: a review, ACM
Comput. Surv., Vol. 31, No. 3. , pp. 264-323, Sep. 1999.
[2] P. Hansen, B. Jaumard, Cluster analysis and mathematical programming,
Mathematical Programming, 79(1-3), 191-215, 1997.
[3] H. H. Bock, Clustering and neural networks, in: A. Rizzi, M. Vichi,
H.H. Bock (Eds.), Advances in Data Science and Classification, Springer,
Berlin, 1998, pp.265-277.
[4] H. Spath, Cluster Analysis Algorithms, Ellis Horwood Limited, Chichester,
1980.
[5] A. M. Bagirov, A. M. Rubinov, and N. V. Soukhoroukova, J. Yearwood,
Supervised and unsupervised data classification via nonsmooth and
global optimization, TOP:Span. Oper. Res. J. 11 (1), 1-93, 2003.
[6] P. Hansen, E. Ngai, and B. K. Cheung, N. Mladenovic, Analysis of global
k-means, an incremental heuristic for minimum sum-of squares clustering,
Research Paper G-2002-43, GERAD, Montreal, Canada, 2002.
[7] C. R. Reeves, Modern Heuristic Techniques for Combinatorial Problems
.London, Blackwell, 1993.
[8] T. G. Kolda, R. M. Lewis, V. Torczon, Optimization by direct search:
new perspectives on some classical and modern methods. SIAM Rev., 45
(2003), pp.385-482.
[9] H. H. Bock, Automatische Klassifikation, Vandenhoeck and Ruprecht,
1974,Gottingen.
[10] V. Torczon, On the convergence of pattern search algorithms, SIAM J.
Optim. 7 (1997) 1-25.
[11] R. M. Lewis, V. Torczon, Pattern search algorithms for linearly constrained
minimization, SIAM Journal on Optimization 10(3), 917-941
(2000)
[12] J. E. Dennis Jr., V. Torczon, Direct Search Methods on Parallel Machines,
SIAM Journal on Optimization 1, 448 ,1991.
[13] C. Audet, J. E. Dennis Jr., Analysis of generalized pattern searches,
SIAM J. Optim. 13, 889-903, 2003.
[14] C. Audet, Convergence results for generalized pattern search algorithms
are tight, Optim. Eng. 5 ,101-122, 2004.
[15] K. S. Al-Sultan, M. M. Khan, Computational experience on four
algorithms for the hard clustering problem, Pattern Recognition Letters
17, 295-308, 1996
[1] A. K. Jain, M. N. Murty and P. J. Flynn, Data clustering: a review, ACM
Comput. Surv., Vol. 31, No. 3. , pp. 264-323, Sep. 1999.
[2] P. Hansen, B. Jaumard, Cluster analysis and mathematical programming,
Mathematical Programming, 79(1-3), 191-215, 1997.
[3] H. H. Bock, Clustering and neural networks, in: A. Rizzi, M. Vichi,
H.H. Bock (Eds.), Advances in Data Science and Classification, Springer,
Berlin, 1998, pp.265-277.
[4] H. Spath, Cluster Analysis Algorithms, Ellis Horwood Limited, Chichester,
1980.
[5] A. M. Bagirov, A. M. Rubinov, and N. V. Soukhoroukova, J. Yearwood,
Supervised and unsupervised data classification via nonsmooth and
global optimization, TOP:Span. Oper. Res. J. 11 (1), 1-93, 2003.
[6] P. Hansen, E. Ngai, and B. K. Cheung, N. Mladenovic, Analysis of global
k-means, an incremental heuristic for minimum sum-of squares clustering,
Research Paper G-2002-43, GERAD, Montreal, Canada, 2002.
[7] C. R. Reeves, Modern Heuristic Techniques for Combinatorial Problems
.London, Blackwell, 1993.
[8] T. G. Kolda, R. M. Lewis, V. Torczon, Optimization by direct search:
new perspectives on some classical and modern methods. SIAM Rev., 45
(2003), pp.385-482.
[9] H. H. Bock, Automatische Klassifikation, Vandenhoeck and Ruprecht,
1974,Gottingen.
[10] V. Torczon, On the convergence of pattern search algorithms, SIAM J.
Optim. 7 (1997) 1-25.
[11] R. M. Lewis, V. Torczon, Pattern search algorithms for linearly constrained
minimization, SIAM Journal on Optimization 10(3), 917-941
(2000)
[12] J. E. Dennis Jr., V. Torczon, Direct Search Methods on Parallel Machines,
SIAM Journal on Optimization 1, 448 ,1991.
[13] C. Audet, J. E. Dennis Jr., Analysis of generalized pattern searches,
SIAM J. Optim. 13, 889-903, 2003.
[14] C. Audet, Convergence results for generalized pattern search algorithms
are tight, Optim. Eng. 5 ,101-122, 2004.
[15] K. S. Al-Sultan, M. M. Khan, Computational experience on four
algorithms for the hard clustering problem, Pattern Recognition Letters
17, 295-308, 1996
@article{"International Journal of Engineering, Mathematical and Physical Sciences:50268", author = "Parvaneh Shabanzadeh and Malik Hj Abu Hassan and Leong Wah June and Maryam Mohagheghtabar", title = "Using Pattern Search Methods for Minimizing Clustering Problems", abstract = "Clustering is one of an interesting data mining topics
that can be applied in many fields. Recently, the problem of cluster
analysis is formulated as a problem of nonsmooth, nonconvex optimization,
and an algorithm for solving the cluster analysis problem
based on nonsmooth optimization techniques is developed. This
optimization problem has a number of characteristics that make it
challenging: it has many local minimum, the optimization variables
can be either continuous or categorical, and there are no exact
analytical derivatives. In this study we show how to apply a particular
class of optimization methods known as pattern search methods
to address these challenges. These methods do not explicitly use
derivatives, an important feature that has not been addressed in
previous studies. Results of numerical experiments are presented
which demonstrate the effectiveness of the proposed method.", keywords = "Clustering functions, Non-smooth Optimization, Nonconvex Optimization, Pattern Search Method.", volume = "4", number = "2", pages = "210-5", }