所谓物以类聚-人以群分,“类”指的是具有相似性的集合,聚类是指将数据集划分为若干类,使得各个类之内的数据最为相似,而各个类之间的数据相似度差别尽可能的大。聚类分析就是以相似性为基础,在一个聚类中的模式之间比不在同一个聚类中的模式之间具有更多的相似性。对数据集进行聚类划分,属于无监督学习。
K-Means是最常用且简单的聚类算法,最大特点是好理解,运算速度快,时间复杂度近于线性,适合挖掘大规模数据集。但是只能应用于连续型的数据,并且一定要在聚类前需要手工指定要分成几类;
K-Means采用距离作为相似性指标,从而发现给定数据集中的K个类,且每个类的中心是根据类中所有数值的均值得到的,每个类的中心用聚类中心来描述。对于给定的一个(包含n个一维以及一维以上的数据点的)数据集X以及要得到的类别数量K,选取欧式距离作为相似度指标,聚类目标是使得类的聚类平方和最小,即最小化:
关联规则挖掘可以让我们从数据集中发现项与项之间的关系,它在我们的生活中有很多应用场景,“购物篮分析”就是一个常见的场景,这个场景可以从消费者交易记录中发掘商品与商品之间的关联关系,进而通过商品捆绑销售或者相关推荐的方式带来更多的销售量。
2、关联规则中重要的概念
我举一个超市购物的例子,下面是几名客户购买的商品列表:
支持度是个百分比,它指的是某个商品组合出现的次数与总次数之间的比例。支持度越高,代表这个组合出现的频率越大。
我们看啤酒出现了3次,那么5笔订单中啤酒的支持度是3/5=0.6。同理,尿布出现了5次,那么尿布的支持度是5/5=1。尿布和啤酒同时出现的支持度是3/6=0.6。
它指的就是当你购买了商品 A,会有多大的概率购买商品 B。
我们可以看上面的商品,购买尿布的同时又购买啤酒的订单数是3,购买啤酒的订单数是3,那么(尿布->啤酒)置信度= 3/3=1。
再看购买了啤酒同时购买尿布的订单数是3,购买尿布的订单数是5,那么(啤酒->尿布)置信度=3/5=0.6。
提升度代表的是“商品 A 的出现,对商品 B 的出现概率提升的”程度。所以我们在做商品推荐的时候,重点考虑的是提升度。
那么我们来计算下尿布对啤酒的提升度是多少:
怎么解读1.67这个数值呢?
其实看上面提升度的公式,我们就可以理解,也就是AB同时出现的次数越多,单独出现B的次数越少,那么支持度也就越大也就是B的出现总是伴随着A的出现,那么A对B出现的概率就越有提升!
我们一起来看下经典的关联规则 Apriori 算法是如何工作的。
Apriori 算法其实就是查找频繁项集 (frequent itemset) 的过程,所以我们需要先了解是频繁项集。
频繁项集就是支持度大于等于最小支持度阈值的项集,所以小于最小值支持度的项目就是非频繁项集,而大于等于最小支持度的项集就是频繁项集。
假设我随机指定最小支持度是0.2。首先,我们先计算单个商品的支持度:
因为最小支持度是 0.2,所以你能看到商品 鸡蛋 是不符合最小支持度的,不属于频繁项集,于是经过筛选商品的频繁项集如下:
在这个基础上,我们将商品两两组合,得到两个商品的支持度:
筛选大于最小支持度(0.2)的数据后:
在这个基础上,我们再将商品三个组合,得到三个商品的支持度:
筛选大于最小支持度(0.2)的数据后:
在这个基础上,我们将商品四个组合,得到四个商品的支持度:
再次筛选大于最小支持度(0.2)数据的话,就全删除了,那么,此时算法结束,上一次的结果就是我们要找的频繁项,也就是{牛奶、面包、尿布}、{面包、尿布、啤酒}。
我们来总结一下上述Apriori算法过程:
我们可以看到 Apriori 在计算的过程中有以下几个缺点:
这就好比我们数据库中的“全表扫描”查询一样,非常浪费IO和时间。在数据库中我们都知道使用索引来快速检索数据,那Apriori 能优化吗?
FP-growth算法是基于Apriori原理的,通过将数据集存储在FP树上发现频繁项集,但不能发现数据之间的关联规则。FP-growth算法只需要对数据库进行两次扫描,而Apriori算法在求每个潜在的频繁项集时都需要扫描一次数据集,所以说Apriori算法是高效的。其中算法发现频繁项集的过程是:(1)构建FP树;(2)从FP树中挖掘频繁项集。
概念知识不在这凑字数了,我们直接来干货!假设我们从以下数据中来挖掘频繁项。
首先创建,项头表,这一步的流程是先扫描一遍数据集,对于满足最小支持度的单个项按照支持度从高到低进行排序,这个过程中删除了不满足最小支持度的项(假设最小支持度是0.2)。
整个流程是需要再次扫描数据集,对于每一条数据,按照支持度从高到低的顺序进行创建节点(也就是第一步中项头表中的排序结果),节点如果存在就将计数 count+1,如果不存在就进行创建。同时在创建的过程中,需要更新项头表的链表。
先把原始数据按照支持度排序,那么原始数据变化如下:
下面我们把以上每行数据,按照顺序插入到FP树中,注意FP树的根节点记为 NULL 节点。
接下来插入第二行数据,由于第二行数据第一个数据也是B,和已有的树结构重合,那么我们保持原来树结构中的B位置不变,同时计数加1,C、D是新增数据,那么就会有新的树分叉,结果如下图:
以此类推,读取下面的三行数据到FP树中。
最后生成的FP数如下:
我们终于把FP树建立好了,那么如何去看这颗树呢?得到 FP 树后,需要对每一个频繁项,逐个挖掘频繁项集。具体过程为:首先获得频繁项的前缀路径,然后将前缀路径作为新的数据集,以此构建前缀路径的条件 FP 树。然后对条件 FP 树中的每个频繁项,获得前缀路径并以此构建新的条件 FP 树。不断迭代,直到条件 FP 树中只包含一个频繁项为止(反正我第一次看完这句话是没理解)。
FP树是从下往上看了,也就是根据子节点找父节点,接下来还是来图解~
首先,我们看包含A的频繁项:
我们可以看到包含A的树有两个,我们先看树2,可以得到路径{B:2,C:2},此处的2是根据A出现的次数定的。接着我们创建FP树,具体的创建过程和上面创建 FP 树的过程一样,如下图:
注意此时头指针表中包含两个元素,所以对每个元素,需要获得前缀路径,并将前缀路径创建成条件 FP 树,直到条件 FP 树中只包含一个元素时返回。
同理,我们来看树1,树1比较简单,就一个路径{B:1},根据上述方法我们得到此分支频繁项为{A:1,B:1},{A:1}。
经典的算法,很多大神已经实现,我们直接拿来用就行了,比如上面的FP-GROWTH算法,介绍一款专门的包pyfpgrowth。
(机器学习图谱+机器学习十大算法)
回复【226】即可领取
《机器学习资料包》概览
--Oracle数据库中的表备份: --备份语句:在备份之后就可以将这张表的所有数据源删除了,但是之后有人对这张表的数据进行操作,但是在操作完成之后要记得将数据表恢复 CREATE TABLE DZH ...