Как создать набор оценок доверия для k-Nearest Neighbor Classification

Что я хочу:

Чтобы отобразить результаты моего простого алгоритма классификации (см. Ниже) в виде цветовой палитры на питоне (данные находятся в 2D), каждому классу присваивается цвет, а уверенность в предсказании в любом месте 2D-карты пропорциональна насыщенности цвета, связанного с предсказанием класса. Изображение ниже иллюстрирует то, что я хочу для двоичной (проблема двух классов), в которой красные части могут предложить сильную уверенность в классе 1, тогда как синие части будут говорить для класса 2. Промежуточные цвета могут указывать на неопределенность в отношении обоих. Очевидно, что я хочу, чтобы цветовая схема обобщала на несколько классов, поэтому мне понадобилось бы много цветов, и тогда масштаб переместился бы от белого (неопределенность) до очень яркого цвета, связанного с классом.

иллюстрация http://www.nicolacarlon.it/out.png

Некоторые примеры кода:

В моем примере кода используется простой алгоритм kNN, где ближайшим точкам k данных разрешено «голосовать» над классом новой точки на карте. Уверенность предсказания просто определяется относительной частотой победившего класса, из числа проголосовавших. Я не занимался связями, и я знаю, что существуют лучшие вероятностные версии этого метода, но все, что я хочу, – это визуализировать мои данные, чтобы показать зрителям вероятность того, что класс находится в определенной части 2D-плоскости.

import numpy as np import matplotlib.pyplot as plt # Generate some training data from three classes n = 100 # Number of covariates (sample points) for each class in training set. mean1, mean2, mean3 = [-1.5,0], [1.5, 0], [0,1.5] cov1, cov2, cov3 = [[1,0],[0,1]], [[1,0],[0,1]], [[1,0],[0,1]] X1 = np.asarray(np.random.multivariate_normal(mean1,cov1,n)) X2 = np.asarray(np.random.multivariate_normal(mean2,cov2,n)) X3 = np.asarray(np.random.multivariate_normal(mean3,cov3,n)) plt.plot(X1[:,0], X1[:,1], 'ro', X2[:,0], X2[:,1], 'bo', X3[:,0], X3[:,1], 'go' ) plt.axis('equal'); plt.show() #Display training data # Prepare the data set as a 3n*3 array where each row is a data point and its associated class D = np.zeros((3*n,3)) D[0:n,0:2] = X1; D[0:n,2] = 1 D[n:2*n,0:2] = X2; D[n:2*n,2] = 2 D[2*n:3*n,0:2] = X3; D[2*n:3*n,2] = 3 def kNN(x, D, k=3): x = np.asarray(x) dist = np.linalg.norm(xD[:,0:2], axis=1) i = dist.argsort()[:k] #Return k indices of smallest to highest entries counts = np.bincount(D[i,2].astype(int)) predicted_class = np.argmax(counts) confidence = float(np.max(counts))/k return predicted_class, confidence print(kNN([-2,0], D, 20)) 

Таким образом, вы можете рассчитать два числа для каждой точки двумерной плоскости

  • доверие (0 .. 1)
  • class (целое число)

Одна из возможностей – рассчитать собственную карту RGB и показать ее с помощью imshow . Как это:

 import numpy as np import matplotlib.pyplot as plt # color vector with N x 3 colors, where N is the maximum number of classes and the colors are in RGB mycolors = np.array([ [ 0, 0, 1], [ 0, 1, 0], [ 1, 0, 1], [ 1, 1, 0], [ 0, 1, 1], [ 0, 0, 0], [ 0, .5, 1]]) # negate the colors mycolors = 1 - mycolors # extents of the area x0 = -2 x1 = 2 y0 = -2 y1 = 2 # grid over the area X, Y = np.meshgrid(np.linspace(x0, x1, 1000), np.linspace(y0, y1, 1000)) # calculate the classification and probabilities classes = classify_func(X, Y) probabilities = prob_func(X, Y) # create the basic color map by the class img = mycolors[classes] # fade the color by the probability (black for zero prob) img *= probabilities[:,:,None] # reverse the negative image back img = 1 - img # draw it plt.imshow(img, extent=[x0,x1,y0,y1], origin='lower') plt.axis('equal') # save it plt.savefig("mymap.png") 

Трюк создания негативных цветов – это просто сделать математику немного легче раскрыть. Конечно, код может быть написан намного плотнее.

Я создал две очень простые функции, имитирующие классификацию и вероятности:

 def classify_func(X, Y): return np.round(abs(X+Y)).astype('int') def prob_func(X,Y): return 1 - 2*abs(abs(X+Y)-classify_func(X,Y)) 

Первое дает для заданной области целочисленные значения от 0 до 4, а последнее дает плавно меняющиеся вероятности.

Результат:

введите описание изображения здесь

Если вам не нравится, как цвета исчезают до нулевой вероятности, вы всегда можете создать некоторую нелинейность, которая применяется при умножении на вероятности.


Здесь функции classify_func и prob_func приводятся в виде двух массивов в качестве аргументов, во-первых, это координаты X, где должны вычисляться значения, а также вторая координата Y. Это хорошо работает, если базовые вычисления полностью векторизованы. С кодом в вопросе это не так, поскольку он только вычисляет одиночные значения.

В этом случае код немного меняется:

 x = np.linspace(x0, x1, 1000) y = np.linspace(y0, y1, 1000) classes = np.empty((len(y), len(x)), dtype='int') probabilities = np.empty((len(y), len(x))) for yi, yv in enumerate(y): for xi, xv in enumerate(x): classes[yi, xi], probabilities[yi, xi] = kNN((xv, yv), D) 

Кроме того, поскольку ваши оценки достоверности не равны 0..1, их необходимо масштабировать:

 probabilities -= np.amin(probabilities) probabilities /= np.amax(probabilities) 

После этого ваша карта должна выглядеть так: с помощью экстентов -4, -4..4,4 (в соответствии с цветовой картой: зеленый = 1, пурпурный = 2, желтый = 3):

Карта kNN


Векторизация или нет для векторизации – вот вопрос

Этот вопрос возникает время от времени. Существует много информации об векторизации в Интернете, но, поскольку быстрый поиск не выявил каких-либо коротких резюме, я приведу здесь несколько мыслей. Это довольно субъективный вопрос, поэтому все просто представляет мои скромные мнения. У других людей могут быть разные мнения.

Существует три фактора:

  • представление
  • разборчивость
  • использование памяти

Обычно (но не всегда) векторизация делает код быстрее, сложнее для понимания и потребляет больше памяти. Использование памяти обычно не является большой проблемой, но с большими массивами это о чем подумать (сотни мегабайт, как правило, в порядке, гигабайты неприятны).

Тривиальные случаи в сторону (элементарные простые операции, простые операции с матрицами), мой подход:

  • написать код без векторизации и проверить его работу
  • профайл код
  • векторизовать внутренние петли, если это необходимо и возможно (1D векторизация)
  • создать двумерную векторизацию, если она проста

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

Я такой паршивый алгоритмист, что в более сложных случаях мне нравится проверять мой векторизованный код на не-векторизованные версии. Следовательно, я почти всегда сначала создаю не-векторизованный код перед его оптимизацией.

Иногда векторизация не дает каких-либо преимуществ в производительности. Например, удобная функция numpy.vectorize может использоваться для векторизации практически любой функции, но в ее документации указано:

Функция векторизации предоставляется в первую очередь для удобства, а не для производительности. Реализация по существу является циклом for.

(Эта функция также могла быть использована в коде выше. Я выбрал версию цикла для удобочитаемости для людей, не очень знакомых с numpy .)

Векторизация дает большую производительность только в том случае, если базовые векторизованные функции быстрее. Они иногда бывают, иногда нет. Расскажет только профилирование и опыт. Кроме того, не всегда необходимо векторизовать все. У вас может быть алгоритм обработки изображений, который имеет как векторизованные, так и пиксельно-пиксельные операции. Там numpy.vectorize очень полезен.

Я попытался бы векторизовать алгоритм поиска kNN выше, по крайней мере, до одного измерения. Нет условного кода (это не будет шоу-стоппер, но это усложнит ситуацию), и алгоритм довольно прямолинейный. Потребление памяти будет расти, но с одномерной векторией это не имеет значения.

И может случиться так, что по пути вы заметите, что n-мерное обобщение не намного сложнее. Затем сделайте это, если позволяет память.