Solution Manual for Data Mining Chapter 9

Chapter 9 Classification: Advanced Methods 9.1 Exercises 1. The following table consists of training data from an employee database. The data have been generalized. For example, “31 . . . 35” for age represents the age range of 31 to 35. For a given row entry, count represents the number of data tuples having the values for department, status, age, and salary given in that row. department sales sales sales systems systems systems systems marketing marketing secretary secretary status senior junior junior junior senior junior senior senior junior senior junior age 31. . . 35 26. . . 30 31. . . 35 21. . . 25 31. . . 35 26. . . 30 41. . . 45 36. . . 40 31. . . 35 46. . . 50 26. . . 30 salary 46K. . . 50K 26K. . . 30K 31K. . . 35K 46K. . . 50K 66K. . . 70K 46K. . . 50K 66K. . . 70K 46K. . . 50K 41K. . . 45K 36K. . . 40K 26K. . . 30K count 30 40 40 20 5 3 3 10 4 4 6 Let status be the class label attribute. (a) Design a multilayer feed-forward neural network for the given data. Label the nodes in the input and output layers. (b) Using the multilayer feed-forward neural network obtained above, show the weight values after one iteration of the backpropagation algorithm, given the training instance “(sales, senior, 31. . . 35, 46K. . . 50K)”. Indicate your initial weight values and biases, and the learning rate used. Answer: (a) There is no standard answer. Every feasible solution is correct. As stated in the book, discretevalued attributes may be encoded such that there is one input unit per domain value. For hidden layer units, the number should be smaller than that of input units, but larger than that of output units. (b) There is no standard answer. Every feasible solution is correct. 2. The support vector machine (SVM) is a highly accurate classification method. However, SVM classifiers suffer from slow processing when training with a large set of data tuples. Discuss how to overcome this difficulty and develop a scalable SVM algorithm for efficient SVM classification in large datasets. Answer: We can use the micro-clustering technique in “Classifying large data sets using SVM with hierarchical clusters” by Yu, Yang, and Han, in Proc. 2003 ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (KDD’03), pages 306-315, Aug. 2003 [YYH03]. A Cluster-Based SVM (CB-SVM) method is described as follows: 1. Construct the microclusters using a CF-Tree (Chapter 7). 2. Train an SVM on the centroids of the microclusters. 3. Decluster entries near the boundary. 4. Repeat the SVM training with the additional entries. 5. Repeat the above until convergence. 3. Compare and contrast associative classification and discriminative frequent pattern-based classification. Why is classification based on frequent patterns able to achieve higher classification accuracy in many cases than a classical decision-tree method? Answer: Association-based classification is a method where association rules are generated and analyzed for use in classification. We first search for strong associations between frequent patterns (conjunctions of attribute-value pairs) and class labels. Using such strong associations we classify new examples. Discriminative frequent pattern-based classification first finds discriminative frequent patterns according to certain measures such as pattern length and pattern frequency and uses these patterns as features. Then it trains classifiers based on these features. Frequent pattern-based classification can achieve higher accuracy than a classical decision tree because it overcomes the constraint of decision trees, which consider only one attribute at a time. Some frequent patterns could have very high discriminative power because they combine multiple attributes. 4. Compare the advantages and disadvantages of eager classification (e.g., decision tree, Bayesian, neural network) versus lazy classification (e.g., k-nearest neighbor, case-based reasoning). Answer: Eager classification is faster at classification than lazy classification because it constructs a generalization model before receiving any new tuples to classify. Weights can be assigned to attributes, which can improve classification accuracy. Disadvantages of eager classification are that it must commit to a single hypothesis that covers the entire instance space, which can decrease classification, and more time is needed for training. Lazy classification uses a richer hypothesis space, which can improve classification accuracy. It requires less time for training than eager classification. A disadvantages of lazy classification is that all training tuples need to be stored, which leads to expensive storage costs and requires efficient indexing techniques. Another disadvantage is that it is slower at classification because classifiers are not built until new tuples need to be classified. Furthermore, attributes are all equally weighted, which can decrease classification accuracy. (Problems may arise due to irrelevant attributes in the data.) Algorithm: k-nearest neighbor. Build a k-nearest neighbor classifier. Input: • Let U be the unknown tuple whose class we want to assign. • Let T be the training set containing training tuples, T1 = (t1,1 , t1,2 , . . . , t1,n ), T2 = (t2,1 , t2,2 , . . . , t2,n ), . . . , Tm = (tm,1 , tm,2 , . . . , tm,n ). • Let attribute ti,n be the class label of Ti . • Let m be the number of training tuples. • Let n be the number of attributes describing each tuple. • Let k be the number of nearest neighbors we wish to find. Output: Class label for U . Method: The method is outlined as follows. 1) array a[m][2]; // m rows containing data regarding the m training tuples. The first column is the Euclidean distance between U and that row’s training tuple. The second column refers to that training tuple’s index. We need to save the index because when sorting the array (according to Euclidean distance), we need some way to determine to which training set the Euclidean distance refers. 2) for i = 1 to m do { 3) a[i][1] = Euclidean distance(U, Ti ); 4) a[i][2] = i;} // save the index, because rows will be sorted later 5) Sort the rows of a by their Euclidean distances saved in a[i][1] (in ascending order); 6) array b[k][2]; // The first column holds the distinct class labels of the k-nearest neighbors, while the second holds their respective counts. In the worst case, each k-nearest neighbor will have a different class label, which is why we need to allocate room for k class labels. 7) for i = 1 to k do { 8) if class label ta[i][2],n already exists in array b then 9) find that class label’s row in array b and increment its count; 10) else add the class label into the next available row of array b and increment its count; } 11) Sort array b in descending order (from class label with largest count down to that with smallest count); 12) return(b[1]); //return most frequent class label of the k-nearest neighbors of U as the class prediction. Figure 9.1: k-nearest neighbor algorithm. 5. Write an algorithm for k-nearest neighbor classification given k, the nearest number of neighbors, and n, the number of attributes describing each tuple. Answer: Figure 9.1 presents an algorithm for k-nearest neighbor classification. 6. Briefly describe the classification processes using i) genetic algorithms, ii) rough sets, and iii) fuzzy sets. Answer: i) Genetic algorithms is based on an analogy to biological evolution. • An initial population is created consisting of randomly generated rules. Each rule is represented by a string of bits. If an attribute has k > 2 values, k bits can be used. • Based on the notion of survival of the fittest, a new population is formed to consist of the fittest rules and their offspring. The fitness of a rule is represented by its classification accuracy on a set of training examples. • Offspring are generated by crossover and mutation. The process continues until a population P evolves when each rule in P satisfies a prespecified threshold. ii) Rough sets are used to approximately or roughly define equivalent classes. A rough set for a given class C is approximated by two sets: a lower approximation (certain to be in C) and an upper approximation (cannot be described as not belonging to C). iii) Fuzzy logic uses truth values between 0.0 and 1.0 to represent the degree of membership (such as in a fuzzy membership graph). Attribute values are converted to fuzzy values. Each applicable rule contributes a vote for membership in the categories. Typically, the truth values for each predicted category are summed, and these sums are combined. 7. Example 9.3 showed an example of the use of error-correcting codes for a multiclass classification problem having four classes. (a) Suppose that, given an unknown tuple to label, the seven trained binary classifiers collectively output the codeword 0101110, which does not match a codeword for any of the four classes. Using error correction, what class label should be assigned to the tuple? (b) Explain why using a 4-bit vector for the codewords is insufficient for error correction. Answer: (a) It should be assigned to C4 , given it has the smallest Hamming distance 1. (b) Since we want to do 4-class classification with error-correcting code, at least we should be able to correct 1-bit error. This requires the minimum hamming distance h between codewords to satisfy ⌊ h−1 ⌋ > 1, which means h > 3. Using 4-bit vector for a codeword, it is obvious that we cannot 2 find 4 4-bit vectors with minimum hamming distance 3 between any two of them. Therefore, it is insufficient for error correction. 8. Semi-supervised classification, active learning and transfer learning are useful for situations in which unlabeled data are abundant. (a) Describe semi-supervised classification, active learning and transfer learning. Elaborate on applications for which they are useful, as well as the challenges of these approaches to classification. (b) Research and describe an approach to semi-supervised classification other than self-training and co-training. (c) Research and describe an approach to active learning other than pool-based learning. (d) Research and describe an alternative approach to instance-based transfer learning. Answer: (a) • Semi-supervised classification uses both labeled and unlabeled data to build a classifier. It is often used in the situation where unlabeled data are plentiful. Applications include intruder detection in a battlefield sensor network because it is costly and error-prone to manually label the large sensor dataset. Semi-supervised leaarning is also widely used in text classification. The main challenge for semi-supervised learning is how to find discriminative features to classify the data. • Active learning purposefully queries a user (e.g., a human oracle) for labels. And then it uses all the labelled data to train the classifier in a standard supervised way. Active learning is suitable for situations where data are abundant, yet the class labels are scarce or expensive to obtain. It can be applied to the areas of text classification and image retrieval and outperforms regular passive learning substantially. The main challenge for active learning is how to choose the data tuples to be queried. This can be computational expensive. • Transfer Learning extracts knowledge from one or more source tasks and then apply the knowledge to a target task. Transfer learning is useful for applications where the data becomes outdated or the distribution changes. Typical applications include web-document classification and email spam filtering. The main challenge for transfer learning is negative transfer. This occurs when the new classifier performs worse than if there had been no transfer at all. (b) There are no standard answers to this question. An alternative approach is to model the joint probability distribution of the features and the labels. For the unlabeled data the labels can then be treated as ’missing data’. Techniques that handle missing data, such as Gibbs sampling or the EM algorithm, can then be used to estimate the parameters of the model. (c) There are no standard answers to this question. Alternative approaches could include membership query synthesis and stream-based selective sampling. • In the setting of membership query synthesis, the learner may request labels for any unlabeled instance in the input space, including (and typically assuming) queries that the learner generates de novo, rather than those sampled from some underlying natural distribution. Efficient query synthesis is often tractable and efficient for finite problem domains [1]. • In the setting of stream-based selective sampling, the key assumption is that obtaining an unlabeled instance is free (or inexpensive), so it can first be sampled from the actual distribution, and then the learner can decide whether or not to request its label. This approach is sometimes called stream-based or sequential active learning, as each unlabeled instance is typically drawn one at a time from the data source, and the learner must decide whether to query or discard it[1]. (d) There are no standard answers to this question. An alternative approach could be feature representation-transfer. This approach aims at finding “good” feature representations to minimize domain divergence and classification or regression model error. Strategies to find “good” feature representations are different for different types of the source domain data. If a lot of labeled data in the source domain are available, supervised learning methods can be used to construct a feature representation. If no labeled data in the source domain are available, unsupervised learning methods are proposed to construct the feature representation[2]. [1] B. Settles. Active Learning Literature Survey. Computer Sciences Tech. Report 1648, Univ. of Wisconsin-Madison. 2009. [2] S. J. Pan and Q. Yang, A Survey on Transfer Learning, IEEE Trans. on Knowledge and Data Engineering, 22(10):1345-1359, 2010. 9.2 Supplementary Exercises 1. To be added