# 五、最近鄰方法 本章將重點介紹最近鄰方法，以及如何在 TensorFlow 中實現它們。我們將首先介紹這些方法，然后我們將說明如何實現各種形式。本章將以地址匹配和圖像識別的示例結束。 在本章中，我們將介紹以下內容： * 使用最近鄰 * 使用基于文本的距離 * 計算混合距離函數 * 使用地址匹配的示例 * 使用最近鄰進行圖像識別 > 請注意，所有最新代碼均可在 [Github](https://github.com/nfmcclure/tensorflow_cookbook) 和 [Packt 倉庫](https://github.com/PacktPublishing/TensorFlow-Machine-Learning-Cookbook-Second-Edition)獲得。 # 介紹 最近鄰方法植根于基于距離的概念思想。我們認為我們的訓練設定了一個模型，并根據它們與訓練集中的點的接近程度對新點進行預測。一種簡單的方法是使預測類與最接近的訓練數據點類相同。但由于大多數數據集包含一定程度的噪聲，因此更常見的方法是采用一組`k-`最近鄰的加權平均值。該方法稱為 K 最近鄰（KNN）。 給定具有相應目標（`y[1], y[2]....y[n]`）的訓練數據集（`x[1],x[2].....x[n]`），我們可以通過查看一組最近鄰來對點`z`進行預測。實際的預測方法取決于我們是進行回歸（連續`y[i]`）還是分類（離散`y[i]`）。 對于離散分類目標，可以通過最大投票方案給出預測，通過到預測點的距離加權：  我們這里的預測`f(z)`是所有類別`j`的最大加權值，其中從預測點到訓練點的加權距離`i`由`φ(d[ij])`給出。如果點`i`在類`j.`中，`l[ij]`只是一個指示器函數如果點`i`在類`j`中，則指示器函數取值 1，如果不是，則取值 0 另外，`k`是要考慮的最近點數。 對于連續回歸目標，預測由最接近預測的所有`k`點的加權平均值給出：  很明顯，預測很大程度上取決于距離度量的選擇`d`。 距離度量的常用規范是 L1 和 L2 距離，如下所示： *  *  我們可以選擇許多不同規格的距離指標。在本章中，我們將探討 L1 和 L2 指標，以及編輯和文本距離。 我們還必須選擇如何加權距離。對距離進行加權的直接方法是距離本身。遠離我們預測的點應該比較近點的影響小。最常見的權重方法是通過距離的歸一化逆。我們將在下一個秘籍中實現此方法。 > 注意，KNN 是一種聚合方法。對于回歸，我們正在執行鄰居的加權平均。因此，預測將不那么極端，并且與實際目標相比變化較小。這種影響的大小將由算法中鄰居的數量`k`決定。 # 使用最近鄰 我們將通過實現最近鄰來預測住房價值來開始本章。這是從最近鄰開始的好方法，因為我們將處理數字特征和連續目標。 ## 準備 為了說明如何在 TensorFlow 中使用最近鄰進行預測，我們將使用波士頓住房數據集。在這里，我們將預測鄰域住房價值中位數作為幾個特征的函數。 由于我們考慮訓練集訓練模型，我們將找到預測點的 KNN，并將計算目標值的加權平均值。 ## 操作步驟 我們按如下方式處理秘籍： 1. 我們將從加載所需的庫并啟動圖會話開始。我們將使用`requests`模塊從 UCI 機器學習庫加載必要的波士頓住房數據： ```py import matplotlib.pyplot as plt import numpy as np import tensorflow as tf import requests sess = tf.Session() ``` 1. 接下來，我們將使用`requests`模塊加載數據： ```py housing_url = 'https://archive.ics.uci.edu/ml/machine-learning-databases/housing/housing.data' housing_header = ['CRIM', 'ZN', 'INDUS', 'CHAS', 'NOX', 'RM', 'AGE', 'DIS', 'RAD', 'TAX', 'PTRATIO', 'B', 'LSTAT', 'MEDV'] cols_used = ['CRIM', 'INDUS', 'NOX', 'RM', 'AGE', 'DIS', 'TAX', 'PTRATIO', 'B', 'LSTAT'] num_features = len(cols_used) # Request data housing_file = requests.get(housing_url) # Parse Data housing_data = [[float(x) for x in y.split(' ') if len(x)>=1] for y in housing_file.text.split('n') if len(y)>=1] ``` 1. 接下來，我們將數據分為依賴和獨立的特征。我們將預測最后一個變量`MEDV`，這是房屋組的中值。我們也不會使用`ZN`，`CHAS`和`RAD`特征，因為它們沒有信息或二元性質： ```py y_vals = np.transpose([np.array([y[13] for y in housing_data])]) x_vals = np.array([[x for i,x in enumerate(y) if housing_header[i] in cols_used] for y in housing_data]) x_vals = (x_vals - x_vals.min(0)) / x_vals.ptp(0) ``` 1. 現在，我們將`x`和`y`值分成訓練和測試集。我們將通過隨機選擇大約 80% 的行來創建訓練集，并將剩下的 20% 留給測試集： ```py train_indices = np.random.choice(len(x_vals), round(len(x_vals)*0.8), replace=False) test_indices = np.array(list(set(range(len(x_vals))) - set(train_indices))) x_vals_train = x_vals[train_indices] x_vals_test = x_vals[test_indices] y_vals_train = y_vals[train_indices] y_vals_test = y_vals[test_indices] ``` 1. 接下來，我們將聲明`k`值和批量大小： ```py k = 4 batch_size=len(x_vals_test) ``` 1. 我們接下來會申報占位符。請記住，沒有模型變量需要訓練，因為模型完全由我們的訓練集確定： ```py x_data_train = tf.placeholder(shape=[None, num_features], dtype=tf.float32) x_data_test = tf.placeholder(shape=[None, num_features], dtype=tf.float32) y_target_train = tf.placeholder(shape=[None, 1], dtype=tf.float32) y_target_test = tf.placeholder(shape=[None, 1], dtype=tf.float32) ``` 1. 接下來，我們將為一批測試點創建距離函數。在這里，我們將說明 L1 距離的使用： ```py distance = tf.reduce_sum(tf.abs(tf.subtract(x_data_train, tf.expand_dims(x_data_test,1))), reduction_indices=2) ``` > 注意，也可以使用 L2 距離函數。我們將距離公式改為`distance = tf.sqrt(tf.reduce_sum(tf.square(tf.subtract(x_data_train, tf.expand_dims(x_data_test,1))), reduction_indices=1))`。 1. 現在，我們將創建我們的預測函數。為此，我們將使用`top_k()`函數，該函數返回張量中最大值的值和索引。由于我們想要最小距離的指數，我們將找到`k` - 最大負距離。我們還將聲明目標值的預測和均方誤差（MSE）： ```py top_k_xvals, top_k_indices = tf.nn.top_k(tf.negative(distance), k=k) x_sums = tf.expand_dims(tf.reduce_sum(top_k_xvals, 1),1) x_sums_repeated = tf.matmul(x_sums,tf.ones([1, k], tf.float32)) x_val_weights = tf.expand_dims(tf.divide(top_k_xvals,x_sums_repeated), 1) top_k_yvals = tf.gather(y_target_train, top_k_indices) prediction = tf.squeeze(tf.batch_matmul(x_val_weights,top_k_yvals), squeeze_dims=[1]) mse = tf.divide(tf.reduce_sum(tf.square(tf.subtract(prediction, y_target_test))), batch_size) ``` 1. 現在，我們將遍歷測試數據并存儲預測和準確率值： ```py num_loops = int(np.ceil(len(x_vals_test)/batch_size)) for i in range(num_loops): min_index = i*batch_size max_index = min((i+1)*batch_size,len(x_vals_train)) x_batch = x_vals_test[min_index:max_index] y_batch = y_vals_test[min_index:max_index] predictions = sess.run(prediction, feed_dict={x_data_train: x_vals_train, x_data_test: x_batch, y_target_train: y_vals_train, y_target_test: y_batch}) batch_mse = sess.run(mse, feed_dict={x_data_train: x_vals_train, x_data_test: x_batch, y_target_train: y_vals_train, y_target_test: y_batch}) print('Batch #' + str(i+1) + ' MSE: ' + str(np.round(batch_mse,3))) Batch #1 MSE: 23.153 ``` 1. 另外，我們可以查看實際目標值與預測值的直方圖。看待這一點的一個原因是要注意這樣一個事實：使用平均方法，我們無法預測目標的極端： ```py bins = np.linspace(5, 50, 45) plt.hist(predictions, bins, alpha=0.5, label='Prediction') plt.hist(y_batch, bins, alpha=0.5, label='Actual') plt.title('Histogram of Predicted and Actual Values') plt.xlabel('Med Home Value in $1,000s') plt.ylabel('Frequency') plt.legend(loc='upper right') plt.show() ``` 然后我們將獲得直方圖，如下所示：  圖 1：KNN 的預測值和實際目標值的直方圖（其中`k=4`） 一個難以確定的是`k`的最佳值。對于上圖和預測，我們將`k=4`用于我們的模型。我們之所以選擇這個，是因為它給了我們最低的 MSE。這通過交叉驗證來驗證。如果我們在`k`的多個值上使用交叉驗證，我們將看到`k=4`給我們一個最小的 MSE。我們在下圖中說明了這一點。繪制預測值的方差也是值得的，以表明它會隨著我們平均的鄰居越多而減少：  圖 2：各種`k`值的 KNN 預測的 MSE。我們還繪制了測試集上預測值的方差。請注意，隨著`k`的增加，方差會減小。 ## 工作原理 使用最近鄰算法，模型是訓練集。因此，我們不必在模型中訓練任何變量。唯一的參數`k`是通過交叉驗證確定的，以最大限度地減少我們的 MSE。 ## 更多 對于 KNN 的加權，我們選擇直接按距離加權。還有其他選擇我們也可以考慮。另一種常見方法是通過反平方距離加權。 # 使用基于文本的距離 最近鄰比處理數字更通用。只要我們有一種方法來測量特征之間的距離，我們就可以應用最近鄰算法。在本文中，我們將介紹如何使用 TensorFlow 測量文本距離。 ## 準備 在本文中，我們將說明如何在字符串之間使用 TensorFlow 的文本距離度量，Levenshtein 距離（編輯距離）。這將在本章后面重要，因為我們擴展了最近鄰方法以包含帶有文本的特征。 Levenshtein 距離是從一個字符串到另一個字符串的最小編輯次數。允許的編輯是插入字符，刪除字符或用不同的字符替換字符。對于這個秘籍，我們將使用 TensorFlow 的 Levenshtein 距離函數`edit_distance()`。值得說明這個函數的用法，因為它的用法將適用于后面的章節。 > 請注意，TensorFlow 的`edit_distance()`函數僅接受稀疏張量。我們必須創建我們的字符串作為單個字符的稀疏張量。 ## 操作步驟 1. 首先，我們將加載 TensorFlow 并初始化圖： ```py import tensorflow as tf sess = tf.Session() ``` 1. 然后，我們將說明如何計算兩個單詞`'bear'`和`'beer'`之間的編輯距離。首先，我們將使用 Python 的`list()`函數從我們的字符串創建一個字符列表。接下來，我們將從該列表中創建一個稀疏的 3D 矩陣。我們必須告訴 TensorFlow 字符索引，矩陣的形狀以及我們在張量中想要的字符。之后，我們可以決定是否要使用總編輯距離`(normalize=False)`或標準化編輯距離`(normalize=True)`，我們將編輯距離除以第二個單詞的長度： ```py hypothesis = list('bear') truth = list('beers') h1 = tf.SparseTensor([[0,0,0], [0,0,1], [0,0,2], [0,0,3]], hypothesis, [1,1,1]) t1 = tf.SparseTensor([[0,0,0], [0,0,1], [0,0,1], [0,0,3],[0,0,4]], truth, [1,1,1]) print(sess.run(tf.edit_distance(h1, t1, normalize=False))) [[ 2.]] ``` > TensorFlow 的文檔將兩個字符串視為提議（假設）字符串和基礎事實字符串。我們將在這里用`h`和`t`張量繼續這個表示法。函數`SparseTensorValue()`是一種在 TensorFlow 中創建稀疏張量的方法。它接受我們希望創建的稀疏張量的索引，值和形狀。 1. 接下來，我們將說明如何將兩個單詞`bear`和`beer`與另一個單詞`beers`進行比較。為了達到這個目的，我們必須復制`beers`以獲得相同數量的可比詞： ```py hypothesis2 = list('bearbeer') truth2 = list('beersbeers') h2 = tf.SparseTensor([[0,0,0], [0,0,1], [0,0,2], [0,0,3], [0,1,0], [0,1,1], [0,1,2], [0,1,3]], hypothesis2, [1,2,4]) t2 = tf.SparseTensor([[0,0,0], [0,0,1], [0,0,2], [0,0,3], [0,0,4], [0,1,0], [0,1,1], [0,1,2], [0,1,3], [0,1,4]], truth2, [1,2,5]) print(sess.run(tf.edit_distance(h2, t2, normalize=True))) [[ 0.40000001 0.2 ]] ``` 1. 在此示例中顯示了將一組單詞與另一單詞進行比較的更有效方法。我們將事先為假設和基本真實字符串創建索引和字符列表： ```py hypothesis_words = ['bear','bar','tensor','flow'] truth_word = ['beers''] num_h_words = len(hypothesis_words) h_indices = [[xi, 0, yi] for xi,x in enumerate(hypothesis_words) for yi,y in enumerate(x)] h_chars = list(''.join(hypothesis_words)) h3 = tf.SparseTensor(h_indices, h_chars, [num_h_words,1,1]) truth_word_vec = truth_word*num_h_words t_indices = [[xi, 0, yi] for xi,x in enumerate(truth_word_vec) for yi,y in enumerate(x)] t_chars = list(''.join(truth_word_vec)) t3 = tf.SparseTensor(t_indices, t_chars, [num_h_words,1,1]) print(sess.run(tf.edit_distance(h3, t3, normalize=True))) [[ 0.40000001] [ 0.60000002] [ 0.80000001] [ 1\. ]] ``` 1. 現在，我們將說明如何使用占位符計算兩個單詞列表之間的編輯距離。這個概念是一樣的，除了我們將`SparseTensorValue()`而不是稀疏張量。首先，我們將創建一個從單詞列表創建稀疏張量的函數： ```py def create_sparse_vec(word_list): num_words = len(word_list) indices = [[xi, 0, yi] for xi,x in enumerate(word_list) for yi,y in enumerate(x)] chars = list(''.join(word_list)) return(tf.SparseTensorValue(indices, chars, [num_words,1,1])) hyp_string_sparse = create_sparse_vec(hypothesis_words) truth_string_sparse = create_sparse_vec(truth_word*len(hypothesis_words)) hyp_input = tf.sparse_placeholder(dtype=tf.string) truth_input = tf.sparse_placeholder(dtype=tf.string) edit_distances = tf.edit_distance(hyp_input, truth_input, normalize=True) feed_dict = {hyp_input: hyp_string_sparse, truth_input: truth_string_sparse} print(sess.run(edit_distances, feed_dict=feed_dict)) [[ 0.40000001] [ 0.60000002] [ 0.80000001] [ 1\. ]] ``` ## 工作原理 在這個秘籍中，我們展示了我們可以使用 TensorFlow 以多種方式測量文本距離。這對于在具有文本特征的數據上執行最近鄰非常有用。當我們執行地址匹配時，我們將在本章后面看到更多內容。 ## 更多 我們應該討論其他文本距離指標。這是一個定義表，描述了兩個字符串`s1`和`s2`之間的其他文本距離： | 名稱 | 描述 | 公式 | | --- | --- | --- | | 漢明距離 | 相同位置的相等字符的數量。僅在字符串長度相等時有效。 | ，其中`I`是相等字符的指示函數。 | | 余弦距離 | `k`差異的點積除以`k`差異的 L2 范數。 |  | | 雅克卡距離 | 共同的字符數除以兩個字符串中的字符總和。 |  | # 使用混合距離函數的計算 在處理具有多個特征的數據觀察時，我們應該意識到特征可以在不同的尺度上以不同的方式縮放。在這個方案中，我們將考慮到這一點，以改善我們的住房價值預測。 ## 準備 擴展最近鄰算法很重要，要考慮不同縮放的變量。在這個例子中，我們將說明如何縮放不同變量的距離函數。具體來說，我們將距離函數作為特征方差的函數進行縮放。 加權距離函數的關鍵是使用權重矩陣。用矩陣運算寫的距離函數變為以下公式：  這里，`A`是一個對角線權重矩陣，我們將用它來縮放每個特征的距離度量。 在本文中，我們將嘗試在波士頓住房價值數據集上改進我們的 MSE。該數據集是不同尺度上的特征的一個很好的例子，并且最近鄰算法將受益于縮放距離函數。 ## 操作步驟 我們將按如下方式處理秘籍： 1. 首先，我們將加載必要的庫并啟動圖會話： ```py import matplotlib.pyplot as plt import numpy as np import tensorflow as tf import requests sess = tf.Session() ``` 1. 接下來，我們將加載數據并將其存儲在 NumPy 數組中。再次注意，我們只會使用某些列進行預測。我們不使用 id，也不使用方差非常低的變量： ```py housing_url = 'https://archive.ics.uci.edu/ml/machine-learning-databases/housing/housing.data' housing_header = ['CRIM', 'ZN', 'INDUS', 'CHAS', 'NOX', 'RM', 'AGE', 'DIS', 'RAD', 'TAX', 'PTRATIO', 'B', 'LSTAT', 'MEDV'] cols_used = ['CRIM', 'INDUS', 'NOX', 'RM', 'AGE', 'DIS', 'TAX', 'PTRATIO', 'B', 'LSTAT'] num_features = len(cols_used) housing_file = requests.get(housing_url) housing_data = [[float(x) for x in y.split(' ') if len(x)>=1] for y in housing_file.text.split('\n') if len(y)>=1] y_vals = np.transpose([np.array([y[13] for y in housing_data])]) x_vals = np.array([[x for i,x in enumerate(y) if housing_header[i] in cols_used] for y in housing_data]) ``` 1. 現在，我們將`x`值縮放到 0 到 1 之間，最小 - 最大縮放： ```py x_vals = (x_vals - x_vals.min(0)) / x_vals.ptp(0) ``` 1. 然后，我們將創建對角線權重矩陣，該矩陣將通過特征的標準偏差提供距離度量的縮放： ```py weight_diagonal = x_vals.std(0) weight_matrix = tf.cast(tf.diag(weight_diagonal), dtype=tf.float32) ``` 1. 現在，我們將數據分成訓練和測試集。我們還將聲明`k`，最近鄰的數量，并使批量大小等于測試集大小： ```py train_indices = np.random.choice(len(x_vals), round(len(x_vals)*0.8), replace=False) test_indices = np.array(list(set(range(len(x_vals))) - set(train_indices))) x_vals_train = x_vals[train_indices] x_vals_test = x_vals[test_indices] y_vals_train = y_vals[train_indices] y_vals_test = y_vals[test_indices] k = 4 batch_size=len(x_vals_test) ``` 1. 我們將聲明接下來需要的占位符。我們有四個占位符 - 訓練和測試集的[??HTG0] - 輸入和`y` - 目標： ```py x_data_train = tf.placeholder(shape=[None, num_features], dtype=tf.float32) x_data_test = tf.placeholder(shape=[None, num_features], dtype=tf.float32) y_target_train = tf.placeholder(shape=[None, 1], dtype=tf.float32) y_target_test = tf.placeholder(shape=[None, 1], dtype=tf.float32) ``` 1. 現在，我們可以聲明我們的距離函數。為了便于閱讀，我們將把距離函數分解為其組件。請注意，我們必須按批量大小平鋪權重矩陣，并使用`batch_matmul()`函數在批量大小中執行批量矩陣乘法： ```py subtraction_term = tf.subtract(x_data_train, tf.expand_dims(x_data_test,1)) first_product = tf.batch_matmul(subtraction_term, tf.tile(tf.expand_dims(weight_matrix,0), [batch_size,1,1])) second_product = tf.batch_matmul(first_product, tf.transpose(subtraction_term, perm=[0,2,1])) distance = tf.sqrt(tf.batch_matrix_diag_part(second_product)) ``` 1. 在我們計算每個測試點的所有訓練距離之后，我們將需要返回頂部 KNN。我們可以使用`top_k()`函數執行此操作。由于此函數返回最大值，并且我們想要最小距離，因此我們返回最大的負距離值。然后，我們將預測作為頂部`k`鄰居的距離的加權平均值： ```py top_k_xvals, top_k_indices = tf.nn.top_k(tf.neg(distance), k=k) x_sums = tf.expand_dims(tf.reduce_sum(top_k_xvals, 1),1) x_sums_repeated = tf.matmul(x_sums,tf.ones([1, k], tf.float32)) x_val_weights = tf.expand_dims(tf.div(top_k_xvals,x_sums_repeated), 1) top_k_yvals = tf.gather(y_target_train, top_k_indices) prediction = tf.squeeze(tf.batch_matmul(x_val_weights,top_k_yvals), squeeze_dims=[1]) ``` 1. 為了評估我們的模型，我們將計算預測的 MSE： ```py mse = tf.divide(tf.reduce_sum(tf.square(tf.subtract(prediction, y_target_test))), batch_size) ``` 1. 現在，我們可以遍歷我們的測試批次并計算每個的 MSE： ```py num_loops = int(np.ceil(len(x_vals_test)/batch_size)) for i in range(num_loops): min_index = i*batch_size max_index = min((i+1)*batch_size,len(x_vals_train)) x_batch = x_vals_test[min_index:max_index] y_batch = y_vals_test[min_index:max_index] predictions = sess.run(prediction, feed_dict={x_data_train: x_vals_train, x_data_test: x_batch, y_target_train: y_vals_train, y_target_test: y_batch}) batch_mse = sess.run(mse, feed_dict={x_data_train: x_vals_train, x_data_test: x_batch, y_target_train: y_vals_train, y_target_test: y_batch}) print('Batch #' + str(i+1) + ' MSE: ' + str(np.round(batch_mse,3))) Batch #1 MSE: 21.322 ``` 1. 作為最終比較，我們可以使用以下代碼繪制實際測試集的住房值分布和測試集的預測： ```py bins = np.linspace(5, 50, 45) plt.hist(predictions, bins, alpha=0.5, label='Prediction') plt.hist(y_batch, bins, alpha=0.5, label='Actual') plt.title('Histogram of Predicted and Actual Values') plt.xlabel('Med Home Value in $1,000s') plt.ylabel('Frequency') plt.legend(loc='upper right') plt.show() ``` 我們將獲得前面代碼的以下直方圖：  圖 3：波士頓數據集上預測房屋價值和實際房屋價值的兩個直方圖；這一次，我們為每個特征不同地縮放了距離函數 ## 工作原理 我們通過引入一種縮放每個特征的距離函數的方法來減少測試集上的 MSE。在這里，我們通過特征標準偏差的因子來縮放距離函數。這提供了更準確的測量視圖，其中測量哪些點是最近的鄰居。由此，我們還將頂部`k`鄰域的加權平均值作為距離的函數，以獲得住房價值預測。 ## 更多 該縮放因子還可以用于最近鄰距離計算中的向下加權或向上加權的特征。這在我們比某些特征更信任某些特征的情況下非常有用。 # 使用地址匹配的示例 現在我們已經測量了數值和文本距離，我們將花一些時間學習如何將它們組合起來測量具有文本和數字特征的觀察之間的距離。 ## 準備 最近鄰是一種用于地址匹配的好算法。地址匹配是一種記錄匹配，其中我們在多個數據集中具有地址并且想要匹配它們。在地址匹配中，我們可能在地址，不同城市或不同的郵政編碼中存在拼寫錯誤，但它們可能都指向相同的地址。在地址的數字和字符組件上使用最近鄰算法可以幫助我們識別實際上相同的地址。 在此示例中，我們將生成兩個數據集。每個數據集將包含街道地址和郵政編碼。但是，一個數據集在街道地址中存在大量拼寫錯誤。我們將非拼寫數據集作為我們的黃金標準，并將為每個拼寫錯誤地址返回一個地址，該地址最接近字符串距離（對于街道）和數字距離（對于郵政編碼）的函數。 代碼的第一部分將側重于生成兩個數據集。然后，代碼的第二部分將運行測試集并返回訓練集中最接近的地址。 ## 操作步驟 我們將按如下方式處理秘籍： 1. 我們將從加載必要的庫開始： ```py import random import string import numpy as np import tensorflow as tf ``` 1. 我們現在將創建參考數據集。為了顯示簡潔的輸出，我們只會使每個數據集由`10`地址組成（但它可以運行更多）： ```py n = 10 street_names = ['abbey', 'baker', 'canal', 'donner', 'elm'] street_types = ['rd', 'st', 'ln', 'pass', 'ave'] rand_zips = [random.randint(65000,65999) for i in range(5)] numbers = [random.randint(1, 9999) for i in range(n)] streets = [random.choice(street_names) for i in range(n)] street_suffs = [random.choice(street_types) for i in range(n)] zips = [random.choice(rand_zips) for i in range(n)] full_streets = [str(x) + ' ' + y + ' ' + z for x,y,z in zip(numbers, streets, street_suffs)] reference_data = [list(x) for x in zip(full_streets,zips)] ``` 1. 要創建測試集，我們需要一個函數，它將在字符串中隨機創建一個拼寫錯誤并返回結果字符串： ```py def create_typo(s, prob=0.75): if random.uniform(0,1) < prob: rand_ind = random.choice(range(len(s))) s_list = list(s) s_list[rand_ind]=random.choice(string.ascii_lowercase) s = ''.join(s_list) return s typo_streets = [create_typo(x) for x in streets] typo_full_streets = [str(x) + ' ' + y + ' ' + z for x,y,z in zip(numbers, typo_streets, street_suffs)] test_data = [list(x) for x in zip(typo_full_streets,zips)] ``` 1. 現在，我們可以初始化圖會話并聲明我們需要的占位符。我們在每個測試和參考集中需要四個占位符，我們需要一個地址和郵政編碼占位符： ```py sess = tf.Session() test_address = tf.sparse_placeholder( dtype=tf.string) test_zip = tf.placeholder(shape=[None, 1], dtype=tf.float32) ref_address = tf.sparse_placeholder(dtype=tf.string) ref_zip = tf.placeholder(shape=[None, n], dtype=tf.float32) ``` 1. 現在，我們將聲明數字拉鏈距離和地址字符串的編輯距離： ```py zip_dist = tf.square(tf.subtract(ref_zip, test_zip)) address_dist = tf.edit_distance(test_address, ref_address, normalize=True) ``` 1. 我們現在將拉鏈距離和地址距離轉換為相似之處。對于相似性，當兩個輸入完全相同時，我們想要`1`的相似性，當它們非常不同時，我們想要`0`附近。對于拉鏈距離，我們可以通過獲取距離，從最大值減去，然后除以距離的范圍來實現。對于地址相似性，由于距離已經在`0`和`1`之間縮放，我們只需從 1 中減去它以獲得相似性： ```py zip_max = tf.gather(tf.squeeze(zip_dist), tf.argmax(zip_dist, 1)) zip_min = tf.gather(tf.squeeze(zip_dist), tf.argmin(zip_dist, 1)) zip_sim = tf.divide(tf.subtract(zip_max, zip_dist), tf.subtract(zip_max, zip_min)) address_sim = tf.subtract(1., address_dist) ``` 1. 為了結合兩個相似度函數，我們將采用兩者的加權平均值。對于這個秘籍，我們對地址和郵政編碼給予同等重視。我們可以根據我們對每個特征的信任程度來改變這一點。然后，我們將返回參考集的最高相似度的索引： ```py address_weight = 0.5 zip_weight = 1\. - address_weight weighted_sim = tf.add(tf.transpose(tf.multiply(address_weight, address_sim)), tf.multiply(zip_weight, zip_sim)) top_match_index = tf.argmax(weighted_sim, 1) ``` 1. 為了在 TensorFlow 中使用編輯距離，我們必須將地址字符串轉換為稀疏向量。在本章的先前秘籍中，使用基于文本的距離，我們創建了以下函數，我們也將在此秘籍中使用它： ```py def sparse_from_word_vec(word_vec): num_words = len(word_vec) indices = [[xi, 0, yi] for xi,x in enumerate(word_vec) for yi,y in enumerate(x)] chars = list(''.join(word_vec)) # Now we return our sparse vector return tf.SparseTensorValue(indices, chars, [num_words,1,1]) ``` 1. 我們需要將參考數據集中的地址和郵政編碼分開，以便在循環測試集時將它們提供給占位符： ```py reference_addresses = [x[0] for x in reference_data] reference_zips = np.array([[x[1] for x in reference_data]]) ``` 1. 我們需要使用我們在步驟 8 中創建的函數創建稀疏張量參考地址集： ```py sparse_ref_set = sparse_from_word_vec(reference_addresses) ``` 1. 現在，我們可以循環遍歷測試集的每個條目，并返回它最接近的引用集的索引。我們將為每個條目打印測試和參考集。如您所見，我們在此生成的數據集中獲得了很好的結果： ```py for i in range(n): test_address_entry = test_data[i][0] test_zip_entry = [[test_data[i][1]]] # Create sparse address vectors test_address_repeated = [test_address_entry] * n sparse_test_set = sparse_from_word_vec(test_address_repeated) feeddict={test_address: sparse_test_set, test_zip: test_zip_entry, ref_address: sparse_ref_set, ref_zip: reference_zips} best_match = sess.run(top_match_index, feed_dict=feeddict) best_street = reference_addresses[best_match[0]] [best_zip] = reference_zips[0][best_match] [[test_zip_]] = test_zip_entry print('Address: ' + str(test_address_entry) + ', ' + str(test_zip_)) print('Match : ' + str(best_street) + ', ' + str(best_zip)) ``` 我們將得到以下結果： ```py Address: 8659 beker ln, 65463 Match : 8659 baker ln, 65463 Address: 1048 eanal ln, 65681 Match : 1048 canal ln, 65681 Address: 1756 vaker st, 65983 Match : 1756 baker st, 65983 Address: 900 abbjy pass, 65983 Match : 900 abbey pass, 65983 Address: 5025 canal rd, 65463 Match : 5025 canal rd, 65463 Address: 6814 elh st, 65154 Match : 6814 elm st, 65154 Address: 3057 cagal ave, 65463 Match : 3057 canal ave, 65463 Address: 7776 iaker ln, 65681 Match : 7776 baker ln, 65681 Address: 5167 caker rd, 65154 ``` ```py Match : 5167 baker rd, 65154 Address: 8765 donnor st, 65154 Match : 8765 donner st, 65154 ``` ## 工作原理 在像這樣的地址匹配問題中要弄清楚的一個難點是權重的值以及如何縮放距離。這可能需要對數據本身進行一些探索和洞察。此外，在處理地址時，我們應該考慮除此處使用的組件之外的組件。我們可以將街道號碼視為街道地址的獨立組成部分，甚至可以包含其他組成部分，例如城市和州。 > 處理數字地址組件時，請注意它們可以被視為數字（具有數字距離）或字符（具有編輯距離）。由您決定選擇哪個。請注意，如果我們認為郵政編碼中的拼寫錯誤來自人為錯誤而不是計算機映射錯誤，我們可以考慮使用郵政編碼的編輯距離。 為了了解拼寫錯誤如何影響結果，我們鼓勵讀者更改拼寫錯誤函數以進行更多拼寫錯誤或更頻繁的拼寫錯誤，并增加數據集大小以查看此算法的工作情況。 # 使用最近鄰進行圖像識別 最近鄰也可用于圖像識別。圖像識別數據集的問題世界是 MNIST 手寫數字數據集。由于我們將在后面的章節中將此數據集用于各種神經網絡圖像識別算法，因此將結果與非神經網絡算法進行比較將會很棒。 ## 準備 MNIST 數字數據集由數千個大小為`28×28`像素的標記圖像組成。雖然這被認為是一個小圖像，但它對于最近鄰算法總共有 784 個像素（或特征）。我們將通過考慮最近的`k`鄰居（`k=4`，在該示例中）的模式預測來計算該分類問題的最近鄰預測。 ## 操作步驟 我們將按如下方式處理秘籍： 1. 我們將從加載必要的庫開始。請注意，我們還將導入 Python 圖像庫（PIL），以便能夠繪制預測輸出的樣本。 TensorFlow 有一個內置方法來加載我們將使用的 MNIST 數據集，如下所示： ```py import random import numpy as np import tensorflow as tf import matplotlib.pyplot as plt from PIL import Image from tensorflow.examples.tutorials.mnist import input_data ``` 1. 現在，我們將啟動圖會話并以單熱編碼形式加載 MNIST 數據： ```py sess = tf.Session() mnist = input_data.read_data_sets("MNIST_data/", one_hot=True) ``` > 單熱編碼是更適合數值計算的分類值的數值表示。這里，我們有 10 個類別（數字 0-9），并將它們表示為長度為 10 的 0-1 向量。例如，類別 0 由向量`1,0,0,0,0,0`表示，類別 1 用`0,1,0,0,0,0`表示，依此類推。 1. 因為 MNIST 數據集很大并且計算數萬個輸入上的 784 個特征之間的距離在計算上是困難的，所以我們將采樣一組較小的圖像來訓練。此外，我們將選擇一個可被 6 整除的測試集編號，僅用于繪圖目的，因為我們將繪制最后一批六個圖像以查看結果的示例： ```py train_size = 1000 test_size = 102 rand_train_indices = np.random.choice(len(mnist.train.images), train_size, replace=False) rand_test_indices = np.random.choice(len(mnist.test.images), test_size, replace=False) x_vals_train = mnist.train.images[rand_train_indices] x_vals_test = mnist.test.images[rand_test_indices] y_vals_train = mnist.train.labels[rand_train_indices] y_vals_test = mnist.test.labels[rand_test_indices] ``` 1. 我們將聲明我們的`k`值和批量大小： ```py k = 4 batch_size=6 ``` 1. 現在，我們將初始化將添加到圖中的占位符： ```py x_data_train = tf.placeholder(shape=[None, 784], dtype=tf.float32) x_data_test = tf.placeholder(shape=[None, 784], dtype=tf.float32) y_target_train = tf.placeholder(shape=[None, 10], dtype=tf.float32) y_target_test = tf.placeholder(shape=[None, 10], dtype=tf.float32) ``` 1. 然后我們將聲明我們的距離度量。在這里，我們將使用 L1 度量（絕對值）： ```py distance = tf.reduce_sum(tf.abs(tf.subtract(x_data_train, tf.expand_dims(x_data_test,1))), reduction_indices=2) ``` > 請注意，我們也可以使用以下代碼來改變距離函數：`distance = tf.sqrt(tf.reduce_sum(tf.square(tf.subtract(x_data_train, tf.expand_dims(x_data_test,1))), reduction_indices=1))`。 1. 現在，我們將找到最接近的頂級`k`圖像并預測模式。該模式將在單熱編碼索引上執行，計數最多： ```py top_k_xvals, top_k_indices = tf.nn.top_k(tf.negative(distance), k=k) prediction_indices = tf.gather(y_target_train, top_k_indices) count_of_predictions = tf.reduce_sum(prediction_indices, reduction_indices=1) prediction = tf.argmax(count_of_predictions) ``` 1. 我們現在可以遍歷我們的測試集，計算預測并存儲它們，如下所示： ```py num_loops = int(np.ceil(len(x_vals_test)/batch_size)) test_output = [] actual_vals = [] for i in range(num_loops): min_index = i*batch_size max_index = min((i+1)*batch_size,len(x_vals_train)) x_batch = x_vals_test[min_index:max_index] y_batch = y_vals_test[min_index:max_index] predictions = sess.run(prediction, feed_dict={x_data_train: x_vals_train, x_data_test: x_batch, y_target_train: y_vals_train, y_target_test: y_batch}) test_output.extend(predictions) actual_vals.extend(np.argmax(y_batch, axis=1)) ``` 1. 現在我們已經保存了實際和預測的輸出，我們可以計算出準確率。由于我們對測試/訓練數據集進行隨機抽樣，這會發生變化，但最終我們的準確率值應該在 80%-90% 左右： ```py accuracy = sum([1./test_size for i in range(test_size) if test_output[i]==actual_vals[i]]) print('Accuracy on test set: ' + str(accuracy)) Accuracy on test set: 0.8333333333333325 ``` 1. 以下是繪制前面批量結果的代碼： ```py actuals = np.argmax(y_batch, axis=1) Nrows = 2 Ncols = 3 for i in range(len(actuals)): plt.subplot(Nrows, Ncols, i+1) plt.imshow(np.reshape(x_batch[i], [28,28]), cmap='Greys_r') plt.title('Actual: ' + str(actuals[i]) + ' Pred: ' + str(predictions[i]), fontsize=10) frame = plt.gca() frame.axes.get_xaxis().set_visible(False) frame.axes.get_yaxis().set_visible(False) ``` 結果如下：  圖 4：我們運行最近鄰預測的最后一批六個圖像。我們可以看到，我們并沒有完全正確地獲得所有圖像。 ## 工作原理 給定足夠的計算時間和計算資源，我們可以使測試和訓練集更大。這可能會提高我們的準確率，也是防止過擬合的常用方法。另外，請注意，此算法需要進一步探索理想的`k`值進行選擇。可以在數據集上進行一組交叉驗證實驗后選擇`k`值。 ## 更多 我們還可以使用最近鄰算法來評估用戶看不見的數字。有關使用此模型評估用戶輸入數字的方法，[請參閱在線倉庫](https://github.com/nfmcclure/tensorflow_cookbook)。 在本章中，我們探討了如何使用 KNN 算法進行回歸和分類。我們討論了距離函數的不同用法，以及如何將它們混合在一起。我們鼓勵讀者探索不同的距離度量，權重和`k`值，以優化這些方法的準確率。