近臨算法（個人總結版）

背景

近鄰算法（Nearest Neighbor Algorithm）是一種基本但非常有效的分類和回歸方法。最早由Fix和Hodges在1951年提出，經過幾十年的發展和改進，已成為數據挖掘、模式識別和機器學習領域的重要工具。近鄰算法基于相似性原則，通過查找最接近的樣本進行預測。其核心思想是相似的樣本具有相似的特征，因而在預測時可以參考相似樣本的類別或數值。常見的近鄰算法包括k近鄰算法（k-Nearest Neighbors, k-NN）、KD樹（KD-Tree）和球樹（Ball Tree）。

一、近鄰算法的基本概念

近鄰算法通過比較樣本之間的距離來進行分類或回歸。其核心思想是相似的樣本具有相似的特征，因而在預測時可以參考相似樣本的類別或數值。

1.1 距離度量

常用的距離度量包括：

  • 歐氏距離（Euclidean Distance）：最常用的距離度量，適用于連續型數據。公式為：

  • 曼哈頓距離（Manhattan Distance）：適用于高維空間和稀疏數據。公式為：

  • 閔可夫斯基距離（Minkowski Distance）：歐氏距離和曼哈頓距離的推廣，適用于多種情況。公式為：

  • 余弦相似度（Cosine Similarity）：用于度量兩個向量之間的夾角，相似度越大，距離越小。公式為：

1.2 算法類型

  • 分類：將新樣本分類到與其最相似的樣本所屬的類別。
  • 回歸：預測新樣本的數值為與其最相似的樣本數值的加權平均。

二、k近鄰算法（k-NN）

2.1 基本原理

k近鄰算法通過查找與目標樣本最近的k個樣本進行預測。對于分類任務，k個鄰居中的多數類作為預測結果；對于回歸任務，k個鄰居的平均值作為預測結果。k近鄰算法無需訓練過程，直接利用所有訓練數據進行預測，因此也被稱為懶惰學習算法（Lazy Learning）。

2.2 具體實現

以下是k近鄰算法的分類實現：

import numpy as np
from collections import Counter
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_scoreclass KNN:def __init__(self, k=3):self.k = kdef fit(self, X, y):self.X_train = Xself.y_train = ydef predict(self, X):predictions = [self._predict(x) for x in X]return np.array(predictions)def _predict(self, x):distances = [np.sqrt(np.sum((x - x_train)**2)) for x_train in self.X_train]k_indices = np.argsort(distances)[:self.k]k_nearest_labels = [self.y_train[i] for i in k_indices]most_common = Counter(k_nearest_labels).most_common(1)return most_common[0][0]# 加載示例數據集
iris = load_iris()
X, y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)# 訓練和預測
knn = KNN(k=3)
knn.fit(X_train, y_train)
predictions = knn.predict(X_test)# 計算準確率
print("Accuracy:", accuracy_score(y_test, predictions))

2.3 優劣勢

優勢：

  • 簡單易懂：k近鄰算法的基本思想簡單直觀，易于理解和實現。
  • 無訓練過程：無需訓練過程，直接利用所有訓練數據進行預測。

劣勢：

  • 計算復雜度高：對每個測試樣本都需要計算與所有訓練樣本的距離，因此預測過程的計算復雜度較高，適合小規模數據集。
  • 對噪聲數據敏感：k近鄰算法對噪聲數據較為敏感，可能影響預測結果。
  • 數據標準化要求：不同特征的量綱不同時，需對數據進行標準化處理，否則距離計算可能會受到影響。

三、KD樹（KD-Tree）

3.1 基本原理

KD樹是一種對k近鄰算法進行優化的數據結構，通過將數據劃分到k維空間中的子區域，實現高效的最近鄰搜索。KD樹通過遞歸地將數據空間劃分為k維超矩形，適用于低維數據的最近鄰搜索。

3.2 具體實現

以下是KD樹的實現和最近鄰搜索：

from scipy.spatial import KDTree# 示例數據
X = np.random.rand(10, 2)# 構建KD樹
kd_tree = KDTree(X)# 查詢最近鄰
point = np.random.rand(1, 2)
distance, index = kd_tree.query(point)print("Nearest neighbor:", X[index])
print("Distance:", distance)

3.3 優劣勢

優勢：

  • 提高了k近鄰搜索的效率：KD樹通過分割數據空間，實現了快速的最近鄰搜索，特別適合低維數據。
  • 支持動態插入和刪除操作：KD樹允許動態插入和刪除數據點，適用于數據集動態變化的場景。

劣勢：

  • 構建和維護樹結構的復雜度較高：構建KD樹需要較高的計算復雜度，插入和刪除操作也較為復雜。
  • 維度災難：隨著維度增加，KD樹的性能提升有限，高維數據的最近鄰搜索效果不佳。

四、球樹（Ball Tree）

4.1 基本原理

球樹是一種替代KD樹的結構，通過使用超球體代替超矩形來劃分空間，適用于高維數據和度量空間。球樹通過遞歸地將數據空間劃分為球形區域，實現高效的最近鄰搜索。

4.2 具體實現

以下是球樹的實現和最近鄰搜索：

from sklearn.neighbors import BallTree# 示例數據
X = np.random.rand(10, 2)# 構建球樹
ball_tree = BallTree(X)# 查詢最近鄰
point = np.random.rand(1, 2)
dist, ind = ball_tree.query(point)print("Nearest neighbor:", X[ind])
print("Distance:", dist)

4.3 優劣勢

優勢：

  • 適用于高維數據：球樹在高維空間中表現良好，比KD樹更適合高維數據。
  • 支持多種距離度量：球樹支持多種距離度量，如歐氏距離、曼哈頓距離等。

劣勢：

  • 構建和維護樹結構的復雜度較高：構建和維護球樹需要較高的計算復雜度，插入和刪除操作也較為復雜。
  • 構建時間較長：隨著數據規模增加，構建球樹的時間較長。

五、應用實例

5.1 手寫數字識別

使用k-NN算法進行手寫數字識別：

from sklearn.datasets import load_digits
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
from sklearn.neighbors import KNeighborsClassifier# 加載數據
digits = load_digits()
X, y = digits.data, digits.target# 預處理數據
scaler = StandardScaler()
X = scaler.fit_transform(X)# 分割數據集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)# 訓練k-NN分類器
knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(X_train, y_train)# 預測并計算準確率
predictions = knn.predict(X_test)
print("Accuracy:", accuracy_score(y_test, predictions))

5.2 圖像檢索

使用KD樹進行圖像特征的最近鄰搜索：

from sklearn.decomposition import PCA
from sklearn.datasets import fetch_olivetti_faces
from scipy.spatial import KDTree# 加載數據
faces = fetch_olivetti_faces()
X, y = faces.data, faces.target# 降維
pca = PCA(n_components=50)
X_pca = pca.fit_transform(X)# 構建KD樹
kd_tree = KDTree(X_pca)# 查詢最近鄰
query_image = X_pca[0].reshape(1, -1)
dist, ind = kd_tree.query(query_image, k=5)# 輸出最近鄰結果
print("Nearest neighbors:", ind)
print("Distances:", dist)

5.3 文章推薦

使用球樹進行文章推薦：

from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.neighbors import BallTree# 示例文章
documents = ["The quick brown fox jumps over the lazy dog.","Never jump over the lazy dog quickly.","Bright vixens jump; dozy fowl quack.","Jinxed wizards pluck ivy from the big quilt.","The five boxing wizards jump quickly."
]# 計算TF-IDF特征
vectorizer = TfidfVectorizer()
X = vectorizer.fit_transform(documents).toarray()# 構建球樹
ball_tree = BallTree(X, metric='cosine')# 查詢最近鄰
query = vectorizer.transform(["Jumping over dogs is fun."]).toarray()
dist, ind = ball_tree.query(query, k=3)# 輸出最近鄰結果
print("Nearest neighbors:", ind)
print("Distances:", dist)

六、總結

近鄰算法是一類基礎且強大的分類和回歸方法，廣泛應用于圖像識別、推薦系統等領域。本文詳細介紹了k近鄰算法（k-NN）、KD樹（KD-Tree）、球樹（Ball Tree）的基本原理、具體實現、優劣勢及應用實例。通過這些算法的學習和應用，可以有效提高分類和回歸任務的性能和精度。

拓展閱讀與參考文獻

  1. 《統計學習方法》 - 李航
  2. 《機器學習》 - 周志華
  3. 《模式分類》 - Duda, Hart, Stork
  4. Efficient Algorithms for Nearest Neighbor Search in High Dimensions - Arya, Mount, Netanyahu, Silverman, Wu (1998)
  5. Nearest Neighbors in High-Dimensional Data: The Efficiency-Accuracy Tradeoff - Indyk, Motwani (1998)

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/bicheng/14645.shtml
繁體地址，請注明出處：http://hk.pswp.cn/bicheng/14645.shtml
英文地址，請注明出處：http://en.pswp.cn/bicheng/14645.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

通過el-tree自定義渲染網頁版工作目錄，實現鼠標懸浮顯示完整名稱、用icon區分文件和文件夾等需求

通過el-tree自定義渲染網頁版工作目錄，實現鼠標懸浮顯示完整名稱、用icon區分文件和文件夾等需求

目錄 一、通過el-tree自定義渲染網頁版工作目錄 1.1、需求介紹 1.2、使用el-tree生成文檔目錄 1.2.1、官方基礎用法 ①效果 ②代碼： 1.2.2、自定義文檔目錄（實現鼠標懸浮顯示完整名稱、用icon區分文件和文件夾） ①效果（直接效…
閱讀更多...
find 幾招在 Linux 中高效地查找目錄

find 幾招在 Linux 中高效地查找目錄

1. 介紹 在 Linux 操作系統中，查找目錄是一項常見的任務。無論是系統管理員還是普通用戶，都可能需要查找特定的目錄以執行各種操作，如導航文件系統、備份數據、刪除文件等。Linux 提供了多種命令和工具來幫助我們在文件系統中快速找到目標目…
閱讀更多...
淺談后端整合Springboot框架后操作基礎配置

淺談后端整合Springboot框架后操作基礎配置

boot基礎配置 現在不訪問端口8080 可以嗎 我們在默認啟動的時候訪問的是端口號8080 基于屬性配置的 現在boot整合導致Tomcat服務器的配置文件沒了 我們怎么去修改Tomcat服務器的配置信息呢 配置文件中的配置信息是很多很多的... 復制工程 保留工程的基礎結構 抹掉原始…
閱讀更多...
樸素貝葉斯+SMSSpamCollections

樸素貝葉斯+SMSSpamCollections

1. 打開 Jupyter 后，在工作目錄中，新建一個文件夾命名為 Test01 ，并且在文件夾中導入數據 集。在網頁端界面點擊 “upload” 按鈕，在彈出的界面中選擇要導入的數據集。然后數據集出現 在 jupyter 文件目錄中，此時…
閱讀更多...
Vue.js Promise 與 async/await 的比較

Vue.js Promise 與 async/await 的比較

在現代 Web 開發中，異步操作是不可避免的。在處理異步數據獲取時，開發人員通常會使用 Promise 或 async/await。雖然兩者都可以實現相同的功能，但它們在代碼風格、可讀性和錯誤處理等方面有所不同。本文將對這兩種方法進行比較，并…
閱讀更多...
初識Qt：從Hello world到對象樹的深度解析

初識Qt：從Hello world到對象樹的深度解析

Qt中的對象樹深度解析 Hello world1.圖形化界面創建命令行式創建在棧上創建在堆上創建為什么傳文本需要QString，std::string不行嗎？那為什么要傳入this指針？為什么new后不用顯示調用delete函數呢，不會造成內存泄漏問題嗎&#xff…
閱讀更多...
python：__class_getitem__使用以及cached_property源碼分析

python：__class_getitem__使用以及cached_property源碼分析

python：__class_getitem__使用以及cached_property源碼分析 1 前言 Python中如何模擬泛型類型？ 當使用類型標注時，使用 Python 的方括號標記來形參化一個 generic type 往往會很有用處。 例如，list[int] 這樣的標注可以被用來表…
閱讀更多...
深入 OpenFeign：探索緩存、QueryMap、MatrixVariable 和 CollectionFormat 的高級用法以實現優雅的遠程調用

深入 OpenFeign：探索緩存、QueryMap、MatrixVariable 和 CollectionFormat 的高級用法以實現優雅的遠程調用

免費多模型AI網站,支持豆包、GPT-4o、谷歌Gemini等AI模型，無限制使用，快去白嫖👉海鯨AI 一、OpenFeign簡介 OpenFeign 是一個聲明式的 HTTP 客戶端，它使得我們可以通過簡單的注解和接口定義來調用遠程 HTTP 服務。與傳統的 HTTP …
閱讀更多...
K8S集群再搭建

K8S集群再搭建

前述：總體是非常簡單的，就是過程繁瑣，不過都是些重復的操作 master成員: [controller-manager, scheduler, api-server, etcd, proxy,kubelet] node成員: [kubelet, proxy] master要修改的配置文件有 1. vi /etc/etcd/etcd.conf # 數…
閱讀更多...
Mokito的一些API

Mokito的一些API

Mockito是一個Java單元測試框架，它允許開發者創建和配置模擬對象（mock objects），以便在隔離的環境中測試代碼，尤其是當實際對象難以構造或其行為不確定時。下面是一些核心的Mockito API及其使用場景和代碼示例。 基礎…
閱讀更多...
wordpress教程視頻 wordpress教程網盤 wordpress教程推薦wordpress教程網

wordpress教程視頻 wordpress教程網盤 wordpress教程推薦wordpress教程網

WordPress，作為一款強大且靈活的開源內容管理系統，已成為許多網站開發者與運營者的首選。其強大的功能、豐富的插件以及易于上手的特點，使得無論是初學者還是專業開發者都能輕松構建出個性化的網站。然而，對于初學者來說&#xff…
閱讀更多...
JUnit5標記測試用例

JUnit5標記測試用例

使用場景： 通過Tag對用例分組： 環境分組：測試環境、預發布環境階段分組：冒煙用例版本分組：V1.1、V1.2 Tag標記用例： 設置標簽根據標簽執行 結合Maven執行結合測試套件執行 設置標簽： 通過T…
閱讀更多...
NER 數據集格式轉換

NER 數據集格式轉換

NER 數據集格式 格式一 某些地方的數據和標簽拆成兩個文件了 sentences.txt 如 何 解 決 足 球 界 長 期 存 在 的 諸 多 矛 盾 ， 重 振 昔 日 津 門 足 球 的 雄 風 ， 成 為 天 津 足 壇 上 下 內 外 到 處 議 論 的 話 題 。 該 縣 一 手 抓 農 業…
閱讀更多...
【Spring Cloud】全面解析服務容錯中間件 Sentinel 持久化兩種模式

【Spring Cloud】全面解析服務容錯中間件 Sentinel 持久化兩種模式

文章目錄 推送模式本地文件持久化（拉模式）配置yml編寫處理類添加配置演示 配置中心持久化（推模式）修改nacos在sentinel中生效引入依賴配置文件 修改sentinel在nacos中生效下載源碼更改代碼演示 總結 推送模式 Sentinel 規則的推送…
閱讀更多...
allegro 無法刪除Xnet

allegro 無法刪除Xnet

allegro 無法刪除Xnet Orcad中打開Constraint Manager之后，再生成網表，導入PCB后就會出現一堆Xnet網絡。無法去除Xnet。 解決辦法 在原理圖ORCAD中， 1、打開Edit Object properties 2、選擇Filter by:Capture 3、點擊New Property 4、設置…
閱讀更多...
火山引擎邊緣云亮相 Force 原動力大會，探索 AI 應用新范式

火山引擎邊緣云亮相 Force 原動力大會，探索 AI 應用新范式

5月15日，2024 春季火山引擎 FORCE 原動力大會在北京正式舉辦。大會聚焦 AI 主題，以大模型應用為核心、以 AI 落地為導向，展示了火山引擎在大模型、云計算領域的實踐應用，攜手汽車、手機終端、金融、消費、互聯網等領域的專家和企業…
閱讀更多...
2024042102-array-list

2024042102-array-list

數組 Array 一、前言 數組是數據結構還是數據類型？ 數組只是個名稱，它可以描述一組操作，也可以命名這組操作。數組的數據操作，是通過 idx->val 的方式來處理。它不是具體要求內存上要存儲著連續的數據才叫數據，而…
閱讀更多...
js積累三(web頁面一段時間未操作，退出登錄)

js積累三(web頁面一段時間未操作，退出登錄)

//核心代碼，已封裝function CountDownLogout() {/* if 30 seconds no operation then logout */var maxTime 30; // seconds，可自行修改時長var time_time maxTime;/* 鼠標點擊事件 */$(document).mousedown(function(){time_time maxTime; //…
閱讀更多...
Spring Aop對本地事務的影響

Spring Aop對本地事務的影響

1.Transactional聲明式事物也是基于aop實現的，public方法加了Transactional注解后，已經成功的創建了事務，但是當前方法仍在方法攔截器中 2.業務方法發生異常之后的處理 判斷回滾條件： 如果自定義了RollbackRuleAttribute列表&am…
閱讀更多...
EI會議的最佳論文獎是什么？如何申請？

EI會議的最佳論文獎是什么？如何申請？

EI會議的最佳論文獎通常是指在EI（工程索引，Engineering Index）收錄的學術會議中，評選出的表現最優秀的論文獎項。以下是關于該獎項的一些基本信息及申請步驟： 最佳論文獎的含義 評選標準：最佳論文獎通常基…
閱讀更多...
最新文章

Copyright @ 2022~2023