在資料探勘研究領域中，資料分群的方法扮演相當重要的角色，被廣泛應在不同的領域中。一個好的分群演算法能快速而正確的分群，進而可以突顯群集的特性，以便後續的資料處理分析動作。k-means是最為常用的分群演算法，雖具有快速分群以及簡單運用之特性，但也存在許多缺點導致其分群效果未必能達成最佳的分群結果。本文為了增進k-means的分群結果，因此提出以模擬退火演算法為基礎的分群方式，此方法簡稱為HSAKM。
首先找出第一次k-means分群後之中心點，在每群中找最接近原中心點的m個資料點作為新的中心，再經過退火擾動分群動作，可增進K-Means分群的效能。本研究將與K-Means以及與其它的分群分群演算法相互比較，以驗證所提的出方法較能有更好的效能。

The data clustering acted as crucial role for data mining, and it is used in more different fields extensively. A good clustering algorithm can quickly and correctly for partition the dataset into clusters. Also, it can point out the cluster characteristics, and then may be provided for further data analysis work. The k-means algorithm is one of the most commonly used clustering algorithms. However, the k-means clustering result doesn’t reach the best clustering result, so in order to promote the k-means algorithm to get the best or near-best clustering result. Therefore, we propose an integrated approach based on SA algorithm called HSAKM for data clustering.
First k-means clustering to find cluster centers. Then search m data with the shortest distance to the cluster center of each cluster as new cluster centers. Moreover, perform the SA clustering to improving the efficiency for the k-means. Furthermore, compare HSAKM algorithm with each other clustering algorithms to demonstrate our proposed clustering algorithm is much better than others.

[1] UCI(University of California，Irvine) Repository of Machine Learning Databases.
Available：ftp://ftp.ics.uci.edu/pub/machine-learning-databases/
[2] W.T.A. Lopes, Madeiro，M.S. Alencar, and B.G. Aguiar Neto, “Simulated Annealing for Robust VQ: Improving Image Transmission through a Fading Channel，”IEEE Computer Society Press，VI Brazilian Symposium on Neural Networks，pp.243-248，Rio de Janeiro，Brazil，2000.
[3] J. Ning, S. McClean, and K. Cranley, “3D Reconstruction from Two Orthogonal Views Using Simulated Annealing Approach,”IEEE Computer Society Press，Third International Conference on 3-D Digital Imaging and Modeling, pp.309-319, 2001.
[4] X.Y. Wang, J.M. Garibaldi, “Simulated Annealing Fuzzy Clustering in Cancer Diagnosis,”Information，Vol.29,pp.61-70,Number 2005.
[5] N. Metropolis, A.W. Rosenbluth, A. Teller, and E. Teller, “Wquation of State Calculation by Fast computing Machines,”Journal of Chemical Physics, Vol.21, No. 6, pp. 1087-1092，1953.
[6] S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi, “Optimization by Simulated Annealing,”Science, vol.220, N0.4589, pp.671-680, 1983.
[7] Q. Zhang and Y.W. Leung, “An orthogonal genetic algorithm for multimedia multicast routine,”IEEE Trans, Evolutionary Computation, col.3, no.1, pp.41-53, Apr. 1998.
[8] Y.W. Leung, Y. Wang, “An Orthogonal Genetic algorithm with Quantization for Global Numerical Optimization,”IEEE Trans. Evolutionary Computers. , Vol.5, pp.41-53，Feb. 2001.
[9] J.T. Tsai, J.H Chou, and T.K. Lin, “Tuning the Structure and Parameters of a Neural Network by using Hybrid Taguchi-genetic Algorithm，”IEEE Trans. Neural Networks，Vol.17, pp.69-80, Jan. 2006.
[10] S.Y. HO, Y.K. Lin, “OSA: Orthogonal Simulated Annealing Algorithm and Its Application to Designing Mixed / Optimal Controllers,”IEEE Trans. Syst., Man, Cybern. A，Vol. 34，pp.588-600, Sept. 2004.
[11] S.Y Ho , Y.K. Lin, “Orthogonal Simulated Annealing for Floorplanning,”Artificial Intelligence and Application Conference，pp.469-474, 2002.
[12] D.C. Montgomery, Design and Analysis of Experiments，3rd ed. New York: Wiley, 1991.
[13] C.R. Hicks, Fundamental Concepts in the Design of Experiments，4th ed .TX:Saunders College Publishing, 1993.
[14] T.S. Chen, Y.T. Chen, C.C. Lin，and R.C. Chen, “A combined K-Means and Hierarchical Clustering Method for Improving the Clustering Efficiency of Microarray,” Intelligent Signal Processing and Communications Systems, pp.405-408, 2005.
[15] M.H. Dunham, Data Ming: Introductory and Advanced Topics, Prentice Hall, 2003.
[16] R.J. Roiger, M.W. Geatz, Data Mining：A Tutorial-Based Primer，Addision Wesley, 2003.
[17] H. Szu, R. Hartley，“Fast simulated annealing,”Phys.Lett. , Vol. 122，pp.157-162, 1987.
[18] V. Petridis, S. Kazarlis, and A. Bakirtzis, “Varying fitness function in genetic algorithm constrained optimization：The cutting stock and unit commitment problems,”IEEE Trans. Syst. , Man，Cybern.B, Vol. 28，pp.629-540, Oct.1998.
[19] P.S. Shelokar, V. K. Jayaraman, B. D. Kulkarni, “An ant colony approach for cluster,”Analytica Chimica Acta, Vol.509, Issue 2, pp. 187-195，May. 2004.
[20] Lizhong Xiao, Zhiqing Shao, Gang Liu, “K-means Algorithm Based on Particle Swarm Optimization Algorithm for Anomaly Intrusion Detection,” Intelligent Control and Automation Vol.2, pp.5854-5858, June. 2006
[21] Fun Ye, C.Y. Chen, “Alternative KPSO-Clustering Algorithm,” Journal of Science and Engineering, Vol. 8, No 2, pp.165- 174, 2005.
[22] Ujjwal Maulik, Sanghamitra Bandyopadhyay, “Genetic algorithm- based clustering technique,”Pattern Recognition, Vol. 33, pp.1455- 1465, 2000.
[23] Ujjwal Maulik, Sanghamitra Bandyopadhyay, “Cluster Using Simulated Annealing with Probabilistic Redistribution,” Journal of Pattern Recognition and Artificial Intelligence, Vol.15, pp.269- 285, 2001.
[24] Zülal Güngör, Alper Ünler, “K-harmonic means data clustering with simulated annealing heuristic,”Applied Mathematics and Computation, Vol. 184, Issue 2, 15, pp.199-209, Jane. 2007.
[25] Krista Rizman Žalik, “An efficient k′-means clustering algorithm，”Pattern Recognition Letters, Volume 29, Issue 9, 1, pp. 1385-1391,July 2008.
[26] Adil M. Bagirov, “Modified global k-means algorithm for minimum sum-of-squares clustering problems,” Pattern Recognition, Vol.41, Issue 10, pp. 3192-3199, Oct. 2008.
[27] 林育臣(2002)，群聚技術之研究，碩士論文，朝陽科技大學資訊管理系，台中。