跳至主要内容

A-Priori 笔记

A-Priori算法

目的

寻找频繁项集

概念

假设有集合 I 和 j，有关联规则 R =>( I -> j )

频繁项集

一个子集，在多个集合中出现，并且出现次数大于支持度，就是一个频繁项集合

如果项集 I 是频繁的，那么其所有的子集都是频繁的

支持度

区分是否频繁的值，一般会定义得很大，使得频繁集合（二元，三元）只占有原来集合的1%

可信度

对于关联规则 R，集合I U { j } 的支持度与 I 的支持度的比值

就是说规则是否能成立，有点像新词发现，只要 I 出现，j 就出现

兴趣度

对于关联规则 R, 可信度及包含 j 的集合比率之间的差值

就是说规则有没有能引起人的兴趣，接近0就没趣了，正数表示吸引，负数表示互斥

算法过程

  1. 遍历一遍编号1~n
  2. 找出频繁的单项物品1~m(m<n)
  3. 两两组合成二元集合，组合的两个项必须都是频繁的（单调性）
  4. 根据计数器，找出二元集合中的频繁项对
n元上的A-Priori算法
  • L(k): 有k个元素的集合，这个集合是频繁的，当C(k)的频繁度>s(支持度)，C(k) => L(k)
  • C(k): 有k个元素的集合，其中任意k-1个元素的集合都是L(k-1)

优化

hash 频繁桶

利用hash的性质，hash到一个桶中的集合有自己的频繁度计数器pc，对于同一个桶 sum(pc) < s,那么桶内的集合都不是频繁的

可以多进行一次hash频繁桶来降低扫描数量，当一个集合同时出现在第一次和第二次的hash频繁桶中，这个集合才有可能频繁

son算法

这个算法属于抽样算法中的优化，可以派出所有伪反例和伪正例

mapreduce计算

第一次：

  • map: in_key => 购物篮集合中的一个子集, in_value => no
    out_key => 频繁度 > ps 的候选项目对
  • p为这个map分到的集合的比例, 可以证明，如果是频繁项，至少有一个map会传递它给reduce
  • reduce： 输出候选值

第二次：

  • map: in => 候选集合+部分原来购物车数据(或购物车数据) out_key => 候选集合，out_value => 频繁度
  • reduce: 统计工作
标签：

评论

发表评论

此博客中的热门博文

Spark 矩阵相乘实现

矩阵相乘计算的意义十分重要，比如我们做数据分析经常使用到的join操作就可以理解成为矩阵相乘的一个部分，矩阵相乘在很多分布式计算框架都有自己的实现，这些实现也可以根据不同大小的矩阵做不同的优化，比如在MapReduce上就有两种基本的实现： 大矩阵乘小矩阵 我可以把小矩阵放到DistrubutedCache，让每个mapper读取，这就是hive的MapJoin的实现。 两个大矩阵相乘 相乘中两个矩阵都是超大矩阵的话，为了减少MapReduce过程中产生的巨大数据，使用的带宽。都会采用矩阵分块的做法，以下会详细介绍这种实现方法。 Spark介绍 官网介绍 超大矩阵拆分计算方法 单机（单线程）矩阵相乘 假设有矩阵 A ， B ，相乘的结果为 C ，那么相乘的伪代码： C = 0 for(i <- 0 to A.lenght) for(k <- 0 to A[i].lenght) if(A[i][k]!=0) for(j <- B[k].lenght) { C[i][j] += A[i][k] * B[k][j] } 单机的计算中，时间复杂度是 O(n^3)，如果 n 增长到一定程度的时候，那么计算用时就会非常大，所以下面会说一下并行计算方法。 并行矩阵相乘 在计算的过程中，我们很容易发现每个 A[i][k] * B[k][j] 都可以单独计算，因此我也可以单独计算这些组合，最后做一个累计就可以获得 C 矩阵了，相乘伪代码如下： A = ((row, column), value) => (column, (row, value)) B = ((row, column), value) => (row, (column, value)) Temp = A.join(B) => (k, (rowA, valueA), (columnB, valueB)) => ((rowA, columnB), valueA * valueB) => ((rowC, columnC), valueC) C = Temp.reduceByKey =...
发表评论
阅读全文

iphone 自动打包脚本

最近做ios开发，经常需要给老大打ipa包，这个虽然在xcode中编译并打包是很简单的事，不过每次都得花几分钟的时间做一些手动的放入Payload并压缩成zip包的操作。比较麻烦的是，在开发过程中，突然就说要一个可以执行的包做测试。那么，思路断了，正在写的代码要注释掉，这样持续下去浪费的时间会很多，所以还是需要写一个打包脚本。 打包具体用到的命令是这些： xcodebuild: 主要用于编译项目 xcrun: 主要用于打ipa包 具体打包流程就是编译，然后打一个发布包，一个ipa包，其实用脚本来说话就好了。另外，我用一个conf.dat来存放target和configuration,这些都在xcode里面指定好了，用xxx:xxx这样的格式来存放，xcodebuild在编译的时候会自动找到对应的配置。 打包脚本如下: #!/bin/sh basePath=`pwd` distDir="target" distDir="${basePath}/${distDir}" rm -rdf "$distDir" mkdir -p "$distDir" baseName="xxx" #.app 的名字 projectDir=$(cd ../mobile/xxx; pwd) # 进入xcode工程目录 cd $projectDir for line in $(cat ${basePath}/conf.dat) do targetName=`echo $line | cut -f1 -d':'` conf=`echo $line | cut -f2 -d':'` releaseDir="${projectDir}/build/${conf}-iphoneos" rm -rdf "$releaseDir" echo "======build ${baseName}.app start..." echo "======clean ${conf}..." xcodebuild clean -configuration "$...
发表评论
阅读全文

【转】ELO-对弈与排名（有触感的排名）

原文： https://www.cnblogs.com/leoin2012/p/4854442.html ELO介绍 ELO等级分制度 是指由 匈牙利 裔 美国 物理学家 Elo创建的一个衡量各类对弈活动水平的评价方法，是当今对弈水平评估的公认的权威方法。被广泛用于 国际象棋 、 围棋 、 足球 、 篮球 等运动。网络游戏 英雄联盟 、 魔兽世界 内的竞技对战系统也采用此分级制度。 历史 ELO等级分制度是基于 统计学 的一个评估棋手水平的方法。 美国 国际象棋 协会在1960年首先使用这种计分方法。由于它比先前的方法更公平客观，这种方法很快流行开来。1970年国际棋联正式开始使用等级分制度。 Elo模型原先采用 正态分布 。但是实践显明棋手的表现并非呈正态分布，所以现在的等级分计分系统通常使用的是 Logistic distribution 。 计分方法 假设棋手A和B的当前等级分分别为 和 ，则按Logistic distribution A对B的胜率期望值当为 类似B对A的胜率为 假如一位棋手在比赛中的真实得分 （胜=1分，和=0.5分，负=0分）和他的胜率期望值 不同，则他的等级分要作相应的调整。具体的数学公式为 公式中 和 分别为棋手调整前后的等级分。在大师级比赛中 通常为16。 例如，棋手A等级分为1613，与等级分为1573的棋手B战平。若K取32，则A的胜率期望值为 ，约为0.5573，因而A的新等级分为1613 + 32 · (0.5 − 0.5573) = 1611.166 国际象棋中的等级分 国际象棋中，等级分和棋联称号的大致对应为 2500分以上：国际特级大师 2400-2499分：国际大师 2300-2399分：棋联大师  
发表评论
阅读全文