7.基于实例的学习-k近邻

1、1基于实例学习李云2Instance-Based LearningUnlike other learning algorithms, does not involve construction of an explicit abstract generalization but classifies new instances based on direct comparison and similarity to known training instances.直接比较相似性Training can be very easy, just memorizing training instan

2、ces.训练简单，只需要记忆所有的样本Testing can be very expensive, requiring detailed comparison to all past training instances.测试代价比较高，需要跟所有训练样本进行比较。Also known as:Case-based Exemplar-basedNearest NeighborMemory-basedLazy Learning3Similarity/Distance MetricsInstance-based methods assume a function for determining th

3、e similarity or distance between any two instances.For continuous feature vectors, Euclidian distance is the generic choice:Where ap(x) is the value of the pth feature of instance x.For discrete features, assume distance between two values is 0 if they are the same and 1 if they are different (e.g.

4、Hamming distance for bit vectors).To compensate for difference in units across features, scale all continuous values to the interval 0,1归一化.4Other Distance MetricsMahalanobis distanceScale-invariant metric that normalizes for variance.Cosine SimilarityCosine of the angle between the two vectors.Used

5、 in text and other high-dimensional data.Pearson correlationStandard statistical correlation coefficient.Used for bioinformatics data.Edit distanceUsed to measure distance between unbounded length strings.Used in text and bioinformatics.5K-Nearest Neighbor K近邻Calculate the distance between a test po

6、int and every training instance.Pick the k closest training examples and assign the test instance to the most common category amongst these nearest neighbors.Voting multiple neighbors helps decrease susceptibility to noise. Usually use odd value for k to avoid ties.65-Nearest Neighbor Example7Implic

7、it Classification FunctionAlthough it is not necessary to explicitly calculate it, the learned classification rule is based on regions of the feature space closest to each training example.For 1-nearest neighbor with Euclidian distance, the Voronoi diagram（维诺图） gives the complex polyhedra（多面体） segme

8、nting the space into the regions closest to each point.8Efficient IndexingLinear search to find the nearest neighbors is not efficient for large training sets.Indexing structures can be built to speed testing.For Euclidian distance, a kd-tree can be built that reduces the expected time to find the n

9、earest neighbor to O(log n) in the number of training examples.Nodes branch on threshold tests on individual features and leaves terminate at nearest neighbors.Other indexing structures possible for other metrics or string data.Inverted index for text retrieval.9Nearest Neighbor VariationsCan be use

10、d to estimate the value of a real-valued function (regression) by taking the average function value of the k nearest neighbors to an input point.All training examples can be used to help classify a test instance by giving every training example a vote that is weighted by the inverse square of its di

11、stance from the test instance.10Feature Relevance and WeightingStandard distance metrics weight each feature equally when determining similarity.Problematic if many features are irrelevant, since similarity along many irrelevant examples could mislead the classification.Features can be weighted by s

12、ome measure that indicates their ability to discriminate the category of an example, such as information gain.Overall, instance-based methods favor global similarity over concept simplicity.+Training Data+Test Instance?11Rules and Instances inHuman Learning BiasesPsychological experiments show that

13、people from different cultures exhibit distinct categorization biases.“Western” subjects favor simple rules (straight stem) and classify the target object in group 2.“Asian” subjects favor global similarity and classify the target object in group 1. 1212Lazy vs. Eager LearningLazy vs. eager learning

14、Lazy learning (e.g., 基于实例的学习): 仅存储数据 (或稍加处理) 直到碰到检验样本才开始处理Eager learning (前面介绍的方法): 给定训练数据,在遇到待处理的新数据前构造分类模型Lazy: 训练用时很少，预测时用时多准确性惰性学习方法可以有效地利用更丰富的假设空间，使用多个局部线性函数来对目标函数形成一个隐式的全局逼近Eager: 必须限于一个假设，它覆盖了整个实例空间1313Lazy Learner:基于实例的方法Instance-based learning: Store training examples and delay the processi

15、ng (“lazy evaluation”) until a new instance must be classified典型的方法k-nearest neighbor approach实例表示为欧氏空间中的点.Locally weighted regressionConstructs local approximation基于案例的推理Case-based reasoning使用符号表示和知识为基础的推理1414k-最近邻算法所有的样本对应于n-D 空间的点通过Euclidean distance, dist(X1, X2) 定义最近邻居目标函数可以是discrete- or real-

16、值对于离散值, k-NN 返回与目标元组最近的k个训练样本的多数类Vonoroi diagram: the decision surface induced by 1-NN for a typical set of training examples . _+_xq+_+_+.1515k-NN Algorithm的讨论k-NN：元组的未知实值的预测时返回与未知元组k个最近邻居的平均值（对应属性）Distance-weighted nearest neighbor algorithm根据与目标元组的距离权重组合k个近邻的贡献Give greater weight to closer neighb

17、orsRobust to noisy data by averaging k-nearest neighborsCurse of dimensionality: 邻居间的距离会被无关联的属性影响 坐标轴伸缩或去除次要的属性16Other IssuesCan reduce storage of training instances to a small set of representative examples.Support vectors in an SVM are somewhat analogous.Can hybridize with rule-based methods or neural-net methods.Radial basis functions in neural nets and Gaussian kernels in SVMs are similar.Can be used for more complex relational or graph data.Similarity computation is complex since it involves some sort of graph isomorphism.Can be used in problems other than class