`

基于 FP-Tree 的关联规则挖掘——Bash实现

阅读更多

本文假设读者至少有对数据挖掘中的关联规则有基本了解,对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

 

 呵呵,你懂得。

 

 

 

 

 

 

 

 

  • 大小: 61.9 KB
分享到:
评论

相关推荐

    FP-growth发现频繁项集python实现(含数据集)

    在实际应用中,我们还可以基于频繁项集挖掘关联规则,如“如果顾客买了牛奶,那么他们可能也会买面包”,这可以帮助企业进行商品推荐或市场策略规划。总之,FP-growth算法是数据挖掘中一个强大的工具,它能够帮助...

    vue-json-tree-view-master.zip

    Vue JSON Tree View是一款基于Vue.js框架的开源组件,用于将JSON数据以清晰的树状结构展示出来。在前端开发中,处理和展示JSON数据时,这样的插件非常实用,能够帮助开发者直观地查看和理解复杂的数据结构。接下来,...

    python-1(csdn)————程序.pdf

    PyTorch是一个开源的机器学习框架,它基于 Torch 设计,提供了丰富的功能和灵活性,广泛用于深度学习和神经网络的研究与应用。在Python中,PyTorch的安装通常包括以下几个步骤: 1. **Anaconda安装**:Anaconda是一...

    Effective-Robotics-Programming-with-ROS——中文学习笔记

    ### Effective Robotics Programming with ROS —— 中文学习笔记 #### 知识点一:ROS环境配置与准备工作 **1.1 安装ROS Indigo** 在开始深入学习《Effective Robotics Programming with ROS》之前,首先需要搭建...

    react-reactbash可配置扩展的bash终端React组件

    在压缩包`react-bash-master`中,包含了React-bash的源代码。你可以通过阅读这些代码了解其工作原理,学习如何进行定制和扩展。源码通常包含`src`目录,其中的`index.js`或`App.js`是入口文件,`components`目录包含...

    CSDN-markdown编辑器文档——官方文档

    这个是CSDN-markdown编辑器第一次使用时的文档,只显示一次。这里把他存下来分享出去。在编写博客的时候有不明白的可以看一下,一目了然。

    解决ssh远程登陆linux显示-bash-4.1$的问题

    以上就是小编为大家带来的解决ssh远程登陆linux显示-bash-4.1$的问题全部内容了,希望大家多多支持软件开发网~ 您可能感兴趣的文章:浅谈linux中shell变量$#,$@,$0,$1,$2的含义解释php $_SERVER windows系统与linux...

    vue树可拖动拖动项目排序

    在本案例中,我们将探讨如何在Vue项目中使用第三方库实现拖放排序功能,主要关注"vue-sortable-tree"这个库。 首先,"vue-sortable-tree"是一个专门用于Vue.js的树形组件库,它提供拖放排序功能,允许用户通过鼠标...

    Element-ui el-tree新增和删除节点后如何刷新tree的实例

    本文将详细讲解如何在Element-ui的`el-tree`组件中实现这一功能。 首先,我们要理解`el-tree`的工作原理。`el-tree`是基于Vue.js构建的,它依赖Vue的数据绑定机制来更新视图。当数据源(通常是一个数组)发生变化时...

    maven-bash-completion, Maven Bash自动完成.zip

    maven-bash-completion, Maven Bash自动完成 Maven Bash完成默认情况下,Maven 不发布Bash自动完成脚本,只使用一个非常简单的指南插件。 这里脚本为你提供了更多帮助你日常 Maven 构建的脚本。演示 安装手动安装...

    修复bash漏洞的4.3.30源码包

    鉴于目前绝大部分服务器因为没有注册的yum或者因不通外网等问题导致无法使用yum update -y bash 命令进行漏洞修复,如采用RPM包升级修复漏洞又存在各服务器系统有的是32位有的是64位或者bash的版本不一样导致需要...

    linux-shell-scripting-fundamentals-bash.epub

    linux-shell-scripting-fundamentals-bash.epub

    test.bash——bash的语法例程

    主要是bash语法的例程,在记录学习笔记的时候做练习用的。学习记录请参考:https://blog.csdn.net/xiaodouhao123456/article/details/109473083,及其所在专栏中的其他笔记。

    linux-torque一个用纯bash编写的transmissiondaemonTUI客户端

    Linux-Torque是一个基于Bash shell脚本的 Transmission Daemon 图形用户界面(TUI)客户端,专为那些喜欢在命令行环境中工作但又想享受简单易用的交互式界面的Linux用户设计。Transmission是一个流行的BitTorrent...

    高级Bash脚本编程指南--中文版(advance_bash_scriipt_progaming_guide).pd苹果脚本跟我学.pdff

    "苹果脚本跟我学.pdf"可能侧重于Apple Script,它是苹果生态系统中的脚本语言,虽然语法不同,但其核心思想——通过脚本实现自动化,与Bash脚本编程有相通之处。结合这两份资源,你可以从不同角度全面了解和掌握脚本...

    bash-oo-framework:Bash Infinity是bash的现代样板框架标准库

    **Bash Infinity(bash-oo-framework):Bash的现代样板框架标准库** Bash Infinity,简称bash-oo-framework,是一个强大的开源项目,专为Bash脚本开发提供了一套全面的面向对象编程(OOP)框架。这个框架旨在提高...

    Python-bashpy用于Python的内联Bash脚本运行器

    3. **替代方案**:除了`bash.py`,还有其他库如`sh`、`subprocess`模块等可以实现类似功能,选择哪种取决于具体需求。 **jpetrucciani-bash.py-3aa8c07** 这个文件名看起来像是`bash.py`库的一个版本或分支,由...

    Laravel开发-tree

    这种技术基于“Nested Set Model”(嵌套集合模型)模式,由 Laravel 的扩展包 "tree" 提供支持。"tree" 扩展包使得在Laravel中处理层级数据变得简单易行。 "Nested Set Model" 是一种存储树形结构的方法,其核心...

    Linux运维-运维系统服务04-Shell脚本d2-shell基础知识-05BASH特性.mp4

    Linux运维-运维系统服务04-Shell脚本d2-shell基础知识-05BASH特性.mp4

    Linux运维-3.Shell编程-11shell基础-103Bash基本功能2.avi

    Linux运维-3.Shell编程-11shell基础-103Bash基本功能2.avi

Global site tag (gtag.js) - Google Analytics