本文假设读者至少有对数据挖掘中的关联规则有基本了解,对Apriori算法的实现有一定了解。
在此基础上,我们讨论一种比Apriori更加高效的关联规则挖掘方法——基于FP-Tree的关联规则挖掘。
(一) 关于Apriori:
Apriori是关联规则挖掘中最最最经典的算法,没有之一。同时,它也是向初学同学阐明关联规则精髓的最佳武器。
首先,我们简单回顾下Apriori算法的两个概念:
频繁项集:即支持度不小于指定的最小支持度的项集就是频繁项集。
向下封闭:如果k项候选集中有一项不是频繁项集,则这个k项集也不是频繁项集。
它的主要问题是:
在由频繁k项集生成频繁k+1项集时,需要将每个组合得到的候选k+1项集在事务数据中扫描一遍。以此来判断生成的k+1项集是否是频繁项集。
这就意味着,整个计算过程中,它会多次地重复扫描事务数据,导致了其效率比较低下。
(二) 基于FP-Tree计算频繁2项集
这里之所以只计算频繁2项集,是因为:
1. 我们应用中,绝大多数情况下,只需要挖掘到2项集,即满足最小支持度的pair 对,如:<left_item,right_item>
2. 你会发现,如果你掌握了如何用FP-Tree生成频繁2项集,那生成频繁N项集就只是多走那么一小步了哈。
这里我们先简单介绍下基于FP-Tree的关联规则算法:
更官方的名字应该是FP-growth算法(Frequent Pattern-growth),它使用一种紧缩的数据结构来存储查找频繁项集所需要的全部信息。这里的FP-Tree就是FP-growth算法中用到的这种紧缩数据结构。
更多的关于FP-Tree和FP-growth算法的信息可参考百度百科或者直接在百度搜索。。。
接下来,我们使用Bash Shell来编码实现基于FP-Tree的频繁二项集挖掘。
假设,我们有如下事务数据文件:
A,B,E,C
A,B,C
A,D
A,B
A,E
并且假设,我们指定最小支持度为2.
则我们可目测得到结果如下:
B,A:3
C,A:2
C,B:2
E,A:2
接下来,我们通过如下代码来得到我们想要的结果:
#!/home/admin/bin/bash_bin/bash_4 if [ $# -ne 2 ]; then echo "please input the trans input file"; exit 1; fi trans_file=$1; min_support=$2; if [ "x$trans_file" == "x" ]; then echo "the input file can not be null"; exit 2; fi if [ ! -f "$trans_file" ]; then echo "trans should be a existed data file" exit 3; fi if [ -z "$min_support" ]; then echo "please specify the min support for the freq-2 items" exit 4; fi ## get the freq-1 items and the frequents for each of them declare -A freq_1; for line in `cat $trans_file` do currentItemArray=(${line//,/ }); for i in ${currentItemArray[@]} do if [ -z ${freq_1[$i]} ]; then freq_1[$i]=1; else ((freq_1[$i]+=1)); fi done done for k in ${!freq_1[@]} do if [ ${freq_1[$k]} -lt $min_support ]; then unset freq_1[$k]; fi done ### sort the freq_1 using external sort commond declare -a freq_1_sorted_item; freq_1_sorted_length=0; for i in ` for i in ${!freq_1[@]} do echo "$i,${freq_1[$i]}" done | sort -s -t ',' -k 2 -nr ` do freq_1_sorted_item[$freq_1_sorted_length]=${i%%,*}; ((freq_1_sorted_length+=1)); done ### Generate the FP-Tree using a one dimensional array with a virtual root node ### The element with struct {itemName:Support:Child:Next:Parent} ### The virtual root node is {NULL:0:0:0:0} that the only Child filed will not be '0'. ### Because it has no parent and no sibling nodes and no support. declare -a FP_TREE; ## this is the fp_tree declare -A Node_Index; ## the index of each freq_1 item ### push the virtual root node FP_TREE[0]="NULL:0:0:0:0"; ### scan the trans file again and also the last time. ### and generate the fp_tree for line in `cat $trans_file` do ### scan the sorted freq_1 items ### no need to sort the original trans input line.... current_node_index=0; for freq_1_item in ${freq_1_sorted_item[@]} do if [[ ",$line," == *",$freq_1_item,"* ]]; then current_node_line=${FP_TREE[$current_node_index]}; current_node_info=(${current_node_line//:/ }); child_index=${current_node_info[2]}; if [ "$child_index" == "0" ]; then ### add a new node as the first left child of the current node new_node="$freq_1_item:1:0:0:$current_node_index"; FP_TREE_LENGTH=${#FP_TREE[@]}; FP_TREE[$FP_TREE_LENGTH]=$new_node; ### update the child pointer of the current node current_node_info[2]=$FP_TREE_LENGTH; tmp_line=${current_node_info[*]}; FP_TREE[$current_node_index]=${tmp_line// /:}; current_node_index=$FP_TREE_LENGTH; Node_Index[$freq_1_item]="${Node_Index[$freq_1_item]}:$current_node_index"; else while : do child_node_line=${FP_TREE[$child_index]}; child_node_info=(${child_node_line//:/ }); ### find a existed node match the current freq_1_item if [ "${child_node_info[0]}" == "$freq_1_item" ]; then ((child_node_info[1]+=1)); tmp_line=${child_node_info[*]}; FP_TREE[$child_index]=${tmp_line// /:}; current_node_index=$child_index; break; fi next_index=${child_node_info[3]}; if [ "$next_index" == "0" ]; then ### add a new node as the last child of the current node ### and also means the next node of the current last child node of the current node new_node="$freq_1_item:1:0:0:$current_node_index"; FP_TREE_LENGTH=${#FP_TREE[@]}; FP_TREE[$FP_TREE_LENGTH]=$new_node; ### update the next pointer of the current last child of the current node child_node_info[3]=$FP_TREE_LENGTH; tmp_line=${child_node_info[*]}; FP_TREE[$child_index]=${tmp_line// /:}; current_node_index=$FP_TREE_LENGTH; Node_Index[$freq_1_item]="${Node_Index[$freq_1_item]}:$current_node_index"; break; fi child_index=$next_index; done fi fi done done ### FP_TREE Done!!!!! fp_tree_length=${#FP_TREE[@]}; for((i=0;i<fp_tree_length;i++)) do echo "$i->${FP_TREE[$i]}"; done echo ### get the freq_2 items and their support from the FP_TREE!!! declare -A item_4_freq2; for freq_1_item in ${freq_1_sorted_item[@]} do treeIndex_item=${Node_Index[$freq_1_item]}; indexs=(${treeIndex_item//:/ }); base_support=0; for index in ${indexs[@]} do p_node_line=${FP_TREE[$index]}; p_node_info=(${p_node_line//:/ }); current_path_support=${p_node_info[1]}; ((base_support+=$current_path_support)); index=${p_node_info[4]}; ## search the parent node until the root while [ "$index" != "0" ] do p_node_line=${FP_TREE[$index]}; p_node_info=(${p_node_line//:/ }); p_item=${p_node_info[0]}; if [ -n "${item_4_freq2[$p_item]}" ]; then ((item_4_freq2[$p_item]+=$current_path_support)); else item_4_freq2[$p_item]=$current_path_support; fi index=${p_node_info[4]}; done done for key in ${!item_4_freq2[@]} do freq_2_items_support=0; [ $base_support -lt ${item_4_freq2[$key]} ] && ((freq_2_items_support=$base_support)) || ((freq_2_items_support=${item_4_freq2[$key]})); if [ $freq_2_items_support -ge $min_support ]; then echo "$freq_1_item,$key:$freq_2_items_support"; fi unset item_4_freq2[$key]; done done
关于代码的说明:
1. 代码中使用了关联数组,即你看到的declare -A *** 的部分,因此需要Bash4.0以上支持才能运行该代码。
2. 代码中首先扫描一次数据,生成了频繁1项集,并根据support对它们进行desc排序。
3. 根据生成的频繁1项集,第二次,也是最后一次扫描事务数据,生成FP-Tree,具体参见注释。
4. 最后根据生成的FP-Tree挖掘得到所有的频繁二项集,以及其支持度。
生成的FP-Tree:
如果你的机器上碰巧装有Bash4.0或以上版本时,可以运行该代码,可以看到生成的FP-Tree。
由于Bash不支持复合数据结构和多维数组,我只好通过结构化字符串的方式通过一维数组模拟FP-Tree。
代码中的FP-Tree:
FP-Tree节点的内部结构为{itemName:Support:Child:Next:Parent}
0->NULL:0:1:0:0
1->A:5:2:0:0
2->B:3:3:5:1
3->C:2:4:0:2
4->E:1:0:0:3
5->E:1:0:0:1
左边为node在数组中的位置。
更直观的FP-Tree:
通过上述的输出信息,不难看出真实的树结构应该是这样的:
接下来就是根据这棵树,获取到我们需要的频繁二项集。
可能有人会说,这一步比原生的FP-growth算法要少做很多事情。
确实,因为我们这里只需要生成频繁2项集,因此不需要原本这一步中用来生成所有频繁项集的那些步骤。。。。
生成的频繁2项集如下:
B,A:3
C,A:2
C,B:2
E,A:2
具体可见代码:line156~line193。
在此就不做赘述了。。。
此外,代码运行命令:
./fp-tree-apriori.sh trans_input.dat 2
呵呵,你懂得。
相关推荐
在实际应用中,我们还可以基于频繁项集挖掘关联规则,如“如果顾客买了牛奶,那么他们可能也会买面包”,这可以帮助企业进行商品推荐或市场策略规划。总之,FP-growth算法是数据挖掘中一个强大的工具,它能够帮助...
Vue JSON Tree View是一款基于Vue.js框架的开源组件,用于将JSON数据以清晰的树状结构展示出来。在前端开发中,处理和展示JSON数据时,这样的插件非常实用,能够帮助开发者直观地查看和理解复杂的数据结构。接下来,...
PyTorch是一个开源的机器学习框架,它基于 Torch 设计,提供了丰富的功能和灵活性,广泛用于深度学习和神经网络的研究与应用。在Python中,PyTorch的安装通常包括以下几个步骤: 1. **Anaconda安装**:Anaconda是一...
### Effective Robotics Programming with ROS —— 中文学习笔记 #### 知识点一:ROS环境配置与准备工作 **1.1 安装ROS Indigo** 在开始深入学习《Effective Robotics Programming with ROS》之前,首先需要搭建...
在压缩包`react-bash-master`中,包含了React-bash的源代码。你可以通过阅读这些代码了解其工作原理,学习如何进行定制和扩展。源码通常包含`src`目录,其中的`index.js`或`App.js`是入口文件,`components`目录包含...
这个是CSDN-markdown编辑器第一次使用时的文档,只显示一次。这里把他存下来分享出去。在编写博客的时候有不明白的可以看一下,一目了然。
以上就是小编为大家带来的解决ssh远程登陆linux显示-bash-4.1$的问题全部内容了,希望大家多多支持软件开发网~ 您可能感兴趣的文章:浅谈linux中shell变量$#,$@,$0,$1,$2的含义解释php $_SERVER windows系统与linux...
在本案例中,我们将探讨如何在Vue项目中使用第三方库实现拖放排序功能,主要关注"vue-sortable-tree"这个库。 首先,"vue-sortable-tree"是一个专门用于Vue.js的树形组件库,它提供拖放排序功能,允许用户通过鼠标...
本文将详细讲解如何在Element-ui的`el-tree`组件中实现这一功能。 首先,我们要理解`el-tree`的工作原理。`el-tree`是基于Vue.js构建的,它依赖Vue的数据绑定机制来更新视图。当数据源(通常是一个数组)发生变化时...
maven-bash-completion, Maven Bash自动完成 Maven Bash完成默认情况下,Maven 不发布Bash自动完成脚本,只使用一个非常简单的指南插件。 这里脚本为你提供了更多帮助你日常 Maven 构建的脚本。演示 安装手动安装...
鉴于目前绝大部分服务器因为没有注册的yum或者因不通外网等问题导致无法使用yum update -y bash 命令进行漏洞修复,如采用RPM包升级修复漏洞又存在各服务器系统有的是32位有的是64位或者bash的版本不一样导致需要...
linux-shell-scripting-fundamentals-bash.epub
主要是bash语法的例程,在记录学习笔记的时候做练习用的。学习记录请参考:https://blog.csdn.net/xiaodouhao123456/article/details/109473083,及其所在专栏中的其他笔记。
"苹果脚本跟我学.pdf"可能侧重于Apple Script,它是苹果生态系统中的脚本语言,虽然语法不同,但其核心思想——通过脚本实现自动化,与Bash脚本编程有相通之处。结合这两份资源,你可以从不同角度全面了解和掌握脚本...
**Bash Infinity(bash-oo-framework):Bash的现代样板框架标准库** Bash Infinity,简称bash-oo-framework,是一个强大的开源项目,专为Bash脚本开发提供了一套全面的面向对象编程(OOP)框架。这个框架旨在提高...
3. **替代方案**:除了`bash.py`,还有其他库如`sh`、`subprocess`模块等可以实现类似功能,选择哪种取决于具体需求。 **jpetrucciani-bash.py-3aa8c07** 这个文件名看起来像是`bash.py`库的一个版本或分支,由...
这种技术基于“Nested Set Model”(嵌套集合模型)模式,由 Laravel 的扩展包 "tree" 提供支持。"tree" 扩展包使得在Laravel中处理层级数据变得简单易行。 "Nested Set Model" 是一种存储树形结构的方法,其核心...
Linux运维-运维系统服务04-Shell脚本d2-shell基础知识-05BASH特性.mp4
Linux运维-3.Shell编程-11shell基础-103Bash基本功能2.avi
Linux运维-3.Shell编程-11shell基础-102Bash基本功能1.avi