臺灣博碩士論文加值系統

分群演算法已經廣泛被使用在圖形識別、資料探勘、機器學習等相關領域，是屬於非監督式，主要是可依資料特性劃分成群，相似的聚成同一群，不相似的歸類成其他群，一般來說，分群的方法有分成劃分法、階層法、密度法、格子法、模型法，這裡我們主要研究劃分法。K-means (KM) 分群演算法是一種硬式分群，把資料明確的劃分，只有屬於特定群集，然而這樣的劃分有些過於明確。Bezdek首先提出KM的改良式演算法fuzzy c-means (FCM) 分群演算法，是應用了模糊理論的概念，使資料在也不是屬於特定群集，而是有歸屬程度來表現。在FCM分群演算法有容易受雜訊與離異點影響的問題，故有很多學者研究如何去克服此問題，著名的有possibilistic c-means (PCM) 分群演算法、fuzzy possibilistic c-means (FPCM)分群演算法和possibilistic fuzzy c-means (PFCM) 分群演算法等都是針對FCM分群演算法容易受雜訊與離異點影響所提出來的改善演算法。在研究符號區間資料的分群，最著名的interval FCM (IFCM) 對於符號區間資料分群被提出，但仍然有雜訊與離異點的影響，因此我們提出了interval PCM (IPCM) 分群演算法、interval FPCM (IFPCM) 分群演算法、interval PFCM (IPFCM) 分群演算法。
在基於粗糙集廣義FCM 分群演算法被提出，他是一種結合粗糙集與模糊集，應用在分群資料的不明確、模糊劃分，可以有效的處理資料重疊劃分，考慮了它的優點，應用在我們的演算法中，我們更進一步的改良為rough IPCM (RIPCM) 分群演算法、rough IFPCM (RIFPCM) 分群演算法、rough IPFCM (RIPFCM)分群演算法。最後，我們把部份新的演算法實現於智慧型手機。

Clustering algorithms have been widely used such as pattern recognition, data mining and machine learning, etc. It is an unsupervised classification that is divided into groups according to data sets. That is, the data sets of similarity partition belong to the same group; otherwise data sets divide other groups in the clustering algorithms. In general, clustering methods are divided into partitioning-based, hierarchical, density-based, grid-based and model-based. In this thesis, we focus on the partitioning-based approach. K-means (KM) clustering algorithm is famous hard clustering that also belongs to partitioning-based. It is definitely to partition into group that only belonging to a particular group; however, the partition is not suitable to deal with fuzzy situation. Bezdek firstly proposed an improved KM clustering algorithm; namely, fuzzy c-means (FCM) clustering algorithm. The FCM clustering algorithm applied fuzzy theory concept of which the data sets not belong to specific group but membership have to representation. In the FCM clustering algorithm is difficult to deal with data sets with noise and outliers. Therefore, the many papers proposed many approaches; namely, possiblilistic c-means (PCM) clustering algorithm, fuzzy possiblilistic c-means (FPCM) clustering algorithm and possiblilistic fuzzy c-means (PFCM) clustering algorithm to overcome this problem. On the other hand, the interval FCM (IFCM) clustering method was proposed to deal with symbolic interval data. However, it still has noisy and outliers problems. Hence, we propose interval PCM (IPCM) clustering algorithm, interval FPCM (IFPCM) clustering algorithm and interval PFCM (IPFCM) clustering algorithm to overcome the IFCM clustering algorithm for the symbolic interval data clustering in noisy and outlier environments.
In order to efficient handling of overlapping partitions problem the rough set based generalized FCM algorithm was proposed. This approach includes rough set and fuzzy set of which the concept of lower and upper approximations of rough sets deals with uncertainty, vagueness, and incompleteness in class definition. Therefore, we consider advantage of rough set. Hence, we combine the rough set with our propose algorithm for application. That is, we proposed rough IPCM (RIPCM) clustering algorithm, rough IFPCM (RIFPCM) clustering algorithm and rough IPFCM (RIPFCM) clustering algorithm that can to efficient handling of overlapping partitions problem for symbolic interval data. Finally, we also implement the proposed algorithms to smart phone.

CONTENTS
ABSTRACT...............i
中文摘要.................iii
ACKNOWLEDGEMENTS........v
LIST OF TABLES..........viii
LIST OF FIGURES..........ix
CHAPTER 1 INTRODUCTION.............1
1.1 Review of Machine Learning...........1
1.2 Review of Clustering Algorithm.........1
1.3 Review of Symbolic Data Analysis...........2
1.4 Motivations and Contributions.........3
1.5 Organization of this Thesis..........3
CHAPTER 2 PRELIMINARIES.............5
2.1 Interval Distance Measure..........5
2.2 Optimization Theory...........5
2.3 Clustering Algorithm..........6
2.3.1 Fuzzy C-Means Clustering Algorithm..........7
2.3.2 Possibilistic C-Means Clustering Algorithm.........7
2.3.3 Fuzzy Possibilistic C-Means Clustering Algorithm....8
2.3.4 Possibilistic Fuzzy C-Means Clustering Algorithm......9
2.4 Rough Sets Theory.........10
CHAPTER 3 INTERVAL POSSIBILISTIC FUZZY C-MEANS CLUSTERING ALGORITHM.........13
3.1 Interval Possibilistic C-Means Clustering Algorithm.......13
3.2 Interval Fuzzy Possibilistic C-Means Clustering Algorithm.......17
3.3 Interval Possibilistic Fuzzy C-Means Clustering Algorithm.......23
3.4 Simulation Results..........29
3.5 Concluding Remarks.......57
CHAPTER 4 ROUGH INTERVAL POSSIBILISTIC FUZZY C-MEANS CLUSTERING ALGORITHM.........59
4.1 Rough Interval Possibilistic C-Means Clustering Algorithm........59
4.2 Rough Interval Fuzzy Possibilistic C-Means Clustering Algorithm.........67
4.3 Rough Interval Possibilistic Fuzzy C-Means Clustering Algorithm........77
4.4 Simulation Results.......87
4.5 Concluding Remarks..........102
CHAPTER 5 SMART PHONE IMPLEMENT.........104
5.1 Introduction to Smart Phone......104
5.2 Windows Mobile Systems Enviroment for Smart Phone.......105
5.3 Window form and Pseudo Code of the Proposed Algorithm........106
5.4 Experimental Results........109
5.5 Concluding Remarks.......113
CHAPTER 6 CONCLUSIONS........114
REFERENCES............115
EXTENDED ABSTRACT........119
CURRICULUM VITAE.............122

[1]C. Peterson and M. Ringne’r, “Analyzing Tumor Gene Expression Profiles,” Artificial Intelligence in Medicine, vol. 28, no. 1, pp. 59-74, May 2003.
[2]汪昭緯，應用分群技術偵測信用卡異常交易之研究，國立中央大學，資訊管理研究所，碩士論文，2002。
[3]MacKay David, “Chapter 20. An Example Inference Task: Clustering,” Information Theory, Inference and Learning Algorithms, Cambridge University Press, pp.284–292, 2003.
[4]T. Velmurugan and T. Santhanam, “Computational Complexity between K-Means and K-Medoids Clustering Algorithms for Normal and Uniform Distributions of Data Points,” Journal of Computer Science, vol 6, no 3, pp. 363-368, 2010.
[5]Raymond T. Ng and Jiawei Han, “CLARANS: a method for clustering objects for spatial data mining,” IEEE Transactions on Knowledge and Data Engineering, vol. 14, no. 5, pp. 1003-1016, 2002.
[6]Sudipto Guha, Rajeev Rastogi and Kyuseok Shim, “Cure: an efficient clustering algorithm for large databases,” Information Systems, vol. 26, no. 1, pp. 35-58, 2001.
[7]Sudipto Guha, Rajeev Rastogi and Kyuseok Shim, “Rock: A robust clustering algorithm for categorical attributes,” Information Systems, vol. 25, no. 5, pp. 345-366, 2000.
[8]George Karypis, Eui-Hong Han and Vipin Kumar, “Chameleon: Hierarchical Clustering Using Dynamic Modeling,” IEEE Computer, vol. 32, no. 8, pp. 68-75, Aug. 1999.
[9]M. Tekbir and S. Albayrak, “Recursive-Partitioned DBSCAN,” 2010 IEEE 18th Signal Processing and Communications Applications Conference (SIU), pp. 113-116, 2010.
[10]Jun He and Weimin Pan, “A DENCLUE based approach to neuro-fuzzy system modeling,” 2010 2nd International Conference on Advanced Computer Control (ICACC), vol. 4, pp. 42-46, 2010.
[11]M. Ankerst, M. Breunig, H.-P. Kriegel, and J. Sander, “Optics: Ordering Points to Identify the Clustering Structure,” Proc. of the 1999 International Conference on Management of Data, pp. 49-60, 1999.
[12]W. Wang, J. Yang and R. Muntz, “STING: A Statistical Information Grid Approach to Spatial Data Mining,” Proc. of the 23th VLDB Conference, pp. 186-195, 1997.
[13]Xiaoli Li and Min Luo, “An Improved WaveCluster Algorithm Based on ICA,” Wireless Communications, Networking and Mobile Computing, 2009. WiCom ''09. 5th International Conference on, pp. 1-5, 2009.
[14]S.K. Bethi, V.V. Phoha and Y.B. Reddy, "CLIQUE clustering approach to detect denial-of-service attacks," Information Assurance Workshop, 2004. Proceedings from the Fifth Annual IEEE SMC, pp. 447-448, 2004.
[15]D. Fisher, "Improving inference through conceptual clustering," Proceedings of the 1987 AAAI Conferences, AAAI Conference, Seattle Washington, pp. 461–465, 1987.
[16]J Gennari, P. Langley and D. Fisher, “Models of Incremental Concept Formation,” Artificial Intelligence, vol. 40, pp. 11-61, 1989.
[17]J.A.F. Costa and Hujun Yin, "Gradient-based SOM clustering and visualisation methods," The 2010 International Joint Conference on Neural Networks (IJCNN), pp. 1-8, 2010.
[18]L. Billard and E. Diday, “From the statistics of data to the statistics of knowledge: Symbolic data analysis,” Journal of the American Statistical Association, vol 98, pp. 470-487, 2003.
[19]H. H. Bock and E. Diday, Analysis of symbolic data: Exploratory methods for extracting statistical information from complex data, Springer-Verlag, 2000.
[20]Jin-Tsong Jeng, Chen-Chia Chuang and C. W. Tao, “Interval competitive agglomeration clustering algorithm,” Expert Systems with Applications, vol. 37, pp. 6567-6578, 2010.
[21]K. C. Gowda and E. Diday, “Symbolic clustering using a new dissimilarity measure,” Pattern Recognition, vol. 24, pp. 567-578, 1991.
[22]K. C. Gowda and E. Diday, “Symbolic clustering using a new similarity measure,” IEEE Transactions on Systems Man Cybernetic, vol. 22, pp. 368-378, 1992.
[23]K. C. Gowda and T. R. Ravi, “Divisive clustering of symbolic objects using the concepts of both similarity and dissimilarity,” Pattern Recognition, vol. 28, pp. 1277-1282, 1995.
[24]K. C. Gowda and T. R. Ravi, “Agglomerative clustering of symbolic objects using the concepts of both similarity and dissimilarity,” Pattern Recognition Letter, vol. 16, pp. 647-652, 1995.
[25]F. A. T. De Carvalho, R. M. C. R. Souza, M. Chavent, and Y. Lechevallier, “Adaptive Hausdorff distances and dynamic clustering of symbolic data,” Pattern Recognition Letter, vol. 27, pp. 167-179, 2006.
[26]F. A. T. De Carvalho, “Fuzzy c-means clustering methods for symbolic interval data,” Pattern Recognition Letter, vol. 28, pp.423-437, 2007.
[27]Nello Cristianini and John Shawe-Taylor, An Introduction to Support Vector Machines and Other Kernel-based Learning Methods, Cambridge University Press, 2000.
[28]J. C. Bezdek, “A convergence theorem for the fuzzy ISODATA clustering algorithms,” IEEE Trans. on Pattern Analysis and Machine Intelligence, pp. 1-8, 1980.
[29]R. Krishnapuram and J. M. Keller, “A possibilistic approach to clustering,” IEEE Transactions on Fuzzy Systems, vol. 1, pp. 98-110, 1993.
[30]N. R. Pal, K. Pal and J. C. Bezdek, “Amixed c-means clustering model,” Proc. Of 1997 IEEE Int. Conf. on Fuzzy Systems, vol. 1, pp. 11-21, 1997.
[31]N. R. Pal, K. Pal, J. M Keller and J. C. Bezdek, “A possibilistic fuzzy c-means clustering algorithm,” IEEE Transactions on Fuzzy Systems, vol. 13, pp. 517-530, 2005.
[32]Z. Pawlak, Rough Sets: Theoretical Aspects of Reasoning about Data, Dordrecht, The Netherlands: Kluwer, 1991.
[33]P. Maji, and S. K. Pal, “Rough Set Based Generalized Fuzzy C-means Algorithm and Quantitative Indices,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 37, pp. 1529-1540, 2007.
[34]维基百科，“Android” [Online]. Available:http://zh.wikipedia.org/wiki/Android.
[35]Open Handset Alliance, “Android Overview” [Online] Available:http://www.openhandsetalliance.com/android_overview.html.
[36]维基百科，“iOS” [Online]. Available: http://zh.wikipedia.org/wiki/IOS.
[37]维基百科，“Symbian_OS” [Online]. Available: http://zh.wikipedia.org/wiki/Symbian_OS.
[38]廖柄火侖，支持向量機於智慧家庭之應用，國立虎尾科技大學，資訊工程研究所，碩士論文，2010。
[39]廖彥博，胡硯，馬騏，Windows Mobile 平台應用與開發，文魁資訊，2007。
[40]Jin-Tsong Jeng, Chen-Chia Chuang, Chih-Cheng Tseng and Chang-Jung Juan "Robust interval competitive agglomeration clustering algorithm with outliers," International Journal of Fuzzy Systems, vol. 12, no. 3, pp. 227-236, 2010.
[41]Shun-Feng Su, Chen-Chia Chuang, C. W. Tao, Jin-Tsong Jeng, Chih-Ching Hsiao, “Radial basis function networks with linear interval regression weights for symbolic interval data,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 42, no. 1, pp. 69-80, 2012.