机器学习算法-初识Learning to Rank

发表于 2017-08-30 更新于 2018-12-17 分类于机器学习算法

本文主要对排序模型做一个简要的整理。首先介绍了一些传统的排序模型，然后介绍比较新的learning to rank.

要想了解L2R，首先我们要了解一下传统的排序模型。

传统的排序模型

传统的排序模型主要分为两类：相关度排序模型和重要性排序模型。

重要性排序模型(Importance Ranking Model)

重要性排序模型就不考虑上述提到的【查询】，而仅仅根据网页(亦即文档)之间的图结构来判断文档的权威程度，典型的权威网站包括Google，Yahoo!等。常用的模型包括PageRank，HITS，HillTop，TrustRank等等。

传统排序模型的缺陷

以上的这些传统的排序模型，单个模型往往只能考虑某一个方面(相关度或者重要性)，所以只是用单个模型达不到要求。搜索引擎通常会组合多种排序模型来进行排序，但是，如何组合多个排序模型来形成一个新的排序模型，以及如何调节这些参数，都是一个很大的问题。

因此，伟大的科学家们提出了Learning to Rank，来解决上述问题。

Learning to Rank

Learning to Rank是一种机器学习模型。它使用机器学习的方法，我们可以把各个现有排序模型的【输出作为特征】，然后训练一个新的模型，并自动学得这个新的模型的参数，从而很方便的可以组合多个现有的排序模型来生成新的排序模型。

L2R特征的选取

与文本分类不同，L2R考虑的是【给定查询的文档集合的排序】。所以，L2R用到的特征不仅仅包含文档d本身的一些特征(比如是否是Spam)等，也包括文档d和给定查询q之间的相关度，以及文档在整个网络上的重要性(比如PageRank值等)，亦即我们可以使用相关性排序模型和重要性排序模型的输出来作为L2R的特征。

总结来说，L2R的特征有以下两点：

传统排序模型的输出，既包括相关性排序模型的输出f(q,d)，也包括重要性排序模型的输出。
文档本身的一些特征，比如是否是Spam等。

L2R训练数据的构造

L2R的训练数据可以有三种形式：

对于每个查询，各个文档的绝对相关值(非常相关，比较相关，不相关，等等)；
对于每个查询，两两文档之间的相对相关值(文档1比文档2相关，文档4比文档3相关，等等)；
对于每个查询，所有文档的按相关度排序的列表(文档1>文档2>文档3)。

这三种形式的训练数据之间可以相互转换，详见[1]。

训练数据的获取有两种主要方法：人工标注[3]和从日志文件中挖掘[4]:

人工标注：首先从搜索引擎的搜索记录中随机抽取一些查询，将这些查询提交给多个不同的搜索引擎，然后选取各个搜索引擎返回结果的前K个，最后由专业人员来对这些文档按照和查询的相关度进行标注。

从日志中挖掘：搜索引擎都有大量的日志记录用户的行为，我们可以从中提取出L2R的训练数据。Joachims提出了一种很有意思的方法[4]：给定一个查询，搜索引擎返回的结果列表为L，用户点击的文档的集合为C，如果一个文档di被点击过，另外一个文档dj没有被点击过，并且dj在结果列表中排在di之前，则di>dj就是一条训练记录。亦即训练数据为：{di>dj|di属于C，dj属于L-C，p(dj) < p(di)}，其中p(d)表示文档d在查询结果列表中的位置，越小表示越靠前。

L2R模型训练

L2R是一个有监督学习过程。

对与每个给定的查询-文档对(query document pair)，抽取相应的特征(既包括查询和文档之间的各种相关度，也包括文档本身的特征以及重要性等)，另外通过或者人工标注或者从日志中挖掘的方法来得到给定查询下文档集合的真实序列。然后我们使用L2R的各种算法来学到一个排序模型，使其输出的文档序列和真实序列尽可能相似。

L2R算法分类和简介

L2R算法主要包括三种类别：PointWise，PairWise，ListWise。

PointWise L2R

pointwise简介 PointWise方法只考虑【给定查询下】，单个文档的绝对相关度，而不考虑其他文档和给定查询的相关度。亦即给定查询q的一个真实文档序列，我们只需要考虑【单个文档di和该查询的相关程度ci】，亦即输入数据应该是如下的形式：

一种思想是将query与doc之间的相关程度作为标签，比如标签有三档，问题就变为多类分类问题,模型有McRank,svm，最大熵等。另一种思想是将query与doc之间的相关程度作为分数利用回归模型拟合，经典回归模型有线性回归，dnn，mart等。

pointwise形式 输入：doc 的特征向量输出：每个doc的相关性分数损失函数: 回归loss，分类loss，有序回归loss

pointwise常用算法 Pointwise方法主要包括以下算法：Pranking (NIPS 2002), OAP-BPM (EMCL 2003), Ranking with Large Margin Principles (NIPS 2002), Constraint Ordinal Regression (ICML 2005)。

pointwise特点 Pointwise方法仅仅使用传统的分类，回归或者Ordinal Regression方法来对给定查询下单个文档的相关度进行建模。这种方法没有考虑到排序的一些特征，比如文档之间的排序结果针对的是给定查询下的文档集合，而Pointwise方法仅仅考虑单个文档的绝对相关度；另外，在排序中，排在最前的几个文档对排序效果的影响非常重要，Pointwise没有考虑这方面的影响。

PairWise

pairwise简介 Pairwise方法考虑给定查询下，【两个文档之间】的相对相关度。亦即给定查询q的一个真实文档序列，我们只需要考虑任意两个相关度不同的文档之间的相对相关度：di>dj，或者di < dj 。

pairwise原理 Pairwise的方法是将文档组成文档对，不单考虑单个文档，而是考虑文档组对是否合理，比如对于query 1返回的三个文档 doc1，doc2，doc3, 有三种组对方式，<doc1,doc2>,<doc2,doc3>,<doc1,doc3>。当三个文档原来的label为3,4,2时，这样组对之后的三个例子就有了新的分数（表达这种顺序是否合理），可以利用这种数据进行分类学习，模型如SVM Rank, 还有RankNet(C. Burges, et al. ICML 2005)， FRank(M.Tsai, T.Liu, et al. SIGIR 2007)，RankBoost(Y. Freund, et al. JMLR 2003)。

参考文献机器学习排序之Learning to Rank简单介绍对pairwise方法做出了比较容易理解的介绍：文档对方法（parwise）则将重点转向量对文档顺序关系是否合理进行判断。之所以被称为文档对方法，是因为这种机器学习方法的训练过程和训练目标，是判断任意两个文档组成的文档对<D0C1，D0C2>是否满足顺序关系，即判断是否D0C1应该排在DOC2的前面。图3展示了一个训练实例：査询Q1对应的搜索结果列表如何转换为文档对的形式，因为从人工标注的相关性得分可以看出，D0C2得分最高，D0C3次之，D0C1得分最低，于是我们可以按照得分大小顺序关系得到3个如图3所示的文档对，将每个文档对的文档转换为特征向量后，就形成了一个具体的训练实例。【备注：根据我的理解，下图有了一些错误。doc1分数应该为3，doc2分数应该为5】。图3 文档对的方法训练实例

根据转换后的训练实例，就可以利用机器学习方法进行分类函数的学习，具体的学习方法有很多，比如SVM. Boosts、神经网络等都可以作为具体的学习方法，但是不论具体方法是什么，其学习目标都是一致的，即输入- 个査询和文档对<Docl，DOC2>, 机器学习排序能够判断这种顺序关系是否成立，如果成立，那么在搜索结果中D0C1应该排在D0C2 前面，否则Doe2应该摔在Docl前面，通过这种方式，就完成搜索结果的排序任务。

那么，如何将排序问题转化为机器学习能够学习的分类问题呢？

参考文献Learning to Rank之Ranking SVM 简介给出了一个很好的例子解释这个问题：给定查询q, 文档d1>d2>d3(亦即文档d1比文档d2相关, 文档d2比文档d3相关, x1, x2, x3分别是d1, d2, d3的特征)。为了使用机器学习的方法进行排序，我们将排序转化为一个分类问题。我们定义新的训练样本, 令x1-x2, x1-x3, x2-x3为正样本,令x2-x1, x3-x1, x3-x2为负样本, 然后训练一个二分类器(支持向量机)来对这些新的训练样本进行分类，如下图所示: 左图中每个椭圆代表一个查询, 椭圆内的点代表那些要计算和该查询的相关度的文档, 三角代表很相关, 圆圈代表一般相关, 叉号代表不相关。我们把左图中的单个的文档转换成右图中的文档对(di, dj), 实心方块代表正样本, 亦即di>dj, 空心方块代表负样本, 亦即di < dj。将【排序问题转化为分类问题】之后, 我们就可以使用常用的机器学习方法解决该问题。

pairwise存在的问题

尽管文档对方法相对单文档方法做出了改进，但是这种方法也存在两个明显的问题：

一个问题是：文档对方法只考虑了两个文档对的相对先后顺序，却没有考虑文档出现在搜索列表中的位置，排在搜索站果前列的文档更为重要，如果前列文档出现判断错误，代价明显高于排在后面的文档。针对这个问题的改进思路是引入代价敏感因素，即每个文档对根据其在列表中的顺序具有不同的权重，越是排在前列的权重越大，即在搜索列表前列如果排错顺序的话其付出的代价更高?

另外一个问题是：不同的査询，其相关文档数量差异很大，所以转换为文档对之后，有的查询对能有几百个对应的文档对，而有的查询只有十几个对应的文档对，这对机器学习系统的效果评价造成困难 ?我们设想有两个查询，査询Q1对应500个文文档对，查询Q2 对应10个文档对，假设学习系统对于査询Ql的文档对能够判断正确480个，对于査询 Q2的义格对能够判新正确2个，如果从总的文档对数量来看，这个学习系统的准确率是 (480+2)/（500+10）=0.95.即95%的准确率，但是从査询的角度，两个査询对应的准确率分别为：96%和20%,两者平均为58%,与纯粹从文档对判断的准确率相差甚远，这对如何继续调优机器学习系统会带来困扰。

ListWise（文档列表方法）

listwise简介 单文档方法将训练集里每一个文档当做一个训练实例，文档对方法将同一个査询的搜索结果里任意两个文档对作为一个训练实例。与Pointwise和Pairwise方法不同，文档列表方法与上述两种表示方式不同，是将每一个查询对应的【所有搜索结果列表整体】作为一个训练实例，这也是为何称之为文档列表方法的原因。

listwise原理 文档列表方法根据K个训练实例（一个査询及其对应的所有搜索结果评分作为一个实例）训练得到最优评分函数F，对于一个新的用户査询，函数F 对每一个文档打分，之后按照得分顺序由高到低排序，就是对应的搜索结果。

所以关键问题是：拿到训练数据，如何才能训练得到最优的打分函数？

这里介绍一种训练方法，它是基于搜索结果排列组合的概率分布情况来训练的，图4是这种方式训练过程的图解示意。图4 不同评分函数的KL距离

首先解释下什么是搜索结果排列组合的概率分布，我们知道，对于搜索引擎来说，用户输入査询Q，搜索引擎返回搜索结果，我们假设搜索结果集合包含A、B和C 3个文档，搜索引擎要对搜索结果排序，而这3个文档的顺序共有6种排列组合方式:

ABC, ACB, BAG, BCA, CAB和CBA,

而每种排列组合都是一种可能的搜索结果排序方法。

对于某个评分函数F来说，对3个搜索结果文档的相关性打分，得到3个不同的相关度得分F(A)、F(B)和F(C)，根据这3个得分就可以计算6种排列组合情况各自的概率值。

不同的评分函数，其6种搜索结果排列组合的概率分布是不一样的。

了解了什么是搜索结果排列组合的概率分布，我们介绍如何根据训练实例找到最优的评分函数。图4展示了一个具体的训练实例，即査询Q1及其对应的3个文档的得分情况，这个得分是由人工打上去的，所以可以看做是标准答案。

可以设想存在一个最优的评分函数g，对查询Q1来说，其打分结果是：A文档得6分，B文档得4分，C文档得3分，

因为得分是人工打的，所以具体这个函数g是怎样的我们不清楚，我们的任务就是找到一个函数，使得函数对Ql的搜索结果打分顺序和人工打分顺序尽可能相同。既然人工打分 (虚拟的函数g) 已知，那么我们可以计算函数g对应的搜索结果排列组合概率分布，其具体分布情况如图4中间的概率分布所示。

假设存在两个其他函数h和f，它们的计算方法已知，对应的对3个搜索结果的打分在图上可以看到，由打分结果也可以推出每个函数对应的搜索结果排列组合概率分布，那么h与f哪个与虚拟的最优评分函数g更接近呢？

一般可以用两个分布概率之间的距离远近来度量相似性，KL距离就是一种衡量概率分布差异大小的计算工具，通过分别计算h与g的差异大小及f与g的差异大小，可以看出f比h更接近的最优函数g，那么在这个函数中，我们应该优先选f作为将来搜索可用的评分函数，训练过程就是在可能的函数中寻找最接近虚拟最优函数g的那个函数作为训练结果，将来作为在搜索时的评分函数。

上述例子只是描述了对于单个训练实例如何通过训练找到最优函数，事实上我们有K 个训练实例，虽然如此，其训练过程与上述说明是类似的，可以认为存在一个虚拟的最优评分函数g(实际上是人工打分），训练过程就是在所有训练实例基础上，探寻所有可能的候选函数，从中选择那个KL距离最接近于函数g的，以此作为实际使用的评分函数。经验结果表明，基于文档列表方法的机器学习排序效果要好于前述两种方法。

常用算法 Listwise算法主要包括以下几种算法：LambdaRank (NIPS 2006), AdaRank (SIGIR 2007), SVM-MAP (SIGIR 2007), SoftRank (LR4IR 2007), GPRank (LR4IR 2007), CCA (SIGIR 2007), RankCosine (IP&M 2007), ListNet (ICML 2007), ListMLE (ICML 2008) 。

相比于Pointwise和Pairwise方法，Listwise方法直接优化给定查询下，整个文档集合的序列，所以比较好的解决了克服了以上算法的缺陷。Listwise方法中的LambdaMART(是对RankNet和LambdaRank的改进)在Yahoo Learning to Rank Challenge表现出最好的性能。

参考文献

[1]. Learning to Rank for Information Retrieval. Tie-yan Liu. [2]. Learning to Rank for Information Retrieval and Natural Language Processing. Hang Li. [3]. A Short Introduction to Learning to Rank. Hang Li. [4]. Optimizing Search Engines using Clickthrough Data. Thorsten Joachims. SIGKDD,2002. [5]. Learning to Rank小结

数据库常用语句

发表于 2017-07-25 更新于 2018-12-17 分类于数据库

启动/关闭

启动：sudo systemctl start mysqld或mysql -u root -p
查看状态：sudo systemctl status mysqld

linux下执行sql脚本

进入到mysql后，执行source /路径/tester.sql;即可

databases操作

列出所有数据库：SHOW DATABASES;
创建数据库：CREATE DATABASE database_name;
进入某数据库：USE database_name;

tables操作

列出所有表：SHOW TABLES;

创建表：

CREATE TABLE 表名称
(
列名称1 数据类型,
列名称2 数据类型,
列名称3 数据类型,
....
)

输出表头：SHOW COLUMNS FROM Table_name;

MYSQL数据类型

MySQL 数据类型

参考文献

归并排序

发表于 2017-07-23 更新于 2018-12-17 分类于排序算法

思路

分治法 将数组分成A、B两组，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

代码

//将两个有序数组合并成一个有序数组
void merge(int a[], int begin,int mid,int end,int b[]) {
    int i = begin;
    int j = mid + 1;
    int k = 0;
    while ((i <= mid) && (j <= end)) {
        if (a[i] < a[j]) {
            b[k] = a[i];
            k++;
            i++;
        }
        else{
            b[k] = a[j];
            k++;
            j++;
        }
    }
    while (i<=mid){
        b[k] = a[i];
        k++;
        i++;
    }
    while (j <= end){
        b[k] = a[j];
        k++;
        j++;
    }
    for (int i = 0; i < k; i++){
        a[begin + i] = b[i];
    }
}
//归并排序
void MergeSort(int a[], int begin,int end,int b[]) {
    if (begin < end) {
        int mid = (begin + end) / 2;
        MergeSort(a, begin, mid, b);
        MergeSort(a, mid + 1, end, b);
        merge(a, begin, mid, end, b);
    }
}

时间复杂度

由于归并排序是先将数组分成两部分，将两部分分别排序后，再合并。假设n个元素排序的时间是T(n)，而两部分分别排序的时间是T(n/2)，合并的复杂度是cn；因此：

\[T(n) = 2T(n/2) + cn\]

再解释一下$T(n) = 2T(n/2) + cn$ 这个东西，$ 2T(n/2)$ 是下一层带来的代价，$cn$ 是本层带来的代价。因此我们画一颗递归树，树的【每层表示本层所消耗的代价】，如下图所示：

第一行cn表示当前层消耗的代价
第二行两个T(n/2)代表下一层消耗的代价

将这个递归树再往下拓展一层，我们得到：

我们再进行扩展：

我们看到，完全扩展了的递归树具有$logn + 1$ 层，其中每层的代价都是$cn$ 。因此总的代价为【每一层的代价之和】：

\[cn (log n + 1) = cnlogn + cn = O(nlogn)\]

最坏情况$O(n\log(n))$
平均情况$O(n\log(n))$

选择排序

发表于 2017-07-22 更新于 2018-12-17 分类于排序算法

思路

每次从无序区选择一个最小的放大有序区的最后

设数组为a[0…n-1]。

初始时，数组全为无序区为a[0..n-1]。令i=0
在无序区a[i…n-1]中选取一个最小的元素，将其与a[i]交换。交换之后a[0…i]就形成了一个有序区。
i++并重复第二步直到i==n-1。排序完成。

代码

//选择排序
void SekectSort(int a[], int len) {
    for (int i = 0; i < len; i++) {
        int min = a[i];
        int loc = i;
        //寻找最小的元素
        for (int j = i + 1; j < len; j++) {
            if (a[j] < min) {
                min = a[j];
                loc = j;
            }
        }
        //把最小的元素放在有序区后面
        int temp = a[loc];
        a[loc] = a[i];
        a[i] = temp;
    }
}

参考

MoreWindows Blog 白话经典算法系列

希尔排序

发表于 2017-07-22 更新于 2018-12-17 分类于排序算法

思想

希尔排序的实质是分组插入排序，又称缩小增量排序。

该方法的基本思想是： 1. 先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的），对这些子序列分别进行直接插入排序 2. 依次缩减增量再进行排序 3. 待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

例子

现在我们要将这样一个数组排序，一共有10个元素

第一次增量 gap = 10/2 = 5

整个数组被分成了5个子数组，分别是[49,13]，[38,27]，[65,49]，[97,55]，[26,4] 然后对这五个子数组进行插入排序，得到下面结果

第二次增量 gap = 5/2 = 2

这次我们把整个数组分成了两个子数组，分别是[13,49,4,38,97],[27,55,49,65,26] 对这个两个子数组排序，结果如下：

第三次增量 gap = 2/2 = 1 此时整个数组已经接近有序，对整个数组进行全排列

最终得到数组有序

代码

//希尔排序
void HillSort(int a[], int len) {
    int delta = len/2;
    while (delta > 0) {
        for (int i = 0; i < delta; i++) {//分成了delta个子序列
            //对每个子序列进行插入排序
            for (int j = i + delta; j < len; j = j + delta) {
                int jj = j - delta;
                int temp = a[j];
                while ((a[jj] > temp)&&(jj>=0)) {
                    a[jj + delta] = a[jj];
                    jj -= delta;
                }
                //插入
                a[jj + delta] = temp;
            }
        }
        delta = delta / 2;
    }
}

优化

白话经典算法系列原文是这么说的 >很明显，上面的shellsort1代码虽然对直观的理解希尔排序有帮助，但代码量太大了，不够简洁清晰。因此进行下改进和优化，以第二次排序为例，原来是每次从1A到1E，从2A到2E，可以改成从1B开始，先和1A比较，然后取2B与2A比较，再取1C与前面自己组内的数据比较…….。这种每次从数组第gap个元素开始，每个元素与自己组内的数据进行直接插入排序显然也是正确的。

我理解了一下，思路就是把在序列中提取子序列的过程简化了，我们可以从第gap个元素开始，向后遍历到序列末尾，可以个元素都跟其所在的子序列中位于它前面的数字做插入排序，最终就会得到一个有序数列了~

画个图表示一下吧，还是刚才那个序列，比如说此时进行到第二次排序了，gap=2的情况：

从a[2]开始遍历，此时a[2]所在的子序列为[a[0],a[2],a[4],a[6],a[8]]，需要将a[2]和位于它前面的a[0]比较，插入到合适的位置：

指针后移一位，同上此时a[3]所在的子序列为[a[1],a[3],a[5],a[7],a[9]]，需要将a[3]和位于它前面的a[1]比较，插入合适的位置：

接下来指针指向a[4],此时需要将a[4]和位于它前面的a[2]、a[0]比较，插入合适的位置：

下面重复上面的步骤：

此处省略剩余步骤.....最终可以将数组排列至有序状态

现在可以上代码了~

//希尔排序
void HillSort(int a[], int len) {
    int delta = len/2;
    while (delta > 0) {
        for (int i = delta; i < len; i++) {//遍历
            //对该元素子前面的子数组进行插入排序
            int temp = a[i];
            int jj = i - delta;
            while ((jj >=0)&&(a[jj]>temp)){
                swap(a[jj], a[jj+delta]);
                jj -= delta;
            }
        }
        delta = delta / 2;
    }
}

参考

MoreWindows Blog 白话经典算法系列

插入排序

发表于 2017-07-20 更新于 2018-12-17 分类于排序算法

思想

直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

设数组为a[0…n-1]。

初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1
将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。
i++并重复第二步直到i==n-1。排序完成。

在查找某元素应该插入到前面有序序列的位置时，我们可以采用边交换边插入的方式，直到无需交换

代码

void InsertSort(int a[],int len) {
    for (int i = 1; i < len; i++) {
        //查找应该插入的位置
        for (int j = i; j > 0; j--){
            if (a[j - 1] > a[j]) {
                int temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
            }
            else
                break;
        }
    }
}

其中交换元素部分可以调用STL中的swap函数实现

//插入排序
void InsertSort(int a[],int len) {
    for (int i = 1; i < len; i++) {
        //查找应该插入的位置
        for (int j = i; j > 0; j--){
            if (a[j - 1] > a[j]) {
                swap(a[j], a[j - 1]);
            }
            else
                break;
        }
    }
}

时间复杂度

$O(n^2)$

冒泡排序

发表于 2017-07-20 更新于 2018-12-17 分类于排序算法

思想

依次比较相邻的两个数据，如果前面的比后面的大，就将其交换
这样交换一轮之后，整个序列中最大的就“沉”到了最后面的位置
重复上述过程，依次把第二大、第三大...的数字放到后面的位置。

代码

void BubbleSort(int a[], int len) {
    for (int i = 0; i < len; i++) {//一共需要遍历len轮
        for (int j = 0; j < len -1-i; j++) {//后面的len-1个数据
            if (a[j] > a[j + 1]) {
                int temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;
            }
        }
    }
}

接下来可以优化一下，上面的程序中一共进行了N轮比较，其实如果有一趟没有发生交换就说明这时候每两个相邻数据都已经呈现前边比后边小的状态了，此时已经达到有序状态了，所以后面就无需再继续比较了

改进代码

void BubbleSort(int a[], int len) {
    int flag = 1;
    for (int i = 0; i < len; i++) {//一共需要遍历len轮
        int flag = 0;//用来记录本轮是否发生交换
        for (int j = 0; j < len - 1 - i; j++) {//后面的len-1个数据
            if (a[j] > a[j + 1]) {
                int temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;
                flag = 1;//本轮发生交换了
            }
        }
        if (flag == 0) {//如果本轮未发生交换，跳出
            break;
        }
    }
}

还可以进一步优化，假设有100个数的数组，只有前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。

一般地，冒泡排序在进行过程中，也会出现后面已经排好了的情况，所以如果记录一下有序的位置，下一次就可以不用向后遍历了。

代码

void BubbleSort(int a[], int len) {
    int k ;//用于记录从那个数据开始之后的数据为
    int flag = len-1;//用于几率从哪个数据开始之后的数据有序
    while (flag > 0) {
        k = flag;//计算到k之前
        flag = 0;//用于记录本轮是否有交换
        for (int j = 0; j < k; j++) {//后面的len-1个数据
            if (a[j] > a[j + 1]) {
                int temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;
                flag = j;//本轮交换了，更新交换位置
            }
        }
    }
}

总结一下冒泡排序的关键点就是相邻元素两两比较交换，执行N轮，如果有某一轮没有发生交换说明已经有序，停止；记录下每一轮交换停止的位置，这之后的数据时有序的，下一轮无需考察。

时间复杂度

$O(n^2)$

快速排序

发表于 2017-07-17 更新于 2018-12-17 分类于排序算法

感谢@MoreWindows的白话经典算法系列，浅显易懂，让我终于看懂了快速排序，总结一下

思想

步骤：

从数列中选择一个作为基准数
分区操作：把比基准数小的都排在基准数的左边，比基准数大的都排在基准数的右边
对基准数的左边和右边分治排序

具体实现：挖坑填数+分治法

这里结合个实际例子说明

根据上面的步骤，选取第一个作为基准数，接下来我们需要把比它小的数字放到它的左边，比它大的数字放到它的右边，这里就需要重点注意挖坑填数的方法了，划重点！！！

temp=72

我们先把基准数72保存到变量temp中，这时候就相当于在数组的第一个位置上挖了一个“坑”，如果我们在后边发现有比temp小的数字，就可以把那个比较小的数字填到这个空缺的“坑”里了。

我们定义一个从后向前遍历的指针j，发现a[8]位置上的48比72小，所以我们要把48放到前面去，填补之前72留下的空缺.

这时候原来存放48的这个位置就空了出来，有了一个新的“坑”，此时指针i向后遍历，如果找到比temp大的数字，便可以填补之前的48留下的坑了。恩，我们找到了a[3]位置上的88，将他填补到之前48留下来的“坑”里。

接下来继续重复上面的过程，先从后向前找到比基准值小的，填补在前面的“坑”里，然后再从前向后找比基准值大的，填补刚才空出来的“坑”。直到最终两个指着相遇。

而此时空缺的位置，恰好就是基准值temp的位置。将基准值填入空缺位置，至此就完成了一次分区的操作，此时基准数前面的数字都比基准数小，后面的都比基准数大。

接下来就是对基准数前后两段数组分而治之，采用递归调用的思想，将整个数组调整至有序状态。

代码

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;

void quiksort(vector<int> &vec, int i, int j) {
    if (i < j) {
        int temp = vec[i];//存储基准值
        int left = i;
        int right = j;
        while (left < right) {
            //后指针向前遍历，寻找比基准值小的数字
            while (left < right && vec[right] >= temp) {
                right--;
            }
            //填数
            vec[left] = vec[right];
            //前指针向后遍历，寻找比基准值大的数字
            while (left < right && vec[left] <= temp) {
                left++;
            }
            //填数
            vec[right] = vec[left];
        }
        vec[right] = temp;
        //递归调用
        quiksort(vec, i, right - 1);
        quiksort(vec, right + 1, j);
    }
}

int main() {
    int n;
    int temp;
    vector<int> vec = {};
    scanf_s("%d", &n);
    while (n > 0) {
        scanf_s("%d", &temp);
        vec.push_back(temp);
        n--;
    }
    quiksort(vec, 0, vec.size() - 1);
    for (int i = 0; i < vec.size(); i++) {
        cout << vec[i]<<" ";
    }
    system("pause");
    return 0;
}

时间复杂度

最坏时间复杂度：$O(n^2)$
期望时间复杂度：$O(n\log(n))$

协同过滤推荐算法

简介

简介：通过在用户的一系列行为中寻找特定模式来产生用户特殊推荐。输入：仅仅依赖于惯用数据（例如评价、购买、下载等用户偏好行为）。方式：可通过单个用户行为单独构造模型；也可以通过其他用户行为，使用群组知识并基于相似用户来形成推荐内容。类型： - 基于领域的协同过滤（user-based或item-based） - 基于模型的协同过滤（矩阵因子分解、受限玻尔兹曼机、贝叶斯网络等等）

实例

为了更好地理解，我们以博客推荐为例。已知用户已订阅并阅读博客的信息，可以根据用户偏好来对他们进行分组。例如可以将阅读多篇相同博客的用户分到一个组。基于组信息，可识别出该组阅读了哪些最流行的博客，然后对于群组中的某个用户，可以向他推荐他还未阅读也未订阅的最流行的博客。

在下图的表中，行是一组博客，列是用户，表是该用户阅读该文章的数量。
通过根据用户的阅读习惯来为用户划分集群。比如使用一个 nearest-neighbor 算法：找到与当前用户user口味相近的k各用户；对用户u没有见过的博客p，利用k个近邻对p进行预测评分。
用以上算法我们得到两个分别包含两个用户的cluster，每个cluster中的成员都有相似的阅读习惯：Marc 和 Elise（他们都阅读了多篇关于 Linux® 和云计算的文章）形成 Cluster 1。Cluster 2 中包含 Megan 和 Jill，他们都阅读了多篇关于 Java™ 和敏捷性的文章。

nearest-nerghbor算法

刚才说到了用nearest-nerghbor算法来计算user-based的user相似度，然后再进行推荐，那么就带来了两个问题： - 如何度量user之间的相似性？ - 如何推荐博客？

首先解决第一个问题，如何度量相似性？

先说结论：采用改进的余弦相似度来进行度量。

首先我们看一下Pearson相关系数和余弦相似度。 pearson相关系数用来描诉两组向量一同变化的趋势，取值从+1（强正相关）到-1（强负相关）。用户a和用户b的相似度：其中： - $r_{a,p}$表示用户a对博客p的阅读量； - $\overline{r_a}$表示用户a的平均阅读量； - pearson相关系数越接近于1，那么用户a、b月相似。

然而，这并不完美，pearson相关系数存在以下缺陷： - 未考虑博客的数量对相似度的影响；例如：用户a与b有两个重叠项，用户a与c有10个重叠项；但有可能出现$sim(a,c)< sim(a,b)$的情况，因为计算pearson系数时，重叠项的个数没有影响。但这并不能说明用户b更与a相似。 - 如果只有一个重叠项，或所有重叠项的评分都相等，就无法计算pearson相关系数（分子或分母为0）。

接下来我们看看另一种相似度度量方式——余弦相似度。这代表两个user向量的夹角。但这与向量的大小无关，因此伟大的科学家们提出了改进的余弦相似度：它的取值范围在$[-1,1]$。

接下来我们来解决第二个问题，如何推荐博客？

先选取k个用户的近邻，利用这k个近邻的阅读排行来做推荐。

其实，这个方法是基于user-based的。它并不是完美的。有两个问题：数据稀疏（用户看过的博客非常少）和算法复杂度高。而这两个问题可以通过item-based方法来解决。具体内容见参考文献基于物品的协同过滤推荐算法——读“Item-Based Collaborative Filtering Recommendation Algorithms”

协同过滤的方法

上面提到的方法是基于领域（记忆）的方法，而还有一类叫基于模型的方法——即隐语义模型。矩阵分解就是实现隐语义模型的成果实现。参考文献个性化推荐中的矩阵分解技术给出了矩阵分解的方法。矩阵分解的核心思想认为用户的兴趣只受少数几个因素的影响，因此将稀疏且高维的User-Item评分矩阵分解为两个低维矩阵，即通过User、Item评分信息来学习到的用户特征矩阵P和物品特征矩阵Q，通过重构的低维矩阵预测用户对产品的评分。

基于内容的推荐

基于内容的推荐是指根据用户的行为来推荐内容。

基于内容推荐的过程： - item Representation:为每个item抽取特征（也就是item的内容）来表示item; - Profile Learning:利用用户过去喜欢（及不喜欢）的item的特征数据，来学习出此用户的喜好特征(profile)； - Recommendation Generation:通过比较上一步得到的用户profile与候选item的特征，为此用户推荐一组相关性最大的item。

上面三个步骤有一张很细致的流程图（第一步对应着Content Analyzer，第二步对应着Profile Learner，第三步对应着Filtering Component）：举个例子，对于博客推荐来说，一个item就是一篇博客； - 第一步，首先从文章内容中抽取文章的特征。常用算法就是利用这篇文章的关键词来代表这篇文章，而每个词对应的权重往往使用tf-idf来计算。利用这种方法，将一篇文章用一个向量来表示即可； - 第二步，根据用户过去喜好来刻画用户profile。最简单的方法可以把用户所有喜欢的文章对应的向量的平均值作为此用户的profile。比如某个用户经常关注与推荐系统有关的文章，那么他的profile中“CB”、“CF”和“推荐”对应的权重值就会较高。 - 第三步，利用所有item与用户profile的相关度进行推荐。一个常用的相关度计算方法是向量的cos夹角。最终把候选item里与此用户最相关（cosine值最大）的N个item作为推荐返回给此用户。

接下来我们来详细了解一下以上三个步骤。 ## item representation 想用属性来描述item时，我们会遇到两种属性： - 结构化(structured)属性：取值固定，例如身高、学历、籍贯等； - 非结构化(unstructured)属性：如文章；

接下来我们针对如何将非结构化的属性转化为结构化属性。我们采用最常用的向量空间模型（Vector Space Model,简称VSM）：已知： - 所有文章集合$D={d_1,d_2,...,d_N}$ - 所有文章中出现的词的集合$T={t_1,t_2,...,t_n}$

目标：用向量表示文章： - 第j篇文章被表示为$d_j={w_{1j},w_{2j},...,w_{nj}}$,其中$w_{nj}$表示第$n$个词在文章$j$中的权重。

最简单的表示权重$w_{nj}$的方式是直接统计出现次数。但一般来说我们还是使用tf-idf： \[TFIDF(t_k,d_j)=TF(t_k,d_j)log \frac{N}{n_k}\] 其中： - $TF(t_k,d_j)$是词频，表示第$k$个词在文章$j$中出现的次数； - $log \frac{N}{n_k}$是逆文档词频，其中$n_k$是所有文章中包括第$k$个词的文章数量；$N$是文章数量。

最终第$k$个词在文章$j$中的权重由下面公式获得： \[w_{k,j}=\frac{TFIDF(t_k,d_j)}{\sqrt{\sum_{s=1}^{|T|}TFIDF(t_k,d_j)^2}}\] 做归一化的好处是不同文章之间的表示向量被归一到一个量级上，便于下面步骤的操作。

Profile Learning

假设用户u已经对一些item给出了他的喜好判断，喜欢其中的一部分item，不喜欢其中的另一部分。那么，这一步要做的就是通过用户u过去的这些喜好判断，为他产生一个模型。有了这个模型，我们就可以根据此模型来判断用户u是否会喜欢一个新的item。所以，我们要解决的是一个典型的有监督分类问题，理论上机器学习里的分类算法都可以照搬进这里。

下面我们简单介绍下CB里常用的一些学习算法： 1. KNN 2. Rocchio 3. 决策树（DT） 4. 线性分类（LC） 5. 朴素贝叶斯（NB）

Recommendation Generation

如果上一步Profile Learning中使用的是分类模型（如DT、LC和NB），那么我们只要把模型预测的用户最可能感兴趣的n个item作为推荐返回给用户即可。而如果Profile Learning中使用的直接学习用户属性的方法（如Rocchio算法），那么我们只要把与用户属性最相关的n个item作为推荐返回给用户即可。其中的用户属性与item属性的相关性可以使用如cosine等相似度度量获得。

基于内容的推荐的优缺点

优点 1. 用户之间的独立性（User Independence）：既然每个用户的profile都是依据他本身对item的喜好获得的，自然就与他人的行为无关。而协同过滤就需要利用很多其他人的数据。因此这种用户独立性带来的一个显著好处是别人不管对item如何作弊（比如利用多个账号把某个产品的排名刷上去）都不会影响到自己。 2. 好的可解释性（Transparency）：如果需要向用户解释为什么推荐了这些产品给他，你只要告诉他这些产品有某某属性，这些属性跟你的品味很匹配等等。 3. 新的item可以立刻得到推荐（New Item Problem）：只要一个新item加进item库，它就马上可以被推荐，被推荐的机会和老的item是一致的。而协同过滤对于新item就很无奈，只有当此新item被某些用户喜欢过（或打过分），它才可能被推荐给其他用户。所以，如果一个纯CF的推荐系统，新加进来的item就永远不会被推荐:( 。这也就是常说的item冷启动问题。

缺点 1. item的特征抽取一般很难（Limited Content Analysis）：如果系统中的item是文档（如个性化阅读中），那么我们现在可以比较容易地使用信息检索里的方法来“比较精确地”抽取出item的特征。但很多情况下我们很难从item中抽取出准确刻画item的特征，比如电影推荐中item是电影，社会化网络推荐中item是人，这些item属性都不好抽。其实，几乎在所有实际情况中我们抽取的item特征都仅能代表item的一些方面，不可能代表item的所有方面。这样带来的一个问题就是可能从两个item抽取出来的特征完全相同，这种情况下基于内容的推荐就完全无法区分这两个item了。比如如果只能从电影里抽取出演员、导演，那么两部有相同演员和导演的电影对于基于内容的推荐来说就完全不可区分了。 2. 无法挖掘出用户的潜在兴趣（Over-specialization）：既然CB的推荐只依赖于用户过去对某些item的喜好，它产生的推荐也都会和用户过去喜欢的item相似。如果一个人以前只看与推荐有关的文章，那基于内容的推荐只会给他推荐更多与推荐相关的文章，它不会知道用户可能还喜欢数码。 3. 无法为新用户产生推荐（New User Problem）：新用户没有喜好历史，自然无法获得他的profile，所以也就无法为他产生推荐了。当然，这个问题协同过滤也有。

参考文献

朴素贝叶斯的理解

发表于 2017-07-15 更新于 2018-12-17 分类于机器学习算法

朴素贝叶斯分类的思想基础

参考文献算法杂货铺——分类算法之朴素贝叶斯分类指出，朴素贝叶斯分类是一种十分简单的分类算法，叫它朴素贝叶斯分类是因为这种方法的思想真的很朴素，朴素贝叶斯的思想基础是这样的：对于给出的待分类项，求解在此项出现的条件下各个类别出现的概率，哪个最大，就认为此待分类项属于哪个类别。通俗来说，就好比这么个道理，你在街上看到一个黑人，我问你你猜这哥们哪里来的，你十有八九猜非洲。为什么呢？因为黑人中非洲人的比率最高，当然人家也可能是美洲人或亚洲人，但在没有其它可用信息下，我们会选择条件概率最大的类别，这就是朴素贝叶斯的思想基础。

将上面的描述形式化描述，就是下面的朴素贝叶斯分类的定义。

朴素贝叶斯分类的定义和求解

设$x={a_1,a_2,...,a_m}$为一个待分类项，其中每个$a$是$x$的一个特征属性。
有类别集合$C={y_1,y_2,...,y_n}$
计算$P(y_1|x),P(y_2|x),...,P(y_n|x)$。(也就是这个特征成为每个类别的概率)
如果$P(y_k|x)=max[P(y_1|x),P(y_2|x),...,P(y_n|x)],则x\in y_k$。(选出一个最可能的类别，将这个类别设为x的类别)

如何计算$P(y_i|x)$?

问题来了，那么我们应该如何计算第3步当中的$P(y_i|x)$呢？

$P(y_i|x)$代表在这个$x$的情况下的类别成为$y_i$的概率，一般来说通过建模$p(y|x)$来预测$y$的模型叫“判别式模型”。但问题在于如果特征数量n较大或者每个特征能取大量值时，基于概率模型列出概率表变得不现实。所以我们修改这个模型使之变得可行。因此我们可以先对联合概率分布$p(x,y)$建模，然后再由此得出$P(y_i|x)$，这样的是“生成式模型”。贝叶斯定理为： \[P(y|x)=\frac{p(x,y)}{p(x)}=\frac{p(y)p(x|y)}{p(x)}\tag{公式0}\]

因此将问题转化成了：如何基于训练数据D来估计先验$p(y)$和似然$p(x|y)$？

$p(y)$是先验概率，表示样本空间中各类样本所占比例；可以通过统计近似得出；
$p(x|y)$是各类样本条件下，所有$x$特征分布的概率。假设特征空间$x$有$d$维，且每一维都有2个取值，那么$x$的取值就有$2^d$种。一般来说这远大于训练样本数m。也就是很多取值是覆盖不到的。所以用频率来估计它不可行，因为“未被观测到”和“与出现概率为0”通常是不同的。

现在问题又来了，如何去估计$p(x|y)$？

估计类条件概率的通用解决方案：先假定其具有某种确定的概率分布形式，再基于训练样本对概率分布的参数进行估计。

问题又转化成了:如何进行参数估计？

为明确起见，我们将$p(x|y)$记作$p(x|θ_y)$。

根据频率学派的思路，我们可以通过极大似然法来估计参数θ。

极大似然估计的核心思想是：我们已知$x$已发生，我们再根据实际情况写出$x$发生的概率$p(x_θ)$。目标函数是使得这个概率$p(x_θ)$最大，然后求得$θ$。

在本问题中，我们有训练样本集$X$，令$X_y$表示训练样本集$X$中第$y$类样本组成的集合，假设这些样本独立同分布。似然函数是某事件发生的概率，也就是$P(X_y|θ_y)$: \[P(X_y|θ_y)=∏_{x\in X_y}P(x|θ_y) \tag{公式1}\] 小注，上式表达的意思是：$在参数θ_y时，第y类样本集X_y发生的概率 = X_y中每个样本x发生的概率的乘积$

我们已经知道$X_y|θ_y$这个事件发生了（因为我们观测到了），那就让这个概率$P(X_y|θ_y)$最大化，去求得一个$θ_y$，这就是我们的最终目标——得到$θ_y$。

如何解出参数？

如上所述，我们现在的目标是求得一个$θ_y$是的公式1最大。而公式1的连乘操作容易造成下溢，因此我们通常使用对数似然： \[LL(θ_y)=log P(X_y|θ_y)\] \[=\sum_{x\in X_y}log P(x|θ_y)\tag{公式2.1}\] 此时我们求得一个$θ_y$，使得公式2.1最大:

\[θ_y=arg_{θ_y} max LL(θ_y)\tag{公式2.2}\]

因此，我们只需要知道$p(x|θ)$,就可以求得各$y$类标签取值下的$θ$，就得到了$x$下各label的概率:$P(x|θ_y)$，也就是$P(x|y)$。代入公式0，我们得到了$P(y|x)$。此时我们就解决了朴素贝叶斯分类的定义的第3步，这样就能进行下一步了。

并没有那么简单

然而，这个问题并没有这么简单。在公式2中我们要求得$θ$。假设$x^{(j)}$有$S_j$个取值，那么每个类别下的$θ_y$就有$∏_{j=1}^nS_j$维。且$y$的取值有$k$个，那就是$k∏_{j=1}^nS_j$，这样就很难算，几乎算不出来。

参数太多，维度爆炸了，怎么办？

因此，朴素贝叶斯分类器用了属性条件独立性假设:对于已知类别，假设所有属性相互独立。

此时，公式0可以改写成： \[P(y|x)=\frac{p(y)p(x|y)}{p(x)}=\frac{p(y)}{p(x)}∏_{i=1}^dP(x_i|y)\tag{公式4}\]

而$p(x)$是样本分布，可以认为是常数，所以忽略。按照我们刚刚推导的步骤，想求得$P(y|x)$，我们就回到了朴素贝叶斯分类的定义的第3步，算出公式2.2:

\[θ_y=arg_{θ_y} max LL(θ_y)=arg max_{y\in Y}P(y)∏_{i=1}^dP(x_i|y)\tag{公式5}\]

之后还有半朴素贝叶斯分类器。我们来日再说。

参考文献

那我们回头看看我们的训练集。训练集是由一个已知分类的集合构成，也就是集合$X$和对应的$y$。也就是说，我们可以通过统计来获得各类别下各特征属性的条件概率估计： $P(a_1|y_1),P(a_2|y_1),...,P(a_m|y_1);$ $P(a_1|y_2),P(a_2|y_2),...,P(a_m|y_2);$ $...,$ $P(a_1|y_n),P(a_2|y_n),...,P(a_m|y_n)$

传统的排序模型

相关度排序模型(Relevance Ranking Model)

重要性排序模型(Importance Ranking Model)

传统排序模型的缺陷

Learning to Rank

L2R特征的选取

L2R训练数据的构造

L2R模型训练

L2R算法分类和简介

PointWise L2R

PairWise

ListWise（文档列表方法）

参考文献

启动/关闭

linux下执行sql脚本

databases操作

tables操作

MYSQL数据类型

相关Leetcode题

Left Join

Combine Two Tables

参考文献

思路

代码

时间复杂度

思路

代码

参考

思想

例子

代码

优化

参考

思想

代码

时间复杂度

思想

代码

改进代码

代码

时间复杂度

思想

步骤：

具体实现：挖坑填数+分治法

代码

时间复杂度

协同过滤推荐算法

简介

实例

nearest-nerghbor算法

协同过滤的方法

基于内容的推荐

Profile Learning

Recommendation Generation

基于内容的推荐的优缺点

参考文献

朴素贝叶斯分类的思想基础

朴素贝叶斯分类的定义和求解

如何计算\(P(y_i|x)\)?

因此将问题转化成了：如何基于训练数据D来估计先验\(p(y)\)和似然\(p(x|y)\)？

现在问题又来了，如何去估计\(p(x|y)\)？

问题又转化成了:如何进行参数估计？

如何解出参数？

并没有那么简单

参数太多，维度爆炸了，怎么办？

参考文献