支持向量群聚演算法因為可將資料以任意形狀輪廓來呈現群聚結果之特殊表現，在理論發展和實際應用上已經被廣泛地研究。支持向量群聚演算法包含三個主要的步驟: 1) 藉由解最佳化對偶問題來找到ㄧ個超球體、2) 將資料點根據群聚的結果作正確地歸類分配、以及3)藉由調整核心函數的參數來找到一個令人滿意的群聚結果。由於這三個步驟的限制使得支持向量群聚演算法在處理大量資料上變得沒有效率。根據上述的問題，本論文首先提出一有效率的資料前處理方法消除訓練資料中不重要的資料，並且不會影響到最後的群聚架構。由於資料量的減少，支持向量群聚演算法在解最佳化問題與群聚歸屬分配的運算負擔也會大幅降低。接著，最佳參數搜尋機制亦被提出來搜尋支持向量群聚演算法中的核心函數之參數與拉式函數中之鬆弛邊界常數的最佳數值。此搜尋機制能以較少的執行次數獲得支持向量群聚演算法的最佳群聚架構。最後，在實際應用中，支持向量群聚演算法將用來做音樂情緒的分類。音樂情緒的分類程序包含特徵擷取、特徵選擇、特徵轉換與分類方法，每一個處理程序都有其不可或缺的重要性。透過基準資料與實際應用之電腦模擬，成功地驗證本論文所提出方法的有效性。

Support vector clustering (SVC) has been widely researched in both theoretical development and practical applications due to its outstanding features—arbitrary-shaped cluster representations. SVC involves three main steps: 1) finding the hyper-sphere by solving the Wolfe dual optimization problem, 2) identifying the clusters by labeling the data points with cluster labels, and 3) searching a satisfactory clustering outcome by tuning kernel parameters. These three steps make using SVC to process large datasets inefficient and time-consuming. Based on the above problems, an efficient data preprocessing procedure is first proposed to eliminate insignificant data points from training datasets without significantly affecting the final cluster configuration. Since the size of dataset is reduced, the computational burden for solving the optimization problem as well as cluster labeling can be greatly decreased. Next, an optimal parameter search method is proposed to find the suitable parameter of kernel functions and soft-margin constant of Lagrangian functions of SVC. This dissertation enables SVC to identify optimal cluster configurations with a less number of executions. The applicability of the proposed approach to real-world applications is validated through music emotion classification problems. The classification process of the music samples includes feature extraction, features selection, feature transformation, and classification. Each of these processes possesses its own significant and plays an important role in music emotion classification. Finally, the effectiveness of the proposed approach is successfully validated by computer simulations on benchmark datasets and real-world applications.

[1]M. Aizerman, E. Braverman, and L. Rozonoer, “Theoretical foundations of the potential function method in pattern recognition learning,” Automation and Remote Control, vol. 25, pp. 821–837, 1964.
[2] M. Ankerst, M. Breunig, H. P. Kriegel, and J. Sander, “OPTICS: Ordering points to identify the clustering structure,” in Proceedings of ACM SIGMOD International Conference on Management of Data, 1999, pp.49–60.
[3] L. L. Balkwill and W. F. Thompson, “A cross-cultural investigation of the perception of emotion in music: Psychophysical and cultural cues,” Music Perception, vol. 17, pp. 43–64, 1999.
[4] T. Ban and S. Abe, “Spatially chunking support vector cluster algorithm,” in Proceedings of International Joint Conference on Neural Networks, vol. 1, 2004, pp. 413–418.
[5] A. Ben-Hur, D. Horn, H. T. Siegelmann, and V. Vapnik, “A support vector clustering method,” in Proceedings of International Conference on Pattern Recognition, vol. 2, 2000, pp. 724–727.
[6] A. Ben-Hur, D. Horn, H. T. Siegelmann, and V. Vapnik, “Support vector clustering,” Journal of Machine Learning Research, vol. 2, pp. 125–137, 2001.
[7] K. P. Bennett, S. Wu, and L. Auslender, “On support vector decision trees for database marketing,” in Proceedings of IEEE International Joint Conference on Neural Networks, vol. 2, 1999, pp. 904–909.
[8] A. M. Bensaid, L. O. Hall, J. C. Bezdek, L. P. Clarke, M. L. Silbiger, J. A. Arrington, and R. F. Murtagh, “Validity-guided (re)clustering with applications to image segmentation,” IEEE Transactions on Fuzzy Systems, vol. 4, no. 2, pp. 112–123, 1996.
[9] J. C. Bezdek, “Cluster validity with fuzzy sets,” Journal of Cybernetics, vol. 3, no. 3, pp. 58–72, 1974.
[10] J. C. Bezdek, “Numerical taxonomy with fuzzy sets,” Journal of Mathematical Biology, vol. 1, no. 1, pp. 57–71, 1974.
[11] J. C. Bezdek and N. R. Pal, “Some new indexes of cluster validity,” IEEE Transactions on Systems, Man, and Cybernetics—Part B, vol. 28, pp. 301–315, 1998.
[12] E. Bigand, S. Vieillard, F. Madurell, J. Marozeau, and A. Dacquet, “Multidimensional scaling of emotional responses to music: The effect of musical expertise and of the duration of the excerpts,” Cognition and Emotion, vol. 19, no. 8, pp.1113–1139, 2005.
[13] C. Blake, E. Keogh, and C. Merz, UCI Repository of Machine Learning Databases. Irvine, CA: Department of Information and Computer Sciences, University of California, 1998. [Online]. Available: http://www.ics.uci.edu/~mlearn/MLRepository.html
[14] D. Cabrera, “Psysound: A computer program for psychoacoustical analysis,” in Proceedings of Australian Acoustic Society Conference, 1999, pp. 47–54. [Online]. Available: http://www.psysound.org
[15] F. Camastra and A. Verri, “A novel kernel method for clustering,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 27, no. 5, pp. 801–805, 2005.
[16] C. C. Chang and C. J. Lin, LIBSVM: A Library for Support Vector Machines, 2001. [Online]. Available: http://www.csie.ntu.edu.tw/~cjlin/libsvm/index.html
[17] M. S. Chen, J. W. Han, and P. S. Yu, “Data mining: An overview from a database perspective,” IEEE Transactions on Knowledge and Data Engineering, vol. 8, no. 6, pp. 866–883, 1996.
[18] J. C. Chiang and J. S. Wang, “A validity-guided support vector clustering algorithm for identification of optimal cluster configuration,” in Proceeding of IEEE International Conference on Systems, Man, and Cybernetics, 2004, pp. 3613–3618.
[19] J. H. Chiang and P. Y. Hao, “A new kernel-based fuzzy clustering approach: Support vector clustering with cell growing,” IEEE Transactions on Fuzzy Systems, vol. 11, no. 4, pp. 518–527, 2003.
[20] E. K. P. Chong and S. H. Zak, An Introduction to Optimization. Second Edition, New York, NY: John Wiley & Sons, 2001.
[21] C. H. Chou, M. C. Su, and E. Lai, “A new cluster validity measure for clusters with different densities,” in Proceedings of IASTED International Conference on Intelligent Systems and Control, 2003, pp. 276–281.
[22] W. S. Chung, T. B. Trafalis, and L. Gruenwald, “Support vector clustering for web usage mining,” in Proceeding of Intelligent Engineering Systems Through Artificial Neural Networks, vol. 12, 2002, pp. 385–390.
[23] W. S. Cleveland, “Robust locally weighted regression and smoothing scatter plots,” Journal of the American Statistical Association, vol. 74, pp. 829–836, 1979.
[24] Concertina Connection Inc., Basic Finger Articulation. [Online]. Available: http://www.concertinaconnection.com/basic%20articulation.htm
[25] C. Cortes and V. Vapnik, “Support-vector network,” Machine Learning, vol. 20, no. 3, pp. 273–297, 1995.
[26] R. G. Crowder, “Perception of the major/minor distinction I: Historical and theoretical foundations,” Psychomusicology, vol. 4, pp. 3–12, 1984.
[27] R. G. Crowder, “Perception of the major/minor distinction III: Hedonic, music, and affective discriminations,” Bulletin of the Psychonomic Society, vol. 23, pp. 314–316, 1985.
[28] M. Daszykowski, B. Walczak, and D. L. Massart, “Looking for natural patterns in data Part 1: Density-based approach,” Chemometrics and Intelligent Laboratory Systems, vol. 56, pp. 83–92, 2001.
[29] M. Daszykowski, B. Walczak, and D. L. Massart, “Looking for natural patterns in analytical data II: Tracking local density with OPTICS,” Journal of Chemical Information and Computer Sciences, vol. 42, no. 3, pp. 500–507, 2002.
[30] D. L. Davies and D. W. Bouldin, “A cluster separation measure,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-1, no. 2, pp. 224–227, 1979.
[31] S. Davies, “Philosophical perspectives on music’s expressiveness,” in Music and Emotion: Theory and Research, P. N. Juslin and J. A. Sloboda, Ed., New York: Oxford University Press, 2001, pp. 23–44.
[32] J. C. Dunn, “A fuzzy relative of the ISODATA process and its use in detecting compact well-separation clusters,” Journal of Cybernetics, vol. 3, no. 3, pp. 32–57, 1974.
[33] L. Ertz, M. Steinbach, and V. Kumar, “Finding clusters of different sizes, shapes, and densities in noisy, high dimensional data,” in Proceedings of SIAM International Conference on Data Mining, 2003, pp. 1–12.
[34] M. Ester, H. P. Kriegel, J. Sander, and X. Xu, “A density-based algorithm for discovering clusters in large spatial databases with noise,” in Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, 1996, pp. 226–231.
[35] L. A. Feldman, “Variations in the circumplex structure of mood,” Personality and Social Psychology Bulletin, vol. 21, no. 8, pp. 806–817, 1995.
[36] Y. Feng, Y. Zhuang, and Y. Pan, “Popular music retrieval by detecting mood,” in Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2003, pp. 375–376.
[37] R. Fisher, “The use of multiple measurements in taxonomic problems,” Annals of Eugenics, vol. 7, no. 2, pp. 179–188, 1936.
[38] K. Fukunaga, Introduction to Statistical Pattern Recognition. Academic Press, 1990.
[39] Y. Fukuyama and M. Sugeno, “A new method of choosing the number of clusters for the fuzzy c-means method,” in Proceedings of the 5th Fuzzy Systems Symposium, 1989, pp. 247–250.
[40] A. Gabrielsson and E. Lindstrm, “The influence of musical structure on emotional expression,” in Music and Emotion: Theory and Research, P. N. Juslin and J. A. Sloboda, Ed., New York: Oxford University Press, 2001, pp. 223–248.
[41] S. Guha, R. Rastogi, and K. Shim, “CURE: An efficient clustering algorithms for large databases,” in Proceedings of ACM SIGMOD International Conference on Management of Data, 1998, pp.73–84.
[42] S. Guha, R. Rastogi, and K. Shim, “ROCK: A robust clustering algorithms for categorical attributes,” in Proceedings of IEEE Conference on Data Engineering, 1999, pp.512–521.
[43] I. Guyon, J. Weston, S. Barnhill, and V. Vapnik, “Gene selection for cancer classification using support vector machines,” Machine Learning, vol. 46, pp. 389–422, 2002.
[44] K. Henver, “Experimental studies of the elements of expression in music,” American Journal of Psychology, vol. 48, no. 2, pp. 246–268, 1936.
[45] K. Henver, “The affective value of pitch and tempo in music,” American Journal of Psychology, vol. 49, pp. 621–630, 1937.
[46] C. W. Hsu, C. C. Chang, and C. J. Lin, A Practical Guide to Support Vector Classification, 2003. [Online]. Available: http://www.csie.ntu.edu.tw/~cjlin/papers.html
[47] D. Huron, “Perceptual and cognitive applications in music information retrieval,” in Proceedings of International Symposium Music Information Retrieval, 2000, pp, 105–110.
[48] J. E. Jackson, A User's Guide to Principal Components. John Wiley and Sons, 1991.
[49] R. A. Jarvis and E. A. Patrick, “Clustering using a similarity measure based on shared nearest neighbors,” IEEE Transactions on Computers, vol. C-22, no.11, pp. 1025–1034, 1973.
[50] H. Joguchi and M. Tanaka, “On the support vector machine with the kernel of the q-Normal distribution,” in Proceedings of International Technical Conf. Circuits/Systems, Computers and Communications, vol. 2, 2002, pp. 983–986.
[51] P. N. Juslin and J. A. Sloboda, Music and Emotion: Theory and Research. New York, NY: Oxford University Press, 2001.
[52] G. Karypis, E. H. Han, and V. Kumar, “Chameleon: A hierarchical clustering algorithm using dynamic modeling,” Computer, vol. 32, no. 8, pp. 68–75, 1999.
[53] D. W. Kim, K. H. Lee, and D. Lee, “Fuzzy cluster validation index based on inter-cluster proximity,” Pattern Recognition Letters, vol. 24, no. 15, pp. 2561–2574, 2003.
[54] M. D. Korhonen, D. A. Clausi, and M. Jernigan, “Modeling emotional content of music using system identification,” IEEE Transactions on Systems, Man, and Cybernetics—Part B, vol. 36, no. 3, pp. 588–599, 2006.
[55] C. L. Krumhansl, “Why is musical timbre so hard to understand?” in Structure and Perception of Electroacoustic Sound and Music, S. Nielsen and O. Olsson, Ed., Elsevier, Amsterdam, University Press, 1989, pp. 43–53.
[56] P. J. Lang, M. M. Bradley, and B. N. Cuthbert, “Technical manual and affective ratings,” in Proceedings of International Affective Pictures System, 1997, pp.1–5.
[57] O. Lartillot, P. Toiviainen, and T. Eerola, MIRtoolbox: An Integrated Set of Functions Written in Matlab, Finnish Center of Excellence in Interdisciplinary Music Research, University of Jyvaskyla, Finland. [Online]. Available: http://www.jyu.fi/hum/laitokset/musiikki/en/research/coe/materials/mirtoolbox
[58] J. Lee and D. Lee, “An improved cluster labeling method for support vector clustering,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 27, no. 3, pp. 461–464, 2005.
[59] C. C Liu, Y. H. Yang, P. H. Wu, and H. H. Chen, “Detecting and classifying emotion in popular music,” in Proceedings of the 7th International Conference on Computer Vision, Pattern Recognition and Image Processing, 2006, pp. 996–999.
[60] L. Lu, D. Liu, and H. J. Zhang, “Automatic mood detection and tracking of music audio signals,” IEEE Transactions on Audio, Speech, and Language Processing, vol. 14, no. 1, pp. 5–18, 2006.
[61] L. Lundqvist, F. Carlsson, and P. Hilmersson, “Emotional response to music: Experience, expression, and philology,” Psychology of Music, pp.1–30, 2008.
[62] A. M. Martinez and A. C. Kak, “PCA versus LDA,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 23, no. 2, pp. 228–233, 2001.
[63] A. Padova and R. Santoboni, “Influence of timbre on emotions and recognition memory for music,” in Proceedings of Interdisciplinary Musicology Conference, 2005, pp. 1–8.
[64] E. Rapoport, “Emotional expression code in opera and lied singing,” Journal of New Music Research, vol. 25, pp. 109–149, 1996.
[65] H. S. Rhee and K. W. Oh, “A validity measure for fuzzy clustering and its use in selecting optimal number of clusters,” in Proceedings of IEEE International Conference on Fuzzy Systems, vol. 2, 1996, pp. 1020–1025.
[66] M. G. Rigg, “The mood effects of music: A comparison of data from four investigators,” Journal of Psychology, vol. 58, pp. 427–438, 1964.
[67] J. A. Rusesell, “A circumplex model of affect,” Journal of Personality and Social Psychology, vol. 39, no. 6, pp. 1161–1178, 1980.
[68] J. Saketha and S. K. Shevade, “An efficient clustering scheme using support vector methods,” Pattern Recognition, vol. 39, no. 8, pp. 1473–1480, 2006.
[69] E. Schubert, “Measurement and time series analysis of emotion in music,” Ph.D. dissertation, University of New South Wales, Sydney, 1999.
[70] E. Schubert, “Continuous measurement of self-report emotional response to music,” in Music and Emotion: Theory and Research, P. N. Juslin and J. A. Sloboda, Ed., New York: Oxford University Press, 2001, pp. 393–414.
[71] J. A. Sloboda and P. N. Juslin, “Psychological perspectives on music and emotion,” in Music and Emotion: Theory and Research, P. N. Juslin and J. A. Sloboda, Ed., New York: Oxford University Press, 2001, pp. 71–104.
[72] M. C. Su, A New Index of Cluster Validity, 2004. [Online]. Available: http://www.cs.missouri.edu/~skubic/8820/ClusterValid.pdf
[73] B. Y. Sun and D. S. Huang, “Support vector clustering for multiclass classification problems,” in Proceedings of IEEE Congress Evolutionary Computation, vol. 2, 2003, pp. 1480–1485.
[74] P. Synak and A. Wieczorkowska, “Some issues on detecting emotions in music,” Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, pp. 314–322, 2005.
[75] J. F. Thayer, “Multiple indicators of affective response to music,” Ph.D. dissertation, New York University, New York, 1986.
[76] G. Tzanetakis and P. Cook, “Musical genre classification of audio signals,” IEEE Transactions on Speech and Audio Processing, vol. 10, no.5, pp. 293–302, 2002. [Online]. Available: http://marsyas.sness.net
[77] L. Wang, “Feature selection with kernel class separability,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30, no. 9, pp. 1534–1546, 2008.
[78] X. L. Xie and G. Beni, “A validity measure for fuzzy clustering,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, no. 8, pp. 841–847, 1991.
[79] C. S. Xu, N. C. Maddage, and X. Shao, “Automatic music classification and summarization,” IEEE Transactions on Speech and Audio Processing, vol. 13, no. 3, pp. 441–450, 2005.
[80] D. Yang and W. Lee, “Disambiguating music emotion using software agents,” in Proceedings of International Conference on Music Information Retrieval, 2004, pp. 52–58.
[81] J. Yang, V. E. Castro, and S. K. Chalup, “Support vector clustering through proximity graph modeling,” in Proceeding of the 9th International Conference on Neural Information Processing, vol. 2, 2002, pp. 898–903.
[82] J. H. Yang and I. Lee, “Cluster validity through graph-based boundary analysis,” in Proceedings of International Conference on Information and Knowledge Engineering, 2004, pp. 204–210.
[83] Y. H. Yang, C. C. Liu, and H. H. Chen, “Music emotion classification: A fuzzy approach,” ACM Multimedia, 2006, pp. 81–84.
[84] Y. H. Yang, Y. C. Lin, Y. F. Su, and H. H. Chen, “Music emotion classification: A regression approach,” in Proceedings of IEEE International Conference on Multimedia and Expo, 2007, pp. 208–211.
[85] Y. H. Yang, Y. F. Su, Y. C. Lin, and H. H. Chen, “Music emotion recognition: The role of individuality,” ACM International Workshop on Human-Centered Multimedia, 2007, pp. 13–21.
[86] Y. H. Yang, Y. C. Lin, Y. F. Su, and H. H. Chen, “A Regression approach to music emotion recognition,” IEEE Transactions on Audio, Speech, Language Process., vol. 16, no. 2, pp. 448–457, 2008.
[87] O. Yilmaz, E. K. Achenie, and R. Srivastava, “Systematic tuning of parameters in support vector clustering,” Mathematical Bioscience, vol. 205, pp.252–270, 2007.
[88] T. Zhang, R. Ramakrishnan, and M. Linvy, “BIRCH: An efficient data clustering method for very large databases,” in Proceedings of ACM SIGMOD International Conference on Management of Data, 1996, pp. 103–114.