❶ 使用Node.js如何实现K最近邻分类算法
源于数据挖掘的一个作业， 这里用Node.js技术来实现一下这个机器学习中最简单的算法之一k-nearest-neighbor算法(k最近邻分类法)。
k-nearest-neighbor-classifier
还是先严谨的介绍下。急切学习法（eager learner）是在接受待分类的新元组之前就构造了分类模型，学习后的模型已经就绪，急着对未知的元组进行分类，所以称为急切学习法，诸如决策树归纳，贝叶斯分类等都是急切学习法的例子。惰性学习法（lazy learner）正好与其相反，直到给定一个待接受分类的新元组之后，才开始根据训练元组构建分类模型，在此之前只是存储着训练元组，所以称为惰性学习法，惰性学习法在分类进行时做更多的工作。
本文的knn算法就是一种惰性学习法，它被广泛应用于模式识别。knn基于类比学习，将未知的新元组与训练元组进行对比，搜索模式空间，找出最接近未知元组的k个训练元组，这里的k即是knn中的k。这k个训练元祖就是待预测元组的k个最近邻。
balabala了这么多，是不是某些同学想大喊一声..speak Chinese! 还是来通俗的解释下，然后再来看上面的理论应该会明白很多。小时候妈妈会指着各种各样的东西教我们，这是小鸭子，这个红的是苹果等等，那我们哼哧哼哧的看着应答着，多次被教后再看到的时候我们自己就能认出来这些事物了。主要是因为我们在脑海像给这个苹果贴了很多标签一样，不只是颜色这一个标签，可能还有苹果的形状大小等等。这些标签让我们看到苹果的时候不会误认为是橘子。其实这些标签就对应于机器学习中的特征这一重要概念，而训练我们识别的过程就对应于泛化这一概念。一台iphone戴了一个壳或者屏幕上有一道划痕，我们还是能认得出来它，这对于我们人来说非常简单，但蠢计算机就不知道怎么做了，需要我们好好调教它，当然也不能过度调教2333，过度调教它要把其他手机也认成iphone那就不好了，其实这就叫过度泛化。
所以特征就是提取对象的信息，泛化就是学习到隐含在这些特征背后的规律，并对新的输入给出合理的判断。
我们可以看上图，绿色的圆代表未知样本，我们选取距离其最近的k个几何图形，这k个几何图形就是未知类型样本的邻居，如果k=3，我们可以看到有两个红色的三角形，有一个蓝色的三正方形，由于红色三角形所占比例高，所以我们可以判断未知样本类型为红色三角形。扩展到一般情况时，这里的距离就是我们根据样本的特征所计算出来的数值，再找出距离未知类型样本最近的K个样本，即可预测样本类型。那么求距离其实不同情况适合不同的方法，我们这里采用欧式距离。
综上所述knn分类的关键点就是k的选取和距离的计算。
2. 实现
我的数据是一个xls文件，那么我去npm搜了一下选了一个叫node-xlrd的包直接拿来用。
// node.js用来读取xls文件的包
var xls = require('node-xlrd');
然后直接看文档实例即可，把数据解析后插入到自己的数据结构里。
var data = [];// 将文件中的数据映射到样本的属性var map = ['a','b','c','d','e','f','g','h','i','j','k'];// 读取文件
xls.open('data.xls', function(err,bk){
if(err) {console.log(err.name, err.message); return;}
var shtCount = bk.sheet.count;
for(var sIdx = 0; sIdx < shtCount; sIdx++ ){
var sht = bk.sheets[sIdx],
rCount = sht.row.count,
cCount = sht.column.count;
for(var rIdx = 0; rIdx < rCount; rIdx++){
var item = {};
for(var cIdx = 0; cIdx < cCount; cIdx++){
item[map[cIdx]] = sht.cell(rIdx,cIdx);
}
data.push(item);
}
}
// 等文件读取完毕后 执行测试
run();
});
然后定义一个构造函数Sample表示一个样本，这里是把刚生成的数据结构里的对象传入，生成一个新的样本。
// Sample表示一个样本
var Sample = function (object) {
// 把传过来的对象上的属性克隆到新创建的样本上
for (var key in object)
{
// 检验属性是否属于对象自身
if (object.hasOwnProperty(key)) {
this[key] = object[key];
}
}
}
再定义一个样本集的构造函数
// SampleSet管理所有样本 参数k表示KNN中的kvar SampleSet = function(k) {
this.samples = [];
this.k = k;
};
// 将样本加入样本数组
SampleSet.prototype.add = function(sample) {
this.samples.push(sample);
}
然后我们会在样本的原型上定义很多方法，这样每个样本都可以用这些方法。
// 计算样本间距离 采用欧式距离
Sample.prototype.measureDistances = function(a, b, c, d, e, f, g, h, i, j, k) {
for (var i in this.neighbors)
{
var neighbor = this.neighbors[i];
var a = neighbor.a - this.a;
var b = neighbor.b - this.b;
var c = neighbor.c - this.c;
var d = neighbor.d - this.d;
var e = neighbor.e - this.e;
var f = neighbor.f - this.f;
var g = neighbor.g - this.g;
var h = neighbor.h - this.h;
var i = neighbor.i - this.i;
var j = neighbor.j - this.j;
var k = neighbor.k - this.k;
// 计算欧式距离
neighbor.distance = Math.sqrt(a*a + b*b + c*c + d*d + e*e + f*f + g*g + h*h + i*i + j*j + k*k);
}
};
// 将邻居样本根据与预测样本间距离排序
Sample.prototype.sortByDistance = function() {
this.neighbors.sort(function (a, b) {
return a.distance - b.distance;
});
};
// 判断被预测样本类别
Sample.prototype.guessType = function(k) {
// 有两种类别 1和-1
var types = { '1': 0, '-1': 0 };
// 根据k值截取邻居里面前k个
for (var i in this.neighbors.slice(0, k))
{
var neighbor = this.neighbors[i];
types[neighbor.trueType] += 1;
}
// 判断邻居里哪个样本类型多
if(types['1']>types['-1']){
this.type = '1';
} else {
this.type = '-1';
}
}
注意到我这里的数据有a-k共11个属性，样本有1和-1两种类型，使用truetype和type来预测样本类型和对比判断是否分类成功。
最后是样本集的原型上定义一个方法，该方法可以在整个样本集里寻找未知类型的样本，并生成他们的邻居集，调用未知样本原型上的方法来计算邻居到它的距离，把所有邻居按距离排序，最后猜测类型。
// 构建总样本数组，包含未知类型样本
SampleSet.prototype.determineUnknown = function() {
for (var i in this.samples)
{
// 如果发现没有类型的样本
if ( ! this.samples[i].type)
{
// 初始化未知样本的邻居
this.samples[i].neighbors = [];
// 生成邻居集
for (var j in this.samples)
{
// 如果碰到未知样本 跳过
if ( ! this.samples[j].type)
continue;
this.samples[i].neighbors.push( new Sample(this.samples[j]) );
}
// 计算所有邻居与预测样本的距离
this.samples[i].measureDistances(this.a, this.b, this.c, this.d, this.e, this.f, this.g, this.h, this.k);
// 把所有邻居按距离排序
this.samples[i].sortByDistance();
// 猜测预测样本类型
this.samples[i].guessType(this.k);
}
}
};
最后分别计算10倍交叉验证和留一法交叉验证的精度。
留一法就是每次只留下一个样本做测试集，其它样本做训练集。
K倍交叉验证将所有样本分成K份，一般均分。取一份作为测试样本，剩余K-1份作为训练样本。这个过程重复K次，最后的平均测试结果可以衡量模型的性能。
k倍验证时定义了个方法先把数组打乱随机摆放。
// helper函数 将数组里的元素随机摆放
function ruffle(array) {
array.sort(function (a, b) {
return Math.random() - 0.5;
})
}
剩余测试代码好写，这里就不贴了。
测试结果为
用余弦距离等计算方式可能精度会更高。
3. 总结
knn算法非常简单，但却能在很多关键的地方发挥作用并且效果非常好。缺点就是进行分类时要扫描所有训练样本得到距离，训练集大的话会很慢。
可以用这个最简单的分类算法来入高大上的ML的门，会有点小小的成就感。
❷ 如何通过图像的灰度值矩阵判断物体真假matlab
如何通过图像的灰度值矩阵判断物体真假matlab，彩色图像：每个像兆亩素帆猜没由R、G、B三个分量表示，每个通道取值范围0~255。（通一个彩色图像是由三页组成的，分别是R、G、B，每一页都是一个二维矩阵）
灰度图像：每个像素只有一个采样颜色的图像，这类图像通常显态纳示为从最暗黑色到最亮的白色的灰度。灰度值分布在0~255之间。
二值图像（黑白图像）：每个像素点只有两种可能，0和1.0代表黑色，1代表白色。数据类型通常为1个二进制位。
❸ 维度规约（特征的提取和组合）
介绍
第一部分 参数方法——类密度模型参数估计
第二部分 监督学习——分类（基于似然的方法）
第三部分 监督学习——袜段雹分类（基于判别式的方法）（参数方法——判别式参数估计）
第四部分 监督学习——回归
第五部分 监督学习——关联规则
第六部分 维度规约（特征的提取和组合）
第七部分 半参数方法
第八部分 非监督学习——聚类
第九部分 非参数方法——密度估计
第十部分 非参数方法——决策树实现的判别式
第十一部分 多层感知器——非参数估计器
第十二部分 局部模型
第十三部分 支持向量机与核机器
第十四部分 隐马尔科夫模型
第十五部分 参数的贝叶斯估计
第十六部分 集成学习——组合多学告帆习器
第十七部分 增强学习
第十八部分 机器学习实验
第十九部分 特征工程与数据预处理
任何分类和回归方法的复杂度都依赖于输入的数量。我们需要输入数据含有可供决策的信息。理想情况下，不需要将特征选择或特征提取作为一个单独的过程。并且有效的方法，应该能够利用任何必要的特征，并丢弃不相关的特征。
但将降维作为一个单独的预处理步骤，有如下一些原因：
1、在大多数机器学习算法中，复杂度依赖于输入的维度d及样本规模N。为了减少存储及计算时间，需要考虑降低维度。同时降低d也降低了检验算法的复杂度。
2、去除不必要的采集数据，
3、更简单的模型可以在小数据集上更鲁棒。（《 监督学习——分类（基于判别式的方法）（参数方法——判别式参数估计） 》多元情况部分中，提到过高维输入x可能存在奇异的协方差矩阵估计）
4、当数据可以用较少的特征解释时，有利于理解数据背后的过程，并提取知识，利于解释。
降低维度主要有两类方法：特征选择、特征提取。
特征选择 ——从d个维中找到 提供最多信息的k个维度，丢弃其他（d-k）个维度的数据。
特征提取 ——找到k个维度的新集合，这k个维度是原来d个维度的组合。这些方法可以是监督的或者非监督的。如同为 线性投影方法 的 主成分分析（PCA） 和 线性判别分析（LDA） 分别是非监督的和监督的。线性维度归约以外，还有非线性维度归约方法，如 等距特征映射（Isomap） 、 局部线性嵌入（LLE） 、 拉普拉斯特征映射 。
1、主成分计算
在投影方法中，我们要找到的是从原d维输入空间到新的 维空间的、具有最小信息损失的映射。
x在方向omega 上的投影为 。
PCA是一种非监督方法，其最大化的准则是方差，主成分是这样的 ，样本投影在 上后最分散。同时为了保证解唯一，要求 。
如果 且 ，则 。寻找 使得 在约束 下最大化。写成拉格朗日问题，有：
关于 求导并令它等于0，有 ，也就是 。 是 的特征向量， 是对应的特征值。因为我们想最大化方差 ，特征值就等于方差，所以选择最大化特征值的特征向量。
因此，主成分是输入样本协方差矩阵的具有最大特征值的特征向量。
第二个主成分 也应该最大化方差 ，具有单位长度，并且与 正交（也就是与 不相关）。则对第二个主成分有：
关于 求导并令它等于0，有 。左乘 ，得 。
其中 。
于是得 ， 。表明 是 得具有第二大特征值的特征向量。类似地，其他维可由递减特征值的特征向量给出。并且，因为 是对称的，所以对于任意两个不同的特征值，对应的特征向量是正交的。
最后有降维后的数据 ，其中W的k列是Sigma 的估计S的k个主特征向量。 投影前从 x 中减燃弯去样本均值 m ，将数据原点中心化 。
等同地，我们想找到一个矩阵W，使得 (不失一般性，x已经中心化)， ，其中D是对角矩阵，既我们希望得到不相关的z_i。令S是D的估计， 矩阵C的第 i 列是S的规范化特征向量 ，则 。且有
其中D是对角矩阵，对角元素是特征值lambda_i。这称为S的谱分解。C是正交的，有 。所以可以令 ， 是对角矩阵。
2、 选取主成分
得到了各主成分 ，根据特征值大小，可统计方差比例 ，取贡献了一定比例以上的前k个主成分。或可通过忽略小于平均输入方差的特征值对应的特征向量，来得到k个主成分。
PCA解释方差，但对离群点很敏感。少量离群点会明显影响方差，从而对特征向量产生很大影响。一般会通过计算数据点的马氏距离，丢弃孤立的离群点，保证估计的鲁棒性。
因子分析（FA）同PCA一样时非监督的。假设存在不可观测的潜在因子集合 ，它们组合成样本实例 。与PCA方法相反，FA的目的时通过较少的因子 z 刻画观测变量 x 之间的依赖性。也就是相较于PCA的 ，FA试图找到 z 使得其构成 x ： 。
在PCA中，挑选大特征值的特征向量构成W，损失了没有被选中的特征值对应的方差。但FA虽也在一个更小的维空间重构数据，但没有丢失信息。
X是 的样本数据矩阵，协方差矩阵是 的。如果X已中心化，具有零均值，则协方差矩阵等于 。PCA使用 的特征向量，谱分解是 ，C的各列是 的特征向量，D是对应特征值构成的 对角矩阵。
如果我们想将维度归约到 ，在PCA中，假定W中的特征向量按特征值大小排序，取W的前k列（ 具有最大特征值的k个特征向量），我们记这些特征向量为 ，对应特征值为 。从原始输入空间映射到新的k维空间：
对任意 ，有
因此， 是 的具有特征值 的特征向量。注意， 是 的，而 是 的。
其谱分解为 ，其中 是 的， 的列是 的特征向量 （单位化后的）， 是对应特征值构成的对角矩阵。 的N维特征向量是新的特征嵌入（FE）空间的坐标。
求得了 ，可直接得到 （PCA所做的）：
通常 ，这是使用PCA来计算 更简单。而有时 ，则计算 容易一些。
对于PCA，得到的是投影向量，可通过取x与特征向量的点积，将任意一个x投影到新的k维空间。但线性嵌入没有学习得到投影映射的模型，每当有一个新的数据加入，都需要重新进行计算。
假设N个点，知道每对点间距离 （不需知道这些点的坐标，维度，也不必知道如何计算这些距离）。多维定位（MDS）是把这些点映射到低维空间的方法，使它们在低维空间重得欧式距离 尽可能接近原始空间中的给定距离 。
可以使用MDS进行维度归约，通过d维 x 空间的逐对欧氏距离，将距离作为MDS的输入。如有样本 ，其中 ，在运用MDS方法时，不需知道 x 的具体坐标。对每两个点 r 和 s。它们之间的平方欧氏距离为
，其中 。
将数据中心化并假定 。由此有 。
并记 ，得到
由上述各等式可得：
故通过已知的 ，计算得到了 ，也就是得到了 。也就是线性嵌入的结果。通过B的特征向量得到各实例在新空间中的坐标。
PCA、FA与MDS做了同样的事情，当d<N时，PCA代价更低。在相关性矩阵上而不是协方差矩阵上做PCA等价于用标准欧氏距离来做MDS，其中每个变量都有单位方差。而MDS
上面介绍的MDS用线性映射的方法，将原空间上的数据，线性地映射到新空间：
MDS中也可以使用非线性的映射，这被称为Sammon映射。映射中的标准化误差称为Sammon应力：
可对g使用任何回归方法，训练 最小化训练数据 X 上的Sammon应力。
对于分类的情况，可在距离的定义中包含类信息，如 ，其中 是r和s所属类之间的距离。应该主观地提供这个类间距离， 用交叉验证优化。
线性判别分析（LDA）是一种用于分类问题的维度归约的 监督 方法。
两类问题 ，考虑两个类 ， 的样本，希望找到由向量 定义的方向，使得当数据投影到 上时，来自两个类的样本尽可能分开。
是 到 上的投影。 和 是 类样本在投影前和投影后的均值。注意这里 ，而 。设样本 ，对 有 ， 有 。
， 。
来自两个类的样本投影后在均值周围的散布是
， 。
投影后，为了使各类尽可能地分开，则希望均值金尽可能远离，并且类实例散布在尽可能小的范围里。既， 大， 小。费希尔线性判别式是这样的 ，最大化 。其中
其中 是类间散度矩阵， 是类内散布的和。从而
，关于 求 的导数，并令其为0，得
其中 是常数，有 ，c是常数。这里关注的是 的方向，故c取1。
对于 K>2 个类，我们希望找到矩阵W，使得 ，其中z是k维的，矩阵W是 矩阵。 的类内散布矩阵是
，其中对 有 ，否则为0。
总的类内散布矩阵是 。
类间散布矩阵是 ，其中 。
投影后类间散布矩阵为 ，类内散布矩阵是 ，都是 矩阵。
同样地，我们希望类间散布更大，类内散布更小，故最大化 ，其解为 的最大的特征向量。注意， 是K个秩为1的矩阵 的和，并且可知它们之中最多只有K-1个是独立，因此S_B的秩最大只有K-1。同2类一样，数据在 上的投影自然是降维的。
为了使用LDA，需要类内散布矩阵 可逆。如果不可逆，可先用PCA消除奇异性，在运用LDA。同时，应该确保PCA 没有把维度降得太低，使得LDA没有多少事可做。
相比于PCA只注重总体的方差，LDA的监督性注重类间散布 。
前面所介绍的方法，都需要数据落在一个线性子空间中。但这一前提并不总是成立。等距特征映射（Isomap）与下面的局部线性嵌入和拉普拉斯特征映射，不同于上面的方法，考虑的是 流形（mainfold） 上的输入数据，且为 非监督方法 。关注的局部数据的逐对距离，而不是全局相似性。
Isomap使用所有数据点对之间的测地距离（沿流形的距离）。对输入空间中靠近的邻近点，可以使用欧氏距离。对距离远的点，用沿流形的各点之间的距离和来近似。
视两个点 r 和 s 是连接的，如果 或 s 是 r 的n个最近邻之一，则其rs边长是 。对任意两个节点 r 和s， 是它们之间最短路径的长度。然后在 可上应用MDS。
与使用MDS一样，由于使用了线性嵌入来将N个数据放到一个低维空间，所以没有学习一个从原空间到低维空间的映射函数。
局部线性嵌入（LLE）从局部线性拟合来发现全局非线性结构。其基本思想是，流形的每个局部可以线性地近似。每个点可通过其邻近点的线性加权和给出。
原数据 和它的近邻 可使用最小二乘法找到重构权重 。其最小化误差 ，
且满足 。
LLE试图用重构权重 反应数据的固有几何性质，期望这种性质在映射后的新空间中也能保持。因此，LLE方法下一步保持 固定，来取新坐标 z 的值。
与Isomap一样，LLE的解是N个点的新坐标，不学习映射。对此有两种解决方案：
1、使用相同的思想，对新元素 ，在原始 d 维空间中找出 的n个近邻（原数据集中的实例，已映射到新空间），并且首先学习最小化 的重构权重 。然后使用它们在新的k维空间中重构 。
2、使用映射后的结果 作为训练集，可训练任意回归器 。例如多层感知器，作为从 到 映射的近似。
Isomap和LLE中，全局非线性组织 通过整合部分重叠的局部线性约束而得到。
考虑数据实例 和它们的投影 。假定实例点对之间相似度为 ， 可在原始空间中计算。r和s相等时 取最大值，并且它是对称的 。
这里的目标函数是 ，意义在于 相似的实例应该放在新空间中的邻近位置，而不相似的实例在新空间中的位置相对不关心。
计算 ，MDS方法中使用点积 。但在拉普拉斯特征映射中，同Isomap和LLE一样，只关注局部相似性。通过r 和s 之间的某个最大 距离，或者通过k最近邻来定义邻域，邻域之外，设置 。邻域之内，对于用户指定的某个 值，使用高斯核把欧氏距离转换为相似度：
定义了 后，最小化目标函数
简写为 ，其中D是 的 对角矩阵，B是 构成的 矩阵。
定义 图拉普拉斯（graph Laplacian） 。目标最小化 。约束 。与特征嵌入一样，得到新空间中的坐标 z。其解是L的特征向量，又因为我们要最小化 ，所以选则最小特征值的特征向量作为解（注意忽略0特征值）。
拉普拉斯特征映射是一种特征嵌入方法。也就是直接在新空间中得到坐标，而没有可用于新实例的映射模型。
拉普拉斯特征映射使用特征嵌入的思想，并保持逐对相似性。相同的思想也用于核机器，核机器中逐对相似性由核函数给出。
核机器的运用，将非线性空间的问题变为新的线性空间上的问题。具体对核方法的介绍见《 支持向量机与核机器 》一节。
对于维度规约方法，也可以运用核方法。对于处理线性子空间的方法，不能直接运用在流形问题上。核版本的方法可以解决这个问题，核机器内在地将原问题映射到新的线性子空间中，再在线空间上采用线性方法。核PCA使用核矩阵的特征向量核特征值，这对应于在基函数映射后的 的空间上做线性维度规约。而在MDS中，核值则作为相似度值。`
❹ 为什么k临近算法不能处理特征很多的数据集
机器学习中常常要用到分类算法，在诸多的分类算法中有一种算法名为k-近邻算法，也称为kNN算法。
一、kNN算法的工作原理
二、适用情况
三、算法实例及讲解
---1.收集数据
---2.准备数据
---3.设计算法分析数据
---4.测试算法
一、kNN算法的工作原理
官方解释：存在一个样本数据集，也称作训练样本集，并且样本中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系，输入没有标签的新数据后，将新数据的每个特征与样本集中的数据对应的特征进行比较，然后算法提取样本集中特征最相似的数据（最近邻）的分类标签。一般来说，我们只选择样本集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数，最后，选择k个最相似的数据中出现次数最多的分类，作为新数据的分类。
我的理解：k-近邻算法就是根据“新数据的分类取决于它的邻居”进行的，比如邻居中大多数都是退伍军人，那么这个人也极有可能是退伍军人。而算法的目的就是先找出它的邻居，然后分析这几位邻居大多数的分类，极有可能就是它本省的分类。
二、适用情况
优点：精度高，对异常数据不敏感（你的类别是由邻居中的大多数决定的，一个异常邻居并不能影响太大），无数据输入假定；
缺点：计算发杂度高（需要计算新的数据点与样本集中每个数据的“距离”，以判断是否是前k个邻居），空间复杂度高（巨大的矩阵）；
适用数据范围：数值型（目标变量可以从无限的数值集合中取值）和标称型（目标变量只有在有限目标集中取值）。
❺ 如何计算sift每幅图像提取多少特征点
一、特征点（角点）匹配
图像匹配能够应用的场合非常多，如目标跟踪，检测，识别，图像拼接等，而角点匹配最核心的技术就要属角点匹配了，所谓角点匹配是指寻找两幅图像之间的特征像素点的对应关系，从而确定两幅图像的位置关系。
角点匹配可以分为以下四个步骤：
1、提取检测子：在两张待匹配的图像中寻找那些最容易识别的像素点（角点），比如纹理丰富的物体边缘点等。
2、提取描述子：对于检测出的角点，用一些数学上的特征对其进行描述，如梯度直方图，局部随机二值特征等。检测子和描述子的常用提取方法有：sift，harris，surf，fast，agast，brisk，freak，brisk，brief/orb等。
3、匹配：通过各个角点的描述子来判断它们在两张图像中的对应关系，常用方法如 flann等。
4、消噪：去除错误匹配的外点，保留正确的匹配点。常用方法有KDTREE，BBF，Ransac，GTM等。
二、SIFT匹配方法的提出
为了排除因为图像遮挡和背景混乱而产生的无匹配关系的关键点，SIFT的作者Lowe提出了比较最近邻距离与次近邻距离的SIFT匹配方式：取一幅图像中的一个SIFT关键点，并找出其与另一幅图像中欧式距离最近的前两个关键点，在这两个关键点中，如果最近的距离除以次近的距离得到的比率ratio少于某个阈值T，则接受这一对匹配点。因为对于错误匹配，由于特征空间的高维性，相似的距离可能有大量其他的错误匹配，从而它的ratio值比较高。显然降低这个比例阈值T，SIFT匹配点数目会减少，但更加稳定，反之亦然。
Lowe推荐ratio的阈值为0.8，但作者对大量任意存在尺度、旋转和亮度变化的两幅图片进行匹配，结果表明ratio取值在0. 4~0. 6 之间最佳，小于0. 4的很少有匹配点，大于0. 6的则存在大量错误匹配点，所以建议ratio的取值原则如下:
ratio=0. 4：对于准确度要求高的匹配；
ratio=0. 6：对于匹配点数目要求比较多的匹配；
ratio=0. 5：一般情况下。
三、常见的SIFT匹配代码
1、vlfeat中sift toolbox中的vl_ubcmatch.c使用的是普通的欧氏距离进行匹配（该SIFT代码贡献自Andrea
Vedaldi）。
2、Lowe的C++代码中使用的是欧氏距离，但是在matlab代码中为了加速计算，使用的是向量夹角来近似欧氏距离：先将128维SIFT特征向量归一化为单位向量（每个数除以平方和的平方根），然后点乘来得到向量夹角的余弦值，最后利用反余弦（acos函数）求取向量夹角。实验证明Lowe的办法正确率和耗时都很不错。
同样，也可以采用knnsearch函数求最近点和次近点：knnsearch采用euclidean距离时得到的结果与lowe采用的近似方法结果几乎一致，正好印证了模拟欧氏距离的效果。
3、Rob Hess的OpenSIFT采用了KDTREE来对匹配进行优化。
4、CSDN大神v_JULY_v实现了KDTREE+BBF对SIFT匹配的优化和消除错误匹配：从K近邻算法、距离度量谈到KD树、SIFT+BBF算法
- 结构之法 算法之道 - 博客频道 - CSDN.NET。
5、OpenCV中features2d实现的SIFT匹配有多种matcher：VectorDescriptorMatcher，BFMatcher（Brute-force descriptor matcher），FernDescriptorMatcher，OneWayDescriptorMatcher，FlannBasedMatcher 等等。目前只知道采用knnsearch，提供了多种距离度量方式，具体区别不懂。
❻ 特征工程中数据预处理方法总结
特征工程
“巧妇难为无米之炊”，在机器学习中，数据和特征便是“米”，而模型和算法则是“巧妇”。没有充足的数据和合适的特征，再强大的模型也无法拟合出满意的结果。因此，对于机器学习的问题，常说的一句话是数据和特征决定了结果的上限，而模型和算法则是在优化过程中逐步接近这个上限。所以，特征的处理在整个机器学习过程中占有举足轻重的地位，对特征的处理过程被称为特征工程。特征工程是对原始数据进行一系列的工程处理，将其提炼为特征，作为输入工算法和模型使用。
特征工程又包含了Data PreProcessing（数据预处理）、Feature Extraction（特征提取）、Feature Selection（特征选择）和Feature construction（特征构造）等子问题，而数据预处理又包括了数据清洗和特征预处理等子问题。本文用作总结数据预处理的一系列方法。
1、无量纲化
（1）什么是无量纲化
为了消除数据特征之间的量纲影响，我们需要对特征进行归一化和标准化处理，使得不同指标之间具有可比性。例如：分析一个人的身高和体重对健康的影响，如果使用米和千克作为单位，那么身高和体重会处于不同的数值范围内，体重的数值在量上要远大于身高，而如果不对其做处理直接用的情况下分析结果显然会更依赖于数值差别较大的体重特征。因此，为了得到更为准确的结果，就需要对特征进行归一化和标准化处理，使各项指标处于同一数量级，以便进行分析。
（2）无量纲化方法
无量纲化通常也被称为归一化或标准化，是因为归一化和标准化是无量纲化的两个主要方法
1）归一化
归一化是对原始数据进行线性变换， 使结果映射到[0, 1]的范围， 实现对原始数据的等比缩放。 最常用对的是Min-Max Scaling归一化方法（也叫极差变换法），公式如下 ：
其中X为原始数据， Xmax、Xmin分别为数据最大值和最小值。最值归一化的使用范围是特征的分布具有明显边界的，受outlier的影响比较大。
除此之外，常用的归一化方法有原始值比最大值。
2）标准化
标准化会将原始数据映射到均值为0、 标准差为1的分布派慎上。常用的方法是零均值标准化（Z-Score Normalization）。 具体来说， 假设原始特征的均值为μ、 标准差为σ， 那么归一化公式定义为 ：
零均值标准化适用于数据中没有明显的边界，有可能存在极端数据值的情况。
3）不同的无量纲方法的适用范围
无量纲化避免了不同量纲的选取对距离计算产生的巨大影响。但是，归一化和标准化适用于不同的场景，在分类、聚类算法中，需要使用距离来度量相似性的时候、或者使用PCA技术进行降维的时候，标准化方法表现更好。在不涉及距离度量、协方差计算、数据不符合正太分布的时候，可以使用归一化方法。比如图像处理中，将RGB图像转换为灰度图像后将其值限定在[0 255]的范围。
（3）无量纲化的作用和适用模型
1）作用
无量纲化的作用除了可以使分析结果不明显倾向于差异化较大的特征外，另一个重要作用是在随机梯度下降算法中，如果对特征进行了无量纲化处理，会在相同的学习率的情况下减少差异较大的特征的迭代次数，更快找到最优解。例如，假设有两种数告丛值型特征，x1x1的取值范围为 [0, 10]，x2x2的取值范围为[0, 3]。则在未归一化和归一化数据的梯度下降过程分别如下图：
由图可以看出，在学习速率相同的情况下，x1相比与x2需要较多的迭代才能找到最优解。但是，如果将 x1 和 x2都映射到到相同的数值区间后， 优化目标的等值图会变成圆形。x1和 x2 的更新速度变得更为一致， 容易更快地通过梯度下降找到最优解。
2）适用算法
机器学习中，并不是所有的模型都需要对特征进行无量纲化处理。比如概率模型并不需要，因为它们不关心变量的值，而是关心变量的分布和变量之间的条件概率。但是，像线性回归、逻辑回归和支持向量机以及神经网络模型等则就需要提前进行特征的无量纲化。从尘友敬另一个角度来看，通过梯度下降法求解的模型通常需要无量纲化。否则，像决策树在求解过程中，主要依据特征值的信息增益比等信息，而这些信息跟特征是否经过归一化等无量纲化处理是无关的，因此决策数不要求对特征进行无量纲化处理。
2、类别型特征编码
类别型特征的值表现为类别变量，类别型变量，也被称为定性变量（categorical variable）。比如性别、省份、学历、产品等级等。这类变量的取值通常是用文字而非数字来表示。在机器学习中，除了决策树族的算法能直接接受类别型特征作为输入，对于支持向量机，逻辑回归等模型来说，必须对其做一定的处理，转换成可靠的数值特征才能正确运行。类别型特征的处理方法有：
（1）序列编码（ordinal encoding）
一般处理类别间具有大小关系的数据，例如期末成绩的 [A, B, C, D] 四挡可以直接转化为 [0, 1, 2, 3]。在转化后，依然保持类别之间的顺序关系。
（2）独热编码（one-hot encoding）
序列编码潜在的定义了类别之间的距离具有相同的含义。以成绩为例，两个人之间，得分A与B的成绩差，和B与C的成绩差，在进行预测时，是完全等价的，由于 [A, B, C, D] 直观上与成绩正相关，使用序列编码不会带来太大的损失。然而在处理像血型这样的类别特征时，如果将 [A, B, AB, O] 直接编码成 [1, 2, 3, 4]，显然A与B和B与AB之间的距离，并不具有相同的含义，甚至是完全抽象的无法理解的意义，此时，序列编码就不适用了。因此，便出现了独热编码，独热编码将类别特征用一组比特位来表示，每一位代表一个可能的类别，如果该变量不能一次称为多个类别，那么该组中只有一位可以是1。
对于类别取值较多的情况下适用独热编码需要注意以下问题：
1）适用稀疏向量来节省空间。在独热编码下，特征向量只有某一维取值为1，其他位置取值均为0。因此，可以利用向量的稀疏表示有效节省空间，并且目前大部分的算法均接受稀疏向量形式的输入。
2）配合特征选择来降低维度。高维度特征会带来几方面的问题，一是在K近邻算法中，高维空间下两点之间的距离很难得到有效的衡量；二是在逻辑回归模型中，参数的数量会随着维度的增加而增高，容易引起过拟合问题；三是通常只有部分维度是对分类、预测有帮助，因此可以考虑配合特征选择来降低维度。
（3）哑变量（mmy encoding）
哑变量是独热编码的一种形式，onehot编码的问题是它允许k个自由度，其中变量本身只需要k-1。虚拟编码通过仅适用表示中的k-1个特征来消除额外的自由度。
3、数值型特征离散化
离散化是数值型特征非常重要的一个处理，其实就是要将数值型数据转化成类别型数据。连续值的取值空间可能是无穷的，为了便于表示和在模型中处理，需要对连续值特征进行离散化处理。
（1）无监督方法
1）自定义离散化，根据业务经验或者常识等自行设定划分的区间，然后将原始数据归类到各个区间中。
2）等距化方法，按照相同宽度将数据分成几等份，其缺点是受到异常值的影响比较大。
3）等频化方法，将数据分成几等份，每等份数据里面的个数是一样的。
4）聚类离散化
5）二值化方法，设定一个阈值，大于阈值的赋值为1，小于等于阈值的赋值为0。
（2）有监督方法
1）卡方法，自底向上的(即基于合并的)数据离散化方法。它依赖于卡方检验：具有最小卡方值的相邻区间合并在一起,直到满足确定的停止准则。其基本思想是，对于精确的离散化，相对类频率在一个区间内应当完全一致。因此,如果两个相邻的区间具有非常类似的类分布，则这两个区间可以合并；否则，它们应当保持分开。而低卡方值表明它们具有相似的类分布。
2）最小熵法，需要使总熵值达到最小，也就是使分箱能够最大限度地区分因变量的各类别。数据集的熵越低，说明数据之间的差异越小，最小熵划分就是为了使每箱中的数据具有最好的相似性。给定箱的个数，如果考虑所有可能的分箱情况，最小熵方法得到的箱应该是具有最小熵的分箱。
4、缺失值处理方法
（1）直接删除
如果在数据集中，只有几条数据的某几列中存在缺失值，那么可以直接把这几条数据删除。
（2）均值插补
数据的属性分为定距型和非定距型。如果缺失值是定距型的，就以该属性存在值的平均值来插补缺失的值；如果缺失值是非定距型的，就根据统计学中的众数原理，用该属性的众数(即出现频率最高的值)来补齐缺失的值。
（3）利用同类均值插补
同均值插补的方法都属于单值插补，不同的是，它用层次聚类模型预测缺失变量的类型，再以该类型的均值插补。
（4）极大似然估计
在缺失类型为随机缺失的条件下，假设模型对于完整的样本是正确的，那么通过观测数据的边际分布可以对未知参数进行极大似然估计（Little and Rubin）。
（5）多重插补
多重插补的思想来源于贝叶斯估计，认为待插补的值是随机的，它的值来自于已观测到的值。具体实践上通常是估计出待插补的值，然后再加上不同的噪声，形成多组可选插补值。根据某种选择依据，选取最合适的插补值。
❼ 大数据算法：分类算法
KNN算法，即K近邻（K Nearest Neighbour）算法，是一种基本的分类算法。其主要原理是：对于一个需要分类的数据，将其和一组已经分类标注好的样本集合进行比较，得到距离最近的K个样本，K个样本最多归属的类别，就是这个需要分类数据的类别。下面我给你画了一个KNN算法的原理图。
图中，红蓝绿三种颜色的点为样本数据，分属三种类别 、 、 。对于待分类点 ，计算和它距离最近的5个点（即K为5），这5个点最多归属的类别为 （4个点归属 ，1个点归属 ），那么 的类别被分类为 。
KNN的算法流程也非常简单，请看下面的流程图。
KNN算法是一种非常简单实用的分类算法，可用于各种分类的场景，比如新闻分类、商品分类等，甚至可用于简单的文字识别。对于新闻分类，可以提前对若干新闻进行人工标注，标好新闻类别，计算好特征向量。对于一篇未分类的新闻，计算其特征向量后，跟所有已标注新闻进行距离计算，然后进一步利用KNN算法进行自动分类。
读到这你肯定会问，如何计算数据的距离呢？如何获得新闻的特征向量呢？
KNN算法的关键是要比较需要分类的数据与样本数据之间的距离，这在机器学习中通常的做法是：提取数据的特征值，根据特征值组成一个n维实数向量空间（这个空间也被称作特征空间），然后计算向量之间的空间距离。空间之间的距离计算方法有很多种，常用的有欧氏距离、余弦距离等。
对于数据 和 ，若其特征空间为n维实数向量空间 ，即 ， ，则其欧氏距离计算公式为
这个欧式距离公式其实我们在初中的时候就学过，平面几何和立体几何里两个点之间的距离，也是用这个公式计算出来的，只是平面几何（二维几何）里的n=2，立体几何（三维几何）里的n=3，而机器学习需要面对的每个数据都可能有n维的维度，即每个数据有n个特征值。但是不管特征值n是多少，两个数据之间的空间距离的计算公式还是这个欧氏计算公式。大多数机器学习算法都需要计算数据之间的距离，因此掌握数据的距离计算公式是掌握机器学习算法的基础。
欧氏距离是最常用的数据计算公式，但是在文本数据以及用户评价数据的机器学习中，更常用的距离计算方法是余弦相似度。
余弦相似度的值越接近1表示其越相似，越接近0表示其差异越大，使用余弦相似度可以消除数据的某些冗余信息，某些情况下更贴近数据的本质。我举个简单的例子，比如两篇文章的特征值都是：“大数据”“机器学习”和“极客时间”，A文章的特征向量为（3, 3, 3），即这三个词出现次数都是3；B文章的特征向量为（6, 6, 6），即这三个词出现次数都是6。如果光看特征向量，这两个向量差别很大，如果用欧氏距离计算确实也很大，但是这两篇文章其实非常相似，只是篇幅不同而已，它们的余弦相似度为1，表示非常相似。
余弦相似度其实是计算向量的夹角，而欧氏距离公式是计算空间距离。余弦相似度更关注数据的相似性，比如两个用户给两件商品的打分分别是（3, 3）和（4, 4），那么两个用户对两件商品的喜好是相似的，这种情况下，余弦相似度比欧氏距离更合理。
我们知道了机器学习的算法需要计算距离，而计算距离需要还知道数据的特征向量，因此提取数据的特征向量是机器学习工程师们的重要工作，有时候甚至是最重要的工作。不同的数据以及不同的应用场景需要提取不同的特征值，我们以比较常见的文本数据为例，看看如何提取文本特征向量。
文本数据的特征值就是提取文本关键词，TF-IDF算法是比较常用且直观的一种文本关键词提取算法。这种算法是由TF和IDF两部分构成。
TF是词频（Term Frequency），表示某个单词在文档中出现的频率，一个单词在一个文档中出现的越频繁，TF值越高。
词频：
IDF是逆文档频率（Inverse Document Frequency），表示这个单词在所有文档中的稀缺程度，越少文档出现这个词，IDF值越高。
逆文档频率：
TF与IDF的乘积就是TF-IDF。
所以如果一个词在某一个文档中频繁出现，但在所有文档中却很少出现，那么这个词很可能就是这个文档的关键词。比如一篇关于原子能的技术文章，“核裂变”“放射性”“半衰期”等词汇会在这篇文档中频繁出现，即TF很高；但是在所有文档中出现的频率却比较低，即IDF也比较高。因此这几个词的TF-IDF值就会很高，就可能是这篇文档的关键词。如果这是一篇关于中国原子能的文章，也许“中国”这个词也会频繁出现，即TF也很高，但是“中国”也在很多文档中出现，那么IDF就会比较低，最后“中国”这个词的TF-IDF就很低，不会成为这个文档的关键词。
提取出关键词以后，就可以利用关键词的词频构造特征向量，比如上面例子关于原子能的文章，“核裂变”“放射性”“半衰期”这三个词是特征值，分别出现次数为12、9、4。那么这篇文章的特征向量就是（12, 9, 4），再利用前面提到的空间距离计算公式计算与其他文档的距离，结合KNN算法就可以实现文档的自动分类。
贝叶斯公式是一种基于条件概率的分类算法，如果我们已经知道A和B的发生概率，并且知道了B发生情况下A发生的概率，可以用贝叶斯公式计算A发生的情况下B发生的概率。事实上，我们可以根据A的情况，即输入数据，判断B的概率，即B的可能性，进而进行分类。
举个例子：假设一所学校里男生占60%，女生占40%。男生总是穿长裤，女生则一半穿长裤一半穿裙子。假设你走在校园中，迎面走来一个穿长裤的学生，你能够推断出这个穿长裤学生是男生的概率是多少吗？
答案是75%，具体算法是：
这个算法就利用了贝叶斯公式，贝叶斯公式的写法是：
意思是A发生的条件下B发生的概率，等于B发生的条件下A发生的概率，乘以B发生的概率，除以A发生的概率。还是上面这个例子，如果我问你迎面走来穿裙子的学生是女生的概率是多少。同样带入贝叶斯公式，可以计算出是女生的概率为100%。其实这个结果我们根据常识也能推断出来，但是很多时候，常识受各种因素的干扰，会出现偏差。比如有人看到一篇博士生给初中学历老板打工的新闻，就感叹读书无用。事实上，只是少见多怪，样本量太少而已。而大量数据的统计规律则能准确反映事物的分类概率。
贝叶斯分类的一个典型的应用场合是垃圾邮件分类，通过对样本邮件的统计，我们知道每个词在邮件中出现的概率 ，我们也知道正常邮件概率 和垃圾邮件的概率 ，还可以统计出垃圾邮件中各个词的出现概率 ，那么现在一封新邮件到来，我们就可以根据邮件中出现的词，计算 ，即得到这些词出现情况下，邮件为垃圾邮件的概率，进而判断邮件是否为垃圾邮件。
现实中，贝叶斯公式等号右边的概率，我们可以通过对大数据的统计获得，当有新的数据到来的时候，我们就可以带入上面的贝叶斯公式计算其概率。而如果我们设定概率超过某个值就认为其会发生，那么我们就对这个数据进行了分类和预测，具体过程如下图所示。
训练样本就是我们的原始数据，有时候原始数据并不包含我们想要计算的维度数据，比如我们想用贝叶斯公式自动分类垃圾邮件，那么首先要对原始邮件进行标注，需要标注哪些邮件是正常邮件、哪些邮件是垃圾邮件。这一类需要对数据进行标注才能进行的机器学习训练也叫作有监督的机器学习。
❽ 07_推荐系统算法详解
基于人口统计学的推荐与用户画像、基于内容的推荐、基于协同过滤的推荐。
1、基于人口统计学的推荐机制( Demographic-based Recommendation)是一种最易于实现的推荐方法，它只是简单的根据系统用户的基本信息发现用户的相关程度，然后将相似用户喜爱的其他物品推荐给当前用户。
2、对于没有明确含义的用户信息(比如登录时间、地域等上下文信息)，可以通过聚类等手段，给用户打上分类标签。
3、对于特定标签的用户，又可以根据预设的规则(知识)或者模型，推荐出对应的物品。
4、用户信息标签化的过程一般又称为 用户画像 ( User Profiling）。
（1）用户画像( User Profile)就是企业通过收集与分析消费者社会属性、生活习惯、消费行为等主要信息的数据之后，完美地抽象出一个用户的商业全貌作是企业应用大数据技术的基本方式。
（2）用户画像为企业提供了足够的信息基础，能够帮助企业快速找到精准用户群体以及用户需求等更为广泛的反馈信息。
（3）作为大数据的根基，它完美地抽象出一个用户的信息全貌，为进一步精准、快速地分析用户行为习惯、消费习惯等重要信息，提供了足够的数据基础。
1、 Content- based Recommendations(CB)根据推荐物品或内容的元数据，发现物品的相关性，再基于用户过去的喜好记录，为用户推荐相似的物品。
2、通过抽取物品内在或者外在的特征值,实现相似度计算。比如一个电影,有导演、演员、用户标签UGC、用户评论、时长、风格等等，都可以算是特征。
3、将用户(user)个人信息的特征(基于喜好记录或是预设兴趣标签)，和物品(item)的特征相匹配，就能得到用户对物品感兴趣的程度。在一些电影、音乐、图书的社交网站有很成功的应用,有些网站还请专业的人员对物品进行基因编码/打标签(PGC）。
4、 相似度计算：
5、对于物品的特征提取——打标签(tag)
- 专家标签(PGC）
- 用户自定义标签(UGC)
- 降维分析数据,提取隐语义标签(LFM)
对于文本信息的特征提取——关键词
- 分词、语义处理和情感分析(NLP)
- 潜在语义分析(LSA）
6、 基于内容推荐系统的高层次结构
7、 特征工程
（1）特征( feature)：数据中抽取出来的对结果预测有用的信息。
特征的个数就是数据的观测维度。
特征工程是使用专业背景知识和技巧处理数据，使得特征能在机器学习算法上发挥更好的作用的过程。
特征工程一般包括特征清洗(采样、清洗异常样本)，特征处理和特征选择。
特征按照不同的数据类型分类，有不同的特征处理方法：数值型、类别型、时间型、统计型。
（2）数值型特征处理
用连续数值表示当前维度特征，通常会对数值型特征进行数学上的处理，主要的做法是归一化和离散化。
* 幅度调整归一化：
特征与特征之间应该是平等的，区别应该体现在 特征内部 。
例如房屋价格和住房面积的幅度是不同的，房屋价格可能在3000000~15000000(万)之间,而住房面积在40-300(平方米)之间，那么明明是平等的两个特征，输入到相同的模型中后由于本身的幅值不同导致产生的效果不同，这是不合理的
* 数值型特征处理——离散化
离散化的两种方式：等步长——简单但不一定有效；等频——min -> 25% -> 75% -> max
两种方法对比：
等频的离散化方法很精准，但需要每次都对数据分布进行一遍从新计算，因为昨天用户在淘宝上买东西的价格分布和今天不一定相同，因此昨天做等频的切分点可能并不适用，而线上最需要避免的就是不固定，需要现场计算，所以昨天训练出的模型今天不一定能使用。
等频不固定，但很精准，等步长是固定的，非常简单，因此两者在工业上都有应用。
（3） 类别型特征处理
类别型数据本身没有大小关系，需要将它们编码为数字，但它们之间不能有预先设定的大小关系，因此既要做到公平，又要区分开它们，那么直接开辟多个空间。
One-Hot编码/哑变量：One-Hot编码/哑变量所做的就是将类别型数据平行地展开，也就是说，经过One-Hot编码哑变量后，这个特征的空间会膨胀。
（4） 时间型特征处理
时间型特征既可以做连续值,又可以看做离散值。
连续值：持续时间(网页浏览时长)；间隔时间(上一次购买/点击离现在的时间间隔)。
离散值：一天中哪个时间段；一周中的星期几；一年中哪个月/星期；工作日/周末。
（5） 统计型特征处理
加减平均：商品价格高于平均价格多少，用户在某个品类下消费超过多少。
分位线：商品属于售出商品价格的分位线处。
次序性：商品处于热门商品第几位。
比例类：电商中商品的好/中/差评比例。
8、 推荐系统常见反馈数据 ：
9、 基于UGC的推荐
用户用标签来描述对物品的看法，所以用户生成标签(UGC)是联系用户和物品的纽带，也是反应用户兴趣的重要数据源。
一个用户标签行为的数据集一般由一个三元组(用户,物品,标签)的集合表示，其中一条记录(u,i,b)表示用户u给物品打上了标签b。
一个最简单的算法：
- 统计每个用户最常用的标签
- 对于每个标签,统计被打过这个标签次数最多的物品
- 对于一个用户，首先找到他常用的标签，然后找到具有这些标签的最热门的物品，推荐给他
- 所以用户u对物品i的兴趣公式为 ，其中 使用户u打过标签b的次数， 是物品i被打过标签b的次数。
简单算法中直接将用户打出标签的次数和物品得到的标签次数相乘，可以简单地表现出用户对物品某个特征的兴趣。
这种方法倾向于给热门标签(谁都会给的标签,如“大片”、“搞笑”等)、热门物品(打标签人数最多)比较大的权重，如果一个热门物品同时对应着热门标签,那它就会“霸榜”，推荐的个性化、新颖度就会降低。
类似的问题,出现在新闻内容的关键字提取中。比如以下新闻中,哪个关键字应该获得更高的权重?
10、 TF-IDF：词频逆文档频率 ( Term Frequency- -Inverse Document Frequency,TF-DF)是一种用于资讯检索与文本挖掘的常用加权技术。
TFDF是一种统计方法，用以评估一个字词对于一个文件集或一个语料库中的其中份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。
TFIDF=TF IDF
TF-IDF的主要思想是 ：如果某个词或短语在一篇文章中出现的频率TF高，并且在其他文章中很少出现，则认为此词或者短语具有很好的类别区分能力，适合用来分类。
TF-DF加权的各种形式常被搜索引擎应用，作为文件与用户查询之间相关程度的度量或评级。
词频( Term Frequency,TF) ：指的是某一个给定的词语在该文件中出现的频率。这个数字是对词数的归一化，以防止偏向更长的文件。(同一个词语在长文件里可能会比短文件有更高的词数,而不管该词语重要与否。） ，其中 表示词语 i 在文档 j 中出现的频率， 表示 i 在 j 中出现的次数， 表示文档 j 的总词数。
逆向文件频率( Inverse Document Frequency,IDF) ：是一个词语普遍重要性的度量，某一特定词语的IDF，可以由总文档数目除以包含该词语之文档的数目，再将得到的商取对数得到 ，其中 表示词语 i 在文档集中的逆文档频率，N表示文档集中的文档总数， 表示文档集中包含了词语 i 的文档数。
（11） TF-IDF对基于UGC推荐的改进 ： ，为了避免热门标签和热门物品获得更多的权重，我们需要对“热门进行惩罚。
借鉴TF-IDF的思想，以一个物品的所有标签作为“文档”，标签作为“词语”，从而计算标签的“词频”(在物品所有标签中的频率)和“逆文档频率”(在其它物品标签中普遍出现的频率）。
由于“物品i的所有标签” 应该对标签权重没有影响，而 “所有标签总数” N 对于所有标签是一定的，所以这两项可以略去。在简单算法的基础上,直接加入对热门标签和热门物品的惩罚项： ，其中， 记录了标签 b 被多少个不同的用户使用过， 记录了物品 i 被多少个不同的用户打过标签。
（一）协同过滤（Collaborative Filtering, CF）
1、基于协同过滤(CF)的推荐：基于内容( Content based,CB)主要利用的是用户评价过的物品的内容特征，而CF方法还可以利用其他用户评分过的物品内容。
CF可以解决CB的一些局限：
- 物品内容不完全或者难以获得时,依然可以通过其他用户的反馈给出推荐。
- CF基于用户之间对物品的评价质量，避免了CB仅依赖内容可能造成的对物品质量判断的干。
- CF推荐不受内容限制，只要其他类似用户给出了对不同物品的兴趣，CF就可以给用户推荐出内容差异很大的物品(但有某种内在联系)
分为两类：基于近邻和基于模型。
2、基于近邻的推荐系统：根据的是相同“口碑”准则。是否应该给Cary推荐《泰坦尼克号》?
（二）基于近邻的协同过滤
1、 基于用户（User-CF）： 基于用户的协同过滤推荐的基本原理是，根据所有用户对物品的偏好，发现与当前用户口味和偏好相似的“邻居”用户群，并推荐近邻所偏好的物品。
在一般的应用中是采用计算“K-近邻”的算法；基于这K个邻居的历史偏好信息，为当前用户进行推荐。
User-CF和基于人口统计学的推荐机制：
- 两者都是计算用户的相似度，并基于相似的“邻居”用户群计算推荐。
- 它们所不同的是如何计算用户的相似度：基于人口统计学的机制只考虑用户本身的特征，而基于用户的协同过滤机制可是在用户的历史偏好的数据上计算用户的相似度，它的基本假设是，喜欢类似物品的用户可能有相同或者相似的口味和偏好。
2、基于物品（Item-CF）：基于项目的协同过滤推荐的基本原理与基于用户的类似，只是使用所有用户对物品的偏好，发现物品和物品之间的相似度，然后根据用户的历史偏好信息，将类似的物品推荐给用户。
Item-CF和基于内容(CB)的推荐
- 其实都是基于物品相似度预测推荐，只是相似度计算的方法不一样，前者是从用户历史的偏好推断，而后者是基于物品本身的属性特征信息。
同样是协同过滤，在基于用户和基于项目两个策略中应该如何选择呢?
- 电商、电影、音乐网站,用户数量远大于物品数量。
- 新闻网站，物品(新闻文本)数量可能大于用户数量。
3、 User-CF和Item-CF的比较
同样是协同过滤，在User-CF和ltem-CF两个策略中应该如何选择呢？
Item-CF应用场景
- 基于物品的协同过滤( Item-CF ) 推荐机制是 Amazon在基于用户的机制上改良的一种策略因为在大部分的Web站点中，物品的个数是远远小于用户的数量的，而且物品的个数和相似度相对比较稳定，同时基于物品的机制比基于用户的实时性更好一些，所以 Item-CF 成为了目前推荐策略的主流。
User-CF应用场景
- 设想一下在一些新闻推荐系统中，也许物品一一也就是新闻的个数可能大于用户的个数，而且新闻的更新程度也有很快，所以它的相似度依然不稳定，这时用 User-cf可能效果更好。
所以，推荐策略的选择其实和具体的应用场景有很大的关系。
4、 基于协同过滤的推荐优缺点
（1）基于协同过滤的推荐机制的优点：
它不需要对物品或者用户进行严格的建模，而且不要求对物品特征的描述是机器可理解的，所以这种方法也是领域无关的。
这种方法计算出来的推荐是开放的，可以共用他人的经验，很好的支持用户发现潜在的兴趣偏好。
（2）存在的问题
方法的核心是基于历史数据，所以对新物品和新用户都有“冷启动”的问题。
推荐的效果依赖于用户历史好数据的多少和准确性。
在大部分的实现中，用户历史偏好是用稀疏矩阵进行存储的，而稀疏矩阵上的计算有些明显的问题，包括可能少部分人的错误偏好会对推荐的准确度有很大的影响等等。
对于一些特殊品味的用户不能给予很好的推荐。
（三）基于模型的协同过滤
1、基本思想
（1）用户具有一定的特征，决定着他的偏好选择
（2）物品具有一定的特征，影响着用户需是否选择它。
（3）用户之所以选择某一个商品，是因为用户特征与物品特征相互匹配。
基于这种思想，模型的建立相当于从行为数据中提取特征，给用户和物品同时打上“标签”；这和基于人口统计学的用户标签、基于内容方法的物品标签本质是一样的，都是特征的提取和匹配。
有显性特征时(比如用户标签、物品分类标签)我们可以直接匹配做出推荐；没有时，可以根据已有的偏好数据，去发据出隐藏的特征,这需要用到隐语义模型(LFM)。
2、基于模型的协同过滤推荐，就是基于样本的用户偏好信息，训练一个推荐模型,然后根据实时的用户喜好的信息进行预测新物品的得分，计算推荐
基于近邻的推荐和基于模型的推荐
- 基于近邻的推荐是在预测时直接使用已有的用户偏好数据，通过近邻数据来预测对新物品的偏好(类似分类)
- 而基于模型的方法，是要使用这些偏好数据来训练模型，找到内在规律，再用模型来做预测(类似回归)
训练模型时，可以基于标签内容来提取物品特征，也可以让模型去发据物品的潜在特征；这样的模型被称为 隐语义模型 ( Latent Factor Model,LFM)。
（1）隐语义模型(LFM)：用隐语义模型来进行协同过滤的目标：
- 揭示隐藏的特征,这些特征能够解释为什么给出对应的预测评分
- 这类特征可能是无法直接用语言解释描述的,事实上我们并不需要知道,类似“玄学”
通过矩阵分解进行降维分析
- 协同过滤算法非常依赖历史数据，而一般的推荐系统中，偏好数据又往往是稀疏的；这就需要对原始数据做降维处理。
- 分解之后的矩阵，就代表了用户和物品的隐藏特征
隐语义模型的实例：基于概率的隐语义分析(pLSA)、隐式迪利克雷分布模型(LDA)、矩阵因子分解模型(基于奇异值分解的模型,SVD)
（2）LFM降维方法——矩阵因子分解
（3）LFM的进一步理解
我们可以认为，用户之所以给电影打出这样的分数，是有内在原因的，我们可以挖掘出影响用户打分的隐藏因素，进而根据未评分电影与这些隐藏因素的关联度，决定此未评分电影的预测评分。
应该有一些隐藏的因素，影响用户的打分，比如电影：演员、题材、年代…甚至不定是人直接可以理解的隐藏因子。
找到隐藏因子，可以对user和Iiem进行关联(找到是由于什么使得user喜欢/不喜欢此Item,什么会决定user喜欢/不喜欢此item)，就可以推测用户是否会喜欢某一部未看过的电影。
（4）矩阵因子分解
（5）模型的求解——损失函数
（6）模型的求解算法——ALS
现在，矩阵因子分解的问题已经转化成了一个标准的优化问题，需要求解P、Q，使目标损失函数取最小值。
最小化过程的求解，一般采用随机梯度下降算法或者交替最小二乘法来实现交替最小二乘法( Alternating Least Squares,ALS)
ALS的思想是，由于两个矩阵P和Q都未知,且通过矩阵乘法耦合在一起，为了使它们解耦，可以先固定Q，把P当作变量，通过损失函数最小化求出P，这就是一个经典的最小二乘问题；再反过来固定求得的P，把Q当作变量，求解出Q：如此交替执行，直到误差满足阅值条件，或者到达迭代上限。
（7）梯度下降算法
❾ 哪种机器学习算法可以进行一维数据的扩充
您好，一维数据扩充可以使用多种机器学习算法，比如最常用的K近邻算法(KNN)、支持向量机(SVM)、决策树(DT)、贝叶斯算法(Bayes)、神经网络(NN)等。K近邻算法是一种基于实例的学习方法，它的工作原理是：如果一个样本在特征空间中的k个最相似（即特征空间中最邻近）的样本中的大多数属于某一个类别，则该样本也属于这个类别。支持向量机是一种有监督的学习模型，它的工作原理是：在特征空间中找到一个最优的超平面，使得超平面上的样本点和超平面之间的距离最小，从而实现对数据的分类。决策树是一种基于规则的学习模型，它的工作原理是：通过对数据的分析，构建一棵决策树，以汪告此来决定数据的分类。贝叶斯算法是一种基于概率的学习模型，它的锋陵陵工作原理是：根据贝叶斯定理，通过计算概率来决定数据的分类。神经银戚网络是一种模拟人脑神经元的网络，它的工作原理是：通过训练神经网络，让神经网络学习数据的特征，以此来决定数据的分类。
❿ KNN算法，k近邻
K最近邻(k-Nearest Neighbour，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。