Apriori算法学习和java实现

2024-05-16 05:08
文章标签 java 算法 实现 学习 apriori

本文主要是介绍Apriori算法学习和java实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

关联规则挖掘可以发现大量数据中项集之间有趣的关联或相关联系。一个典型的关联规则挖掘例子是购物篮分析，即通过发现顾客放入其购物篮中的不同商品之间的联系，分析顾客的购物习惯，从而可以帮助零售商指定营销策略，引导销售等。国外有"啤酒与尿布"的故事，国内有泡面和火腿的故事。本文以Apriori算法为例介绍关联规则挖掘并以java实现。

什么是关联规则：

对于记录的集合D和记录A，记录B,A,B属于D：  A--->B  [support(A->B)=p(AUB) ,confidence(A->B)=p(B|A) ]

关联规则的表示形式：

泡面 ------>火腿[support=0.2,confidence=0.8]

规则的支持度和置信度是两个规则兴趣度度量，它们分别反映发现规则的有用性和确定性。上式表示同时购买泡面和火腿的记录占全部记录的2%（实际应该没这么多的，不然天天吃泡面），置信度0.8表示在购买泡面的记录中，有80%的人同时购买火腿（反正我就是属于80%的。

如果挖掘的关联规则满足最小支持阈值和最小置信度阈值，则称关联规则是有趣的。

重要性质：频繁项集的所有非空子集都必须是频繁的。（一个集合如果不能通过测试，则它的所有超集也不能通过测试）


Apriori算法思想：逐层搜索的迭代方法，首先寻找1-项频繁集的集合，集合记做L1， L1用于寻找两项频繁集合L2，L2用于寻找L3，如此下去，直到不能找K项频繁集合。

Apriori算法迭代的两个阶段：

 1连接步；为找L（k） ，通过将L（k-1）与自身连接产生候选K项集的集合。

2减枝步；根据项的支持度计数去掉非频繁的候选集合，确定频繁集反复迭代直到不能产生满足最小支持度的集合为止。

Apriori重要性质：频繁项集的所有非空子集都必须是频繁的在减枝中的应用就在于，对于候选集只要它不是频繁的，就可以删除掉，这样大大减少数据量。

下面直接上算法流程图：


下面举例说明：



下面直接贴代码：部分地方写的有点冗余，程序有点长的主要原因是向控制台输出挖掘的过程，这样便于理解算法的挖掘过程

但是算法思路是清晰的，基本上一个while就能搞定。


package cluster;import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;/*** Apriori算法实现 最大模式挖掘，涉及到支持度，但没有置信度计算* @author push_pop**/
public class AprioriMyself {private static final double MIN_SUPPROT = 0.2;//最小支持度private static boolean endTag = false;//循环状态static List<List<String>> record = new ArrayList<List<String>>();//数据集public static void main(String args[]){//*************读取数据集**************record = getRecord();//控制台输出记录System.out.println("以矩阵形式读取数据集record");for(int i=0;i<record.size();i++){List<String> list= new ArrayList<String>(record.get(i));for(int j=0;j<list.size();j++){System.out.print(list.get(j)+" ");}System.out.println();}//************获取候选1项集**************List<List<String>> CandidateItemset = findFirstCandidate();//控制台输出1项候选集System.out.println("第一次扫描后的1级 备选集CandidateItemset");for(int i=0;i<CandidateItemset.size();i++){List<String> list = new ArrayList<String>(CandidateItemset.get(i));for(int j=0;j<list.size();j++){System.out.print(list.get(j)+" ");}System.out.println();}//************获取频繁1项集***************List<List<String>> FrequentItemset = getSupprotedItemset(CandidateItemset);//控制台输出1项频繁集System.out.println("第一次扫描后的1级 频繁集FrequentItemset");for(int i=0;i<FrequentItemset.size();i++){List<String> list = new ArrayList<String>(FrequentItemset.get(i));for(int j=0;j<list.size();j++){System.out.print(list.get(j)+" ");}System.out.println();}//***************迭代过程**************while(endTag!=true){//**********连接操作****由k-1项频繁集      获取      候选k项集**************List<List<String>> nextCandidateItemset = getNextCandidate(FrequentItemset);System.out.println("扫描后备选集");for(int i=0;i<nextCandidateItemset.size();i++){List<String> list = new ArrayList<String>(nextCandidateItemset.get(i));for(int j=0;j<list.size();j++){System.out.print(list.get(j)+" ");}System.out.println();}//**************减枝操作***由候选k项集       获取     频繁k项集****************List<List<String>> nextFrequentItemset = getSupprotedItemset(nextCandidateItemset);System.out.println("扫描后频繁集");for(int i=0;i<nextFrequentItemset.size();i++){List<String> list = new ArrayList<String>(nextFrequentItemset.get(i));for(int j=0;j<list.size();j++){System.out.print(list.get(j)+" ");}System.out.println();}//*********如果循环结束，输出最大模式**************if(endTag == true){System.out.println("Apriori算法--->频繁集");for(int i=0;i<FrequentItemset.size();i++){List<String> list = new ArrayList<String>(FrequentItemset.get(i));for(int j=0;j<list.size();j++){System.out.print(list.get(j)+" ");}System.out.println();}}//****************下一次循环初值********************CandidateItemset = nextCandidateItemset;FrequentItemset = nextFrequentItemset;}}/*** 读取txt数据* @return*/public static List<List<String>> getRecord() {List<List<String>> record = new ArrayList<List<String>>();try {String encoding = "GBK"; // 字符编码(可解决中文乱码问题 )File file = new File("simple.txt");if (file.isFile() && file.exists()) {InputStreamReader read = new InputStreamReader(new FileInputStream(file), encoding);BufferedReader bufferedReader = new BufferedReader(read);String lineTXT = null;while ((lineTXT = bufferedReader.readLine()) != null) {//读一行文件String[] lineString = lineTXT.split("	");List<String> lineList = new ArrayList<String>();for (int i = 0; i < lineString.length; i++) {//处理矩阵中的T、F、YES、NOif (lineString[i].endsWith("T")|| lineString[i].endsWith("YES"))lineList.add(record.get(0).get(i));else if (lineString[i].endsWith("F")|| lineString[i].endsWith("NO"));// F，NO记录不保存elselineList.add(lineString[i]);}record.add(lineList);}read.close();} else {System.out.println("找不到指定的文件！");}} catch (Exception e) {System.out.println("读取文件内容操作出错");e.printStackTrace();}return record;}/*** 有当前频繁项集自连接求下一次候选集* @param FrequentItemset* @return*/private static List<List<String>> getNextCandidate(List<List<String>> FrequentItemset) {List<List<String>> nextCandidateItemset = new ArrayList<List<String>>();for (int i=0; i<FrequentItemset.size(); i++){HashSet<String> hsSet = new HashSet<String>();HashSet<String> hsSettemp = new HashSet<String>();for (int k=0; k< FrequentItemset.get(i).size(); k++)//获得频繁集第i行hsSet.add(FrequentItemset.get(i).get(k));int hsLength_before = hsSet.size();//添加前长度hsSettemp=(HashSet<String>) hsSet.clone();for(int h=i+1; h<FrequentItemset.size(); h++){//频繁集第i行与第j行(j>i)连接   每次添加且添加一个元素组成    新的频繁项集的某一行，   hsSet=(HashSet<String>) hsSettemp.clone();//！！！做连接的hasSet保持不变for(int j=0; j< FrequentItemset.get(h).size();j++)hsSet.add(FrequentItemset.get(h).get(j));int hsLength_after = hsSet.size();			if(hsLength_before+1 == hsLength_after && isSubsetOf(hsSet,record)==1 && isnotHave(hsSet,nextCandidateItemset)){//如果不相等，表示添加了1个新的元素，再判断其是否为record某一行的子集     若是则其为  候选集中的一项Iterator<String> itr = hsSet.iterator();List<String>  tempList = new ArrayList<String>();while(itr.hasNext()){String Item = (String) itr.next();tempList.add(Item);}nextCandidateItemset.add(tempList);}}}return nextCandidateItemset;}/*** 判断新添加元素形成的候选集是否在  新的候选集中* @param hsSet* @param nextCandidateItemset* @return*/private static boolean isnotHave(HashSet<String> hsSet,List<List<String>> nextCandidateItemset) {// TODO Auto-generated method stubList<String>  tempList = new ArrayList<String>();Iterator<String> itr = hsSet.iterator();while(itr.hasNext()){String Item = (String) itr.next();tempList.add(Item);}for(int i=0; i<nextCandidateItemset.size();i++)if(tempList.equals(nextCandidateItemset.get(i)))return false;return true;}/*** 判断hsSet是不是record2中的某一记录子集* @param hsSet* @param record2* @return*/private static int isSubsetOf(HashSet<String> hsSet,List<List<String>> record2) {//hsSet转换成ListList<String>  tempList = new ArrayList<String>();Iterator<String> itr = hsSet.iterator();while(itr.hasNext()){String Item = (String) itr.next();tempList.add(Item);}		for(int i=1;i<record.size();i++){List<String>  tempListRecord = new ArrayList<String>();for(int j=1;j<record.get(i).size();j++)tempListRecord.add(record.get(i).get(j));if(tempListRecord.containsAll(tempList))return 1;}return 0;}/*** 由k项候选集剪枝得到k项频繁集* @param CandidateItemset* @return*/private static List<List<String>> getSupprotedItemset(List<List<String>> CandidateItemset) {// TODO Auto-generated method stubboolean end = true;List<List<String>> supportedItemset = new ArrayList<List<String>>();int k = 0;for (int i = 0; i < CandidateItemset.size(); i++){int count = countFrequent(CandidateItemset.get(i));//统计记录数if (count >= MIN_SUPPROT * (record.size()-1)){	supportedItemset.add(CandidateItemset.get(i));end = false;}}endTag = end;//存在频繁项集则不会结束if(endTag==true)System.out.println("无满足支持度项集,结束连接");return supportedItemset;}/*** 统计record中出现list集合的个数* @param list* @return*/private static int countFrequent(List<String> list) {// TODO Auto-generated method stubint count = 0;for(int i = 1; i<record.size(); i++) {boolean notHaveThisList = false;for (int k=0; k < list.size(); k++){//判断record.get(i)是否包含listboolean thisRecordHave = false;for(int j=1; j<record.get(i).size(); j++){if(list.get(k).equals(record.get(i).get(j)))//list。get(k)在record。get(i)中能找到thisRecordHave = true;}if(!thisRecordHave){//只要有一个list元素找不到，则退出其余元素比较,进行下一个record。get(i)比较notHaveThisList = true;break;}}if(notHaveThisList == false)count++;}return count;}/*** 获得一项候选集* @return*/private static List<List<String>> findFirstCandidate() {// TODO Auto-generated method stubList<List<String>> tableList = new ArrayList<List<String>>();HashSet<String> hs  = new HashSet<String>();for (int i = 1; i<record.size(); i++){  //第一行为商品信息for(int j=1;j<record.get(i).size();j++){hs.add(record.get(i).get(j));}}	Iterator<String> itr = hs.iterator();while(itr.hasNext()){List<String>  tempList = new ArrayList<String>();String Item = (String) itr.next();tempList.add(Item);tableList.add(tempList);}return tableList;}
}





Apriori算法的缺陷也是很明显的：

1 .若数据量较大，将大量的候选集。N个频繁1项集可能产生(N-1)*N/2个候选2项集

 2   数据库需要多边扫描，频繁集每自连接一次，就要重新扫面一次数据。

关于其改进将在下一篇博客写出--不产生候选集的关联规则挖掘算法FPTree  

这篇关于Apriori算法学习和java实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/993962。

相关文章

HarmonyOS学习(七)——UI（五）常用布局总结

HarmonyOS学习(七)——UI（五）常用布局总结

自适应布局 1.1、线性布局（LinearLayout） 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列，Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距，达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式，且在各类尺寸屏幕上表现一致，其中交叉轴为垂直时，取值为Vert
阅读更多...
Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya（不是本人，claude AI）在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容： 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用
阅读更多...
JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2