SVM的Map-Reduce數(shù)據(jù)挖掘算法
作者:kobeshow
SVM支持向量機,最近十五年機器學習界的明星算法,學術界也是各種研究,現(xiàn)今已經(jīng)達到一個瓶頸,屋漏偏逢連夜雨,隨著深度學習的雄起,SVM弄的一個人走茶涼的境遇(也許正是90年代神經(jīng)網(wǎng)絡的感受吧,呵呵),現(xiàn)在講一講關于SVM的并行。
由于原算法較難應用并行策略,而它的另一個算法變種-pegasos 適合并行,下面是該算法的過程。
初始化W=0(向量形式)
for i in t:
隨機選擇K個樣本
for j in K:
if 第j個樣本分錯
利用該樣本更新權重
累加W的更新
end for
下面是基于mrjob的map-reduce版
- class MRsvm(MRJob):
- DEFAULT_INPUT_PROTOCOL = 'json_value'
- #一些參數(shù)的設置
- def __init__(self, *args, **kwargs):
- super(MRsvm, self).__init__(*args, **kwargs)
- self.data = pickle.load(open('data_path'))
- self.w = 0
- self.eta = 0.69 #學習率
- self.dataList = [] #用于收集樣本的列表
- self.k = self.options.batchsize
- self.numMappers = 1
- self.t = 1 # 迭代次數(shù)
- def map(self, mapperId, inVals):
- #<key,value> 對應著 <機器mapperID,W值或者樣本特征跟標簽>
- if False: yield
- #判斷value是屬于W還是樣本ID
- if inVals[0]=='w':
- self.w = inVals[1]
- elif inVals[0]=='x':
- self.dataList.append(inVals[1])
- elif inVals[0]=='t': self.t = inVals[1]
- def map_fin(self):
- labels = self.data[:,-1]; X=self.data[:,0:-1]#解析樣本數(shù)據(jù)
- if self.w == 0: self.w = [0.001]*shape(X)[1] #初始化W
- for index in self.dataList:
- p = mat(self.w)*X[index,:].T #分類該樣本
- if labels[index]*p < 1.0:
- yield (1, ['u', index])#這是錯分樣本id,記錄該樣本的id
- yield (1, ['w', self.w]) #map輸出該worker的w
- yield (1, ['t', self.t])
- def reduce(self, _, packedVals):
- for valArr in packedVals: #解析數(shù)據(jù),錯分樣本ID,W,迭代次數(shù)
- if valArr[0]=='u': self.dataList.append(valArr[1])
- elif valArr[0]=='w': self.w = valArr[1]
- elif valArr[0]=='t': self.t = valArr[1]
- labels = self.data[:,-1]; X=self.data[:,0:-1]
- wMat = mat(self.w); wDelta = mat(zeros(len(self.w)))
- for index in self.dataList:
- wDelta += float(labels[index])*X[index,:] #更新W
- eta = 1.0/(2.0*self.t) #更新學習速率
- #累加對W的更新
- wMat = (1.0 - 1.0/self.t)*wMat + (eta/self.k)*wDelta
- for mapperNum in range(1,self.numMappers+1):
- yield (mapperNum, ['w', wMat.tolist()[0] ])
- if self.t < self.options.iterations:
- yield (mapperNum, ['t', self.t+1])
- for j in range(self.k/self.numMappers):
- yield (mapperNum, ['x', random.randint(shape(self.data)[0]) ])
- def steps(self):
- return ([self.mr(mapper=self.map, reducer=self.reduce,
- mapper_final=self.map_fin)]*self.options.iterations)
責任編輯:彭凡
來源:
YYGamer