基于Python PLA 感知机学习方法【100011903】

## 人工智能实验 lab3 实验报告 ### PLA 感知机学习方法 #### 一、算法原理 PLA 是针对二元分类问题，它可以用来解决二维或者高维的**线性可分**问题。在二分类问题中，PLA 算法通过一个共享的权重向量$w=(w_1,w_2,...,w_d)$和某个样例的特征向量$x=(x_1,x_2,x_3...x_d)$ 做向量的内积，并通过与某个阈值$w_0$来比较大小，我们可以定义如果内积的结果大于阈值，就判为一类，反之则属于另外一类，就起到了二分类的效果。  为了方便我们的算法中使用矩阵的乘法运算，也方便优化或求导，我们可以把阈值转化成一个参数融入到权重向量中：  其中：  PLA 的算法步骤是： 1. 先将权重矩阵和阈值合并，并给每一个样本特征向量前加一个 1 2. 随机初始化一个权重矩阵 3. 计算每个样本点的特征向量和权重矩阵的乘积，然后判断是大于 0 还是小于 0（使用符号函数 `sign` 来计算）。遍历所有的样本点，如果找到一个预测错误的样本，就更新权重向量，直到所有的训练样本都预测正确。如果遇到错误的样本可以通过下面的式子对权重矩阵进行更新：  PLA 并不一定会停下来，因为如果数据存在噪声或者线性不可分的时候就会一直有错误的点，因此我们需要设置一个总的迭代次数来让算法停止。 4. 训练结束后我们会得到一个权重矩阵，我们通过这个权重矩阵和要预测的 x 做内积来预测它的标签 #### 二、伪代码 ```` procedure PLA_algorithm(data,w): // input: data 待训练的数据集样本点 // w 要训练的初始权重矩阵 // return: w 训练出的权重矩阵 iteration=15 for i in range(iteration): // PLA算法迭代iteration或者没有错误点的时候停止 isComplete=1 for point in data:// 遍历所有的样本点 res = point.dot(w) // 计算当前点和权重矩阵的点乘 if sign(res)=sigh(label) // 如果计算结果的符号和这个点原本的符号相同，就继续下个点 continue else: // 出现错误的点，更新权重向量w并立刻返回 w=w+label*x isComplete=False// 出现了错误的点，下次要继续迭代 if isComplete: // 如果遇到一次是没有错误点的就可以直接退出了 break return w ```` #### 三、代码展示 传统 PLA 算法： ````python def PLA_algorithm(data): ''' PLA算法，当算法迭代次数达到上限，或者没有错误的点的时候停止 ''' iteration=15 w = np.ones(len(data[0])) # 定义权重向量 count=0 for _ in range(iteration): # PLA算法迭代iteration或者没有错误点的时候停止 count+=1 isComplete=1 for point in data: # 遍历每个数据点不断更新w x=np.append(np.array([1]),point[:-1]) #在开头加一个1表示阈值 res = x.dot(w) if (point[-1]==1 and np.sign(res)==1) or (point[-1]==0 and np.sign(res)==-1) or res == 0: continue else: # 出现错误的点，更新权重向量w并立刻返回 w=w+(-np.sign(res))*x isComplete=False if isComplete: # 如果遇到一次是没有错误点的就可以直接退出了 break print("训练迭代了%d次"%(count)) return w ```` 对 PLA 算法进行升级口袋算法，因为口袋算法每次迭代要更新权重矩阵 W，如果线形不可分，在遍历数据集的时候如果开头几个点一直有错误，就一直利用不到后面的数据点，所以口袋算法采用了随机选取数据点，找到错误的点进行更新的方法： ````python def PLA_algorithm(data): ''' PLA算法，当算法迭代次数达到上限，或者没有错误的点的时候停止 ''' iteration=15 w = np.ones(len(data[0])) # 定义权重向量 count=0 for _ in range(iteration): # PLA算法迭代iteration或者没有错误点的时候停止 count+=1 isComplete=1 for point in data: # 遍历每个数据点不断更新w x=np.append(np.array([1]),point[:-1]) #在开头加一个1表示阈值 res = x.dot(w) if (point[-1]==1 and np.sign(res)==1) or (point[-1]==0 and np.sign(res)==-1) or res == 0: continue else: # 出现错误的点，更新权重向量w并立刻返回 w=w+(-np.sign(res))*x isComplete=False if isComplete: # 如果遇到一次是没有错误点的就可以直接退出了 break print("训练迭代了%d次"%(count)) return w ```` 训练完成后，我们会得到一个权重矩阵 W，我们可以利用这个权重矩阵来对我们划分的验证集进行验证： ````python def k_fold(dataSet,k,i): ''' 对数据集进行训练集和验证集的划分 :param dataSet: 数据集 :param k: 划分成k个部分 :param i: 选取第i个部分为验证集 :return: 返回训练和验证集的数据 ''' total = len(dataSet) step_len=total//k # 求出每一份的长度 val_begin=i*step_len val_end=val_begin+step_len return np.vstack((dataSet[:val_begin],dataSet[val_end:])),dataSet[val_begin:val_end] def validation(validation_set,w): count=0 total=validation_set.shape[0] for point in validation_set: # 遍历每个数据点不断更新w x=np.append(np.array([1]),point[:-1]) #在开头加一个1表示阈值 res = x.dot(w) if (point[-1]==1 and np.sign(res)==1) or (point[-1]==0 and np.sign(res)==-1) or res == 0: count+=1 print("PLA在验证集上的正确率为：%f"%(count/total)) ```` #### 四、 实验结果以及分析： 我尝试了 100 次迭代并统计每一次迭代后的在验证集上的准确率，作出的图像如下所示：  可以看到因为数据集不是线形可分的，所以 PLA 找不到一个最优的解，每次迭代更新了一次后，准确率就会波动，有可能上升也可能下降，因此可见 PLA 对于线形不可分的数据集表现并不是很出色。 再看口袋算法，每次迭代都随机选取一个点，如果是错误的就进行更正，并和当前的最好 w 进行对比，如果在训练集上表现更好，就替换原来的最好 w。可以看到，每次迭代后在验证集上的正确率一直是上升趋势，可见，口袋算法比起传统的 PLA 在非线形可分的数据集上有更好的表现效果。  #### 五、思考题： 1. 有什么手段可以让 PLA 适用于非线形可分的数据集： 对于非线形可分的数据集，传统 PLA 算法不会停下来，因为一直会有错误的点，如果我们仅仅是设置迭代次数让它停下来的话，我们这一次纠正了这个点，下一次纠正另外一个点的时候，有可能导致前一个点有变成错误的的点了。所以 P