经典反超算法

❶ 事业单位考试笔试面试成绩6:4的比例,怎么算反超分差

一般都是笔试成绩和面试成绩的总和做为最后录取的成绩，一般综合成绩的算法为为：笔试成绩×40%﹢面试成绩×60%。

比例内末位考生综合成绩如出现并列，按以下顺序确定进入体检考生：笔试成绩高者,烈士子女或配偶，学历(学位)较高者，具有基层工作经历或基层工作经历较长者。

(1)经典反超算法扩展阅读：

事业单位考试算反超分差是面试分差乘以1.5系数，就是笔试分差乘以1.5等于的数，就是面试反超的出的分数。

事业单位考试又称事业编歼尘制考试，这项工作由各用人单位的人事部门委托省级和地级市的人事厅局所属人事考试中心(事业单位，考试中心命题和组织报名、考试并交用人单位成绩名单，部分单位自行蔽改中命题组织实施)。

尚无全国和全省、市统一招考，最多县级各个单位统一招考 ，一般规模大的采取网络报名，人数少则现场报名。

事业单位，是指国家为了社会公益目的。(《事业单位登记管理暂行条例》国务院第252、411号令)，事业单位不属于政府机构。

一般情况下国家会对这些事业单位予以财政补宏山助，分为全额拨款事业单位、差额拨款事业单位，还有一种是自主事业单位，是国家不拨款的事业单位。

事业单位是国家设置的带有一定的公益性质的机构，但他并不是属于政府机构，而公务员是做为政府机构的。一般情况下事业单位主要是从事医学、教育和文化等方面工作的。

事业单位不是以盈利为主要目的，这就跟企业单位有很大的区别。企业一般是自负盈亏。事业单位的财政通常是由国家予以补助。但让补助也分两个方面，一是全额拨款事业单位，如学校等，二是差额拨款事业单位，如医院等。

❷ 面试官常问十大经典算法排序（用python实现）

算法是一种与语言无关的东西，更确切地说就算解决问题的思路，就是一个通用的思想的问题。代码本身不重要，算法思想才是重中之重

我们在面试的时候总会被问到一下算法，虽然算法是一些基础知识，但是难起来也会让人非常头疼。

排序算法应该算是一些简单且基础的算法，但是我们可以从简单的算法排序锻炼我们的算法思维。这里我就介绍经典十大算法用python是怎么实现的。

十大经典算法可以分为两大类：

比较排序： 通过对数组中的元素进行比较来实现排序。

非比较排序： 不通过比较来决定元素间的相对次序。

算法复杂度

冒泡排序比较简单，几乎所有语言算法都会涉及的冒泡算法。

基本原理是两两比较待排序数据的大小 ，当两个数据的次序不满足顺序条件时即进行交换，反之，则保持不变。

每次选择一个最小（大）的，直到所有元素都被输出。

将第一个元素逐个插入到前面的有序数中，直到插完所有元素为止。

从大范围到小范围进行比较-交换，是插入排序的一种，它是针对直接插入排序算法的改进。先对数据进行预处理，使其基本有序，然后再用直接插入的排序算法排序。

该算法是采用 分治法 对集合进行排序。

把长度为n的输入序列分成两个长度为n/2的子序列，对这两个子序列分别采用归并排序，最终合并成序列。

选取一个基准值，小数在左大数在在右。

利用堆这种数据结构所设计的一种排序算法。

堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。利用最大堆和最小堆的特性。

采用字典计数-还原的方法，找出待排序的数组中最大和最小的元素，统计数组中每个值为i的元素出现的次数，对所有的计数累加，将每个元素放在新数组依次排序。

设置一个定量的数组当作空桶；遍历输入数据，并且把数据一个一个放到对应的桶里去；对每个不是空的桶进行排序；从不是空的桶里把排好序的数据拼接起来。

元素分布在桶中：

然后，元素在每个桶中排序：

取得数组中的最大数，并取得位数；从最低位开始取每个位组成新的数组；然后进行计数排序。

上面就是我整理的十大排序算法，希望能帮助大家在算法方面知识的提升。看懂之后可以去试着自己到电脑上运行一遍。最后说一下每个排序是没有调用数据的，大家记得实操的时候要调用。

参考地址：https://www.runoob.com/w3cnote/ten-sorting-algorithm.html

❸ 数据挖掘十大经典算法之EM

EM（Expectation-Maximum）算法也称期望最大化算法，它是最常见的隐变量估计方法，在机器学习中有极为广泛的用途，例如常被用来学习高斯混合模型（Gaussian mixture model，简称GMM）的参数；隐式马尔科夫算法（HMM）、LDA主题模型的变分推断等等。

EM算法是一种迭代优化策略，由于它的计算方法中每一次迭代都分两步，其中一个为期望步（E步），另一个为极大步（M步），一轮轮迭代更新隐含数据和模型分布参数，直到收敛，即得到我们需要的模型参数。

1. EM算法推导过程

补充知识：Jensen不等式：

如果f是凸函数，函数的期望 大于等于 期望的函数。当且仅当下式中X是常量时，该式取等号。（应用于凹函数时，不等号方向相反）

2. EM算法流程

3. EM算法的其他问题

上面介绍的传统EM算法对初始值敏感，聚类结果随不同的初始值而波动较大。总的来说，EM算法收敛的优劣很大程度上取决于其初始参数。

EM算法可以保证收敛到一个稳定点，即EM算法是一定收敛的。

EM算法可以保证收敛到一个稳定点，但是却不能保证收敛到全局的极大值点，因此它是局部最优的算法，当然，如果我们的优化目标是凸的，则EM算法可以保证收敛到全局最大值，这点和梯度下降法这样的迭代算法相同。

EM算法的简单实例： https://zhuanlan.hu.com/p/40991784

参考：

https://zhuanlan.hu.com/p/40991784

https://blog.csdn.net/u011067360/article/details/24368085

❹ (2)非数值计算常用经典算法

1、交换（两量交换借助第三者） 不借助第三个变量

参考：
http://blog.csdn.net/hackbuteer1/article/details/6531775

2、累加

累加算法的要领是形如“s=s+A”的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为0。
例如：求1+2+3+……+100的和。
sum=0;i=1;
sum=sum+i;
i++;

3、累乘

累乘算法的要领是形如“s=s*A”的累乘式，此式必须出现在循环中才能被反复执行，从而实现累乘功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为1。
例如：求10！
n=10;sum=1;
n>0
sum=sum*n;
n--;

也称为“枚举法”，即将可能出现的每一种情况一一测试，判断是否满足条件，一般采用循环来实现。
例如：用穷举法输出所有的水仙花数（即这样的三位正整数：其每位数位上的数字的立方和与该数相等，比如：13+53+33=153）。

参考：
http://www.cnblogs.com/fanyong/archive/2012/03/23/2413559.html
http://www.cnblogs.com/kkun/archive/2011/11/23/2260312.html

冒泡排序

假设要对含有n个数的序列进行升序排列，冒泡排序算法步骤是：
1、从存放序列的数组中的第一个元素开始到最后一个元素，依次对相邻两数进行比较，若前者大后者小，则交换两数的位置；
2、第一趟结束后，最大数就存放到数组的最后一个元素里了，然后从第一个元素开始到倒数第二个元素，依次对相邻两数进行比较，若前者大后者小，则交换两数的位置；
3、重复步骤1 n-1趟，每趟比前一趟少比较一次，即可完成所求。

（2）选择法排序

选择法排序是相对好理解的排序算法。假设要对含有n个数的序列进行升序排列，算法步骤是：
1、从数组存放的n个数中找出最小数的下标（算法见下面的“求最值”），然后将最小数与第1个数交换位置；
2、除第1个数以外，再从其余n-1个数中找出最小数（即n个数中的次小数）的下标，将此数与第2个数交换位置；
3、重复步骤1 n-1趟，即可完成所求。

（3）插入法排序

要想很好地掌握此算法，先请了解“有序序列的插入算法”，就是将某数据插入到一个有序序列后，该序列仍然有序。插入法排序的要领就是每读入一个数立即插入到最终存放的数组中，每次插入都使得该数组有序。
参考：
http://www.cnblogs.com/fanyong/archive/2012/03/23/2413553.html

**（4）归并排序 **

即将两个都升序（或降序）排列的数据序列合并成一个仍按原序排列的序列。
例如：有一个含有6个数据的升序序列和一个含有4个数据的升序序列，将二者合并成一个含有10个数据的升序序列。

参考： http://blog.csdn.net/cwj649956781/article/details/7409635

（1）顺序查找（即线性查找）

顺序查找的思路是：将待查找的量与数组中的每一个元素进行比较，若有一个元素与之相等则找到；若没有一个元素与之相等则找不到。
例如：任意读入10个数存放到数组a中，然后读入待查找数值，存放到x中，判断a中有无与x等值的数。

（2）折半查找（即二分法）

顺序查找的效率较低，当数据很多时，用二分法查找可以提高效率。使用二分法查找的前提是数列必须有序。
二分法查找的思路是：要查找的关键值同数组的中间一个元素比较，若相同则查找成功，结束；否则判别关键值落在数组的哪半部分，就在这半部分中按上述方法继续比较，直到找到或数组中没有这样的元素值为止。
例如：任意读入一个整数x，在升序数组a中查找是否有与x等值的元素。
参考： http://blog.csdn.net/shuilan0066/article/details/7608096

❺ 关于Multi-Armed Bandit（MAB）问题及算法

地址： Multi-armed bandit

   -  A Problem in which a fixed limited set of resources must be allocated between competing (alternative) choices in a way that maximizes their expected gain, when each choice's properties are only partially known at the time of allocation, and may become better understood as time passes or by allocating resources to the choice.[1]

    - 经典的强化学习算法（ Reinforcement Learning(RL) ），用于处理Exploration-Exploitation（EE） trade-off dilemma。

    - 名字来源于casino中赌博机slot machine（or one armed bandit)

    一个赌徒，要去摇老虎机，走进赌场一看，一排老虎机，外表一模一样，但是每个老虎机吐钱的概率可不一样，他不知道每个老虎机吐钱的概率分布是什么，那么每次该选择哪个老虎机可以做到最大化收益呢？这就是多臂赌博机问题。[2]

     - MAB问题也在 stochastic scheling 领域范畴中。Stochastic scheling problems can be classified into three broad types: problems concerning the scheling of a batch of stochastic jobs ,  multi-armed bandit  problems , and problems concerning the scheling of queueing systems.

     1. 有K台machine，每次选取其中一台pull the lever，该machine提供一个random的reward，每一台machine的reward服从特定的概率分布。

     2. 一个gambler有N次lever pulls的机会，他的目标是使得回报reward最大化，那么他要确定这N次pull 的arm的顺序。显然，作为一个聪明的赌徒，他会记录下每一次得到的reward，试图找出能给出最大reward的那台machine，尽量多次数的去pull这台machine 的arm。

     3. 对于每一轮选择，主要面对的问题是Exploitation-Exploration.

        Exploitation: to pull the arm with Highest expected payoff    OR 

        Exploration: to play other machines to get more information about the expected payoffs of them.

     4. 得到的收益称为reward，一般假设为伯努利分布，即0或1。得到的收益与真实的最大收益（上帝视角，假设一开始就知道哪个payoff最大，那我肯定pull那个arm）之间的差值称为regret。

Online service that benefits from adapting the service to the  indivial sequence of requests,  Ad placement, website optimization, and packeting route.

1. 推荐系统领域，领域有两个经典问题：EE问题和用户冷启动问题。[2]

    EE问题：上面提到过的exploit-explore问题；比如已知某用户对A产品感兴趣，那么在大多数时间要给他推送A的链接才能赚钱，这就是 exploit ；但是为了赚更多的钱，就需要知道他还对哪些产品感兴趣，那么在有些时候就可以尝试一下给他推送B，C，D，E等选择看用户的反应，这就是 explore 。

    用户冷启动问题：面对新用户时如何用尽量少的次数，猜出用户的大致兴趣。[2]

2. 临床测试场景clinical trials

    假设有一批用于治疗某种疾病的新药需要进行测试，目标肯定是在尽量少的测试体上进行尝试，找出效果最好的那一种然后应用于其他病患。由于测试需要等待并观察，尽早找出效果最好的药物类型也有利于救助更多的病患；同时，该方法也有助于减少承受不良药物副作用的测试体数量/增加病患存活率。[3]

在讨论算法之前，首先要明确几种bandit model。根据对于reward过程的不同假设，主要可以分为三种类型： Stochastic  ， Adversarial   and  Markovian。 几种经典的策略与之对应 ， UCB algorithm for the stochastic case，  Exp3 randomized algorithm for theadversarial case， so-called  Gittins indices for the Markovian case.[4]

本文目前主要讨论Stochastic bandits problem（另外两种待以后补充），以下为[4]对其定义：

针对MAB问题常用的基本算法有： -greedy， Boltzmann exploration(Softmax), pursuit, reinforcement comparisonm, UCB1, UCB1-Tuned, Thompson Sampling(TS) [3]

arm    共K个arm

round   共N次机会

： The empirical mean of arm i after t rounds

: The probability of picking arm i at round t

实际操作：每一轮在[0，1]生成一个随机数，如果小于\epsilon，则在K个arm中随机选一个；否则选平均收益最大的那个（如果多个则随机选一个）。

- 为了不记录n歌reward，更高效的办法是对均值做增量式计算，每一轮只记录两个变量：已经尝试的次数和最近的平均reward。

对于constant \epsilon，regret的bound是linear的。

如果\epsilon随着时间减小，regret的bound是poly-logarithmic的。

若摇臂奖赏的不确定性较大，比如概率分布较宽，则需要更多的explore，对应较大的\epsilon。若摇臂奖赏的不确定性较小，比如概率分布集中，则少量的尝试就能很好的近似真实奖赏，只需要较小的\epsilon。

通常让epsilon为一个较小的数如0.1或0.01。 不过，如果尝试次数很大，在一段时间后各个arm的奖赏都能很好近似出来，不需要再explore，这种情况下可以让epsilon随时间逐渐减小，例如

随机系数 ，称为“温度”。 tau越小则平均奖赏高的摇臂被选取的概况更高；趋于0的时候-〉仅利用exploit； 趋于无穷大的时候-〉仅探索explore

与Pursuit Algorithm类似，RC方法的行为也不是直接由empirical means计算而来。该方法同时还保留一个平均预期回报（average expected reward） ，将平均回报和预期回报作比较。

- 如果 empirical mean 〉average expected reward，选该arm的概率上升。

- 如果empirical mean〈 average expected reward，选该arm的概率下降。

- 对于arm i 存在偏好（preference） , 每一轮preference会根据结果进行更新：

    含有参数： ( The empirical mean of arm  i  after  t  rounds

                        the number of times that arm i has been played after t rounds

    1、初始化: 所有arm都被play一次。

    2、选择arm j(t)：

    3、观察选择结果，更新t和ni。其中加号前面是这个臂到目前的收益均值，后面的叫做bonus，本质上是均值的标准差

这个公式反映一个特点：均值越大，标准差越小，被选中的概率会越来越大。被选次数较少的臂虽然可能均值不大，但根号那一项会比较大，也会得到试验机会。

将每个arm的variance引入了考虑

核心思想：[2]

    1. 假设每个arm产生收益的概率p符合 Beta（wins，lose）分布，两个参数wins和lose。

    2. 每个arm 维护（maintain）一对beta分布的参数。每次实验选一个arm摇一下，有收益该arm的wins+=1 ， 否则 lose+=1

    3. 每次选arm的方式：用每个arm的beta分布产生一个随机数b，选择所有arm产生的随机书最大的那个arm去摇。

beta（a，b）有a和b两个参数，两个参数决定了分布形状。

a+b的值越大，分布曲线就越集中，反之则越疏远（两边大中间小）

当a/(a+b)的值越大，分布集中位置的中心越靠近1，反之越靠近0，这样产生的随机数位置也相应更容易靠近1或0

因此，Beta分布总体有三种情况，曲线很窄靠近1、曲线很窄靠近0、曲线很宽

由此，若把Beta分布的参数a看做推荐后得到用户点击的次数，把b看做未得到用户点击的次数，如下：

取出每一个候选对应的a和b

为每个候选用a和b作为参数，用Beta分布产生一个随机数

按照随机数排序，输出最大值对应的候选

观察用户反馈，如果用户点击则将对应候选的a增加1，反之b增加1

因此在推荐系统中，为每个用户都保存一套参数，每个用户对应每个物品都保存一份a和b

- 为什么有效？

如果候选被选中次数很多，那么a+b分布变窄，换句话说这个候选的收益已经确定，用它产生随机数，基本就在分布的中心位置附近，接近这个分布的平均收益

如果一个候选不但a+b很大，且a/(a+b)也很大，那么就是一个好的候选项，平均收益很好，每次选择占据优势，就进入利用阶段，反之则几乎再无出头之日

如果一个候选项的a+b很小，分布很宽，就是没有给充分的探索次数，此时不能确定好坏，那么这个较宽的分布有可能得到一个较大的随机数，在排序时被优先输出，给予次数做探索

[Notes]Regret Analysis of Stochastic and Nonsto... -

腾讯QQ大数据：神盾推荐——MAB算法应用总结 | 互联网数据资讯中心-199IT | 中文互联网数据研究资讯中心-199IT

小白都能看懂的softmax详解 - bitcarmanlee的博客 - CSDN博客

bandit算法原理及Python实现 - 新颜_USTC - CSDN博客

Contextual Bandit算法在推荐系统中的实现及应用 - 知乎 （比较详细介绍了LinUCB的思想和实现）

    这个系列太值得读了！从整体框架到细节，还有各种资源！ 比之前看到的都好多了！    

[1] https://en.wikipedia.org/wiki/Multi-armed_bandit

[2] Bandit算法与推荐系统： https://blog.csdn.net/heyc861221/article/details/80129310

[3] Kuleshov，Precup. Algorithms for the multi-armed bandit problem. Journal of Machine Learning Research.

[4] Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit

[5] https://blog.csdn.net/lyx_yuxiong/article/details/81237416

❻ 数据挖掘的十大经典算法，总算是讲清楚了，想提升自己的赶快收藏

一个优秀的数据分析师，除了要掌握基本的统计学、数据分析思维、数据分析工具之外，还需要掌握基本的数据挖掘思想，帮助我们挖掘出有价值的数据，这也是数据分析专家和一般数据分析师的差距所在。

国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART.

不仅仅是选中的十大算法，其实参加评选的18种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖掘领域都产生了极为深远的影响。今天主要分享其中10种经典算法，内容较干，建议收藏备用学习。

1. C4.5

C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：

1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；

2) 在树构造过程中进行剪枝；

3) 能够完成对连续属性的离散化处理；

4) 能够对不完整数据进行处理。

C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效（相对的CART算法只需要扫描两次数据集，以下仅为决策树优缺点）。

2. The k-means algorithm 即K-Means算法

k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k < n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均 方误差总和最小。

3. Support vector machines

支持向量机，英文为Support Vector Machine，简称SV机（论文中一般简称SVM）。它是一种监督式学习的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更 高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。一个极好的指南是C.J.C Burges的《模式识别支持向量机指南》。van der Walt 和 Barnard 将支持向量机和其他分类器进行了比较。

4. The Apriori algorithm

Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。

5. 最大期望(EM)算法

在统计计算中，最大期望（EM，Expectation–Maximization）算法是在概率（probabilistic）模型中寻找参数最大似然 估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variabl）。最大期望经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。

6. PageRank

PageRank是Google算法的重要内容。2001年9月被授予美国专利，专利人是Google创始人之一拉里·佩奇（Larry Page）。因此，PageRank里的page不是指网页，而是指佩奇，即这个等级方法是以佩奇来命名的。

PageRank根据网站的外部链接和内部链接的数量和质量俩衡量网站的价值。PageRank背后的概念是，每个到页面的链接都是对该页面的一次投票， 被链接的越多，就意味着被其他网站投票越多。这个就是所谓的“链接流行度”——衡量多少人愿意将他们的网站和你的网站挂钩。PageRank这个概念引自 学术中一篇论文的被引述的频度——即被别人引述的次数越多，一般判断这篇论文的权威性就越高。

7. AdaBoost

Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器 (强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权 值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。

8. kNN: k-nearest neighbor classification

K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

9. Naive Bayes

在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和朴素贝叶斯模型（Naive Bayesian Model，NBC）。 朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。

同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，NBC模型与其他分类方法相比具有最小的误差率。 但是实际上并非总是如此，这是因为NBC模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给NBC模型的正确分类带来了一定影响。在属 性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型。而在属性相关性较小时，NBC模型的性能最为良好。

10. CART: 分类与回归树

CART, Classification and Regression Trees。 在分类树下面有两个关键的思想。第一个是关于递归地划分自变量空间的想法（二元切分法）；第二个想法是用验证数据进行剪枝（预剪枝、后剪枝）。在回归树的基础上的模型树构建难度可能增加了，但同时其分类效果也有提升。

参考书籍：《机器学习实战》