K-近邻算法
k-近邻算法简单、直观：给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类。
优点：精度高、对异常值不敏感、无数据输入假定。
缺点：计算复杂度高、空间复杂度高。
适用数据范围：数值型和标称型（只在有限目标集中取值，如真与假，常用于分类问题。）。
K-近邻算法
Python实现
- 使用Python导入数据
def createDataSet():
'''
创建带标签的数据集
:return: 返回训练集和标签
'''
# 4*2的特征变量矩阵
group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
labels = ['A', 'A', 'B', 'B']
return group, labels
group矩阵包含4组数据，向量labels包含了每个数据点的标签信息。此处，我们将数据点(1, 1.1)和(1, 1)定义为类A，将数据点(0, 0)和(0, 0.1)定义为类B。
- 实施KNN分类算法
算法伪代码如下：
(1) 计算已知类别数据集中的点与当前点之间的距离；
(2) 按照距离递增次序排列；
(3) 选取与当前点距离最小的k个点；
(4) 确定前k个点所在类别的出现频率；
(5) 返回前k个点出现频率最高的类别作为当前点的预测分类。
def classify0(inX, dataSet, labels, k):
'''
KNN算法
:param inX: 用于分类的输入向量
:param dataSet: 训练集
:param labels: 标签向量
:param k: 用于选择最近邻居的数目
:return: 返回分类类别
'''
# 距离计算
dataSetSize = dataSet.shape[0] # 读取dataSet的第一维长度
diffMat = tile(inX, (dataSetSize, 1)) - dataSet
sqDiffMat = diffMat ** 2
sqDistances = sqDiffMat.sum(axis=1) # 对矩阵的每一行求和
distances = sqDistances ** 0.5
# 将数据按照距离从小到大排序
sortedDistIndicies = distances.argsort()
classCount = {}
# 选择距离最小的k个点
for i in range(k):
voteIlabel = labels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
# 按照字典的第二个元素的大小对排序，此为逆序
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
- 测试代码
if __name__ == '__main__':
# KNN算法实现
group, labels = createDataSet()
label = classify0([0, 0], group, labels, 3)
print label
测试结果为：
B
因简书不支持Latex语法，可以访问本人CSDN博客查看，谢谢！
