分类 算法 下的文章

Sprague–Grundy theorem


翻译自维基

定义

Sprague-Grundy理论针对信息充分、满足结束条件(所有游戏都有结果:不存在无限循环的游戏)和正常游戏条件(不能移动的玩家失败)的双人游戏。 类似于Nim这样完全公平的游戏,任何时刻每个玩家都有完全一样的可行步骤。而对于tic-tac-toe(井字棋),象棋这些游戏不是完全公平游戏。在象棋里,玩家只能移动自己的棋子,不能移动对方的棋子。而在tic-tac-toe中,一名玩家画X,另一名玩家只能画O。公平游戏只有两类结果:要么先手赢(N-position),要么后手赢(P-position). 在这个证明里,一个状态由当前状态能一步到达的状态集合确定(这些状态称为选项)。例如,状态{}是一个P-position(必败态),在正常游戏里,当前玩家因为不能移动而失败。而状态则相反,是一个N-position(必胜态);当前玩家只有一个选择,而这个转移对于对方是一个必败状态。 一个nimber是一个特殊状态用*n表示序数n.*0是{}。其他nimber类似地由*(n+1)=*n∪{*n};此外,*1={*0},*2={*0,*1}等。因此*n对应一个有n个数的nim堆。 两个状态G和H能够组合成一个新状态G+H在当前玩家能够选择移到状态G或H的组合游戏中。集合G+H用规则G+G={G+h|h∈H}∪{g+H|g∈G}计算, 这个规则表明状态叠加是可交换和可结合的。 两个状态G和G'被认为相等当且仅当,对于每个状态H,状态G+H和G'+H有相同结果,写为G≈G'。


FP-growth算法简介


  参考:FP-growth

  FP-growth算法是一种高效的频繁集挖掘算法。它基于Apriori,但不同之处在于将数据集存储在FP树结构中,从而加快执行效率。FP-growth只需要对数据进行两次扫描,Apriori对潜在的频繁项集都会扫描,从而降低了效率。

  那么什么是FP数结构?


Apriori关联算法简介


Wiki链接:关联规则

  Apriori算法是基于关联分析的产生算法,关联分析即从数据集中寻找物品的隐含关系。比如超市对顾客的购买记录数据库进行关联规则挖掘,可以发现顾客的购买习惯。经典的有购物篮分析。Apriori算法提供了一种更高效的搜寻方法。   Apriori算法的主要作用在于发现频繁项集和关联规则,首先需要发现频繁项集(链接)。Apriori算法接受接受两个参数,最小支持度和数据集,通过扫描数据集发现满足最小支持度的项集。


K-均值聚类算法


Wiki百科:K-平均算法

  K-均值聚类算法是一种无监督的机器学习算法,所谓无监督简单来说就是事先不告诉计算机需要做什么让其主动学习,具体来说,就是设计分类器时候,让程序处理未被分类标记的样本集。   K-均值聚类算法同时是聚类方法的一种,而聚类是将不同数据划分为相同特征集合的一种方式。K代表了数据集的数目。


用AdaBoost元算法提高分类性能


维基百科:AdaBoost

  首先介绍一下元算法,它是对其它算法进行组合的一种方式,而AdaBoost就是其中一种元算法。   在分类过程中我们可以将不同的方法进行组合,无论是kNN还是朴素贝叶斯,它们的组合叫做集成方法或者元算法,这既可以是一种算法的不同设置,也可以是不同算法的分配。   boosting方法从原始数据集选择S次后获得S个新数据集,是通过集中关注已有分类器错分的数据来获得新的分类器,分类器中的权重并不相同,权重代表的是上一轮迭代的成功度。Adaboost只是其中一个版本。