<jupyter_start><jupyter_text>**K-Nearest Neighbor** Table of Content:* Description of KNN Algorithm* Advantages* Disadvantages* KNN Algorithm* Step 1: Calculate Euclidean Distance.* Step 2: Get Nearest Neighbors.* Step 3: Make Predictions.* Step 2: Get Nearest Neighbors.* Step 3: Make Predictions.* Implement KNN Algorithm using Sklearn* References---**Description:** **The K-Nearest Neighbor** (KNN) is a non-parametric, lazy learning algorithm. Its purpose is to use a database in which the data points are separated into several classes to predict the classification of a new sample point. **Advantages:** *   Simple algorithm — to explain and understand/interpret.*   High accuracy (relatively) — it is pretty high but not competitive in comparison to better supervised learning models.*   Versatile — useful for classification or regression.**Disadvantages:***   Computationally expensive — because the algorithm stores all of the training data.*   High memory requirement.*   Stores all (or almost all) of the training data Prediction stage might be slow.*   Sensitive to irrelevant features and the scale of the data.**KNN Algorithm:**kNN Algorithm is broken down into 3 parts:1.   Calculate Euclidean Distance.2.   Get Nearest Neighbors.3.   Make Predictions. **Step 1: Calculate Euclidean Distance**Euclidean Distance between points p and q is the length of the line segment connecting them.In Cartesian coordinates, if p = (p1, p2,..., pn) and q = (q1, q2,..., qn) are two points in Euclidean n-space, then the distance (d) from p to q, or from q to p is given by the Pythagorean formula:$$d(p,q)=\sqrt{\sum_{i=0}^n (qi-pi)^2}$$``` calculate the Euclidean distance between two vectorsdef euclidean_distance(row1, row2):	distance = 0.0	for i in range(len(row1)-1):		distance += (row1[i] - row2[i])**2	return sqrt(distance)```<jupyter_code># Example of calculating Euclidean distance
from math import sqrt
 
# calculate the Euclidean distance between two vectors
def euclidean_distance(row1, row2):
	distance = 0.0
	for i in range(len(row1)-1):
		distance += (row1[i] - row2[i])**2
	return sqrt(distance)
 
# Test distance function
dataset = [[2.7810836,2.550537003,0],
          [1.465489372,2.362125076,0],
          [3.396561688,4.400293529,0],
          [1.38807019,1.850220317,0],
          [3.06407232,3.005305973,0],
          [7.627531214,2.759262235,1],
          [5.332441248,2.088626775,1],
          [6.922596716,1.77106367,1],
          [8.675418651,-0.242068655,1],
          [7.673756466,3.508563011,1]]
row0 = dataset[0]
print(row0)
distance = [euclidean_distance(row0, row) for row in dataset]
print(distance)<jupyter_output>[2.7810836, 2.550537003, 0]
[0.0, 1.3290173915275787, 1.9494646655653247, 1.5591439385540549, 0.5356280721938492, 4.850940186986411, 2.592833759950511, 4.214227042632867, 6.522409988228337, 4.985585382449795]<jupyter_text>**Step 2: Get Nearest Neighbors.**Once distances are calculated from distance function prepared above, we must sort all of the records in the training dataset by their distance to the new data. We can then select the top k to return as the most similar neighbors.``` Locate the most similar neighborsdef get_neighbors(train, test_row, num_neighbors):	distances = list()	for train_row in train:		dist = euclidean_distance(test_row, train_row)		distances.append((train_row, dist))	distances.sort(key=lambda tup: tup[1])	neighbors = list()	for i in range(num_neighbors):		neighbors.append(distances[i][0])	return neighbors  ```<jupyter_code># Example of getting neighbors for an instance
from math import sqrt
 
# calculate the Euclidean distance between two vectors
def euclidean_distance(row1, row2):
	distance = 0.0
	for i in range(len(row1)-1):
		distance += (row1[i] - row2[i])**2
	return sqrt(distance)
 
# Locate the most similar neighbors
def get_neighbors(train, test_row, num_neighbors):
  
	distances = list()
	for train_row in train:
		dist = euclidean_distance(test_row, train_row)
		distances.append((train_row, dist))
	distances.sort(key=lambda tup: tup[1])
 
	neighbors = list()
	for i in range(num_neighbors):
		neighbors.append(distances[i][0])
	return neighbors
 
# Test distance function
dataset = [[2.7810836,2.550537003,0],
          [1.465489372,2.362125076,0],
          [3.396561688,4.400293529,0],
          [1.38807019,1.850220317,0],
          [3.06407232,3.005305973,0],
          [7.627531214,2.759262235,1],
          [5.332441248,2.088626775,1],
          [6.922596716,1.77106367,1],
          [8.675418651,-0.242068655,1],
          [7.673756466,3.508563011,1]]
neighbors = get_neighbors(dataset, dataset[0], 3)
for neighbor in neighbors:
	print(neighbor)<jupyter_output>[2.7810836, 2.550537003, 0]
[3.06407232, 3.005305973, 0]
[1.465489372, 2.362125076, 0]<jupyter_text>**Step 3: Make Predictions.**Now that we know how to get neighbors from the dataset, we can use them to make predictions.``` Make a classification prediction with neighborsdef predict_classification(train, test_row, num_neighbors):	neighbors = get_neighbors(train, test_row, num_neighbors)	output_values = [row[-1] for row in neighbors]	prediction = max(set(output_values), key=output_values.count)	return prediction```<jupyter_code># Example of making predictions
from math import sqrt
 
# calculate the Euclidean distance between two vectors
def euclidean_distance(row1, row2):
	distance = 0.0
	for i in range(len(row1)-1):
		distance += (row1[i] - row2[i])**2
	return sqrt(distance)
 
# Locate the most similar neighbors
def get_neighbors(train, test_row, num_neighbors):
	distances = list()
	for train_row in train:
		dist = euclidean_distance(test_row, train_row)
		distances.append((train_row, dist))
	distances.sort(key=lambda tup: tup[1])
	neighbors = list()
	for i in range(num_neighbors):
		neighbors.append(distances[i][0])
	return neighbors
 
# Make a classification prediction with neighbors
def predict_classification(train, test_row, num_neighbors):
	neighbors = get_neighbors(train, test_row, num_neighbors)
	output_values = [row[-1] for row in neighbors]
	prediction = max(set(output_values), key=output_values.count)
	return prediction
 
# Test distance function
dataset = [[2.7810836,2.550537003,0],
          [1.465489372,2.362125076,0],
          [3.396561688,4.400293529,0],
          [1.38807019,1.850220317,0],
          [3.06407232,3.005305973,0],
          [7.627531214,2.759262235,1],
          [5.332441248,2.088626775,1],
          [6.922596716,1.77106367,1],
          [8.675418651,-0.242068655,1],
          [7.673756466,3.508563011,1]]
prediction = predict_classification(dataset, dataset[0], 3)
print('Expected %d, Got %d.' % (dataset[0][-1], prediction))
y = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
from sklearn.neighbors import KNeighborsClassifier
dataset2 = [[2.7810836,2.550537003],
          [1.465489372,2.362125076],
          [3.396561688,4.400293529],
          [1.38807019,1.850220317],
          [3.06407232,3.005305973],
          [7.627531214,2.759262235],
          [5.332441248,2.088626775],
          [6.922596716,1.77106367],
          [8.675418651,-0.242068655],
          [7.673756466,3.508563011]]
          
knn = KNeighborsClassifier(n_neighbors=3)
knn = knn.fit(dataset, y)
y_pred = knn.predict([[2.7810836, 2.550537003]])
print('Expected %d, Got %d.' % (y[0], y_pred))<jupyter_output>Expected 0, Got 0.
{'fraction_non_alphanumeric': 0.12245733788395904, 'fraction_numerical': 0.1561774744027304, 'mean_word_length': 4.331877729257642, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '634944', 'license': 'MIT', 'n_tokens_mistral': 3277, 'n_tokens_neox': 2565, 'n_words': 679, 'path': 'K-Nearest Neighbor/K-NN.ipynb', 'repo_name': 'MohamedHussein736/Natural-Language-Processing-NLP-Topics', 'size': '7325'}