`

基于 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,及其所在专栏中的其他笔记。

    高级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

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

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

Global site tag (gtag.js) - Google Analytics