RSS订阅
交换友链|关于我们
猫友运动|猫友图库
当前位置：Python在线学习 > python专区 > Python技术分享 > 正文

用Python实现K近邻算法

文章目录 [ 隐藏 ]

K近邻算法简介

什么是K近邻算法

K近邻算法简称kNN，kNN算法的模型就是整个训练数据集。当需要对一个未知数据实例进行预测时，kNN算法会在训练数据集中搜寻k个最相似实例。对k个最相似实例的属性进行归纳，将其作为对未知实例的预测。

相似性度量依赖于数据类型。对于实数，可以使用欧式距离来计算。其他类型的数据，如分类数据或二进制数据，可以用汉明距离。

对于回归问题，会返回k个最相似实例属性的平均值。对于分类问题，会返回k个最相似实例属性出现最多的属性。

kNN如何工作？

kNN属于基于实例算法簇的竞争学习和懒惰学习算法。

基于实例的算法运用数据实例（或数据行）对问题进行建模，进而做出预测决策。kNN算法算是基于实例方法的一种极端形式，因为其保留所有的训练集数据作为模型的一部分。

kNN是一个竞争学习算法，因为为了做出决策，模型内部元素（数据实例）需要互相竞争。 数据实例之间客观相似度的计算，促使每个数据实例都希望在竞争中“获胜”或者尽可能地与给定的未知数据实例相似，继而在预测中做出贡献。

懒惰学习是指直到需要预测时算法才建立模型。它很懒，因为它只在最后一刻才开始工作。优点是只包含了与未知数据相关的数据，称之为局部模型。缺点是，在大型训练数据集中会重复相同或相似的搜索过程，带来昂贵的计算开销。

最后，kNN的强大之处在于它对数据不进行任何假设，除了任意两个数据实例之间距离的一致计算。因此，它被称为成为无参数或者非线性的，因为它没有预设的函数模型。

使用测量值对鸢尾花分类

原始数据集由来自3个品种鸢尾花的150个观察结果组成。对每一朵花有四个测量值：萼片长度、萼片宽度、花瓣长度、花瓣宽度，单位都是厘米。待预测鸢尾花属于Setosa，Versicolour，Virginica三个种类之一。

这是一个标准的数据集，所有示例的种类都是已知的。因此我们可以将数据集分割成训练数据集和测试数据集，并使用预测结果来评估实现的算法。这个问题，比较好的分类算法的准确度在90%以上，通常为96%甚至更好。

你可以从iris.data上免费下载数据集，更多细节见参考资料部分。

怎样用Python实现k-Nearest Neighbors

本教程将KNN算法分为如下几步：

数据处理：打开CSV文件获取数据，将原始数据分为测试集/训练集。

相似性度量：计算每两个数据实例之间的距离。

近邻查找：找到k个与当前数据最近的邻居。

结果反馈：从近邻实例反馈结果。

精度评估：统计预测精度。

主函数：将上述过程串起来。

1. 数据处理

我们首先要做的是把文件中的数据加载进来。这些数据以CSV形式存放在文件中，不包含header行和其它任何引用。我们可以使用open函数打开这些文件，然后使用csv module中的reader函数去读取文件。

1
2
3
4
5
import csv
with open('iris.data', 'rb') as csvfile:
    lines = csv.reader(csvfile)
    for row in lines:
        print(', '.join(row))

接下来，我们需要将这些数据拆分为kNN用于做预测的训练集(training dataset)和用来评估模型精度的测试集(test dataset)。

首先，我们需要将以字符串形式载入的鸢尾花测量数据转换为容易处理的数组。接下来，我们需要将数据集随机的分为训练集与测试集。通常训练集/测试集的划分比例标准为67/33。

将上述步骤合在一起，我们可以定义一个叫loadDataset的函数，该函数可以加载指定的CSV文件，并按照指定的比例随机分为训练集与测试集。

1
2
3
4
5
6
7
8
9
10
11
12
13
import csv
import random
def loadDataset(filename, split, trainingSet=[] , testSet=[]):
    with open(filename, 'rb') as csvfile:
        lines = csv.reader(csvfile)
        dataset = list(lines)
        for x in range(len(dataset)-1):
            for y in range(4):
                dataset[x][y] = float(dataset[x][y])
            if random.random() < split:
                trainingSet.append(dataset[x])
            else:
                testSet.append(dataset[x])

将鸢尾花数据集的csv文件下载到本地目录，我们可以用鸢尾花数据集按照如下方式测试这个函数：

1
2
3
4
5
trainingSet=[]
testSet=[]
loadDataset('iris.data', 0.66, trainingSet, testSet)
print 'Train: ' + repr(len(trainingSet))
print 'Test: ' + repr(len(testSet))

2.相似性度量

为了进行预测我们需要计算任意两个数据实例的相似性。这是必要的，因为对于给定的每一个测试集中的数据实例，我们都可以在训练集中找出k个相似性最高的数据实例，这样就可以依次进行预测。

假定鸢尾花的4个测量数据都为数值形式且单位相同，我们可以直接采用欧氏距离(Euclidean distance)进行相似性度量。欧式距离定义为：两组向量对应元素之差的平方和再做平方根运算。

另外，我们要控制哪个字段参与欧式距离的计算。具体来讲，我们只想包括前四个属性。一种方法是采用固定长度的向量来限制欧式距离，忽略最后的维度。

将上述步骤合在一起，我们可以将euclideanDistance函数定义为：

1
2
3
4
5
6
import math
def euclideanDistance(instance1, instance2, length):
    distance = 0
    for x in range(length):
        distance += pow((instance1[x] - instance2[x]), 2)
    return math.sqrt(distance)

我们可以用一些样本数据来测试这个函数，具体如下：

1
2
3
4
data1 = [2, 2, 2, 'a']
data2 = [4, 4, 4, 'b']
distance = euclideanDistance(data1, data2, 3)
print 'Distance: ' + repr(distance)

3. 近邻查找

由于我们有相似性度量的方法，因此可以采用该方法寻找未知数据实例的k个相似性最高的实例。

处理过程直接计算所有样本点到给定点的欧式距离，进而筛选距离最近的样本点子集。

下面是getNeighbors函数，该函数遍历训练集并返回与测试实例距离最近的k个近邻样本点（采用已经定义好的euclideanDistance函数）。

1
2
3
4
5
6
7
8
9
10
11
12
import operator
def getNeighbors(trainingSet, testInstance, k):
    distances = []
    length = len(testInstance)-1
    for x in range(len(trainingSet)):
        dist = euclideanDistance(testInstance, trainingSet[x], length)
        distances.append((trainingSet[x], dist))
    distances.sort(key=operator.itemgetter(1))
    neighbors = []
    for x in range(k):
        neighbors.append(distances[x][0])
    return neighbors

我们可以按如下方法来测试这个函数：

1
2
3
4
5
trainSet = [[2, 2, 2, 'a'], [4, 4, 4, 'b']]
testInstance = [5, 5, 5]
k = 1
neighbors = getNeighbors(trainSet, testInstance, 1)
print(neighbors)

4. 结果反馈<、h3>

我们已经找到了测试实例的最近的邻居，下一步就是基于这些近邻做出预测结果。

我们可以让每个邻居对测试实例的类别属性进行投票，最终以票数多者做为预测结果。

下面的函数提供了从近邻投票中反馈多数投票结果的机制。该函数假定每个邻居的最后一列为类别属性。

1
2
3
4
5
6
7
8
9
10
11
import operator
def getResponse(neighbors):
    classVotes = {}
    for x in range(len(neighbors)):
        response = neighbors[x][-1]
        if response in classVotes:
            classVotes[response] += 1
        else:
            classVotes[response] = 1
    sortedVotes = sorted(classVotes.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedVotes[0][0]

我们可以输入近邻数据测试该函数，结果如下：

1
2
3
neighbors = [[1,1,1,'a'], [2,2,2,'a'], [3,3,3,'b']]
response = getResponse(neighbors)
print(response)

5. 精度评估

我们已经具备了所有的kNN算法片段。还有一件事情仍需我们重点关注，那就是就是如何评估预测精度。

评估模型精度最简单的方法就是计算正确预测结果数量占全部预测结果数量的比例，称为分类精度。

下面是getAccuracy函数，该函数统计所有的正确预测并返回正确分类的百分比精度。

1
2
3
4
5
6
def getAccuracy(testSet, predictions):
    correct = 0
    for x in range(len(testSet)):
        if testSet[x][-1] is predictions[x]:
            correct += 1
    return (correct/float(len(testSet))) * 100.0

我们可以采用测试集与预测结果来测试该函数，结果如下：

1
2
3
4
testSet = [[1,1,1,'a'], [2,2,2,'a'], [3,3,3,'b']]
predictions = ['a', 'a', 'a']
accuracy = getAccuracy(testSet, predictions)
print(accuracy)

6. 主函数

目前为止，我们已经具备了所有的算法组成元素，下面我们将这些元素串起来，组成主函数。

下面是从零开始实现的kNN算法完整Python代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
# Example of kNN implemented from Scratch in Python
 
import csv
import random
import math
import operator
 
def loadDataset(filename, split, trainingSet=[] , testSet=[]):
    with open(filename, 'rb') as csvfile:
        lines = csv.reader(csvfile)
        dataset = list(lines)
        for x in range(len(dataset)-1):
            for y in range(4):
                dataset[x][y] = float(dataset[x][y])
            if random.random() &lt; split:
                 trainingSet.append(dataset[x])
             else:
                 testSet.append(dataset[x])
def euclideanDistance(instance1, instance2, length):
    distance = 0
    for x in range(length):
        distance += pow((instance1[x] - instance2[x]), 2)
    return math.sqrt(distance)
def getNeighbors(trainingSet, testInstance, k):
    distances = []
    length = len(testInstance)-1
    for x in range(len(trainingSet)):
        dist = euclideanDistance(testInstance, trainingSet[x], length)
        distances.append((trainingSet[x], dist))
    distances.sort(key=operator.itemgetter(1))
    neighbors = []
    for x in range(k):
        neighbors.append(distances[x][0])
    return neighbors
def getResponse(neighbors):
    classVotes = {}
    for x in range(len(neighbors)):
        response = neighbors[x][-1]
        if response in classVotes:
            classVotes[response] += 1
        else:
            classVotes[response] = 1
    sortedVotes = sorted(classVotes.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedVotes[0][0]
def getAccuracy(testSet, predictions):
    correct = 0
    for x in range(len(testSet)):
        if testSet[x][-1] == predictions[x]:
            correct += 1
    return (correct/float(len(testSet))) * 100.0
def main():
    # prepare data
    trainingSet=[]
    testSet=[]
    split = 0.67
    loadDataset('iris.data', split, trainingSet, testSet)
    print 'Train set: ' + repr(len(trainingSet))
    print 'Test set: ' + repr(len(testSet))
    # generate predictions
    predictions=[]
    k = 3
    for x in range(len(testSet)):
        neighbors = get
        Neighbors(trainingSet, testSet[x], k)
     result = getResponse(neighbors)
     predictions.append(result)
     print('&gt; predicted=' + repr(result) + ', actual=' + repr(testSet[x][-1]))
    accuracy = getAccuracy(testSet, predictions)
    print('Accuracy: ' + repr(accuracy) + '%')
 
main()

运行上述实例代码，你将会看到每一项预测分类结果和与之对应的测试集的实际分类结果。在运行的结尾，你将会看到整个模型的预测精度。当前的实例的预测精度略高于98%。

1
2
3
4
5
6
7
...
> predicted='Iris-virginica', actual='Iris-virginica'
> predicted='Iris-virginica', actual='Iris-virginica'
> predicted='Iris-virginica', actual='Iris-virginica'
> predicted='Iris-virginica', actual='Iris-virginica'
> predicted='Iris-virginica', actual='Iris-virginica'
Accuracy: 98.0392156862745%

未经允许不得转载：Python在线学习 » 用Python实现K近邻算法

赞 (3)

猜你喜欢

来吐槽吧 0

取消
  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址