臺灣博碩士論文加值系統

本計畫主要是提出萬用演算法為基礎的可能性多變量模糊加權c-平均數(Possibilistic multivariate fuzzy weighted c-means；PMFWCM) 演算法來分群混合型資料集。原本PMFWCM演算法是使用於數值型資料集上，為了將其應用在市場區隔的實際資料集上，該模型需要進行更新。本論文應用了基因演算法(GA)、粒子群最佳化演算法(PSO)及正弦餘弦演算法(SCA) 此三個萬用演算法和PMFWCM演算法進行結合，目的在於使PMFWCM演算法得出更佳的結果及更穩定地運作。為了能明確為真實世界的資料作分群，本論文提出的演算法先以標竿資料集做驗證。實驗結果顯示SCA-PMFWCM、GA-PMFWCM和PSO-PMFWCM三個演算法皆優於PMFWCM演算法。從案例研究的結果來看，SCA-PMFWCM演算法具有最小的平方誤差和，比起GA-PMFWCM、PSO-PMFWCM和PMFWCM演算法，則具有更短的計算時間。

This study intends to propose the metaheuristic-based possibilistic multivariate fuzzy weighted c-means (PMFWCM) algorithm for clustering mixed dataset. PMFWCM algorithm itself is normally used for numerical dataset. To apply in real dataset in terms of market segmentation, model improvement is need. Thus, there are three meta-heuristics applied, namely genetic algorithm (GA), particle swarm optimization algorithm (PSO) and sine cosine algorithm (SCA). These three algorithms are combined with PMFWCM algorithm. The aim is to give better results for PMFWCM algorithm and make the algorithms more stable. In order to cluster a real-world dataset certainly, the proposed algorithms are verified using benchmark datasets. The experiment results showed that SCA-PMFWCM, GA-PMFWCM and PSO-PMFWCM algorithms are better than PMFWCM algorithm. Moreover, from case study results, SCA-PMFWCM gives the smallest sum of squared error and also has faster computational time than GA-PMFWCM, PSO-PMFWCM, and PMFWCM algorithms.

摘要 ………………………………………………………………………………………i
ABSTRACT ………………………………………………………………………………ii
ACKNOWLEDGEMENTS ………………………………………………………………iii
TABLE OF CONTENTS ………………………………………………………………iv
LIST OF FIGURES ………………………………………………………………………vii
LIST OF TABLES ………………………………………………………………………viii
CHAPTER 1 INTRODUCTION ………………………………………………………1
1.1 Research Background ………………………………………………………………1
1.2 Problem Definition ………………………………………………………………2
1.3 Research Objectives ………………………………………………………………2
1.4 Research Scope and Assumptions ………………………………………………3
1.5 Organization of Thesis ………………………………………………………………3
CHAPTER 2 LITERATURE SURVEY ………………………………………………5
2.1 Data Mining ………………………………………………………………………5
2.2 Data Features ………………………………………………………………………6
2.2.1 Numerical Data ………………………………………………………………6
2.2.2 Categorical Data ………………………………………………………………6
2.2.3 Mixed Data ………………………………………………………………7
2.3 Cluster Analysis ………………………………………………………………7
2.3.1 Overview of Clustering Approaches ………………………………………7
2.3.2 Fuzzy c-means Algorithm based Algorithm……………………………………. 8
2.3.2.1 Fuzzy c-means Algorithm …………………………………………………. 8
2.3.2.2 Multivariate Fuzzy c-means Algorithm ………………………………10
2.3.2.3 Possibilistic Multivariate Fuzzy c-means Algorithm ………………………11
2.3.3 Clustering Approaches for Mixed Attributes ………………………………12
2.3.3.1 Fuzzy k-prototype Algorithm ………………………………………………12
2.3.3.2 Fuzzy c-means Algorithms with Fuzzy p-mode Prototypes ………………13
2.3.3.3 Subspace Clustering ………………………………………………………14
2.4 Meta-heuristics ………………………………………………………………………15
2.4.1 Sine Cosine Algorithm (SCA) ………………………………………………16
2.4.2 Genetic Algorithm (GA) ………………………………………………………16
2.4.3 Particle Swarm Optimization (PSO) ………………………………………17
CHAPTER 3 METHODOLOGY ………………………………………………………18
3.1 Methodology Framework ………………………………………………………18
3.2 Possibilistic Multivariate Fuzzy Weighted c-means (PMFWCM) Algorithm ………19
3.3 Meta-heuristics Based Clustering ………………………………………………20
3.3.1 Sine Cosine Algorithm Based Clustering ………………………………………20
3.3.2 Genetic Algorithm Based Clustering ………………………………………23
3.3.3 Particle Swarm Optimization Algorithm Based Clustering ………………24
CHAPTER 4 COMPUTATIONAL RESULTS ………………………………………25
4.1 Data Sets ………………………………………………………………………25
4.2 Data Preprocessing ………………………………………………………………25
4.3 Parameter Setting ………………………………………………………………26
4.4 Experimental Result and Analysis ………………………………………………34
4.4.1 Computational Results ………………………………………………………34
4.4.2 Statistical Results ………………………………………………………………38
CHAPTER 5 CASE STUDY ………………………………………………………………42
5.1 Market Segmentation ………………………………………………………………42
5.1.1 Problem Description ………………………………………………………42
5.2 Number of Clusters ………………………………………………………………43
5.3 Results and Discussion ………………………………………………………………44
5.3.1 Tuning Parameter ………………………………………………………………44
5.3.2 SSE Results of Proposed Methods ………………………………………44
5.3.3 Clustering Results for Market Segmentation ………………………………47
CHAPTER 6 CONCLUSIONS AND FUTURE WORK ………………………………49
6.1 Conclusions ………………………………………………………………………49
6.2 Contributions ………………………………………………………………………49
6.3 Future Study ………………………………………………………………………49
REFERENCES ………………………………………………………………………50
APPENDIX I GENERAL FACTORIAL DESIGN OF DETERMINING TUNING PARAMETERS FOR SOLVING CLUSTERING ………………………………………52
APPENDIX II DETERMINATION CLUSTER OF PROPOSED ALGORITHM ………74
APPENDIX III QUESTIONNAIRE OF SOFT DRINK CONSUMERS ………………77

GAN, G., MA, C. & WU, J. 2007. Data clustering: theory, algorithms, and applications. SIAM: Society for Industrial and Applied Mathematics.
HAN, J. & KAMBER, M. 2007. Data Mining: Concepts and Techniques. San Francisco, Elsevier Inc.
TAN, P. N., STEINBACH, M. & KUMAR, V. 2017. Introduction to Data Mining. New York, Pearson Education.
JAIN, A. K., MURTY, M. N. & FLYNN, P. J. 1999. Data clustering: a review. ACM Comput. Surv., 31, 264-323.
ANDERBERG, M. R. 1973. Cluster analysis for applications. New York, Academic Press.
HAN. J., KAMBER, M. & PEI, J. 2012. Cluster Analysis: Basic Concepts and Methods. Data Mining (Third Edition). Boston: Morgan Kaufman.
BEZDEK, J. C., EHRLICH, R. & FULL, W. 1984. FCM: The fuzzy c-means clustering algorithm. Computers & Geosciences, Vol. 10, 191-203.
BRUNO, A. P. & RENATA, M. C. R. 2013. A multivariate fuzzy c-means method. Applied Soft Computing, Vol. 13, 1592-1607.
BRUNO, A. P. & RENATA, M. C. R. 2016. Multivariate fuzzy c-means algorithms with weighting. Neurocomputing, Vol. 174, 946-965.
PAL, N. R., PAL, K., KELLER, J. M. & BEZDEK, J. C. 2005. A possibilistic fuzzy c-means clustering algorithm. IEEE Transactions on fuzzy systems, Vol. 13, 517-530.
LUDMILA, H. & STEFAN, C. A Possibilistic multivariate fuzzy c-means clustering algorithm. Scalable Uncertainty Management, 338-344.
JI, J., PANG, W., ZHOU, C., HAN, X. & WANG, Z. 2012. A fuzzy k-prototype clustering algorithm for mixed numeric and categorical data. Knowledge-Based Systems, Vol. 30, 129-135.
LEE, M. & WITOLD, P. 2009. The fuzzy c-means algorithm with fuzzy P-mode prototypes for clustering objects having mixed features. Fuzzy Sets and Systems, Vol. 160, 3590-3600.
JIA, H. & CHEUNG, Y. M. 2017. Subspace clustering of categorical and numerical data with an unknown number of clusters. IEEE Transactions on Neural Networks and Learning Systems, 1-18.
LIU, J., LIAO, X., HUANG, W. & LIAO, X. 2019. Market segmentation: A multiple criteria approach combining preference analysis and segmentation decision. Omega, Vol. 83, 1-13.
HENRIETTE, M. & ULRICH, H. 2014. Stability of market segmentation with cluster analysis - A methodological approach. Food Quality and Preference, Vol. 34, 70-78.
TALBI, E. G. 2009. Population-Based Metaheuristics. Metaheuristics. John Wiley & Sons, Inc.
RANGEL-MERINO, A., LOPEZ-BONILLA, J. L. & MIRANSA, R. L. Y. 2005. Optimization Method Based on Genetic Algorithms. Apeiron, 12.
SEYEDALI, M. 2016. SCA: A Sine Cosine Algorithm for solving optimization problems. Knowledge-Based Systems, 120-133.
SIMGE, E., PAKIZE, E. & BUSRA, O. 2017. Solving Constrained Optimization Problems with Sine-Cosine Algorithm. Periodicals of Engineering and Natural Sciences, Vol. 5, 378-386.
QU, C., ZENG, Z., DAI, J., YI, Z. & HE, W. 2018. A modified sine-cosine algorithm based on neighborhood search and greedy Levy mutation. Hindawi, 1-19.