# parallel-knn

**Repository Path**: liukun06/parallel-knn

## Basic Information

- **Project Name**: parallel-knn
- **Description**: The implemention of knn with parallel framework
- **Primary Language**: Java
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2017-06-01
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

#parallel-knn

## 如何运行代码

1. clone 代码： git clone git@git.oschina.net:liukun06/parallel-knn.git

2. 将代码使用Maven项目导入eclipse或者IDEA中

3. 数据文件在：parallel-knn/parallel/src/main/resources 目录中

4. 两个主类分别为：

**edu.algorithm.knn.parallel.impl.KNNSerial**串行KNN实现

**edu.algorithm.knn.parallel.impl.KNNParallel**并行KNN实现

## 实验结果与内容

KNN的串行实现与并行实现的性能比较
### 实验数据

训练数据：3.5万条

测试数据：1.5万条

数据属性：14个float类型

### 实验环境

win10

8核

### 实验结果

**并行实验**

实验1：并行KNN实现，改变K值，固定Threshold（表示将最多将多少个测试数据分成一个线程进行并行计算）

|实验编号|K|Threshold|时间/ms|
|------|----|----|----|
|1|10|1000|108602|
|2|50|1000|109297|
|3|200|1000|109784|
|4|1000|1000|109443|
|5|2000|1000|108118|
|6|4000|1000|105828|

通过数据可以得出结论，当threshold固定的时候（并行程度固定）K值基本不会影响最终计算所需要的时间。

实验2：并行KNN实现，改变threshold，固定K值

|实验编号|K|Threshold|时间/ms|
|------|----|----|----|
|1| 10 | 250 |93539|
|2| 10 |500|96742|
|3| 10 |1000|112195|
|4| 10 |2000|134812|
|5| 10 |3000|135464|
|6| 10 |5000|238331|
|7| 10 |8000|452831|

通过实验数据可以发现，当threshold越小，说明并行程度越高，消耗的时间也越少。当threshold=8000的时候，1.5万的测试数据只能分成两组进行并行计算（只能用到PC机器8个处理器其中的两个)。

**串行实验**

实验1：串行KNN实现，改变K值

|实验编号|K|Threshold|时间/ms|
|------|----|----|----|
|1| 10 | * |906042|
|2| 100 |*|908042|
|3| 200 |*|909042|

通过实验可以发现串行实验中改变K值并不影响最后计算的使用时间。


**实验结论**：在并行KNN实验中，通过调整threshold来改变并行程度从而充分使用更多的处理器可以加速计算，减少运行时间。并且当充分利用8个处理器的时候耗时约为串行的1/8.