《统计学习方法:李航》笔记 从原理到实现(基于python)-- 第3章 k邻近邻法

2024-01-25 09:28

本文主要是介绍《统计学习方法:李航》笔记 从原理到实现(基于python)-- 第3章 k邻近邻法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 第3章 k邻近邻法
    • 3.1 k近邻算法
    • 3.2 k近邻模型
      • 3.2.1 模型
      • 3.2.2 距离度量
      • 3.2.3 k值的选择
      • 3.2.4 分类决策规则
    • 3.3 k近邻法的实现:kd树
      • 3.3.1 构造kd树
      • 3.3.2 搜索kd树
    • 算法实现
      • 课本例3.1
      • iris数据集
      • scikit-learn实例
      • kd树:构造平衡kd树算法
      • 例3.2

《统计学习方法:李航》笔记 从原理到实现(基于python)-- 第3章 k邻近邻法
《统计学习方法:李航》笔记 从原理到实现(基于python)-- 第1章 统计学习方法概论
《统计学习方法:李航》笔记 从原理到实现(基于python)-- 第 2章感知机

我算是有点基础的(有过深度学习和机器学的项目经验),但也是半路出家,无论是学Python还是深度学习,都是从问题出发,边查边做,没有系统的学过相关的知识,这样的好处是入门快(如果想快速入门,大家也可以试试,直接上手项目,从小项目开始),但也存在一个严重的问题就是,很多东西一知半解,容易走进死胡同出不来(感觉有点像陷入局部最优解,找不到出路),所以打算系统的学习几本口碑比较不错的书籍。
  书籍选择: 当然,机器学习相关的书籍有很多,很多英文版的神书,据说读英文版的书会更好,奈何英文不太好,比较难啃。国内也有很多书,周志华老师的“西瓜书”我也有了解过,看了前几章,个人感觉他肯能对初学者更友好一点,讲述的非常清楚,有很多描述性的内容。对比下来,更喜欢《统计学习方法》,毕竟能坚持看完才最重要。
  笔记内容: 笔记内容尽量省去了公式推导的部分,一方面latex编辑太费时间了,另一方面,我觉得公式一定要自己推到一边才有用(最好是手写)。尽量保留所有标题,但内容会有删减,通过标黑和列表的形式突出重点内容,要特意说一下,标灰的部分大家最好读一下(这部分是我觉得比较繁琐,但又不想删掉的部分)。
  代码实现: 最后是本章内容的实践,如果想要对应的.ipynb文件,可以留言

第3章 k邻近邻法

  k近邻法(k-nearest neighbor,k-NN) 是一种基本分类与回归方法。

  k近邻法的输入为实例的特征向量,对应于特征空间的点;输出为实例的类别,可以取多类。

  k近邻法假设给定一个训练数据集,其中的实例类别已定。分类时,对新的实例,根据其k个最近邻的训练实例的类别,通过多数表决等方式进行预测。

  因此,k近邻法不具有显式的学习过程。k近邻法实际上利用训练数据集对特征向量空间进行划分,并作为其分类的“模型”。

  k值的选择距离度量分类决策规则是k近邻法的三个基本要素

3.1 k近邻算法

  k近邻算法简单、直观:给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的k个实例,这k个实例的多数属于某个类,就把该输入实例分为这个类。

k近邻算法:

输入: 训练数据集

T = ( ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . . . . ( x N , y N ) ) T=((x_1,y_1),(x_2,y_2),......(x_N,y_N)) T=((x1,y1),(x2,y2),......(xN,yN))

  其中, x i ∈ R n x_i\in R^n xiRn为实例的特征向量, y i ∈ Y = ( c 1 , c 2 , … , c K ) y_i\in Y=({c_1,c_2,…,c_K}) yiY(c1c2,,cK)为实例的类别

输出: 实例x所属的类y。

  (1)根据给定的距离度量,在训练集T中找出与x最邻近的k个点,涵盖这k个点的x的邻域记作 N k ( x ) N_k(x) Nk(x)
  (2)在 N k ( x ) N_k(x) Nk(x)中根据分类决策规则(如多数表决)决定x的类别y:

y = a r g m a x ∑ x i ∈ N k ( x ) I ( t i = c j ) , i = 1 , 2.... N ; j = 1 , 2.... K y=arg max \sum_{x_i \in N_k(x)}I(t_i=c_j),i=1,2....N;j=1,2....K y=argmaxxiNk(x)I(ti=cj),i=1,2....N;j=1,2....K

  其中,I为指示函数,即当 y i = c j y_i=c_j yicj时I为1,否则I为0。

3.2 k近邻模型

  k近邻法使用的模型实际上对应于对特征空间的划分

  模型由三个基本要素——距离度量、k值的选择和分类决策规则决定。

3.2.1 模型

  特征空间中,对每个训练实例点 x i x_i xi,距离该点比其他点更近的所有点组成一个区域,叫作单元(cell)。每个训练实例点拥有一个单元,所有训练实例点的单元构成对特征空间的一个划分。

  最近邻法将实例 x i x_i xi的类 y i y_i yi作为其单元中所有点类标记(class label)。这样,每个单元的实例点的类别是确定的。

3.2.2 距离度量

  特征空间中两个实例点的距离是两个实例点相似程度的反映。k近邻模型的特征空间一般是 n维实数向量空间 R n R^n Rn 使用的距离是欧氏距离,但也可以是其他距离。

  设特征空间X是n维实数向量空间 R n R^n Rn , x i , x i ∈ X ,x_i,x_i \in X ,xi,xiX x i = ( x i ( 1 ) , x i ( 2 ) … x i ( T ) ) T x_i=(x_i^{(1)},x_i^{(2)}…x_i^{(T)})^T xi=(xi(1),xi(2)xi(T))T x j = ( x j ( 1 ) , x j ( 2 ) … x j ( n ) ) T x_j=(x_j^{(1)},x_j^{(2)}…x_j^{(n)})^T xj=(xj(1),xj(2)xj(n))T**

   x i , x i x_i,x_i xi,xi的距离 L p L_p Lp定义为:

L p ( x i , x j ) = ( ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ p ) 1 p L_p(x_i,x_j)=(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p)^{\frac{1}{p}} Lp(xi,xj)=(l=1nxi(l)xj(l)p)p1

  • 当p≥1。当p=2时,称为欧氏距离(Euclidean distance);
  • 当p=1时,称为曼哈顿距离(Manhattan distance)
  • 当p=∞ 时,它是各个坐标距离的最大值

下面的例子说明,由不同的距离度量所确定的最近邻点是不同的。

在这里插入图片描述

3.2.3 k值的选择

  k值的选择会对k近邻法的结果产生重大影响。

  • 如果选择较小的k值: 就相当于用较小的邻域中的训练实例进行预测
    • “学习”的近似误差(approximation error)会减小,只有与输入实例较近的(相似的)训练实例才会对预测结果起作用。
    • 但缺点是“学习”的估计误差(estimation error)会增大,预测结果会对近邻的实例点非常敏感[2]。(如果邻近的实例点恰巧是噪声,预测就会出错。换句话说,k值的减小就意味着整体模型变得复杂,容易发生过拟合。)
  • 如果选择较大的k值: 就相当于用较大邻域中的训练实例进行预测。
    • 其优点是可以减少学习的估计误差。
    • 但缺点是学习的近似误差会增大。这时与输入实例较远的(不相似的)训练实例也会对预测起作用,使预测发生错误。(k值的增大就意味着整体的模型变得简单。)

  在应用中,k值一般取一个比较小的数值。通常采用交叉验证法来选取最优的k值。

3.2.4 分类决策规则

  k近邻法中的分类决策规则往往是多数表决,即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。
多数表决规则(majority voting rule):

  对给定的实例 x ∈ X x\in X xX,其最近邻的k个训练实例点构成集合 N k ( x ) N_k(x) Nk(x)。如果涵盖 N k ( x ) N_k(x) Nk(x)的区域的类别是 c j c_j cj,那么误分类率是:

1 k ∑ x i ∈ N x ( x ) I ( y i ≠ c j ) = 1 − 1 k ∑ x i ∈ N x ( x ) I ( y i = c j ) \frac{1}{k}\sum_{x_i\in N_x(x)}I(y_i\neq c_j)=1-\frac{1}{k}\sum_{x_i\in N_x(x)}I(y_i=c_j) k1xiNx(x)I(yi=cj)=1k1xiNx(x)I(yi=cj)

  要使误分类率最小即经验风险最小,就要使 ∑ x i ∈ N x ( x ) I ( y i = c j ) \sum_{x_i\in N_x(x)}I(y_i=c_j) xiNx(x)I(yi=cj)最大,所以多数表决规则等价于经验风险最小化

3.3 k近邻法的实现:kd树

  实现k近邻法时,主要考虑的问题是如何对训练数据进行快速k近邻搜索
k近邻法最简单的实现方法是线性扫描(linear scan)。这时要计算输入实例与每一个训练实例的距离。
  为了提高k近邻搜索的效率,可以考虑使用特殊的结构存储训练数据,以减少计算距离的次数。

3.3.1 构造kd树

  kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。

  kd树是二叉树,表示对k维空间的一个划分(partition)。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分,构成一系列的k维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。

构造kd树的方法如下:

  • 构造根结点,使根结点对应于k维空间中包含所有实例点的超矩形区域;
  • 通过下面的递归方法,不断地对k维空间进行切分,生成子结点。
  • 在超矩形区域(结点)上选择一个坐标轴和在此坐标轴上的一个切分点,确定一个超平面,这个超平面通过选定的切分点并垂直于选定的坐标轴,将当前超矩形区域切分为左右两个子区域(子结点);
  • 这时,实例被分到两个子区域。这个过程直到子区域内没有实例时终止(终止时的结点为叶结点)。

在这里插入图片描述

3.3.2 搜索kd树

  下面介绍如何利用kd树进行k近邻搜索。可以看到,利用kd树可以省去对大部分数据点的搜索,从而减少搜索的计算量。

  这里以最近邻为例加以叙述,同样的方法可以应用到k近邻。

  • 给定一个目标点,搜索其最近邻。
  • 首先找到包含目标点的叶结点;
  • 然后从该叶结点出发,依次回退到父结点;
  • 不断查找与目标点最邻近的结点,当确定不可能存在更近的结点时终止。

  这样搜索就被限制在空间的局部区域上,效率大为提高。

  包含目标点的叶结点对应包含目标点的最小超矩形区域。以此叶结点的实例点作为当前最近点。目标点的最近邻一定在以目标点为中心并通过当前最近点的超球体的内部(参阅图3.5)。

  然后返回当前结点的父结点,如果父结点的另一子结点的超矩形区域与超球体相交,那么在相交的区域内寻找与目标点更近的实例点。如果存在这样的点,将此点作为新的当前最近点。算法转到更上一级的父结点,继续上述过程。如果父结点的另一子结点的超矩形区域与超球体不相交,或不存在比当前最近点更近的点,则停止搜索。

在这里插入图片描述

算法实现

import math
from itertools import combinations
def L(x, y, p=2):# x1 = [1, 1], x2 = [5,1]if len(x) == len(y) and len(x) > 1:sum = 0for i in range(len(x)):sum += math.pow(abs(x[i] - y[i]), p)return math.pow(sum, 1 / p)else:return 0

课本例3.1

在这里插入图片描述

x1 = [1, 1]
x2 = [5, 1]
x3 = [4, 4]
# x1, x2
for i in range(1, 5):r = {'1-{}'.format(c): L(x1, c, p=i) for c in [x2, x3]}print(min(zip(r.values(), r.keys())))
==============================
(4.0, '1-[5, 1]')
(4.0, '1-[5, 1]')
(3.7797631496846193, '1-[4, 4]')
(3.5676213450081633, '1-[4, 4]')

iris数据集

python实现,遍历所有数据点,找出n个距离最近的点的分类情况,少数服从多数

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inlinefrom sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from collections import Counter# data
iris = load_iris()
df = pd.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]])
sepal lengthsepal widthpetal lengthpetal widthlabel
05.13.51.40.2
14.93.01.40.2
24.73.21.30.2
34.63.11.50.2
45.03.61.40.2
55.43.91.70.4
64.63.41.40.3
75.03.41.50.2
84.42.91.40.2
94.93.11.50.1
105.43.71.50.2
114.83.41.60.2
124.83.01.40.1
134.33.01.10.1
145.84.01.20.2
155.74.41.50.4
165.43.91.30.4
175.13.51.40.3
185.73.81.70.3
195.13.81.50.3
205.43.41.70.2
215.13.71.50.4
224.63.61.00.2
235.13.31.70.5
244.83.41.90.2
255.03.01.60.2
265.03.41.60.4
275.23.51.50.2
285.23.41.40.2
294.73.21.60.2
1206.93.25.72.3
1215.62.84.92.0
1227.72.86.72.0
1236.32.74.91.8
1246.73.35.72.1
1257.23.26.01.8
1266.22.84.81.8
1276.13.04.91.8
1286.42.85.62.1
1297.23.05.81.6
1307.42.86.11.9
1317.93.86.42.0
1326.42.85.62.2
1336.32.85.11.5
1346.12.65.61.4
1357.73.06.12.3
1366.33.45.62.4
1376.43.15.51.8
1386.03.04.81.8
1396.93.15.42.1
1406.73.15.62.4
1416.93.15.12.3
1425.82.75.11.9
1436.83.25.92.3
1446.73.35.72.5
1456.73.05.22.3
1466.32.55.01.9
1476.53.05.22.0
1486.23.45.42.3
1495.93.05.11.8

150 rows × 5 columns

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()

在这里插入图片描述

data = np.array(df.iloc[:100, [0, 1, -1]])
X, y = data[:,:-1], data[:,-1]
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
class KNN:def __init__(self, X_train, y_train, n_neighbors=3, p=2):"""parameter: n_neighbors 临近点个数parameter: p 距离度量"""self.n = n_neighborsself.p = pself.X_train = X_trainself.y_train = y_traindef predict(self, X):# 取出n个点knn_list = []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(self.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 = [k[-1] for k in knn_list]count_pairs = Counter(knn)
#         max_count = sorted(count_pairs, key=lambda x: x)[-1]max_count = sorted(count_pairs.items(), key=lambda x: x[1])[-1][0]return max_countdef score(self, X_test, y_test):right_count = 0n = 10for X, y in zip(X_test, y_test):label = self.predict(X)if label == y:right_count += 1return right_count / len(X_test)
clf = KNN(X_train, y_train)
clf.score(X_test, y_test)
==============================
0.95test_point = [6.0, 3.0]
print('Test Point: {}'.format(clf.predict(test_point)))
=================================
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.plot(test_point[0], test_point[1], 'bo', label='test_point')
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()

在这里插入图片描述

scikit-learn实例

from sklearn.neighbors import KNeighborsClassifier
clf_sk = KNeighborsClassifier()
clf_sk.fit(X_train, y_train)
======================================
KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',metric_params=None, n_jobs=None, n_neighbors=5, p=2,weights='uniform')clf_sk.score(X_test, y_test)
========================================
0.95

kd树:构造平衡kd树算法

# 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-treeself.right = right  # 该结点分割超平面右子空间构成的kd-treeclass KdTree(object):def __init__(self, data):k = len(data[0])  # 数据维度def CreateNode(split, data_set):  # 按第split维划分数据集exset创建KdNodeif 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)
# 对构建好的kd树进行搜索,寻找与目标点最近的样本点:
from math import sqrt
from collections import namedtuple# 定义一个namedtuple,分别存放最近坐标点、最近距离和访问过的节点数
result = namedtuple("Result_tuple","nearest_point  nearest_dist  nodes_visited")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 = 1s = 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.lefttemp1 = travel(nearer_node, target, max_dist)  # 进行遍历找到包含目标点的区域nearest = temp1.nearest_point  # 以此叶结点作为“当前最近点”dist = temp1.nearest_dist  # 更新最近距离nodes_visited += temp1.nodes_visitedif 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_visitedif 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"))  # 从根节点开始递归

例3.2

在这里插入图片描述

data = [[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]]
kd = KdTree(data)
preorder(kd.root)
==================================
[7, 2]
[5, 4]
[2, 3]
[4, 7]
[9, 6]
[8, 1]
from time import clock
from random import random# 产生一个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)]
ret = find_nearest(kd, [3,4.5])
print (ret)
=========================================
Result_tuple(nearest_point=[2, 3], nearest_dist=1.8027756377319946, nodes_visited=4)
N = 400000
t0 = 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)
=========================================
time:  5.4623788 s
Result_tuple(nearest_point=[0.09929288205798159, 0.4954936771850429, 0.8005722800665575], nearest_dist=0.004597223680778027, nodes_visited=42)

这篇关于《统计学习方法:李航》笔记 从原理到实现(基于python)-- 第3章 k邻近邻法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/642834

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

python: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别: 当你在一个模块(文件)中使用 global 声明变量时,这个变量只在该模块的全局命名空

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

hdu1496(用hash思想统计数目)

作为一个刚学hash的孩子,感觉这道题目很不错,灵活的运用的数组的下标。 解题步骤:如果用常规方法解,那么时间复杂度为O(n^4),肯定会超时,然后参考了网上的解题方法,将等式分成两个部分,a*x1^2+b*x2^2和c*x3^2+d*x4^2, 各自作为数组的下标,如果两部分相加为0,则满足等式; 代码如下: #include<iostream>#include<algorithm

深入探索协同过滤:从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤(UserCF)2. 基于物品的协同过滤(ItemCF)3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代,推荐系统成为连接用户与内容的桥梁。本文聚焦于

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi