KNN 演算法最佳化應用與貝氏分類別器

– 17 分鐘閱讀

KNN 演算法在資料分析中被廣泛應用，其效能取決於 k 值的選擇。透過驗證集的誤分類別率選取最佳 k 值，能有效提升模型準確度。實務上，可根據新資料與鄰近樣本的距離和多數決規則進行分類別，並透過設定截斷值來調整分類別結果。KNN 演算法的優點在於簡單易實作、無需引數設定且能處理非線性關係，然而其計算複雜度高，需要大量記憶體且對異常值敏感。KNN 常用於分類別和預測，例如手寫字辨識、影像分類別和房價預測等。貝氏分類別器則根據條件機率，根據已知資訊判斷新資料的類別歸屬。完整貝氏分類別器需要計算所有預測變陣列合的條件機率，在大資料集上計算成本高昂。為此，Naive Bayes 方法做了簡化假設，認為各預測變數相互獨立，降低了計算複雜度，但可能犧牲部分準確性。條件機率是理解貝氏分類別器的關鍵，它描述了在特定事件發生的前提下，另一事件發生的機率。獨立事件則指兩個事件互不影響，其條件機率等於事件本身的機率。

k-最近鄰（k-NN）演算法的最佳化與應用

在進行資料分析時，選擇適合的k值對於k-最近鄰（k-NN）演算法的表現至關重要。以下將探討如何根據驗證集的誤分類別率來選擇最佳的k值，並進一步瞭解如何應用k-NN進行新資料的分類別。

選擇最佳k值

給定的資料集包含了多個樣本，每個樣本都有一個對應的類別標籤。為了評估k-NN演算法的表現，我們計算了驗證集的誤分類別率，結果如下：

k值誤分類別率
633.3333
733.3333
816.6667
916.6667
1016.6667

根據結果，當k=8時，誤分類別率最低，因此我們選擇k=8作為最佳k值。

應用k-NN進行新資料分類別

一旦選擇了最佳的k值，k-NN演算法就可以用來分類別新的、未知類別的資料。以下是使用k=8對新資料進行分類別的例子：

新資料：Record ID = 1，收入 = $60,000，土地面積 = 20,000平方英尺

根據k-NN演算法，該新資料點的8個最近鄰居中，有5個是房主，3個是非房主。因此，根據多數決規則，新資料點被分類別為房主，且其屬於房主類別的機率估計為5/8。

設定截斷值

在二元分類別問題中，截斷值的設定直接影響著分類別結果。截斷值決定了何時將一個新資料點分類別為某一類別。例如，在房主與非房主的分類別問題中，如果新資料點的屬於房主類別的機率估計大於截斷值（通常設為0.5），則該新資料點被分類別為房主。

k-NN 演算法的應用與優缺點

k-NN 演算法是一種簡單 yet 效果良好的分類別和預測方法。以下是其應用和優缺點的分析：

k-NN 分類別

k-NN 分類別是一種根據鄰近樣本的分類別方法。其基本思想是根據新的樣本與已知樣本之間的距離，找出最接近的 k 個鄰近樣本，並根據這些鄰近樣本的類別進行分類別。

例如，假設我們有一個新的家庭樣本，需要根據其特徵進行分類別。k-NN 演算法會根據距離公式（例如歐幾裡得距離）找出最接近的 k 個鄰近樣本。如果其中 5 個鄰近樣本是業主，那麼新的家庭樣本就會被分類別為業主。

k-NN 的優點

  1. 簡單易實作：k-NN 演算法簡單易懂，實作起來也相對容易。
  2. 非引數性：k-NN 演算法不需要任何引數設定，直接根據資料進行分類別。
  3. 能夠處理非線性關係：k-NN 演算法能夠處理非線性關係的資料。

k-NN 的缺點

  1. 計算複雜度高：k-NN 演算法需要計算每個樣本與其他樣本之間的距離，這個過程可能很耗時。
  2. 需要大量記憶體：k-NN 演算法需要儲存所有的訓練資料，這可能需要大量的記憶體。
  3. 敏感度高：k-NN 演算法對於異常值和噪聲非常敏感，可能會影響分類別結果。

k-NN 的應用

  1. 分類別：k-NN 演算法常用於分類別問題，例如手寫字辨識、影像分類別等。
  2. 預測：k-NN 演算法也可以用於預測連續值，例如預測房價、股票價格等。

7.3 機器學習工作流程

在本章中，我們使用的k-NN模型的機器學習工作流程如圖7.4所示。注意，工作流程包含了「連續資料重縮放」和「評分」兩個步驟。這兩個步驟是在訓練k-NN模型的過程中同時完成的：數值預測變數的重縮放是透過標準化實作的；而對新軌跡的評分則是透過「評分新資料」和「匹配」兩個步驟實作的。

圖7.4：k-NN模型的全方位工作流程

7.4 k-NN演算法的優點和缺點

k-NN方法的主要優點在於其簡單性和無需引數假設。在足夠大的訓練集存在的情況下，這些方法可以表現得非常出色，特別是在每個類別都有明確特徵的情況下。例如，在房地產資料函式庫中，可能有多種組合的{房屋型別、房間數量、鄰裡、要價等}來描述那些快速售出的房屋和那些長期滯留在市場上的房屋。

然而，實際應用k-NN方法的力量存在三個困難。首先，雖然不需要時間來估計引數（與引數模型如迴歸分析不同），但是在大型訓練集中找到最近鄰居的時間可能是不可接受的。為了克服這個困難，實施了多種想法。主要的想法包括：

  • 透過對資料進行預處理來減少計算距離所需的時間。
  • 使用高階資料結構，如搜尋樹，來加速最近鄰居的識別。這種方法通常會選擇一個「幾乎最近」的鄰居來提高速度。例如，可以使用分桶法，將記錄分組到桶中，使得每個桶中的記錄彼此接近。對於待預測的記錄，桶按距離排序。從最近的桶開始，計算待預測記錄與每個桶中的記錄之間的距離。當距離超過目前為止最接近的記錄距離時，演算法停止。

其次，隨著預測變數數量(p)的增加，訓練集所需的記錄數量呈指數增長，以確保模型具有足夠大的訓練集。這是因為預期距離最近鄰居會隨著(p)的增加而迅速增加，除非訓練集的大小也隨著(p)呈指數增長。這種現象被稱為維度災難，是所有分類別、預測和聚類別技術的一個基本問題。因此，我們通常會尋求透過選擇子集或使用主成分分析和奇異值分解等方法來減少預測變數的數量（詳見第4章）。

第三，k-NN是一種「懶惰學習者」：耗時的計算被延遲到預測時。在預測每條記錄時，我們只在預測時計算其與整個訓練集記錄之間的距離。這種行為禁止使用此演算法進行大量記錄的實時預測。

總之，k-NN演算法具有簡單性和無需引數假設的優點，但也存在計算效率低下、需要大量訓練資料以及延遲計算等缺點。因此，在實際應用中需要根據具體情況選擇合適的演算法和最佳化策略。

音樂推薦服務Pandora的工作原理

Pandora是一個根據使用者偏好而提供音樂推薦的服務。它允許使用者建立自定義的「電臺」，這些電臺會根據使用者指定的歌曲或藝人播放類別似的音樂。Pandora的核心技術是根據Music Genome Project，這是一種根據k-NN（k-近鄰）演算法的音樂推薦系統。

音樂基因體計畫（Music Genome Project）

音樂基因體計畫是一個龐大的音樂分析專案，旨在將每首歌曲根據其音樂特徵進行分類別和評估。這些特徵包括旋律、和聲、節奏、音色等多個方面。透過對這些特徵的分析，Pandora可以將使用者指定的歌曲或藝人與其他具有相似特徵的歌曲或藝人進行匹配，從而提供給使用者個人化的音樂推薦。

Pandora的工作流程

  1. 使用者輸入: 使用者指定一首歌曲或藝人作為電臺的基礎。
  2. 音樂分析: Pandora的系統分析這首歌曲或藝人的音樂特徵，並根據Music Genome Project中的資料函式庫找到具有相似特徵的其他歌曲或藝人。
  3. 推薦: 系統根據分析結果推薦給使用者一首新的歌曲。
  4. 使用者反饋: 使用者可以對推薦的歌曲進行評價，例如「喜歡」或「不喜歡」。
  5. 更新電臺: 根據使用者的反饋，Pandora會更新使用者的電臺，增加或減少某些特徵的權重，以提供更符合使用者口味的音樂推薦。

技術實作

Pandora的技術實作包括以下幾個步驟：

  • 資料收集: 收集大量的音樂資料，包括歌曲、藝人、專輯等。
  • 特徵提取: 從收集到的資料中提取音樂特徵，例如旋律、和聲、節奏等。
  • k-NN演算法: 使用k-NN演算法對提取出的特徵進行分類別和匹配。
  • 使用者互動: 提供使用者互動介面，讓使用者可以輸入偏好、評價推薦的歌曲等。

優缺點

Pandora的優點包括：

  • 個人化推薦: 提供給使用者高度個人化的音樂推薦。
  • 豐富的音樂函式庫: 擁有大量的音樂資料函式庫，可以滿足不同使用者的需求。

缺點包括：

  • 依賴人工標注: Music Genome Project需要大量的人工標注和評估，成本高且耗時。
  • 難以擴充套件: 隨著使用者數量和音樂函式庫的增大，系統可能難以擴充套件和維護。

8.1 介紹

在這個章節中，我們將介紹一個名為「天真貝葉斯分類別器」（Naive Bayes Classifier）的方法，它可以應用於具有類別預測變數的資料中。首先，我們回顧條件機率的概念，然後介紹完整的貝葉斯分類別器。接下來，我們會看到為什麼在大多數情況下，這個方法是不實際的，然後學習如何修改它並使用「天真貝葉斯」分類別器，這是一種更為通用的方法。

8.1.1 完整貝葉斯分類別器

完整貝葉斯分類別器的基本原理很簡單。對於每一筆要被分類別的記錄：

  1. 找出所有具有相同預測變數profile的其他記錄（即，預測變數值相同）。
  2. 確定這些記錄屬於哪些類別，並找出哪個類別最為普遍。
  3. 將這個類別指派給新的記錄。

或者（或另外），也可能需要修改這個方法，以回答「屬於某個類別的傾向是多少？」而不是「哪個類別最可能？」的問題。獲得類別機率允許使用一個滑動的截斷點來分類別一筆記錄為屬於某個類別，即使這個類別不是最可能的類別。這種方法在我們對某個特定的類別感興趣，並且願意「過度識別」記錄為屬於這個類別時很有用。

8.1.2 截斷機率方法

截斷機率方法包括以下步驟：

  1. 為感興趣的類別設定一個截斷機率，在這個機率以上，我們認為一筆記錄屬於這個類別。
  2. 找出所有具有相同預測變數profile的訓練記錄（即，預測變數值相同）。
  3. 確定這些記錄屬於感興趣的類別的機率。
  4. 如果這個機率高於截斷機率，則將新的記錄指派給感興趣的類別。

8.1.3 條件機率

兩種程式都包含了條件機率的概念，即事件A發生的機率，假設事件B已經發生了[表示為P(A|B)]。在這種情況下，我們將研究一筆記錄屬於某個類別的機率，假設其預測變數值為x1, x2,…, xp。一般而言，對於一個具有m個類別（C1, C2,…, Cm）的反應變數和預測變數值x1, x2,…, xp，我們想要計算一筆記錄屬於某個類別的機率。

內容解密：

上述內容介紹了天真貝葉斯分類別器的基本概念，包括完整貝葉斯分類別器、截斷機率方法和條件機率。天真貝葉斯分類別器是一種根據貝葉斯定理的簡化版本，假設所有預測變數之間相互獨立。這種假設使得計算簡單化，但也可能導致模型過度簡化。

  graph LR
    A[完整貝葉斯分類別器] --> B[截斷機率方法]
    B --> C[條件機率]
    C --> D[天真貝葉斯分類別器]

圖表翻譯：

此圖表展示了完整貝葉斯分類別器、截斷機率方法和條件機率之間的關係。完整貝葉斯分類別器是基礎，而截斷機率方法是其的一種實作方式。條件機率是兩者共有的概念，而天真貝葉斯分類別器則是根據這些概念的一種簡化版本。

瞭解貝氏分類別器的運作原理

在機器學習中，貝氏分類別器是一種根據機率的分類別方法，根據每個類別的條件機率計算出樣本屬於每個類別的可能性。其運作原理如下：

給定一個樣本 $x_1, x_2,…, x_p$，我們想要計算出它屬於每個類別 $C_i$ 的機率 $P(C_i|x_1, x_2,…, x_p)$。根據貝氏定理，這個機率可以表示為：

$$ P(C_i|x_1, x_2,…, x_p) = \frac{P(x_1, x_2,…, x_p|C_i) \cdot P(C_i)}{P(x_1, x_2,…, x_p)} $$

其中，$P(x_1, x_2,…, x_p|C_i)$ 是給定類別 $C_i$ 下，樣本出現的機率，稱為似然度；$P(C_i)$ 是類別 $C_i$ 的先驗機率；$P(x_1, x_2,…, x_p)$ 是樣本出現的機率，稱為證據。

貝氏分類別器的應用

以下是一個使用貝氏分類別器預測財務報表是否為欺詐的例子：

假設有一家會計師事務所，每年都會審核大量公司的財務報表。為了提高審核效率，會計師事務所希望使用機器學習演算法預測哪些財務報表可能是欺詐的。為此，他們收集了1500家公司的財務報表資料，包括報表是否為欺詐以及公司是否有過往法律糾紛的資訊。

資料前處理

首先，會計師事務所需要將收集到的資料進行前處理。由於貝氏分類別器只能處理類別變數，因此需要將數值變數轉換為類別變數。例如，可以根據公司過往法律糾紛的次數將其分為兩類別：有過往法律糾紛和沒有過往法律糾紛。

訓練模型

接下來，會計師事務所需要將前處理後的資料分為訓練集和驗證集。假設訓練集包含1000家公司的資料，驗證集包含500家公司的資料。

使用訓練集計算每個類別的先驗機率和條件機率。例如，可以計算出有過往法律糾紛的公司中，財務報表為欺詐的比例，以及沒有過往法律糾紛的公司中，財務報表為欺詐的比例。

測試模型

使用驗證集測試貝氏分類別器的效能。對於每家公司，計算出其財務報表屬於每個類別的機率，並根據機率進行分類別。

結果分析

最終，會計師事務所可以根據測試結果評估貝氏分類別器的效能。例如，可以計算出分類別器正確識別欺詐財務報表的比例，以及錯誤識別正常財務報表為欺詐的比例。

圖表翻譯：

  flowchart TD
    A[資料收集] --> B[資料前處理]
    B --> C[訓練模型]
    C --> D[測試模型]
    D --> E[結果分析]

這個流程圖描述了使用貝氏分類別器預測財務報表是否為欺詐的步驟。從資料收集開始，到資料前處理、訓練模型、測試模型，最終到結果分析，每一步驟都非常重要，以保證分類別器的效能和準確性。

應用完整（精確）貝氏分類別器

在評估一家新公司的財務報告時，我們希望能夠根據其屬性將其分類別為誠實或欺詐。為此，我們計算了屬於每個類別的機率。假設這家新公司曾有法律問題，其屬於欺詐類別的機率為 P(欺詐|曾有法律問題) = 50/230，因為在訓練資料集中，共有 230 家公司曾有法律問題，其中 50 家的財務報告被認定為欺詐。另一方面，屬於誠實類別的機率自然是剩餘部分，即 180/230。

使用「分配給最可能類別」方法

如果一家公司曾有法律問題，我們會將其分配到誠實類別。對於沒有法律問題的公司，類別似的計算作為讀者的練習留下。 在這個例子中，使用「分配給最可能類別」的規則，所有記錄都會被分配到誠實類別。這與天真地將所有記錄分配給多數類別的結果相同。

使用截止機率方法

在這個例子中，我們更感興趣的是識別欺詐報告，因為那些報告可能會使稽核員面臨法律責任。為了識別欺詐報告，我們承認有些誠實報告可能會被誤認為欺詐，從而降低整體分類別準確率。因此，我們的方法是建立一個截止值，用於計算一條記錄屬於欺詐類別的機率，並將所有超過該值的記錄分類別為欺詐。貝氏公式用於計算一條記錄屬於類別 C_i 的機率，如下所示：

P(C_i | x_1,…, x_p) = P(x_1,…, x_p | C_i) * P(C_i)

內容解密：

上述公式是貝氏定理的應用，描述了在給定特徵 x_1,…, x_p的情況下，一條記錄屬於類別 C_i 的後驗機率。其中，P(x_1,…, x_p | C_i) 是在假設記錄屬於類別 C_i的情況下觀察到特徵 x_1,…, x_p 的機率，P(C_i) 是類別 C_i 的先驗機率。

圖表翻譯：

  flowchart TD
    A[記錄屬於類別 C_i] -->|貝氏定理|> B[計算後驗機率]
    B -->|使用截止值|> C[分類別為欺詐或誠實]
    C -->|根據結果|> D[進行相應處理]

圖表翻譯：

上述流程圖描述了使用貝氏定理計算記錄屬於某一類別的機率，並根據該機率進行分類別的過程。首先，根據貝氏定理計算記錄屬於類別 C_i 的後驗機率，然後使用預設的截止值來決定是否將記錄分類別為欺詐或誠實，最後根據分類別結果進行相應的處理。

瞭解貝氏定理在分類別中的應用

在分類別問題中，貝氏定理是一種強大的工具，能夠根據先驗機率和條件機率對新資料進行分類別。然而，在實際應用中，尤其是當預測變數數量較大時，貝氏定理的直接應用可能會遇到困難。

問題描述

給定一個分類別問題，假設我們有 $p$ 個預測變數，目的是根據這些變數對新資料進行分類別。直接使用貝氏定理需要找到所有與新資料在所有預測變數上完全匹配的記錄，這在大資料集中可能是不現實的。

難點分析

當預測變數數量增加時，即使是中等規模的資料集，也可能找不到與新資料完全匹配的記錄。例如，根據人口統計變數預測投票行為，即使只有八個變數，也可能因為個體差異太大而無法找到完全匹配的記錄。

解決方案：Naive Bayes

為瞭解決這個問題，Naive Bayes 方法被提出。與直接應用貝氏定理不同，Naive Bayes 方法不要求找到完全匹配的記錄，而是使用整個資料集來電腦率。這種方法假設所有預測變數之間相互獨立，從而簡化了計算過程。

Naive Bayes 方法

Naive Bayes 方法的核心思想是計算每個類別下新資料出現的機率，並根據這些機率進行分類別。具體來說，對於每個類別 $C_i$，計算 $P(C_i)$ 和 $P(x_1, x_2,…, x_p | C_i)$，然後使用貝氏定理更新後驗機率 $P(C_i | x_1, x_2,…, x_p)$。

優點和應用

Naive Bayes 方法因其簡單和高效而被廣泛應用於各種分類別問題。它能夠處理高維度資料，並且對缺失值具有良好的容忍度。然而，需要注意的是，Naive Bayes 方法對預測變數之間的獨立性假設可能不總是成立，這可能會影響其效能。

分類別程式的演進：從基本到納伊夫貝葉斯

在探討分類別問題時，我們最初的基本分類別程式包括了以下步驟：

  1. 尋找相似記錄：找出所有具有相同預測變數（predictor）設定的記錄。
  2. 確定類別：判斷這些記錄屬於哪些類別，並找出最常見的類別。
  3. 分類別新記錄：將新記錄分類別為最常見的類別。

接下來，我們將介紹納伊夫貝葉斯（Naive Bayes）修改過的基本分類別程式。這個修改過的程式包括了以下步驟：

  1. 估計條件機率：針對每個類別 (C_1)，估計每個預測變數 (x_j) 的條件機率 (P(x_j | C_1))。這代表了在類別 (C_1) 中出現特定預測變數值的機率。
  2. 電腦率積：將這些條件機率相乘，然後再乘以一個額外的因子。
  3. 重複計算：對所有類別重複步驟 1 和 2。
  4. 估計類別機率：根據預測變數值估計每個類別的機率。
  5. 分類別：將新記錄分類別為具有最高機率的類別。

這些步驟導致了納伊夫貝葉斯公式的產生，該公式用於計算一筆記錄具有給定的預測變數值 (x_1, \ldots, x_p) 屬於類別 (C_1) 的機率。納伊夫貝葉斯公式可以寫成如下形式：

[P_{nb}(C_1 | x_1, \ldots, x_p) = \frac{P(C_1) \prod_{j=1}^{p} P(x_j | C_1)}{\sum_{i=1}^{m} P(C_i) \prod_{j=1}^{p} P(x_j | C_i)}]

內容解密：

上述公式中，(P(C_1)) 代表類別 (C_1) 的先驗機率，(\prod_{j=1}^{p} P(x_j | C_1)) 代表在類別 (C_1) 中觀察到預測變數值 (x_1, \ldots, x_p) 的聯合機率。分母中的項則代表所有類別的機率之和，確保了結果是一個有效的機率分佈。

圖表翻譯：

  graph LR
    A[新記錄] -->|具有預測變數值|> B[納伊夫貝葉斯公式]
    B -->|電腦率|> C[類別機率]
    C -->|比較機率|> D[分類別結果]
    D -->|最高機率類別|> E[最終分類別]

這個流程圖展示瞭如何使用納伊夫貝葉斯公式對新記錄進行分類別，從計算每個類別的機率到最終根據最高機率進行分類別。

機率論基礎：條件機率和獨立事件

在機率論中，條件機率是指在已知某一事件發生後，另一個事件發生的機率。這個概念對於理解事件之間的關係非常重要。給定兩個事件A和B，條件機率P(A|B)表示在事件B已經發生後，事件A發生的機率。

條件機率公式

條件機率的公式為：

P(A|B) = P(A ∩ B) / P(B)

其中，P(A ∩ B)是事件A和B同時發生的機率，P(B)是事件B發生的機率。

內容解密：

import numpy as np

def conditional_probability(P_A_and_B, P_B):
    """
    計算條件機率P(A|B)
    
    引數：
    P_A_and_B (float): 事件A和B同時發生的機率
    P_B (float): 事件B發生的機率
    
    傳回：
    float: 條件機率P(A|B)
    """
    if P_B == 0:
        raise ValueError("事件B的機率不能為0")
    
    return P_A_and_B / P_B

# 例子：假設P(A ∩ B) = 0.4，P(B) = 0.8
P_A_and_B = 0.4
P_B = 0.8

P_A_given_B = conditional_probability(P_A_and_B, P_B)
print(f"P(A|B) = {P_A_given_B}")

獨立事件

如果兩個事件A和B滿足P(A|B) = P(A)，則稱這兩個事件是獨立的。這意味著事件B的發生不會影響事件A的發生機率。

圖表翻譯：

  flowchart TD
    A[事件A] -->|獨立|> B[事件B]
    B -->|不影響|> A
    note "獨立事件：P(A|B) = P(A)"

圖表翻譯：

在上述Mermaid圖表中，我們展示了兩個獨立事件A和B之間的關係。由於它們是獨立的，事件B的發生不會影響事件A的發生機率，因此我們可以直接得出P(A|B) = P(A)。

從商業價值視角來看，k-NN 演算法作為一種易於理解和實作的機器學習方法，為企業提供了快速構建分類別和預測模型的途徑。透過分析驗證集的誤分類別率，我們可以選取最佳的 k 值，從而提升模型的預測準確性，進而降低商業決策的風險。然而，k-NN 演算法的計算複雜度較高，尤其在處理大規模資料集時，需要考量其效能瓶頸。技術團隊應著重於資料預處理、特徵工程以及探索更有效率的近似最近鄰搜尋演算法，例如 KD-Tree 或 Ball-Tree，以最佳化 k-NN 的執行效率。對於資源有限的企業，建議優先將 k-NN 應用於高價值的商業場景，例如客戶流失預測、精準行銷等，以最大化其商業效益。玄貓認為，儘管 k-NN 演算法存在一些限制，但其簡單性、非引數特性以及處理非線性關係的能力，使其在特定應用場景中仍具有相當的競爭力。隨著硬體效能的提升和演算法的持續最佳化，預見 k-NN 的應用範圍將進一步擴大。

玄貓

玄貓

技術愛好者，專注於分享程式開發、雲端技術與 AI 應用的心得體會。