机器学习面试问题8
userCF和itemCF在实际当中如何使用，提供具体操作，以及它们的优势（推荐系统）
基于用户的协同过滤算法UserCF
基于用户的协同过滤，通过不同用户对物品的评分来评测用户之间的相似性，基于用户间的相似性做出推荐。
简单来讲就是：给用户推荐和他兴趣相似的其他用户喜欢的物品。
基于UserCF的基本思想相当简单，基于用户对物品的偏好找到相邻邻居用户，然后将邻居用户喜欢的推荐给当前用户。
计算上，就是将一个用户对所有物品的偏好作为一个向量来计算用户之间的相似度，找到K邻居后，根据邻居的相似度权重以及他们对物品的偏好，预测当前用户没有偏好的未涉及物品，计算得到一个排序的物品列表作为推荐。
基于物品的协同过滤算法ItemCF
基于item的协同过滤，通过用户对不同item的评分来评测item之间的相似性，基于item之间的相似性做出推荐。
简单来讲就是：给用户推荐和他之前喜欢的物品相似的物品。
基于ItemCF的原理和基于UserCF类似，只是在计算邻居时采用物品本身，而不是从用户的角度，即基于用户对物品的偏好找到相似的物品，然后根据用户的历史偏好，推荐相似的物品给他。
从计算的角度看，就是将所有用户对某个物品的偏好作为一个向量来计算物品之间的相似度，得到物品的相似物品后，根据用户历史的偏好预测当前用户还没有表示偏好的物品，计算得到一个排序的物品列表作为推荐。
User CF 和Item CF的比较：
对于电子商务，用户数量一般大大超过商品数量，此时Item CF的计算复杂度较低。
在非社交网络的网站中，内容内在的联系是很重要的推荐原则，它比基于相似用户的推荐原则更加有效。比如在购书网站上，当你看一本书的时候，推荐引擎会给你推荐相关的书籍，这个推荐的重要性远远超过了网站首页对该用户的综合推荐。可以看到，在这种情况下，Item CF 的推荐成为了引导用户浏览的重要手段。基于物品的协同过滤算法，是目前电子商务采用最广泛的推荐算法。
在社交网络站点中，User CF 是一个更不错的选择，User CF 加上社会网络信息，可以增加用户对推荐解释的信服程度。
如何用Logic regression建立一个广告点击次数预测模型
主要分为两个步骤：线下训练和线上计算。
线下训练中使用Hadoop，从搜索引擎日志出发，经历数据清洗、提取特征、合并增量、排序降维、模型求解、模型验证等步骤，最终得出一个特征到权重的映射文件，即所需模型。
在线上计算部分，要经历扩展匹配、广告粗选、CTR计算等步骤，取出CTR中最高的10个广告返回给前端。
逻辑回归模型用于提取数据集中区分度高的特征。
详细可参考：
http://www.doc88.com/p-7042012124449.html
举一个适合采用层次分析法的例子
层次分析法的思想：将所有要分析的问题层次化，根据问题的性质和所要达到的总目标，将问题分为不同的组成因素，并按照这些因素间的关联影响即其隶属关系，将因素按不同层次聚集组合，形成一个多层次分析结构模型，最后，对问题进行优劣性比较排序。
层次分析法的步骤：
1）找准各因素之间的隶属度关系建立递阶层次结构。
2）构造判断矩阵（成对比较阵）并赋值。
3）层次单排序（计算权向量）与检验（一致性检验）。
4）层次总排序（组合权向量）与检验（一致性检验）。
5）结果分析。
关联分析中的极大频繁项集,FP增长算法
最大频繁项集是各频繁k项集中符合无超集条件的频繁项集。
项集：由项组成的集合。
若项集的支持度≥给定最小支持度，称其为频繁项集。
超集：若一个集合S2中的每一个元素都在集合S1中，且集合S1中可能包含S2中没有的元素，则集合S1就是S2的一个超集。 S1是S2的超集，则S2是S1的真子集。
如果频繁项集L 的所有超集都是非频繁项集, 那么称L 为最大频繁项集或称最大频繁模式。
频繁项集是最大频繁项集的子集。最大频繁项集中包含了频繁项集的频繁信息， 且通常项集的规模要小几个数量级。所以在数据集中含有较长的频繁模式时挖掘最大频繁项集是非常有效的手段。
FP增长算法：在算法中使用了一种称为频繁模式树（Frequent Pattern Tree）的数据结构。
Apriori算法在产生频繁模式完全集前需要对数据库进行多次扫描，同时产生大量的候选频繁集，这就使Apriori算法时间和空间复杂度较大。但是Apriori算法中有一个很重要的性质：频繁项集的所有非空子集都必须也是频繁的。由此性质，引出了FP增长算法。
首先介绍FP增长算法中的几个概念：
a.FP-Tree：将事务数据表中的各个事务数据项按照支持度排序后，把每个事务中的数据项按降序依次插入到一棵以NULL为根结点的树中，同时在每个结点处记录该结点出现的支持度。
b.条件模式基：包含FP-Tree中与后缀模式一起出现的前缀路径的集合。
c.条件树：将条件模式基按照FP-Tree的构造原则形成的一个新的FP-Tree。
步骤：
挖掘频繁模式前首先要构造FP-Tree，
输入:一个事物数据库D和一个最小支持度threshold.
输出:对应的FP-tree.
算法流程
1.扫描数据库T一遍.得到频繁项的集合F和每个频繁项的支持度.把F按支持度递降排序,结果记为L.
2.创建FP-tree的根节点,记为T,并且标记为”null”.然后对D中的每个事务t,
根据L中的顺序,选出并排序t中的事务项.把t中排好序的事务项列表记为[p|P],其中p是第一个元素,P是列表的剩余部分.调用insert_tree([p|P],T).
函数insert_tree([p|P],T)的运行如下.
如果T有一个子结点N,其中N.item-name=p.item-name,则将N的count阈值+1;
否则,创建一个新节点N,使它的count为1,使它的父节点为T,并且使它的node_link和那些具有相同item_name域串起来.如果P非空,则递归调用insert_tree(P,N).
对FP-Tree进行挖掘，算法如下：
输入:一棵用算法一建立的树Tree
输出:所有的频繁集
步骤:
调用FP-growth(Tree,null).
procedure FP-Growth ( Tree, x)
{
(1) if (Tree只包含单路径P) then
(2) 对路径P中节点的每个组合（记为B）
(3) 生成模式B并x，支持数=B中所有节点的最小支持度
(4) else 对Tree头上的每个ai，do
{
(5) 生成模式B= ai 并 x，支持度=ai.support；
(6) 构造B的条件模式库和B的条件FP树TreeB；
(7) if TreeB != 空集
(8) then call FP-Growth ( TreeB , B )
}}
如何解决过拟合问题
过拟合：为了得到一致假设而使假设变得过度复杂称为过拟合。
过拟合的产生原因：
1）由于对样本数据，可能存在隐单元的表示不唯一，即产生的分类的决策面不唯一。
2）权值学习迭代次数足够多，拟合了训练数据中的噪声和训练样例中没有代表性的特征。
过度拟合解决方法：
1）权值衰减。
在每次迭代过程中以某个小因子降低每个权值，这等效于修改E的定义，加入一个与网络权值的总量相应的惩罚项，此方法的动机是保持权值较小，避免权值衰减，从而使学习过程向着复杂决策面的反方向偏。
2）适当的停止准则。
3）验证数据。
一个最成功的方法是在训练数据外再为算法提供一套验证数据,应该使用在验证集合上产生最小误差的迭代次数，不是总能明显地确定验证集合何时达到最小误差。当验证出现的错误上升时停止训练。
4）交叉验证。
交叉验证方法在可获得额外的数据提供验证集合时工作得很好，但是小训练集合的过度拟合问题更为严重。
k-fold交叉方法:
把训练样例分成k份,然后进行k次交叉验证过程,每次使用不同的一份作为验证集合,其余k-1份合并作为训练集合.每个样例会在一次实验中被用作验证样例,在k-1次实验中被用作训练样例;每次实验中,使用上面讨论的交叉验证过程来决定在验证集合上取得最佳性能的迭代次数n*,然后计算这些迭代次数的均值,作为最终需要的迭代次数。
5） 减少特征
人工选择，预留一些特征；利用算法选取一些比较好的特征。
6）正则化
降低模型复杂度。
也可参见：
http://blog.csdn.net/heyongluoyao8/article/details/49429629
L1和L2正则的区别，如何选择L1和L2正则
正则化项即罚函数，该项对模型向量进行“惩罚”，从而避免单纯最小二乘问题的过拟合问题。训练的目的是最小化目标函数，则C越小，意味着惩罚越小，分类间隔也就越小，分类错误也就越少。
正则化项本质上是一种先验信息，整个最优化问题从贝叶斯观点来看是一种贝叶斯最大后验估计，其中正则化项对应后验估计中的先验信息，损失函数对应后验估计中的似然函数，两者的乘积即对应贝叶斯最大后验估计的形式，如果你将这个贝叶斯最大后验估计的形式取对数，即进行极大似然估计，你就会发现问题立马变成了损失函数+正则化项的最优化问题形式。
(1) 避免出现过拟合（over-fitting）。经验风险最小化 + 正则化项 = 结构风险最小化。
(2) 从模型求解上看，正则化提供了一种唯一解的可能。光用最小二乘拟合可能出现无数组解，加个L1或L2正则化项能有唯一解。
L1范数是指向量中各个元素绝对值之和，用于特征选择;
L1正则化将系数的l1范数作为惩罚项加到损失函数上。
L2范数是指向量各元素的平方和然后求平方根，用于 防止过拟合，提升模型的泛化能力。
L2正则化将系数向量的L2范数添加到了损失函数中。L2惩罚项中系数是二次方的。
L1与L2区别：使用L1可以得到稀疏的权值；用L2可以得到平滑的权值。
L1优点是能够获得sparse模型，对于large-scale的问题来说这一点很重要，因为可以减少存储空间。缺点是加入L1后目标函数在原点不可导，需要做特殊处理。
L2优点是实现简单，能够起到正则化的作用。缺点就是L1的优点：无法获得sparse模型。
实际上L1也是一种妥协的做法，要获得真正sparse的模型，要用L0正则化。
随机森林的学习过程
随机森林指的是利用多棵树对样本进行训练并预测的一种分类器。
在机器学习中，随机森林是一个包含多个决策树的分类器， 并且其输出的类别是由个别树输出的类别的众数而定。
随机森林的构建过程：
首先，从原始的数据集中采取有放回的抽样，构造子数据集，子数据集的数据量是和原始数据集相同的。不同子数据集的元素可以重复，同一个子数据集中的元素也可以重复。第二，利用子数据集来构建子决策树，将这个数据放到每个子决策树中，每个子决策树输出一个结果。最后，如果有了新的数据需要通过随机森林得到分类结果，就可以通过对子决策树的判断结果的投票，得到随机森林的输出结果了。
随机森林中的每一颗树是如何学习的
每棵树按照如下规则生成：
1）如果训练集大小为N，对于每棵树而言， 随机且有放回地 从训练集中的抽取N个训练样本 （这种采样方式称为bootstrap sample） ，作为该树的训练集；
从这里我们可以知道：每棵树的训练集都是不同的，而且里面包含重复的训练样本（理解这点很重要）。
2）如果每个样本的特征维度为M，指定一个 常数m<<M ， 随机地 从M个特征中选取m个特征子集，每次树进行分裂时，从这m个特征中选择最优的；
3）每棵树都尽最大程度的生长，并且没有剪枝过程 。
一开始我们提到的随机森林中的“随机”就是指的这里的两个随机性。 两个随机性的引入对随机森林的分类性能至关重要。由于它们的引入，使得随机森林不容易陷入过拟合，并且具有很好得抗噪能力（比如：对缺省值不敏感）。
详细可参见：
http://blog.csdn.net/luzonghao1/article/details/50857302
随机森林学习算法中CART树的基尼指数是什么
可参见：
2.http://blog.csdn.net/smf0504/article/details/51920678
k-meanshift机制及实现
Mean Shift算法：一般是指一个迭代的步骤，即先算出当前点的偏移均值,移动该点到其偏移均值，然后以此为新的起始点，继续移动，直到满足一定的条件结束。是一种梯度聚类算法。
算法推导可参见：
http://www.cnblogs.com/liqizhou/archive/2012/05/12/2497220.html
meanshift实现：
meanshift.h 代码如下：ifndef _MEANSHIFT_H_
#define _MEANSHIFT_H_
#include "common.h"
class MeanShift
{
public:
typedef std::vector<VecPoint> VecVecPoint;
static const float NEAREST_ZERO;
static const float C; //!高斯核函数中的常数
MeanShift() : m_size(0), R(0.0f){}
/** \brief 设置输入点云
* \param[in] pPntCloud 输入点云
*/
bool setInputCloud(const PointCloud<PointXYZ>::Ptr pPntCloud);
/** \brief 获取聚类后的点云 */
VecVecPoint & getOutputCloud()
{
return vv_pnt;
}
/** \brief 设置K近邻算法的搜索半径
* \param[in] radius 半径
*/
bool setKNNRadius(const float radius)
{
R = radius;
return true;
}
/** \brief 执行MeanShift聚类算法 */
bool process();
/** \brief 保存聚类后的点云文件
* \param[in] dir_name 保存的目录
* \param[in] prex_name 文件名前缀
*/
bool SaveFile(const char *dir_name, const char *prex_name);
private:
size_t m_size; //!要处理点的个数
PointCloud<PointXYZ>::Ptr mp_pointcloud; //!PCL形式的点云，主要是为了使用FLANN的KD树
VecPoint mv_pntcld; //!点云
VecPoint mv_local_mode; //!每个点的局部模式
VecVecPoint vv_pnt; //!聚类后的点云
float R; //!K近邻算法时对应的搜索半径
/** \brief 对每个点执行MeanShift
* \param[in] in_pnt 输入的点
* \param[out] out_pnt 输出的点
*/
inline bool execMeanShiftEachPoint(const PointXYZ &in_pnt, Point &out_pnt);
/** \brief 将具有相同局部模式的点归为一类
* \param[in] v_localmode 各个点对应的局部模式
* \param[out] vv_pnt 归并后的点
*/
bool mergeSameLocalModePoint(const VecPoint &v_localmode, VecVecPoint &vv_pnt);
inline float gauss(float x)
{
return C * sqrt(x) * exp(-0.5 * x);
}
};
#endif
meanshift.cpp 代码如下：#include "meanshift.h"
const float MeanShift::NEAREST_ZERO = 0.01;
const float MeanShift::C = 2.0f;
bool MeanShift::setInputCloud(const PointCloud<PointXYZ>::Ptr pPntCloud)
{
m_size = pPntCloud->points.size();
mv_pntcld.resize(m_size);
mv_local_mode.resize(m_size);
mp_pointcloud = pPntCloud;
for (size_t i = 0; i < m_size; ++i)
{
mv_pntcld[i].x = pPntCloud->points[i].x;
mv_pntcld[i].y = pPntCloud->points[i].y;
mv_pntcld[i].z = pPntCloud->points[i].z;
}
return true;
}
inline bool MeanShift::execMeanShiftEachPoint(const PointXYZ &in_pnt, Point &out_pnt)
{
// Set up KDTree
pcl::KdTreeFLANN<PointXYZ>::Ptr tree (new pcl::KdTreeFLANN<PointXYZ>);
tree->setInputCloud (mp_pointcloud);
// Main Loop
PointXYZ pnt = in_pnt;
while (1)
{
// Neighbors containers
std::vector<int> k_indices;
std::vector<float> k_distances;
float sum_weigh = 0;
float x = 0.0f, y = 0.0f, z = 0.0f;
float dist_pnts = 0.0f;
tree->radiusSearch (pnt, R, k_indices, k_distances);
for (int i = 0, pnumber = k_indices.size(); i < pnumber; ++i)
{
size_t index = k_indices[i];
PointXYZ &nbhd_pnt = mp_pointcloud->points[index];
float sqr_dist = k_distances[i];
float gauss_param = sqr_dist / (R * R);
float w = gauss(gauss_param);
x += nbhd_pnt.x * w;
y += nbhd_pnt.y * w;
z += nbhd_pnt.z * w;
sum_weigh += w;
}
x = x / sum_weigh;
y = y / sum_weigh;
z = z / sum_weigh;
float diff_x = x - pnt.x, diff_y = y - pnt.y, diff_z = z - pnt.z;
dist_pnts = sqrt(diff_x * diff_x + diff_y * diff_y + diff_z * diff_z);
if (dist_pnts <= 0.0001/*MeanShift::NEAREST_ZERO*/)
{
break;
}
pnt.x = x;
pnt.y = y;
pnt.z = z;
};
out_pnt.x = pnt.x;
out_pnt.y = pnt.y;
out_pnt.z = pnt.z;
return true;
}
bool MeanShift::mergeSameLocalModePoint(const VecPoint &v_localmode, VecVecPoint &vv_pnt)
{
assert(v_localmode.size() == m_size);
std::vector<bool> v_iscluster(m_size, false);
for (size_t i = 0; i < m_size; ++i)
{
for (size_t j = i + 1; j < m_size; ++j)
{
const Point & lmpnt1 = v_localmode[i];
const Point & lmpnt2 = v_localmode[j];
Point pnt1(mp_pointcloud->points[i].x, mp_pointcloud->points[i].y, mp_pointcloud->points[i].z);
Point pnt2(mp_pointcloud->points[j].x, mp_pointcloud->points[j].y, mp_pointcloud->points[j].z);
float dist = 0.0f;
dist = getPointsDist(lmpnt1, lmpnt2);
if (dist <= MeanShift::NEAREST_ZERO)
{
//两个点可近似重合
VecPoint v_pnt;
if ( !v_iscluster[i] && !v_iscluster[j])
{
v_iscluster[i] = true;
v_pnt.push_back(pnt1);
v_iscluster[j] = true;
v_pnt.push_back(pnt2);
vv_pnt.push_back(v_pnt);
}
else if ( v_iscluster[i] && !v_iscluster[j])
{
size_t clustered_count = vv_pnt.size();
size_t m, n;
for (m = 0; m < clustered_count; ++m)
{
size_t count = vv_pnt[m].size();
for (n = 0; n < count; ++n)
{
if (pnt1 == vv_pnt[m][n])
{
vv_pnt[m].push_back(pnt2);
v_iscluster[j] = true;
goto LABEL1;
}
} // for n
} // for m
LABEL1:
;
} // else if
else if ( !v_iscluster[i] && v_iscluster[j])
{
size_t clustered_count = vv_pnt.size();
size_t m, n;
for (m = 0; m < clustered_count; ++m)
{
size_t count = vv_pnt[m].size();
for (n = 0; n < count; ++n)
{
if (pnt2 == vv_pnt[m][n])
{
vv_pnt[m].push_back(pnt1);
v_iscluster[i] = true;
goto LABEL2;
}
} // for n
} // for m
LABEL2:
;
}
else
{
//都已经聚类，就不做处理
}
} // if (dist <= NEAREST_ZERO)
} // for j
} // for i
for (size_t i = 0; i < m_size; ++i)
{
if (!v_iscluster[i])
{
Point pnt(mp_pointcloud->points[i].x, mp_pointcloud->points[i].y, mp_pointcloud->points[i].z);
VecPoint v_pnt;
v_iscluster[i] = true;
v_pnt.push_back(pnt);
vv_pnt.push_back(v_pnt);
}
}
return true;
}
bool MeanShift::process()
{
for (size_t i = 0; i < m_size; ++i)
{
const PointXYZ &pnt = mp_pointcloud->points[i];
execMeanShiftEachPoint(pnt, mv_local_mode[i]);
}
mergeSameLocalModePoint(mv_local_mode, vv_pnt);
return true;
}
bool MeanShift::SaveFile(const char *dir_name, const char *prex_name)
{
size_t cluster_count = vv_pnt.size();
for (size_t i = 0; i < cluster_count; ++i)
{
pcl::PointCloud<pcl::PointXYZ>::Ptr p_pnt_cloud(new pcl::PointCloud<pcl::PointXYZ> ());
for (size_t j = 0, grp_pnt_count = vv_pnt[i].size(); j < grp_pnt_count; ++j)
{
pcl::PointXYZ pt;
pt.x = vv_pnt[i][j].x;
pt.y = vv_pnt[i][j].y;
pt.z = vv_pnt[i][j].z;
p_pnt_cloud->points.push_back(pt);
}
p_pnt_cloud->width = static_cast<size_t>(vv_pnt[i].size());
p_pnt_cloud->height = 1;
char newFileName[256] = {0};
char indexStr[16] = {0};
strcat(newFileName, dir_name);
strcat(newFileName, "/");
strcat(newFileName, prex_name);
strcat(newFileName, "-");
sprintf(indexStr, "%d", i + 1);
strcat(newFileName, indexStr);
strcat(newFileName, ".pcd");
io::savePCDFileASCII(newFileName, *p_pnt_cloud);
}
return true;
}
可参见：http://blog.csdn.net/lming_08/article/details/23595201
实现最小二乘法
最小二乘法（又称最小平方法）是一种数学优化技术。它通过最小化误差的平方和寻找数据的最佳函数匹配。利用最小二乘法可以简便地求得未知的数据，并使得这些求得的数据与实际数据之间误差的平方和为最小。最小二乘法还可用于曲线拟合。其他一些优化问题也可通过最小化能量或最大化熵用最小二乘法来表达。
最小二乘法C++实现参数1为输入文件
输入 ： x
输出： 预测的y
*/
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
class LeastSquare{
double a, b;
public:
LeastSquare(const vector<double>& x, const vector<double>& y)
{
double t1=0, t2=0, t3=0, t4=0;
for(int i=0; i<x.size(); ++i)
{
t1 += x[i]*x[i];
t2 += x[i];
t3 += x[i]*y[i];
t4 += y[i];
}
a = (t3*x.size() - t2*t4) / (t1*x.size() - t2*t2); // 求得β1
b = (t1*t4 - t2*t3) / (t1*x.size() - t2*t2); // 求得β2
}
double getY(const double x) const
{
return a*x + b;
}
void print() const
{
cout<<"y = "<<a<<"x + "<<b<<"\n";
}
};
int main(int argc, char *argv[])
{
if(argc != 2)
{
cout<<"Usage: DataFile.txt"<<endl;
return -1;
}
else
{
vector<double> x;
ifstream in(argv[1]);
for(double d; in>>d; )
x.push_back(d);
int sz = x.size();
vector<double> y(x.begin()+sz/2, x.end());
x.resize(sz/2);
LeastSquare ls(x, y);
ls.print();
cout<<"Input x:\n";
double x0;
while(cin>>x0)
{
cout<<"y = "<<ls.getY(x0)<<endl;
cout<<"Input x:\n";
}
}
}
监督学习中，如果预测的变量是离散的，我们称其为分类（如决策树，支持向量机等），如果预测的变量是连续的，我们称其为回归。回归分析中，如果只包括一个自变量和一个因变量，且二者的关系可用一条直线近似表示，这种回归分析称为一元线性回归分析。如果回归分析中包括两个或两个以上的自变量，且因变量和自变量之间是线性关系，则称为多元线性回归分析。对于二维空间线性是一条直线；对于三维空间线性是一个平面，对于多维空间线性是一个超平面。
