Apriori算法是数据挖掘中十分经典的算法，在关联度的计算中会经常用到，通过实现来更好的理解Apriori算法。 Apriori定律 1：如果一个集合是频繁项集，则它的所有子集都是频繁项集。举例：假设一个集合{A,B}是频繁项集，即A、B同时出现在一条记录的次数大于等于最小支持度min_support，则它的子集{A},{B}出现次数必定大于等于min_support，即它的子集都是频繁项集。 2：如果一个集合不是频繁项集，则它的所有超集都不是频繁项集。举例：假设集合{A}不是频繁项集，即A出现的次数小于min_support，则它的任何超集如{A,B}出现的次数必定小于min_support，因此其超集必定也不是频繁项集。 只计算了频繁项集的支持度，置信度在后续实现。 该算法主要分为连接和剪枝两个步骤，都在函数getNextCandidate（）中，其中又有许多借助于PHP函数的关键步骤，如：判断子集是否是候选集，判断是否有重复项等等，具体参考代码。 代码如下：
<?php include "readFile.php"; /** * *实现Apriori算法 * @author tju_zyt@tju.edu.cn * */ class Apriori{ public static $dCountMap = array(); //频繁集的记数表 private static $MIN_SUP = 0.2; //最小支持度 private static $MIN_CONF = 0.8; //最小置信度 private static $confCount = array(); //置信度记录表 private static $confItemset = array(); //满足支持度的集合 /** * 算法的第一次迭代，对每个项出现次数计数 * @param $data 存储数据的二维数组 * @return $list 返回候选1项集 */ public function getFristCandiate($data){ $count = array(); for($i = 0; $i < sizeof($data); $i++){ for($j = 0; $j < sizeof($data[$i]); $j++){ if(!in_array($data[$i][$j], $count)) array_push($count, $data[$i][$j]); } } $list = array(); for($i = 0; $i < sizeof($count); $i++){ $arr = array(); array_push($arr, $count[$i]); $list[$i] = $arr; } return $list; } /** * 求出CItemset中满足最低支持度集合 * @param $CItemset 备选集 */ public function getSupportedItemset($data, $CItemset){ $end = true; $supportedItemset = array(); $n = sizeof($CItemset[0])-1;//记录这是第几项集 $k = 0; for($i = 0; $i < sizeof($CItemset); $i++){ $count = $this->countFrequent($data, $CItemset[$i]);//统计记录数 if($count >= self::$MIN_SUP * (sizeof($data) - 1)){ $supportedItemset[$k] = $CItemset[$i]; self::$dCountMap[$n][$k] = $count; $k++; } } //var_dump(self::$dCountMap); return $supportedItemset; } /** * 统计数据库记录data出现 备选集 中的集合的个数 * @param $data 数据表 * @param $list 备选集中的某一项 */ public function countFrequent($data, $list){ $count = 0; for($i = 0; $i < sizeof($data); $i++){ $record = true; for($k = 0; $k < sizeof($list); $k++){ if(!in_array($list[$k], $data[$i])){ $record = false; break; } } if($record){ $count++; } } return $count; } /** * 根据cItemset求出下一级的备选集合组，求出的备选集合组中的每个集合的元素的个数 * 比cItemset中的集合的元素大1 * @param $CItemset * @return $nextItemset */ public function getNextCandidate($CItemset){ $nextItemset = array(); $count = 0; //取出每一项集 for($k = 0; $k < sizeof($CItemset); $k++){ //遍历其他项集的每一个元素，判断是否存在于该项集，如果不存在，则该加入该元素 for($i = $k + 1; $i < sizeof($CItemset); $i++){ for($j = 0; $j < sizeof($CItemset[$i]); $j++){ if(!in_array($CItemset[$i][$j], $CItemset[$k])){ $tmp = $CItemset[$k];//先临时储存，满足条件后在加入进去 //剪枝：即去掉子集不是频繁的项集 if($this->isSubsetInC($tmp, $CItemset[$i][$j], $CItemset)){ array_push($tmp, $CItemset[$i][$j]); //去掉重复项 if(!$this->isHave($tmp, $nextItemset)){ $nextItemset[$count] = $tmp; $count++; } } } } } } return $nextItemset; } /** * 剪枝：即去掉子集不是频繁的项集 * @param $itemset 前一项集的某一项，判断能否加入新项后是否是平凡集 * @param $key 即将加入的一项 * @param $CItemset 前一项集 */ public function isSubsetInC($itemset, $key, $CItemset){ $record = 0; //记录子集匹配的个数 for($i = 0; $i < sizeof($itemset); $i++){ for($j = 0; $j < sizeof($CItemset); $j++){ $subset = $itemset; $subset[$i] = $key;//分别替换掉每一项就是子集 //如果相等，则记录加一 if(sizeof(array_diff($subset, $CItemset[$j])) == 0){ $record++; break; } } } if($record == sizeof($itemset)){ return true; } return false; } /** * 判断将要加入的项是否已经存在是否已经存在 * @param $list 将要加入的项 * @param $itemset 项集 */ public function isHave($list, $itemset){ for($i = 0; $i < sizeof($itemset); $i++){ if(sizeof(array_diff($list, $itemset[$i])) == 0){ return true; } } return false; } } $CItemset = array();//备选集 $lItemset = array();//获取备选集$CItemset满足支持度的集合 $n = 0; $apriori = new Apriori(); $CItemset[$n] = $apriori->getFristCandiate($data); //获取第一次的备选集 $lItemset[$n] = $apriori->getSupportedItemset($data, $CItemset[$n]); //获取备选集$CItemset满足支持度的集合 $flag = true; while ($flag) { $itemset = $apriori->getNextCandidate($lItemset[$n]);// 获取第下一次的备选集 if(sizeof($itemset) == 0){ $flag = false; break; } $CItemset[$n+1] = $itemset; $lItemset[$n+1] = $apriori->getSupportedItemset($data, $CItemset[$n+1]); //获取本次备选集$CItemset满足支持度的集合 $n++; } var_dump($CItemset); var_dump($lItemset); var_dump(Apriori::$dCountMap);文章参考自：http://www.cnblogs.com/fengfenggirl/p/associate_apriori.html#2752667
