Быстрый подсчет значений признаков в наивном байесовском классификаторе - PullRequest
Новая
       6

Быстрый подсчет значений признаков в наивном байесовском классификаторе

0 голосов
/ 24 октября 2018

Я реализую наивный байесовский классификатор в Python (как часть университетского задания, поэтому Python является обязательным требованием).Я получил его на работу, и он дает примерно тот же результат, что и sklearn.naive_bayes.MultinomialNB.Однако это очень медленно по сравнению с реализацией sklearn.

Предположим, что значения объектов являются целыми числами в диапазоне от 0 до max_i, а метки классов также являются целыми числами в диапазоне от 0 до max_y.Пример набора данных выглядит следующим образом: 

>>> X = np.array([2,1 1,2 2,2 0,2]).reshape(4,2) # design matrix
>>> print(X)
[[2 1]
 [1 2]
 [2 2]
 [0 2]]
>>> y = np.array([0,  1,  2,  0  ]) # class labels
>>> print(y)
[0 1 2 0]

Теперь, в качестве промежуточного шага, прежде чем работать с вероятностью совместного журнала, мне нужно вычислить условные вероятности класса (то есть P(x_ij | y) так, чтобы матрица ccl содержалавероятность значения k в признаке j данного класса C. Вывод такой матрицы для приведенного выше примера будет: 

>>> print(ccl)
[[[0.5 0.  0.5]
  [0.  0.5 0.5]]

 [[0.  1.  0. ]
  [0.  0.  1. ]]

 [[0.  0.  1. ]
  [0.  0.  1. ]]]
>>> print(ccl[0][1][1]) # prob. of value 1 in feature 1 given class 0
0.5

Код, который я реализовал для достижения этой цели, выглядит следующим образом: 

N, D = X.shape
K = np.max(X)+1
C = np.max(y)+1
ccl = np.zeros((C,D,K))
# ccl = ccl + alpha - 1 # disregard the dirichlet prior for this question
# Count occurences of feature values given class c
for i in range(N):
    for d in range(D):
        ccl[y[i]][d][X[i][d]] += 1
# Renormalize so it becomes a probability distribution again
for c in range(C):
    for d in range(D):
        cls[c][d] = np.divide(cls[c][d], np.sum(cls[c][d]))

Так как цикл Python медленный, это также становится медленным. Я попытался смягчить эту проблему путем горячего кодирования каждого значения свойства (поэтому, если значения объекта находятся в диапазоне [0,1,2], 2 становится: [0,0,1] и т. Д.) И суммируем так: хотя, я думаю, слишком много np-функций вызывается, поэтому вычисление все равно занимает слишком много времени: 

ccl = np.zeros((C,D,K))
for c in range(C):
    x = np.eye(K)[X[np.where(y==c)]] # one hot encoding
    ccl[c] += np.sum(x, axis=0) # summing up
    ccl[c] /= ccl[c].sum(axis=1)[:, numpy.newaxis] # renormalization

Это приведет ктот же вывод, что и выше. Любые советы о том, как сделать это быстрее? Я думаю, что np.eye (однократное кодирование) не нужно и убивает его, но я не могу придумать, как избавиться от него. И последнееЯ считаюкрасный использует np.unique() или collections.Counter для подсчета, но еще не понял.

1 Ответ

0 голосов
/ 24 октября 2018

Так что это довольно аккуратная проблема (и у меня была похожая проблема не так давно ).Похоже, что самый быстрый способ справиться с этим, как правило, состоит в том, чтобы создать индексный массив, используя только арифметические операции, а затем сложить его и изменить его с помощью np.bincount. 

N, D = X.shape
K = np.max(X) + 1
C = np.max(y) + 1
ccl = np.tile(y, D) * D * K + (X +  np.tile(K * range(D), (N,1))).T.flatten()
ccl = np.bincount(ccl, minlength=C*D*K).reshape(C, D, K)
ccl = np.divide(ccl, np.sum(ccl, axis=2)[:, :, np.newaxis])

>>> ccl
array([[[0.5, 0. , 0.5],
        [0. , 0.5, 0.5]],

       [[0. , 1. , 0. ],
        [0. , 0. , 1. ]],

       [[0. , 0. , 1. ],
        [0. , 0. , 1. ]]])

. Для сравнения по скорости funca - ваш первый метод на основе цикла, funcb - ваш второй метод на основе функции numpy, а funcc - метод, использующий bincount.

X = np.random.randint(3, size=(10000,2))
y = np.random.randint(3, size=(10000))
>>> timeit.timeit('funca(X,y)', number=100, setup="from __main__ import funca, X, y")
2.632569645998956
>>> timeit.timeit('funcb(X,y)', number=100, setup="from __main__ import funcb, X, y")
0.10547748399949342
>>> timeit.timeit('funcc(X,y)', number=100, setup="from __main__ import funcc, X, y")
0.03524605900020106

Возможно, это можно уточнить, но у меня больше нет хороших идей.

...