KNN 演算法原理簡單，易於實作，但在處理高維資料和大規模資料集時，效能瓶頸是其一大挑戰。最佳化 KNN 演算法的效能，可以從資料預處理、特徵選擇和距離度量選擇等方面入手。資料預處理包含資料清洗、標準化和降維等步驟，特徵選擇則用於篩選出最具代表性的特徵，而距離度量選擇則根據資料特性選擇合適的距離計算方法。這些最佳化技術能有效提升 KNN 演算法的效率和準確性，使其更適用於實際應用場景。
KNN演算法的最佳化與進階應用
KNN演算法雖然簡單易用，但在實際應用中仍需考慮其效能最佳化和進階應用。儘管經過最佳化，KNN仍存在固有的侷限性，例如對維度詛咒的敏感性和在大資料集上的計算複雜度。在這種情況下，考慮使用替代演算法或更先進的KNN變體（如近似最近鄰演算法）可能是必要的。
KNN的最佳化技術
在前面的討論中，我們已經介紹了幾種KNN的最佳化技術，包括資料預處理、特徵選擇和距離度量選擇。這些技術可以顯著提高KNN的效能，使其在處理高維資料和大規模資料集時更加高效。
KNN的進階應用
KNN的進階應用將演算法的能力擴充套件到複雜的現實場景中。影像識別、詐欺檢測和醫療診斷是KNN在複雜領域中應用的典型例子。
影像識別
在影像識別中，KNN被用作各種任務的基礎，例如人臉識別、物件檢測和手寫字識別。該演算法透過將影像畫素或提取的特徵視為高維空間中的資料點來工作。對於人臉識別，影像通常會被預處理以提取關鍵的人臉特徵，這些特徵然後作為KNN分類別的輸入。
以下是一個使用KNN進行數字識別的簡單範例，使用MNIST資料集：
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_digits
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
# 載入數字資料集
digits = load_digits()
X, y = digits.data, digits.target
# 分割資料
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
# 建立並訓練KNN分類別器
knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train, y_train)
# 進行預測
y_pred = knn.predict(X_test)
# 計算準確率
accuracy = accuracy_score(y_test, y_pred)
print(f"準確率：{accuracy:.2f}")
內容解密：
此範例程式碼展示瞭如何使用KNN識別手寫數字。每個影像都被表示為畫素強度的扁平陣列，KNN根據新影像與訓練資料的相似性進行分類別。
- 資料載入：使用
load_digits函式載入數字資料集。 - 資料分割：將資料集分割為訓練集和測試集。
- 模型訓練：建立KNN分類別器並使用訓練資料進行訓練。
- 預測與評估：使用測試資料進行預測並計算模型的準確率。
詐欺檢測
在詐欺檢測中，KNN透過將可疑交易或行為與已知模式進行比較來識別異常交易。該演算法可以透過查詢交易的最近鄰居並檢查它們是否大多是詐欺交易來標記潛在的詐欺案例。
以下是一個概念性的範例，展示如何使用KNN進行詐欺檢測：
import numpy as np
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
# 模擬交易資料
# 特徵：[交易金額，距上次交易時間，與家的距離]
X = np.array([
[100, 2, 5], # 正常交易
[50, 1, 3], # 正常交易
[1000, 0.1, 100], # 可疑交易
[75, 3, 10], # 正常交易
[5000, 0.2, 500] # 可疑交易
])
# 標籤：0表示正常，1表示詐欺
y = np.array([0, 0, 1, 0, 1])
# 標準化特徵
scaler = StandardScaler()
X_normalized = scaler.fit_transform(X)
# 建立並訓練KNN分類別器
knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(X_normalized, y)
# 新交易分類別
new_transaction = np.array([[200, 1.5, 50]])
new_transaction_normalized = scaler.transform(new_transaction)
# 預測新交易是否為詐欺
prediction = knn.predict(new_transaction_normalized)
probability = knn.predict_proba(new_transaction_normalized)
print(f"預測結果：{'詐欺' if prediction[0] == 1 else '正常'}")
print(f"詐欺機率：{probability[0][1]:.2f}")
內容解密：
此範例展示瞭如何使用KNN根據新交易與已知詐欺和正常交易的相似性對其進行分類別。
- 資料模擬：模擬交易資料，包括交易金額、距上次交易時間和與家的距離等特徵。
- 資料標準化：使用
StandardScaler對特徵進行標準化處理。 - 模型訓練：建立KNN分類別器並使用標準化後的資料進行訓練。
- 預測與機率計算：對新交易進行預測並計算其為詐欺的機率。
醫療診斷
在醫療診斷中，KNN透過將患者的症狀、檢測結果和其他相關資料與先前診斷的病例進行比較，來建議潛在的診斷或預測治療結果。
以下是一個簡化的範例，展示如何使用KNN進行醫療診斷：
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import train_test_split
from sklearn.metrics import classification_report
# 模擬患者資料
# 特徵：[年齡，血壓，膽固醇，血糖]
X = np.array([
[45, 120, 200, 100],
[50, 140, 250, 120],
[35, 110, 180, 90],
[60, 150, 300, 140],
[40, 130, 220, 110]
])
# 標籤：0表示健康，1表示病症A，2表示病症B
y = np.array([0, 1, 0, 2, 1])
# 分割資料
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
# 標準化特徵
scaler = StandardScaler()
X_train_normalized = scaler.fit_transform(X_train)
X_test_normalized = scaler.transform(X_test)
# 建立並訓練KNN分類別器
knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(X_train_normalized, y_train)
# 進行預測
y_pred = knn.predict(X_test_normalized)
# 列印分類別報告
print(classification_report(y_test, y_pred, target_names=['健康', '病症A', '病症B']))
內容解密：
此範例展示瞭如何使用KNN根據患者的醫療資料將其分類別到不同的健康類別中。
- 資料模擬：模擬患者資料，包括年齡、血壓、膽固醇和血糖等特徵。
- 資料分割：將資料集分割為訓練集和測試集。
- 資料標準化：對特徵進行標準化處理。
- 模型訓練與預測：建立KNN分類別器並進行訓練，然後對測試資料進行預測。
- 評估：列印分類別報告以評估模型的效能。
探索進階演算法的世界
在深入瞭解KNN演算法的先進應用後，我們將目光轉向其他重要的進階演算法，包括圖形演算法、字串演算法和網路演算法。這些演算法在解決複雜問題和最佳化系統效能方面發揮著關鍵作用。
圖形演算法：探索複雜關係的利器
圖形演算法是處理圖形資料結構的重要工具，廣泛應用於電腦網路、社交網路分析和交通系統等領域。圖形由頂點（節點）和連線這些頂點的邊組成，圖形演算法能夠有效地解決與圖形相關的問題。
深度優先搜尋（DFS）
深度優先搜尋是一種基本的圖形演算法，透過沿著每個分支盡可能深入地探索圖形，直到無法繼續為止，然後回溯。DFS在尋找連通元件、檢測環和解決迷宮問題等方面非常有用。
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for next_node in graph[start] - visited:
dfs(graph, next_node, visited)
return visited
# 範例用法
graph = {
'0': set(['1', '2']),
'1': set(['0', '3', '4']),
'2': set(['0']),
'3': set(['1']),
'4': set(['2', '3'])
}
dfs(graph, '0')
內容解密：
- 函式定義：
dfs函式接受一個圖形graph、一個起始節點start和一個可選的visited集合，用於記錄已存取的節點。 - 初始化
visited集合：如果未提供visited，則初始化為空集合。 - 存取當前節點：將
start節點加入visited並列印。 - 遞迴存取鄰居節點：對
start的每個未存取鄰居節點遞迴呼叫dfs。 - 傳回已存取節點集合：最終傳回所有已存取的節點。
廣度優先搜尋（BFS）
與DFS不同，BFS在深入探索之前，會先存取當前深度的所有鄰居節點。BFS常用於在未加權圖形中尋找兩個節點之間的最短路徑。
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
print(vertex, end=' ')
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# 範例用法
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
bfs(graph, 'A')
內容解密：
- 使用佇列實作BFS：利用
deque建立佇列，儲存待存取的節點。 - 存取節點並加入鄰居：從佇列中取出節點，存取並將未存取的鄰居節點加入佇列。
- 確保每個節點僅存取一次：透過
visited集合記錄已存取節點，避免重複存取。
字串演算法：高效處理文字資料
字串演算法專門用於字串操作和模式匹配。Knuth-Morris-Pratt（KMP）演算法是一種著名的字串匹配演算法，透過利用先前匹配嘗試的資訊來提高效率。
def compute_lps(pattern):
lps = [0] * len(pattern)
length = 0
i = 1
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
def kmp_search(text, pattern):
M = len(pattern)
N = len(text)
lps = compute_lps(pattern)
i = j = 0
while i < N:
if pattern[j] == text[i]:
i += 1
j += 1
if j == M:
print(f"Pattern found at index {i - j}")
j = lps[j - 1]
elif i < N and pattern[j] != text[i]:
if j != 0:
j = lps[j - 1]
else:
i += 1
# 範例用法
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
kmp_search(text, pattern)
內容解密：
- 計算LPS陣列：
compute_lps函式計算模式字串的最長真字首同時也是字尾的陣列。 - KMP搜尋：利用LPS陣列，在文字中高效搜尋模式字串。
- 匹配成功處理：當匹配成功時，輸出起始索引並調整
j值繼續搜尋。
網路演算法：最佳化網路效能
網路演算法在電腦網路中有著廣泛的應用，處理路由、流量控制和網路設計等問題。Dijkstra演算法是一種經典的網路演算法，用於在圖形中尋找兩個節點之間的最短路徑。
import heapq
def dijkstra(graph, start):
distances = {node: float('infinity') for node in graph}
distances[start] = 0
pq = [(0, start)]
while pq:
current_distance, current_node = heapq.heappop(pq)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
# 範例用法
graph = {
'A': {'B': 4, 'C': 2},
'B': {'A': 4, 'C': 1, 'D': 5},
'C': {'A': 2, 'B': 1, 'D': 8, 'E': 10},
'D': {'B': 5, 'C': 8, 'E': 2, 'F': 6},
'E': {'C': 10, 'D': 2, 'F': 3},
'F': {'D': 6, 'E': 3}
}
print(dijkstra(graph, 'A'))
內容解密：
- 初始化距離：將所有節點的距離初始化為無窮大，起始節點距離設為0。
- 使用優先佇列：利用堆積實作優先佇列，儲存待處理的節點及其當前最短距離。
- 更新鄰居節點距離：對當前節點的鄰居，計算新的距離並在更短時更新。
- 傳回最短距離：最終傳回所有節點到起始節點的最短距離。
