python中怎么模擬k臨近算法

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

1. 本章第一個(gè)程序是求向量的范數(shù)

import math
# combinations函數(shù)用于組合，表示從n中取出m個(gè)
# 作為對(duì)比，permutations函數(shù)用于排序，表示從n中依次取出m個(gè)
# from itertools import combinations

def L(x, y, p):
    if len(x) == len(y) and len(x) > 1:  # 進(jìn)行計(jì)算的前提
        sum = 0
        for i in range(len(x)):  # i表示下標(biāo)
            sum += math.pow(abs(x[i] - y[i]), p)  # pow求冪，abs求絕對(duì)值
        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("當(dāng)前次數(shù)：{}，當(dāng)前r：{}".format(i, r))
        print("當(dāng)前最?。?quot;)
        print(min(zip(r.values(), r.keys())))

輸出結(jié)果：

當(dāng)前次數(shù)：1，當(dāng)前r：{'1-[5, 1]': 4.0, '1-[4, 4]': 6.0}
當(dāng)前最?。?
(4.0, '1-[5, 1]')
當(dāng)前次數(shù)：2，當(dāng)前r：{'1-[5, 1]': 4.0, '1-[4, 4]': 4.242640687119285}
當(dāng)前最?。?
(4.0, '1-[5, 1]')
當(dāng)前次數(shù)：3，當(dāng)前r：{'1-[5, 1]': 3.9999999999999996, '1-[4, 4]': 3.7797631496846193}
當(dāng)前最?。?
(3.7797631496846193, '1-[4, 4]')
當(dāng)前次數(shù)：4，當(dāng)前r：{'1-[5, 1]': 4.0, '1-[4, 4]': 3.5676213450081633}
當(dāng)前最?。?
(3.5676213450081633, '1-[4, 4]')

2. 第二個(gè)程序，模擬k臨近算法

思想：遍歷所有的點(diǎn)，找出最近的k個(gè)點(diǎn)，通過(guò)多數(shù)表決，決定測(cè)試點(diǎn)的分類。這種方法在訓(xùn)練集大時(shí)非常耗時(shí)。

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  # 用于劃分?jǐn)?shù)據(jù)
from collections import Counter  # 計(jì)數(shù)器

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

    def predict(self, X):
        knn_list = []
        # 先求出三個(gè)點(diǎn)的“距離”，這里的k=3，p=2。根據(jù)需要修改
        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]))
        # 然后，遞歸遍歷剩下的點(diǎn)，通過(guò)判斷：距離  是否比  已經(jīng)計(jì)算的距離  小，小就替換。最終這個(gè)列表剩下的是最臨近的三個(gè)點(diǎn)
        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中最后一行取出來(lái)，即取出了最臨近的三個(gè)點(diǎn)的類別
        knn = [k[-1] for k in knn_list]
        # 用計(jì)數(shù)器，這一步結(jié)果應(yīng)該是{"1":數(shù)量，“0”：數(shù)量 }
        count_pairs = Counter(knn)
        # count_pairs.items()存儲(chǔ)的是，[類別，數(shù)量]
        # 按照列表的第二維進(jìn)行排序，從小到大。
        # 這里排序考慮到有些數(shù)據(jù)不止兩種類型。
        # [-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]
# 將數(shù)據(jù)劃分成訓(xùn)練集和測(cè)試集，測(cè)試集占比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("評(píng)分：")
print(clf.score(X_test, y_test))

test_point = [5.0, 4.0]
print('test point score:{}'.format(clf.predict(test_point)))  # 輸出這個(gè)點(diǎn)可能的類別，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()

結(jié)果： 評(píng)分大多數(shù)時(shí)候1.0，偶爾0.96

3. 用kd樹(shù)實(shí)現(xiàn)k臨近算法

在訓(xùn)練集很大時(shí)，我們通過(guò)構(gòu)架kd樹(shù)以加快檢索速度。

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

在這個(gè)例子中，程序選擇坐標(biāo)軸（即特征）是從0開(kāi)始的，這樣子并不一定合理。

更合理的選擇特征的方式是：選當(dāng)前所有特征中方差最大的特征。因?yàn)檫@樣子方便我們更快的搜索出最近鄰。就好比梯度下降中，我們從橢圓的中心向邊緣下降。如果我們從橢圓的長(zhǎng)軸下降 花費(fèi)的時(shí)間 自然比 從短軸下降 花費(fèi)的時(shí)間 要多！再比如，下山，方差大就好比陡一些，方差小就好比緩一些，我們自然選擇陡一些的，這樣我們可以更快地下山。

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

# 定義一個(gè)namedtuple,分別存放最近坐標(biāo)點(diǎn)、最近距離和訪問(wèn)過(guò)的節(jié)點(diǎn)數(shù)
result = namedtuple("Result_tuple",
                    "nearest_point  nearest_dist  nodes_visited")


# kd-tree每個(gè)結(jié)點(diǎn)中主要包含的數(shù)據(jù)結(jié)構(gòu)如下
class KdNode(object):
    def __init__(self, dom_elt, split, left, right):
        self.dom_elt = dom_elt  # k維向量節(jié)點(diǎn)(k維空間中的一個(gè)樣本點(diǎn))
        self.split = split  # 整數(shù)（進(jìn)行分割維度的序號(hào)）
        self.left = left  # 該結(jié)點(diǎn)分割超平面左子空間構(gòu)成的kd-tree
        self.right = right  # 該結(jié)點(diǎn)分割超平面右子空間構(gòu)成的kd-tree


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

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

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

        self.root = CreateNode(0, data)  # 從第0維分量開(kāi)始構(gòu)建kd樹(shù),返回根節(jié)點(diǎn)


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


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

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

        if target[s] <= pivot[s]:  # 如果目標(biāo)點(diǎn)第s維小于分割軸的對(duì)應(yīng)值(目標(biāo)離左子樹(shù)更近)
            nearer_node = kd_node.left  # 下一個(gè)訪問(wèn)節(jié)點(diǎn)為左子樹(shù)根節(jié)點(diǎn)
            further_node = kd_node.right  # 同時(shí)記錄下右子樹(shù)
        else:  # 目標(biāo)離右子樹(shù)更近
            nearer_node = kd_node.right  # 下一個(gè)訪問(wèn)節(jié)點(diǎn)為右子樹(shù)根節(jié)點(diǎn)
            further_node = kd_node.left

        temp1 = travel(nearer_node, target, max_dist)  # 進(jìn)行遍歷找到包含目標(biāo)點(diǎn)的區(qū)域

        nearest = temp1.nearest_point  # 以此葉結(jié)點(diǎn)作為“當(dāng)前最近點(diǎn)”
        dist = temp1.nearest_dist  # 更新最近距離

        nodes_visited += temp1.nodes_visited

        if dist < max_dist:
            max_dist = dist  # 最近點(diǎn)將在以目標(biāo)點(diǎn)為球心，max_dist為半徑的超球體內(nèi)

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

        # 計(jì)算目標(biāo)點(diǎn)與分割點(diǎn)的歐氏距離
        temp_dist = sqrt(sum((p1 - p2)**2 for p1, p2 in zip(pivot, target)))

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

        # 檢查另一個(gè)子結(jié)點(diǎn)對(duì)應(yīng)的區(qū)域是否有更近的點(diǎn)
        temp2 = travel(further_node, target, max_dist)

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


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


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


# 產(chǎn)生n個(gè)k維隨機(jī)向量
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))            # 構(gòu)建包含四十萬(wàn)個(gè)3維空間樣本點(diǎn)的kd樹(shù)
ret2 = find_nearest(kd2, [0.1, 0.5, 0.8])      # 四十萬(wàn)個(gè)樣本點(diǎn)中尋找離目標(biāo)最近的點(diǎn)
t1 = clock()
print("time: ", t1-t0, "s")  # 找出最近點(diǎn)的時(shí)間
print(ret2)  # 輸出找打的最近點(diǎn)相關(guān)信息

看完上述內(nèi)容，你們對(duì)python中怎么模擬k臨近算法有進(jìn)一步的了解嗎？如果還想了解更多知識(shí)或者相關(guān)內(nèi)容，請(qǐng)關(guān)注億速云行業(yè)資訊頻道，感謝大家的支持。