政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/130956

政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/130956

English | 正體中文 | 简体中文 | Post-Print筆數 : 27 | Items with full text/Total items : 113822/144841 (79%)
Visitors : 51785202 Online Users : 10

RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.

Scope

please add "double quotation mark" for query phrases to get precise results

please goto advance search for comprehansive author search

Adv. Search

Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer

Goto mobile version

政大典藏 > College of Commerce > Department of Statistics > Theses > Item 140.119/130956

Please use this identifier to cite or link to this item: https://nccur.lib.nccu.edu.tw/handle/140.119/130956

Title:	有大小限制之切割式分群演算法 Partitional Clustering Algorithms with Size Constraints
Authors:	粘明揚 Nian, Ming-Yang
Contributors:	洪英超 Hung, Ying-Chao 粘明揚 Nian, Ming-Yang
Keywords:	非監督式學習法切割分群演算法有限制的分群演算法尺寸限制分群演算法梯度下降法位區途程問題
Date:	2020
Issue Date:	2020-08-03 17:31:26 (UTC+8)
Abstract:	分群演算法是常見且重要的非監督式學習法。在實際應用上，我們有時必須考量分群樣本個數的大小尺寸限制，這是一般傳統分群演算法做不到的。在本篇論文中，我們提出有大小限制的切割式分群演算法，其流程類似於Lloyd 的演算法，終止迭代直至中心點收斂，盡量最小化分群的目標函式，且每一群的樣本數都滿足預先設定的尺寸限制。而我們的演算法主要有兩個部分，第一個部分為調整群樣本個數至滿足限制條件，在面對不平衡資料時，分群結果往往優於傳統分群演算法。第二個部分則是梯度下降法，藉由此部分來求得最佳中心點，也能夠避免群中心點受到極端值影響的情況(如K-means 演算法)，進而改善分群結果。在電腦模擬與實證分析方面，本文將所提出的演算法除了可以處理不平衡資料分群，還能解決汽車服務系統的位區途程策略問題(Location-Routing Problem，LRP)。除此之外，本文也就目標函式值大小以及演算法所耗費的運算時間和文獻中其他方法做比較，電腦模擬的結果證明本文所提之演算法無論是準確度和速度皆遠高於文獻中所提之方法。
Reference:	[1] J. Han, M. Kamber, J. Pei, (2011). “Data mining: concepts and techniques”, Burlington, Massachusetts, USA: Morgan Kaufmann. [2] P. Tan, M. Steinbach, and V. Kumar, (2005). “Introduction to data mining”, Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc. [3] A. K. Jain, M. N. Murty, and P. J. Flynn, (1999). “Data clustering: A review”, ACM computing surveys (CSUR), vol. 31, no. 3, pp. 264–323. [4] C. Aggarwal and K. Reddy, (2013). “Data clustering: Algorithms and applications”, UK: Chapman & Hall/CRC. [5] M. Steinbach, G. Karypis, V. Kumar et al., (2000). “A comparison of document clustering techniques,” KDD workshop on text mining, vol. 400, no. 1, pp. 525–526. [6] D. L. Pham, (2001). “Spatial models for fuzzy clustering”, Computer vision and image understanding, vol. 84, no. 2, pp. 285–297. [7] S. Kotsiantis, (2007). “Supervised machine learning: A review of classification techniques”, Informatica Journal, no. 31, pp. 249–268. [8] S. Haykin, (1998). “Neural networks: A comprehensive foundation”, Upper Saddle River, New Jersey, USA: Upper Saddle River: Prentice Hall. [9] M. Seeger, (2001). “Learning with labeled and unlabeled data.”, Ottawa-Carleton Institute for Computer Science. [10] Hinton, Geoffrey, Sejnowski, Terrence, (1999). “Unsupervised learning: foundations of neural computation”, Boston, MA, USA: MIT Press. [11] J. Buhmann, H. Kuhnel, (1992). “Unsupervised and supervised data clustering with competitive neural networks”, IJCNN International Joint Conference on Neural Networks. 4. pp. 796–801. [12] N. Grira, M. Crucianu, N. Boujemaa, (2004). “Unsupervised and semi-supervised clustering: A brief survey”, A Review of Machine Learning Techniques for Processing Multimedia Content, Report of the MUSCLE European Network of Excellence. [13] X. Zhu, A. B. Goldberg, (2009). “Introduction to semi-supervised learning”, UK: CRC. [14] S. Basu, A. Banerjee, R. J. Mooney, (2002). “Semi-supervised clustering by seeding”, in: Proceedings of ICML, pp. 27–34. [15] S. Basu, A. Banerjee, R. J. Mooney, (2004). “Active semi-supervision for pairwise constrained clustering”, in: Proceedings of SIAM Data Mining, pp. 333–344. [16] Z. Sun, G. Fox, W. Gu, (2014). “A parallel clustering method combined information bottleneck theory and centroid-based clustering”, The Journal of Supercomputing, no.69, pp. 452-467. [17] F. Gullo, A. Tagarelli, (2012). “Uncertain centroid based partitional clustering of uncertain data”, Scalable Uncertainly Management, pp. 229-242. [18] A. Solovyov, W. L. Lipkin, (2013). “Centroid based clustering of high throughput sequencing reads based on n-mer counts”, BMC Bioinformatics, no.268. [19] R. Sibson, (1973). “An optimally efficient algorithm for the single-link cluster method”, The Computer Journal. British Computer Society. [20] F. Murtagh, P. Contreras, (2012). “Algorithms for hierarchical clustering: An overview”, WIREs Data Mining and Knowledge Discovery, vol.2. [21] A. P. Reynolds, G. Richards, B. de la lglesia, V. J. Rayward-Smith, (2006). “Clustering rules: A comparison of partitioning and hierarchical clustering algorithms”, Journal of Mathematical Modelling and Algorithms, vol. 5, pp. 475–504. [22] E. Martin, K. Hans-Peter, J. Sander, X. Xu, (1996). “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise,” Proceedings of the Second International Conference on Knowledge Discovery and Data Mining(KDD-96). [23] H. Kriegel, P. Kroger, J. Sander, A. Zimek, (2011). “Density-based clustering”. [24] McInnes et al, (2017), “Hierarchical density based clustering”, Journal of Open Source Software, vol.2, no.11, pp. 205. [25] X. Xu, M. Ester, H. Kriegel, J. Sander, (1998). “A distribution-based clustering algorithm for mining in large spatial databases”, Proceedings of the Fourteenth International Conference on Data Engineering, pp. 324-331. [26] M. Bendechache, M. Kechadi, (2018). “Distributed Clustering Algorithm for Spatial Data mining”, Ireland: School of Computer Science & Informatics. [27] R. Corizzo, G. Pio, M. Ceci, et al. (2019). “DENCAST: distributed density-based clustering for multi-target regression”, Journal of Big Data, vol.6, no.43. [28] J. B. MacQueen, (1967). “Some methods for classification and analysis of multivariate observations”, in Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, vol.1, pp.281-297. [29] J. A. Hartigan, M. A. Wong, (1979). “Algorithm AS 136: A K-means clustering algorithm”, Journal of the Royal Statistical Society, Series C, vol.28, no.1, pp.100-108. [30] K. L. Wu, Y. J. Lin, (2012). “Kernelized K-means algorithm based on Gaussian kernel”, Advances in Control and Communication, pp 657-664. [31] Y. Zhao, S. Zhang, J. Ma, (2013). “Kernel K-means algorithm for clustering analysis”, Intelligent Computing Theories and Technology. pp. 234-243. [32] I. S. Dhillon, Y. Guan, B. Kulis, (2004). “Kernel K-means, spectral clustering and normalized cuts”, Research Tracker Poster, pp.551-556. [33] N. Ganganath, C. Cheng, and C. K., (2014). “Data clustering with cluster size constraints using a modified K-means algorithm”, Cyber-Enabled Distributed Computing and Knowledge Discovery. [34] P.S. Bradley, K.P. Bennett, A. Demiriz, (2000). “Constrained K-means clustering”, Technical Report MSR-TR-2000-65, Microsoft Research. [35] M. Baranwal and S. M. Salapaka, (2017). “Clustering with capacity and size constraints: A deterministic approach”, ICC. [36] S.Lloyd, (1982). “Least square quantization in PCM,” IEEE Transations on Information Theory, vol.28, no. 2, pp. 129-137. [37] S. Zhu, D. Wang, and T. Li, (2010). “Data clustering with size constraints,” Knowledge-Based Systems, vol. 23, no. 8, pp. 883–889. [38]林育丞 (2019)。《利用資料驅動方法解決汽車服務系統的位區途程問題》。國立政治大學，統計所，臺北。 [39] H. Massatfa, (1992). “An algorithm to maximize the agreement between partitions”, Journal of Classification 9, vol.1, pp.5–15. [40] L. Kaufman and P.J. Rousseeuw, (1987). “Clustering by means of medoids”, Amsterdam: North-Holland. [41] E. Schubert and P. Rousseeuw, (2019). “Faster K-medoids clustering: Improving the PAM, CLARA, and CLARANS algorithms”, SISAP 2019: Similarity Search and Applications, pp. 171-187. [42] C. Lemarecha, (2012). “Cauchy and the gradient method”, Documenta Mathematica Extra Volume ISMP, pp. 251-254. [43] E. Polak, (1997). “Optimization : Algorithms and consistent approximations”, New York: Springer-Verlag. [44] COIN-OR/SYMPHONY, Retrieved 2006, from: https://github.com/coinor/SYMPHONY [45] Greenberg, (1997). “Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method.”, University of Colorado at Denver. [46] A. Arias, J. D. Sanchez, and M. Granada, (2018). “Integrated planning of electric vehicles routing and charging stations location considering transportation networks and power distribution systems”, International Journal of Industrial Engineering Computations, vol. 9, no. 4, pp. 535-550. [47] R. T. Berger, C. R. Coullard, and M. S. Daskin, (2017). “Location-routing problems with distance constraints”, Transportation Science, vol. 41, pp. 29-43. [48] T.W. Chien, (1993). “Heuristic procedures for practical-sized uncapacitated location-capacitated routing problems”, Decision Sciences, vol.24, pp.995-1021. [49] J. Hof, M. Schneider, and D. Goeke, (2017). “Solving the battery swap station location-routing problem with capacitated electric vehicles using an AVNS algorithm for vehicle-routing problems with intermediate stops”, Transportation Research Part B Methodological, vol.97, pp.102-112. [50] Y. C. Hung and G. Michailidis, (2015). “Optimal routing for electric vehicle service systems”, European Journal of Operational Research, vol. 247, no.2, pp.515- 524. [51] J. Paz, M. Granada-Echeverri, and J. Escobar, (2018). “The multi-depot electric vehicle location routing problem with time windows”, International Journal of Industrial Engineering Computations, vol.9, no.1, pp. 123-136. [52] J. Yang and H. Sun, (2015). “Battery swap station location-routing problem with capacitated electric vehicles”, Computers and Operations Research, vol. 55, no. C, pp. 217-232. [53] L. Wang and Y. B. Song, (2015). “Multiple charging station location-routing problem with time window of electric vehicle”, Journal of Engineering Science and Technology Review, vol. 8, no. 5, pp. 190-201. [54] D. Efthmiou, K. Chrysostomou, M. Morfoulaki, and G. Aifantopoulou, (2017). “Electric vehicles charging infrastructure location: a genetic algorithm approach”, European Transport Research Review, vol.9, no.27. [55] Q. Kong, M. Fowler, E. Entchev, H. Ribberink, and R. McCallum, (2018). “The role of charging infrastructure in electric vehicle implementation within smart grids”, Energies, vol.11, no.3362. [56] S. Deb, K. Kalita, and P. Mahanta, (2018). “Impact of electric vehicle charging station load on distribution network,” Energies, vol. 11, no. 178. [57] W. Yuan, J. Huang, Y. Jun, and A. Zhang, (2017). “Competitive charging station pricing for plug-in electric vehicles,” IEEE Transactions on Smart Grid, vol. 8, no. 2, pp.627-639. [58] Y. Marinakis, (2008). “Location routing problem. In: Floudas C., Pardalos P. (eds) encyclopedia of optimization.”, Boston, MA, USA: Springer.
Description:	碩士國立政治大學統計學系 107354014
Source URI:	http://thesis.lib.nccu.edu.tw/record/#G0107354014
Data Type:	thesis
DOI:	10.6814/NCCU202000924
Appears in Collections:	[Department of Statistics] Theses

Files in This Item:

File	Description	Size	Format
401401.pdf		2540Kb	Adobe PDF2	15	View/Open

All items in 政大典藏 are protected by copyright, with all rights reserved.

社群 sharing

著作權政策宣告 Copyright Announcement

1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.

DSpace Software Copyright © 2002-2004 MIT & Hewlett-Packard / Enhanced by NTU Library IR team Copyright © - Feedback