COP5992 – DATA MINING TERM PROJECT RANDOM …：cop5992–数据挖掘项目随机….pptVIP

COP5992 – DATA MINING TERM PROJECTRANDOM SUBSPACE METHOD + CO-TRAININGbySELIM KALAYCI RANDOM SUBSPACE METHOD (RSM) Proposed by Ho “The Random Subspace for Constructing Decision Forests”, 1998 Another combining technique for weak classifiers like Bagging, Boosting. RSM ALGORITHM 1. Repeat for b = 1, 2, . . ., B: (a) Select an r-dimensional random subspace X from the original p-dimensional feature space X. 2. Combine classifiers Cb(x), b = 1, 2, . . ., B, by simple majority voting to a final decision rule MOTIVATION FOR RSM Redundancy in Data Feature Space Completely redundant feature set Redundancy is spread over many features Weak classifiers that have critical training sample sizes RSM PERFORMANCE ISSUES RSM Performance depends on: Training sample size The choice of a base classifier The choice of combining rule (simple majority vs. weighted) The degree of redundancy of the dataset The number of features chosen DECISION FORESTS (by Ho) A combination of trees instead of a single tree Assumption: Dataset has some redundant features Works efficiently with any decision tree algorithm and data splitting method Ideally, look for best individual trees with lowest tree similarity UNLABELED DATA Small number of labeled documents Large pool of unlabeled documents How to classify unlabeled documents accurately? EXPECTATION-MAXIMIZATION (E-M) CO-TRAINING Blum and Mitchel, “Combining Labeled and Unlabeled Data with Co-Training”, 1998. Requirements: Two sufficiently strong feature sets Conditionally independent CO-TRAINING APPLICATION OF CO-TRAINING TO A SINGLE FEATURE SET Algorithm: Obtain a small set L of labeled examples Obtain a large set U of unlabeled examples Obtain two sets F1 and F2 of features that are sufficiently redundant While U is not empty do: Learn classifier C1 from L based on F1 Learn classifier C2 from L based on F2 For each classifier Ci do: Ci labels examples from U based on Fi Ci chooses the most confidently predicted