(3.238.130.97) 您好!臺灣時間:2021/05/18 11:11
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:陳昱丞
研究生(外文):Yu-Cheng Chen
論文名稱:運用粒子群演算法以求解分群問題
論文名稱(外文):Particle Swarm Optimization for Sloving Clustering Problem
指導教授:李維平李維平引用關係
指導教授(外文):Wei-Ping Lee
學位類別:碩士
校院名稱:中原大學
系所名稱:資訊管理研究所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2009
畢業學年度:96
語文別:中文
論文頁數:45
中文關鍵詞:粒子群演算法置換群集分析分群擾動因子
外文關鍵詞:PSOClusterReplaceDissipative
相關次數:
  • 被引用被引用:1
  • 點閱點閱:242
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
資料分群在資料探勘中,是一門常見與重要的技術,它可以從龐大的資料中,找出資料的分佈狀況並找出其隱藏的意義。而隨著群體智慧的興起,相關學者紛紛將群體智慧技術應用在資料分群研究上,也獲得良好的分群效果。而在相關研究中,粒子群演算法在資料分群上亦獲得良好的效果。粒子群演算法乃模擬鳥群覓食的行為所衍生的最佳化搜尋演算法,具備穩健性,快速收斂與易實現的特性,在解空間中充分展現極佳的搜尋能力。

針對資料分群問題,為求得最佳分群結果,本研究提出RDPSO演算法,主要運用粒子群演算法的區域搜尋與快速收斂能力於資料分群上,同時為加強群集中心分群時的正確性,加入群中心點置換策略,以改善隨機選擇的問題。另外粒子群的快速收斂易導致粒子陷入區域最佳解問題,於演算法中加入擾動因子,讓粒子可以跳脫區域最佳解的問題。因此本研究所提之RDPSO的優點有
A.在一定的機率下加入擾動因子增加搜尋空間,讓粒子可以跳脫區域最佳解的困境,以提高分群的結果;另外因加入機率因素於演算法中,使得粒子不會侷現在固定迭代數的問題,使得粒子的迭代運算更加靈活。
B.群集中心點的選擇,運用群中心點置換策略,讓中心點與各個粒子運用歐幾里得距離向量演算來決定中心點的最適性,取代以往採用隨機方式選擇中心點作為群集中心點。
Data Clustering in Data Mining is the common and important technology. It can find out the data distribution and meaning in the huge data.By the Swarm Intelligence rising, more researchers use this technology of the Swarm Intelligence on data clustering, also get better effect.However,in these researches, Particle Swarm Optimization Algorithm(PSO) also has good effect on data clustering. PSO is a population-based stochastic search process, modeled after the social behavior of a bird flock, has the character of robust、quick converges and easy accomplish,and in space it shows the best search process.

For the problem of data clustering to have the best clustering result, in this study, the research suggest RDPSO Algorithm, and the primary in data clustering, perform the PSO local search and quick converges ability, simultaneously to enhance choose the cluster center correctness in clustering, I recommand the concept of K Nearest Neighbor algorithm to impove the random choose problem.Beside it, the quick converges of PSO will result to get into local optima problem. I add the chaos factor in the algorithm to let particle escape the local optima problem.Therefore, the advantage of RDPSO in the reasearch is:
A. In the certain probability to add chaos factor to increase particle search space, let particle escape local optima problem to enhance the clustering result; and by add probability factor in the algorithm, make particle to being more automatic and flexible increase more opportunities to search new space.
B.The clustering central point's choice, replaces the strategy using the group central point, lets the central point with each granule using Euclidean from the vector calculus decide that the central point most suitable, the substitution formerly used the stochastic mode selection central point to take the clustering central point.
目 錄
中 文 摘 要 I
英 文 摘 要 II
謝 誌 III
圖目錄 VI
表目錄 VII
第一章 緒 論 - 1 -
1.1 研究背景 - 1 -
1.2 研究動機 - 2 -
1.3 研究目的 - 3 -
第二章 文獻探討 - 4 -
2.1傳統群集分析 - 4 -
2.1.1分割分群演算法(partitional clustering algorithms ) - 4 -
2.1.2 階層分群演算法(hierarchical clustering algorithm) - 5 -
2.1.3密集度導向分群演算法(density-based clustering algorithm) - 5 -
2.1.4 格子基礎分群演算法(grid-based clustering algorithm) - 6 -
2.2粒子群演算法 - 8 -
2.3 演化式演算法解分群問題相關研究 - 11 -
2.4 活化型粒子群演算法 - 16 -
第三章 研究方法 - 17 -
3.1 粒子群分群演算設計 - 18 -
3.1.1 粒子分群建立 - 18 -
3.1.2 適應值 - 19 -
3.1.3 分群終止條件 - 20 -
3.2 演算法架構 - 21 -
3.2.1 DPSO分群演算法 - 21 -
3.2.2 RDPSO分群演算法 - 24 -
第四章 實驗結果 - 27 -
4.1 實驗測試集 - 27 -
4.2 實驗環境與參數設計 - 28 -
4.3 實驗結果 - 29 -
4.4 綜合比較 - 32 -
第五章 結論與未來研究 - 34 -
5.1結論 - 34 -
5.2未來研究 - 35 -
文獻參考 - 36 -

圖目錄

圖2.1階層式演算法示意圖…………………………………………….………….5
圖2.3粒子速度與位置示意圖……………………………………………………. 8
圖2.4粒子群演算法流程示意圖………………………………………….………10
圖3.1研究架構之演算法設計步驟圖…………………………………………….17
圖3.2粒子編碼範例圖…………………………………………………………….18
圖3.3 DPSO流程圖………..……………………………………………..………..22
圖3.4群中心點置換策略示意圖…….…….……………………………..……….24
圖3.5 RDPSO流程圖……………..…..…………………………………..……….25

表目錄

表2-1 K-means、PSO、Hybrid Clustering演算法比較…………….……….…..13
表2-2 K-means, FCM, KHM, H2, GA and PSO 比較表……………….…….…..14
表2-3 DCPSO Clustering on Natural Images…………………………….....….….15
表4.1四種測試集總表…………………………………………………….…….…..28
表4.2 PSO參數設定……………………………………………….…...…………...28
表4.3實驗數據比較表…………………………………….……………….………..29
表4-4 RDPSO參數實驗數據表………………………………………………….…30
表4-5適應值綜合比較………………………………………………………….......33
[1] Han J. and Kamber M., “Data Mining: Concepts and Techniques,” Morgan Kaufmann, 2000.
[2] Brucker P, “On the complexity of clustering problems,” in Optimization and Operations Research, vol. 157, Beckmenn M, and Kunzi H. P., Berlin Eds., Germany: Springer-Verlag, 1978, pp. 45–54.
[3] MacQueen J., “Some Methods for Classification and Analysis of Multivariate Observations,” In Proc. 5th Berkeley Symp. Math. Stat. and Prob., Vol. 1, pp. 281-297, 1967.
[4] Kaufman L. and Rousseeuw PJ, “Finding Groups in Data: an Introduction to Cluster Analysis,” John Wiley & Sons, 1990.
[5] Ng R. and Han J., “ Efficient and Effective Clustering Method for Spatial Data Mining,” In Proc. 1994 Int. Conf. Very Large Databases (VLDB’94), pp. 144-155, Santiago, Chile, Sept. 1994.
[6] Jain A. K., Murty M. N., and Flynn P. J., “Data clustering: A review,”ACM Comput.
Surv., vol. 31, no. 3, pp. 264–323, Sep. 1999.
[7] Zhang T., Ramakrishnan R. and Livny M., “BIRCH: An Efficient Data Clustering Method for Very Large Databases,” In Proc. 1996 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD’96), pp. 103-114, 1996.
[8] Guha S., Rastogi R. and Shim K., “CURE: An efficient clustering algorithm for large databases,” In Proc. 1998 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD’98), pp. 73-84, Seattle, WA, June 1998.
[9] Guha S., Rastogi R. and Shim K., “ROCK: A Robust Clustering Algorithm For Categorical Attribute,” In Proc. 1999 Int. Conf. Data Engineering (ICDE’99), pp. 512-521, Sydney, Australia, Mar. 1999.
[10] Karypis G., Han E.H. and Kumar V., “CHAMELEON: Hierarchical Clustering Using Dynamic Modeling,” IEEE Computer, Vol. 32, No. 8, pp. 68-75, (1999).
[11] Estivill-Castro V. and Lee I., “AMOEBA: Hierarchical Clustering Based on Spatial Proximity Using Delaunay Diagram,” In Proc. 9th Int. Spatial Data Handling (SDH2000), pp. 10-12, Beijing, China, Aug. 2000.
[12] Estivill-Castro V. and Lee I., “AUTOCLUST: Automatic Clustering via Boundary Extraction for Massive Point Data Sets,” In Proc. 5th Int. Conf. Geo-Computation, pp. 23-25, University of Greenwich, Kent, UK. Aug. 2000.
[13] Ester M., Kriegel H.P., Sander J. and Xu X., “Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise,” In Proc. 1996 Int. Conf. Knowledge Discovery and Data Mining (KDD’96), pp. 226-231, Portland, OR, Aug. 1996.
[14] Ankerst M., Breunig M., Kriegel H.P. and Sander J., “OPTICS: Ordering points to identify the clustering structure,” In Proc. 1999 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD’99), pp. 49-60, Philadelphia, PA, June 1999.
[15] Wang W., Yang and Muntz R., “STING: A Statistical Information grid Approach to Spatial Data Mining,” In Proc. 1997 Int. Conf. Very Large Data Bases(VLDB’97), pp. 186-195, Athens, Greece, Aug. 1997.
[16] Sheikholeslami G., Chatterjee S., and Zhang A., “WaveCluster: A multi-resolution clustering approach for very large spatial databases,” In Proc. 1998 Int. Conf. Very Large Databases (VLDB’98), pp. 428-439, New York, Aug. 1998.
[17] 王子評, "一種有效及有效率的方法從含有雜訊的大型資料集中偵測任意圖樣的群集", 國立屏東科技大學資訊管理系碩士學位論文,2006.
[18] Raghavan V. V. andBirchand K., “A clustering strategy based on a formalism of the reproductive process in a natural system,” in Proc. 2nd Int.Conf. Inf. Storage Retrieval, 1979, pp. 10–22.
[19] Krishna K. and Murty M. N., “Genetic K-means algorithm,” IEEE Trans.Syst., Man,Cybern., vol. 29, no. 3, pp. 433–439, Jun. 1999
[20] Van der Merwe and Engelbrecht, "Data Clustering using Particle Swarm Optimization",IEEE Conf Syst.,2003
[21] Kennedy J. and Eberhart R. C., “A discrete binary version of the particle swarm algorithm, ” in Proc. IEEE Conf. Syst., Man, Cybern., 1997,pp. 4104–4108
[22] Omran M., Engelbrecht A., and Salman A., “Particle swarm optimization method for image clustering,” Int. J. Pattern Recognit. Artif. Intell.,vol. 19, no. 3, pp. 297–322, 2005.
[23] Mahamed G.H Omran, Andries P Engelbrecht, and Ayed Salman, "Dynamic Clustering using Particle Swarm Optimization with Application in Unsupervised Image Classification", PWAS Volume9 November,2005
[24] Ajith Abraham, Swagatam Das, and Sandip Roy,"Swarm Intelligence Algorithms for Data Clustering"
[25] Xiao-Feng Xie, Wen-Jun Zhang, Zhi-Lian Yang, "A Dissipative Particle Swarm Optimization",IEEE Conf Syst,2002
[26] Fix E. and Hodges J.L., “Discriminatory Analysis—Nonparametric Discrimination: Consistency Properties,” Project 21-49-004, Report 4, US Air Force School of Aviation Medicine, Randolph Field, pp. 261-279, 1951.
[27] Paterlini Sandra and Krink Thiemo, “Differential Evolution and Particle Swarm Optimization in Partitional Clustering.”, Computational Statistics and Data Analysis, 2006.
[28] 曾憲雄,蔡秀滿,蘇東興,曾秋蓉,王慶堯,”資料探勘”,旗標出版社,2006.
[29] 陳慶逸,“分群驗證及其在群聚分析演算法的應用”,Journal of China College of Marine Technology and Commerce,2007.
[30] 郭信川、張建仁、劉清祥,"粒子群演算法於最佳化問題之研究",國立台灣海洋大學
第一屆台灣作業研究學會學術研討會暨2004年科技與管理學術研討
會,p419-432,2004
[31] 陳慶逸,余繁“應用於資料探勘之演化式群聚分析技術”,2004 智慧型知識經濟暨
第二屆演化代計算應用研討會,真理大學,pp.153-161, 2004.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top