综合实践能力创新实训（2）实验报告
《数据挖掘》实验报告
专业班级：
姓 名：
学 号：
指导教师：
时 间：
地 点：
指导教师评语：
签名：
年 月 日
成绩： 等级：
综合实践能力创新实训（2）实验报告
1
目录
实验一 Apriori 算法设计与应用 ....................................................1
实验二 KNN 算法设计与应用 ........................................................6
实验三 DBSCAN 算法设计与应用...............................................11
实验四 Kmeans 算法设计与应用 .................................................17
实验五 PageRank 算法设计与应用 .............................................23
综合实践能力创新实训（2）实验报告
1
一、实验题目
实验一 Apriori 算法设计与应用
二、背景介绍
Apriori 算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选
集生成和向下封闭检测两个阶段来挖掘频繁项集。
三、实验内容
1.3.1 运用的理论知识
关联规则挖掘是数据挖掘中最活跃的研究方法之一，最初的动机是针对购物
篮分析问题提出的，其目的是为了发现交易数据库中不同商品之间的练习规则。
通过用户给定的最小支持度，寻找所有频繁项目集，即满足 Support 不小于 Minsup
port 的所有项目子集。通过用户给定的最小可信度，在每个最大频繁项目集中，
寻找 Confidence 不小于 Minconfidence 的关联规则。
支持度：支持度就是几个关联的数据在数据集中出现的次数占总数据集的比
重。或者说几个数据关联出现的概率。
置信度：置信度体现了一个数据出现后，另一个数据出现的概率，或者说数
据的条件概率。
1.3.2 实验原理
Apriori 算法基本思想：
首先扫描数据库中所需要进行分析的数据，在设置完支持度以及置信度以后，
在最小支持度的支持下产生频繁项，即统计所有项目集中包含一个或一个以上的
元素频数，找出大于或者等于设置的支持度的项目集。其次就是频繁项的自连接。
再者是如果对频繁项自连接以后的项的子集如果不是频繁项的话，则进行剪枝处
理。接着对频繁项处理后产生候选项。最后循环调用产生频繁项集。
1.3.3 算法详细设计
（1）定义数据集、最小支持度、最小支持数、最小置信度以及存放所有频
繁项目集的 Map 集合。调用就封装好的 initDataList()方法对数据进行初始化。
（2）调用 getAllElement()方法获取到数据集所含有的所有类别元素 allEleme
nt，将 allElement 数组进行排列组合获取候选集 candidateL1。调用 getItemSets()
方法遍历 candidateL1，将出现次数不小于最小支持数 minSupportCount 的项加入
综合实践能力创新实训（2）实验报告
2
到 itemSets 中，遍历结束，获取到 1-频繁项目集 L1，并将 L1 打印输出。
（3）开始循环找 k-频繁项目集，直到得到的 k-频繁项目集 Lk 为空，跳出
循环。在循环体内部，将 k-1-候选集 candidateLast 所含有的所有类别元素 allEleme
ntLast 作为参数调用 getCombination()方法，获取 k-候选集 candidateNow，遍历 k-
候选集，将出现次数不小于最小支持数的项加入到 itemSets 并返回，得到频繁项
目集 Lk。如果 k-频繁项集为空，则结束循环，若 Lk 不为空，则将 Lk 加入到存
放所有频繁项目集 allItemSets 的集合中，方便之后找强关联规则。
（4）调用 correlation()方法进行强关联规则的挖掘。在方法体内部，遍历所
有的频繁项目集，得到每一项频繁项目集的非空子集集合 subSet，遍历每一项频
繁项目集的非空子集，以此非空子集和此频繁项目集作为参数，调用 isConfidence
()方法判断是否满足置信度大于最小置信度，若满足，则输出此非空子集==>非
空子集的补集。
1.3.4 关键源代码
/**
* 获取候选集
* @param allItemStr 含频繁项目集所有元素的数组
* @param k 要生成 k 候选集
* @return
*/
public static List<String[]> getCombination(String[] allItemStr, int k){
//定义候选集
List<String[]> candidateSets = new ArrayList<>();
//对 allItemStr 进行 k 组合
IGenerator<List<String>> candidateList = Generator.combination(allItemStr).simple(k);
for (List<String> candidate : candidateList) {
String[] candidateStr = candidate.toArray(new String[candidate.size()]);
candidateSets.add(candidateStr);//将每一项组合放入候选集中
}
return candidateSets;
}
/**
* 处理候选集，获取频繁项目集
* @param itemList 候选集
* @return 频繁项目集
*/
public static Multimap<Integer, String[]> getItemSets(List<String[]> itemList){
Multimap<Integer, String[]> itemSets = ArrayListMultimap.create(); //项目集
//得到排列组合结果（候选集）每一项在数据集中出现的次数
Multimap<Integer, String[]> itemCount = getItemCount(itemList);
//使用迭代器遍历 multimap
综合实践能力创新实训（2）实验报告
3
Iterator<Map.Entry<Integer, String[]>> iterator = itemCount.entries().iterator();
//遍历排列组合结果的每一项，将出现次数不小于 minSupportCount 的项加入到
itemSets
while (iterator.hasNext()){
Map.Entry<Integer, String[]> entry = iterator.next();
if (entry.getKey() >= minSupportCount){
itemSets.put(entry.getKey(), entry.getValue());
}
}
return itemSets;
}
/**
* 找强关联规则
*/
public static void correlation(){
//遍历所有频繁项目集
for (int k = 1; k <= allItemSets.size(); k++) {
//获取 k-频繁项目集
Multimap<Integer, String[]> keyItemSet = allItemSets.get(k);
Iterator<Map.Entry<Integer, String[]>> iterator = keyItemSet.entries().iterator();
//遍历 k 频繁项目集
while (iterator.hasNext()){
Map.Entry<Integer, String[]> entry = iterator.next();
String[] value = entry.getValue();
// List<String> valueList = Arrays.asList(value);
// List<String> valueList = new ArrayList<>();
// Collections.addAll(valueList, value);
//求 value 的非空子集
for (int i = 1; i < value.length; i++) {
List<String[]> subSet = getCombination(value, i); //非空子集的集合
for (String[] subSetItem : subSet) { //subSetItm 是频繁项目集每一个非空
子集
List<String> valueList = new ArrayList<>();
Collections.addAll(valueList, value);
List<String> subSetItemList = Arrays.asList(subSetItem);
//去除已经求得子集后的 valueList
valueList.removeAll(subSetItemList); //此时 valueList 中存放非空子
集的补集
if (isConfidence(subSetItem, value)){
System.out.println(Arrays.toString(subSetItem) + "==>" +
Arrays.toString(valueList.toArray(new String[valueList.size()])));
}
}
}
