s0plete vector machines

svm.py

# -*- coding: utf-8 -*-

import numpy
import cvxopt


cvxopt.solvers.options['show_progress'] = False


class SVMClassifier(object):

    def __init__(self, kernel=None):
        if kernel is None:
            kernel = self._default_kernel()
        self.kernel = kernel
        self.data = None
        self.b = None

    def fit(self, X, Y):
        assert len(X) == len(Y)

        X = numpy.array(X)
        Y = numpy.array(Y)

        n = len(X)
        K = numpy.zeros((n, n))
        for i in range(n):
            for j in range(n):
                K[i, j] = self.kernel(X[i], X[j])

        P = cvxopt.matrix(numpy.outer(Y, Y) * K)
        q = cvxopt.matrix(numpy.ones(n) * -1)
        A = cvxopt.matrix(Y, (1, n))
        b = cvxopt.matrix(0.0)
        G = cvxopt.matrix(numpy.diag(numpy.ones(n) * -1))
        h = cvxopt.matrix(numpy.zeros(n))

        solution = cvxopt.solvers.qp(P, q, G, h, A, b)
        self.data = []
        for i, alfa in enumerate(solution["x"]):
            if alfa > 1e-5:  # This simulates non-zero
                label = Y[i]
                support_vector = X[i]
                self.data.append((i, support_vector, label, alfa))

        self.b = 0
        indexes = numpy.array([i for i, _, _, _ in self.data])
        alfas = numpy.array([alfa for _, _, _, alfa in self.data])
        labels = numpy.array([label for _, _, label, _ in self.data])
        for i, support_vector, label, alfa in self.data:
            self.b += label
            self.b -= numpy.sum(alfas * labels * K[i, indexes])
        self.b /= len(alfas)

    def predict(self, X):
        if self.data is None:
            message = "This classifier is not trained, are you threatening me??"
            raise Exception(message)

        Y = []
        for unknown in X:
            proj = sum([alfa * y * self.kernel(unknown, spvector)
                        for i, spvector, y, alfa in self.data])
            value = proj + self.b
            Y.append(numpy.sign(value))
        return numpy.array(Y)


    def _default_kernel(self):
        n = 2

        def linear(xi, xj):
            return numpy.dot(xi, xj)

        def poly(xi, xj):
            return (numpy.dot(xi, xj) + 1) ** n

        return poly

if __name__ == "__main__":
    X = numpy.array([(0, 0), (1, 1), (1, 2), (3, 3), (4, 4), (20, 20)])
    Y = numpy.array([float(x) for x in [1, -1, -1, 1, 1, 1]])

    classifier = SVMClassifier()
    classifier.fit(X, Y)

    X = [(0, 1), (25, 25)]
    print(classifier.predict(X))