基于k-近邻算法的室内WiFi位置指纹定位实验报告

k-近邻算法（KNN）
简单地说，k-近邻算法采用测量不同特征值之间的距离方法进行分类。
优点：精度高、对异常值不敏感、无数据输入假定。
缺点：计算复杂度高、空间复杂度高。
适用数据范围：数值型和标称型。
算法原理：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中数据对应的特征进行比较，然后算法提取样本集中特征值最相似数据（最近邻）的分类标签。一般来说，我们只选取样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后选择k个相似数据中出现次数最多的分类，作为新数据的分类。

采样方法
本组分别在食堂三层以及文实429教室进行数据采集。
食堂三层，以四根柱子将区域分成6块，采用6个AP在每个区域采集20条数据，共计120条数据。示意图及具体数据，如下所示。

AP1 AP2 AP3 AP4 AP5 AP6 区域
64 57 59 52 41 39 4
63 57 56 58 38 36 4
62 64 56 49 40 37 1
62 65 64 56 42 43 1
61 55 36 42 57 54 2
61 56 57 58 51 43 4
61 54 53 56 52 46 4
61 54 55 56 48 49 4
61 61 58 62 41 44 4
61 60 59 63 37 37 4
60 56 57 55 32 44 1
60 61 56 55 50 55 1
60 53 54 57 42 33 4
59 53 50 58 39 37 4
58 60 59 63 39 46 1
58 58 58 60 40 43 1
58 61 58 55 47 47 1
58 65 57 57 39 36 1
58 57 59 55 40 44 4
58 54 56 57 40 40 4
57 56 60 56 33 41 1
57 50 38 39 53 55 2
57 62 61 60 46 36 4
56 57 50 52 48 41 1
56 54 49 44 51 48 2
56 66 44 44 57 63 2
56 54 54 60 46 45 4
56 58 54 64 43 38 4
55 52 43 40 52 56 1
55 50 45 45 56 56 1
55 58 58 52 44 42 1
55 62 69 56 43 40 1
55 62 59 56 37 47 1
55 48 49 43 63 63 2
55 53 43 44 47 49 2
55 56 45 50 48 48 5
55 51 43 56 43 46 5
55 46 52 44 44 51 5
54 59 62 57 44 49 1
54 56 54 52 47 47 1
54 55 61 54 34 45 1
54 51 51 46 48 56 2
54 49 39 44 52 55 2
54 41 43 47 52 58 3
54 61 52 52 48 48 4
54 55 49 57 38 41 4
54 49 54 56 45 43 4
54 59 45 54 46 43 4
54 60 53 57 48 44 5
54 53 45 57 47 45 5
54 48 62 62 71 71 6
54 43 64 58 72 69 6
53 57 54 55 49 47 1
53 48 42 43 55 62 2
53 57 42 45 51 46 2
53 48 55 53 64 64 3
53 54 49 49 40 43 4
52 53 53 57 44 46 1
52 50 40 43 53 53 2
52 45 61 54 70 54 5
51 50 44 39 58 56 2
51 48 33 44 59 57 2
51 50 58 56 64 63 3
51 46 57 54 66 70 3
51 55 50 56 46 41 4
51 47 59 58 68 66 6
50 47 51 46 59 61 3
50 44 59 61 67 68 3
50 44 57 51 62 66 3
50 52 43 51 40 45 5
50 49 45 44 48 53 5
50 44 53 51 51 58 5
49 51 48 49 50 57 2
49 50 52 50 49 50 2
49 47 37 40 54 54 2
49 49 62 55 64 66 6
48 44 54 48 63 67 3
48 44 63 63 61 63 6
47 50 44 46 49 54 2
47 49 53 47 54 57 2
47 50 59 53 63 65 3
46 39 56 52 64 63 3
46 45 59 51 65 66 3
46 48 66 59 65 66 3
46 45 51 49 61 56 5
45 49 47 52 45 61 2
45 47 49 55 52 53 5
45 47 58 59 65 61 5
45 51 61 63 67 60 6
45 38 60 54 65 66 6
44 41 61 63 57 56 3
44 47 62 63 60 65 3
44 40 56 58 66 60 6
43 44 54 50 57 58 3
43 41 49 53 57 67 3
43 40 55 55 63 63 3
43 39 51 53 62 59 3
43 44 43 51 57 52 5
43 44 61 55 65 61 6
43 46 60 60 62 60 6
43 37 50 54 63 61 6
42 51 42 42 60 55 2
42 34 54 57 60 58 6
42 35 57 62 66 66 6
42 38 50 57 56 56 6
41 38 53 53 57 59 5
41 40 55 60 61 59 5
41 39 53 57 59 55 5
40 40 51 57 57 60 5
39 43 59 49 60 64 3
39 39 57 59 63 60 3
39 42 48 54 54 59 5
39 46 52 57 56 61 6
38 41 44 55 56 56 5
38 40 48 57 59 58 6
37 45 49 59 60 56 5
37 38 58 57 65 61 6
36 38 46 52 61 61 6
33 43 56 59 65 60 6
30 46 52 60 63 61 6

文实429教室数据采集，初期分成10个区域效果不好，最终将10区减少为5区，即每一列为一区，而不是原来的每一桌为一区，将错误率减少了20%，但由于选取的范围仍然差异较小，所以文实组实验错误率较高。选取5个AP，每个区域采集24条数据，共计120条数据。

AP1 AP2 AP3 AP4 AP5 区域
67 65 44 35 61 2
68 63 42 40 54 1
68 69 40 40 62 2
69 67 39 40 59 2
66 62 40 40 58 2
69 62 45 40 59 2
62 62 42 40 59 2
65 64 43 41 93 2
70 69 47 41 63 2
66 68 45 43 61 1
68 67 48 43 51 1
70 64 42 44 64 1
62 61 48 44 72 5
66 61 47 45 62 2
65 58 50 45 56 3
74 65 50 46 65 1
70 68 45 46 60 1
65 64 44 46 63 2
66 65 44 46 66 3
64 68 41 47 61 1
67 71 48 47 57 1
67 68 43 47 57 2
60 66 47 47 64 3
60 64 42 47 62 3
68 72 43 48 62 1
65 68 50 48 62 1
66 64 46 48 62 3
62 59 50 48 61 3
69 71 49 49 59 1
62 63 48 49 66 3
61 56 45 49 66 3
51 52 56 49 69 5
65 67 44 50 56 2
66 71 45 50 68 3
67 61 46 50 64 3
59 55 52 50 69 4
55 58 51 50 69 4
61 54 52 50 74 5
52 57 49 51 69 3
57 59 55 51 65 4
54 54 52 51 68 5
68 57 50 52 65 3
58 57 51 52 67 4
60 58 49 52 65 4
56 56 48 52 69 5
64 64 48 53 54 1
56 53 50 53 73 4
56 58 53 53 70 4
52 61 54 53 64 4
55 56 54 53 73 5
56 56 52 53 71 5
56 53 48 53 72 5
67 67 54 54 73 4
67 67 54 54 73 4
52 51 51 54 75 5
53 61 54 55 71 5
53 53 50 55 68 5
57 52 59 56 67 4
50 49 56 56 69 5
57 58 57 57 74 4
57 58 53 57 74 4
52 58 57 57 68 4
64 53 58 57 69 5
43 41 70 58 65 2
45 48 67 58 67 3
52 49 61 58 63 4
43 48 63 59 59 2
57 49 60 59 59 3
52 49 61 59 69 3
56 56 53 59 72 5
54 53 58 59 75 5
43 43 63 60 59 2
49 50 71 60 69 3
54 50 64 60 62 3
54 55 61 60 72 4
64 62 58 60 77 5
40 45 65 61 60 2
41 45 83 61 64 2
50 50 64 61 64 3
65 55 57 61 71 4
51 48 61 61 62 4
49 55 52 61 69 5
41 45 74 62 61 1
38 47 63 62 59 2
48 49 65 62 65 3
56 45 58 62 69 4
52 49 64 62 65 4
54 49 56 62 68 5
51 56 54 62 67 5
56 54 60 62 74 5
60 55 57 62 68 5
46 47 62 63 61 1
48 48 62 63 64 3
48 46 63 63 67 3
46 52 61 63 66 3
44 47 67 63 64 3
54 53 53 63 67 4
59 66 62 63 75 5
56 53 60 63 74 5
44 41 71 64 60 1
46 41 67 64 62 2
42 49 65 64 58 2
42 48 68 64 62 3
46 49 65 65 65 2
40 40 70 65 64 2
59 59 53 65 67 4
46 45 63 66 64 1
54 50 59 66 73 4
50 43 64 67 62 1
47 41 65 67 59 1
55 52 59 67 68 4
55 66 60 67 72 5
38 40 72 68 58 1
51 43 71 69 60 1
41 45 65 69 48 1
45 51 64 69 64 2
38 46 64 69 63 2
44 48 66 70 65 1
42 51 70 73 51 1
54 49 65 74 52 1

在训练算法的过程中，分别选取不同比例的数据作为训练集和测试集，同时在k取不同值时，最终结果亦不同。两个实验场所，共进行80次实验，实验条件如下所。

食堂组：共51组实验

文实429组：共39组实验

实验结果
食堂组最优结果如下，正确率79.2%。


文实429组最优结果如下，正确率58.4%，且有三组实验皆能取得最优成果。




实验分析
从结果上看食堂组的实验结果更加理想，经组内讨论分析，这可能与数据采集区域规则程度、大小等因素有关，食堂组划分的区域更加接近正方形，且区域面积更大，相对采集点密度降低，分布也更加均匀，从而最后的实验结果也更为理想。同时，由于对于编程的不熟悉，本次小组采用的编码程序可能存在考虑因素遗漏的情况，成为本次实验的局限之处。
未来实验的改进可以从代码优化以及数据科学采集两方面入手，从而使实验结果更加理想。最后附上本次实验的编码程序。

小组成员：伍秋晨、薛睿、许雪梅、杨涵月、赵鑫