java apriori

作者:原创时间:2022-03-23
文档

java apriori是什么,让我们一起了解一下?

Apriori算法是第一个关联规则挖掘算法,它利用逐层搜索的迭代方法找出数据库中项集的关系,以形成规则,其过程由连接(类矩阵运算)与剪枝(去掉那些没必要的中间结果)组成。

Apriori算法的描述如下:

(1)扫描全部数据,产生候选1-项集的集合C1。

(2)根据最小支持度,由候选1-项集的集合C1产生频繁1-项集的集合L1。

(3)对k>1,重复执行步骤(4)、(5)、(6)。

(4)由Lk执行连接和剪枝操作,产生候选(k+l)-项集的集合Ck+1。

(5)根据最小支持度,由候选(k+l)-项集的集合Ck+1,产生频繁(k+1)-项集的集合Lk+1。

(6)若L≠Φ,则k=k+1,跳往步骤(4);否则,跳往步骤(7)。

(7)根据最小置信度,由频繁项集产生强关联规则,结束。

Apriori算法如何让JAVA实现?

项集用HashMap,integer>来表示,关键字用Set集合可以自动排序,值用于记录项集在原始事物数据中出现的次数,原始数据用文件方式读取,注意文件内容每一行为一个原始事物项,不需要输入事物的编号。

package datamining;
 
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
 
public class Apriori {
//剪枝函数
public ArrayList> apriori_gen(HashMap, Integer> L_last, int last_index){
ArrayList> result = new ArrayList>();  //存储剪枝后的结果
ArrayList> item_set = null;  
item_set = get_item_set(L_last);  //获取上一个频繁项的所有项集,并转为字符串List
for(int i = 0; i < item_set.size() - 1; i++) {
ArrayList str = item_set.get(i);
for(int j = i + 1; j < item_set.size(); j++) {
Set new_item = new HashSet();  //存储新的候选项集
ArrayList str2 = item_set.get(j);
int length = str.size();
for(int k = 0; k < length - 1; k++) {         //进行join操作
if(!str.get(k).equals(str2.get(k)))
break;
else
new_item.add(str.get(k));
}
new_item.add(str.get(str.size()-1));
new_item.add(str2.get(str2.size()-1));
if(new_item.size() == length + 1 && has_infrequent_subset(new_item, item_set, last_index))  //判断新的候选项集是否满足所有K-1项子集要求
result.add(new_item);    //满足则加入结果集
}
}
return result;
}
//判断新的item的所有K-1项子集是否在上一个频繁项中都出现
public boolean has_infrequent_subset(Set candidate, ArrayList> last_item_set, int last_index) {
boolean flag = true;
ArrayList> sub_set = get_subset(candidate, last_index);
//for(int j = 0; j < sub_set.size(); j++) {
//System.out.println(sub_set.get(j));
//}
for(int i  = 0; i < sub_set.size(); i++) {
ArrayList item = sub_set.get(i);
int j = 0;
for(j = 0; j < last_item_set.size(); j++) {
if(last_item_set.get(j).equals(item))
break;
}
if( j == last_item_set.size()) flag = false;
}
return flag;
}
//获取候选项集的K-1项所有子集
public ArrayList> get_subset(Set candidate, int index){
ArrayList> sub_set = new ArrayList>();
ArrayList item_set = new ArrayList();
Iterator iter = candidate.iterator();
while(iter.hasNext())
item_set.add((String)iter.next());
if(index == 1) {         //当index等于1时单独考虑
for(int k = 0; k < item_set.size(); k++) {
ArrayList buffer = new ArrayList();
buffer.add(item_set.get(k));
sub_set.add(buffer);
}
}else {
for(int i = 0; i < item_set.size() - index + 1; i++) {
for(int j = i + 1; j < item_set.size(); j++) {
ArrayList buffer = new ArrayList();
buffer.add(item_set.get(i));
for(int k = 0; k < index - 1; k++) {   //关键步骤,循环index-1次
if((k + j) < item_set.size())
buffer.add(item_set.get(k+j));
}
if(buffer.size() == index)
sub_set.add(buffer);
}
}
}
return sub_set;
}
//获取上一个频繁项的所有项集并转为List方便处理
public ArrayList> get_item_set(HashMap, Integer> L_last){
ArrayList> result = new ArrayList>();
Iterator iter = L_last.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Set set = (Set)entry.getKey();
Iterator iter2 = set.iterator();
ArrayList item = new ArrayList();
while(iter2.hasNext()) {
String str = (String)iter2.next();
item.add(str);
}
result.add(item);
}
return result;
}
//处理原始事物数据
public HashMap, Integer> process_rawdata(ArrayList> raw_input, int min_sub){
HashMap, Integer> first_input = new HashMap, Integer>(); //存储处理后结果
//处理原始输入事物数据,统计每个单独事物的次数
for(int i = 0; i < raw_input.size(); i++) {
Set item = raw_input.get(i);
Iterator iter = item.iterator();
while(iter.hasNext()) {
String str = (String)iter.next();
Set single_item = new HashSet();
single_item.add(str);
if(first_input.containsKey(single_item)) {
int count = first_input.get(single_item);
first_input.put(single_item, count+1);
}else
first_input.put(single_item, 1);
}
}
//移除单独事物出现次数少于min_sub的事物
for (Iterator, Integer>> iter = first_input.entrySet().iterator(); iter.hasNext();){
    Map.Entry, Integer> entry = iter.next();
Object key = entry.getKey();
int val = (int)entry.getValue();
if(val < min_sub){
iter.remove();
}
}
return first_input;
}
//计数函数,记录每个候选项集在事物数据中出现的次数
public int count_item(Set item, ArrayList> raw_input) {
int count = 0;
Set item2 = new HashSet<>(item);
for(int i = 0; i < raw_input.size(); i++){
Set item_set = new HashSet(raw_input.get(i));
item_set.retainAll(item2);
if(item_set.size() == item2.size())
count++;
}
return count;
}
//算法主函数
public List, Integer>> apriori_main(ArrayList> raw_input, int min_sub){
int last_index = 1;
List, Integer>> results = new ArrayList, Integer>>(); //存储最终结果
HashMap, Integer> first_input = process_rawdata(raw_input, min_sub); //获取第一个频繁项集
ArrayList> candidates = apriori_gen(first_input, last_index); //获取第二个候选项集
while(!(candidates.size() == 0)) {   //循环终止条件,无法选出下一个候选集合为止
HashMap, Integer> result = new HashMap, Integer>();
for(int i = 0; i < candidates.size(); i++) {
int count = count_item(candidates.get(i), raw_input);  //计算每个候选项集在原始事物数据中出现次数
if(count >= min_sub)
result.put(candidates.get(i), count);  //将满足结果的加入结果集中
}
if(result.size() > 0)
results.add(result);
last_index++;                               //索引加1
candidates = apriori_gen(result, last_index);  //计算下一个候选项集合
}
return results;
}
public static void main(String args[]) throws IOException {
ArrayList> raw_data = new ArrayList>();  //存储原始数据
File file = new File(".\\data\\apriori.txt");   //获取外部原始事物数据
BufferedReader reader = new BufferedReader(new FileReader(file));
String string = "";
while((string = reader.readLine())!=null){
Set item = new HashSet();
String[] items = string.split(",");
for(int i = 0; i < items.length; i++)
item.add(items[i]);
raw_data.add(item);
}
Apriori apriori = new Apriori();
List, Integer>> result = apriori.apriori_main(raw_data, 2); //定义min_sub为2
System.out.println(result.get(result.size()-1));  //输出最后结果
}
}

以上就是小编今天的分享了,希望可以帮助到大家。



显示全文
java archive java arcsin java arccos java arctan java args java arrays.sort java ascii java asmx java aspectj java aspose java assembly java async win10专业版和企业版的区别 java bacnet java barrier java base64 java base64decoder java bean 手机充电时可以玩手机吗 手机充电发热发烫是什么原因 java application java append 苹果13蓝牙搜索不到设备怎么办 java apns java ant java annotation java android iphone呼叫失败是什么原因 java algorithm ipad2是哪年的 java akka java aggregation java aes加密 java advice java addall java add java actuator 西北五省是哪五省 java activity java activiti