机器学习入门5:KNN近邻算法-图像检索-NN最近邻检索和ANN近似最近邻检索

本文是机器学习入门的基础版,学习对象产品经理同学;

目前图像检索中最基础的检索能力:

NN检索-最近邻检索(Nearest Neighbor Search)

ANN检索-近似最近邻检索Approximate Nearest Neighbor。区别于ANN

 

1.概述

最近邻检索就是根据数据的相似性,从数据库中寻找与目标数据最相似的项目。这种相似性通常会被量化到空间上数据之间的距离,可以认为数据在空间中的距离越近,则数据之间的相似性越高。

K最近邻(K-Nearest Neighbor,KNN)检索:当需要查找离目标数据最近的前k个数据项时。

最近邻检索是线性复杂度的,不能满足对于大规模数据检索的时间性能要求。

 

2.应用领域

起初应用于文档检索系统,最近邻检索作为具有查找相似性文档信息的方法;
随后在地理信息系统中,最近邻检索也被广泛应用于位置信息,空间数据关系的查询、分析与统计;
如今在图像检索、数据压缩、模式识别以及机器学习等领域都有非常重要的作用。
在图像处理与检索的研究中,基于内容的图像检索方法(CBIR)是目前的主流。

2.1 图像的内容是什么?

这里的“内容”是指:图像中包含的主要对象的几何形状、颜色强度、表面纹理等外在特性,以及前景与后景的对比程度等整体特征。

图像的描述方式:局部特征描述子(SIFT、SURF、BRIEF) ,全局特征描述子(GIST),特征频率直方图,纹理信息,显著性区域等。

最近邻检索的引入将图像检索转化到特征向量空间,通过查找与目标特征向量距离最近的向量来获得相应图像之间的关系。 这种特征向量之间的距离通常被定义为欧几里得距离(Euclidean distance),即是空间中两点之间的直线距离。

 

3.发展趋势

最近邻检索作为数据检索中使用最为广泛的技术一直以来都是国内外学者研究的热点。近些年,涌现出大量以最近邻检索或近似最近邻检索为基本思想的两类方法。一类是基于提升检索结构性能的方法,主要方法大多基于树形结构;另一类主要基于对数据本身的处理,包括哈希算法、矢量量化方法等。

3.1 最近邻检索(精确检索)

背景:精确检索中数据维度一般较低,所以会采用穷举搜索,即在数据库中依次计算其中样本与所查询数据之间的距离,抽取出所计算出来的距离最小的样本即为所要查找的最近邻。当数据量非常大的时候,搜索效率急剧下降。

基于树结构的最近邻检索方法

概述:由于实际数据会呈现出簇状的聚类形态,因此可以考虑对数据库中的样本数据构建数据索引,索引树就是最常见的方法。其基本思想是对搜索空间进行层次划分,再进行快速匹配。

结论:当数据维度不太高(如d< 20),通常采用树型索引结构对数据进行分区以实现高效索引,如最经典的KD树算法 、R树、M树等等,它们的时间和空间复杂度都是以d为指数的指数级别的,在实际搜索时也取得了良好的效果。

当d=1时,只要采用传统的二分查找法或者各类平衡树就能找到最近邻;
当d=2时,将最近邻检索问题转化为求解查询点究竟落在哪个区域的Voronoi图问题,再通过二分查找树就能很好的解决。

 

3.2 近似最近邻检索

背景:面对庞大的数据量以及数据库中高维的数据信息,现有的基于 NN 的检索方法无法获得理想的检索效果与可接受的检索时间。因此,研究人员开始关注近似最近邻检索(Approximate Nearest Neighbor,ANN)。

概述:近似最近邻检索利用数据量增大后数据之间会形成簇状聚集分布的特性,通过对数据分析聚类的方法对数据库中的数据进行分类或编码,对于目标数据根据其数据特征预测其所属的数据类别,返回类别中的部分或全部作为检索结果。

近似最近邻检索的核心思想:搜索可能是近邻的数据项而不再只局限于返回最可能的项目,在牺牲可接受范围内的精度的情况下提高检索效率。

分类
一种是采用哈希散列的办法,另一种则是矢量量化。

3.2.1 局部敏感哈希(LSH)
核心思想:在高维空间相邻的数据经过哈希函数的映射投影转化到低维空间后,他们落入同一个吊桶的概率很大而不相邻的数据映射到同一个吊桶的概率则很小。在检索时将欧式空间的距离计算转化到汉明(Hamming)空间,并将全局检索转化为对映射到同一个吊桶中的数据进行检索,从而提高了检索速度。这种方法的主要难点在于如何寻找适合的哈希函数。

3.2.2 矢量量化
其代表是乘积量化(PQ)。它的主要思想是将特征向量进行正交分解,在分解后的低维正交子空间上进行量化,由于低维空间可以采用较小的码本进行编码,因此可以降低数据存储空间 。

PQ方法采用基于查找表的非对称距离计算(Asymmetric Distance Computation,ADC)快速求取特征向量之间的距离,在压缩比相同的情况下,与采用汉明距离的二值编码方法,采用ADC的PQ方法的检索精度更高。

感谢参考文献 

机器学习入门2:第一个算法-决策树DecisionTree

本文是机器学习入门的基础版,学习对象产品经理同学;

决策树学习三个过程:1.特征选择。2.构建决策树。3.剪枝

 

1.决策树是什么?

决策树DecisionTree是机器学习中相当经典的一种算法,既可以用作分类,也可以用作回归,同时还适合做集成学习用于随机森林等等,今天就来好好介绍一下决策树算法。

首先,决策树的思想就是非常容易理解的。通俗地讲就是拿到一堆样本之后,我首先根据某个特征,将样本划分为几类,然后在划分的每一类中,又根据新的特征再划分为若干类,这样重复的进行下去,总会达到一个效果,就是所有的样本都有且有唯一一条规则与之对应,这样决策树的构建就完成了。书面地讲就是从一个根节点出发根据某一特征划分成若干个子节点,再根据某一特征递归地划分下去,直到所有的样本都包含在内。其中中间节点通常表示样本的某一特征或者属性,而最后的叶节点则表示某一个类。

提示:若时间充足,请先阅读下方扩展知识点,了解和决策树相关几个概念)

信息

这个是熵和信息增益的基础概念,是对一个抽象事物的命名,无论用不用‘信息’来命名这种抽象事物,或者用其他名称来命名这种抽象事物,这种抽象事物是客观存在的。如果带分类的事物集合可以划分为多个类别当中,则某个类(xi)的信息(量)定义如下:

I(x)用来表示随机变量的信息,p(xi)指是当xi发生时的概率。当事件xi发生的概率p(xi)很小,但是它却发生了,那这个信息量相当大,比如买彩票中奖了,那么这个信息量肯定是很大的。相反,对于大概率事件,人们习以为常,那么这个事件的信息量就很小。这就体现在上述公式中。

信息熵
“信息熵”是度量样本纯度最常用的一种指标。所谓样本纯度,相反而言之就是凌乱程度。如一个数据集U中的样本都属于同一类,那么这时样本纯度最高而凌乱程度最低。信息熵定义为:

其中D表示样本集合,|y|样本中类别的数目, pk表示第k种分类占集合的比例。Ent(D)的值越小,D的纯度越高。

信息增益
信息增益 指的是,使用某一个属性a进行划分后,所带来的纯度提高的大小。一般而言,信息增益越大,意味着使用属性a来进行划分所获得的“纯度提升”越大。信息增益定义如下:

信息增益 = 根节点的信息熵 – 所有分支节点的信息熵的加权和

其中,权值为划分后属性a=ak节点中样本的数量与划分前节点中的样本数量的比值,即概率。概率确保了权重的和为1.

上图描述的是,使用属性a对样本集合D进行划分,因为a有V个取值,因此决策树会有V个分支。划分后每一个节点中样本的数量为属性a=ak的样本的数量。 

问:如何理解:信息增益越大,意味着使用属性a来进行划分所获得的“纯度提升”越大?

    答:因为Ent(D)的值越小,D的纯度越高。而划分后,所有的分支节点的Ent(Dk)的和就是划分后的信息熵,公式体现了前后的差距,如果差距越大,那么就说明划分后所有的分支节点的信息熵越小,纯度提升越大。

增益率

背景:当样本集中的某一属性取值使得所有样本被分到不同类别,此时分支的纯度达到最高,无需再继续划分。然而这样的决策树不具备泛化能力。事实上,信息增益准则对可取值较多的属性有所偏好。

为了减少这种偏好可能带来的影响,因此使用增益率代替信息增益准则选择划分属性。

即增益率(Gain_ratio(D,a))=信息增益Gain(D,a)/属性固有值(IV(a))。
属性A的可能取值越大,固有值IV(a)通常越大。
信息增益率偏向于可能取值减少的属性。因此C4.5算法不直接使用信息增益率来选择划分属性。

基尼值
基尼值 Gini(D) 反映了从数据集中随机抽取两个样本,其类别标记不一致的概率。当数据集的纯度越高,每次抽到不同类别标记的概率越小。打个比方,在一个袋子里装100个乒乓球,其中有99个白球,1个黄球,那么当我们随机抽取两个球的时候,很大概率是抽到两个白球。

所以数据集D的纯度可以用基尼值来度量,其定义如下:

基尼值越小,数据集D纯度越高。

基尼指数

基尼指数是针对于属性定义的,其反映的是,使用属性a进行划分后,所有分支中(使用基尼值度量的)纯度的加权和。

属性a的基尼指数定义如下:

我们在属性集合A中选择划分属性的时候,就选择使得划分后基尼指数最小的属性作为最优划分属性。CART就是用基尼指数来选择划分属性的。

2.如何构建决策树?

构建决策树的关键步骤是分裂属性,指在某个节点按照一类特征属性的不同划分构建不同的分支,使每个分支中的数据类别尽可能的纯。
决策树是一种贪心算法策略,只考虑当前数据特征的最好分割方式,不能回溯操作(只能从上往下分割)
步骤:
1.将所有的特征看成一个一个的节点
2.遍历所有特征,遍历到其中某一个特征时:遍历当前特征的所有分割方式,找到最好的分割点,将数据划分为不同的子节点,计算划分后子节点的纯度信息
3.在遍历的所有特征中,比较寻找最优的特征以及最优特征的最优划分方式,纯度越高,则对当前数据集进行分割操作
4.对新的子节点继续执行2-3步,直到每个最终的子节点都足够纯

决策树算法构建的停止条件:
1.(会导致过拟合)当子节点中只有一种类型的时候停止构建
2.(比较常用)当前节点种样本数小于某个值,同时迭代次数达到指定值,停止构建,此时使用该节点中出现最多的类别样本数据作为对应值

3.决策树三大算法

ID3算法: 内部使用信息熵以及’信息增益‘来进行构建,每次迭代选择信息增益最大的特征属性作为分割属性。只支持离散的特征属
优点:决策树构建速度快,实现简单
缺点:算法依赖样本中出现次数较多的特征属性,但是出现次数最多的属性并不一定最优

C4.5算法:使用’信息增益率‘来构建,在树的构建过程中会进行剪枝操作的优化,能够自动完成对连续属性的离散化处理。选择信息增益率大的属性进行分割
优点:准确率较高,实现简单
缺点:对数据集需要进行多次顺序扫描和排序,效率较低。

CART算法:使用’基尼系数’作为数据纯度的量化指标来构建,选择‘GINI增益率’来分割,越大的即作为当前数据集的分割属性.可用于分类和回归。(二叉树构建)

三种算法主要区别:CART构建的一定是二叉树,ID3,C4.5构建的不一定是二叉树

4.分类树和回归数的区别:

1.分类树是基于概率来构建的,采用信息增益、信息增益率、基尼系数来作为树的评价指标。
2.回归数是基于平均值来构建的,采用均方差作为树的评价指标。 

5.决策树优化策略:

1.决策树欠拟合:没有将不同的数据类别划分开,原因:决策树深度太浅导致。
解决方案:1.增加树的深度。2.使用集成算法,Boosting算法(GBDT)
2.决策树过拟合:学习能力太强,将噪音数据特征也学习到数据分割中了,原因:决策树深度太深导致
解决方案:1.剪枝(调整API中的参数)2.使用集成算法:Bagging算法(随机森林)
 

 6.决策树的剪枝:

1.前置剪枝:是指在决策树生成过程中,对每个节点在划分前先进行估计,若当前的节点划分不能带来决策树泛化的提升,则停止划分并将当前节点标记为叶子节点。(深度浅,容易欠拟合)
2.后置剪枝:是指先从训练数据集中生成一课完整的决策树,然后自底向上对非叶子节点进行考察,若将该节点对应的子树替换为叶子结点能够带来决策树泛化能力的提升,则将该节点替换为叶子节点。 
参考文献:

https://blog.csdn.net/NeilGY/article/details/82746270

https://blog.csdn.net/sinat_22594309/article/details/59090895

https://blog.csdn.net/akirameiao/article/details/79953980

机器学习入门1:算法概述

本文是机器学习入门的基础版,学习对象产品经理同学;

机器学习,简言之:一堆数据,用算法模型进行训练,再用于使用。

似乎算法看上去是最重要的,但这里也需要强调下:数据来源,数据处理,特征选取,在特定场景下算法优劣的衡量和算法一样重要。 

1.算法

算法满意度:

如何衡量一个算法的好坏,有两个指标:准确率、召回率(也叫查准率和查全率)。准确率和召回率都是越高越好,且是互斥关系,单独说准确率或召回率高是没有意义。

有如下定义:

准确率 P = TP/TP+FP = TP/T’ 识别出的正例中有多少是正例
召回率 R = TP/TP+FN = TP/T 输入的正例中多少被找回了

算法平衡点:

在衡量算法好坏时,常用P-R图表示。将预测结果按预测概率从高到低排序,再按此顺序,将样本作为正例,计算准确率和召回率。以准确率为横轴、召回率为纵轴得到P-R曲线。

而以假正例率为横轴,真正例率为纵轴得到的ROC曲线,面积称为AUC。 
当A曲线完全包含B曲线时,则断定A曲线性能更好,若有交叉,则无法一般性的断定谁更好,只能在给定准确率/召回率时比较。

 

2.数据预处理-归一化

在上述算法中,如果我测试100个苹果,100个非苹果,准确率是1/2;但如果我测试100个苹果,200个非苹果,得到的准确率是100/300=1/3; 测试200个苹果,100个非苹果,得到的准确率是2/3;发生了什么问题?这是因为在统计时,必须两种样本的数量相当,否则计算概率(比值)一定会倾向于数量大的那部分。

即在训练过程也是一样,最好保持训练样本中正负样本的数量相当。

所以,在训练之前,数据预处理的重要一步是归一化。

(注:归一化还包括其他内容,例如让数据的变化范围在给定区域等,这里仅指让正负样本的数量一致。) 
最简单的方式有二种: 

1) 上采样(过采样)
将样本少的一方放大,但不能简单的copy多份,会导致严重过拟合问题。过拟合是指,学习算法把样本学的太好了,很可能把一些训练样本自身的特征当成了该类别的一般特征,导致泛化性能下降。 
代表性算法有SMOTE是通过对正例进行插值得到额外的正例。(可自主了解该算法) 

2) 下采样(欠采样) 
将样本多的一方缩小,但不能随意丢弃,很可能丢失重要信息。代表性算法有EasyEnsemble。

扩展阅读:不均衡学习的抽样方法

 

3.特征提取/特征选择

要点:数据和特征决定了机器学习的上限,而模型和算法只是逼近这个上限而已; 

为什么要进行特征选择?

1.维数灾难。当属性太多时,选择重要的特征,使学习过程仅在一部分特征上构建模型,则维数灾难问题将大为减轻。

2.去除不相关特征会降低学习任务的难度。属性并不是越多越好,复杂的,没有意义的属性会增加学习的成本。就好像侦破案件时,只保留关键因素,真相越容易看清。 

如何从初识特征集中选取子集,并评价该子集的好坏。一般的,由贪心算法的思路,分为前向搜索、后向搜索、或二者结合的方式。

前向搜索是指,在初始集合中先选取一个属性作为特征子集,在接下来的每一轮中,都选择一个最有意义的属性加入特征子集,直到特征子集最有意义。

后向搜索是指,将初始集合作为特征子集,在接下来的每一轮中,都剔除一个最无意义的属性,直到保留下来的特征子集最有意义。 
上述表达中的“最有意义”依赖如何评价子集的好坏,一般可通过计算特征子集的信息增益判断。 
常见的特征选择方法有:过滤式、包裹式、嵌入式。 

4.算法的划分方式

机器学习算法有很多,有分类、回归、聚类、推荐、图像识别领域等等。在机器学习算法中,没有最好的算法,只有“更适合”解决当前任务的算法。

按照学习方式的不同,一般划分为四类:

监督学习

输入数据叫训练集,训练集中需要预测的字段是有已知答案的(比如是不是垃圾邮件,或者某一时间点的股价)。

一个预测模型通过训练过程来准备,训练过程中如果预测是错误的能够得到纠正。训练过程会一直持续,直到算法模型达到一定的预测准确度。

典型的问题是分类回归

典型的算法有对数几率回归和反向传播神经网络。

 

非监督学习

输入数据中需要预测的字段没有已知答案。

预测模型通过输入数据中的推导结构来准备。这样可能抽象出通用规则。它通过一个过程来系统地减少冗余,也有可能是通过相似性来组织数据。

典型的问题是聚合,降维,和相关性学习。

典型的算法是Apriori算法和k-Means算法。

总结:当使用数据构建商业决策模型,你通常会使用监督型和非监督型的学习算法。

 

半监督学习

输入数据中有的有预测结果,有的没有。

存在需要预测的问题,但是模型需要学习结构来组织数据并作出预测。大多数的实际应用都是半监督学习,因为现在的数据太多了,不太可能所有的数据都没有标签,同时,将所有的数据都带上标签又太费时间,所以半监督学习是个很好的折中。

典型问题是分类回归

典型算法是一些对其他灵活算法的扩展,这些灵活的算法对如何为数据建模作出了假设。

目前一个热点问题就是在类似图像识别这样的领域中使用半监督学习,这些问题中一般都拥有很大的数据集,但是很少的数据已经有了预测结果。

强化学习

输入数据作为对模型的反馈,不像监督模型那样,输入数据仅仅是作为一个检查模型对错的方式,在强化学习下,输入数据直接反馈到模型,模型必须对此立刻作出调整。

典型问题是常见的应用场景包括动态系统以及机器人控制等,AlphaGo则是强化学习最有名的实例。

典型算法-马可夫决策就是强化学习的一种,还包括Q-Learning、时间差学习(Temporal difference learning)。 

常用top10算法:

线性回归(Linear Regression)
逻辑回归(Logistic Regression)
决策树(Decision Tree)
支持向量机(Support Vector Machine, “SVM”)
朴素贝叶斯分类(Naive Bayes)
K最近邻(K-Nearest Neighbors, “KNN”)
K均值(K-Means)
随机森林(Random Forest)
降维(Dimensionality Reduction Algorithms)
梯度增强和自适应增强(Gradient Boost & Adaboost)


算法思想:

现有的机器学习算法只有几种思想,基于每种算法思想会衍生出一系列同类型的算法,使机器学习算法家族庞大而复杂。

例如以神经网络为思想衍生的一系列算法,BP网络是指BP算法训练的多层前馈神经网络,RBF网络是一种单隐层前馈网络,以及复杂模型为代表的深度学习。同时,各思想之间有借鉴及交融,形成新的算法。

例如,集成学习的主要思想是通过结合多个学习器来完成学习任务,其两大类别的代表算法有Boosting和随机森林。而随机森林的基础思想是决策树,所以可以说随机森林是一种集成学习算法,也可以说随机森林是一种决策树算法。