感知机算法的原始形式:
import numpy as np class Perceptron(object): def __init__(self, n): """ :param n: the dimesion number of x :return: """ self.w = [] self.b = 0 for i in range (0, n): self.w.append(0) def calculate(self,sample): """ :param sample: [(x1,x2,..,xn), y] :return: the res of y(wx + b) """ res = 0 for i in range(0, len(sample[0])): res += sample[0][i] * self.w[i] res += self.b res = res * sample[1] return res def update(self, sample, step): """ :return: """ for i in range (0, len(self.w)): self.w[i] = self.w[i] + step * sample[0][i] * sample[1] self.b = self.b + step * sample[1] def run(self, samples, step): """ :param samples: the list of sample :return: false if there is a res is negative """ flag = True for i in range(0, len(samples)): sample = samples[i] if self.calculate(sample) <= 0: flag = False self.update(sample, step) return flag def perceptron(self, samples, step, max_run): """ :param samples: :param step: :param max_run: :return: """ for i in range(0, max_run): if self.run(samples, step): print "get the result success, after %d times" %(i) print "the w is %s" %(str(self.w)) print "the b is %d" %(self.b) return print "get the result failed" if __name__ == '__main__': samples = [[(3, 3), 1], [(4, 3), 1], [(1, 1), -1]] p = Perceptron(2) p.perceptron(samples, 1, 1000)
感知机的对偶形式:
import numpy as np class Perceptron(object): def __init__(self, n): """ :param n: the number of samples :return: """ self.alpha = np.zeros(n) self.b = 0 def get_gram(self, samples): n = len(samples) gram = np.zeros((n,n)) for i in range(0, len(samples)): for j in range(0, len(samples)): gram[i][j] = np.dot(samples[i][0], samples[j][0]) return gram def calculate(self, gram, samples, i): res = 0 for j in range(0, len(samples)): res += self.alpha[j] * samples[j][1] * gram[j][i] res += self.b res *= samples[i][1] return res def run(self, samples, step, gram): """ :param samples: :param step: :param gram: :return: """ flag = True for i in range(0, len(samples)): if self.calculate(gram, samples, i) <= 0: self.alpha[i] += step self.b += step * samples[i][1] flag = False return flag def get_w(self, samples): """ :param samples: :return: """ w = np.zeros(len(samples[0])) for i in range(0, len(samples)): w += np.dot(self.alpha[i] * samples[i][1], samples[i][0]) return w def perceptron(self, samples, step, run_times): gram = self.get_gram(samples) for i in range(0, run_times): if self.run(samples, step, gram): w = self.get_w(samples) print "calculate success!" print "the w is %s" %(str(w)) print "b is %d" %(self.b) return print "calculate failed!" if __name__ == '__main__': samples = [[(3, 3), 1], [(4, 3), 1], [(1, 1), -1]] p = Perceptron(3) p.perceptron(samples, 1, 1000)