NBNN及SIS Measure

2024-05-06 04:08
文章标签 sis measure nbnn

本文主要是介绍NBNN及SIS Measure,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文主要讲一种稀疏表示下的特征相似度度量方法,叫做SIS Measure,该度量方法结合NBNN可以完成目标分类的任务,且对特征空间非聚集的特征分类有很好的效果。相关实验结果可参考文献[2]。本文主要是实现该方法时的一些简单的心得和代码,欢迎交流。

1.  实验步骤
1.1.  NBNN
       首先阅读论文[1],了解了非参数分类器的基本内容,如非参数分类器的优势在于:(1) 能自然地处理大量数据的分类问题;(2) 有效地避免过拟合;(3) 无需学习/训练阶段。同时熟悉了NBNN的算法概要,如下:

1.2.  SIS Measure
      而后开始阅读参考文献[2],了解Similarity Measure的大致内容,进一步理解SIS(Sparsity Induced Similarity) Measure的算法含义。Similarity Measure主要有欧式距离、高斯核的相似度等,它们的不足在于忽略了类的结构信息。在参考文献[2]中,考虑到特征空间中,人们使用高维特征向量,而可以假设每一类的特征向量都属于低维的特征子空间,提出了特征向量的稀疏表示下的相似度度量。 参考文献[2]提出的稀疏引导的相似度度量方法定义如下:

       其中,  L1 范数最小化问题是由Focuss 算法求解的。之所以选择Focuss 算法,是因为:该问题下,对于解向量稀疏度没有很好的先验知识,因此不能使用OMP等方法;另一方面,如采用[2]中所述的linear programming 的方法,由于引入  x+,x−, 将加大程序的空间复杂度。 通过该相似度度量,我们可以得出输入特征向量与其余样本向量的相似度,由此得到一个N×N的相似度矩阵,再由该相似度矩阵通过最近邻算法得到其分类标记。

2.  实验结果
       如图1即为得到的相似度矩阵。

 

       由最终实验预测可知,bed的预测正确率为60%,forest的预测正确率为70%。另实验代码见文档附录。

3.  实验中遇到的问题
3.1.  SIS的理解
       SIS的构造并非只是简单的计算稀疏系数向量,再比较各向量中对应类分量的模值大小,而是需要分别计算出  Sij 和  Sji在最初实验时,我曾选择某一特征向量作为输入,计算其在剩余向量撑成的矩阵中的稀疏系数,继而比较稀疏系数大小来确定其所属类别。虽然这样的处理与文献[2]中Toy problem所示类似,但是却不是SIS度量的正确理解,之后重新修改了代码,实现了完整的SIS度量方式。

3.2.  Wii的设置 
       Wii 虽然在论文中设置为1(符合相似度度量的直观),但是为了代码的简便性,实际实验中预测时设置其为0。这是因为如果实验中将Wii设置为1,预测时需要额外的步骤把对应该项元素值踢出;而将其设置为0,则在预测时Wii对预测不产生影响。

4.  实验反思
       首先本次实验中使用的数据量较小,因此对于论文中采用的“CD”欧式距离特征预选择并未能用到;出于同样的原因,在构造出所有向量的相似度矩阵后,采用最近邻分类时,采用相似度最高的特征向量所属的类作为输入向量的分类标记,一定程度上忽略了类的分布结构信息,影响了分类的准确度。在得到更多数据的前提下,修改以上两点可以获得更高的分类准确度,以及数据量归一化下更快的执行速度。

 

Reference
[1] Boiman O, Shechtman E, Irani M  In defense of nearest-neighbor based image classification[C]//Computer Vision and Pattern Recognition, 2008  CVPR 2008  IEEE Conference on  IEEE, 2008: 1-8 
[2] H   Cheng,  Z   Liu,  L   Hou,  and  J  Yang   Sparsity  induced  similarity  measure  and  its  applications   IEEE Transactions on Circuits and Systems for Video Technology, 2012

 


附录:实验代码(Matlab语言)

clear all; 
close all 
clc load bedroom.mat 
load forest.mat 
[m,n] = size(bedroom); 
%data feature normalization 
for i =1:m Nbedroom(i,:) = bedroom(i,:)./max(bedroom(i,:)); 
end 
for i =1:m NMITforest(i,:) = MITforest(i,:)./max(MITforest(i,:)); 
end 
Nbedroom = Nbedroom'; 
NMITforest = NMITforest';  
[m,n] = size(Nbedroom); 
%parameter 
%% bed  
for k = 1:n fk = Nbedroom(:,k); Gk = [Nbedroom(:,1:k-1) Nbedroom(:,k+1:end) NMITforest]; [x_bed(:,k)] = Focuss(Gk,fk); 
end 
for k = 1:n fk = NMITforest(:,k); Gk = [Nbedroom NMITforest(:,1:k-1) NMITforest(:,k+1:end)]; [x_forest(:,k+n)] = Focuss(Gk,fk); 
end Xk = [x_bed zeros(19,10)]+ x_forest;                        
[M,N] = size(Xk); 
for k = 1:N for i = 1:M x = Xk(:,k); rest = sum(x' * (x > 0)) - max(x(i),0); S(k,i) = max(Xk(i,k),0) ./ (rest); end 
end 
for i = 1:N s = S(i,:);  S_new(i,:) = [s(1:i-1) 0 s(i:end)]; 
end 
W = (S_new + S_new')./2;  
Wnew = W + eye(N);                  
%compute classified probability 
for i = 1:N [whatever,sim_label(i)] = max(W(i,:)); 
end 
class = sim_label < N/2;        
ratebed = sum(class(1:N/2))/length(class(1:N/2)) 
rateforest = sum(~(class(N/2+1:N)))/length(class(N/2+1:N)) 


 

这篇关于NBNN及SIS Measure的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

论文笔记:GEO-BLEU: Similarity Measure for Geospatial Sequences

22 sigspatial 1 intro 提出了一种空间轨迹相似性度量的方法比较了两种传统相似度度量的不足 DTW 基本特征是它完全对齐序列以进行测量,而不考虑它们之间共享的局部特征这适用于完全对齐的序列,但不适用于逐步对齐没有太多意义的序列BLEU 适用于不完全对齐的序列将序列中的地点视为单词,它们的连续组合视为地理空间𝑛-gram,应用这种方法基于局部特征评估地理空间轨迹的相似性然而,

准确率、精确率、召回率、F1(F-Measure)都是什么?

机器学习ML、自然语言处理NLP、信息检索IR等领域,评估(Evaluation)是一个必要的工作,而其评论价值指标往往有如下几点: 准确率 Accuracy; 精准率 Precision; 召回率 Recal; F1-Measure; TP: True Positive 把正的判断为正的数目True Positive,判断正确,且判为了正,即正的预测为正的; FN:False N

ImportError: cannot import name ‘compare_mse‘ from ‘skimage.measure‘

问题描述  在复现模型代码的时候遇到错误:ImportError: cannot import name 'compare_mse' from 'skimage.measure' 。 解决方案 这是由于 scikit-image 的版本问题,由于scikit-image版本升级后就修改了库函数。 方法1(修改scikit-image版本,不推荐): pip install sci

Activtiy完全解析(三、View的显示过程measure、layout、draw)

版权声明:本文为openXu原创文章【openXu的博客】,未经博主允许不得以任何形式转载   在Activity完全解析的第一篇文章 Activtiy完全解析(一、Activity的创建过程)中,我们分析了从调用startActivtiy()到Activtiy创建完成的整个过程。其中**step20:ActivtiyThread.handleLaunchActivity(r, null)

信息检索中常用的评价指标:MAP,nDCG,ERR,F-measure

知识点文本检索常用的评价指标:MAP、nDCG、ERR、F-score/F-measure以及附加的Precision、Recall、AveP、CG、DCG、IDCG、MRR、cascade models 而ROC曲线及其度量指标AUC主要用于分类和识别 一,MAP Precision(P): 准确率(精确度)是指检索得到的文档中相关文档所占的比例,公式如下: precisi

Borel probability measure space (Borel 概率测度空间)是个啥?

设X为某集合 1. σ-algebra 所谓的σ-algebra实则是给定某个集合X,它的一个子集族,这个子集族对取补运算和可数并运算保持封闭。 2.Borel set 如果B = B(X) 是X里面最小的σ-algebra,并且包含了所以X的开子集, 那么B里面的每一个元素(其实是开子集啦)被叫做Borel set. 3.Borel measure 假设(X,d)是一个测量空间

NLP09_机器学习、监督学习、模型搭建流程、朴素贝叶斯、系统评估、准确率,精确率召回率,F1-Measure

基于概率的系统 给定数据集,X代表特征信息,y代表标签 最终学习到x到y的映射关系f 模型f可以表示线性回归、逻辑回归、神经网络 nlp依赖于机器学习 机器学习 算法分类 监督学习,给定标签。无监督学习只有特征,没有标签 朴素贝叶斯:用于文本分类(垃圾邮件过滤,情感分析)上 逻辑回归: CRF: HMM:常用于语言识别 LDA:抽取文本主题 GMM:高斯回归模型 监督学习

odeforces Round #503 (by SIS, Div. 2) C. Elections

题目:点击打开链接 题意:有n个学生,m个政党,每个学生有支持的政党,但是如果你给他一些钱,他就可以给你想让他投的党投票,现在想付出最少的钱使得1政党有绝对优势(票数严格大于其他党)。 分析:有一种贪心策略是一直收买所需钱最少的学生直到符合条件,但是这样显然是有点问题的,有可能其实只用收买一个收钱多的使得他的政党失败就可以了。考虑枚举最终票数。枚举完票数就开始处理,把每个党超过这个票数且收钱最少

A Robust and Simple Measure for Quality-Guided 2 D Phase Unwrapping Algorithms

A Robust and Simple Measure for Quality-Guided 2 D Phase Unwrapping Algorithms 论文总共分为六个部分,分别是:介绍,质量引导求解相位,残差点,载波信号的影响,本文建议的求解质量方法,实验与结论。 质量引导解包 本节中介绍的质量引导解包是2002年的一篇文章:Fast two dimensional phase-unw