Py 机器基础及其实践 3

第3章K近邻算法与参数估计3.1KNN算法原理3.3KNN算法的优缺点3.2KNN算法的应用3.4非参数估计3.5非参数估计算法的实现13.1KNN算法原理K近邻算法就是生活里“随大流”的逻辑——“看身边最熟的几个人是啥样，你就大概是啥样”。2/48小明刚转到一所新的学校，想知道班里一个没有说过话的同学A是“学霸组”还是“玩机组”。他不好意思直接去问，就观察：先看这位同学A课间总跟谁待着（离得最近的人）；他观察了与同学A走的最近的3（K=3）个同学，这3个人里有2个总在刷题（只有学霸符合这个特征），1个总在打游戏（玩家）；于是基本能断定：这个新同学A大概率也是学霸组的。对未标记样本的类别，由距离其最近的K个邻居投票来决定属于哪个类别。假设有一个已标记好的数据集，此时有一个未标记的数据样本，我们的任务是预测出这个数据样本所属的类别。KNN的原理是：计算待标记样本和数据集中每个样本的距离，取距离最近的k个样本。待标记的样本所属类别就由这K个距离最近的样本投票产生。3/48第1步，“认亲”——先找到谁是“近邻”。第2步，“挑人”——选几个最亲的（确定K值）。第3步，“随大流”——多数说了算。4/48KNN算法步骤假设X_test为待标记的样本，X_train为已标记的数据集，算法原理描述如下：（1）遍历X_train中的所有样本，计算每个样本与X_test的距离，并把距离保存在数组D[]中。（2）对数组D[]进行排序，取距离最近的k个点，记为X_knn。（3）在X_knn中统计每个类别的个数，即class0在X_knn中有几个样本；class1在X_knn中有几个样本等。待标记样本的类别，就是在X_knn中样本个数最多的那个类别。例如，在图4-1中，有两类不同的样本数据，分别用三角形和正方形表示，而中间的圆形表示的是待分类的数据，还不知道属于哪一类，我们用“？”标记。下面我们根据K近邻的思想为该圆形表示的样本进行分类。如果K=5，在圆形最近的样本点中，有4个正方形和1个三角形，根据少数从属于多数的原则，判定圆形这个待分类样本属于正方形表示的样本一类。如果K=11，在离圆形最近的样本中，有6个三角形和5个正方形，还是少数从属于多数的原则，判定圆形这个待分类样本属于三角形一类。5/481.闵可夫斯基距离6/48

两个样本点之间的距离度量常用的距离度量方法有：闵可夫斯基距离、马氏距离、汉明距离、夹角余弦等。闵可夫斯基距离（MinkowskiDistance）将样本看作高维空间中的点进行距离度量。对于n维空间中任意两个样本点和，P和Q的闵可夫斯基距离定义为：其中，p≥1，为的p范数。当p=1时，有：7/48此时，的取值就是两个点的绝对值之和，称为曼哈顿距离（ManhattanDistance）。几何意义就是沿水平方向从P到Q的距离。当p=2时，P和Q的距离为：

就表示二维空间中两个点P和Q之间的直线距离，称为欧几里得距离或欧氏距离（EuclideanDistance）。defeuclidean_distance(p,q):"""

计算两个n维点p和q的欧氏距离:paramp:点1的坐标，如列表/元组[x1,x2,...,xn]:paramq:点2的坐标，如列表/元组[y1,y2,...,yn]:return:欧氏距离数值"""#确保两个点维度一致iflen(p)!=len(q):raiseValueError("两个点的维度必须相同！")

sum_squared=0#初始化平方和forxi,yiinzip(p,q):sum_squared+=(xi-yi)**2#累加各维度差的平方returnsum_squared**0.5#开平方得到距离8/489/482.马氏距离与欧氏距离、曼哈顿距离一样，马氏距离（MahalanobisDistance）常被用于评定数据之间的相似度指标，它可以看作是欧氏距离的修正，修正了欧氏距离中各维度尺度不一致且相关的问题。单个数据点的马氏距离定义为：数据点P和Q之间的马氏距离定义为：其中，是多维随机变量的协方差矩阵，为样本均值。当样本的各个特征向量相互独立，协方差是单位向量，马氏距离就成了欧氏距离。这里的的作用是用于衡量两个变量之间的关联性。1.修正“特征尺度差异”——让不同单位的特征“公平比较”比如有两个特征：•身高（单位cm）：数值范围150-200（跨度大）•年龄（单位岁）：数值范围10-80（跨度小）如果用欧氏距离，身高的“1cm差异”和年龄的“1岁差异”会被直接相加，但显然“身高差10cm”和“年龄差10岁”的实际意义完全不同。欧氏距离会被大尺度特征（身高）主导，小尺度特征（年龄）的影响被“碾压”。10/48协方差矩阵里的方差项（对角线元素），能反映每个特征的“波动幅度”。马氏距离用协方差矩阵的逆，相当于给大尺度特征“缩小权重”、小尺度特征“放大权重”，让它们的差异能被公平比较。比如身高方差大（波动大），协方差矩阵逆的对应元素小，这样身高差异在计算中被“削弱”；年龄方差小（波动小），逆矩阵对应元素大，这样年龄差异就会被“强化”。11/483.汉明距离汉明距离（HammingDistance）需要将处理的样本数据转换为0和1表示的二进制串，样本中各分量的取值只能是0或1，例如字符串“1110”与“1001”之间的汉明距离为3。对于任意样本特征和，有，其汉明距离为：汉明距离常应用在信息论、编码理论、密码学等领域。12/484.夹角余弦夹角余弦（Cosine）度量将样本看成是高维空间中的向量进行度量，度量方法就是计算两个向量的余弦夹角。对于任意两个n维样本和，其夹角余弦为：当n=2时，夹角余弦计算的就是二维空间中两条直线的夹角余弦值。夹角余弦的取值范围为[-1,1]。夹角余弦值越大，表示两个向量的夹角越小；夹角余弦越小，表示两向量的夹角越大。当两个向量的方向重合时，夹角余弦取最大值1；当两个向量的方向完全相反时，夹角余弦取最小值-1。defcosine_similarity(p,q):"""

计算余弦相似性参数：

p(list/tuple):向量1，如[x1,x2,...,xn]q(list/tuple):向量2，如[y1,y2,...,yn]

返回：余弦相似性值（float，范围[-1,1]）

"""#1.检查向量维度是否一致

iflen(p)!=len(q):raiseValueError("两个向量的维度必须相同！")#2.计算点积：Σ(x_i*y_i)dot_product=sum(a*bfora,binzip(p,q))#3.计算向量模长：√(Σx_i²)和√(Σy_i²)norm_p=(sum(a**2forainp))**0.5norm_q=(sum(b**2forbinq))**0.5#4.避免除以0（若模长为0，视为相似性0）

ifnorm_p==0ornorm_q==0:return0.0#5.余弦相似性=点积/模长的乘积

returndot_product/(norm_p*norm_q)13/483.2k近邻算法应用学习基础学习认知能力信息素养高Iris鸢尾花数据集（iris_training.csv）的数据可分为3类（iris-setosa，iris-versicolour，iris-virginica），共150条记录，每类各50个数据，每条记录有4个属性：花萼长度（SepalLength）、花萼宽度（SepalWidth）、花瓣长度（PetalLength）、花瓣宽度（PetalWidth），可以通过这4个特征预测鸢尾花属于哪一类。column_names=['SepalLength','SepalWidth','PetalLength','PetalWidth','Species']iris_data=pd.read_csv("iris_training.csv",header=0,names=column_names)print(df_iris.head())3.2k近邻算法应用学习基础学习认知能力信息素养高Iris鸢尾花数据集（iris_training.csv）的数据可分为3类（iris-setosa，iris-versicolour，iris-virginica），共150条记录，每类各50个数据，每条记录有4个属性：花萼长度（SepalLength）、花萼宽度（SepalWidth）、花瓣长度（PetalLength）、花瓣宽度（PetalWidth），可以通过这4个特征预测鸢尾花属于哪一类。3.2k近邻算法应用学习基础学习认知能力信息素养高Iris鸢尾花数据集（iris_training.csv）的预测类别:[1.0,2.0,0.0,1.0,1.0,1.0,0.0,2.0,1.0,2.0,2.0,0.0,2.0,1.0,1.0,0.0,1.0,0.0,0.0,2.0,0.0,1.0,2.0,2.0,1.0,1.0,0.0,1.0,2.0,1.0]Accuracy:96.66666666666667%3.3非参数估计17/48如果你想知道“你们小区所有住户的平均月收入”——这个“平均月收入”就是一个“参数”，它是整个小区（总体）的一个固定特征，但你不可能挨家挨户问（太麻烦，或者住户太多）。这时候你可以随机找10户人家问问收入，算出这10户的平均月收入（比如8000元）。你心里可能会想：“小区的平均收入大概就是8000元吧？”——这就是用样本（10户）的特征，去猜总体（全小区）的参数（平均收入），这就是“参数估计”。参数估计（parameterestimation）是统计推断的一种方法，根据从总体中抽取的随机样本估计总体分布中未知参数的过程。即先假定研究的问题具有某种数学模型，如正态分布、二项分布，再利用已知类别的学习样本估计里面的参数。18/48你想知道小区居民每天锻炼时长的分布规律（比如大多数人练多久，有没有人练特别久或特别短）。这些数据按时间分段（比如0-10分钟、10-20分钟…）如下：非参数估计(nonparametricestimation)又称为非参数检验，是相对于参数估计来说的一类估计方法，它不假定数据服从某种特定概率分布（如正态分布、泊松分布），直接用已知类别的学习样本的先验知识直接估计数学模型。它完全由数据驱动，更适合复杂、未知或非典型分布的场景。19/48非参数估计的核心思想是“在不假设数据服从某种特定分布的情况下，直接从数据本身估计概率密度函数”，其推导思路可以从“如何用数据‘画’出分布形状”。20/483.3.1非参数估计的推导过程假设px’是x’的密度函数，向量x落在区域R的概率为：假设进行N次独立重复试验，k个向量要么落入区域R中，要不不落入R中，因此随机变量k服从二项分布，记为k~Binomial(N,P)，则N个向量中k个向量落在R内的概率为：有E(k)=NP，Var（k）=NP(1-P)，则k/N的均值和方差分别为：21/48当N→∞时，频率与概率的取值趋于相等，公式为：当N足够小时，p(x)在R上是不变的，

可近似为“密度值p(x)乘以区域体积V”，公式为：对于随机变量X的一组抽样，即使X的值是连续的，我们也可以划分出若干宽度相同的区间，统计这组样本在各个区间的频率，并画出直方图。图4-4所示是均值为0，方差为4的正态分布直方图，其中，x为直方图个数，f(x)为概率密函数。我们对样本X分成k个等间隔区间，假设样本总数为N，每个区间内样本数为qi，则每个区间的概率密度为。因此，x处的概率密度估计可表示为：22/483.3非参数估计3.3.2直方图和Parzen窗估计1.直方图估计法1根据数据的最小值和最大值及窗口大小确定将数据划分为多少区间。2根据测试集样本test_sample确定该样本所在的窗口。3统计测试样本所在窗口中不同类别的训练样本数量correct_class0和correct_class1。4求出每类样本的概率密度并进行比较，将该测试样本test_sample划为概率密度较大的一类。5重复执行步骤1

~4，直到所有测试样本都完成分类。6统计预测的分类与真实的类别，求出分类的准确率。

23/4824/48（1）数据预处理下面使用非参数估计方法对Fish.xls的鱼类数据进行分类，Fish.xls包含一维数据和二维数据两种类型，各2000条，一维数据的前6条数据如表3-2所示。importxlrdfromoperatorimportitemgetterimportmatplotlib.pyplotaspltimportnumpyasnp#读取数据workbook=xlrd.open_workbook(r'Fish.xls')worksheet=workbook.sheet_by_name('long')#直接通过名称获取工作表，移除重复索引赋值n_rows,n_cols=worksheet.nrows,worksheet.ncolsprint(f"数据规模：{n_rows}行，{n_cols}列")#提取数据（跳过表头）fish_data=[]foriinrange(1,n_rows):feat=worksheet.cell(i,0).value#特征值

label=worksheet.cell(i,1).value#真实标签

fish_data.append([feat,label,0,0,0])#[特征,真实标签,类0概率,类1概率,预测标签]#划分数据集train_class0=fish_data[0:500]#类别0训练集train_class1=fish_data[1000:1500]#类别1训练集train_set=train_class0+train_class1test_class0=fish_data[500:1000]#类别0测试集test_class1=fish_data[1500:]#类别1测试集test_set=test_class0+test_class1print(f"训练集规模：{len(train_set)}，测试集规模：{len(test_set)}")25/4826/48#贝叶斯分类参数bin_width=0.5#窗口宽度train_size=500#每类训练样本数correct_class0=0#类别0正确计数correct_class1=0#类别1正确计数

#计算特征值范围max_feat=max(train_set,key=itemgetter(0))[0]min_feat=min(train_set,key=itemgetter(0))[0]num_bins=int((max_feat-min_feat)/bin_width)print(f"特征范围：[{min_feat},{max_feat}]，区间数量：{num_bins}")（2）直方图概率密度估计设置窗口大小bin_width，求出训练集中样本的最大值max_feat和最小值min_feat，计算训练集被划分为多少个区间num_bins。对每一条测试数据test_sample，先以test_sample为中心确定其所处的区间current_feat，然后统计训练集中各个类别有多少样本点落在current_feat中，估计概率密度值。#遍历测试集进行分类fori,test_sampleinenumerate(test_set):current_feat=test_sample[0]#当前测试特征

true_label=test_sample[1]#真实标签

#计算当前特征所在区间

bin_idx=-1forbinxinrange(num_bins):if(current_feat>=min_feat+(binx-1)*bin_width)and(current_feat<=min_feat+binx*bin_width):bin_idx=binxbreak#找到区间后跳出循环，减少计算

#区间边界

lower=min_feat+(bin_idx-1)*bin_widthupper=min_feat+bin_idx*bin_width

#统计区间内训练样本数

count0=sum(1fordintrain_class0iflower<=d[0]<=upper)count1=sum(1fordintrain_class1iflower<=d[0]<=upper)

#计算类条件概率密度

class_pro0=count0/(train_size*bin_width)class_pro1=count1/(train_size*bin_width)27/48（3）对测试样本分类比较窗口内分别属于类别0和类别1的概率大小，将测试样本test_sample划分为概率值较大的一类，并计算分类的准确率。28/48

#保存概率与预测标签（简化判断逻辑）

test_sample[2],test_sample[3]=class_pro0,class_pro1test_sample[4]=0ifclass_pro0>class_pro1else1#二选一，移除重复if#统计正确数（用测试集长度判断类别，避免硬编码500）

ifi<len(test_class0):iftest_sample[4]==true_label:correct_class0+=1else:iftest_sample[4]==true_label:correct_class1+=1#计算准确率acc0=correct_class0/len(test_class0)acc1=correct_class1/len(test_class1)print(f"类别0准确率：{acc0:.4f}，类别1准确率：{acc1:.4f}")29/48（4）数据可视化在实现分类之前，可以通过将数据可视化观察两类数据的分布情况。#绘制分类结果分布直方图plt.rcParams['font.sans-serif']=['SimHei']#提前设置中文字体，避免重复plt.rcParams['axes.unicode_minus']=False

#提取预测结果特征pred0_feats=[d[0]fordintest_setifd[4]==0]pred1_feats=[d[0]fordintest_setifd[4]==1]

plt.hist(pred0_feats,num_bins,color='r',label='类别0')plt.hist(pred1_feats,num_bins,color='b',label='类别1')plt.legend(loc='upperright')plt.title(f"一维数据分布直方图(窗口宽度={bin_width})")plt.show()30/48为了将直方图概率密度可视化，就是将每个区域间的数据概率以直方图形式显示出来，因此，需要首先统计出训练集中每个区域内的样本数，并计算出概率值。我们分别设置窗口为0.5和v=1.0，以对比不同窗口大小情况下的概率密度显示效果和分类准确率。

31/48利用Parzen矩形窗估计概率密度、分类与直方图密度估计不同的是，Parzen矩形窗是以目标样本x作为中心点，根据窗口大小h，判断样本落入以x为中心的窗口内的样本数，从而得到x的概率。Parzen矩形窗估计与直方图估计的区别是：Parzen矩形窗是根据目标样本点x确定矩形窗，直方图估计是先确定矩形窗，然后根据样本点找相应的矩形窗。假设是d维的向量，每个区间是一个超立方体，它在每一维上的棱长都是h，则每个区域的体积是，若定义d维单位方窗函数，公式如下：32/48bin_width=3#窗口宽度train_size=500#每类训练样本数#分类正确计数correct_class0=0correct_class1=0

fori,test_sampleinenumerate(test_set):class0_count=0#类别0落在窗口内的计数

class1_count=0#类别1落在窗口内的计数

current_feat=test_sample[0]#计算窗口上下界

lower=current_feat-bin_width/2upper=current_feat+bin_width/2

fortrain_sampleintrain_class0:iflower<=train_sample[0]<=upper:class0_count+=1fortrain_sampleintrain_cla