大数据分析实验，包含五个子实验：wordCount实验，PageRank实验，关系挖掘实验，k-means算法，推荐系统算法

# 实验一 wordCount 算法及其实现 ## 1.1 实验目的 - 理解 map-reduce 算法思想与流程； - 应用 map-reduce 思想解决 wordCount 问题； - 可选）掌握并应用 combine 与 shuffle 过程。 ## 1.2 实验内容 提供 9 个预处理过的源文件（source01-09）模拟 9 个分布式节点，每个源文件中包含一百万个由英文、数字和字符（不包括逗号）构成的单词，单词由逗号与换行符分割。 要求应用 map-reduce 思想，模拟 9 个 map 节点与 3 个 reduce 节点实现 wordCount 功能，输出对应的 map 文件和最终的 reduce 结果文件。由于源文件较大，要求使用多线程来模拟分布式节点。 学有余力的同学可以在 map-reduce 的基础上添加 combine 与 shuffle 过程，并可以计算线程运行时间来考察这些过程对算法整体的影响。 提示：实现 shuffle 过程时应保证每个 reduce 节点的工作量尽量相当，来减少整体运行时间。 ## 1.3 实验过程 ### 1.3.1 编程思路 总思路如图 1-1 所示：  图 1-1：总体逻辑实现 1. map： 1. 编写面向一个 data 文件的 map 函数，具体实现逻辑就是对出现过的单词进行记录，生成形如“单词，1”的键值对，然后存入另一个 data 文件； 2. 主函数里开 9 个线程，同时处理 9 个 data 文件，并生成 9 个 map 处理后的文件。 2. reduce： 1. 编写面向三个 data 文件的 reduce 函数，具体实现逻辑就是对三个文件里的单词进行出现次数统计，生成形如“单词，出现次数”的键值对，然后存入一个 data 文件； 2. 主函数里先开三个线程分别处理 9 个 map 生成的文件，同时会生成 3 个经过 reduce 处理的文件，最后等待三个线程处理结束后，将刚刚 reduce 生成的 3 个文件作为参数再次进行一次 reduce 操作，生成最终的结果文件。 ### 1.3.2 遇到的问题及解决方式 1. map： 1. 文件处理时的细节：由于我是按照特定的字符切割行来读取的文件流，但是文件的最后一行与其他行相比少了一个换行符，由此会出现一个单词统计的错误，解决方案就是在做文件解析之前先将文件里写入一个”\n”，保证所有行之间的一致性，这样就能避免此错误； 2. 线程的实现：采用的是 threading 包里的 Thread 方法来实现多个线程。 2. reduce： 1. map 文件处理与 reduce 文件处理的一致性：由于经过 map 处理后的文件键值对的第二项均为 1，reduce 处理后的文件键值对的第二项为单词出现次数，原 reduce 函数实现时记录单词出现次数的方式肯定不能再用了，改为加上键值对第二项的数值这一逻辑后即解决了问题； 2. 线程等待的实现：使用 join()方法实现主函数的阻塞，在三个线程结束之后才开始最后结果文件的生成。 ### 1.3.3 实验测试与结果分析 1. 经过 map 处理后生成的 data 文件如下图 1-2，图 1-3 所示：  图 1-2 map 处理后生成的文件  图 1-3：spurce01_ans 文件部分内容 2. 经过 reduce 处理后生成的文件如下图 1-4，1-5 所示：  图 1-4：reduce 处理后生成的文件  图 1-5：source123 文件部分内容 3. 将三个 reduce 处理后生成的文件再进行一次 reduce 处理后生成的最终结果文件，如下图 1-6 所示：  图 1-6：final_ans 文件部分内容 ## 1.4 实验总结 通过实验一更好的理解了 mapreduce 的核心思想，也是一次对于线程操作的实践。 # 实验二 PageRank 算法及其实现 ## 2.1 实验目的 - 学习 pagerank 算法并熟悉其推导过程； - 实现 pagerank 算法；（可选进阶版）理解阻尼系数的作用； - 将 pagerank 算法运用于实际，并对结果进行分析。 ## 2.2 实验内容 提供的数据集包含邮件内容（emails.csv），人名与 id 映射（persons.csv），别名信息（aliases.csv），emails 文件中只考虑 MetadataTo 和 MetadataFrom 两列，分别表示收件人和寄件人姓名，但这些姓名包含许多别名，思考如何对邮件中人名进行统一并映射到唯一 id？（提供预处理代码 preprocess.py 以供参考）。 完成这些后，即可由寄件人和收件人为节点构造有向图，不考虑重复边，编写 pagerank 算法的代码，根据每个节点的入度计算其 pagerank 值，迭代直到误差小于 10-8 实验进阶版考虑加入 teleport β，用以对概率转移矩阵进行修正，解决 dead ends 和 spider trap 的问题。 输出人名 id 及其对应的 pagerank 值。 ## 2.3 实验过程 ### 2.3.1 编程思路 1. 对 CSV 文件进行解析，生成一个阿拉伯数字到节点的映射，一个边集用来表示节点的关联关系； 2. 通过边集与映射关系生成一个转移矩阵； 3. 通过计算公式进行迭代计算，当误差小于 0.00000001 时，迭代结束，公式为：r，β为阻尼系数，值设为 0.85 4. 根据映射关系将迭代后的结果转化成一个结果字典，最后对字典按照推荐度从大到小排序，最后写入文件。 ### 2.3.2 遇到的问题及解决方式 文件处理，即转移矩阵初始化问题：由于给的原始文件中，sender 与 receiver 的 id 是没有规律的，所以就想着通过一个映射关系来简化操作，以便生成原始的转移矩阵，具体的映射方式就是按照节点在 CSV 文件里的出现次序来赋值； ### 2.3.3 实验测试与结果分析 结果文件如下图所示：  图：final.txt 文件部分内容 ## 2.4 实验总结 PageRank 实验是最简单的一个实验，只要将初始的转移矩阵构造出来，后面要处理的东西就势如破竹，直接套公式迭代即可，重要的还是拓展了视野，了解了网页排名算法的大致思想。 # 实验三 关系挖掘实验 ## 3.1 实验内容 1. 实验内容 编程实现 Apriori 算法，要求使用给定的数据文件进行实验，获得频繁项集以及关联规则。 2. 实验要求 以 Groceries.csv 作为输入文件 输出 1~3 阶频繁项集与关联规则，各个频繁项的支持度，各个规则的置信度，各阶频繁项集的数量以及关联规则的总数 固定参数以方便检查，频繁项集的最小支持度为 0.005，关联规则的最小置信度为 0.5 ## 3.2 实验过程 ### 3.2.1 编程思路 1. 文件处理：将文件解析成一个列表，列表里的元素也为列表，列表里包含各个单词字符串； 2. 编写创建 1 项候选集函数：即将文件解析后的列表解析为单项集； 3. 编写扫描数据集函数：该函数根据设置的最小支持度生成频繁项集以及候选项集的支持度字典； 4. 编写利用频繁项集构建候选项集函数：该函数即基于 k 阶频繁项集生成 k+1 阶候选项集； 5. 编写 apriori 主函数，循环处理三次生成 1，2，3 阶频繁项集，函数逻辑如下图 3-1 所示：