前言
在K近邻的原始算法中，没有对K近邻的方法进行优化，还是遍历训练集，找到与输入实例最近的K个训练实例，统计他们的类别，以此作为输入实例类别的判断。具体的模型理论见：统计学习方法——K近邻法（原始方法）
1. K近邻算法的实现
在算法实现的过程中，利用的是欧氏距离进行点与点之间的距离度量。在进行数据运算的时候，没有利用numpy，而是利用Python中自带的list来进行数据的计算。
def
knn
(
x
,
dataSet
,
labels
,
k
)
:
distanceMemories
=
{
}
# 利用字典来记录距离
for
i
in
range
(
len
(
dataSet
)
)
:
distance
=
euDis
(
x
,
dataSet
[
i
]
)
distanceMemories
[
i
]
=
distance
sortResult
=
sorted
(
distanceMemories
.
items
(
)
,
key
=
lambda
x
:
x
[
1
]
)
distance_min_k
=
sortResult
[
:
k
]
classCount
=
{
}
# 用来记录前k个中各个类出现的次数
for
i
in
range
(
len
(
distance_min_k
)
)
:
if
labels
[
distance_min_k
[
i
]
[
0
]
]
not
in
classCount
:
classCount
[
labels
[
distance_min_k
[
i
]
[
0
]
]
]
=
0
classCount
[
labels
[
distance_min_k
[
i
]
[
0
]
]
]
+=
1
result
=
sorted
(
classCount
.
items
(
)
,
key
=
lambda
x
:
x
[
1
]
,
reverse
=
True
)
# 对统计结果，按照字典中的各个值，进行降序排序
return
result
[
0
]
[
0
]
def
euDis
(
x
,
y
)
:
# 欧式距离的计算
dim
=
len
(
x
)
temp
=
0
for
i
in
range
(
dim
)
:
temp
+=
(
x
[
i
]
-
y
[
i
]
)
**
2
return
temp
**
0.5
dataSet
=
[
[
3
,
104
]
,
[
2
,
100
]
,
[
1
,
81
]
,
[
101
,
10
]
,
[
99
,
5
]
,
[
98
,
2
]
]
# 这是机器学习实战一书上的小例子
labels
=
[
"爱情片"
,
"爱情片"
,
"爱情片"
,
"动作片"
,
"动作片"
,
"动作片"
]
print
(
knn
(
[
18
,
90
]
,
dataSet
,
labels
,
3
)
)
# 输出结果：爱情片
