English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  Items with full text/Total items : 94986/125531 (76%)
Visitors : 30960826      Online Users : 231
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version
    政大機構典藏 > 商學院 > 統計學系 > 學位論文 >  Item 140.119/130956
    Please use this identifier to cite or link to this item: http://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:[統計學系] 學位論文

    Files in This Item:

    File Description SizeFormat
    401401.pdf2540KbAdobe PDF0View/Open


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


    社群 sharing

    著作權政策宣告
    1.本網站之數位內容為國立政治大學所收錄之機構典藏,無償提供學術研究與公眾教育等公益性使用,惟仍請適度,合理使用本網站之內容,以尊重著作權人之權益。商業上之利用,則請先取得著作權人之授權。
    2.本網站之製作,已盡力防止侵害著作權人之權益,如仍發現本網站之數位內容有侵害著作權人權益情事者,請權利人通知本網站維護人員(nccur@nccu.edu.tw),維護人員將立即採取移除該數位著作等補救措施。
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback