一、前言

本篇是面向机器学习基石第一次作业而言。

15-20题都是需要编程实现才能正确做出选择。

前面14个选择题，我觉得题目出得并不好。这里就不再多说。主要面向最后的LPA和pocket算法的实现。

代码对应的gitee地址

二、PLA算法实现

数据集中每个样本都是的$X$都是四维向量$[x_1,x_2,x_3,x_4]$，对应y = {1， -1}

1. 按照数据集给定的顺序更新算法

def pla(datas):size = len(datas)if size <= 1:return;err_i = -1  # 标记当前用于更新的data行dms = len(datas[0])if dms == 0:return;w = [0 for x in range(0, dms)]run_times = 0last_pause = sizenow = 0while True:run_times = run_times + 1 # 整个数据循环的圈数while now != last_pause:    # 转一圈之后，两个碰在一起p = 0now %= size # 当前在size中的位置for x in range(0, dms-1):p += w[x] * datas[now][x]p += w[-1]if p <= 0 and datas[now][-1] > 0 or p >0 and datas[now][-1] < 0:err_i = nowlast_pause = err_iif last_pause == 0:last_pause == sizenow += 1breaknow += 1# 更新w（w_0放在末尾）if err_i != -1:for x in range(0, dms - 1):w[x] += datas[err_i][-1]*datas[err_i][x]w[-1] += datas[err_i][-1]err_i = -1else:break;return [w, run_times]

其中需要是last_pause是当前最后错误的位置，如果从当前错误的位置转了一圈又回到这里而没有遇到其他错误的更新点的时候，说明已经更新完毕。

2. 随机访问数据的顺序更新算法

# 永远保证当前时刻是[0,n)
# 每次交换当前i的随机的数
def randomIndex(n):index = [i for i in range(0,n)]def swap(l,x,y):l[x] = l[x]+l[y]l[y] = l[x] - l[y]l[x] = l[x] - l[y]for i in range(0,n):swap(index,i,int(random.random()*n))return indexdef plaImproved(datas,n = 1):size = len(datas)if size<=1:return;err_i = -1dms = len(datas[0])if dms == 0:return;para = [0 for x in range(0,dms)]run_times = 0index = randomIndex(size)last_pause = sizei = 0while True:#if run_times>=50:#breakrun_times+=1#for i in range(0, size):while i != last_pause:p = 0i %= sizefor x in range(0, dms - 1):p += para[x] * datas[index[i]][x]p += para[-1]if p <= 0 and datas[index[i]][-1] > 0 or p > 0 and datas[index[i]][-1] < 0:#ignore datas[i][-1] == 0err_i = index[i]break; #遇到错误推出循环i+=1if err_i != -1:for x in range(0, dms - 1): #用这个错误来更新参数para[x] = para[x]+ n* datas[err_i][-1] * datas[err_i][x]  # update the parameterspara[-1] += n * datas[err_i][-1]last_pause = iif last_pause == 0:last_pause = sizei+=1err_i = -1;else:break;return [para,run_times]

注意

1. 所谓improved版本的PLA，主要是实现利用打乱的后的index来作为更新顺序。
2. 更改权重w：会影响到最终的效果。但是从最终结果来看，平均更新次数差不多。
   $$W_{t+1}=W_t+w\ast y_n(t)X_n(t)$$

三、Pocket算法实现

def pocket(datas, max_time=50, greedy=1):size=len(datas)if size <= 1:returnerr_i = -1dms = len(datas[0])if dms == 0:returnw = [0 for x in range(0,dms)]new_w = [0 for x in range(0,dms)]new_error = 0last_error = sizerun_times = 0while True:index = randomIndex(size)if run_times>max_time:breakrun_times += 1for i in range(0, size):p = 0for x in range(0, dms-1):p += new_w[x]*datas[index[i]][x]p += new_w[-1]if p <= 0 and datas[index[i]][-1] > 0 or p > 0 and datas[index[i]][-1] < 0:#ignore datas[i][-1] == 0err_i = index[i]breakif err_i != -1:for x in range(0, dms - 1): #用这个错误来更新参数new_w[x] += datas[err_i][-1] * datas[err_i][x]  # update the parametersnew_w[-1] += datas[err_i][-1]if greedy == 1:           for i in range(0, size):p = 0for x in range(0, dms-1):p += new_w[x]*datas[index[i]][x]p += new_w[-1]if p <= 0 and datas[index[i]][-1] > 0 or p > 0 and datas[index[i]][-1] < 0:#ignore datas[i][-1] == 0new_error += 1if (new_error < last_error):w = copy.deepcopy(new_w)    # 如果不是deepcopy，就等于只是引用last_error = new_errornew_error = 0err_i = -1else: breakif greedy == 0:return [new_w, run_times]else:return [w, run_times]

注意事项

1. python中的拷贝：使用deepcopy才能真正实现我们想要的拷贝
2. 更新次数的提升，会降低错误分类的比例。100次更新time比50次要好1%左右
3. 就50次更新而言，使用pocket比直接使用更新后的w效果好，大约1%左右

四、算法可视化

随机生成二维平面[0-20]的点：

def random2DDatas(num):result = []g1 = [random.random()*20,random.random()*20]g2 = [random.random()*20,random.random()*20]# 由数据范围内的两个点来确定分割线，保证划分线一定会经过生成的点的范围w = [(g1[1] - g2[1])/(g1[0] -g2[0]),-1,g1[1] - (g1[1] - g2[1])/(g1[0] -g2[0])*g1[0]]result.append(w) # 完美分割线for i in range(num):x = [random.random()*20,random.random()*20]y = w[0]*x[0]+w[1]*x[1]+w[2]if y<0:x.append(-1)elif y>0:x.append(1)else:continue#print(x,y)result.append(x)return result

调用PLA算法，并做可视化：

def visualizePLA(all,w = []):x = np.linspace(0,20,50)  # 在1到10之间产生50组数据(数据之间呈等差数列)y = - all[0][2]/all[0][1]  - all[0][0]/all[0][1]*x  # 最开始的线plt.figure()plt.plot(x,y,color="black")if len(w)!=0:z = - w[2] / w[1] - w[0] / w[1] * xplt.plot(x,z,color="orange",linestyle="--")posx = []posy = []negx = []negy = []for i in  range(1,len(all)):if all[i][-1] == -1:negx.append(all[i][0])negy.append(all[i][1])else:posx.append(all[i][0])posy.append(all[i][1])plt.scatter(negx,negy,marker='x',c='r')plt.scatter(posx,posy,marker='o',c='g')plt.show()

最终效果：