{ 项目名称 }
XXX技术预研报告
机构公开信息
项目名称，《XXX技术预研报告》
版 本 历 史
? 机构名称，2002
Page 2 of 5
项目名称，《XXX技术预研报告》
目 录
0. 文档介绍 ........................................................................................... 错误！未定义书签。 摘要.................................................................................................... 错误！未定义书签。 读者对象 ............................................................................................ 错误！未定义书签。 参考文档 ............................................................................................ 错误！未定义书签。 术语与缩写解释 ................................................................................ 错误！未定义书签。
1. 背景介绍 ............................................................................................................................ 4
2. 技术预研目标 ..................................................................................................................... 5
3. 技术预研取得的工作成果 ................................................................................................. 5
4. 技术A的研究报告 ............................................................................................................ 5
5. 技术B的研究报告 ............................................................................................................ 5 ? 机构名称，2002
Page 3 of 5
项目名称，《XXX技术预研报告》
0. 文档介绍
0.1 文档目的
0.2 文档范围
0.3 读者对象
0.4 参考文档
提示：列出本文档的所有参考文献（可以是非正式出版物），格式如下：
[标识符] 作者，文献名称，出版单位（或归属单位），日期
例如：
[SPP-PROC-PP] SEPG，需求开发规范，机构名称，日期
0.5 术语与缩写解释
? 机构名称，2002
Page 4 of 5
项目名称，《XXX技术预研报告》
1. 背景介绍
提示：说明为什么要开展技术预研 。
2. 技术预研目标
提示：说明本次技术预研的主要内容与目标（必须是可以验证的）。
3. 技术预研取得的工作成果
提示：说明本次技术预研取得的工作成果（程序、文档、数据等）以及时间。
4. 技术A的研究报告
提示：
（1）解释重要的术语、基本概念；
（2）论述思想方法、技术方案、技术细节
5. 技术B的研究报告
提示：
（1）解释重要的术语、基本概念；
（2）论述思想方法、技术方案、技术细节
? 机构名称，2002
Page 5 of 5
第二篇：推荐系统技术预研报告
Mahout技术 预研报告
版本：V1.0
修订记录
用户书册
用户书册
目 录
1 简介 ................................................................................................................................................... 3
1.1
1.2 编写目的 ......................................................................................................................... 3 背景 ................................................................................................................................. 3
1.2.1
1.2.2
1.3 任务的提出 ....................................................................................................... 3 使用者 ............................................................................................................... 3 参考资料 ......................................................................................................................... 3
2 协同过滤机制分析 ........................................................................................................................... 4
2.1
2.2
2.3
2.4
2.5 基于协同过滤的推荐机制基本原理 ............................................................................. 4 基于用户的协同过滤推荐 ............................................................................................. 4 基于项目的协同过滤推荐 ............................................................................................. 5 SLOPE ONE协同过滤推荐 ................................................................................................. 6 协同过滤各种算法比较 ................................................................................................. 7
3 相似度的计算 ................................................................................................................................... 8
3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8 皮尔逊相关系数（PEARSON CORRELATION COEFFICIENT） ................................................... 8 欧几里德距离（EUCLIDEAN DISTANCE） ............................................................................ 8 COSINE 相似度（COSINE SIMILARITY） .............................................................................. 9 修正的余弦相似性 ......................................................................................................... 9 SPEARMAN秩相关系数--SPEARMAN CORRELATION ................................................................. 10 TANIMOTO 系数（TANIMOTO COEFFICIENT） ........................................................................ 10 对数似然相似度 ........................................................................................................... 11 曼哈顿距离 ................................................................................................................... 11
4 降维算法分析 ................................................................................................................................. 11
4.1
4.2 主成分分析 ................................................................................................................... 11 奇异值分解 ................................................................................................................... 12
5 关联规则挖掘算法分析 ................................................................................................................. 13
5.1
5.2 概要 ............................................................................................................................... 13 并行FP GROWTH算法（PARALLEL FP GROWTH ALGORITHM） ............................................... 13
6 聚类算法分析 ................................................................................................................................. 14
6.1
6.2 概要 ............................................................................................................................... 14 各种聚类算法 ............................................................................................................... 14 第1页
用户书册
6.2.1
6.2.2
6.2.3
6.2.4
6.2.5
6.2.6 K均值 （K-means） ...................................................................................... 14 模糊K均值（Fuzzy K-means） ................................................................... 14 Canopy聚类（Canopy Clustering） .......................................................... 15 均值漂移聚类(Mean Shift Clustering) ................................................... 15 EM聚类(Expectation Maximization) ........................................................ 16 狄利克雷聚类算法 ......................................................................................... 17
7 分类算法分析 ................................................................................................................................. 17
7.1
7.2 概要 ............................................................................................................................... 17 各种分类算法 ............................................................................................................... 17
7.2.1
7.2.2
7.2.3
7.2.4
7.2.5
7.2.6
逻辑回归算法 ................................................................................................. 17 贝叶斯算法 ..................................................................................................... 18 SVM（支持向量机） ....................................................................................... 19 神经网络 ......................................................................................................... 20 HMM (隐马尔科夫模型) ................................................................................. 21 决策树 ............................................................................................................. 21
第2页
用户书册
1 简介
1.1 编写目的
通过对Apache Mahout开源框架和推荐系统相关技术的学习，归纳出推荐系统领域目前的主要相关算法以及这些算法的应用场景及优缺点，为后续“金融产品推荐”产品提供理论支持和技术储备。
1.2 背景
1.2.1 任务的提出
。。。。。。。。
1.2.2 使用者
金融产品推荐项目组开发者。
1.3 参考资料
参考资料主要来源于互联网和相关算法的论文。
第3页
用户书册
2 协同过滤机制分析
2.1 基于协同过滤的推荐机制基本原理
协同过滤是利用集体智慧的一个典型方法。协同过滤的核心思想是我们一般更倾向于从口味比较类似的朋友那里得到推荐。
协同过滤一般是在海量的用户中发掘出一小部分和你品位比较类似的，在协同过滤中，这些用户成为邻居，然后根据他们喜欢的其他东西组织成一个排序的目录作为推荐给你。
要实现协同过滤，需要以下几个步骤 ：
? 收集用户偏好
? 找到相似的用户或物品 （计算相似度）
? 计算推荐列表
下面介绍mahout实现的的三种协同过滤推荐机制。
2.2 基于用户的协同过滤推荐
1. 基本原理说明
基于用户的协同过滤推荐的基本原理是，根据所有用户对物品或者信息的偏好，发现与当前用户口味和偏好相似的“邻居”用户群，在一般的应用中是采用计算“K- 邻居”的算法；然后，基于这 K 个邻居的历史偏好信息，为当前用户进行推荐。下图给出了原理图。
基于用户的协同过滤推荐机制的基本原理
上图示意出基于用户的协同过滤推荐机制的基本原理，假设用户A喜欢物品A，物品C，用户B喜欢物品B，用户C喜欢物品A ，物品C和物品D；从这些用户的历史喜好信息中，我们可以发现用户A和用户C的口味和偏好是比较类似的，同时用户C还喜欢物品D，那么我们可以推断用户A可能也喜欢物品 D，因此可以将物品D推荐给用户A。
第4页
用户书册
基于用户的协同过滤推荐机制和基于人口统计学的推荐机制都是计算用户的相似度，并基于“邻居”用户群计算推荐，但它们所不同的是如何计算用户的相似度，基于人口统计学的机制只考虑用户本身的特征，而基于用户的协同过滤机制可是在用户的历史偏好的数据上计算用户的相似度，它的基本假设是，喜欢类似物品的用户可能有相同或者相似的口味和偏好。
2. 基于mahout实现基于用户的协同过滤推荐
给出示例代码如下：
DataModel model = new FileDataModel(new File("preferences.dat"));
UserSimilarity similarity = new PearsonCorrelationSimilarity(model);
UserNeighborhood neighborhood = new NearestNUserNeighborhood(100,
similarity, model);
Recommender recommender = new GenericUserBasedRecommender(model,
neighborhood, similarity);
2.3 基于项目的协同过滤推荐
1. 基本原理说明
基于项目的协同过滤推荐的基本原理也是类似的，只是说它使用所有用户对物品或者信息的偏好，发现物品和物品之间的相似度，然后根据用户的历史偏好信息，将类似的物品推荐给用户，下图诠释了它的基本原理。
基于项目的协同过滤推荐机制的基本原理
假设用户A喜欢物品A和物品C，用户B喜欢物品A，物品B和物品C，用户C喜欢物品A，从这些用户的历史喜好可以分析出物品A和物品C时比较类似的，喜欢物品A的人都喜欢物品C，基于这个数据可以推断用户C很有可能也喜欢物品C，所以系统会将物品 第5页
用户书册
C推荐给用户C。基于项目的协同过滤推荐和基于内容的推荐其实都是基于物品相似度预测推荐，只是相似度计算的方法不一样，前者是从用户历史的偏好推断，而后者是基于物品本身的属性特征信息。
2. 基于mahout实现基于项目的协同过滤推荐
给出示例代码如下：
DataModel model = new FileDataModel(new File("preferences.dat"));
ItemSimilarity similarity = new PearsonCorrelationSimilarity(model);
Recommender recommender = new GenericItemBasedRecommender(model,
similarity);
2.4 Slope One协同过滤推荐
1. 基本原理说明
User CF 和 Item CF 是最常用最容易理解的两种 CF 的推荐策略，但在大数据量时，它们的计算量会很大，从而导致推荐效率较差。因此 Mahout 还提供了一种更加轻量级的 CF 推荐策略：Slope One。 Slope One 是有 Daniel Lemire 和 Anna Maclachlan 在 2005 年提出的一种对基于评分的协同过滤推荐引擎的改进方法，下面介绍一下它的基本思想。
上图给出了例子，假设系统对于物品 A，物品 B 和物品 C 的平均评分分别是
3，4 和 4。基于 Slope One 的方法会得到以下规律：
? 用户对物品 B 的评分 = 用户对物品 A 的评分 + 1
第6页
用户书册
? 用户对物品 B 的评分 = 用户对物品 C 的评分
基于以上的规律，我们可以对用户 A 和用户 B 的打分进行预测：
? 对用户 A，他给物品 A 打分 4，那么我们可以推测他对物品 B 的评分是 5，对
物品 C 的打分也是 5。
? 对用户 B，他给物品 A 打分 2，给物品 C 打分 4，根据第一条规律，我们可以
推断他对物品 B 的评分是 3；而根据第二条规律，推断出评分是 4。当出现冲突
时，我们可以对各种规则得到的推断进行就平均，所以给出的推断是 3.5。
这就是 Slope One 推荐的基本原理，它将用户的评分之间的关系看作简单的线性关系。
2. 基于mahout实现Slope One
下面给出代码示例：
DiffStorage diffStorage = new MemoryDiffStorage(model, Weighting.UNWEIGHTED, false, Long.MAX_VALUE));
Recommender recommender = new SlopeOneRecommender(model, Weighting.UNWEIGHTED, Weighting.UNWEIGHTED, diffStorage);
//Database-based Recommender
AbstractJDBCDataModel model = new MySQLJDBCDataModel();
DiffStorage diffStorage = new MySQLJDBCDiffStorage(model);
Recommender recommender = new SlopeOneRecommender(model, Weighting.WEIGHTED, Weighting.WEIGHTED, diffStorage);
2.5 协同过滤各种算法比较
基于项目的协同过滤推荐机制是 Amazon 在基于用户的机制上改良的一种策略，因为在大部分的 Web 站点中，物品的个数是远远小于用户的数量的，而且物品的个数和相似度相对比较稳定，同时基于项目的机制比基于用户的实时性更好一些。但也不是所有的场景都是这样的情况，可以设想一下在一些新闻推荐系统中，也许物品，也就是新闻的个数可能大于用户的个数，而且新闻的更新程度也有很快，所以它的形似度依然不稳定。但在大数据量时，基于项目的协同过滤和基于用户的协同过滤计算量会很大，从而导致推荐效率较差。
所以，其实可以看出，推荐策略的选择其实和具体的应用场景有很大的关系。
第7页
用户书册
3 相似度的计算
关于相似度的计算，现有的几种基本方法都是基于向量（Vector）的，其实也就是计算两个向量的距离，距离越近相似度越大。在推荐的场景中，在用 户 - 物品偏好的二维矩阵中，我们可以将一个用户对所有物品的偏好作为一个向量来计算用户之间的相似度，或者将所有用户对某个物品的偏好作为一个向量来计算物品 之间的相似度。下面我们详细介绍几种常用的相似度计算方法：
3.1 皮尔逊相关系数（Pearson Correlation Coefficient）
皮尔逊相关系数一般用于计算两个定距变量间联系的紧密程度，它的取值在 [-1，+1] 之间。
Sx, Sy是 x 和 y 的样品标准偏差。
原理：用来反映两个变量线性相关程度的统计量
范围：[-1,1]，绝对值越大，说明相关性越强，负相关对于推荐的意义小。
基于皮尔森相关系数的相似度有以下缺点：
? 没有考虑用户间重叠的评分项数量对相似度的影响；（共同评分项的数量）
? 如果两个用户之间只有一个共同的评分项，相似度也不能被计算。
? 如果重叠的值都相等，也无法计算相似性（标准差为0，做除数）。
3.2 欧几里德距离（Euclidean Distance）
最初用于计算欧几里德空间中两个点的距离，假设 x，y 是 n 维空间的两个点，它们之间的欧几里德距离是：
可以看出，当 n=2 时，欧几里德距离就是平面上两个点的距离。当用欧几里德距离表示相似度，一般采用以下公式进行转换：距离越小，相似度越大。
第8页
用户书册
原理：利用欧式距离d定义的相似度s，s=1 / (1+d)。
范围：[0,1]，值越大，说明d越小，也就是距离越近，则相似度越大。
说明：同皮尔森相似度一样，该相似度也没有考虑重叠数对结果的影响.只要至少有一个共同评分项，就能用欧几里德距离计算相似度；如果没有共同评分项，那么欧几里德距离也就失去了作用。
3.3 Cosine 相似度（Cosine Similarity）
Cosine 相似度被广泛应用于计算文档数据的相似度：
原理：多维空间两点与所设定的点形成夹角的余弦值。
范围：[-1,1]，值越大，说明夹角越大，两点相距就越远，相似度就越小。
余弦相似度的特点：
只关注共同评分的项目
? 对用户的绝对的数值不敏感
? 计算时不考虑用户之间的共同评分项数量，即使仅仅有极少相同评分项，也有可能
获得很大的相似度结果
? 只要各个评分项之间越趋向于对应成比例，而不论数值差异如何，则相似度越趋近
于1.000.
欧式距离和余弦相似性的比较
根据欧氏距离和余弦相似度各自的计算方式和衡量特征，分别适用于不同的数据分析模型：欧氏距离能够体现个体数值特征的绝对差异，所以更多的用于需要从维度的数值大小中体现差异的分析，如使用用户行为指标分析用户价值的相似度或差异；而余弦相似度更多的是从方向上区分差异，而对绝对的数值不敏感，更多的用于使用用户对内容评分来区分用兴趣的相似度和差异，同时修正了用户间可能存在的度量标准不统一的问题（因为余弦相似度对绝对数值不敏感）。
3.4 修正的余弦相似性
第9页
用户书册
在余弦相似度的介绍中说到：余弦相似度更多的是从方向上区分差异，而对绝对的数值不敏感。因此没法衡量每个维数值的差异，会导致这样一个情况：比如用户对内容评分，5分制，X和Y两个用户对两个内容的评分分别为(1,2)和(4,5)，使用余弦相似度得出的结果是0.98，两者极为相似，但从评分上看X似乎不喜欢这两个内容，而Y比较喜欢，余弦相似度对数值的不敏感导致了结果的误差，需要修正这种不合理性，就出现了调整余弦相似度，即所有维度上的数值都减去一个均值，比如X和Y的评分均值都是3，那么调整后为(-2,-1)和(1,2)，再用余弦相似度计算，得到-0.8，相似度为负值并且差异不小，但显然更加符合现实。
3.5 Spearman秩相关系数--Spearman Correlation
原理：Spearman秩相关系数通常被认为是排列后的变量之间的Pearson线性相关系数。 范围：{-1.0,1.0}，当一致时为1.0，不一致时为-1.0。
说明：计算非常慢，有大量排序。针对推荐系统中的数据集来讲，用Spearman秩相关系数作为相似度量是不合适的。
3.6 Tanimoto 系数（Tanimoto Coefficient）
Tanimoto 系数不关心用户对物品的具体评分值是多少，它关心用户与物品之间是否存在关联关系。Tanimoto 系数依赖于用户和物品之间的这种Boolean关系作为输入。更准确的说法为：Tanimoto 系数主要用于计算符号度量或布尔值度量的个体间的相似度，因为个体的特征属性都是由符号度量或者布尔值标识，因此无法衡量差异具体值的大小，只能获得“是否相同”这个结果，所以Tanimoto 系数只关心个体间共同具有的特征是否一致这个问题。Tanimoto 系数又被叫做Jaccard 系数，其值等于两个用户共同关联（不管喜欢还是不喜欢）的物品数量除于两个用户分别关联的所有物品数量。
也就是关联的交集除于关联的并集，用公式表示为：
其值介于[0, 1]之间，如果两个用户关联的物品完全相同，交集等于并集，值为1；如果没有任何关联，交集为空，值为0。
第10页
用户书册
Tanimoto 系数多用于计算文档数据的相似度：
原理：是对Jaccard系数的扩展，等式为
范围：[0,1]，完全重叠时为1，无重叠项时为0，越接近1说明越相似。
说明：处理无打分的偏好数据。
3.7 对数似然相似度
原理：重叠的个数，不重叠的个数，都没有的个数
说明：处理无打分的偏好数据，比Tanimoto系数的计算方法更为智能。
3.8 曼哈顿距离
原理：曼哈顿距离的实现，同欧式距离相似，都是用于多维数据空间距离的测度 范围：[0,1]，同欧式距离一致，值越小，说明距离值越大，相似度越大。
说明：比欧式距离计算量少，性能相对高。
4 降维算法分析
4.1 主成分分析
主成分分析将多个变量通过线性变换以选出较少个数重要变量的一种多元统计分析方法。又称主分量分析。在用统计分析方法研究多变量的课题时，变量个数太多就会增加课题的复杂性。人们自然希望变量个数较少而得到的信息较多。在很多情形，变量之间是有一定的相关关系的，当两个变量之间有一定相关关系时，可以解释为这两个变量反映此课题的信息有一定的重叠。主成分分析是对于原先提出的所有变量，建立尽可能少的新变量，使得这些新变量是两两不相关的，而且这些新变量在反映课题的信息方面尽可能保持原有的信息。
算法原理：主成分分析所要做的就是设法将原来众多具有一定相关性的变量，重新组合为一组新的相互无关的综合变量来代替原来变量。通常，数学上的处理方法就是将原来的变量做线性组合，作为新的综合变量，但是这种组合如果不加以限制，则可以有很多，应该如 第11页
用户书册
何选择呢？如果将选取的第一个线性组合即第一个综合变量记为F1，自然希望它尽可能多地反映原来变量的信息，这里“信息”用方差来测量，即希望Var(F1)越大，表示F1包含的信息越多。因此在所有的线性组合中所选取的F1应该是方差最大的，故称F1为第一主成分。如果第一主成分不足以代表原来p个变量的信息，再考虑选取F2即第二个线性组合，为了有效地反映原来信息，F1已有的信息就不需要再出现在F2中，用数学语言表达就是要求Cov(F1,F2)=0，称F2为第二主成分，依此类推可以构造出第三、四??第p个主成分。
说明：主成分分析是采取一种数学降维的方法，找出几个综合变量来代替原来众多的变量，使这些综合变量能尽可能地代表原来变量的信息量，而且彼此之间互不相关。在推荐引擎中主要用来降维大规模的用户—物品矩阵。
4.2 奇异值分解
奇异值分解是一种矩阵分解技术，可将一个矩阵R分解成为3个矩阵的乘积，即R=TSD，S=diag(s1,s2,s3,…,sr)，其中，s1>=s2>=s3>=…>=sr，T和D分别为两个正交矩阵，r是矩阵R的秩，S是一个对角矩阵，所有的si按照大小顺序排列，称为奇异值。
奇异值分解有一个优点，它允许存在一个简化的近似矩阵。对于S，保留k个最大的奇异值，将其余的用0来代替，这样，我们就可以将S简化为仅有k个奇异值的矩阵（k<r）。因为引入了0，可以将S中的值为0的行和列删除，得到一个新的对角矩阵S1，如果对矩阵T和D据此简化得到矩阵T1和D1，那么有重构的矩阵R1=T1S1D1，R1约等于R，并且得到了降维。奇异值分解能够生成初始矩阵R的所有秩等于k的矩阵中与矩阵R最近似的一个。
第12页
用户书册
5 关联规则挖掘算法分析
5.1 概要
挖掘数据之间的关联、相关和许多其他有趣的联系，可以发现更多潜在的信息，进而影响商业决策。此外，他对数据的分类、聚类和其他数据挖掘任务也有很大的帮助。推荐系统中他可以帮助我们发现潜在的相似的用户群体
5.2 并行FP Growth算法（Parallel FP Growth Algorithm）
1. 工作原理
在关联规则挖掘领域最经典的算法是Apriori，其本质上就是寻找频繁项集（频繁项集就是所谓的“支持度”比较高的项集），是在满足一定支持度的情况下寻找置信度达到阈值的所有模式。其致命的缺点是需要多次扫描事务数据库，而且会生成大量短的候选模式。于是人们提出了各种裁剪（prune）数据集的方法以减少I/O开支，其中FP Growth算法就是其中非常高效的一种。其中使用了一种叫做FP-tree的数据结构，通过这种结构大大的减少了IO开销。
并行实现
我们把整个事务数据库放在一个列表里面传给FPGrowth，在实际中这是不可取的，因为内存不可能容下整个事务数据库，我们可能需要从数据库中一条一条地读入来建立FP-Tree。但无论如何 FP-Tree是肯定需要放在内存中的，但内存如果容不下怎么办？另外FPGrowth仍然是非常耗时的，你想提高速度怎么办？解决办法：分而治之，并行计算。我们把原始事务数据库分成N部分，在N个节点上并行地进行FPGrowth挖掘，最后把关联规则汇总到一起就可以了。
2. 优缺点
优点：高效
缺点：并行的情况下可能会遗漏关联规则或是得到的关联规则可能是冗余的，我们需要针对这两个问题做其他的处理。另外关联规则挖掘会产生大量的规则，但并不是所有的规则都是有用的及有些规则是隐性的，并不容易挖掘
第13页
用户书册
6 聚类算法分析
6.1 概要
聚类从广义上来讲是指分组时，将相似的事物放在一起。与分类不同的是我们事先并不知道事物有哪些类别，只是根据事物的特征将相似的事物归为一种类别。聚类是一种无监督的数据挖掘方法，它的形式多种多样。在推荐系统中我们可能会对用户进行聚类，进而针对特定的人群进行推荐。或是把产品进行聚类，向特定的用户推荐某一类产品。下面主要介绍一下几种常用的算法
6.2 各种聚类算法
6.2.1 K均值 （K-means）
3. 工作原理
算法首先随即的从数据集中选取K个初始聚族中心，计算各个样本数据到各个聚族中心的距离，然后把样本归到离他最近的那个聚族中心所在的类。计算形成的每一个聚族中数据对象的平均值（中心点）得到新的聚族中心，如果相邻两次的聚族中心没有变化，则说明样本调整已经结束。本算法的一个特点就是每次迭代都需要检测每个样本是否分类正确，若不正确，则需要调整，在样本全部调整完毕后再修改聚族中心，进入下次迭代。如果在一次迭代中，所有的样本已经被正确的分类，则不会调整，聚类中心也不会再有任何变化，则标志着算法结束。
4. 优缺点
缺点：
这个算法需要人为的去指定聚类的数目，在特定的应用场景中可能并不太适合，我们无法预先知道聚类的数量。算法起始阶段随即的选取初始聚类中心，这会导致算法对噪音数据及孤点数据的容忍度不够
优点：
这个算法的思想简单，确定的K个划分的平方误差最小，当聚类是密集的且类与类之间的区别明显是效果很好，在处理大数据集时这种算法相对来说是可伸缩的、高效的
6.2.2 模糊K均值（Fuzzy K-means）
1. 工作原理
K均值的分类结果使得一个特征向量要么属于某一聚族，要么不属于，而模糊k均值的 第14页
用户书册
结果是一个特征向量属于某一个聚族的概率。模糊K均值是在K均值算法的一个发展。
2. 优缺点
优缺点：K均值的优缺点同样是模糊K均值的优缺点，只是他们的结果集不同而已。
6.2.3 Canopy聚类（Canopy Clustering）
1. 工作原理：
capony聚类算法的可以分为两个阶段：
Stage1、把相似的样本数据放在一个canopy中，把整个数据集划分为一个个canopy，Canopy之间会存在重叠，但是不会存在某个样本不属于任何一个canopy的情况
Stage2、在各个Canopy 内使用传统的聚类方法(如K-means)，不属于同一Canopy 的对象之间不进行相似性计算。
并行算法
并行点是比较明显的，就是生成Canopy的过程可以并行，第一阶段，各个slave可以依据存储在本地的数据，各自在本地用上述算法生成若干 Canopy，最后在master机器将这些Canopy用相同算法汇总后得到最终的Canopy集合，第二阶段聚类操作就利用最终的Canopy集合进 行。 用map-reduce描述就是：datanode在map阶段，利用上述算法在本地生成若干Canopy，之后通过reduce操作得到最终的Canopy集合。
2. 优缺点
优点：
canopy第一阶段在计算对象相似性的时候使用了一种简单、代价较小的方法来计算相似性，可以提高算法的效率。（这里计算的相似度对数据进行一下预分类，不一定很准确）类似于K-means这样的聚类方法是需要人为指出K的值的，通过Stage1得到的Canopy 个数完全可以作为这个K值，一定程度上减少了选择K的 盲目性。Canopy对噪音及孤点数据的容忍度较高
缺点：
? 首先是轻量距离量度的选择，是选择数据模型其中的一个属性，还是其它外部属性
这对canopy的分布最为重要。
? T1, T2的取值影响到canopy重叠率f，以及canopy的粒度。
6.2.4 均值漂移聚类(Mean Shift Clustering)
1. 工作原理
第15页
用户书册
均值漂移算法是一种基于密度梯度上升的非参数方法, 一般是指一个迭代的步骤,即先算出当前点的偏移均值,移动该点到其偏移均值,然后以此为新的起始点,继续移动,直到满足一定的条件结束。
算法的具体步骤
? 选择窗的大小和初始位置.
? 计算此时窗口内的Mass Center.
? 调整窗口的中心到Mass Center.
? 重复2和3，直到窗口中心"会聚"，即每次窗口移动的距离小于一定的阈值。
2. 优缺点
优点：计算量小，简单易实现
缺点：窗口大小及初始位置的选择，会影响算法的准确性及效率。可以结合canopy算法来使用，用canopy算法来定初始位置
6.2.5 EM聚类(Expectation Maximization)
1. 工作原理
EM算法是基于模型的聚类方法，假设样本分布符合高斯混合模型，算法目的是确定各个高斯部件的参数，充分拟合给定数据，并得到一个模糊聚类，即每个样本以不同概率属于每个高斯分布，概率数值将由以上各个参数计算得到。EM 算法分为两步实现，即E-Step
M-Step
E-step：通过样本数据和模型参数（初始参数或是上一个迭代产生的参数值）来计算潜在变量（聚类中可以理解为潜在的类别）的似然函数
M-Step：对E步产生的似然函数求极大值，进而得到新的参数估值
这样不断的进行迭代，直到算法收敛。
2. 优缺点
优点：计算结果稳定、准确
缺点：相比于k-means计算复杂、收敛速度慢，对初始值敏感、只能达到局部最优解，对噪音及孤点数据的容忍度相对较差
第16页
用户书册
6.2.6 狄利克雷聚类算法
1. 工作原理
首先需要定义一个分布模型，简单的例如：圆形，三角形 等，复杂的例如正则分布，泊松分布等；然后按照模型对数据进行分类，将不同的对象加入一个模型，模型会增长或者收缩；每一轮过后需要对模型的各个参数进行重新计算，同时估计对象属于这个模型的概率。所以说，基于模型的聚类算法的核心是定义模型，对于一个聚类问题，模型定义的优劣直接影响了聚类的结果。
2. 优缺点
如果数据集对于其他聚类方法难以解释的时候，可以考虑此算法。但是不同的模型选择对结果有较大影响。
7 分类算法分析
7.1 概要
分类算法是解决分类问题的方法，是数据挖掘、机器学习和模式识别中一个重要的研究领域。分类算法通过对已知类别训练集的分析，从中提取描述重要数据类的模型，随后我们可以根据这个模型进行预测，推荐就是一种预测的行为。
分类算法的应用非常广泛，银行中风险评估、客户类别分类、文本检索和搜索引擎分类、安全领域中的入侵检测以及软件项目中的应用等等。
可以考虑通过和协同过滤推荐结合，以提高推荐的准确性。
7.2 各种分类算法
7.2.1 逻辑回归算法
3. 工作原理
首先了解逻辑回归之前先了解下线性回归：因变量和自变量之前存在线性关系。一般模型如下：
从一般模型可以看出Y和X(X1,X2,X3...)之间存在线性关系。线性回归的目的就是为了确定因变量和自变量的关系程度，换言之，就是求回归模型的参数。
第17页
用户书册
然后，下面给出逻辑回归的一般形式：
P是概率，是某个事件发生的概率，处理类别属性，而且进行了logit变换。也就是说logit(P)与自变量之间存在线性关系，而p显然和X不存在线性关系。
最后，需要进行参数估计。模型有了，需要利用已知的样本来进行参数估计， mahout中用的是随机梯度下降法(SVD)。计算出参数后，就可以利用公式进行预测。
4. 优缺点
优点：
? 可用于概率预测，也可用于分类
? 各feature间不需要满足条件独立假设，但各个feature的贡献是独立计算的。 ? 适用于不同特性值的情况，如特性值为文字，数字等。
? 在训练数据集较小（千万级以下）的情况下比较适用
缺点：
? 仅能用于线性问题。
? mahout对逻辑回归的算法实现是在线的，不支持并行计算，不适合大数据情况
7.2.2 贝叶斯算法
1. 工作原理
朴素贝叶斯分类是一种十分简单的分类算法，它的思想基础是这样的：对于给出的待分类项，求解在此项出现的条件下各个类别出现的概率，哪个最大，就认为此待分类项属于哪个类别。
设每个数据样本用一个n维特征向量来描述n个属性的值，即：X={x1，x2，…，xn}，假定有m个类，分别用C1, C2,…，Cm表示。给定一个未知的数据样本X（即没有类标号），若朴素贝叶斯分类法将未知的样本X分配给类Ci，则一定是
P(Ci|X)>P(Cj|X) 1≤j≤m，j≠i
第18页
用户书册
根据贝叶斯定理
由于P(X)对于所有类为常数，最大化后验概率P(Ci|X)可转化为最大化先验概率P(X|Ci)P(Ci)。如果训练数据集有许多属性和元组，计算P(X|Ci)的开销可能非常大，为此，通常假设各属性的取值互相独立，这样
先验概率P(x1|Ci)，P(x2|Ci)，…，P(xn|Ci)可以从训练数据集求得。
根据此方法，对一个未知类别的样本X，可以先分别计算出X属于每一个类别Ci的概率P(X|Ci)P(Ci)，然后选择其中概率最大的类别作为其类别。
2. 优缺点
优点：
? 适用于训练数据集较大（远远大于逻辑回归）的情况。
? 支持并行计算
缺点：
? 只适用于特性值为文本的情况（如文档分类，垃圾邮件判断等），
? 前提是各属性之间互相独立。当数据集满足这种独立性假设时,分类的准确度较高，
否则可能较低。另外，该算法没有分类规则输出。
7.2.3 SVM（支持向量机）
1. 工作原理
支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力（泛化能力）。它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。
2. 优缺点
优点：
? 不涉及概率测度及大数定律，避开了从归纳到演绎的传统过程,实现了高效的从训
练样本到预报样本的“转导推理”,大大简化了通常的分类和回归等问题
? SVM 的最终决策函数只由少数的支持向量所确定,计算的复杂性取决于支持向量 第19页
用户书册
的数目,而不是样本空间的维数,这在某种意义上避免了“维数灾难”。
? 少数支持向量决定了最终结果,这不但可以帮助我们抓住关键样本、“剔除”大量冗
余样本
? 不需要大量的训练样本，可以解决非线性的问题
缺点：
? SVM算法对大规模训练样本难以实施，由于SVM是借助二次规划来求解支持向
量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大
时该矩阵的存储和计算，将耗费大量的机器内存和运算时间。
? 用SVM解决多分类问题存在困难，经典的支持向量机算法只给出了二类分类的算
法，而在数据挖掘的实际应用中，一般要解决多类的分类问题。可以通过多个二类
支持向量机的组合来解决。
7.2.4 神经网络
1. 工作原理
人工神经网络是由大量的简单基本元件——神经元相互联接而成的自适应非线性动态系统。每个神经元的结构和功能比较简单，但大量神经元组合产生的系统行为却非常复杂。
人工神经网络反映了人脑功能的若干基本特性，但并非生物系统的逼真描述，只是某种模仿、简化和抽象。与数字计算机比较，人工神经网络在构成原理和功能特点等方面更加接近人脑，它不是按给定的程序一步一步地执行运算，而是能够自身适应环境、总结规律、完成某种运算、识别或过程控制。
人工神经网络首先要以一定的学习准则（如果网络做出错误的判决，则通过网络的学习，应使得网络减少下次犯同样错误的可能性。）进行学习，然后才能工作。一般说来，网络中所含的神经元个数越多，则它能记忆、识别的模式也就越多。
2. 优缺点
? 自学习性较强，多用于分类。
? 网络内的神经元按规则相互连接，信息在个神经元内是等势分布的，整个网络都会
参与到对信息的处理，即使有部分神经元失效，网络仍能继续运作，有很强的容错
性和鲁棒性。
? 并行协同处理特性，随着计算机技术的发展，从而可以更快速的进行大量运算。 第20页
用户书册
? 联想式记忆功能，神经网络的运作依赖内部所有神经元之间的相互连接和作用，这
类似于大脑的发散性思维，使网络具有非局限性。
? 自学习、自组织、自适应能力，可以处理位置系统，使网络具有很好的预测功能。 ? 解决优化问题，可以快速找到优化解。通常处理很费时间和需要大量计算的复杂问
题时使用神经网络算法。
7.2.5 HMM (隐马尔科夫模型)
1. 工作原理
HMM实质上就是隐藏了状态的马尔科夫模型，模型状态不能直接可见，只能观察到由状态到符号的映射过程所产生的观察值序列，是一个双重随机过程：一重是马尔科夫模型的概率状态转移过程，另一重是从底层状态到表层观察值的随机过程。它能够解决三个问题
? 评估：对于一个给定的HMM其生成一个给定的观察序列的概率是多少，前向算法
可以有效的解决此问题；
? 解码：什么样的隐藏状态序列最有可能生成一个给定的观察序列，Viterbi算法可以
有效的解决此问题；
? 学习：对于一个给定的观察序列样本，什么样的HMM最可能生成该序列——也就
是确定HMM的参数，这个问题可以使用Baum-Welch或是EM算法解决。
注：mahout中分类器中使用到了HMM，用HMM的评估这部分
2. 优缺点
优点：
? 算法成熟、高效
? 拥有结实的统计学基础
? 模型灵活、通用
缺点：
? 算法训练样本数据大
? 初始值对结果的影响较大
? 马尔科夫的假设在现实中并不一定成立
7.2.6 决策树
1. 工作原理
第21页
用户书册
一般都是自上而下的来生成的。每个决策或事件（即自然状态）都可能引出两个或多个事件，导致不同的结果，把这种决策分支画成图形很像一棵树的枝干，故称决策树。
2. 优缺点
优点：
? 可生成可以理解的规则；
? 计算量相对来说不是很大；
? 可以处理连续和种类字段；
? 决策树可以清晰的显示哪些字段比较重要。
缺点：
? 对连续性的字段比较难预测；
? 对有时间顺序的数据，需要很多预处理的工作；
? 当类别太多时，错误可能就会增加的比较快；
? 一般的算法分类的时候，只是根据一个字段来分类。
第22页