Это дополнение к серии Давайте понятно объясним, в котором я демонстрирую, как кодировать упомянутые модели на питоне с нуля. Если вы не знакомы с КНН, прочитайте мой рассказ по теме:
Данные:
Сначала нам нужно получить наши данные. Хотя я не использую какие-либо расширенные библиотеки для построения модели, такие как sklearn, я собираюсь использовать ее для создания набора данных Iris в целях тестирования. (На практике набор данных будет импортирован из вашего фактического источника)
from sklearn import datasets
import numpy as np
iris = datasets.load_iris()
sepalLength = iris.data[:,0]
sepalWidth = iris.data[:,1]
petalLength = iris.data[:,2]
petalWidth = iris.data[:,3]
## Reducing 4 dimensional data to 2: x = width*height
## Also keeping in a (n, 2) shape of numpy array
X = np.hstack([(petalLength*petalWidth).reshape(iris.data.shape[0],1), \
(sepalLength*sepalWidth).reshape(iris.data.shape[0],1)])
y = iris.target # Labels
## Generate an unknown labeled datapoint
## Assuring same shape as X: (m, 2)
newData = np.array([8,19]).reshape(1,2)
«X» содержит наш набор данных 150x2, включающий 50 из каждых 3 категорий меток. Каждая точка данных содержит информацию о двух функциях: PetalWidth*PetalHeight и SepalWidth*SepalHeight. «y» содержит 3 метки 150 точек данных, и мы сгенерировали «newData» неизвестной точки данных с меткой. Наша неизвестная радужка имеет значения PetalWidth*PetalHeight = 8 и SepalWidth*SepalHeight = 19.
Модель:
Наша цель — найти ближайшие точки данных Iris относительно наших «новых данных» и подсчитать, какая метка появляется чаще. Сначала мы должны рассчитать каждое расстояние до каждой из 150 точек данных.
def getDistances(X, newData, p=2):
distances = []
for x in X:
## Minkowsky method with variable parameter
## (defaulting to p=2 -> Eucledian)
distance = sum(abs(x-newData)**p)**(1/p)
distances.append(distance)
return np.array(distances) ## Converting to numpy array
## Calculate a numpy array of each distance
distances = getDistances(X, newData[0])
Теперь, когда мы знаем, как далеко наши «новые данные» расположены относительно нашего набора данных, мы должны выбрать ближайших «К» соседей.
def getNeighbors(distances, k):
return np.argsort(distances)[:k] ## Indexes of the neighbors
print(X.shape[0]**0.5) ## -> 12.2475
neighbors = getNeighbors(distances, 13)
Как я отметил в своей истории KNN, мы определяем K как нечетное число, близкое к квадратному корню из размера нашей выборки: 13. Наш результат соседи содержит индексы 13 ближайших соседей. Остается только последний шаг — проверить метки этих соседей и сделать прогноз.
def predict(y, neighbors):
labels = y[neighbors] ## Slice for neighbors
## Create a Dict of each label and calculate proportions
probs = {label:(labels==label).sum()/labels.shape[0] for label in np.unique(y)}
return probs
pred = predict(y, neighbors)
## -> {0: 0, 1: 0.6154, 2: 0.3846}
Мы видим, что 61,54% соседей помечены как «1», а остальные 38,46% помечены как «2», поэтому мы классифицируем наши «новые данные» как «1». Ниже вы можете увидеть весь программный код вместе:
from sklearn import datasets
import numpy as np
def getDistances(X, newData, p=2):
distances = []
for x in X:
## Minkowsky method with variable parameter (defaulting to p=2 -> Eucledian)
distance = sum(abs(x-newData)**p)**(1/p)
distances.append(distance)
return np.array(distances) ## Converting to numpy array
def getNeighbors(distances, k):
return np.argsort(distances)[:k]
def predict(y, neighbors):
labels = y[neighbors] ## Slice for neighbors
## Create a Dict of each label and calculate proportions
probs = {label:(labels==label).sum()/labels.shape[0] for label in np.unique(y)}
return probs
### Load Data
iris = datasets.load_iris()
sepalLength = iris.data[:,0]
sepalWidth = iris.data[:,1]
petalLength = iris.data[:,2]
petalWidth = iris.data[:,3]
## Reducing 4 dimensional data to 2: x = width*height
## Also keeping in a (n, 2) shape of numpy array
X = np.hstack([(petalLength*petalWidth).reshape(iris.data.shape[0],1), \
(sepalLength*sepalWidth).reshape(iris.data.shape[0],1)])
y = iris.target # Labels
newData = np.array([8,19]).reshape(1,2)
distances = getDistances(X, newData[0])
print(X.shape[0]**0.5) ## -> 12.2475
neighbors = getNeighbors(distances, 13)
pred = predict(y, neighbors)
## -> {0: 0, 1: 0.6153, 2: 0.3846}
В поисках лучшего К
В качестве дополнительной темы я расскажу о методе поиска оптимизированного K для нашего набора данных. Идея, лежащая в основе этого, состоит в том, чтобы итеративно выбирать каждую из 150 точек данных в качестве наших «новых данных» (таким образом, мы будем знать их истинную метку) и прогнозировать их на основе разных значений «К». После этого мы можем измерить точность модели в каждом сценарии.
k_accuracy = {}
for K in range(1,100): ## Iterating through K = 1 to 100
accuracy = 0
for i, newData in enumerate(X): ## Iterating through each datapoint
tempX = np.delete(X, i, 0) ## Remove our "newData" from the dataset
distances = getDistances(tempX, newData)
neighbors = getNeighbors(distances, K)
probs = predict(y, neighbors)
pred = max(probs, key=probs.get) ## Get the label with max probability
accuracy += pred == y[i] ## Increment accuracy if managed to predict successfully
k_accuracy[K] = accuracy / tempX.shape[0]
plt.scatter(x=k_accuracy.keys(), y=k_accuracy.values())
best_K = max(k_accuracy, key=k_accuracy.get) ## Get Best K
print(best_K, k_accuracy[best_K])
## -> 9, 0.9732
Наилучший (но не единственный) K оказался равным 9 с точностью 97,32%. График хорошо показывает, что слишком большое увеличение K может снизить точность. Кроме того, K = 12 и 13 также имеют точность 97,32%, поэтому кажется, что использование эмпирического правила (квадратный корень из n) является эффективным методом.
