介绍一种经典的算法,最好的算法是,介绍一种经典的算法,最好的算法英语

　　数据挖掘的十大经典算法：KNN，C4.5，朴素贝叶斯，CART，SVM，Kmeans，PageRank，AdaBoost，EM，Apriori

　　一些被引用的博客已被标记。

　　关联规则简介关联规则分析：目的是找出一个数据集中项目之间的关联关系，这些关联关系在数据集中是无法直接展现的。

　　购物篮分析是关联规则的一个著名应用：例如，一家超市的经理想更多地了解顾客的购物习惯，如“一次购买中同时购买了哪组商品”或“顾客三个月后购买数码相机的概率是多少”。如果发现顾客买面包就很有可能买牛奶，那么给出一个关联规则“面包==牛奶”。其中，面包不是第一项，但牛奶也不是最后一项。通过降低面包的售价，促进销售，适当提高牛奶的售价，关联的牛奶可能会增加超市的整体利润。

　　国内外应用1目前，关联规则挖掘技术在西方金融企业已经得到了广泛的应用，它可以成功地预测银行客户的需求。一旦获得这些信息，银行就可以改进自己的营销。现在，银行每天都在开发与客户沟通的新方式。每家银行都将客户可能感兴趣的产品信息捆绑在自己的ATM机上，以便使用其ATM机的用户能够了解这些信息。如果数据库显示某个信用额度高的客户更改了地址，那么很有可能该客户最近买了更大的房子，所以有可能他需要一张新的信用额度更高、更高端的信用卡，或者需要住房改善贷款。所有这些产品都可以通过信用卡账单邮寄给客户。当客户打电话咨询时，数据库可以有效地帮助电话销售代表。销售代表的电脑屏幕可以显示客户的特征，同时也可以显示客户会对什么产品感兴趣。

　　其中，我们熟知的例子如：2

　　(1)沃尔玛的尿布和啤酒

　　(2)超级市场的牛奶和面包

　　(3)百度文库推荐相关文档。

　　(4)淘宝推荐相关书籍。

　　(5)可能的治疗组合的医学建议

　　(6)银行推荐相关业务。

　　这些都是商业智能和关联规则在现实生活中的应用。

　　然而，目前在中国，“数据海量，信息匮乏”是商业银行在数据集中后普遍面临的尴尬。目前金融行业实现的大部分数据库只能实现数据录入、查询、统计等底层功能，无法在数据中找到各种有用的信息。例如，通过分析这些数据，我们可以发现它们的数据模式和特征，然后我们可以发现某个客户、消费群体或组织的金融和商业利益，观察金融市场的变化趋势。可以说，国内对关联规则挖掘技术的研究和应用还不是很广泛。

　　近年来，由于许多应用问题往往比超市采购问题更复杂，大量研究从不同角度对关联规则进行了扩展，将更多的因素融入到关联规则的挖掘方法中，从而丰富了关联规则的应用领域，拓宽了支持管理决策的范围。例如，考虑属性之间的类别层次关系、时态关系和多表挖掘。近年来，对关联规则的研究主要集中在两个方面，即扩大经典关联规则能解决问题的范围，提高经典关联规则挖掘算法的效率和规则的兴趣度。

　　常用的关联规则算法

　　Apriori算法是挖掘布尔关联规则频繁项集最有影响力的算法之一。许多挖掘算法都是在Apriori算法的基础上改进的，如基于Hash的方法、基于数据划分的方法、不产生候选项集的FP-GROWTH方法等。所以，要理解关联规则算法，首先要理解Apriori算法。

　　现实中的Apriori算法，一个销售的例子：提取关联规则最大的困难是商品的品类很多，导致商品有大量可能的组合。各种关联规则算法的目标是从不同方面减少可能的搜索空间和扫描数据的数量。

　　Apriori算法：挖掘频繁项集最经典的算法，第一次从大数据集中提取关联规则。核心思想是通过连接生成候选项及其支持度，然后通过剪枝生成频繁项集。

　　关联规则和频繁项集关联规则的一般形式：

　　mhdj和B同时出现的概率就是关联规则的支持度(相对支持度)。

　　mhdj出现和项集B出现的概率就是关联规则的置信度。

　　最低支持和最低信心

　　最低支持度：用户或专家确定的衡量支持度的阈值，表明项目集的最低统计重要性；

　　最小置信度：用户或专家定义的衡量置信度的阈值，表示关联规则的最低可靠性。

　　同时满足最小支持度阈值核心最小置信度阈值的规则称为强规则项集。

　　包含K个项目的项目集称为K项目集：示例集{牛奶、谷物、糖}是一个包含3个项目的集合。

　　项目集的出现概率是包含项目集的所有事务的计数，称为绝对支持度(支持度计数)。

　　频繁项集：如果项集I的相对支持度满足预定义的最小支持度阈值，则I为频繁项集，频繁K项集记录为K支持度计数。

　　如果支持度已知，则可以从所有交易中统计出规则A==B的支持度的核心置信度以及mhdj和mhdjB的支持度：ps:图中的支持度应为P(B/A)，表示在A的前提下B发生的概率。

　　上图：输入：所有事务的个数，A，B，A B的支持数。

　　输出：关联规则A==B and B==A=a

　　置信度公式：分子是包含mhdjB的交易数，分母是mhdj的交易数。Apriori算法流程

性质

　　频繁项集的所有非空子集(支持度必须大于或等于给定的最小支持度阈值)也必须是频繁项集。

　　当事务A被添加到非频繁项集I的项集时，新的项集IA一定不是频繁项集。

　　*实施过程

　　1.找出所有频繁项集，通过连接步骤和剪枝步骤进行融合，得到最大频繁项集Lk。

　　-连接步骤

　　目的：找出k项集。

　　(1)对于给定的最小支持度阈值，消除一个候选集C1，得到一个频繁集L1；

　　(2)连接L1本身生成两个候选集C2，保留C2中满足约束条件的项集，得到两个项集L2；

　　(3)连接L2和L1，生成三个候选集C3，保留C3满足约束条件的项目集L3。

　　(4)循环得到最大频繁项集Lk。

　　-修剪步骤

　　接下来，连接步骤在生成候选Ck的过程中起到减少搜索空间的作用。

　　Ck由Lk-1和L1之间的连接产生。根据Apriori性质，Ck中不会存在不满足的项集，即剪枝。

　　2.从频繁项集生成强关联规则，从1中得到满足最小置信度阈值的频繁项集，从而挖掘强关联规则。

　　例子下面是一个例子，让算法过程更容易理解。

　　数据库中的一些订购数据：

　　上表是交易数据，整理关联规则模型需要的数据结构是交易数据集。

　　假设：交易数据集为10个订单，设置支持度S=0.2(支持度计数2)，菜品{18491，8842，8693，7794，8705}记为{a，b，c，d，e}

　　流程：

　　找出k项的最大频繁集

　　1)共有10个事务，每个事务都是候选项集C1的成员，计算每个项的支持度：P({a})=项集{a}支持度计数/所有事务数=7/10=0.7；将C1中的每个支持度与集合支持度S进行比较，得到一个频繁集合L1，如上图第一行所示。

　　2)扫描所有事务，连接L1和L1，得到候选2-项集C2，计算每个项的支持度：P({a，b})=项集的支持度数{a，b }/所有事务数=5/10=0.5，然后剪枝：C2的每个L1都是频繁集，没有一个项集从C2删除。

　　3)将C2各集的支持度与预设的S进行比较，得到如上图所示的L2。

　　4)扫描所有事务，连接L2和L1得到候选3项集C3，计算每一项的支持度：P({a，b，c})=项集的支持度计数{a，b，c}/所有事务数=3/10=0.3，然后剪枝：L2和L1连接的所有项集：{a，b，c }根据Apriori算法的性质，因为{b，d}、{b，e}和{c，d}不在L2，所以剔除。C3中的最终项集是{a，b，c}，{a，c，e}。

　　5)计算C3的支持度，过滤得到三个频繁集L3。

　　6)L3和L1连接得到4个候选集，剪枝后为空。终止。

　　结果：L1、L2和L3都是频繁项集，L2是最大频繁项集的关联规则。

　　根据置信度公式生成关联规则：第一条：顾客点A菜和B菜的概率为50%，点A菜和B菜的概率为71.428%。

　　算法优缺点：简单易懂，对数据要求低。

　　算法缺点：I/O负载重，导致候选项目集过多。

　　应用：消费市场价格分析，入侵检测，移动通信。

　　代码实现对实际数据使用Apriori算法。不给数据集的都是流氓：kosarak.dat

　　数据集：新闻网站点击流的数据集。每行包含某个用户浏览的新闻报道。新闻报道编码成整数(新闻ID)，共有99万条。

　　示例：用户浏览的所有新闻id，用空格分隔。

　　目的：挖掘热门新闻报道，使用Apriori或FP-growth算法挖掘频繁项集，看哪些新闻id被用户广泛关注。

　　包装：