基于Python实现KNN回归任务(人工智能实验)【100011919】

# 一、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 | | -------- | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | -