算法简介

‘壹’ 推荐算法简介

在这个时代，无论是信息消费者还是信息生产者都遇到了很大的挑战:作为信息消费者，如何从大量信息中找到自己感兴趣的信息是一件非常困难的事情;作为信息生产者， 如何让自己生产的信息脱颖而出，受到广大用户的关注，也是一件非常困难的事情。推荐系统就是解决这一矛盾的重要工具。推荐系统的任务就是联系用户和信息，一方面帮助用户发现对自己有价值的信息，另一方面让信息能够展现在对它感兴趣的用户面前，从而实现信息消费者和信息 生产者的双赢。和搜索引擎不同的是，推荐系统不需要用户提供明确的需求，而是通过分析用户的历史行为给用 户的兴趣建模，从而主动给用户推荐能够满足他们兴趣和需求的信息 个性化推荐的成功需要两个条件。第一是存在 信息过载 ，因为如果用户可以很容易地从所有物品中找到喜欢的物品，就不需要个性化推荐。第二用 户大部分时候没有特别明确的需求 ，因为用户没有明确的需求，可以直接通过搜索引擎找到感兴趣的物品。

一个完整的推荐系统一般存在3个参与方：用户、物品提供者和提供推荐系统的网站。以图书推荐为例， 首先，推荐系统需要满足用户的需求，给用户推荐那些令他们感兴趣的图书。其次，推荐系统要让各出版社的书都能够被推荐给对其感兴趣的用户，而不是只推荐几个大型出版社的书。最后， 好的推荐系统设计，能够让推荐系统本身收集到高质量的用户反馈，不断完善推荐的质量，增加 用户和网站的交互，提高网站的收入。因此在评测一个推荐算法时，需要同时考虑三方的利益， 一个好的推荐系统是能够令三方共赢的系统。

推荐系统中，主要有3种评测推荐效果的实验方法，即离线实验(offline experiment)、用户调查(user study)和在线实验(online experiment)。

2.1 离线实验

离线实验的方法一般由如下几个步骤构成: (1) 通过日志系统获得用户行为数据，并按照一定格式生成一个标准的数据集; (2) 将数据集按照一定的规则分成训练集和测试集; (3) 在训练集上训练用户兴趣模型，在测试集上进行预测; (4) 通过事先定义的离线指标评测算法在测试集上的预测结果。

从上面的步骤可以看到，推荐系统的离线实验都是在数据集上完成的，也就是说它不需要一个实际的系统来供它实验，而只要有一个从实际系统日志中提取的数据集即可。这种实验方法的 好处是不需要真实用户参与，可以直接快速地计算出来，从而方便、快速地测试大量不同的算法。它的主要缺点是无法获得很多商业上关注的指标，如点击率、转化率等，而找到和商业指标非常相关的离线指标也是很困难的事情

2.2 用户调查

3.3 在线实验

在完成离线实验和必要的用户调查后，可以将推荐系统上线做 AB测试 ，将它和旧的算法进行比较。 AB测试 是一种很常用的在线评测算法的实验方法。它通过一定的规则将用户随机分成几组，并对不同组用户采取不同的算法，然后通过统计不同组用户的各种不同的评测指标比较不同算法的好坏。 AB测试的优点是可以公平获得不同算法实际在线时的性能指标，包括商业上关注的指标。 AB测试的缺点主要是周期比较长，必须进行长期的实验才能得到可靠的结果。因此一般不会用 AB测试测试所有的算法，而只是用它测试那些在离线实验和用户调查中表现很好的算法。其次， 一个大型网站的AB测试系统的设计也是一项复杂的工程。

一般来说，一个新的推荐算法最终上线，需要完成上面所说的3个实验。 1）首先，需要通过离线实验证明它在很多离线指标上优于现有的算法。 2）然后，需要通过用户调查确定它的用户满意度不低于现有的算法。 3）最后，通过在线的AB测试确定它在我们关心的指标上。

本节将介绍各种推荐系统的评测指标。这些评测指标可用于评价推荐系统各方面的性能。这 些指标有些可以定量计算，有些只能定性描述，有些可以通过离线实验计算，有些需要通过用户 调查获得，还有些只能在线评测。

(1) 用户满意度

用户作为推荐系统的重要参与者，其满意度是评测推荐系统的最重要指标。但是，用户满意度没有办法离线计算，只能通过用户调查或者在线实验获得。

在在线系统中，用户满意度主要通过一些 对用户行为的统计得到 。比如在电子商务网站中，用户如果购买了推荐的商品，就表示他们在一定程度上满意。因此，我们可以 利用购买率度量用 户的满意度 。此外，有些网站会通过设计一些用户 反馈界面收集用户满意度 。比如在视频网站中，都有对推荐结果满意或者不满意的 反馈按钮 ，通过统计两种按钮的单击情况就可以度量系统的用户满意度。更一般的情况下，我们可以用 点击率、用户停留时间和转化率等指标度量 用户的满意度。

(2) 预测准确度

预测准确度度量一个推荐系统或者推荐算法预测用户行为的能力。这个指标是最重要的推荐系统离线评测指标

在计算该指标时需要有一个离线的数据集，该数据集包含用户的历史行为记录。然后，将该数据集通过时间分成训练集和测试集。最后，通过在训练集上建立用户的行为和兴趣模型预测用户在测试集上的行为，并计算预测行为和测试集上实际行为的重合度作为预测准确度。 预测准确度指标有分为以下几种：

评分预测：

预测用户对物品评分的行为成为评分预测，在评分预测中，预测准确度一般通过均方根误差RMSE和平均绝对误差MAE计算，对于测试集中的一个用户u和物品i,令[图片上传失败...(image-62a797-1560412790460)] 是用户u对物品i的实际评分，而[图片上传失败...(image-28cfbc-1560412790460)] 是推荐算法给出的预测评分，那么RMSE定义为：

其中T为样本个数

MAE采用绝对值计算预测误差，它的定义为:

TopN推荐

网站在提供推荐服务时，一般是给用户一个个性化的推荐列表，这种推荐叫做TopN推荐。TopN推荐的预测准确率一般通过准确率(precision)/召回率(recall)度量。 令R(u)是根据用户在训练集上的行为给用户作出的推荐列表，而T(u)是用户在测试集上的行为列表。那么，推荐结果的召回率定义为:

推荐结果准确率定义：

(3) 覆盖率

覆盖率（coverage）描述一个推荐系统对物品长尾的发掘能力。覆盖率有不同的定义方法，最简单的定义为推荐系统能够推荐出来的物品占总物品集合的比例。假设系统的用户集合U，推荐系统给每个用户推荐一个长度为N的物品集合R（u）。那么推荐系统的覆盖率可以通过下面的公式计算：

I为总物品数

此外，从上面的定义也可以看到，热门排行榜的推荐覆盖率是很低的，它只会 推荐那些热门的物品，这些物品在总物品中占的比例很小。一个好的推荐系统不仅需要有比较高的用户满意度，也要有较高的覆盖率。

但是上面的定义过于粗略。覆盖率为100%的系统可以有无数的物品流行度分布。为了更细致地描述推荐系统发掘长尾的能力，需要统计推荐列表中不同物品出现次数的分布。如果所有的 物品都出现在推荐列表中，且出现的次数差不多，那么推荐系统发掘长尾的能力就很好。因此， 可以通过研究物品在推荐列表中出现次数的分布描述推荐系统挖掘长尾的能力。如果这个分布比 较平，那么说明推荐系统的覆盖率较高，而如果这个分布较陡峭，说明推荐系统的覆盖率较低。 在信息论和经济学中有两个着名的指标可以用来定义覆盖率。第一个是信息熵:

其中：n代表推荐列表中物品类别个数，p(i)代表每个类别的所占的比率

第二个指标是基尼系数：

(4) 多样性

为了满足用户广泛的兴趣，推荐列表需要能够覆盖用户不同的兴趣领域，即推荐结果需要具有多样性。多样性推荐列表的好处用一句俗话表示就是（不在一棵树上吊死）。尽管用户的兴趣在较长的时间跨度中是一样的。但具体到用户访问推荐系统的某一时刻，其兴趣往往是单一的，那么如果推荐列表只能覆盖用户的一个兴趣点，而这个兴趣点不是用户这个时刻的兴趣点，推荐结果就不会让用户满意。反之如果推荐列表表较多样，覆盖用户绝大多数的兴趣点，那么久会增加用户找到感兴趣物品的概率。因此给用户的推荐列表也需要满足用户广泛的兴趣，即具有多样性。

多样性描述了推荐列表中物品两两之间的不相似性，因此，多样性和相似性是对应的。假设s(i, j) ∈Î[0,1] 定义了物品i和j之间的相似度，那么用户u的推荐列表R(u)的多样性定义如下：

而推荐系统的整体多样性可以定义为所有用户推荐列表多样性的平均值：

(5) 新颖性

新颖的推荐是指给用户推荐那些他们以前没有听说过的物品。在一个网站中 实现新颖性 的最简单办法是，把那些用户之前在网站中对其有过行为的物品从推荐列表中过滤掉。比如在一个视 频网站中，新颖的推荐不应该给用户推荐那些他们已经看过、打过分或者浏览过的视频。 评测新颖度的最简单方法是利用推荐结果的平均流行度，因为越不热门的物品越 可能让用户觉得新颖。因此，如果推荐结果中物品的平均热门程度较低，那么推荐结果就可能有比较高的新颖性。

(6) 惊喜度

惊喜度(serendipity)是最近这几年推荐系统领域最热门的话题。如果推荐结果和用户的历史兴趣不相似，但却让用户觉得满意，那么就可以说推荐结果的惊喜度很高，而推荐的新颖性仅仅取决于用户是否听说过这个推荐结果。提高推荐惊喜度需要提高推荐结果的用户满意度，同时降低推荐结果和用户历史兴趣的相似度。

(7) 信任度

度量推荐系统的信任度只能通过问卷调查的方式，询问用户是否信任推荐系统的推荐结果。 提高推荐系统的信任度主要有两种方法。首先需要增加推荐系统的透明度(transparency)， 而增加推荐系统透明度的主要办法是提供推荐解释。只有让用户了解推荐系统的运行机制，让用 户认同推荐系统的运行机制，才会提高用户对推荐系统的信任度。其次是考虑用户的社交网络 信息，利用用户的好友信息给用户做推荐，并且用好友进行推荐解释。这是因为用户对他们的 好友一般都比较信任，因此如果推荐的商品是好友购买过的，那么他们对推荐结果就会相对比较信任

(8) 实时性

在很多网站中，因为物品(新闻、微博等)具有很强的时效性，所以需要在物品还具有时效 性时就将它们推荐给用户。 推荐系统的实时性包括两个方面。首先，推荐系统需要实时地更新推荐列表来满足用户新的 行为变化。实时性的第二个方面是推荐系统需要能够将新加入系统的物品推荐给用户。这主要考验了推 荐系统处理物品冷启动的能力。

(9) 健壮性

健壮性(即robust,鲁棒 性)指标衡量了一个推荐系统抗击作弊的能力。算法健壮性的评测主要利用模拟攻击。首先，给定一个数据集和一个算法，可以用这个算法 给这个数据集中的用户生成推荐列表。然后，用常用的攻击方法向数据集中注入噪声数据，然后 利用算法在注入噪声后的数据集上再次给用户生成推荐列表。最后，通过比较攻击前后推荐列表 的相似度评测算法的健壮性。如果攻击后的推荐列表相对于攻击前没有发生大的变化，就说明算 法比较健壮

(10) 商业目标

很多时候，网站评测推荐系统更加注重网站的商业目标是否达成，而商业目标和网站的盈利模式是息息相关的

(11) 总结

上一节介绍了很多评测指标，但是在评测系统中还需要考虑评测维度，比如一个推荐算法， 虽然整体性能不好，但可能在某种情况下性能比较好，而增加评测维度的目的就是知道一个算法 在什么情况下性能最好。这样可以为融合不同推荐算法取得最好的整体性能带来参考。

一般来说，评测维度分为如下3种。 1） 用户维度 ：主要包括用户的人口统计学信息、活跃度以及是不是新用户等。 2） 物品维度 ：包括物品的属性信息、流行度、平均分以及是不是新加入的物品等。 3） 时间维度 ：包括季节，是工作日还是周末，是白天还是晚上等。 如果能够在推荐系统评测报告中包含不同维度下的系统评测指标，就能帮我们全面地了解推 荐系统性能，找到一个看上去比较弱的算法的优势，发现一个看上去比较强的算法的缺点。

‘贰’ 几种常用的算法简介

1、穷举法穷举法是最基本的算法设计策略，其思想是列举出问题所有的可能解，逐一进行判别，找出满足条件的解。
穷举法的运用关键在于解决两个问题：
在运用穷举法时，容易出现的问题是可能解过多，导致算法效率很低，这就需要对列举可能解的方法进行优化。
以题1041--纯素数问题为例，从1000到9999都可以看作是可能解，可以通过对所有这些可能解逐一进行判别，找出其中的纯素数，但只要稍作分析，就会发现其实可以大幅度地降低可能解的范围。根据题意易知，个位只可能是3、5、7，再根据题意可知，可以在3、5、7的基础上，先找出所有的二位纯素数，再在二位纯素数基础上找出三位纯素数，最后在三位纯素数的基础上找出所有的四位纯素数。
2、分治法分治法也是应用非常广泛的一种算法设计策略，其思想是将问题分解为若干子问题，从而可以递归地求解各子问题，再综合出问题的解。
分治法的运用关键在于解决三个问题：
我们熟知的如汉诺塔问题、折半查找算法、快速排序算法等都是分治法运用的典型案例。
以题1045--Square
Coins为例，先对题意进行分析，可设一个函数f(m,
n)等于用面值不超过n2的货币构成总值为m的方案数，则容易推导出：
f(m,
n)
=
f(m-0*n*n,
n-1)+f(m-1*n*n,
n-1)+f(m-2*n*n,
n-1)+...+f(m-k*n*n,
n-1)
这里的k是币值为n2的货币最多可以用多少枚，即k=m/(n*n)。
也很容易分析出，f(m,
1)
=
f(1,
n)
=
1
对于这样的题目，一旦分析出了递推公式，程序就非常好写了。所以在动手开始写程序之前，分析工作做得越彻底，逻辑描述越准确、简洁，写起程序来就会越容易。
3、动态规划法
动态规划法多用来计算最优问题，动态规划法与分治法的基本思想是一致的，但处理的手法不同。动态规划法在运用时，要先对问题的分治规律进行分析，找出终结子问题，以及子问题向父问题归纳的规则，而算法则直接从终结子问题开始求解，逐层向上归纳，直到归纳出原问题的解。
动态规划法多用于在分治过程中，子问题可能重复出现的情况，在这种情况下，如果按照常规的分治法，自上向下分治求解，则重复出现的子问题就会被重复地求解，从而增大了冗余计算量，降低了求解效率。而采用动态规划法，自底向上求解，每个子问题只计算一次，就可以避免这种重复的求解了。
动态规划法还有另外一种实现形式，即备忘录法。备忘录的基本思想是设立一个称为备忘录的容器，记录已经求得解的子问题及其解。仍然采用与分治法相同的自上向下分治求解的策略，只是对每一个分解出的子问题，先在备忘录中查找该子问题，如果备忘录中已经存在该子问题，则不须再求解，可以从备忘录中直接得到解，否则，对子问题递归求解，且每求得一个子问题的解，都将子问题及解存入备忘录中。
例如，在题1045--Square
Coins中，可以采用分治法求解，也可以采用动态规划法求解，即从f(m,
1)和f(1,
n)出发，逐层向上计算，直到求得f(m,
n)。
在竞赛中，动态规划和备忘录的思想还可以有另一种用法。有些题目中的可能问题数是有限的，而在一次运行中可能需要计算多个测试用例，可以采用备忘录的方法，预先将所有的问题的解记录下来，然后输入一个测试用例，就查备忘录，直接找到答案输出。这在各问题之间存在父子关系的情况下，会更有效。例如，在题1045--Square
Coins中，题目中已经指出了最大的目标币值不超过300，也就是说问题数只有300个，而且各问题的计算中存在重叠的子问题，可以采用动态规划法，将所有问题的解先全部计算出来，再依次输入测试用例数据，并直接输出答案。
4、回溯法回溯法是基于问题状态树搜索的求解法，其可适用范围很广。从某种角度上说，可以把回溯法看作是优化了的穷举法。回溯法的基本思想是逐步构造问题的可能解，一边构造，一边用约束条件进行判别，一旦发现已经不可能构造出满足条件的解了，则退回上一步构造过程，重新进行构造。这个退回的过程，就称之为回溯。
回溯法在运用时，要解决的关键问题在于：
回溯法的经典案例也很多，例如全排列问题、N后问题等。
5、贪心法贪心法也是求解最优问题的常用算法策略，利用贪心法策略所设计的算法，通常效率较高，算法简单。贪心法的基本思想是对问题做出目前看来最好的选择，即贪心选择，并使问题转化为规模更小的子问题。如此迭代，直到子问题可以直接求解。
基于贪心法的经典算法例如：哈夫曼算法、最小生成树算法、最短路径算法等。

‘叁’ 推荐算法简介

写在最前面：本文内容主要来自于书籍《推荐系统实践》和《推荐系统与深度学习》。

推荐系统是目前互联网世界最常见的智能产品形式。从电子商务、音乐视频网站，到作为互联网经济支柱的在线广告和新颖的在线应用推荐，到处都有推荐系统的身影。推荐算法是推荐系统的核心，其本质是通过一定的方式将用户和物品联系起来，而不同的推荐系统利用了不同的方式。

推荐系统的主要功能是以个性化的方式帮助用户从极大的搜索空间中快速找到感兴趣的对象。因此，目前所用的推荐系统多为个性化推荐系统。个性化推荐的成功应用需要两个条件：

在推荐系统的众多算法中，基于协同的推荐和基于内容的推荐在实践中得到了最广泛的应用。本文也将从这两种算法开始，结合时间、地点上下文环境以及社交环境，对常见的推荐算法做一个简单的介绍。

基于内容的算法的本质是对物品内容进行分析，从中提取特征，然后基于用户对何种特征感兴趣来推荐含有用户感兴趣特征的物品。因此，基于内容的推荐算法有两个最基本的要求：

下面我们以一个简单的电影推荐来介绍基于内容的推荐算法。

现在有两个用户A、B和他们看过的电影以及打分情况如下：

其中问好（?）表示用户未看过。用户A对《银河护卫队 》《变形金刚》《星际迷航》三部科幻电影都有评分，平均分为 4 .7 分 （ (5+4+5 ) / 3=4.7 ）；对《三生三世》《美人鱼》《北京遇上西雅图》三部爱情电影评分平均分为 2.3 分 （ ( 3十2+2 ) /3=2.3 ）。现在需要给A推荐电影，很明显A更倾向于科幻电影，因此推荐系统会给A推荐独立日。而对于用户B，通过简单的计算我们可以知道更喜欢爱情电影，因此给其推荐《三生三世》。当然，在实际推荐系统中，预测打分比这更加复杂些，但是其原理是一样的。

现在，我们可以将基于内容的推荐归纳为以下四个步骤：

通过上面四步就能快速构建一个简单的推荐系统。基于内容的推荐系统通常简单有效，可解释性好，没有物品冷启动问题。但他也有两个明显的缺点：

最后，顺便提一下特征提取方法：对于某些特征较为明确的物品，一般可以直接对其打标签，如电影类别。而对于文本类别的特征，则主要是其主题情感等，则些可以通过tf-idf或LDA等方法得到。

基于协同的算法在很多地方也叫基于邻域的算法，主要可分为两种：基于用户的协同算法和基于物品的协同算法。

啤酒和尿布的故事在数据挖掘领域十分有名，该故事讲述了美国沃尔玛超市统计发现啤酒和尿布一起被购买的次数非常多，因此将啤酒和尿布摆在了一起，最后啤酒和尿布的销量双双增加了。这便是一个典型的物品协同过滤的例子。

基于物品的协同过滤指基于物品的行为相似度（如啤酒尿布被同时购买）来进行物品推荐。该算法认为，物品A和物品B具有很大相似度是因为喜欢物品A的用户大都也喜欢物品B。

基于物品的协同过滤算法主要分为两步：

基于物品的协同过滤算法中计算物品相似度的方法有以下几种：
（1）基于共同喜欢物品的用户列表计算。

此外，John S. Breese再其论文中还提及了IUF（Inverse User Frequence，逆用户活跃度）的参数，其认为活跃用户对物品相似度的贡献应该小于不活跃的用户，应该增加IUF参数来修正物品相似度的公式：

上面的公式只是对活跃用户做了一种软性的惩罚， 但对于很多过于活跃的用户， 比如某位买了当当网80%图书的用户， 为了避免相似度矩阵过于稠密， 我们在实际计算中一般直接忽略他的兴趣列表， 而不将其纳入到相似度计算的数据集中。

（2）基于余弦相似度计算。

（3）热门物品的惩罚。
从上面（1）的相似度计算公式中，我们可以发现当物品 i 被更多人购买时，分子中的 N(i) ∩ N(j) 和分母中的 N(i) 都会增长。对于热门物品，分子 N(i) ∩ N(j) 的增长速度往往高于 N(i)，这就会使得物品 i 和很多其他的物品相似度都偏高，这就是 ItemCF 中的物品热门问题。推荐结果过于热门，会使得个性化感知下降。以歌曲相似度为例，大部分用户都会收藏《小苹果》这些热门歌曲，从而导致《小苹果》出现在很多的相似歌曲中。为了解决这个问题，我们对于物品 i 进行惩罚，例如下式， 当α∈(0, 0.5) 时，N(i) 越小，惩罚得越厉害，从而使热门物品相关性分数下降（ 博主注：这部分未充分理解 ）：

此外，Kary pis在研究中发现如果将ItemCF的相似度矩阵按最大值归一化， 可以提高推荐的准确率。 其研究表明， 如果已经得到了物品相似度矩阵w， 那么可以用如下公式得到归一化之后的相似度矩阵w'：

归一化的好处不仅仅在于增加推荐的准确度，它还可以提高推荐的覆盖率和多样性。一般来说，物品总是属于很多不同的类，每一类中的物品联系比较紧密。假设物品分为两类——A和B， A类物品之间的相似度为0.5， B类物品之间的相似度为0.6， 而A类物品和B类物品之间的相似度是0.2。 在这种情况下， 如果一个用户喜欢了5个A类物品和5个B类物品， 用ItemCF给他进行推荐， 推荐的就都是B类物品， 因为B类物品之间的相似度大。 但如果归一化之后， A类物品之间的相似度变成了1， B类物品之间的相似度也是1， 那么这种情况下， 用户如果喜欢5个A类物品和5个B类物品， 那么他的推荐列表中A类物品和B类物品的数目也应该是大致相等的。 从这个例子可以看出， 相似度的归一化可以提高推荐的多样性。

那么，对于两个不同的类，什么样的类其类内物品之间的相似度高，什么样的类其类内物品相似度低呢？一般来说，热门的类其类内物品相似度一般比较大。如果不进行归一化，就会推荐比较热门的类里面的物品，而这些物品也是比较热门的。因此，推荐的覆盖率就比较低。相反，如果进行相似度的归一化，则可以提高推荐系统的覆盖率。

最后，利用物品相似度矩阵和用户打过分的物品记录就可以对一个用户进行推荐评分：

基于用户的协同算法与基于物品的协同算法原理类似，只不过基于物品的协同是用户U购买了A物品，会计算经常有哪些物品与A一起购买（也即相似度），然后推荐给用户U这些与A相似的物品。而基于用户的协同则是先计算用户的相似性（通过计算这些用户购买过的相同的物品），然后将这些相似用户购买过的物品推荐给用户U。

基于用户的协同过滤算法主要包括两个步骤：

步骤（1）的关键是计算用户的兴趣相似度，主要是利用用户的行为相似度计算用户相似度。给定用户 u 和 v，N(u) 表示用户u曾经有过正反馈（譬如购买）的物品集合，N(v) 表示用户 v 曾经有过正反馈的物品集合。那么我们可以通过如下的 Jaccard 公式简单的计算 u 和 v 的相似度：

或通过余弦相似度：

得到用户之间的相似度之后，UserCF算法会给用户推荐和他兴趣最相似的K个用户喜欢的物品。如下的公式度量了UserCF算法中用户 u 对物品 i 的感兴趣程度：

首先回顾一下UserCF算法和ItemCF算法的推荐原理：UserCF给用户推荐那些和他有共同兴趣爱好的用户喜欢的物品， 而ItemCF给用户推荐那些和他之前喜欢的物品具有类似行为的物品。

（1）从推荐场景考虑
首先从场景来看，如果用户数量远远超过物品数量，如购物网站淘宝，那么可以考虑ItemCF，因为维护一个非常大的用户关系网是不容易的。其次，物品数据一般较为稳定，因此物品相似度矩阵不必频繁更新，维护代价较小。

UserCF的推荐结果着重于反应和用户兴趣相似的小群体的热点，而ItemCF的推荐结果着重于维系用户的历史兴趣。换句话说，UserCF的推荐更社会化，反应了用户所在小型兴趣群体中物品的热门程度，而ItemCF的推荐更加个性化，反应了用户自己的个性传承。因此UserCF更适合新闻、微博或微内容的推荐，而且新闻内容更新频率非常高，想要维护这样一个非常大而且更新频繁的表无疑是非常难的。

在新闻类网站中，用户的兴趣爱好往往比较粗粒度，很少会有用户说只看某个话题的新闻，而且往往某个话题也不是每天都会有新闻。 个性化新闻推荐更强调新闻热点，热门程度和时效性是个性化新闻推荐的重点，个性化是补充，所以 UserCF 给用户推荐和他有相同兴趣爱好的人关注的新闻，这样在保证了热点和时效性的同时，兼顾了个性化。

（2）从系统多样性（也称覆盖率，指一个推荐系统能否给用户提供多种选择）方面来看，ItemCF的多样性要远远好于UserCF，因为UserCF更倾向于推荐热门物品。而ItemCF具有较好的新颖性，能够发现长尾物品。所以大多数情况下，ItemCF在精度上较小于UserCF，但其在覆盖率和新颖性上面却比UserCF要好很多。

在介绍本节基于矩阵分解的隐语义模型之前，让我们先来回顾一下传统的矩阵分解方法SVD在推荐系统的应用吧。

基于SVD矩阵分解在推荐中的应用可分为如下几步：

SVD在计算前会先把评分矩阵 A 缺失值补全，补全之后稀疏矩阵 A 表示成稠密矩阵，然后将分解成 A' = U∑V T 。但是这种方法有两个缺点：（1）补成稠密矩阵后需要耗费巨大的储存空间，对这样巨大的稠密矩阵进行储存是不现实的；（2）SVD的计算复杂度很高，对这样大的稠密矩阵中进行计算式不现实的。因此，隐语义模型就被发明了出来。

更详细的SVD在推荐系统的应用可参考 奇异值分解SVD简介及其在推荐系统中的简单应用 。

隐语义模型（Latent Factor Model）最早在文本挖掘领域被提出，用于找到文本的隐含语义。相关的算法有LSI，pLSA，LDA和Topic Model。本节将对隐语义模型在Top-N推荐中的应用进行详细介绍，并通过实际的数据评测该模型。

隐语义模型的核心思想是通过隐含特征联系用户兴趣和物品。让我们通过一个例子来理解一下这个模型。

现有两个用户，用户A的兴趣涉及侦探小说、科普图书以及一些计算机技术书，而用户B的兴趣比较集中在数学和机器学习方面。那么如何给A和B推荐图书呢？

我们可以对书和物品的兴趣进行分类。对于某个用户，首先得到他的兴趣分类，然后从分类中挑选他可能喜欢的物品。简言之，这个基于兴趣分类的方法大概需要解决3个问题：

对于第一个问题的简单解决方案是找相关专业人员给物品分类。以图书为例，每本书出版时，编辑都会给出一个分类。但是，即使有很系统的分类体系，编辑给出的分类仍然具有以下缺点：（1）编辑的意见不能代表各种用户的意见；（2）编辑很难控制分类的细粒度；（3）编辑很难给一个物品多个分类；（4）编辑很难给一个物品多个分类；（5）编辑很难给出多个维度的分类；（6）编辑很难决定一个物品在某一个类别中的权重。

为了解决上述问题，研究员提出可以从数据出发，自动找到那些分类，然后进行个性化推荐。隐语义模型由于采用基于用户行为统计的自动聚类，较好地解决了上面提出的5个问题。

LFM将矩阵分解成2个而不是3个：

推荐系统中用户和物品的交互数据分为显性反馈和隐性反馈数据。隐式模型中多了一个置信参数，具体涉及到ALS（交替最小二乘法，Alternating Least Squares）中对于隐式反馈模型的处理方式——有的文章称为“加权的正则化矩阵分解”：

一个小细节：在隐性反馈数据集中，只有正样本（正反馈）没有负反馈（负样本），因此如何给用户生成负样本来进行训练是一个重要的问题。Rong Pan在其文章中对此进行了探讨，对比了如下几种方法：

用户行为很容易用二分图表示，因此很多图算法都可以应用到推荐系统中。基于图的模型（graph-based model）是推荐系统中的重要内容。很多研究人员把基于领域的模型也称为基于图的模型，因为可以把基于领域的模型看作基于图的模型的简单形式。

在研究基于图的模型之前，需要将用户行为数据表示成图的形式。本节的数据是由一系列用户物品二元组 (u, i) 组成的，其中 u 表示用户对物品 i 产生过行为。

令 G(V, E) 表示用户物品二分图，其中 V=V U UV I 由用户顶点 V U 和物品节点 V I 组成。对于数据集中每一个二元组 (u, i) ，图中都有一套对应的边 e(v u , v i )，其中 v u ∈V U 是用户对应的顶点，v i ∈V I 是物品i对应的顶点。如下图是一个简单的物品二分图，其中圆形节点代表用户，方形节点代表物品，用户物品的直接连线代表用户对物品产生过行为。比如下图中的用户A对物品a、b、d产生过行为。

度量图中两个顶点之间相关性的方法很多，但一般来说图中顶点的相关性主要取决于下面3个因素：

而相关性高的一对顶点一般具有如下特征：

举个例子，如下图，用户A和物品c、e没有边直连，但A可通过一条长度为3的路径到达c，而Ae之间有两条长度为3的路径。那么A和e的相关性要高于顶点A和c，因而物品e在用户A的推荐列表中应该排在物品c之前，因为Ae之间有两条路径。其中，（A,b,C,e）路径经过的顶点的出度为（3，2，2，2），而 (A,d,D,e) 路径经过了一个出度比较大的顶点D，所以 (A,d,D,e) 对顶点A与e之间相关性的贡献要小于（A,b,C,e）。

基于上面3个主要因素，研究人员设计了很多计算图中顶点相关性的方法，本节将介绍一种基于随机游走的PersonalRank算法。

假设要给用户u进行个性化推荐，可以从用户u对应的节点 v u 开始在用户物品二分图上进行随机游走。游走到任一节点时，首先按照概率α决定是继续游走还是停止这次游走并从 v u 节点重新开始游走。若决定继续游走，则从当前节点指向的节点中按照均匀分布随机选择一个节点作为游走下次经过的节点。这样，经过很多次随机游走后，每个物品被访问到的概率会收敛到一个数。最终的推荐列表中物品的权重就是物品节点的访问概率。

上述算法可以表示成下面的公式：

虽然通过随机游走可以很好地在理论上解释PersonalRank算法，但是该算法在时间复杂度上有明显的缺点。因为在为每个用户进行推荐时，都需要在整个用户物品二分图上进行迭代，知道所有顶点的PR值都收敛。这一过程的时间复杂度非常高，不仅无法在线进行实时推荐，离线计算也是非常耗时的。

有两种方法可以解决上面PersonalRank时间复杂度高的问题：
（1）减少迭代次数，在收敛之前停止迭代。但是这样会影响最终的精度。

（2）从矩阵论出发，重新涉及算法。另M为用户物品二分图的转移概率矩阵，即：

网络社交是当今社会非常重要甚至可以说是必不可少的社交方式，用户在互联网上的时间有相当大的一部分都用在了社交网络上。

当前国外最着名的社交网站是Facebook和Twitter，国内的代表则是微信/QQ和微博。这些社交网站可以分为两类：

需要指出的是，任何一个社交网站都不是单纯的社交图谱或兴趣图谱。如QQ上有些兴趣爱好群可以认识不同的陌生人，而微博中的好友也可以是现实中认识的。

社交网络定义了用户之间的联系，因此可以用图定义社交网络。我们用图 G(V,E,w) 定义一个社交网络，其中V是顶点集合，每个顶点代表一个用户，E是边集合，如果用户va和vb有社交网络关系，那么就有一条边 e(v a , v b ) 连接这两个用户，而 w(v a , v b )定义了边的权重。一般来说，有三种不同的社交网络数据：

和一般购物网站中的用户活跃度分布和物品流行度分布类似，社交网络中用户的入度（in degree，表示有多少人关注）和出度（out degree，表示关注多少人）的分布也是满足长尾分布的。即大部分人关注的人都很少，被关注很多的人也很少。

给定一个社交网络和一份用户行为数据集。其中社交网络定义了用户之间的好友关系，而用户行为数据集定义了不同用户的历史行为和兴趣数据。那么最简单的算法就是给用户推荐好友喜欢的物品集合。即用户u对物品i的兴趣 p ui 可以通过如下公式计算。

用户u和用户v的熟悉程度描述了用户u和用户在现实社会中的熟悉程度。一般来说，用户更加相信自己熟悉的好友的推荐，因此我们需要考虑用户之间的熟悉度。下面介绍3中衡量用户熟悉程度的方法。

（1）对于用户u和用户v，可以使用共同好友比例来计算他们的相似度：

上式中 out(u) 可以理解为用户u关注的用户合集，因此 out(u) ∩ out(v) 定义了用户u、v共同关注的用户集合。

（2）使用被关注的用户数量来计算用户之间的相似度，只要将公式中的 out(u) 修改为 in(u)：

in(u) 是指关注用户u的集合。在无向社交网络中，in(u)和out(u)是相同的，而在微博这种有向社交网络中，这两个集合的含义就不痛了。一般来说，本方法适合用来计算微博大V之间的相似度，因为大v往往被关注的人数比较多；而方法（1）适用于计算普通用户之间的相似度，因为普通用户往往关注行为比较丰富。

（3）除此之外，还可以定义第三种有向的相似度：这个相似度的含义是用户u关注的用户中，有多大比例也关注了用户v：

这个相似度有一个缺点，就是在该相似度下所有人都和大v有很大的相似度，这是因为公式中的分母并没有考虑 in(v) 的大小，所以可以把 in(v) 加入到上面公式的分母，来降低大v与其他用户的相似度：

上面介绍了3种计算用户之间相似度（或称熟悉度）的计算方法。除了熟悉程度，还需要考虑用户之间的兴趣相似度。我们和父母很熟悉，但很多时候我们和父母的兴趣确不相似，因此也不会喜欢他们喜欢的物品。因此，在度量用户相似度时，还需要考虑兴趣相似度，而兴趣相似度可以通过和UserCF类似的方法度量，即如果两个用户喜欢的物品集合重合度很高，两个用户的兴趣相似度很高。

最后，我们可以通过加权的形式将两种权重合并起来，便得到了各个好有用户的权重了。

有了权重，我们便可以针对用户u挑选k个最相似的用户，把他们购买过的物品中，u未购买过的物品推荐给用户u即可。打分公式如下：

其中 w' 是合并后的权重，score是用户v对物品的打分。

node2vec的整体思路分为两个步骤：第一个步骤是随机游走（random walk），即通过一定规则随机抽取一些点的序列；第二个步骤是将点的序列输入至word2vec模型从而得到每个点的embedding向量。

随机游走在前面基于图的模型中已经介绍过，其主要分为两步：（1）选择起始节点；（2）选择下一节点。起始节点选择有两种方法：按一定规则抽取一定量的节点或者以图中所有节点作为起始节点。一般来说会选择后一种方法以保证所有节点都会被选取到。

在选择下一节点方法上，最简单的是按边的权重来选择，但在实际应用中需要通过广度优先还是深度优先的方法来控制游走范围。一般来说，深度优先发现能力更强，广度优先更能使社区内（较相似）的节点出现在一个路径里。

斯坦福大学Jure Leskovec教授给出了一种可以控制广度优先或者深度优先的方法。

以上图为例，假设第一步是从t随机游走到v，这时候我们要确定下一步的邻接节点。本例中，作者定义了p和q两个参数变量来调节游走，首先计算其邻居节点与上一节点t的距离d，根据下面的公式得到α：

一般从每个节点开始游走5~10次，步长则根据点的数量N游走根号N步。如此便可通过random walk生成点的序列样本。

得到序列之后，便可以通过word2vec的方式训练得到各个用户的特征向量，通过余弦相似度便可以计算各个用户的相似度了。有了相似度，便可以使用基于用户的推荐算法了。

推荐系统需要根据用户的历史行为和兴趣预测用户未来的行为和兴趣，因此大量的用户行为数据就成为推荐系统的重要组成部分和先决条件。如何在没有大量用户数据的情况下设计个性化推荐系统并且让用户对推荐结果满意从而愿意使用推荐系统，就是冷启动问题。

冷启动问题主要分为三类：

针对用户冷启动，下面给出一些简要的方案：
（1）有效利用账户信息。利用用户注册时提供的年龄、性别等数据做粗粒度的个性化；
（2）利用用户的社交网络账号登录（需要用户授权），导入用户在社交网站上的好友信息，然后给用户推荐其好友喜欢的物品；
（3）要求用户在登录时对一些物品进行反馈，手机用户对这些物品的兴趣信息，然后给用推荐那些和这些物品相似的物品；
（4）提供非个性化推荐。非个性化推荐的最简单例子就是热门排行榜，我们可以给用户推荐热门排行榜，然后等到用户数据收集到一定的时候，在切换为个性化推荐。

对于物品冷启动，可以利用新加入物品的内容信息，将它们推荐给喜欢过和他们相似的物品的用户。

对于系统冷启动，可以引入专家知识，通过一定高效的方式快速建立起物品的相关度表。

在上面介绍了一些推荐系统的基础算法知识，这些算法大都是比较经典且现在还在使用的。但是需要注意的是，在实践中，任何一种推荐算法都不是单独使用的，而是将多种推荐算法结合起来，也就是混合推荐系统，但是在这里并不准备介绍，感兴趣的可以查阅《推荐系统》或《推荐系统与深度学习》等书籍。此外，在推荐中非常重要的点击率模型以及基于矩阵的一些排序算法在这里并没有提及，感兴趣的也可自行学习。

虽然现在用的很多算法都是基于深度学习的，但是这些经典算法能够让我们对推荐系统的发展有一个比较好的理解，同时，更重要的一点——“推陈出新”，只有掌握了这些经典的算法，才能提出或理解现在的一些更好地算法。

‘肆’ Kmeans聚类算法简介（有点枯燥）

1. Kmeans聚类算法简介

由于具有出色的速度和良好的可扩展性，Kmeans聚类算法算得上是最着名的聚类方法。Kmeans算法是一个重复移动类中心点的过程，把类的中心点，也称重心(centroids)，移动到其包含成员的平均位置，然后重新划分其内部成员。k是算法计算出的超参数，表示类的数量；Kmeans可以自动分配样本到不同的类，但是不能决定究竟要分几个类。k必须是一个比训练集样本数小的正整数。有时，类的数量是由问题内容指定的。例如，一个鞋厂有三种新款式，它想知道每种新款式都有哪些潜在客户，于是它调研客户，然后从数据里找出三类。也有一些问题没有指定聚类的数量，最优的聚类数量是不确定的。后面我将会详细介绍一些方法来估计最优聚类数量。

Kmeans的参数是类的重心位置和其内部观测值的位置。与广义线性模型和决策树类似，Kmeans参数的最优解也是以成本函数最小化为目标。Kmeans成本函数公式如下：

μiμi是第kk个类的重心位置。成本函数是各个类畸变程度(distortions)之和。每个类的畸变程度等于该类重心与其内部成员位置距离的平方和。若类内部的成员彼此间越紧凑则类的畸变程度越小，反之，若类内部的成员彼此间越分散则类的畸变程度越大。求解成本函数最小化的参数就是一个重复配置每个类包含的观测值，并不断移动类重心的过程。首先，类的重心是随机确定的位置。实际上，重心位置等于随机选择的观测值的位置。每次迭代的时候，Kmeans会把观测值分配到离它们最近的类，然后把重心移动到该类全部成员位置的平均值那里。

2. K值的确定

2.1 根据问题内容确定

这种方法就不多讲了，文章开篇就举了一个例子。

2.2 肘部法则

如果问题中没有指定kk的值，可以通过肘部法则这一技术来估计聚类数量。肘部法则会把不同kk值的成本函数值画出来。随着kk值的增大，平均畸变程度会减小；每个类包含的样本数会减少，于是样本离其重心会更近。但是，随着kk值继续增大，平均畸变程度的改善效果会不断减低。kk值增大过程中，畸变程度的改善效果下降幅度最大的位置对应的kk值就是肘部。为了让读者看的更加明白，下面让我们通过一张图用肘部法则来确定最佳的kk值。下图数据明显可分成两类：

从图中可以看出，k值从1到2时，平均畸变程度变化最大。超过2以后，平均畸变程度变化显着降低。因此最佳的k是2。

2.3 与层次聚类结合

经常会产生较好的聚类结果的一个有趣策略是，首先采用层次凝聚算法决定结果粗的数目，并找到一个初始聚类，然后用迭代重定位来改进该聚类。

2.4 稳定性方法

稳定性方法对一个数据集进行2次重采样产生2个数据子集，再用相同的聚类算法对2个数据子集进行聚类，产生2个具有kk个聚类的聚类结果，计算2个聚类结果的相似度的分布情况。2个聚类结果具有高的相似度说明kk个聚类反映了稳定的聚类结构，其相似度可以用来估计聚类个数。采用次方法试探多个kk，找到合适的k值。

2.5 系统演化方法

系统演化方法将一个数据集视为伪热力学系统，当数据集被划分为kk个聚类时称系统处于状态kk。系统由初始状态k=1k=1出发，经过分裂过程和合并过程，系统将演化到它的稳定平衡状态 kiki ，其所对应的聚类结构决定了最优类数 kiki 。系统演化方法能提供关于所有聚类之间的相对边界距离或可分程度，它适用于明显分离的聚类结构和轻微重叠的聚类结构。

2.6 使用canopy算法进行初始划分

基于Canopy Method的聚类算法将聚类过程分为两个阶段

(1) 聚类最耗费计算的地方是计算对象相似性的时候，Canopy Method在第一阶段选择简单、计算代价较低的方法计算对象相似性，将相似的对象放在一个子集中，这个子集被叫做Canopy，通过一系列计算得到若干Canopy，Canopy之间可以是重叠的，但不会存在某个对象不属于任何Canopy的情况，可以把这一阶段看做数据预处理；

(2) 在各个Canopy内使用传统的聚类方法(如Kmeans)，不属于同一Canopy的对象之间不进行相似性计算。

从这个方法起码可以看出两点好处：首先，Canopy不要太大且Canopy之间重叠的不要太多的话会大大减少后续需要计算相似性的对象的个数；其次，类似于Kmeans这样的聚类方法是需要人为指出K的值的，通过(1)得到的Canopy个数完全可以作为这个k值，一定程度上减少了选择k的盲目性。

其他方法如贝叶斯信息准则方法(BIC)可参看文献[4]。

3. 初始质心的选取

选择适当的初始质心是基本kmeans算法的关键步骤。常见的方法是随机的选取初始中心，但是这样簇的质量常常很差。处理选取初始质心问题的一种常用技术是：多次运行，每次使用一组不同的随机初始质心，然后选取具有最小SSE(误差的平方和)的簇集。这种策略简单，但是效果可能不好，这取决于数据集和寻找的簇的个数。

第二种有效的方法是，取一个样本，并使用层次聚类技术对它聚类。从层次聚类中提取kk个簇，并用这些簇的质心作为初始质心。该方法通常很有效，但仅对下列情况有效：(1)样本相对较小，例如数百到数千(层次聚类开销较大)；(2) kk相对于样本大小较小。

第三种选择初始质心的方法，随机地选择第一个点，或取所有点的质心作为第一个点。然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点。使用这种方法，确保了选择的初始质心不仅是随机的，而且是散开的。但是，这种方法可能选中离群点。此外，求离当前初始质心集最远的点开销也非常大。为了克服这个问题，通常该方法用于点样本。由于离群点很少(多了就不是离群点了)，它们多半不会在随机样本中出现。计算量也大幅减少。

第四种方法就是上面提到的canopy算法。

4. 距离的度量

常用的距离度量方法包括：欧几里得距离和余弦相似度。两者都是评定个体间差异的大小的。

欧氏距离是最常见的距离度量，而余弦相似度则是最常见的相似度度量，很多的距离度量和相似度度量都是基于这两者的变形和衍生，所以下面重点比较下两者在衡量个体差异时实现方式和应用环境上的区别。

借助三维坐标系来看下欧氏距离和余弦相似度的区别：

从图上可以看出距离度量衡量的是空间各点间的绝对距离，跟各个点所在的位置坐标(即个体特征维度的数值)直接相关；而余弦相似度衡量的是空间向量的夹角，更加的是体现在方向上的差异，而不是位置。如果保持A点的位置不变，B点朝原方向远离坐标轴原点，那么这个时候余弦相似cosθ是保持不变的，因为夹角不变，而A、B两点的距离显然在发生改变，这就是欧氏距离和余弦相似度的不同之处。

根据欧氏距离和余弦相似度各自的计算方式和衡量特征，分别适用于不同的数据分析模型：欧氏距离能够体现个体数值特征的绝对差异，所以更多的用于需要从维度的数值大小中体现差异的分析，如使用用户行为指标分析用户价值的相似度或差异；而余弦相似度更多的是从方向上区分差异，而对绝对的数值不敏感，更多的用于使用用户对内容评分来区分用户兴趣的相似度和差异，同时修正了用户间可能存在的度量标准不统一的问题(因为余弦相似度对绝对数值不敏感)。

因为欧几里得距离度量会受指标不同单位刻度的影响，所以一般需要先进行标准化，同时距离越大，个体间差异越大；空间向量余弦夹角的相似度度量不会受指标刻度的影响，余弦值落于区间[-1,1]，值越大，差异越小。但是针对具体应用，什么情况下使用欧氏距离，什么情况下使用余弦相似度？

从几何意义上来说，n维向量空间的一条线段作为底边和原点组成的三角形，其顶角大小是不确定的。也就是说对于两条空间向量，即使两点距离一定，他们的夹角余弦值也可以随意变化。感性的认识，当两用户评分趋势一致时，但是评分值差距很大，余弦相似度倾向给出更优解。举个极端的例子，两用户只对两件商品评分，向量分别为(3,3)和(5,5)，这两位用户的认知其实是一样的，但是欧式距离给出的解显然没有余弦值合理。

5. 聚类效果评估

我们把机器学习定义为对系统的设计和学习，通过对经验数据的学习，将任务效果的不断改善作为一个度量标准。Kmeans是一种非监督学习，没有标签和其他信息来比较聚类结果。但是，我们还是有一些指标可以评估算法的性能。我们已经介绍过类的畸变程度的度量方法。本节为将介绍另一种聚类算法效果评估方法称为轮廓系数(Silhouette Coefficient)。轮廓系数是类的密集与分散程度的评价指标。它会随着类的规模增大而增大。彼此相距很远，本身很密集的类，其轮廓系数较大，彼此集中，本身很大的类，其轮廓系数较小。轮廓系数是通过所有样本计算出来的，计算每个样本分数的均值，计算公式如下：

aa是每一个类中样本彼此距离的均值，bb是一个类中样本与其最近的那个类的所有样本的距离的均值。

6. Kmeans算法流程

输入：聚类个数k，数据集XmxnXmxn。 

输出：满足方差最小标准的k个聚类。

(1) 选择k个初始中心点，例如c[0]=X[0] , … , c[k-1]=X[k-1]；

(2) 对于X[0]….X[n]，分别与c[0]…c[k-1]比较，假定与c[i]差值最少，就标记为i；

(3) 对于所有标记为i点，重新计算c[i]={ 所有标记为i的样本的每个特征的均值}；

(4) 重复(2)(3)，直到所有c[i]值的变化小于给定阈值或者达到最大迭代次数。

Kmeans的时间复杂度：O(tkmn)，空间复杂度：O((m+k)n)。其中，t为迭代次数，k为簇的数目，m为样本数，n为特征数。

7. Kmeans算法优缺点

7.1 优点

(1). 算法原理简单。需要调节的超参数就是一个k。

(2). 由具有出色的速度和良好的可扩展性。

7.2 缺点

(1). 在 Kmeans 算法中 kk 需要事先确定，这个 kk 值的选定有时候是比较难确定。

(2). 在 Kmeans 算法中，首先需要初始k个聚类中心，然后以此来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果。多设置一些不同的初值，对比最后的运算结果，一直到结果趋于稳定结束。

(3). 该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。

(4). 对离群点很敏感。

(5). 从数据表示角度来说，在 Kmeans 中,我们用单个点来对 cluster 进行建模，这实际上是一种最简化的数据建模形式。这种用点来对 cluster 进行建模实际上就已经假设了各 cluster的数据是呈圆形(或者高维球形)或者方形等分布的。不能发现非凸形状的簇。但在实际生活中，很少能有这种情况。所以在 GMM 中，使用了一种更加一般的数据表示，也就是高斯分布。

(6). 从数据先验的角度来说，在 Kmeans 中,我们假设各个 cluster 的先验概率是一样的,但是各个 cluster 的数据量可能是不均匀的。举个例子,cluster A 中包含了10000个样本,cluster B 中只包含了100个。那么对于一个新的样本,在不考虑其与A cluster、 B cluster 相似度的情况,其属于 cluster A 的概率肯定是要大于 cluster B的。

(7). 在 Kmeans 中，通常采用欧氏距离来衡量样本与各个 cluster 的相似度。这种距离实际上假设了数据的各个维度对于相似度的衡量作用是一样的。但在 GMM 中，相似度的衡量使用的是后验概率 αcG(x|μc,∑c)αcG(x|μc,∑c) ，通过引入协方差矩阵,我们就可以对各维度数据的不同重要性进行建模。

(8). 在 Kmeans 中，各个样本点只属于与其相似度最高的那个 cluster ，这实际上是一种 hard clustering 。

针对Kmeans算法的缺点，很多前辈提出了一些改进的算法。例如 K-modes 算法，实现对离散数据的快速聚类，保留了Kmeans算法的效率同时将Kmeans的应用范围扩大到离散数据。还有K-Prototype算法，可以对离散与数值属性两种混合的数据进行聚类，在K-prototype中定义了一个对数值与离散属性都计算的相异性度量标准。当然还有其它的一些算法，这里我 就不一一列举了。

Kmeans 与 GMM 更像是一种 top-down 的思想，它们首先要解决的问题是，确定 cluster 数量，也就是 k 的取值。在确定了 k 后,再来进行数据的聚类。而 hierarchical clustering 则是一种 bottom-up 的形式，先有数据，然后通过不断选取最相似的数据进行聚类。

‘伍’ ECC 算法简介

与 RSA（Ron Rivest，Adi Shamir，Len Adleman 三位天才的名字）一样，ECC（Elliptic Curves Cryptography，椭圆曲线加密）也属于公开密钥算法。

一、从平行线谈起

平行线，永不相交。没有人怀疑把：）不过到了近代这个结论遭到了质疑。平行线会不会在很远很远的地方相交了？事实上没有人见到过。所以“平行线，永不相交”只是假设（大家想想初中学习的平行公理，是没有证明的）。

既然可以假设平行线永不相交，也可以假设平行线在很远很远的地方相交了。即平行线相交于无穷远点P∞（请大家闭上眼睛，想象一下那个无穷远点P∞，P∞是不是很虚幻，其实与其说数学锻炼人的抽象能力，还不如说是锻炼人的想象力）。

给个图帮助理解一下：

直线上出现P∞点，所带来的好处是所有的直线都相交了，且只有一个交点。这就把直线的平行与相交统一了。为与无穷远点相区别把原来平面上的点叫做平常点。

以下是无穷远点的几个性质。

直线 L 上的无穷远点只能有一个。（从定义可直接得出）

平面上一组相互平行的直线有公共的无穷远点。（从定义可直接得出）

平面上任何相交的两直线 L1、L2 有不同的无穷远点。（否则 L1 和 L2 有公共的无穷远点 P ，则 L1 和 L2 有两个交点 A、P，故假设错误。）

平面上全体无穷远点构成一条无穷远直线。（自己想象一下这条直线吧）

平面上全体无穷远点与全体平常点构成射影平面。

二、射影平面坐标系

射影平面坐标系是对普通平面直角坐标系（就是我们初中学到的那个笛卡儿平面直角坐标系）的扩展。我们知道普通平面直角坐标系没有为无穷远点设计坐标，不能表示无穷远点。为了表示无穷远点，产生了射影平面坐标系，当然射影平面坐标系同样能很好的表示旧有的平常点（数学也是“向下兼容”的）。

我们对普通平面直角坐标系上的点A的坐标（x, y）做如下改造：

令 x=X/Z ，y=Y/Z（Z≠0）；则 A 点可以表示为（X:Y:Z）。

变成了有三个参量的坐标点，这就对平面上的点建立了一个新的坐标体系。

例 2.1：求点（1,2）在新的坐标体系下的坐标。

解：

∵X/Z=1 ，Y/Z=2（Z≠0）

∴X=Z，Y=2Z

∴坐标为（Z:2Z:Z），Z≠0。

即（1:2:1）（2:4:2）（1.2:2.4:1.2）等形如（Z:2Z:Z），Z≠0 的坐标，都是（1,2）在新的坐标体系下的坐标。

我们也可以得到直线的方程 aX+bY+cZ=0（想想为什么？提示：普通平面直角坐标系下直线一般方程是 ax+by+c=0）。

新的坐标体系能够表示无穷远点么？那要让我们先想想无穷远点在哪里。根据上一节的知识，我们知道无穷远点是两条平行直线的交点。那么，如何求两条直线的交点坐标？这是初中的知识，就是将两条直线对应的方程联立求解。

平行直线的方程是：

aX+bY+c1Z =0；

aX+bY+c2Z =0  (c1≠c2)； （为什么？提示：可以从斜率考虑，因为平行线斜率相同）；

将二方程联立，求解。有

c2Z= c1Z= -（aX+bY）

∵c1≠c2

∴Z=0 

∴aX+bY=0

所以无穷远点就是这种形式（X：Y：0）表示。注意，平常点 Z≠0，无穷远点 Z=0，因此无穷远直线对应的方程是 Z=0。

例 2.2：求平行线 L1：X+2Y+3Z=0 与 L2：X+2Y+Z=0 相交的无穷远点。

解：

因为 L1∥L2

所以有 Z=0， X+2Y=0

所以坐标为（-2Y:Y:0），Y≠0。

即（-2:1:0）（-4:2:0）（-2.4:1.2:0）等形如（-2Y:Y:0），Y≠0 的坐标，都表示这个无穷远点。

看来这个新的坐标体系能够表示射影平面上所有的点，我们就把这个能够表示射影平面上所有点的坐标体系叫做射影平面坐标系。

练习：

1、求点A(2,4) 在射影平面坐标系下的坐标。

2、求射影平面坐标系下点(4.5:3:0.5)，在普通平面直角坐标系下的坐标。

3、求直线X+Y+Z=0上无穷远点的坐标。

4、判断：直线aX+bY+cZ=0上的无穷远点 和 无穷远直线与直线aX+bY=0的交点，是否是同一个点？

三、椭圆曲线

上一节，我们建立了射影平面坐标系，这一节我们将在这个坐标系下建立椭圆曲线方程。因为我们知道，坐标中的曲线是可以用方程来表示的（比如：单位圆方程是 x2+y2=1）。椭圆曲线是曲线，自然椭圆曲线也有方程。

椭圆曲线的定义：

一条椭圆曲线是在射影平面上满足如下方程的所有点的集合，且曲线上的每个点都是非奇异（或光滑）的。

Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3                 [3-1]

定义详解：

Y2Z+a1XYZ+a3YZ2 = X3+a2X2Z+a4XZ2+a6Z3 是 Weierstrass 方程（维尔斯特拉斯，Karl Theodor Wilhelm Weierstrass,1815-1897），是一个齐次方程。

椭圆曲线的形状，并不是椭圆的。只是因为椭圆曲线的描述方程，类似于计算一个椭圆周长的方程（计算椭圆周长的方程，我没有见过，而对椭圆线 积分 （设密度为1）是求不出来的），故得名。

我们来看看椭圆曲线是什么样的。

所谓“非奇异”或“光滑”的，在数学中是指曲线上任意一点的偏导数 Fx(x,y,z)，Fy(x,y,z)，Fz(x,y,z) 不能同时为0。如果你没有学过高等数学，可以这样理解这个词，即满足方程的任意一点都存在切线。下面两个方程都不是椭圆曲线，尽管他们是方程 [3-1] 的形式，因为他们在（0:0:1）点处（即原点）没有切线。

椭圆曲线上有一个无穷远点O∞（0:1:0），因为这个点满足方程[3-1]。

知道了椭圆曲线上的无穷远点。我们就可以把椭圆曲线放到普通平面直角坐标系上了。因为普通平面直角坐标系只比射影平面坐标系少无穷远点。我们在普通平面直角坐标系上，求出椭圆曲线上所有平常点组成的曲线方程，再加上无穷远点O∞（0:1:0），不就构成椭圆曲线了么？

我们设 x=X/Z，y=Y/Z 代入方程 [3-1] 得到：

y2+a1xy+a3y = x3+a2x2+a4x+a6                            [3-2]

也就是说满足方程 [3-2] 的光滑曲线加上一个无穷远点O∞，组成了椭圆曲线。为了方便运算，表述，以及理解，今后论述椭圆曲线将主要使用 [3-2] 的形式。

本节的最后，我们谈一下求椭圆曲线一点的切线斜率问题。由椭圆曲线的定义可以知道，椭圆曲线是光滑的，所以椭圆曲线上的平常点都有切线。而切线最重要的一个参数就是斜率 k 。

例 3.1：求椭圆曲线方程 y2+a1xy+a3y=x3+a2x2+a4x+a6上，平常点 A(x,y) 的切线的斜率 k 。

解：

令

F(x,y)= y2+a1xy+a3y-x3-a2x2-a4x-a6

求偏导数

Fx(x,y)= a1y-3x2-2a2x-a4

Fy(x,y)= 2y+a1x+a3

则导数为：

f'(x)=- Fx(x,y)/ Fy(x,y)=-( a1y-3x2-2a2x-a4)/(2y+a1x +a3) = (3x2+2a2x+a4-a1y) /(2y+a1x +a3)

所以

k=(3x2+2a2x+a4-a1y) /(2y+a1x +a3)             [3-3]

看不懂解题过程没有关系，记住结论[3-3]就可以了。

练习：      

1、将给出图例的椭圆曲线方程Y2Z=X3-XZ2 和Y2Z=X3+XZ2+Z3转换成普通平面直角坐标系上的方程。

四、椭圆曲线上的加法

上一节，我们已经看到了椭圆曲线的图象，但点与点之间好象没有什么联系。我们能不能建立一个类似于在实数轴上加法的运算法则呢？天才的数学家找到了这一运算法则

自从近世纪代数学引入了群、环、域的概念，使得代数运算达到了高度的统一。比如数学家总结了普通加法的主要特征，提出了加群（也叫交换群，或 Abel（阿贝尔）群），在加群的眼中。实数的加法和椭圆曲线的上的加法没有什么区别。这也许就是数学抽象把。关于群以及加群的具体概念请参考近世代数方面的数学书。

运算法则：任意取椭圆曲线上两点 P、Q （若 P、Q两点重合，则做 P 点的切线）做直线交于椭圆曲线的另一点 R’，过 R’ 做 y 轴的平行线交于 R。我们规定 P+Q=R。（如图）

法则详解：

这里的 + 不是实数中普通的加法，而是从普通加法中抽象出来的加法，他具备普通加法的一些性质，但具体的运算法则显然与普通加法不同。

根据这个法则，可以知道椭圆曲线无穷远点 O∞ 与椭圆曲线上一点 P 的连线交于 P’，过 P’ 作 y 轴的平行线交于 P，所以有 无穷远点 O∞ + P = P 。这样，无穷远点 O∞ 的作用与普通加法中零的作用相当（0+2=2），我们把无穷远点 O∞ 称为零元。同时我们把 P’ 称为 P 的负元（简称，负P；记作，-P）。（参见下图）

根据这个法则，可以得到如下结论 ：如果椭圆曲线上的三个点 A、B、C，处于同一条直线上，那么他们的和等于零元，即 A+B+C= O∞

k 个相同的点 P 相加，我们记作 kP。如下图：P+P+P = 2P+P = 3P。

下面，我们利用 P、Q点的坐标 (x1,y1)，(x2,y2)，求出 R=P+Q 的坐标 (x4,y4)。

例 4.1：求椭圆曲线方程 y2+a1xy+a3y=x3+a2x2+a4x+a6 上，平常点 P(x1,y1)，Q(x2,y2) 的和 R(x4,y4) 的坐标。

解：

（1）先求点 -R(x3,y3)

因为 P, Q, -R 三点共线，故设共线方程为

y=kx+b

其中，若 P≠Q (P,Q两点不重合)，则直线斜率

k=(y1-y2)/(x1-x2)

若 P=Q (P,Q两点重合)，则直线为椭圆曲线的切线，

故由例 3.1 可知：

k=(3x2+2a2x+a4 -a1y) /(2y+a1x+a3)

因此 P, Q, -R 三点的坐标值就是以下方程组的解：

y2+a1xy+a3y=x3+a2x2+a4x+a6                                   [1]

y=(kx+b)                                                                      [2]

将 [2] 代入[1] 有

(kx+b)2+a1x(kx+b)+a3(kx+b) =x3+a2x2+a4x+a6        [3]

对 [3] 化为一般方程，根据三次方程根与系数关系（若方程x³＋ax²＋bx＋c=0 的三个根是 x1、x2、x3，则： x1＋x2＋x3=－a，x1x2＋x2x3＋x3x1=b，x1x2x2=－c）

所以

-(x1+x2+x3)=a2-ka1-k2

x3=k2+ka1+a2+x1+x2    --------------------- 求出点 -R 的横坐标

因为

k=(y1-y3)/(x1-x3)

故

y3=y1-k(x1-x3)    ------------------------------ 求出点 -R 的纵坐标

（2）利用 -R 求 R

显然有

x4=x3=k2+ka1+a2+x1+x2   -------------- 求出点 R 的横坐标

而 y3 y4 为 x=x4 时 方程 y2+a1xy+a3y=x3+a2x2+a4x+a6 的解化为一般方程 y2+(a1x+a3)y-(x3+a2x2+a4x+a6)=0 , 根据二次方程根与系数关系（如果方程 ax²＋bx＋c=0 的两根为 x1、x2，那么 x1+x2=-b/a，x1x2=c/a）

得：

-(a1x+a3)=y3+y4

故

y4=-y3-(a1x+a3)=k(x1-x4)-y1-(a1x4+a3)   ----- 求出点 R 的纵坐标

即：

x4=k2+ka1+a2+x1+x2

y4=k(x1-x4)-y1-a1x4-a3

本节的最后，提醒大家注意一点，以前提供的图像可能会给大家产生一种错觉，即椭圆曲线是关于 x 轴对称的。事实上，椭圆曲线并不一定关于 x 轴对称。如下图的 y2-xy=x3+1

五、密码学中的椭圆曲线

我们现在基本上对椭圆曲线有了初步的认识，这是值得高兴的。但请大家注意，前面学到的椭圆曲线是连续的，并不适合用于加密。所以，我们必须把椭圆曲线变成离散的点。

让我们想一想，为什么椭圆曲线为什么连续？是因为椭圆曲线上点的坐标，是实数的（也就是说前面讲到的椭圆曲线是定义在实数域上的），实数是连续的，导致了曲线的连续。因此，我们要把椭圆曲线定义在有限域上（顾名思义，有限域是一种只有由有限个元素组成的域）。

域的概念是从我们的有理数，实数的运算中抽象出来的，严格的定义请参考近世代数方面的数。简单的说，域中的元素同有理数一样，有自己得加法、乘法、除法、单位元(1)，零元(0),并满足交换率、分配率。

下面，我们给出一个有限域 Fp，这个域只有有限个元素。

Fp 中只有 p（p为素数）个元素 0, 1, 2 …… p-2, p-1

Fp 的加法（a+b）法则是 a+b≡c (mod p) ，即 (a+c)÷p 的余数和 c÷p 的余数相同。

Fp 的乘法（a×b）法则是 a×b≡c (mod p)

Fp 的除法（a÷b）法则是 a/b≡c (mod p)，即 a×b-1≡c  (mod p) ，b-1 也是一个 0 到 p-1 之间的整数，但满足 b×b-1≡1 (mod p)；具体求法可以参考初等数论。

Fp 的单位元是 1，零元是 0。

同时，并不是所有的椭圆曲线都适合加密。y2=x3+ax+b是一类可以用来加密的椭圆曲线，也是最为简单的一类。下面我们就把 y2=x3+ax+b 这条曲线定义在 Fp 上：

选择两个满足下列条件的小于 p ( p 为素数) 的非负整数 a、b

4a3+27b2≠0  (mod p)

则满足下列方程的所有点 (x,y)，再加上 无穷远点 O∞ ，构成一条椭圆曲线。

y2=x3+ax+b  (mod p)

其中 x,y 属于 0 到 p-1 间的整数，并将这条椭圆曲线记为 Ep(a,b)。

我们看一下 y2=x3+x+1  (mod 23) 的图像

是不是觉得不可思议？椭圆曲线，怎么变成了这般模样，成了一个一个离散的点？椭圆曲线在不同的数域中会呈现出不同的样子，但其本质仍是一条椭圆曲线。举一个不太恰当的例子，好比是水，在常温下，是液体；到了零下，水就变成冰，成了固体；而温度上升到一网络，水又变成了水蒸气。但其本质仍是 H2O。

Fp上的椭圆曲线同样有加法，但已经不能给以几何意义的解释。不过，加法法则和实数域上的差不多，请读者自行对比。

1. 无穷远点 O∞ 是零元，有 O∞ + O∞ = O∞，O∞ + P = P

2. P(x,y) 的负元是 (x,-y)，有 P + (-P) = O∞

3. P(x1,y1), Q(x2,y2) 的和 R(x3,y3) 有如下关系：

x3≡k2-x1-x2(mod p) 

y3≡k(x1-x3)-y1(mod p)

    其中

若 P=Q 则 k=(3x2+a)/2y1 

若 P≠Q 则 k=(y2-y1)/(x2-x1)

例 5.1：已知 E23(1,1) 上两点 P(3,10)，Q(9,7)，求 (1)-P，(2)P+Q，(3) 2P。

解：

(1)  –P的值为(3,-10)

(2)  k=(7-10)/(9-3)=-1/2

2 的乘法逆元为 12， 因为 2*12≡1 (mod 23)

k≡-1*12 (mod 23)

故 k=11

x=112-3-9=109≡17 (mod 23)

y=11[3-(-6)]-10=89≡20 (mod 23)

故 P+Q 的坐标为 (17,20)

3)  k=[3(32)+1]/(2*10)=1/4≡6 (mod 23)

x=62-3-3=30≡20 (mod 23)

y=6(3-7)-10=-34≡12 (mod 23)

故 2P 的坐标为 (7,12)

最后，我们讲一下椭圆曲线上的点的阶。如果椭圆曲线上一点 P，存在最小的正整数 n，使得数乘 nP=O∞，则将 n 称为 P 的阶，若 n 不存在，我们说 P 是无限阶的。 事实上，在有限域上定义的椭圆曲线上所有的点的阶 n 都是存在的（证明，请参考近世代数方面的书）

练习：

1． 求出 E11(1,6) 上所有的点。

2．已知 E11(1,6) 上一点 G(2,7)，求 2G 到 13G 所有的值。

六、椭圆曲线上简单的加密/解密

公开密钥算法总是要基于一个数学上的难题。比如 RSA 依据的是：给定两个素数 p、q 很容易相乘得到 n，而对 n 进行因式分解却相对困难。那椭圆曲线上有什么难题呢？

考虑如下等式：

K=kG     [其中 K, G为 Ep(a,b) 上的点，k 为小于 n（n 是点 G 的阶）的整数]

不难发现，给定 k 和 G，根据加法法则，计算 K 很容易；但给定 K 和 G，求 k 就相对困难了。这就是椭圆曲线加密算法采用的难题。我们把点 G 称为基点（base point），k（key point）就是私有密钥。

现在我们描述一个利用椭圆曲线进行加密通信的过程：

1、用户 A 选定一条椭圆曲线 Ep(a,b)，并取椭圆曲线上一点，作为基点 G。

2、用户 A 选择一个私有密钥 k，并生成公开密钥 K=kG。

3、用户 A 将 Ep(a,b) 和点 K，G 传给用户 B。

4、用户 B 接到信息后，将待传输的明文编码到 Ep(a,b) 上一点 M（编码方法很多，这里不作讨论），并产生一个随机整数 r（random）。

5、用户 B 计算点 C1=M+rK；C2=rG。

6、用户 B 将 C1、C2 传给用户A。

7、用户 A 接到信息后，计算 C1-kC2，结果就是点 M。因为 C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M ，再对点 M 进行解码就可以得到明文。

在这个加密通信中，如果有一个偷窥者 H ，他只能看到 Ep(a,b)、K、G、C1、C2 而通过 K、G 求 k 或通过 C2、G 求 r 都是相对困难的。因此，H 无法得到 A、B 间传送的明文信息。

密码学中，描述一条 Fp 上的椭圆曲线，常用到六个参量：

T=(p,a,b,G,n,h)

p 、a 、b 用来确定一条椭圆曲线，G 为基点，n 为点 G 的阶，h 是椭圆曲线上所有点的个数 m 与 n 相除的整数部分。这几个参量取值的选择，直接影响了加密的安全性。参量值一般要求满足以下几个条件：

1、p 当然越大越安全，但越大，计算速度会变慢，200 位左右可以满足一般安全要求；

2、p≠n×h；

3、pt≠1 (mod n)，1≤t<20；

4、4a3+27b2≠0 (mod p)；

5、n 为素数；

6、h≤4。

七、椭圆曲线签名在软件保护的应用

我们知道将公开密钥算法作为软件注册算法的好处是：黑客很难通过跟踪验证算法得到注册机。下面，将简介一种利用 Fp(a,b) 椭圆曲线进行软件注册的方法。

软件作者按如下方法制作注册机（也可称为签名过程）

1、选择一条椭圆曲线 Ep(a,b) 和基点 G；

2、选择私有密钥 k；

3、产生一个随机整数 r ；

4、将用户名和点 R 的坐标值 x,y 作为参数，计算 SHA（Secure Hash Algorithm 安全散列算法，类似于 MD5）值，即 Hash=SHA(username,x,y)；

5、计算 sn≡r - Hash * k (mod n)

6、将 sn 和 Hash 作为用户名 username 的序列号

软件验证过程如下：（软件中存有椭圆曲线 Ep(a,b) 和基点 G 以及公开密钥 K）

1、从用户输入的序列号中，提取 sn 以及 Hash；

2、计算点 R≡sn*G+Hash*K ( mod p )，如果 sn、Hash 正确，其值等于软件作者签名过程中点 R(x,y) 的坐标，

因为 sn≡r-Hash*k （mod n）

所以 sn*G+Hash*K=(r-Hash*k)*G+Hash*K=rG-Hash*kG+Hash*K=rG-Hash*K+Hash*K=rG=R；

3、将用户名和点 R 的坐标值 x,y 作为参数，计算 H=SHA(username,x,y)；

4、如果 H=Hash 则注册成功，如果 H≠Hash ，则注册失败（为什么？提示注意点 R 与 Hash 的关联性）。

简单对比一下两个过程：

作者签名用到了：椭圆曲线 Ep(a,b)，基点 G，私有密钥 k，及随机数 r。

软件验证用到了：椭圆曲线 Ep(a,b)，基点 G，公开密钥 K。

黑客要想制作注册机，只能通过软件中的 Ep(a,b)，点 G，公开密钥 K ，并利用 K=kG 这个关系获得 k 才可以，而求 k 是很困难的。

练习：

下面也是一种常于软件保护的注册算法，请认真阅读，并试回答签名过程与验证过程都用到了那些参数，黑客想制作注册机，应该如何做。

软件作者按如下方法制作注册机（也可称为签名过程）

1、选择一条椭圆曲线 Ep(a,b)，和基点 G；

2、选择私有密钥 k；

3、产生一个随机整数 r；

4、将用户名作为参数，计算 Hash=SHA(username)；

5、计算 x’=x  (mod n)

6、计算 sn≡(Hash+x’*k)/r (mod n)

7、将 sn 和 x’ 作为用户名 username 的序列号

软件验证过程如下：(软件中存有椭圆曲线 Ep(a,b) 和基点 G 以及公开密钥 K)

1、从用户输入的序列号中，提取 sn 以及 x’；

2、将用户名作为参数，计算 Hash=SHA(username)；

3、计算 R=(Hash*G+x’*K)/sn，如果 sn、Hash 正确，其值等于软件作者签名过程中点 R(x,y)

因为 sn≡(Hash+x’*k)/r (mod n)

所以 (Hash*G+x’*K)/sn=(Hash*G+x’*K)/[(Hash+x’*k)/r]=(Hash*G+x’*K)/[(Hash*G+x’*k*G)/(rG)]=rG*[(Hash*G+x’*K)/(Hash*G+x’*K)]=rG=R (mod p)

4、v≡x (mod n)

5、如果 v=x’ 则注册成功。如果 v≠x’ ，则注册失败。

主要参考文献

张禾瑞，《近世代数基础》，高等 教育 出版社，1978

闵嗣鹤 严士健，《初等数论》，高等教育出版社，1982

段云所，《网络信息安全》第三讲，北大计算机系

Michael Rosing ，chapter5《Implementing Elliptic Curve Cryptography》，Softbound，1998

《SEC 1: Elliptic Curve Cryptography》，Certicom Corp.，2000

《IEEE P1363a / D9》，2001

‘陆’ 人工智能算法简介

人工智能的三大基石—算法、数据和计算能力，算法作为其中之一，是非常重要的，那么人工智能都会涉及哪些算法呢？不同算法适用于哪些场景呢？

一、按照模型训练方式不同可以分为监督学习（Supervised Learning），无监督学习（Unsupervised Learning）、半监督学习（Semi-supervised Learning）和强化学习（Reinforcement Learning）四大类。

常见的监督学习算法包含以下几类：
（1）人工神经网络（Artificial Neural Network）类：反向传播（Backpropagation）、波尔兹曼机（Boltzmann Machine）、卷积神经网络（Convolutional Neural Network）、Hopfield网络（hopfield Network）、多层感知器（Multilyer Perceptron）、径向基函数网络（Radial Basis Function Network，RBFN）、受限波尔兹曼机（Restricted Boltzmann Machine）、回归神经网络（Recurrent Neural Network，RNN）、自组织映射（Self-organizing Map，SOM）、尖峰神经网络（Spiking Neural Network）等。
（2）贝叶斯类（Bayesin）：朴素贝叶斯（Naive Bayes）、高斯贝叶斯（Gaussian Naive Bayes）、多项朴素贝叶斯（Multinomial Naive Bayes）、平均-依赖性评估（Averaged One-Dependence Estimators，AODE）
贝叶斯信念网络（Bayesian Belief Network，BBN）、贝叶斯网络（Bayesian Network，BN）等。
（3）决策树（Decision Tree）类：分类和回归树（Classification and Regression Tree，CART）、迭代Dichotomiser3（Iterative Dichotomiser 3， ID3）,C4.5算法（C4.5 Algorithm）、C5.0算法（C5.0 Algorithm）、卡方自动交互检测（Chi-squared Automatic Interaction Detection，CHAID）、决策残端（Decision Stump）、ID3算法（ID3 Algorithm）、随机森林（Random Forest）、SLIQ（Supervised Learning in Quest）等。
（4）线性分类器（Linear Classifier）类：Fisher的线性判别（Fisher’s Linear Discriminant）
线性回归（Linear Regression）、逻辑回归（Logistic Regression）、多项逻辑回归（Multionmial Logistic Regression）、朴素贝叶斯分类器（Naive Bayes Classifier）、感知（Perception）、支持向量机（Support Vector Machine）等。

常见的无监督学习类算法包括：
（1） 人工神经网络（Artificial Neural Network）类：生成对抗网络（Generative Adversarial Networks，GAN），前馈神经网络（Feedforward Neural Network）、逻辑学习机（Logic Learning Machine）、自组织映射（Self-organizing Map）等。
（2） 关联规则学习（Association Rule Learning）类：先验算法（Apriori Algorithm）、Eclat算法（Eclat Algorithm）、FP-Growth算法等。
（3）分层聚类算法（Hierarchical Clustering）：单连锁聚类（Single-linkage Clustering），概念聚类（Conceptual Clustering）等。
（4）聚类分析（Cluster analysis）：BIRCH算法、DBSCAN算法，期望最大化（Expectation-maximization，EM）、模糊聚类（Fuzzy Clustering）、K-means算法、K均值聚类（K-means Clustering）、K-medians聚类、均值漂移算法（Mean-shift）、OPTICS算法等。
（5）异常检测（Anomaly detection）类：K最邻近（K-nearest Neighbor，KNN）算法，局部异常因子算法（Local Outlier Factor，LOF）等。

常见的半监督学习类算法包含：生成模型（Generative Models）、低密度分离（Low-density Separation）、基于图形的方法（Graph-based Methods）、联合训练（Co-training）等。

常见的强化学习类算法包含：Q学习（Q-learning）、状态-行动-奖励-状态-行动（State-Action-Reward-State-Action，SARSA）、DQN（Deep Q Network）、策略梯度算法（Policy Gradients）、基于模型强化学习（Model Based RL）、时序差分学习（Temporal Different Learning）等。

常见的深度学习类算法包含：深度信念网络（Deep Belief Machines）、深度卷积神经网络（Deep Convolutional Neural Networks）、深度递归神经网络（Deep Recurrent Neural Network）、分层时间记忆（Hierarchical Temporal Memory，HTM）、深度波尔兹曼机（Deep Boltzmann Machine，DBM）、栈式自动编码器（Stacked Autoencoder）、生成对抗网络（Generative Adversarial Networks）等。

二、按照解决任务的不同来分类，粗略可以分为二分类算法（Two-class Classification）、多分类算法（Multi-class Classification）、回归算法（Regression）、聚类算法（Clustering）和异常检测（Anomaly Detection）五种。
1.二分类（Two-class Classification）
（1）二分类支持向量机（Two-class SVM）：适用于数据特征较多、线性模型的场景。
（2）二分类平均感知器（Two-class Average Perceptron）：适用于训练时间短、线性模型的场景。
（3）二分类逻辑回归（Two-class Logistic Regression）：适用于训练时间短、线性模型的场景。
（4）二分类贝叶斯点机（Two-class Bayes Point Machine）：适用于训练时间短、线性模型的场景。（5）二分类决策森林（Two-class Decision Forest）：适用于训练时间短、精准的场景。
（6）二分类提升决策树（Two-class Boosted Decision Tree）：适用于训练时间短、精准度高、内存占用量大的场景
（7）二分类决策丛林（Two-class Decision Jungle）：适用于训练时间短、精确度高、内存占用量小的场景。
（8）二分类局部深度支持向量机（Two-class Locally Deep SVM）：适用于数据特征较多的场景。
（9）二分类神经网络（Two-class Neural Network）：适用于精准度高、训练时间较长的场景。

解决多分类问题通常适用三种解决方案：第一种，从数据集和适用方法入手，利用二分类器解决多分类问题；第二种，直接使用具备多分类能力的多分类器；第三种，将二分类器改进成为多分类器今儿解决多分类问题。
常用的算法：
（1）多分类逻辑回归（Multiclass Logistic Regression）：适用训练时间短、线性模型的场景。
（2）多分类神经网络（Multiclass Neural Network）：适用于精准度高、训练时间较长的场景。
（3）多分类决策森林（Multiclass Decision Forest）：适用于精准度高，训练时间短的场景。
（4）多分类决策丛林（Multiclass Decision Jungle）：适用于精准度高，内存占用较小的场景。
（5）“一对多”多分类（One-vs-all Multiclass）：取决于二分类器效果。

回归
回归问题通常被用来预测具体的数值而非分类。除了返回的结果不同，其他方法与分类问题类似。我们将定量输出，或者连续变量预测称为回归；将定性输出，或者离散变量预测称为分类。长巾的算法有：
（1）排序回归（Ordinal Regression）：适用于对数据进行分类排序的场景。
（2）泊松回归（Poission Regression）：适用于预测事件次数的场景。
（3）快速森林分位数回归（Fast Forest Quantile Regression）：适用于预测分布的场景。
（4）线性回归（Linear Regression）：适用于训练时间短、线性模型的场景。
（5）贝叶斯线性回归（Bayesian Linear Regression）：适用于线性模型，训练数据量较少的场景。
（6）神经网络回归（Neural Network Regression）：适用于精准度高、训练时间较长的场景。
（7）决策森林回归（Decision Forest Regression）：适用于精准度高、训练时间短的场景。
（8）提升决策树回归（Boosted Decision Tree Regression）：适用于精确度高、训练时间短、内存占用较大的场景。

聚类
聚类的目标是发现数据的潜在规律和结构。聚类通常被用做描述和衡量不同数据源间的相似性，并把数据源分类到不同的簇中。
（1）层次聚类（Hierarchical Clustering）：适用于训练时间短、大数据量的场景。
（2）K-means算法：适用于精准度高、训练时间短的场景。
（3）模糊聚类FCM算法（Fuzzy C-means，FCM）：适用于精确度高、训练时间短的场景。
（4）SOM神经网络（Self-organizing Feature Map，SOM）：适用于运行时间较长的场景。
异常检测
异常检测是指对数据中存在的不正常或非典型的分体进行检测和标志，有时也称为偏差检测。
异常检测看起来和监督学习问题非常相似，都是分类问题。都是对样本的标签进行预测和判断，但是实际上两者的区别非常大，因为异常检测中的正样本（异常点）非常小。常用的算法有：
（1）一分类支持向量机（One-class SVM）：适用于数据特征较多的场景。
（2）基于PCA的异常检测（PCA-based Anomaly Detection）：适用于训练时间短的场景。

常见的迁移学习类算法包含：归纳式迁移学习（Inctive Transfer Learning） 、直推式迁移学习（Transctive Transfer Learning）、无监督式迁移学习（Unsupervised Transfer Learning）、传递式迁移学习（Transitive Transfer Learning）等。

算法的适用场景：
需要考虑的因素有：
（1）数据量的大小、数据质量和数据本身的特点
（2）机器学习要解决的具体业务场景中问题的本质是什么？
（3）可以接受的计算时间是什么？
（4）算法精度要求有多高？
————————————————

原文链接： https://blog.csdn.net/nfzhlk/article/details/82725769