# 一、KNN回归任务
## 1. 算法原理
在本题中，一共有六项数值需要进行回归预测，anger, disgust, fear, joy, sad, surprise的数值作为样本的结果。同样，首先将训练样本进行TF-IDF编码后进行预测。并依据上一题中详细解释过的KNN算法和Lp算法得到K个与测试样本距离最近的训练样本。但是与分类任务不同的是，回归任务不能通过投票预测结果，而是需要另外的算法得到回归结果：
假设通过KNN算法得出了K个与测试样本最相近的训练样本，分别记为$train_1,train_2,...,trian_K$，用$d(train_1,test)$表示$train_1$和测试样本之间的Lp距离，$prob$表示某个回归值，则有：
$$
\displaystyle prob(test)=\sum_{k=1}^K\frac{prob(train_k)}{d(train_k,test)}
$$
即测试样本的某项回归值等于`K`个训练样本的回归值除以该训练样本与测试样本之间的Lp距离之商的和。
这样得出来的结果之和可能不为1，而依据题目要求，六种概率之和必须为1，因此可以对六种数据做以下处理：
$$
\displaystyle porb_i=\frac{prob_i}{\sum^6_{j=1}prob_j}
$$
也就是每个概率都除以六个概率之和，本质上是对六种概率进行相同的线性变化，使得六者的和相加为1。
与分类问题不同的是，回归问题的预测结果不可能和实际结果完全准确，为了使得结果更加精确，引入下面的指标相关系数作为判断预测结果和实际结果差距的依据。
$$
COR(X,Y)=\frac{cov(X,Y)}{\sigma_X\sigma_Y}=\frac{\sum^n_{i=1}(X_i-\overline X)(Y_i-\overline Y)}{\sqrt{\sum^n_{i=1}(X_i-\overline X)^2\sum^n_{i=1}(Y_i-\overline Y)^2}}
$$
本题中的结果有六个概率值。先分别计算六个维度上的真实概率值和预测概率值的相关系数，然后对六个维度取平均，计算得到最终相关系数作为判断依据。相关系数的绝对值越大，预测值和真实值的线性相关程度就越好。
-----
## 2. 伪代码
首先创建TF-IDF矩阵，并且通过KNN算法和Lp距离找出和测试样本最近的`K`个训练样本。和之前的一样，不再重复说明。
找到`K`个训练样本后，根据这些样本的标签对测试样本的回归值进行预测：
```pseudocode
for 每种要预测的概率 i
i = 0
for eachSentence in KNN最近邻
i = i + eachSentence的i值 / eachSentence的Lp距离
end
end
```
得到了每个要预测的回归值后，还需要将这些值归一化，即使得这些概率的和为1。
```pseudocode
每种概率值 = 每种概率值 / 所有概率值之和
```
只要将每种概率值除以所有概率之和，这时所有概率相加为：原来的所有概率之和/原来的所有概率之和=1。
------
## 3. 代码展示
### 3.1 测试流程
生成TF-IDF的矩阵的代码和上述内容相同，不再重复展示。
之后开始测试，以验证集为例。声明下面的函数并进行相关数据的初始化：
```python
def valid(tf_idf, idf, emt, sentenceCount):
#整个验证集预测的6个概率
predictAnger = []
predictDisgust = []
predictFear = []
predictJoy = []
predictSad = []
predictSurprise = []
#整个验证集实际的6个概率
trueAnger = []
trueDisgust = []
trueFear = []
trueJoy = []
trueSad = []
trueSurprise = []
```
接下来打开验证集文件。
```python
with open("validation_set.csv","r")as validSet:
for eachLine in validSet:
s = eachLine.split(',') # 依据逗号拆分每个验证样本
sentence = s[0].split(' ') # 验证样本的文档
s[-1] = s[-1][0:-1] # 将最后的回车去掉
emotion = s[1:7] # 文档对应的6种概率
if emotion[0] == 'anger': # 排除测试集的第一行
continue
for i in range(0, 6):
emotion[i] = float(emotion[i]) # 将概率大小由字符串转为浮点数
```
得到了文档对应的实际的六种概率则可以加入上述列表中：
```python
trueAnger.append(emotion[0])
trueDisgust.append(emotion[1])
trueFear.append(emotion[2])
trueJoy.append(emotion[3])
trueSad.append((emotion[4]))
trueSurprise.append(emotion[5])
```
接着是对`K`个最近邻的查找，通过`findSimSentence`函数完成。得到后调用`predict`函数得到六种预测的概率，再调用`standard`函数将六个概率标准化，即使得六种概率之和为1。这几个函数的详细代码会在之后讨论。其中`findSimSentence`和第二题完全相同，不再展示代码。需要注意的是，为了防止之后出现计算概率时除以0的情况，距离`diff`需要设置最小值。
```python
simSentence = {}
findSimSentence(sentenceCount, tf_idf, idf, sentence ,simSentence, K) #查找最近邻
predictEmt = predict(simSentence, emt) # 依据最近邻预测概率
standard(predictEmt) # 将概率标准化
```
得到了预测的六种概率之后，也分别加入对应的列表中。
```python
predictAnger.append(predictEmt[0])
predictDisgust.append(predictEmt[1])
predictFear.append(predictEmt[2])
predictJoy.append((predictEmt[3]))
predictSad.append(predictEmt[4])
predictSurprise.append(predictEmt[5])
```
有了所有验证样本的实际结果和预测结果组成的六个向量（列表）后，调用`cor`函数计算六个相关系数，并求平均值输出。
```python
print((cor(predictAnger,trueAnger)+cor(predictDisgust,trueDisgust)+cor(predictFear,trueFear)+cor(predictJoy,trueJoy)+cor(predictSad,trueSad)+cor(predictSurprise,trueSurprise))/6)
```
### 3.2 概率值的计算
计算出K个最近邻后，调用以下函数计算六种概率的预测值：
```python
def predict(simSentence, emt):
predictEmt = [0 for i in range(0,6)] # 大小为6的向量，分别对应六种情绪的预测概率值
for i in range(0,6):
for eachSentence in simSentence.keys():
# 概率预测值 = 所有最近邻的概率/Lp距离之和
predictEmt[i] = predictEmt[i] + emt[eachSentence][i]/simSentence[eachSentence]
return predictEmt
```
得到六种概率的预测值后，调用下面的函数将其标准化：
```python
def standard(predictEmt):
total = sum(predictEmt)
for i in range(0,6):
predictEmt[i] /= total
```
求得所有概率值之和，并将所有概率除以该值即可。
### 3.3 相关系数的计算
```python
def cor(x, y):
avgX = sum(x)/len(x) # x的平均值
avgY = sum(y)/len(y) # y的平均值
tmp1 = 0.0 # tmp1用于计算相关系数的分母
tmp2 = 0.0 # tmp2用于计算x的标准差
tmp3 = 0.0 # tmp3用于计算y的标准差
for i in range(0,len(x)):
# 依据公式计算变量值
tmp1 = tmp1 + (x[i]-avgX)*(y[i]-avgY)
tmp2 = tmp2 + (x[i]-avgX)*(x[i]-avgX)
tmp3 = tmp3 + (y[i]-avgY)*(y[i]-avgY)
tmp1 = abs(tmp1)
return tmp1/math.sqrt(tmp2*tmp3)
```
-----
## 4. 实验结果及分析
同样对`K`和`p`进行调整，具体结果如下：
当`p=2`时，对K调优：
| K值 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| -------- | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ |
| 相关系数 | 0.3070 | 0.3445 | 0.3544 | 0.3562 | 0.3540 | 0.3709 | 0.3621 | 0.3535 | 0.3472 | 0.3516 |
| K值 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| -------- | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | -
Python是实现的人工智能实验之KNN回归任务.zip （10个子文件） 
knnre 
设计报告.docx 122KB 3. KNN_regression 
main.py 5KB tf_idf.py 2KB 18340057_ HuTingxi_KNN_regression.csv 37KB LICENSE 1KB README.md 9KB 3 test_set.csv 17KB train_set.csv 42KB validation_set.csv 22KB regression_simple_test.csv 233B资源评论
