改良式螞蟻分群演算法

An improved ACO-based Clustering Algorithm

丁淯淨(Yu-Ching Ting)

指導教授 ： 高有成

大同大學/經營設計學院/資訊經營學系所/碩士(2007年)

摘要

資料分群(Data Clustering)是資料採礦領域重要的研究課題，也是一種相當重要的資料分析技術。由於資料分群問題屬於NP-Hard的問題，所以有許多學者應用巨集啟發法則求解該種問題。Shelokar首先應用螞蟻最佳化演算法(Ant Colony Optimization, ACO)來發展資料分群方法，但是該方法並未使用啟發資訊，所以須要較多的螞蟻數目及較長的時間才能得到較佳的解。本研究改良其方法，將啟發資訊加入於狀態移轉機率模式，期望能提升資料分群之能力。
本研究所提出的演算法，主要是利用資料點與各個群中心的距離作為啟發資訊，來加快個別螞蟻的分群速度，同時以費洛蒙的長期學習機制來避免落入區域最佳解，因此可以有效解決分群問題。其分群過程是讓螞蟻先隨機挑選資料點，再依機率模式選擇群組，而個別螞蟻所形成的群中心會隨著分群過程逐漸調整；當分群過程結束時，最終之群中心也隨之形成。本研究利用數個典型資料分群題目進行驗證，結果顯示本研究所提出的演算法確實優於Shelokar的演算法。最後本研究將演算法應用於求解單元形成問題，以證實其在實務應用面之能力。

關鍵字

資料採礦 ； 資料分群 ； 螞蟻演算法 ； 單元形成問題

並列摘要

Data Clustering is one of the important research topics of data mining. Many people used meta-heuristic method to solve this NP-Hard problem. Previously, Shelokar is the first one to propose an ant colony approach for clustering. Because the heuristic information does not be used in this approach, more ants and more CPU time are required to attain the best solution. In this paper we improve this approach by adding heuristic information to the state transition rule.
At the core of the algorithm we use both the accumulated pheromone and the heuristic information, the distances between data objects and cluster centers of ants, to guide artificial ants to group data objects into proper clusters. This allows the algorithm to perform the clustering process more effectively and efficiently. Due to the nature of stochastic and population-based search, our algorithm can overcome the drawbacks of traditional clustering methods that easily converge to local optima. Experimental results show that the algorithm is batter than Shelokar’s approach. Finally, we apply our algorithm to solve Cell Formation Problem and have a good result.

並列關鍵字

ACO ； data mining ； data clustering ； Cell Formation Problem

參考文獻

[1] Agrawal R., Gehrke J., Gunopulos D. and Raghavan P., “Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications.” Proc. of the ACM SIGMOD Conference on Management of Data, pp. 94-104, 1998.

[2] Al-Sultan K. S., “A tabu search approach to the clustering problem.” Pattern Recognition Vol. 28, 1443-1451, 1995.

[4] Chandrasekharan M. P., and Rajagopalan R., “An ideal seed non-hierarchical clustering algorithm for cellular manufacturing.” International Journal of Production Research, Vol. 24, pp. 451-464, 1986.

[5] Chandrasekharan M.P. and Rajagopalan R., “MODROC : an extension of rank order clustering for group technology.” International Journal of Production Research, Vol. 24 pp.1221-1233, 1986.

[6] Chandrasekharan M.P. and Rajagopalan R., “ZODIAC: an algorithm for concurrent formation of part families and machines cells.” International Journal of Production Research. Vol. 25, pp. 835-850, 1987.