python中怎么模擬k臨近算法

今天就跟大家聊聊有關python中怎么模擬k臨近算法，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結了以下內容，希望大家根據這篇文章可以有所收獲。

1. 本章第一個程序是求向量的范數

import math
# combinations函數用于組合，表示從n中取出m個
# 作為對比，permutations函數用于排序，表示從n中依次取出m個
# from itertools import combinations

def L(x, y, p):
    if len(x) == len(y) and len(x) > 1:  # 進行計算的前提
        sum = 0
        for i in range(len(x)):  # i表示下標
            sum += math.pow(abs(x[i] - y[i]), p)  # pow求冪，abs求絕對值
        return math.pow(sum, 1/p)
    else:
        return 0

x1 = [1, 1]
x2 = [5, 1]
x3 = [4, 4]

for i in range(1, 5):
        r = {"1-{}".format(c):L(x1, c, p=i) for c in [x2, x3]}
        print("當前次數：{}，當前r：{}".format(i, r))
        print("當前最小：")
        print(min(zip(r.values(), r.keys())))

輸出結果：

當前次數：1，當前r：{'1-[5, 1]': 4.0, '1-[4, 4]': 6.0}
當前最小：
(4.0, '1-[5, 1]')
當前次數：2，當前r：{'1-[5, 1]': 4.0, '1-[4, 4]': 4.242640687119285}
當前最小：
(4.0, '1-[5, 1]')
當前次數：3，當前r：{'1-[5, 1]': 3.9999999999999996, '1-[4, 4]': 3.7797631496846193}
當前最小：
(3.7797631496846193, '1-[4, 4]')
當前次數：4，當前r：{'1-[5, 1]': 4.0, '1-[4, 4]': 3.5676213450081633}
當前最小：
(3.5676213450081633, '1-[4, 4]')

2. 第二個程序，模擬k臨近算法

思想：遍歷所有的點，找出最近的k個點，通過多數表決，決定測試點的分類。這種方法在訓練集大時非常耗時。

import numpy as np
import pandas as dp
import matplotlib.pyplot as plt

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split  # 用于劃分數據
from collections import Counter  # 計數器

class KNN:
    def __init__(self, X_train, y_train, n_neighbors=3, p=2):  # 設置了k與p，分別表示最臨近的3個點，和距離用二范數決定
        self.n = n_neighbors
        self.p = p
        self.X_train = X_train
        self.y_train = y_train

    def predict(self, X):
        knn_list = []
        # 先求出三個點的“距離”，這里的k=3，p=2。根據需要修改
        for i in range(self.n):
            dist = np.linalg.norm(X - self.X_train[i], ord=self.p)
            knn_list.append((dist, self.y_train[i]))
        # 然后，遞歸遍歷剩下的點，通過判斷：距離  是否比  已經計算的距離  小，小就替換。最終這個列表剩下的是最臨近的三個點
        for i in range(self.n, len(X_train)):
            max_index = knn_list.index(max(knn_list, key=lambda x:x[0]))
            dist = np.linalg.norm(X - self.X_train[i], ord=self.p)
            if knn_list[max_index][0] > dist:
                knn_list[max_index] = (dist, self.y_train[i])
        # 我們將knn_list中最后一行取出來，即取出了最臨近的三個點的類別
        knn = [k[-1] for k in knn_list]
        # 用計數器，這一步結果應該是{"1":數量，“0”：數量 }
        count_pairs = Counter(knn)
        # count_pairs.items()存儲的是，[類別，數量]
        # 按照列表的第二維進行排序，從小到大。
        # 這里排序考慮到有些數據不止兩種類型。
        # [-1][0]取出最后一行的第一維，即最可能的類型
        max_possible = sorted(count_pairs.items(), key=lambda x:x[1])[-1][0]
        return  max_possible

    def score(self, X_test, y_test):
        right_count = 0
        for X, y in zip(X_test, y_test):
            label = self.predict(X)
            if label == y:
                right_count += 1
        return right_count/len(X_test)


iris = load_iris()
df = dp.DataFrame(iris.data, columns=iris.feature_names)
df['label'] = iris.target
df.columns = ["sepal length", "sepal width", "petal length", "petal width", "label"]

data = np.array(df.iloc[:100, [0, 1, -1]])
X, y = data[:, :-1], data[:, -1]
# 將數據劃分成訓練集和測試集，測試集占比0.25
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.25)

clf = KNN(X_train, y_train)
print("評分：")
print(clf.score(X_test, y_test))

test_point = [5.0, 4.0]
print('test point score:{}'.format(clf.predict(test_point)))  # 輸出這個點可能的類別，1或者0

plt.scatter(df[:50]['sepal length'], df[:50]['sepal width'], label="0")
plt.scatter(df[50:100]['sepal length'], df[50:100]['sepal width'], label="1")

plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()
plt.show()

結果： 評分大多數時候1.0，偶爾0.96

3. 用kd樹實現k臨近算法

在訓練集很大時，我們通過構架kd樹以加快檢索速度。

構造kd樹思想：依次選擇坐標軸(即，依次選擇不同的特征)進行切分，并且切分點通常選擇坐標軸的中位數，這樣構造的kd樹是平衡的。注意：平衡的kd樹搜索時的效率未必是最優的。注意，“依次選擇不同的特征”這句話，如果說不同的特征每個都用了一次了，但是此時的葉節點仍有多個數據，這時候需要返回第一個特征再次進行劃分。所以通常的特征選擇公式 ( J mod k ) + 1，其中J為當前節點深度（根節點深度為0），k為樣品特征個數。

在這個例子中，程序選擇坐標軸（即特征）是從0開始的，這樣子并不一定合理。

更合理的選擇特征的方式是：選當前所有特征中方差最大的特征。因為這樣子方便我們更快的搜索出最近鄰。就好比梯度下降中，我們從橢圓的中心向邊緣下降。如果我們從橢圓的長軸下降 花費的時間 自然比 從短軸下降 花費的時間 要多！再比如，下山，方差大就好比陡一些，方差小就好比緩一些，我們自然選擇陡一些的，這樣我們可以更快地下山。

from math import sqrt
from collections import namedtuple
from time import clock
from random import random

# 定義一個namedtuple,分別存放最近坐標點、最近距離和訪問過的節點數
result = namedtuple("Result_tuple",
                    "nearest_point  nearest_dist  nodes_visited")


# kd-tree每個結點中主要包含的數據結構如下
class KdNode(object):
    def __init__(self, dom_elt, split, left, right):
        self.dom_elt = dom_elt  # k維向量節點(k維空間中的一個樣本點)
        self.split = split  # 整數（進行分割維度的序號）
        self.left = left  # 該結點分割超平面左子空間構成的kd-tree
        self.right = right  # 該結點分割超平面右子空間構成的kd-tree


class KdTree(object):
    def __init__(self, data):
        k = len(data[0])  # 數據維度

        def CreateNode(split, data_set):  # 按第split維劃分數據集exset創建KdNode
            if not data_set:  # 數據集為空
                return None
            # key參數的值為一個函數，此函數只有一個參數且返回一個值用來進行比較
            # operator模塊提供的itemgetter函數用于獲取對象的哪些維的數據，參數為需要獲取的數據在對象中的序號
            # data_set.sort(key=itemgetter(split)) # 按要進行分割的那一維數據排序
            data_set.sort(key=lambda x: x[split])
            split_pos = len(data_set) // 2  # //為Python中的整數除法
            median = data_set[split_pos]  # 中位數分割點
            split_next = (split + 1) % k  # cycle coordinates

            # 遞歸的創建kd樹
            return KdNode(
                median,
                split,
                CreateNode(split_next, data_set[:split_pos]),  # 創建左子樹
                CreateNode(split_next, data_set[split_pos + 1:]))  # 創建右子樹

        self.root = CreateNode(0, data)  # 從第0維分量開始構建kd樹,返回根節點


# KDTree的前序遍歷
def preorder(root):
    print(root.dom_elt)
    if root.left:  # 節點不為空
        preorder(root.left)
    if root.right:
        preorder(root.right)


def find_nearest(tree, point):
    k = len(point)  # 數據維度

    def travel(kd_node, target, max_dist):
        if kd_node is None:
            return result([0] * k, float("inf"),
                          0)  # python中用float("inf")和float("-inf")表示正負無窮
        nodes_visited = 1
        s = kd_node.split  # 進行分割的維度
        pivot = kd_node.dom_elt  # 進行分割的“軸”

        if target[s] <= pivot[s]:  # 如果目標點第s維小于分割軸的對應值(目標離左子樹更近)
            nearer_node = kd_node.left  # 下一個訪問節點為左子樹根節點
            further_node = kd_node.right  # 同時記錄下右子樹
        else:  # 目標離右子樹更近
            nearer_node = kd_node.right  # 下一個訪問節點為右子樹根節點
            further_node = kd_node.left

        temp1 = travel(nearer_node, target, max_dist)  # 進行遍歷找到包含目標點的區域

        nearest = temp1.nearest_point  # 以此葉結點作為“當前最近點”
        dist = temp1.nearest_dist  # 更新最近距離

        nodes_visited += temp1.nodes_visited

        if dist < max_dist:
            max_dist = dist  # 最近點將在以目標點為球心，max_dist為半徑的超球體內

        temp_dist = abs(pivot[s] - target[s])  # 第s維上目標點與分割超平面的距離
        if max_dist < temp_dist:  # 判斷超球體是否與超平面相交
            return result(nearest, dist, nodes_visited)  # 不相交則可以直接返回，不用繼續判斷

        # 計算目標點與分割點的歐氏距離
        temp_dist = sqrt(sum((p1 - p2)**2 for p1, p2 in zip(pivot, target)))

        if temp_dist < dist:  # 如果“更近”
            nearest = pivot  # 更新最近點
            dist = temp_dist  # 更新最近距離
            max_dist = dist  # 更新超球體半徑

        # 檢查另一個子結點對應的區域是否有更近的點
        temp2 = travel(further_node, target, max_dist)

        nodes_visited += temp2.nodes_visited
        if temp2.nearest_dist < dist:  # 如果另一個子結點內存在更近距離
            nearest = temp2.nearest_point  # 更新最近點
            dist = temp2.nearest_dist  # 更新最近距離
        return result(nearest, dist, nodes_visited)
    return travel(tree.root, point, float("inf"))  # 從根節點開始遞歸


# data = [[2, 3], [5, 4], [9, 6], [4, 7], [8, 1], [7, 2]]
# kd = KdTree(data)
# preorder(kd.root)  # 前序遍歷kd樹


# 產生一個k維隨機向量，每維分量值在0~1之間
def random_point(k):
    return [random() for _ in range(k)]


# 產生n個k維隨機向量
def random_points(k, n):
    return [random_point(k) for _ in range(n)]


N = 400000
t0 = clock()  # python3.8 移除了clock()
kd2 = KdTree(random_points(3, N))            # 構建包含四十萬個3維空間樣本點的kd樹
ret2 = find_nearest(kd2, [0.1, 0.5, 0.8])      # 四十萬個樣本點中尋找離目標最近的點
t1 = clock()
print("time: ", t1-t0, "s")  # 找出最近點的時間
print(ret2)  # 輸出找打的最近點相關信息

看完上述內容，你們對python中怎么模擬k臨近算法有進一步的了解嗎？如果還想了解更多知識或者相關內容，請關注億速云行業資訊頻道，感謝大家的支持。