数据挖掘FP-tree树

fp树算法FP树算法，全称频繁模式树算法（Frequent Pattern Tree Algorithm），是一种用来挖掘大规模数据集种频繁模式的算法。

其核心思想是利用FP树结构来存储数据集并高效地发现频繁模式。

这一算法在数据挖掘任务中被广泛使用，尤其适合处理大量离散数据的场景。

FP树算法的主要步骤分为三个部分：首先，统计出数据集中所有项的出现次数，并创建FP树结构；然后，通过遍历FP树结构，找出所有频繁项集；最后，再通过递归方法，在频繁项集种寻找关联规则。

首先，利用常用的Apriori算法，统计数据集中所有项（Item）的出现次数，并保留所有出现次数大于等于最小支持度（minimum support）的项。

然后，根据这些项构建FP树，FP树的节点包含了一个Item和指向所有出现该Item的项的连接。

其次，利用FP树结构，遍历FP树的所有路径，并寻找包含所有Item的路径，即频繁项集（Frequent Itemsets）。

在FP树结构中，由于每个Item的排序是根据最初出现的顺序而定，因此按顺序寻找每个Item，可以高效地找到频繁项集。

同时，在FP Tree的节点之间采用连接链接的方法构造，可以高效地遍历所有路径，从而找到所有频繁项集。

最后，对频繁项集可以进行关联规则的挖掘。

在求解关联规则时，需要考虑可信度（confidence）的概念，表示对于一个频繁项集$I$中的项$x$与$y$，给定$x$的前提下，$y$出现的概率。

我们可以通过计算$\frac{support(I)}{support(x)}$来得到$x$与$y$的可信度。

在求解规则时，在所有可信度达到最小置信度（minimum confidence）的规则中选择最优解。

总的来说，FP树算法具有以下几个优点：首先，它可以快速地找到频繁项集，因为它只遍历了FP树的所有路径而不是组合所有的项。

其次，它可以高效地存储数据，因为FP树只需要存储每个项的出现次数以及连接信息，比传统的关系型数据库存储更加高效。

fp树挖掘频繁项集例题频繁模式树（FP-Tree）是一种用于挖掘频繁项集的数据结构和算法。

它通过构建一棵树来表示事务数据库中的频繁项集，并利用树的结构和特性来高效地挖掘频繁项集。

下面我将通过一个例题来说明如何使用FP-Tree进行频繁项集的挖掘。

假设我们有以下事务数据库：事务1，{A, B, C, D}。

事务2，{B, C, E}。

事务3，{A, B, C, E}。

事务4，{B, D, E}。

事务5，{A, B, C, D, E}。

我们的目标是找出支持度不低于阈值的频繁项集。

在这个例子中，我们设定阈值为2，即支持度至少为2。

首先，我们需要进行两个步骤，构建频繁项集的项头表和构建FP-Tree。

1. 构建项头表：首先扫描数据库，统计每个项的支持度计数。

然后根据支持度计数筛选出满足阈值的频繁项，并按照支持度降序排序。

在这个例子中，我们得到的频繁项集为，{B, A, C, D, E}。

2. 构建FP-Tree：从数据库中的每个事务开始，按照频繁项集的顺序构建FP-Tree。

对于每个事务，我们按照频繁项集的顺序遍历，如果项在事务中存在，则将其插入到FP-Tree中的适当位置。

如果该项已经存在于FP-Tree中的某个节点上，则增加该节点的支持度计数。

如果该项不存在于FP-Tree中，则创建一个新的节点，并设置其支持度计数为1。

根据以上步骤，我们可以得到如下的FP-Tree：null.|。

B./ | \。

A C D.| |。

E E.接下来，我们可以利用构建好的FP-Tree来挖掘频繁项集。

3. 挖掘频繁项集：首先，我们以项头表中的频繁项为基础，依次从后往前挖掘频繁项集。

对于每个频繁项，我们找到其对应的条件模式基，即以该频繁项为结尾的路径集合。

然后，利用条件模式基构建新的条件FP-Tree，并递归地重复上述步骤，直到无法再构建新的条件FP-Tree为止。

在这个例子中，我们以{E}为基础进行挖掘。

首先找到所有以{E}结尾的路径集合，即{B, C, E}和{B, D, E}。

fp-tree例题FP-Growth算法是一种用于发现频繁模式的数据挖掘算法，它通过构建FP树来高效地发现频繁模式。

下面我将通过一个简单的例子来说明FP-Growth算法的工作原理。

假设我们有以下交易数据集：TID 交易项集。

1 {f, a, c, d, g, i, m, p}。

2 {a, b, c, f, l, m, o}。

3 {b, f, h, j, o}。

4 {b, c, k, s, p}。

5 {a, f, c, e, l, p, m, n}。

首先，我们需要构建一个项头表（Header Table），用来存储每个频繁项的计数和链表头指针。

然后根据项头表和原始数据集构建FP树。

在构建FP树时，需要按照每条交易中的频繁项的出现次数进行排序，然后按照排序后的顺序插入到FP树中。

接下来，我们需要遍历数据集，对每条交易进行处理。

对于每条交易，我们需要根据项头表中的频繁项顺序构建相应的前缀路径，并将其插入到FP树中。

如果某个节点已经存在于FP树中，则更新该节点的计数；如果不存在，则创建一个新节点并更新项头表中的链表指针。

构建好FP树之后，我们可以利用FP树来高效地发现频繁模式。

通过递归地挖掘FP树，可以得到所有的频繁项集以及它们的支持度计数。

在上面的例子中，我们可以通过构建FP树来发现频繁模式，进而进行关联规则挖掘等任务。

这就是FP-Growth算法的基本原理和应用。

希望以上内容能够帮助你更好地理解FP-Growth算法的工作原理。

如果你还有其他问题，欢迎继续提问。

FP树算法的MATLAB程序示例FP树（频繁模式树）算法是一种用于挖掘频繁模式的数据挖掘算法。

下面是一个基于事实的FP树算法的MATLAB 程序示例：function [frequent_patterns] = fp_tree(data, min_support) % 构建频繁模式树root = create_tree(data);% 获取频繁项集frequent_patterns = mine_patterns(root, min_support);endfunction [root] = create_tree(data)root = struct('item', 'null', 'count', 0, 'children', {});% 统计每个项的计数item_counts = containers.Map();for i = 1:length(data)itemset = data{i};for j = 1:length(itemset)item = itemset{j};if isKey(item_counts, item)item_counts(item) = item_counts(item)+ 1;elseitem_counts(item) = 1;endendend% 删除不满足最小支持度的项items = keys(item_counts);for i = 1:length(items)item = items{i};if item_counts(item) < min_supportremove(item_counts, item);endend% 如果没有满足最小支持度的项，返回空树if isempty(keys(item_counts))return;end% 对每个事务中的项按照支持度降序排序for i = 1:length(data)itemset = data{i};[~, sorted_indices] = sort(cellfun(@(x) item_counts(x), itemset), 'descend');data{i} = itemset(sorted_indices);end% 构建树for i = 1:length(data)itemset = data{i};insert_tree(root, itemset, item_counts);endendfunction [] = insert_tree(node, itemset, item_counts)if isempty(itemset)return;enditem = itemset{1};child = find_child(node, item);if isempty(child)child = struct('item', item, 'count', item_counts(item), 'children', {});node.children{end+1} = child;elsechild.count = child.count + item_counts(item);endinsert_tree(child, itemset(2:end), item_counts);endfunction [child] = find_child(node, item)children = node.children;for i = 1:length(children)if strcmp(children{i}.item, item)child = children{i};return;endendchild = [];endfunction [frequent_patterns] = mine_patterns(root, min_support)frequent_patterns = struct('pattern', {}, 'support', []);if isempty(root.children)return;endfor i = 1:length(root.children)child = root.children{i};pattern = {child.item};support = child.count;frequent_patterns(end+1) = struct('pattern', pattern, 'support', support);subtree_data = get_subtree_data(child);subtree_patterns = fp_tree(subtree_data, min_support);frequent_patterns = [frequent_patterns, subtree_patterns];endendfunction [subtree_data] = get_subtree_data(node)subtree_data = {};if isempty(node.children)return;endsubtree_data = cell(1, node.count);for i = 1:length(node.children)child = node.children{i};for j = 1:child.countsubtree_data{j} = [subtree_data{j}, child.item];endendend这是一个简化的FP树算法的MATLAB实现。

fptree算法例题摘要：1.算法背景介绍2.FP-Tree 的构建3.FP-Tree 的应用4.FP-Tree 的优化5.总结正文：1.算法背景介绍FP-Tree（Fast Patricia Tree）是一种用于存储频繁项集的数据结构，它可以在O(logN) 的时间复杂度内完成寻找最大频繁项集的操作。

FP-Tree 最早由Aho et al.在1994 年提出，它基于Patricia Tree（Prefix Tree）进行修改，将Patricia Tree 的每个节点存储扩展为频繁项集，从而提高了查找频繁项集的效率。

2.FP-Tree 的构建FP-Tree 的构建过程分为两步。

首先，构建一颗Patricia Tree，将输入数据序列按照前缀模式进行存储。

然后，在Patricia Tree 的基础上，根据频繁项集的支持度阈值，将每个节点扩展为一个频繁项集，并将这些频繁项集按照支持度从高到低排序。

3.FP-Tree 的应用FP-Tree 在数据挖掘和信息检索领域有广泛的应用。

其中最常见的应用是挖掘频繁项集，即找出在数据集中出现频率较高的项目组合。

此外，FP-Tree 还可以用于挖掘关联规则、文本分类、信息检索等任务。

4.FP-Tree 的优化为了进一步提高FP-Tree 的性能，研究者们提出了许多优化方法。

例如，可以使用压缩技术减小FP-Tree 的存储空间；可以采用增量算法，对输入数据进行实时更新，减少FP-Tree 的重建时间；还可以使用并行计算技术，提高FP-Tree 的构建速度。

5.总结FP-Tree 是一种高效的数据结构，可以快速地挖掘频繁项集及其关联规则。

通过构建FP-Tree，我们可以从大量数据中挖掘出有价值的信息，为数据挖掘和信息检索等领域提供有力支持。

fp-growth算法原理fp-growth算法是一种用于频繁项集挖掘的算法，它是基于一种称为FP树的数据结构来实现的。

该算法可以高效地挖掘事务数据集中的频繁项集，因此广泛应用于数据挖掘和机器学习领域。

一、FP树FP树是一种基于前缀树的数据结构，可以用来存储事务数据集中各个事务的项集。

它通过将项集按照出现次数从高到低进行排序，并进行压缩，从而大大减小了数据的存储空间。

FP树由一个根节点开始，每个节点存储一个项和该项出现的次数。

FP树上的每一个路径都代表一个项集，而每个路径上的叶节点都包含了相同的项集，而仅仅是出现的次数不同。

假设我们有以下事务数据集：{| class="wikitable" style="text-align:center" |+ style="font-size:larger;" |事务数据集 |- ! style="padding:0.2em 1em;text-align:left;" | 事务编号 ! style="padding:0.2em 1em;text-align:left;" | 项集 |- | 1 | A, B, C |- | 2 | B, D |- | 3 | C, D |- | 4 | A, B, D |- |}我们需要扫描整个事务数据集，计算每个项的出现次数，并按照出现次数从高到低进行排序，得到如下表格：{| class="wikitable" style="text-align:center" |+ style="font-size:larger;" |频繁项集 |- ! style="padding:0.2em 1em;text-align:left;" | 项 !style="padding:0.2em 1em;text-align:left;" | 支持度 |- | B | 3 |- | C | 2 |- | A | 2 |- | D | 2 |-}然后，我们可以通过FP树来表示整个事务数据集。

fap分选方法-概述说明以及解释1.引言1.1 概述概述部分内容：在现代科技和工业领域中，纳米颗粒的制备和应用逐渐成为研究的热点。

在这一过程中，纳米颗粒的分选显得尤为重要，因为不同大小或形状的颗粒在物理、化学和生物学性质上可能存在很大差异，从而对其性能和应用造成影响。

FAP分选方法，即基于浮力、阻力和表面电位的纳米颗粒分选方法，是一种常用于纳米颗粒分选的有效技术。

该方法基于颗粒在流体中的运动行为以及颗粒与流体的相互作用，利用浮力、阻力和表面电位的差异来实现颗粒的分离和分选。

FAP分选方法的原理是通过控制流体的流速和颗粒与流体的相互作用，使得具有特定浮力、阻力和表面电位的纳米颗粒在流体中呈现出不同的运动行为。

通过调节这些因素，可以实现对纳米颗粒的粒径、形状和表面性质的分选，从而获得具有所需特性的纳米颗粒。

FAP分选方法在科学研究和工业生产中具有广泛的应用。

在科学研究方面，该方法可以用于研究纳米颗粒的特性和性能，以及纳米颗粒与流体之间的相互作用机制。

在工业生产方面，FAP分选方法可以应用于纳米颗粒的制备和纯化过程中，以获得具有一致性和高纯度的产品。

总的来说，FAP分选方法是一种基于浮力、阻力和表面电位的纳米颗粒分选技术，具有准确、可控和高效的特点。

它在纳米颗粒的研究和应用中发挥着重要的作用，并且有着广阔的发展前景。

接下来的文章将对FAP 分选方法的背景、原理和应用进行详细的介绍和讨论，以期更好地理解和推动这一领域的发展。

1.2 文章结构文章结构部分的内容:文章的结构是指对整篇文章进行组织和安排的方式。

一个清晰、合理的结构有助于读者理解文章的逻辑关系和思路展开。

本文采用以下结构来呈现FAP分选方法的相关内容。

首先，在引言部分，我们将对FAP分选方法进行概述，介绍其背景、原理和应用领域。

这部分旨在为读者提供对FAP分选方法的整体了解，引发对该方法的兴趣。

接下来，在正文部分，我们将详细讨论FAP分选方法的背景。

FP-Tree算法详细过程（Java实现）我就不说FP-Tree的作⽤、优点什么的了,直接⽤例⼦来解释构建FP-Tree和找出所有频繁项集,第⼀次写博客,不对之处还请指出。

输⼊⽂件:testInput.txtT1 125T2 42T3 23T4 124T5 13T6 23T7 13T8 1235T9 123先计算所有数据的单项的⽀持度计数,计算后为{1,(⽀持度计数:6)} {2,(⽀持度计数:7)} {3,(⽀持度计数:6)} {4,(⽀持度计数:2)} {5,(⽀持度计数:2)}然后根据⽀持度计数将各⾏数据按⽀持度计数的⼤⼩从⼤到⼩进⾏排序,排序后为:21524232141323132135213然后构建FP-Tree树(最⼩⽀持度计数为2)，同时构建项头表,项头表按⽀持度计数排序好(⽆箭头的表⽰树之间的连线,有箭头的表⽰链表之间的连线):先是数据 2 1 5，括号⾥的数字为节点当前的⽀持度计数.数据2 4数据2 3数据 2 1 4数据 1 3数据 2 3数据 1 3数据 2 1 3 5数据 2 1 3构建完成后,从项透表的最后⼀个项5开始,从树周为5的节点向上遍历,找出条件模式基有{2 (1),1 (1)}和{2 (1),1 (1),3 (1)}两个条件模式基,由于3的⽀持度计数⼩于最⼩⽀持度计数,在构建的时候不能加⼊树中,所以构建后的项头表和条件FP-Tree树为:因为其条件FP-Tree为单路径,所以只要找出{2 (2),1 (2)}的所有⼦项集加上后缀{5 (2)}即可,得出3个频繁项集{2(2),1(2),5(2)}、{2(2),5(2)}、{1(2),5(2)}.然后是4,条件模式基为{2(1)}和{2(1),1(1)}，1⼩于最⼩⽀持度计数,不参与树的构造,遍历得出频繁项集{2(2),4(2)}然后是3,条件模式基为{2(2),1(2)}、{2(2)}、{1(2)}由于该条件FP-Tree不是单路径,所以应该遍历该项头表,即从1开始,此时后缀为3遍历时,⾸先将项头表的1与其前⼀次后缀连接,得到⼀个频繁项集{1(4),3(4)},⽀持度计数为1在树中出现的总次数,1-频繁项集也是如此得到,因为那时前⼀次后缀为空;然后得到1的条件模式基为{2(2)},因为只有⼀个,所以可以直接遍历其所有⼦项加上此时的后缀13构成⼀个频繁项集{2(2),1(2),3(2)},⽀持度计数为条件模式基的⽀持度计数如果有两个条件模式基,则继续构建树,直到条件模式基为1个或树只有⼀条路径然后是1,条件模式基为{2(4)},遍历后得到{2(4),1(4)}最后是2,⽆条件模式基总结我在写代码的时候难点主要在构建条件FP-Tree然后找频繁项这⾥,我⼀开始并没有⽤构建条件FP-Tree来找频繁项,⽽是通过第⼀次的条件模式基,然后找出各项的所有条件模式基的⼦项,将满⾜⽀持度计数的并不重复的加⼊挑选出来,⽀持度计数需要与某项的所有条件模式基进⾏⽐较,若包含在该条件模式基中,则加上该条件模式基的⽀持度计数.最后贴出我的Java代码(注意:我的代码是针对单项为"1 2 4"、"a v c d"这种单个字符的,若处理的数据为"啤酒开瓶器抹布"需要修改代码):MyFrequentItem.javapublic class MyFrequentItem {//每项中含有的元素private String array;//该项的⽀持度计数private int support;//该项的长度,即第⼏项集private int arrayLength;public MyFrequentItem(String array,int support) {this.array=array;this.support=support;arrayLength=array.length();}public String getArray() {return array;}public void setArray(String array) {this.array = array;}public int getSupport() {return support;}public void setSupport(int support) {this.support = support;}public int getArrayLength() {return arrayLength;}public void setArrayLength(int arrayLength) {this.arrayLength = arrayLength;}}View CodeFP_tree.javaimport java.io.BufferedReader;import java.io.File;import java.io.FileReader;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import parator;import java.util.HashMap;/**** @author⽯献衡**/class FP_Node{//树String item;int supportCount;ArrayList<FP_Node> childNode;FP_Node parent;public FP_Node(String item,int supportCount,FP_Node parent) {this.item=item;this.supportCount=supportCount;this.parent = parent;childNode = new ArrayList<FP_Node>();}}class LinkedListNode{//链表,同⼀条链表存储的TP_Node节点的item相同FP_Node node;LinkedListNode next;public LinkedListNode(FP_Node node) {this.node=node;next=null;}}public class FP_tree {//⽂件位置private String filePath;//存储从⽂件中读取的数据private String[][] datas;//Integer代表频繁项集的项数,String表⽰频繁项集各项组成的字符串private HashMap<Integer, HashMap<String,MyFrequentItem>> myFrequentItems;//单项出现的次数,⽤来排序HashMap<String, Integer> signalCount;//最⼩⽀持度计数private int minSupportCount;//最⼩置信度private double minConf;//记录的总条数private int allDataCount;//强规则ArrayList<String> strongRules;//弱规则ArrayList<String> weakRules;private MyFrequentItem frequentItem;;public FP_tree(String filePath,int minSupportCount) {this.minSupportCount = minSupportCount;this.filePath = filePath;strongRules = new ArrayList<String>();weakRules = new ArrayList<String>();myFrequentItems = new HashMap<Integer, HashMap<String,MyFrequentItem>>();//读取数据readFile();}/*** .读取⽂件中的数据储存到datas*/private void readFile() {ArrayList<String[]> list = new ArrayList<String[]>();try {String string;FileReader in = new FileReader(new File(filePath));BufferedReader reader = new BufferedReader(in);while((string=reader.readLine())!=null) {list.add(string.substring(3).split(" "));}allDataCount = list.size();datas = new String[allDataCount][];list.toArray(datas);reader.close();in.close();list.clear();} catch (Exception e) {// TODO: handle exception}}public void startTool(double minConf){this.minConf = minConf;//扫描并且排序scanAndSort();//初始化myFrequentItemsfor(int i=1;i<=signalCount.size();i++) {myFrequentItems.put(i, new HashMap<String, MyFrequentItem>());}HashMap<String, Integer> originList = new HashMap<String, Integer>();//将datas的每条记录转换成⼀条排序好的字符串和它的⽀持度的形式//如记录{2,1,5}转换成215和1,就如条件模式基以及其⽀持度计数String s;for(String[] strs : datas) {s = "";for (String string : strs) {s+=string;}if(originList.containsKey(s))originList.put(s,originList.get(s)+1);elseoriginList.put(s,1);}//构造TP树,同时构造链表以及找出所有频繁项fp_Growth(originList, signalCount, "",Integer.MAX_VALUE);int n = signalCount.size();HashMap<String, MyFrequentItem> map = new HashMap<String, MyFrequentItem>(); String string;//输出各频繁项集的频繁项,包括它们的⽀持度计数for(int i=1;i<=n;i++) {map = myFrequentItems.get(i);System.out.println(i+"-项频繁项集为:");for (MyFrequentItem myFrequentItem : map.values()) {System.out.print("{");string = myFrequentItem.getArray();for(int j=0;j<myFrequentItem.getArrayLength();j++) {System.out.print(string.charAt(j)+",");}System.out.print("(⽀持度计数:"+myFrequentItem.getSupport()+")} ");}System.out.println();}//计算k-频繁项集中各频繁项的置信度int k=3;if(myFrequentItems.get(k).size()!=0) {for (MyFrequentItem frequentItem : myFrequentItems.get(k).values()) {relevance(frequentItem);}}}/*** .计算该最⼤频繁项集与其⼦项集的关联性* @param index 频繁集中的第index个* @param k 项频繁集*/private void relevance(MyFrequentItem myFrequentItem2) {//该项的⽀持度int support = myFrequentItem2.getSupport();//该频繁项的元素拼接成的字符串String nowFrequentString = myFrequentItem2.getArray();//找出所有⼦项集childRelevance(nowFrequentString.toCharArray(), 0, "", "", support);System.out.println();for(String weakRule : weakRules) {System.out.println(weakRule);}for(String strongRule : strongRules) {System.out.println(strongRule);}//输出之后清空weakRules.clear();strongRules.clear();}/*** .找出所有⼦项集* @param child* @param k* @param childString 为⼦项集拼接的字符串* @param otherString除⼦项集以外的拼接的字符串* @param support*/private void childRelevance(char[] child,int k,String childString,String otherString,int support) { if(child.length==k) {//空串和其本⾝不计算if(childString.length()==k||childString.length()==0) return;//计算置信度calculateRelevance(childString, otherString, support);}else {childRelevance(child, k+1, childString, otherString+child[k], support);//该字符不要childRelevance(child, k+1, childString+child[k], otherString, support);//该字符要}}/*** .计算置信度* @param childString* @param otherString* @param support*/private void calculateRelevance(String childString,String otherString,int support) {String rule="";//获取⼦频繁项childString的⽀持度计数int childSupport = myFrequentItems.get(childString.length()).get(childString).getSupport();double conf = (double)support/(double)childSupport;rule+="{";for(int m=0;m<childString.length();m++)rule+=(childString.charAt(m)+",");rule+="}-->{";for(int m=0;m<otherString.length();m++) {rule+=(otherString.charAt(m)+",");}rule+=("},confindence(置信度):"+support+"/"+childSupport+"="+conf);if(conf<minConf) {rule+=("由于此规则置信度未达到最⼩置信度的要求，不是强规则");weakRules.add(rule);}else {rule+=("为强规则");strongRules.add(rule);}}/*** .构建树并找出所有频繁项* @param originList 每条路径和该路径的⽀持度计数* @param originCount originList中每个字符的⽀持度计数* @param suffix 后缀*/private void fp_Growth(HashMap<String, Integer> originList,HashMap<String, Integer>originCount,String suffix,int suffixSupport) {FP_Node root = new FP_Node(null, 0, null);//条件FP-Tree的根节点//表头项ArrayList<LinkedListNode> headListNode = new ArrayList<LinkedListNode>();//构建树,并检查是否为单路径树if(treeGrowth(suffix,root, originList, originCount, headListNode)) {//如果是单路径树,直接进⾏递归出所有⼦频繁项String string = "";while(root.childNode.size()!=0) {root = root.childNode.get(0);string+=root.item;}//递归找出所有频繁项findFrequentItem(0, "", string.toCharArray(), suffixSupport, suffix,originCount);}else {//不是单路径树,从最后⼀个表头项的最后⼀个往上找条件模式基findConditional(headListNode, originCount, suffix);}}private boolean treeGrowth(String suffix,FP_Node root,HashMap<String, Integer> originList,HashMap<String, Integer>originCount,ArrayList<LinkedListNode> headListNode) { //链表的当前节点HashMap<String, LinkedListNode> nowNode = new HashMap<String, LinkedListNode>();//表⽰是否找到该字符所在的节点,有则true,否则false并创⼀个新的节点boolean flag;//⽤来记录树是否为单路径boolean isSingle = true;FP_Node treeHead;LinkedListNode listNode;String[] strings;int support;for (String originString : originList.keySet()) {//获取该条件模式基的⽀持度计数support = originList.get(originString);strings = originString.split("");treeHead = root;for(int i=0;i<strings.length; i++) {//⼩于最⼩⽀持度计数的不加⼊树中if(originCount.get(strings[i])<minSupportCount)continue;flag = false;for(FP_Node node : treeHead.childNode) {if(strings[i].equals(node.item)) {flag = true;node.supportCount+=support;treeHead = node;break;}}if(!flag) {//创建新的树节点,同时创建新的链表节点for(int j=i;j<strings.length;j++) {//⼩于最⼩⽀持度计数的不加⼊树中if(originCount.get(strings[j])<minSupportCount)continue;//创建新的树节点FP_Node node = new FP_Node(strings[j], support,treeHead);if(nowNode.containsKey(strings[j])) {//构建链表listNode = new LinkedListNode(node);nowNode.get(strings[j]).next = listNode;nowNode.put(strings[j], listNode);}else {//构建链表listNode = new LinkedListNode(node);headListNode.add(listNode);nowNode.put(strings[j], listNode);}//构建树treeHead.childNode.add(node);treeHead = node;}break;}}}while(root.childNode.size()!=0) {//判断是否为单路径if(root.childNode.size()==1) {root = root.childNode.get(0);}else {isSingle = false;break;}}if(isSingle) return true;Collections.sort(headListNode,new Comparator<LinkedListNode>() {//将链表的头节点按出现的总次数的降序排列@Overridepublic int compare(LinkedListNode o1, LinkedListNode o2) {int p = originCount.get(o2.node.item)-originCount.get(o1.node.item);if(p==0)//如果⽀持度计数相等,按字典序排序return pareTo(o2.node.item);elsereturn p;}});return isSingle;}/*** .找出各项的条件模式基,从headNode后⾯遍历链表的每个节点,* .从每个节点中node开始向树的上⽅遍历,直到根节点停⽌*/private void findConditional(ArrayList<LinkedListNode> hNode,HashMap<String, Integer> originSupport,String suffix) {//当前链表节点LinkedListNode nowListNode;//当前树节点FP_Node nowTreeNode;//条件模式基HashMap<String, Integer> originList;//所有条件模式基中各个事务出现的次数,⽅便条件FP-Tree在构造的时候剪枝HashMap<String, Integer> originCount;String ori;String item;String suf;for(int i=hNode.size()-1;i>=0;i--) {//获取链表头节点nowListNode = hNode.get(i);item = nowListNode.node.item;suf = item+suffix;//树中的单项⽀持度计数必定⼤于或等于最⼩⽀持度计数(构建树的完成的剪枝),所以将该项加其后缀加⼊频繁项集myFrequentItems.get(suf.length()).put(suf, new MyFrequentItem(suf, originSupport.get(item)));originList = new HashMap<String, Integer>();originCount = new HashMap<String, Integer>();int min;while(nowListNode!=null) {//从链表保存的树节点的⽗节点开始向上遍历nowTreeNode = nowListNode.node.parent;//获取该节点的⽀持度计数min = nowListNode.node.supportCount;//⽤来保存该条件模式基ori = "";while(nowTreeNode!=null&&nowTreeNode.item!=null) {if(originCount.containsKey(nowTreeNode.item)) {//如果条件模式基有如21和2这样两条及以上的有共同元素的,⽀持度计数叠加originCount.put(nowTreeNode.item, originCount.get(nowTreeNode.item)+min);}else {originCount.put(nowTreeNode.item, min);}//保存条件模式基,按树的上⾯向下的顺序保存ori=nowTreeNode.item+ori;nowTreeNode = nowTreeNode.parent;}if(ori!="")originList.put(ori, min);nowListNode = nowListNode.next;}if(originList.size()!=0) {//条件模式基不为空if(originList.size()==1) {//只有⼀条,直接递归其所有⼦项集for (String modeBasis : originList.keySet()) {findFrequentItem(0, "", modeBasis.toCharArray(), originList.get(modeBasis), suf,null);}}else {//构建条件FP-Treefp_Growth(originList, originCount,suf,originSupport.get(item));}}}}/**** @param j 当前指向的modeBasis中的位置* @param child 当前⼦项* @param modeBasis 条件模式基中各个字符或单路径树各个节点组成的字符串* @param support 该⼦项的所有单项中最⼩的⽀持度计数* @param suffix 后缀,⼦项加上后缀即为新的频繁项* @param originCount 单路径树各个节点的⽀持度计数*/private void findFrequentItem(int j,String child,char[] modeBasis,int support,String suffix,HashMap<String, Integer> originCount) { if(j==modeBasis.length) {if(child.length()!=0) {//⼦项不为空child=child+suffix;frequentItem = new MyFrequentItem(child, support);myFrequentItems.get(child.length()).put(child, frequentItem);}}else {int p = support;//originCount为null时,代表为条件模式基,条件模式基中各项⽀持度计数相等if(originCount!=null)p =originCount.get(String.valueOf(modeBasis[j]));findFrequentItem(j+1, child+modeBasis[j], modeBasis,support<p?support:p,suffix,originCount);//要该字符findFrequentItem(j+1, child, modeBasis,support,suffix,originCount);//不要该字符}}/*** .扫描两遍数据,第⼀遍得出各个事物出现的总次数* .第⼆遍将每条记录中的事务根据出现的总次数进⾏排序*/private void scanAndSort() {//储存单项的总次数signalCount = new HashMap<String, Integer>();String c;for (String[] string : datas) {//第⼀遍扫描,储存每个字符出现的次数for(int i=0;i<string.length;i++) {c = string[i];if(signalCount.containsKey(c)) {signalCount.put(c, signalCount.get(c)+1);}else {signalCount.put(c, 1);}}}for (String[] string : datas) {//第⼆遍扫描,按每个字符出现的总次数的降序进⾏排序Arrays.sort(string,new Comparator<String>() {@Overridepublic int compare(String o1, String o2) {int p = signalCount.get(o2)-signalCount.get(o1);if(p==0)//如果出现的次数相等,按字典序排序return pareTo(o2);elsereturn p;}});}}}View CodeMyClient.javapublic class MyClient {public static void main(String[] args) {String filePath = "src/apriori/testInput.txt";FP_tree tp_tree = new FP_tree(filePath, 2);tp_tree.startTool(0.7);}}View Code输出:1-项频繁项集为:{1,(⽀持度计数:6)} {2,(⽀持度计数:7)} {3,(⽀持度计数:6)} {4,(⽀持度计数:2)} {5,(⽀持度计数:2)}2-项频繁项集为:{2,3,(⽀持度计数:4)} {2,4,(⽀持度计数:2)} {1,3,(⽀持度计数:4)} {2,5,(⽀持度计数:2)} {1,5,(⽀持度计数:2)} {2,1,(⽀持度计数:4)} 3-项频繁项集为:{2,1,3,(⽀持度计数:2)} {2,1,5,(⽀持度计数:2)}4-项频繁项集为:5-项频繁项集为:{3,}-->{2,1,},confindence(置信度):2/6=0.3333333333333333由于此规则置信度未达到最⼩置信度的要求，不是强规则{1,}-->{2,3,},confindence(置信度):2/6=0.3333333333333333由于此规则置信度未达到最⼩置信度的要求，不是强规则{1,3,}-->{2,},confindence(置信度):2/4=0.5由于此规则置信度未达到最⼩置信度的要求，不是强规则{2,}-->{1,3,},confindence(置信度):2/7=0.2857142857142857由于此规则置信度未达到最⼩置信度的要求，不是强规则{2,3,}-->{1,},confindence(置信度):2/4=0.5由于此规则置信度未达到最⼩置信度的要求，不是强规则{2,1,}-->{3,},confindence(置信度):2/4=0.5由于此规则置信度未达到最⼩置信度的要求，不是强规则{1,}-->{2,5,},confindence(置信度):2/6=0.3333333333333333由于此规则置信度未达到最⼩置信度的要求，不是强规则{2,}-->{1,5,},confindence(置信度):2/7=0.2857142857142857由于此规则置信度未达到最⼩置信度的要求，不是强规则{2,1,}-->{5,},confindence(置信度):2/4=0.5由于此规则置信度未达到最⼩置信度的要求，不是强规则{5,}-->{2,1,},confindence(置信度):2/2=1.0为强规则{1,5,}-->{2,},confindence(置信度):2/2=1.0为强规则{2,5,}-->{1,},confindence(置信度):2/2=1.0为强规则若有不⾜之处,还请指出.。