臺灣博碩士論文加值系統

特徵選擇是由原始特徵空間中挑選一組有用且合適的特徵以便有效地對資料作描述與索引，這項工作對處理分類及分群問題上很重要。然而，當訓練用的資料屬性量大時這卻變的十分困難。此外，當某些屬性(特徵)已被挑選出，則之後所推導出的分類規則將只會由這些屬性所構成，然而，有時我們無法在目前環境下取得這些屬性的數值，則之前推導出的分類規則將無法被利用。在這篇論文中，我們嘗試對屬性分群並從中選取代表的屬性以達到降低屬性數目，且被群組於同一群之屬性亦可輔助日後的分類工作。如同一般對個體的分群，落在同群的屬性彼此會有較高的相似度，而落在不同群的屬性則會有較高的相異度。我們提出三種量度屬性相似度的方法，以及兩個基於這些量度法的屬性分群演算法。第一個稱為最多鄰居優先法，它可依照設定的群數將屬性完成分群。第二個則是基於CAST演算法，它可將屬性群聚成適當的群數，即使無法事先得知屬性的群數。接著，由各群中選出代表的屬性來處理之後的分類工作。我們提出兩個基於屬性分群法的分類演算法，分別改良了基於案例的推理分類法與k-最鄰近分類法。整體而言，利用屬性的分群結果來選擇屬性，除了可降低分類問題的複雜度，當某些被選出的屬性該數値無法得知之時，則可利用屬性取代法的技巧，以同群其他屬性達到近似的推論結果。實驗結果亦證明了所提出的方法之有效性。

Feature selection is to find useful and relevant features from an original feature space to effectively represent and index a given dataset. It is very important to classification and clustering problems, which may be quite difficult to solve when the amount of attributes in a given training data is very large. After feature selection, the rules derived from only the selected features may be hard to use if some values of the selected features cannot be obtained in current environments. In this thesis, we try to select representative features by attribute clustering, and the attributes grouped together in the same clusters can aid the classification work later. Like conventional clustering for objects, the attributes within the same cluster have high similarity, and within different clusters have high dissimilarity. Three similarity measures for a pair of attributes are thus presented. Two attribute clustering algorithms based on the similarity measures are then proposed. The first one, called Most Neighbors First (MNF), clusters the attributes into a pre-defined number of groups. The second one, based on the CAST algorithm, clusters the attributes into an appropriate number of clusters even when the cluster number cannot be obtained in advance. The representative attributes found in the clusters can then be used for classification such that the whole feature space can be greatly reduced. Besides, two classification algorithms based on the proposed attribute clustering approaches are described to solve the problem that some values of the selected features cannot be obtained in current situations. One is based on case-based reasoning and the other is based on the k-nearest-neighbors classifier. By attribute clustering and attribute replacement, some other possible attributes in the same clusters can be used to achieve approximate inference results.

ABSTRACT I
摘要 II
謝誌 III
Contents IV
List of Figures VI
List of Tables VII
CHAPTER 1 Introduction 1
1.1 Background and Motivation 1
1.2 Contributions 4
1.3 Thesis Organization 5
CHAPTER 2 Literature Survey 6
2.1 Feature Selection 6
2.2 Reducts 9
2.3 Relative Dependency 11
2.4 The k-means and the k-medoids Clustering Approaches 12
2.5 Clustering with Unknown Cluster Numbers 14
2.6 Case-Based Reasoning 16
2.7 k-Nearest-Neighbor Classifier 17
CHAPTER 3 Calculation of Attribute Similarity 18
3.1 Attribute Similarity Based on Relative Dependency 18
3.2 Attribute Similarity Based on Majority Sets 19
3.3 Generalized Attribute Similarity Based on Majority Sets 22
CHAPTER 4 Attribute Clustering with Pre-Defined Cluster Numbers 28
4.1 The Basic Concepts of the Proposed Algorithm 28
4.2 The Proposed Algorithm 29
4.3 An Example 32
4.3 Experimental Results 36
CHAPTER 5 Attribute Clustering with Unknown Cluster Numbers 40
5.1 The Basics of the Proposed Algorithm 40
5.2 The Proposed Algorithm 41
5.3 An example 43
CHAPTER 6 Case-Based Reasoning with Attribute Clustering 49
6.1 The Proposed Algorithm 49
6.2 Examples 53
CHAPTER 7 The k-Nearest-Neighbors Classifier with Attribute Clustering 60
7.1 The Proposed Algorithm 60
CHAPTER 8 Conclusions and Future Works 64
References 65

[1]H. Almunallim and T. G. Dieterich, “Learning with many irrelevant features,” The Proceedings of the Ninth National Conference on Artificial Intelligence, 1991, Vol. 2, pp. 547-552.
[2]Q. A. Al-Radaideh, M. N. Sulaiman, M. H. Selamat and H. Ibrahim “Approximate reduct computation by rough sets based attribute weighting,” The Proceedings of the IEEE International Conference on Granular Computing, 2005, Vol. 2, pp. 383-386.
[3]A. Ben-Dor and Z. Yakhini, “Clustering gene expression patterns,” Journal of Computational Biology, 1999, Vol. 6, pp. 281-297.
[4]A. L. Blum and R. L. Rivest, “Training a 3-node neural networks is NP-complete,” Neural Networks, 1992, Vol. 5, pp. 117-127.
[5]A. L. Blum and P. Langley, “Selection of relevant features and examples in machine learning,” Artificial Intelligence, 1997, Vol. 97, pp. 245-271.
[6]H. Bozdogan, “Model selection and Akaike’s information criterion: the general theory and its analytical extensions”, Psychometrika, 1987, Vol. 52, No. 3, pp. 345-370.
[7]B. G. Buchanan and E. H. Shortliffe, Rule-Based Expert System: The MYCIN Experiments of the Standford Heuristic Programming Projects, Addison-Wesley, MA., 1984.
[8]N. Cercone, A. An and C. Chan, “Rule-induction and case-based reasoning: hybrid architectures appear advantageous”, IEEE Transactions on Knowledge and Data Engineering, 1999, Vol. 11, No. 1, 166-174.
[9]Y. M. Cheung, “Rival penalization controlled competitive learning for data clustering with unknown cluster number”, The Proceedings of the Ninth International Conference on Neural Information Processing, 2002, Vol. 1, pp. 18-22.
[10]R. M. Cole, Clustering with Genetic Algorithms, University of Western Australia, Master Thesis, 1998, pp. 2-3.
[11]M. Dash, K. Choi, P. Scheuermann and H. Liu, “Feature selection for clustering – a filter solution,” The Proceedings of the Second International Conference on Data Mining, 2002, pp. 115-122.
[12]K. Gao, M. Liu, K. Chen, N. Zhou and J. Chen, “Sampling-based tasks scheduling in dynamic grid environment,” The Proceedings of the Fifth WSEAS International Conference on Simulation, Modeling and Optimization, 2005, pp.25-30.
[13]I. Guyon and A. Elisseeff, “An introduction to variable and feature selection,” Journal of Machine Learning Research, 2003, Vol. 3, pp. 1,157-1,182.
[14]K. M. Gupta and A. R. Montazemi, “Empirical evaluation of retrieval in case-based reasoning systems using modified cosine matching function”, IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans, 1997, Vol. 27, No. 5, pp. 601-612.
[15]M. Hall, “Correlation-based feature selection for discrete and numeric class machine learning,” The Proceedings of the Seventeenth International Conference on Machine Learning, 2000, pp. 359-366.
[16]M. A. Hall and G. Holmes, “Benchmarking attribute selection techniques for discrete class data mining,” IEEE Transactions on Knowledge and Data Engineering, 2003, Vol. 15, No. 3, pp. 1,437-1,447.
[17]J. Han, X. Hu and T.Y. Lin, “Feature selection based on rough set and information entropy,” The Proceedings of the IEEE International Conference on Granular Computing, 2005, Vol. 1, pp. 153-158.
[18]J. Han and M. Kamber, Data Mining: Concepts and Techniques, Morgan Kaufmann, 2006.
[19]K. Hu, L. Diao, Y. Lu, and C. Shi, “A heuristic optimal reduct algorithm,“ Lecture Notes in Computer Science, Vol. 1983, Springer, Berlin, 2000, pp. 139-144.
[20]L. Kaufman and P. J. Rousseeuw, Finding Groups in Data: An Introduction to Cluster Analysis, John Wiley & Sons, 1990.
[21]K. Kira and L. Rendell, “A practical approach to feature selection”, The Proceedings of the Ninth International Conference on Machine Learning, 1992, pp. 249-256.
[22]Y. Kodratoff and R. S. Michalski, Machine Learning: An Artificial Intelligence Artificial Intelligence Approach, Vol. 3, Morgan Kaufmann Publishers, San Mateo, CA., 1983.
[23]J. Komorowski, L. Polkowski and A. Skowron, “Rough sets: a tutorial”, http:// www.let.uu.nl/esslli/Courses/skowron/skowron.ps.
[24]I. Kononenko, “Estimating attributes: analysis and extensions of relief,” The Proceedings of the Seventh European Conference on Machine Learning, 1994, pp. 171-182.
[25]Y. Li, S. C. K. Shiu and S. K. Pal, “Combining feature reduction and case selection in building CBR classifiers,” IEEE Transactions on Knowledge and Data Engineering, 2006, Vol. 18, No. 3, pp. 415- 429.
[26]H. Liu and R. Setiono, “A probabilistic approach to feature selection: a filter solution,” The Proceedings of the Thirteenth International Conference on Machine Learning, 1996, pp. 319-327.
[27]S. P. Lloyd, “Least squares quantization in PCM,” IEEE Transactions on Information Theory, 1982, Vol. 28, pp. 128-137, (original version: Technical Report, Bell Labs, 1957).
[28]R. S. Michalski, J. G. Carbonell and T. M. Mitchell, Machine Learning: An Artificial Intelligence Approach, Vol. 1, Morgan Kaufmann Publishers, Los Altos, CA., 1983.
[29]R. S. Michalski, J. G. Carbonell and T. M. Mitchell, Machine Learning: An Artificial Intelligence Approach, Vol. 2, Morgan Kaufmann Publishers, Los Altos, CA., 1983.
[30]Z. Pawlak, “Rough set,” International Journal of Computer and Information Sciences, 1982, Vol. 11, No. 1, pp. 341-356.
[31]Z. Pawlak, “Why rough sets?,” The Proceedings of the Fifth IEEE International Conference on Fuzzy Systems, 1996, Vol. 2, pp. 738-743.
[32]P. Pudil, J. Novovicova, and J. Kittler, “Floating search methods in feature selection,” Pattern Recognition Letters, 1994, Vol. 15, pp. 1,119-1,125.
[33]G. Riley, Expert Systems - Principles and Programming, Pws-Kent, Boston, 1989.
[34]M. Sarkar, B. Yegnanarayana and D. Khemani, “A cluster algorithm using an evolutionary programming-based approach”, Pattern Recognition Letters, 1997, Vol. 18, pp. 975-986
[35]G. Schwarz, “Estimating the dimension of a model”, The Annals of Statistics, 1978, Vol. 6, No. 2, pp. 461-464.
[36]K. S. Shin and I. Han, “Case-based reasoning supported by genetic algorithms for corporate bond rating”, Expert Systems with Applications, 1999, Vol. 16, pp. 85-95.
[37]A. Skowron and C. Rauszer, “The discernibility matrices and functions in information systems”, Handbook of Application and Advances of the Rough Sets Theory, Kluwer Academic Publishers, Dordrecht, 1992, pp. 331-362.
[38]H. Q. Sun, Z. Xiong, “Finding minimal reducts from incomplete information systems,” The Proceedings of the Second International Conference on Machine Learning and Cybernetics, 2003, Vol. 1, pp. 350-354.
[39]J. Wroblewski, “Finding minimal reducts using genetic algorithms,” The Proceedings of the Second Annual Join Conference on Information Sciences, 1995, pp. 186-189.
[40]L. Xu, A. Krzyiak and E. Oja, “Rival penalized competitive learning for clustering analysis, RBF Net, and Curve Detection”, IEEE Transaction on Neural Networks, 1993, Vol. 4, pp. 636-648.
[41]L. Yu and H. Liu, “Efficient feature selection via analysis of relevance and redundancy,” Journal of Machine Learning Research, 2004, Vol. 5, pp. 1,205-1,224.
[42]J. Zhang, J. Wang, D. Li, H. He, and J. Sun, “A new heuristic reduct algorithm based on rough sets theory,” Lecture Notes in Computer Science, Vol. 2762, Springer, Berlin, 2003, pp. 247-253.
[43]M. Zhang and J. T. Yao, “A rough sets based approach to feature selection,” The Proceedings of the IEEE Annual Meeting of Fuzzy Information, 2004, pp. 434-439.