Chapter8
k NN:k-Nearest Neighbors
Michael Steinbach and Pang-Ning Tan
Contents
8.1Introduction (151)
8.2Description of the Algorithm (152)
8.2.1High-Level Description (152)
8.2.2Issues (153)
8.2.3Software Implementations (155)
8.3Examples (155)
8.4Advanced Topics (157)
8.5Exercises (158)
Acknowledgments (159)
References (159)
8.1Introduction
One of the simplest and rather trivial classi?ers is the Rote classi?er,which memorizes the entire training data and performs classi?cation only if the attributes of the test object exactly match the attributes of one of the training objects.An obvious problem with this approach is that many test records will not be classi?ed because they do not exactly match any of the training records.Another issue arises when two or more training records have the same attributes but different class labels.
A more sophisticated approach,k-nearest neighbor(k NN)classi?cation[10,11,21],?nds a group of k objects in the training set that are closest to the test object,and bases the assignment of a label on the predominance of a particular class in this neighborhood.This addresses the issue that,in many data sets,it is unlikely that one object will exactly match another,as well as the fact that con?icting information about the class of an object may be provided by the objects closest to it.There are several key elements of this approach:(i)the set of labeled objects to be used for evaluating a test object’s class,1(ii)a distance or similarity metric that can be used to compute
This need not be the entire training set.
151
152kNN:k-Nearest Neighbors
the closeness of objects,(iii)the value of k,the number of nearest neighbors,and(iv) the method used to determine the class of the target object based on the classes and distances of the k nearest neighbors.In its simplest form,k NN can involve assigning an object the class of its nearest neighbor or of the majority of its nearest neighbors, but a variety of enhancements are possible and are discussed below.
More generally,k NN is a special case of instance-based learning[1].This includes case-based reasoning[3],which deals with symbolic data.The k NN approach is also an example of a lazy learning technique,that is,a technique that waits until the query arrives to generalize beyond the training data.
Although k NN classi?cation is a classi?cation technique that is easy to understand and implement,it performs well in many situations.In particular,a well-known result by Cover and Hart[6]shows that the classi?cation error2of the nearest neighbor rule is bounded above by twice the optimal Bayes error3under certain reasonable assump-tions.Furthermore,the error of the general k NN method asymptotically approaches that of the Bayes error and can be used to approximate it.
Also,because of its simplicity,k NN is easy to modify for more complicated classi?-cation problems.For instance,k NN is particularly well-suited for multimodal classes4 as well as applications in which an object can have many class labels.To illustrate the last point,for the assignment of functions to genes based on microarray expression pro?les,some researchers found that k NN outperformed a support vector machine (SVM)approach,which is a much more sophisticated classi?cation scheme[17]. The remainder of this chapter describes the basic k NN algorithm,including vari-ous issues that affect both classi?cation and computational performance.Pointers are given to implementations of k NN,and examples of using the Weka machine learn-ing package to perform nearest neighbor classi?cation are also provided.Advanced techniques are discussed brie?y and this chapter concludes with a few exercises. 8.2Description of the Algorithm
8.2.1High-Level Description
Algorithm8.1provides a high-level summary of the nearest-neighbor classi?cation method.Given a training set D and a test object z,which is a vector of attribute values and has an unknown class label,the algorithm computes the distance(or similarity)
2The classi?cation error of a classi?er is the percentage of instances it incorrectly classi?es.
3The Bayes error is the classi?cation error of a Bayes classi?er,that is,a classi?er that knows the underlying probability distribution of the data with respect to class,and assigns each data point to the class with the highest probability density for that point.For more detail,see[9].
4With multimodal classes,objects of a particular class label are concentrated in several distinct areas of the data space,not just one.In statistical terms,the probability density function for the class does not have a single“bump”like a Gaussian,but rather,has a number of peaks.
8.2Description of the Algorithm 153
Algorithm 8.1Basic k NN Algorithm
Input :D ,the set of training objects,the test object,z ,which is a vector of
attribute values,and L ,the set of classes used to label the objects
Output :c z ∈L ,the class of z foreach object y ∈D do
|Compute d (z ,y ),the distance between z and y ;end
Select N ?D ,the set (neighborhood)of k closest training objects for z ;c z =argmax v ∈L
y ∈N I (v =class (c y ));where I (·)is an indicator function that returns the value 1if its argument is true and 0otherwise.between z and all the training objects to determine its nearest-neighbor list.It then assigns a class to z by taking the class of the majority of neighboring objects.Ties are broken in an unspeci?ed manner,for example,randomly or by taking the most frequent class in the training set.
The storage complexity of the algorithm is O (n ),where n is the number of training objects.The time complexity is also O (n ),since the distance needs to be computed between the target and each training object.However,there is no time taken for the construction of the classi?cation model,for example,a decision tree or sepa-rating hyperplane.Thus,k NN is different from most other classi?cation techniques which have moderately to quite expensive model-building stages,but very inexpensive O (constant )classi?cation steps.
8.2.2Issues
There are several key issues that affect the performance of k NN.One is the choice of k .This is illustrated in Figure 8.1,which shows an unlabeled test object,x ,and training objects that belong to either a “+”or “?”class.If k is too small,then the result can be sensitive to noise points.On the other hand,if k is too large,then the neighborhood may include too many points from other classes.An estimate of the best value for k can be obtained by cross-validation.However,it is important to point out that k =1may be able to perform other values of k ,particularly for small data sets,including those typically used in research or for class exercises.However,given enough samples,larger values of k are more resistant to noise.
Another issue is the approach to combining the class labels.The simplest method is to take a majority vote,but this can be a problem if the nearest neighbors vary widely in their distance and the closer neighbors more reliably indicate the class of the object.A more sophisticated approach,which is usually much less sensitive to the choice of k ,weights each object’s vote by its distance.Various choices are possible;for example,the weight factor is often taken to be the reciprocal of the squared distance:w i =1/d (y ,z )2.This amounts to replacing the last step of Algorithm 8.1with the
154
kNN:k-Nearest Neighbors ++
???????
????
??
???????+++X ++++++????????
?????????????+++++++++++X ?????????????????????+++++++++++
X (a) Neighborhood too
small.(b) Neighborhood just right.(c) Neighborhood too large.
Figure 8.1k -nearest neighbor classi?cation with small,medium,and large k .following:
Distance-Weighted V oting:c z =argmax v ∈L y ∈N w i ×I (v =class (c y ))(8.1)
The choice of the distance measure is another important https://www.doczj.com/doc/31475642.html,monly,Euclidean or Manhattan distance measures are used [21].For two points,x and y ,with n attributes,these distances are given by the following formulas:
d (x ,y )= n k =1
(x k ?y k )2Euclidean distance (8.2)
d (x ,y )= n k =1|x k ?y k |
Manhattan distance (8.3)
where x k and y k are the k th attributes (components)of x and y ,respectively.
Although these and various other measures can be used to compute the distance between two points,conceptually,the most desirable distance measure is one for which a smaller distance between two objects implies a greater likelihood of having the same class.Thus,for example,if k NN is being applied to classify documents,then it may be better to use the cosine measure rather than Euclidean distance.Note that k NN can also be used for data with categorical or mixed categorical and numerical attributes as long as a suitable distance measure can be de?ned [21].
Some distance measures can also be affected by the high dimensionality of the data.In particular,it is well known that the Euclidean distance measure becomes less discriminating as the number of attributes increases.Also,attributes may have to be scaled to prevent distance measures from being dominated by one of the attributes.For example,consider a data set where the height of a person varies from 1.5to 1.8m,
8.3Examples155 the weight of a person varies from90to300lb,and the income of a person varies from$10,000to$1,000,000.If a distance measure is used without scaling,the income attribute will dominate the computation of distance,and thus the assignment of class labels.
8.2.3Software Implementations
Algorithm8.1is easy to implement in almost any programming language.However, this section contains a short guide to some readily available implementations of this algorithm and its variants for those who would rather use an existing implementation. One of the most readily available k NN implementations can be found in Weka[26]. The main function of interest is IBk,which is basically Algorithm8.1.However,IBk also allows you to specify a couple of choices of distance weighting and the option to determine a value of k by using cross-validation.
Another popular nearest neighbor implementation is PEBLS(Parallel Exemplar-Based Learning System)[5,19]from the CMU Arti?cial Intelligence repository[20]. According to the site,“PEBLS(Parallel Exemplar-Based Learning System)is a nearest-neighbor learning system designed for applications where the instances have symbolic feature values.”
8.3Examples
In this section we provide a couple of examples of the use of k NN.For these examples, we will use the Weka package described in the previous section.Speci?cally,we used Weka3.5.6.
To begin,we applied k NN to the Iris data set that is available from the UCI Machine Learning Repository[2]and is also available as a sample data?le with Weka.This data set consists of150?owers split equally among three Iris species:Setosa,Versicolor, and Virginica.Each?ower is characterized by four measurements:petal length,petal width,sepal length,and sepal width.
The Iris data set was classi?ed using the IB1algorithm,which corresponds to the IBk algorithm with k=1.In other words,the algorithm looks at the closest neighbor, as computed using Euclidean distance from Equation8.2.The results are quite good, as the reader can see by examining the confusion matrix5given in Table8.1. However,further investigation shows that this is a quite easy data set to classify since the different species are relatively well separated in the data space.To illustrate, we show a plot of the data with respect to petal length and petal width in Figure8.2. There is some mixing between the Versicolor and Virginica species with respect to 5A confusion matrix tabulates how the actual classes of various data instances(rows)compare to their predicted classes(columns).
156kNN:k-Nearest Neighbors
TABLE 8.1
Confusion Matrix for Weka k NN
Classi?er IB1on the Iris Data Set
Actual/Predicted Setosa Versicolor Virginica Setosa
5000Versicolor
0473Virginica 0446
their petal lengths and widths,but otherwise the species are well separated.Since the other two variables,sepal width and sepal length,add little if any discriminating information,the performance seen with basic k NN approach is about the best that can be achieved with a k NN approach or,indeed,any other approach.
The second example uses the ionosphere data set from UCI.The data objects in this data set are radar signals sent into the ionosphere and the class value indicates whether or not the signal returned information on the structure of the ionosphere.There are 34attributes that describe the signal and 1class attribute.The IB1algorithm applied on the original data set gives an accuracy of 86.3%evaluated via tenfold cross-validation,while the same algorithm applied to the ?rst nine attributes gives an accuracy of 89.4%.In other words,using fewer attributes gives better results.The confusion matrices are given https://www.doczj.com/doc/31475642.html,ing cross-validation to select the number of nearest neighbors gives an accuracy of 90.8%with two nearest neighbors.The confusion matrices for these cases are given below in Tables 8.2,8.3,and 8.4,respectively.Adding weighting for nearest neighbors actually results in a modest drop in accuracy.The biggest improvement is due to reducing the number of attributes.
P e t a l w i d t h Petal length
Figure 8.2Plot of Iris data using petal length and width.
8.4Advanced Topics157
TABLE8.2Confusion Matrix for Weka k NN Classi?er
IB1on the Ionosphere Data Set Using All Attributes
Actual/Predicted Good Signal Bad Signal
Good Signal8541
Bad Signal7218
8.4Advanced Topics
To address issues related to the distance function,a number of schemes have been developed that try to compute the weights of each individual attribute or in some other way determine a more effective distance metric based upon a training set[13,15]. In addition,weights can be assigned to the training objects themselves.This can give more weight to highly reliable training objects,while reducing the impact of unreliable objects.The PEBLS system by Cost and Salzberg[5]is a well-known example of such an approach.
As mentioned,k NN classi?ers are lazy learners,that is,models are not built explic-itly unlike eager learners(e.g.,decision trees,SVM,etc.).Thus,building the model is cheap,but classifying unknown objects is relatively expensive since it requires the computation of the k-nearest neighbors of the object to be labeled.This,in general, requires computing the distance of the unlabeled object to all the objects in the la-beled set,which can be expensive particularly for large training sets.A number of techniques,e.g.,multidimensional access methods[12]or fast approximate similar-ity search[16],have been developed for ef?cient computation of k-nearest neighbor distance that make use of the structure in the data to avoid having to compute distance to all objects in the training set.These techniques,which are particularly applicable for low dimensional data,can help reduce the computational cost without affecting classi?cation accuracy.The Weka package provides a choice of some of the multi-dimensional access methods in its IBk routine.(See Exercise4.)
Although the basic k NN algorithm and some of its variations,such as weighted k NN and assigning weights to objects,are relatively well known,some of the more advanced techniques for k NN are much less known.For example,it is typically possible to eliminate many of the stored data objects,but still retain the classi?cation accuracy of the k NN classi?er.This is known as“condensing”and can greatly speed up the classi?cation of new objects[14].In addition,data objects can be removed to TABLE8.3Confusion Matrix for Weka k NN Classi?er
IB1on the Ionosphere Data Set Using the First Nine Attributes
Actual/Predicted Good Signal Bad Signal
Good Signal10026
Bad Signal11214
158kNN:k-Nearest Neighbors
TABLE8.4Confusion Matrix for Weka k NN
Classi?er IBk on the Ionosphere Data Set Using
the First Nine Attributes with k=2
Actual/Predicted Good Signal Bad Signal
Good Signal1039
Bad Signal23216
improve classi?cation accuracy,a process known as“editing”[25].There has also been a considerable amount of work on the application of proximity graphs(nearest neighbor graphs,minimum spanning trees,relative neighborhood graphs,Delaunay triangulations,and Gabriel graphs)to the k NN problem.Recent papers by Toussaint [22–24],which emphasize a proximity graph viewpoint,provide an overview of work addressing these three areas and indicate some remaining open problems.
Other important resources include the collection of papers by Dasarathy[7]and the book by Devroye,Gyor?,and Lugosi[8].Also,a fuzzy approach to k NN can be found in the work of Bezdek[4].Finally,an extensive bibliography on this subject is also available online as part of the Annotated Computer Vision Bibliography[18].
8.5Exercises
1.Download the Weka machine learning package from the Weka project home-
page and the Iris and ionosphere data sets from the UCI Machine Learning Repository.Repeat the analyses performed in this chapter.
2.Prove that the error of the nearest neighbor rule is bounded above by twice the
Bayes error under certain reasonable assumptions.
3.Prove that the error of the general k NN method asymptotically approaches that
of the Bayes error and can be used to approximate it.
4.Various spatial or multidimensional access methods can be used to speed up
the nearest neighbor computation.For the k-d tree,which is one such method, estimate how much the saving would https://www.doczj.com/doc/31475642.html,ment:The IBk Weka classi?cation algorithm allows you to specify the method of?nding nearest neighbors.Try this on one of the larger UCI data sets,for example,predicting sex on the abalone data set.
5.Consider the one-dimensional data set shown in Table8.5.
TABLE8.5Data Set for Exercise5
x 1.5 2.5 3.5 4.5 5.0 5.5 5.75 6.57.510.5
y++???++?++
References159
(a)Given the data points listed in Table8.5,compute the class of x=5.5
according to its1-,3-,6-,and9-nearest neighbors(using majority vote).
(b)Repeat the previous exercise,but use the weighted version of k NN given
in Equation(8.1).
https://www.doczj.com/doc/31475642.html,ment on the use of k NN when documents are compared with the cosine
measure,which is a measure of similarity,not distance.
7.Discuss kernel density estimation and its relationship to k NN.
8.Given an end user who desires not only a classi?cation of unknown cases,but
also an understanding of why cases were classi?ed the way they were,which classi?cation method would you prefer:decision tree or k NN?
9.Sampling can be used to reduce the number of data points in many kinds of
data https://www.doczj.com/doc/31475642.html,ment on the use of sampling for k NN.
10.Discuss how k NN could be used to perform classi?cation when each class can
have multiple labels and/or classes are organized in a hierarchy.
Acknowledgments
This work was supported by NSF Grant CNS-0551551,NSF ITR Grant ACI-0325949, NSF Grant IIS-0308264,and NSF Grant IIS-0713227.Access to computing facil-ities was provided by the University of Minnesota Digital Technology Center and Supercomputing Institute.
References
[1] D.W.Aha,D.Kibler,and M.K.Albert.Instance-based learning algorithms.
Mach.Learn.,6(1):37–66,January1991.
[2] A.Asuncion and D.Newman.UCI Machine Learning Repository,2007.
[3] B.Bartsch-Sp¨o rl,M.Lenz,and A.H¨u bner.Case-based reasoning—survey
and future directions.In F.Puppe,editor,XPS-99:Knowledge-Based Systems—Survey and Future Directions,5th Biannual German Conference on Knowledge-Based Systems,volume1570of Lecture Notes in Computer Sci-ence,W¨u rzburg,Germany,March3-51999.Springer.
[4]J.C.Bezdek,S.K.Chuah,and D.Leep.Generalized k-nearest neighbor rules.
Fuzzy Sets Syst.,18(3):237–256,1986.
[5]S.Cost and S.Salzberg.A weighted nearest neighbor algorithm for learning
with symbolic features.Mach.Learn.,10(1):57–78,1993.
160kNN:k-Nearest Neighbors
[6]T.Cover and P.Hart.Nearest neighbor pattern classi?cation.IEEE Transactions
on Information Theory,13(1):21–27,January1967.
[7] B.Dasarathy.Nearest Neighbor(NN)Norms:NN Pattern Classi?cation Tech-
https://www.doczj.com/doc/31475642.html,puter Society Press,1991.
[8]L.Devroye,L.Gyor?,and G.Lugosi.A Probabilistic Theory of Pattern Recog-
nition.Springer-Verlag,1996.
[9]R.O.Duda,P.E.Hart,and D.G.Stork.Pattern Classi?cation(2nd Edition).
Wiley-Interscience,November2000.
[10] E.Fix and J.J.Hodges.Discriminatory analysis:Non-parametric discrimi-
nation:Consistency properties.Technical report,USAF School of Aviation Medicine,1951.
[11] E.Fix and J.J.Hodges.Discriminatory analysis:Non-parametric discrimina-
tion:Small sample performance.Technical report,USAF School of Aviation Medicine,1952.
[12]V.Gaede and O.G¨u nther.Multidimensional access methods.ACM Comput.
Surv.,30(2):170–231,1998.
[13] E.-H.Han,G.Karypis,and V.Kumar.Text categorization using weight adjusted
k-nearest neighbor classi?cation.In PAKDD’01:Proceedings of the5th Paci?c-Asia Conference on Knowledge Discovery and Data Mining,pages53–65, London,UK,2001.Springer-Verlag.
[14]P.Hart.The condensed nearest neighbor rule.IEEE https://www.doczj.com/doc/31475642.html,rm.,14(5):515–
516,May1968.
[15]T.Hastie and R.Tibshirani.Discriminant adaptive nearest neighbor classi?ca-
tion.IEEE Trans.Pattern Anal.Mach.Intell.,18(6):607–616,1996.
[16]M.E.Houle and J.Sakuma.Fast approximate similarity search in extremely
high-dimensional data sets.In ICDE’05:Proceedings of the21st Interna-tional Conference on Data Engineering,pages619–630,Washington,DC, 2005.IEEE Computer Society.
[17]M.Kuramochi and G.Karypis.Gene classi?cation using expression pro?les:
A feasibility study.In BIBE’01:Proceedings of the2nd IEEE International
Symposium on Bioinformatics and Bioengineering,page191,Washington,DC, 2001.IEEE Computer Society.
[18]K.Price.Nearest neighbor classi?cation bibliography.http://www.visionbib.
com/bibliography/pattern621.html,2008.Part of the Annotated Computer Vision Bibliography.
[19]J.Rachlin,S.Kasif,S.Salzberg,and D.W.Aha.Towards a better understanding
of memory-based reasoning systems.In International Conference on Machine Learning,pages242–250,1994.
References161 [20]S.Salzberg.PEBLS:Parallel exemplar-based learning system.http://www.
https://www.doczj.com/doc/31475642.html,/afs/cs/project/ai-repository/ai/areas/learning/systems/pebls/0.html, 1994.
[21]P.-N.Tan,M.Steinbach,and V.Kumar.Introduction to Data Minining.Pearson
Addison-Wesley,2006.
[22]G.T.Toussaint.Proximity graphs for nearest neighbor decision rules:Recent
progress.In Interface-2002,34th Symposium on Computing and Statistics, Montreal,Canada,April17–20,2002.
[23]G.T.Toussaint.Open problems in geometric methods for instance-based learn-
ing.In Discrete and Computational Geometry,volume2866of Lecture Notes in Computer Science,pages273–283,December6–9,2003.
[24]G.T.Toussaint.Geometric proximity graphs for improving nearest neighbor
methods in instance-based learning and data https://www.doczj.com/doc/31475642.html,put.Geometry Appl.,15(2):101–150,2005.
[25] D.Wilson.Asymptotic properties of nearest neighbor rules using edited data.
IEEE Trans.Syst.,Man,and Cybernetics,2:408–421,1972.
[26]I.H.Witten and E.Frank.Data Mining:Practical Machine Learning Tools and
Techniques,Second Edition(Morgan Kaufmann Series in Data Management Systems).Morgan Kaufmann,June2005.
kNN算法综述 王宇航13120476 (北京交通大学计算机与信息技术学院，北京，100044) 摘要：kNN算法是著名的模式识别统计学方法，是最好的文本分类算法之一，在机器学习分类算法中占有相当大的地位，是最简单的机器学习算法 之一。本文对kNN算法及相关文献做一份总结，详细介绍kNN算法的思想、原理、实现步骤以及具体实现代码，并分析了算法的优缺点及其各种改进方 案。本文还介绍了kNN算法的发展历程、重要的发表的论文。本文在最后介 绍了kNN算法的应用领域，并重点说明其在文本分类中的实现。 关键字：kNN算法；k近邻算法；机器学习；文本分类 Abstract:KNN algorithm,a famous statistical method of pattern recognition, which is one of the best algorithms for dealing with text categorization,is playing an important role in machine learning classification algorithm,and it is one of the simplest algorithms in machine learning.This paper mainly summaries the kNN algorithm and its related literature,and detailed introduces its main idea,principle, implementation steps and specific implementation code,as well as analyzes the advantages and disadvantages of the algorithm and its various improvement schemes.This paper also introduces the development course of kNN algorithm,its important published paper.In the final,this paper introduces the application field of kNN algorithm,and especially in text categorization. Keywords:KNN algorithm,K neighbor algorithm,Machine learning,Text classification 1引言 分类是数据挖掘中的核心和基础技术，在经营、决策、管理、科学研究等多个领域都有着广泛的应用。目前主要的分类技术包括决策树、贝叶斯分类、kNN分类、人工神经网络等。在这些方法中，kNN分类是一种简单、有效、非参数的方法，现已经广泛应用于文本分类、模式识别、图像及空间分类等领域。本文从各个角度对kNN算法进行较为全面的总结。 本文的结构如下： 在第二部分，主要介绍kNN算法的基本原理、思想、实现步骤、Java实现代码以及发展历程和经典论文。 第三部分是对kNN算法的诸多不足之处进行的讨论，并给出一些改进的方案。 第四部分介绍的是kNN算法如何处理多标签数据。 第五部分介绍了kNN算法目前的主要应用领域，并着重说明了其在文本分类中的出色表现。
Chapter8 k NN:k-Nearest Neighbors Michael Steinbach and Pang-Ning Tan Contents 8.1Introduction (151) 8.2Description of the Algorithm (152) 8.2.1High-Level Description (152) 8.2.2Issues (153) 8.2.3Software Implementations (155) 8.3Examples (155) 8.4Advanced Topics (157) 8.5Exercises (158) Acknowledgments (159) References (159) 8.1Introduction One of the simplest and rather trivial classi?ers is the Rote classi?er,which memorizes the entire training data and performs classi?cation only if the attributes of the test object exactly match the attributes of one of the training objects.An obvious problem with this approach is that many test records will not be classi?ed because they do not exactly match any of the training records.Another issue arises when two or more training records have the same attributes but different class labels. A more sophisticated approach,k-nearest neighbor(k NN)classi?cation[10,11,21],?nds a group of k objects in the training set that are closest to the test object,and bases the assignment of a label on the predominance of a particular class in this neighborhood.This addresses the issue that,in many data sets,it is unlikely that one object will exactly match another,as well as the fact that con?icting information about the class of an object may be provided by the objects closest to it.There are several key elements of this approach:(i)the set of labeled objects to be used for evaluating a test object’s class,1(ii)a distance or similarity metric that can be used to compute This need not be the entire training set. 151
一、层次聚类 1、层次聚类的原理及分类 1）层次法（Hierarchical methods）先计算样本之间的距离。每次将距离最近的点合并到同一个类。然后，再计算类与类之间的距离，将距离最近的类合并为一个大类。不停的合并，直到合成了一个类。其中类与类的距离的计算方法有：最短距离法，最长距离法，中间距离法，类平均法等。比如最短距离法，将类与类的距离定义为类与类之间样本的最短距离。 层次聚类算法根据层次分解的顺序分为：自下底向上和自上向下，即凝聚的层次聚类算法和分裂的层次聚类算法（agglomerative和divisive），也可以理解为自下而上法（bottom-up）和自上而下法（top-down）。自下而上法就是一开始每个个体（object）都是一个 类，然后根据linkage寻找同类，最后形成一个“类”。自上而下法就是反过来，一开始所有个体都属于一个“类”，然后根据linkage排除异己，最后每个个体都成为一个“类”。这两种路方法没有孰优孰劣之分，只是在实际应用的时候要根据数据特点以及你想要的“类”的个数，来考虑是自上而下更快还是自下而上更快。至于根据Linkage判断“类” 的方法就是最短距离法、最长距离法、中间距离法、类平均法等等（其中类平均法往往被认为是最常用也最好用的方法，一方面因为其良好的单调性，另一方面因为其空间扩张/浓缩的程度适中）。为弥补分解与合并的不足，层次合并经常要与其它聚类方法相结合，如循环定位。 2）Hierarchical methods中比较新的算法有BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies利用层次方法的平衡迭代规约和聚类）主要是在数据量很大的时候使用，而且数据类型是numerical。首先利用树的结构对对象集进行划分，然后再利用其它聚类方法对这些聚类进行优化；ROCK（A Hierarchical Clustering Algorithm for Categorical Attributes）主要用在categorical的数据类型上；Chameleon（A Hierarchical Clustering Algorithm Using Dynamic Modeling）里用到的linkage是kNN（k-nearest-neighbor）算法，并以此构建一个graph，Chameleon的聚类效果被认为非常强大，比BIRCH好用，但运算复杂度很高，O(n^2)。 2、层次聚类的流程 凝聚型层次聚类的策略是先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类，它们只是在簇间相似度的定义上有所不同。这里给出采用最小距离的凝聚层次聚类算法流程： (1) 将每个对象看作一类，计算两两之间的最小距离； (2) 将距离最小的两个类合并成一个新类； (3) 重新计算新类与所有类之间的距离； (4) 重复(2)、(3)，直到所有类最后合并成一类。
KNN分类算法（理论）
目录 1.KNN算法 (1) 2.KNN算法描述 (1) 3.KNN主要的应用领域 (2) 4.KNN算法的优、缺点 (2)
1.KNN算法 KNN算法，右又叫K最邻近分类算法，是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。 KNN算法概括来说，就是已知一个样本空间里的部分样本分成几个类，然后，给定一个待分类的数据，通过计算找出与自己最接近的K个样本，由这K个样本投票决定待分类数据归为哪一类。kNN算法在类别决策时，只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，kNN方法较其他方法更为适合。 2.KNN算法描述 一个比较经典的KNN图如下： 从上图中我们可以看到，图中的有两个类型的样本数据，一类是蓝色的正方形，另一类是红色的三角形。而那个绿色的圆形是我们待分类的数据。 如果K=3，那么离绿色点最近的有2个红色三角形和1个蓝色的正方形，这3个点投票，于是绿色的这个待分类点属于红色的三角形。
如果K=5，那么离绿色点最近的有2个红色三角形和3个蓝色的正方形，这5个点投票，于是绿色的这个待分类点属于蓝色的正方形。 3.KNN主要的应用领域 文本分类、聚类分析、预测分析、模式识别、图像处理。 KNN算法不仅可以用于分类，还可以用于预测。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成反比。 4.KNN算法的优、缺点 优点 (1) 简单，易于理解，易于实现，无需估计参数，无需训练； (2) 适合对稀有事件进行分类； (3) 特别适合于多分类问题(multi-modal,对象具有多个类别标签)，kNN比SVM的表现要好。 缺点 (1) 当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。 (2) 计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。
算法综述 王宇航 (北京交通大学计算机与信息技术学院，北京，) 摘要：算法是著名的模式识别统计学方法，是最好的文本分类算法之一，在机器学习分类算法中占有相当大的地位，是最简单的机器学习算法之一。本文对算法及相关文献做一份汇总报告，详细介绍算法的思想、原理、实现步骤以及具体实现代码，并分析了算法的优缺点及其各种改进技术指导文件。本文还介绍了算法的发展历程、重要的发表的论文。本文在最后介绍了算法的应用领域，并重点说明其在文本分类中的实现。 关键字：算法。近邻算法。机器学习。文本分类 :, , , , . , , , , . , . , , . : , , , 1引言 分类是数据挖掘中的核心和基础技术，在经营、决策、管理、科学研究等多个领域都有着广泛的应用。目前主要的分类技术包括决策树、贝叶斯分类、分类、人工神经网络等。在这些方法中，分类是一种简单、有效、非参数的方法，现已经广泛应用于文本分类、模式识别、图像及空间分类等领域。本文从各个角度对算法进行较为全面的汇总报告。 本文的结构如下： 在第二部分，主要介绍算法的基本原理、思想、实现步骤、实现代码以及发展历程和经典论文。 第三部分是对算法的诸多不足之处进行的讨论，并给出一些改进的技术指导文件。 第四部分介绍的是算法如何处理多标签数据。 第五部分介绍了算法目前的主要应用领域，并着重说明了其在文本分类中的出色表现。 2算法简介 2.1算法引入 算法是机器学习里面比较简单的一个分类算法，整体思想比较简单：计算一个点与其他所有点之间的距离，取出与该点最近的个点，然后统计这个点里面所属分类比例最大的，则点属于该分类。下面用一个例子来说明一下：
KNN算法介绍与参数调优 K近邻法(k-nearest neighbors,KNN)是一种很基本的机器学习方法了，在我们平常的生活中也会不自主的应用。比如，我们判断一个人的人品，只需要观察他来往最密切的几个人的人品好坏就可以得出了。这里就运用了KNN的思想。KNN方法既可以做分类，也可以做回归，这点和决策树算法相同。 KNN做回归和分类的主要区别在于最后做预测时候的决策方式不同。KNN做分类预测时，一般是选择多数表决法，即训练集里和预测的样本特征最近的K个样本，预测为里面有最多类别数的类别。而KNN 做回归时，一般是选择平均法，即最近的K个样本的样本输出的平均值作为回归预测值。由于两者区别不大，虽然本文主要是讲解KNN的分类方法，但思想对KNN的回归方法也适用。由于scikit-learn里只使用了蛮力实现(brute-force)，KD树实现(KDTree)和球树(BallTree)实现，本文只讨论这几种算法的实现原理。 1. KNN算法三要素 KNN算法我们主要要考虑三个重要的要素，对于固定的训练集，只要这三点确定了，算法的预测方式也就决定了。这三个最终的要素是k值的选取，距离度量的方式和分类决策规则。 对于分类决策规则，一般都是使用前面提到的多数表决法。所以我们重点是关注与k值的选择和距离的度量方式。 对于k值的选择，没有一个固定的经验，一般根据样本的分布，选择一个较小的值，可以通过交叉验证选择一个合适的k值。 选择较小的k值，就相当于用较小的领域中的训练实例进行预测，训练误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是泛化误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合； 选择较大的k值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少泛化误差，但缺点是训练误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。 一个极端是k等于样本数m，则完全没有分类，此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单。 对于距离的度量，我们有很多的距离度量方式，但是最常用的是欧式距离，即对于两个n维向量x和y，两者的欧式距离定义为： 大多数情况下，欧式距离可以满足我们的需求，我们不需要再去操心距离的度量。 当然我们也可以用他的距离度量方式。比如曼哈顿距离，定义为： 更加通用点，比如闵可夫斯基距离(Minkowski Distance)，定义为：
k n n聚类算法基础知 识
精品文档 Knn(K最近邻分类算法) 1.简介: 邻近算法，或者说K最近邻(kNN，k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。 2.算法核心: kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 kNN方法在类别决策时，只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，kNN 方法较其他方法更为适合。 3.例子: 上图中，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。 4.算法核心思想: K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。 另外, KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成反比。 5优点: 1).简单，易于理解，易于实现，无需估计参数，无需训练； 2). 适合对稀有事件进行分类； 收集于网络，如有侵权请联系管理员删除
KNN算法总结 1 KNN分类算法 1.1KNN简述 K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别[1]。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。 KNN最邻近规则，主要应用领域是对未知事物的识别，即判断未知事物属于哪一类，判断思想是，基于欧几里得定理，判断未知事物的特征和哪一类已知事物的的特征最接近。 1.2 KNN原理 最近邻方法(k-nearest neighbor,简称kNN)是一种简洁而有效的非参数分类方法，是最简单的机器学习算法之一，该算法最初由Cover和Hart提出的，用于解决文本的分类问题。 K近邻算法是最近邻算法的一个推广。该规则将是一个测试数据点x分类为与它最接近的K个近邻中出现最多的那个类别。K近邻算法从测试样本点x开始生长，不断的扩大区域，直到包含进K个训练样本点为止，并且把测试样本点x 归为这最近的K个训练样本点中出现频率最大的类别。其中测试样本与训练样本的相似度一般使用欧式距离测量。 如果K值固定，并且允许训练样本个数趋向于无穷大，那么，所有的这K个
教 育 技 术 前 沿 讲 座 计算机科学学院 教育技术学01 41109020105 刘泽成
KNN - 简介 是K最邻近结点算法（k-Nearest Neighbor algorithm）的缩写形式，是电子信息分类器算法的一种。KNN方法对包容型数据的特征变量筛选尤其有效。 KNN - 算法描述 该算法的基本思路是：在给定新文本后，考虑在训练文本集中与该新文本距离最近（最相似）的 K 篇文本，根据这 K 篇文本所属的类别判定新文本所属的类别，具体的算法步骤如下： 一、:根据特征项集合重新描述训练文本向量 二、:在新文本到达后，根据特征词分词新文本，确定新文本的向量表示 三、:在训练文本集中选出与新文本最相似的 K 个文本，计算公式为： 【图】公式（1）-KNN 其中，K 值的确定目前没有很好的方法，一般采用先定一个初始值，然后根据实验测试的结果调整 K 值，一般初始值定为几百到几千之间。 四、:在新文本的 K 个邻居中，依次计算每类的权重，计算公式如下：【图】】公式（2）-KNN 其中， x为新文本的特征向量， Sim(x,di)为相似度计算公式，与上一步骤的计算公式相同，而y(di,Cj)为类别属性函数，即如果di 属于类Cj ，那么函数值为 1，否则为 0。 五、:比较类的权重，将文本分到权重最大的那个类别中。 除此以外，支持向量机和神经网络算法在文本分类系统中应用得也较为广泛，支持向量机的基本思想是使用简单的线形分类器划分样本空间。对于在当前特征空
间中线形不可分的模式，则使用一个核函数把样本映射到一个高维空间中，使得样本能够线形可分。 而神经网络算法采用感知算法进行分类。在这种模型中，分类知识被隐式地存储在连接的权值上，使用迭代算法来确定权值向量。当网络输出判别正确时，权值向量保持不变，否则进行增加或降低的调整，因此也称为奖惩法。 KNN - 不足 该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。因此可以采用权值的方法（和该样本距离小的邻居权值大）来改进。该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。 KNN - 图示 图示-KNN 右图中，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。 KNN - 主要应用领域
Knn(K最近邻分类算法) 1.简介: 邻近算法，或者说K最近邻(kNN，k-NearestNeighbor)分类算法是数据挖掘分 类技术中最简单的方法之一。所谓K最近邻，就是k个最近的邻居的意思，说的是每 个样本都可以用它最接近的k个邻居来代表。 2.算法核心: kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该 方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属 的类别。 kNN方法在类别决策时，只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域 的交叉或重叠较多的待分样本集来说，kNN方法较其他方法更为适合。 3.例子: 上图中，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果 K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。 4.算法核心思想: K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k 个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于 这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
关于KNN算法的理解及应用 K最近邻即KNN（k-Nearest Neighbor)分类算法是数据聚类中一种较为简单方便的方法。所谓K最近邻，假设每一类包含多个样本数据，而且没个数据有一个唯一的类标记表示这些样本是属于那一个分类，计算没个样本数据到待分类数据的距离，取和待分类数据最近的K个数据样本，那么这K个样本数据中哪个类别的样本数据占多数，则待分类数据就属于该类别。由此可见，KNN算法的核心思想是如果一个样本在特征空间中的K个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较为适合。 我们可以看两个简单的例子来了解一下KNN算法，如图附录1。列表中给出了七部曾经的风靡电影，可以看到该表统计了每部电影中的打斗次数及接吻次
数，并在最后一列对该电影进行了分类：动作电影抑或是爱情电影。通过观察可以发现，打斗次数多而接吻次数少的电影即被判别为动作电影，反之即为爱情电影，这符合正常的逻辑。对于第七部电影，电影名未知，但已知其中接吻及打斗次数，通过简单比较我们就可以判断出该电影属于动作电影。再看图附录2，图中的圆被决定属于哪个类，是三角形还是四方形？根据定义我们可以做简单的判断：当K=3时，由于三角形所占比例为2/3，故圆将被赋予三角形所在的类。当然我们也可以取K=5，此时四方形所占比例为3/5，故圆将被赋予四方形所在的类。 通过上述的两个例子我们可以总结下KNN算法的算法流程：1. 准备数据，对数据进行预处理；2. 选用合适的数据结构存储训练数据和测试元组；3. 设定参数，如K(K 值的确定目前没有很好的方法，一般采用先定一个初始值，然后根据实验测试的结果调整K 值}；4.维护一个大小为k的的按距离由大到小的优先级队列，用于存储最近邻训练元组。随机从训练元组中选取k个元组作为初始的最近邻元组，分别计算测试元组到这k个元组的距离，将训练元组标号和距离存入优先级队列；5. 遍历训练元组集，计算当前训练元组与测试元组的距离，将所得距离L 与优先级队列
机器学习算法基础知识 2016-03-27 数据玩家 在我们了解了需要解决的机器学习问题的类型之后，我们可以开始考虑搜集来的数据的类型以及我们可以尝试的机器学习算法。在本文中，小编会介绍一遍最流行的机器学习算法。通过浏览主要的算法来大致了解可以利用的方法是很有帮助的。 可利用的算法非常之多。困难之处在于既有不同种类的方法，也有对这些方法的扩展。这导致很快就难以区分到底什么才是正统的算法。在本文中，小编希望给你两种方式来思考和区分在这个领域中你将会遇到的算法。 第一种划分算法的方式是根据学习的方式，第二种则是基于形式和功能的相似性(就像把相似的动物归为一类一样)。两种方式都是有用的。 学习方式 基于其与经验、环境，或者任何我们称之为输入数据的相互作用，一个算法可以用不同的方式对一个问题建模。在机器学习和人工智能教科书中，流行的做法是首先考虑一个算法的学习方式。算法的主要学习方式和学习模型只有几个，我们将会逐一介绍它们，并且给出几个算法和它们适合解决的问题类型来作为例子。 ·监督学习：输入数据被称为训练数据，它们有已知的标签或者结果，比如垃圾邮件/非垃圾邮件或者某段时间的股票价格。模型的参数确定需要通过一个训练的过程，在这个过程中模型将会要求做出预测，当预测不符时，则需要做出修改。·无监督学习：输入数据不带标签或者没有一个已知的结果。通过推测输入数据中存在的结构来建立模型。这类问题的例子有关联规则学习和聚类。算法的例子包括Apriori算法和K-means算法。 ·半监督学习：输入数据由带标记的和不带标记的组成。合适的预测模型虽然已经存在，但是模型在预测的同时还必须能通过发现潜在的结构来组织数据。这类问题包括分类和回归。典型算法包括对一些其他灵活的模型的推广，这些模型都对如何给未标记数据建模做出了一些假设。 ·强化学习:输入数据作为来自环境的激励提供给模型，且模型必须作出反应。反馈并不像监督学习那样来自于训练的过程，而是作为环境的惩罚或者是奖赏。典型问题有系统和机器人控制。算法的例子包括Q-学习和时序差分学习（Temporal Difference Learning）。 当你处理大量数据来对商业决策建模时，通常会使用监督和无监督学习。目前一个热门话题是半监督学习，比如会应用在图像分类中，涉及到的数据集很大但是只包含极少数标记的数据。 算法相似性 通常，我们会把算法按照功能和形式的相似性来区分。比如树形结构和神经网络的方法。这是一种有用的分类方法，但也不是完美的。仍然有些算法很容易就可以被归入好几个类别，比如学习矢量量化，它既是受启发于神经网络的方法，又是基于实例的方法。也有一些算法的名字既描述了它处理的问题，也是某一类算法的名称，比如回归和聚类。正因为如此，你会从不同的来源看到对算法进行不同的归类。就像机器学习算法自身一样，没有完美的模型，只有足够好的模型。
各种聚类算法介绍及 对比
一、层次聚类 1、层次聚类的原理及分类 1）层次法（Hierarchical methods）先计算样本之间的距离。每次将距离最近的点合并到同一个类。然后，再计算类与类之间的距离，将距离最近的类合并为一个大类。不停的合并，直到合成了一个类。其中类与类的距离的计算方法有：最短距离法，最长距离法，中间距离法，类平均法等。比如最短距离法，将类与类的距离定义为类与类之间样本的最短距离。 层次聚类算法根据层次分解的顺序分为：自下底向上和自上向下，即凝聚的层次聚类算法和分裂的层次聚类算法（agglomerative和divisive），也可以理解为自下而上法（bottom-up）和自上而下法（top-down）。自下而上法就是一开始每个个体（object）都是一个类，然后根据linkage寻找同类，最后形成一个“类”。自上而下法就是反过来，一开始所有个体都属于一个“类”，然后根据linkage排除异己，最后每个个体都成为一个“类”。这两种路方法没有孰优孰劣之分，只是在实际应用的时候要根据数据特点以及你想要的“类”的个数，来考虑是自上而下更快还是自下而上更快。至于根据Linkage判断“类”的方法就是最短距离法、最长距离法、中间距离法、类平均法等等（其中类平均法往往被认为是最常用也最好用的方法，一方面因为其良好的单调性，另一方面因为其空间扩张/浓缩的程度适中）。为弥补分解与合并的不足，层次合并经常要与其它聚类方法相结合，如循环定位。 2）Hierarchical methods中比较新的算法有BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies利用层次方法的平衡迭代规约和聚类）主要是在数据量很大的时候使用，而且数据类型是numerical。首先利用树的结构对对象集进行划分，然后再利用其它聚类方法对这些聚类进行优化；ROCK（A Hierarchical Clustering Algorithm for Categorical Attributes）主要用在categorical的数据类型上；Chameleon（A Hierarchical Clustering Algorithm Using Dynamic Modeling）里用到的linkage是kNN（k-nearest-neighbor）算法，并以此构建一个graph，Chameleon的聚类效果被认为非常强大，比BIRCH好用，但运算复杂度很高，O(n^2)。 2、层次聚类的流程 凝聚型层次聚类的策略是先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类，它们只是在簇间相似度的定义上有所不同。这里给出采用最小距离的凝聚层次聚类算法流程： (1) 将每个对象看作一类，计算两两之间的最小距离； (2) 将距离最小的两个类合并成一个新类； (3) 重新计算新类与所有类之间的距离； (4) 重复(2)、(3)，直到所有类最后合并成一类。