一种基于并行化关联规则算法的教育云应用统计方法

摘要

本发明涉及一种基于并行化关联规则算法的教育云应用统计方法，首先对教育云应用访问情况进行数据建模，将源数据以布尔矩阵的形式存储在分布式文件系统HDFS中；其次基于MapReduce框架对关联规则算法进行并行化优化，分别编写Map函数和Reduce函数，对存储在分布式文件系统HDFS中的源数据进行挖掘分析，然后得到访问者对教育云应用的使用情况，进行特色推荐。发明的技术方案大大减少了扫描数据项集的次数，降低了系统I/O消耗。

说明书

技术领域

本发明涉及一种基于并行化关联规则算法的教育云应用统计方法，属于计算机统计的技术领域。

背景技术

近年来，随着互联网和云计算技术的发展，数据产生的速度和规模大大超过以往。海量数据中蕴含着大量的价值，如何快速有效的利用数据，这是大数据时代我们面临的一大挑战。教育云平台是云计算技术向教育领域的迁移，包括了教育信息化所必需的一切硬件计算资源，这些资源经过虚拟化之后，向用户提供一个平台，以云应用的形式提供教育云服务。教育云平台通过在SaaS(Software as a service)层部署教育云应用，通过网页浏览器或其他客户端软件来接入，远程服务器上的应用通过网络来运行。随着教育云应用的不断丰富，远程服务器端产生的数据量也在迅速增加。

数据挖掘方法作为处理和利用数据的有效途径，诞生于上世纪90年代，由于当时数据量在规模和复杂度方面不大，传统的数据挖掘算法完全可以处理。但是随着大数据时代的到来，有限的存储资源和计算资源，再加上算法本身对海量数据处理的适应性，形成了数据挖掘的瓶颈。其中，关联规则挖掘是数据挖掘领域一项很重要的方法。关联规则挖掘的主要思想是随着数据量的增加，数据项之间一定存在着某种关联关系，因此算法主要实现的就是对这种关联规则的挖掘。目前，常用的关联规则挖掘相关算法有：Apriori算法、FPTree算法、Eclat算法以及决策树分类等，它们往往只面向小规模数据量的处理，而且处理系统相对单一，并不能适应大规模集群系统的关联规则分析。由于传统数据挖掘方法本身计算量很大，在运算过程中会产生大量中间结果，需要频繁扫描数据库，大大增加了系统I/O消耗，随着数据量的增大，有限的内存很难进行海量数据的处理，随着数据量的爆炸式增长，传统方法很难满足用户需求。

现有的技术中也存在并行化关联分析方法，中国专利CN103914528A的发明专利申请“一种关联分析算法的并行化方法”，该发明申请公开了一种针对经典关联规则分析算法Apriori的优化，但该方法主要是基于分布式系统自有的文件分发机制对原始数据进行处理，本质上仍需频繁扫描原始数据的一部分，在性能方面并不能达到很好的效果。

中国专利CN101799810A，该专利公开了一种关联规则挖掘方法及其系统。方法包括：由频繁K项集生成K+1项集；执行多个并行的处理任务，其中，每个处理任 务获取事务数据集中相应部分的数据，并统计K+1项集在该部分数据中的频繁计数值；对所有处理任务的统计结果进行汇总得到K+1项集在所述事务数据集中的频繁计数值，根据K+1项集的频繁计数值生成满足支持度要求的频繁K+1项集，并根据所述频繁K+1项集在判断有满足可信度要求的关联规则时输出该关联规则。该专利所述方法是关联规则算法在分布式框架下的执行，而本发明首先基于并行化架构对原始数据进行数据建模，建模后的数据再依据MapReduce框架进行迭代，得到频繁项集和关联规则，并针对教育云这一应用场景进行图形化展示，运行效率更高。

中国专利申请CN103150163A，该专利公开了一种基于MapReduce模型的并行关联方法。该方法首先对数据进行预处理，设置最小支持度和最小置信度；然后经特殊处理1项集，求得第1项集和第2项集；然后配置第k项集，执行后再统计出k项集的计数，通过主进程读取第k个任务的输出，计算支持度，获得频繁k项集和k+1项候选集，并设置k＝k+1，开始循环，直至k+1项候选集为空。该专利所述方法是关联规则算法的一般步骤在分布式框架MapReduce下的执行，而本发明创新性地对原始数据进行建模，然后对分布式框架的输入输出进行了设置，通过迭代计算，得到关联规则，算法运行效率更高。

现有技术中还没有一种基于MapReduce框架通过数据预处理和数据建模对数据的关联规则进行挖掘的方法。因此，开发出一种适用于大数据信息挖掘处理的规则算法是当前的热点和难点。

发明内容

针对现有技术的不足，本发明具体提出了一种基于并行化关联规则算法的教育云应用统计方法。

本发明的技术方案如下：

发明概述：

一种基于并行化关联规则算法的教育云应用统计方法，首先获取教育云应用的访问情况，对教育云应用访问情况进行数据建模，将源数据以布尔矩阵的形式存储在分布式文件系统HDFS中；其次基于MapReduce框架对关联规则算法进行并行化优化，分别编写Map函数和Reduce函数，对存储在分布式文件系统HDFS中的源数据进行挖掘分析，然后得到访问者对教育云应用的访问情况。

发明详述：

一种基于并行化关联规则算法的教育云应用统计方法，具体步骤如下：

步骤一、从教育云服务器获取日志信息数据并定时上传到集群节点的分布式文件系统HDFS中；

步骤二、以存储在HDFS中的日志信息数据作为源数据，进行数据库数据建模；

步骤三、源数据经过建模之后，以数据项集文件的形式存储在HDFS中，每一行代表一个访问者的点击流序列；在进行频繁项集和关联规则挖掘之前，采用二进制 表示法，将数据项集转换成布尔矩阵，布尔矩阵存储在分布式文件系统HDFS中；

步骤四、关联规则挖掘：基于MapReduce对传统的挖掘方法进行并行化优化，具体步骤为：

10)扫描存储在分布式文件系统HDFS中的布尔矩阵，生成频繁项集；

11)生成关联规则：由频繁项集生成关联规则；

步骤五、根据步骤四的步骤10)生成的频繁项集，以图形化形式向访问者展示教育云应用的使用情况。

根据本发明优选的，所述的一种基于并行化关联规则算法的教育云应用统计方法中，步骤一的具体步骤如下：首先编写shell脚本，通过cp命令复制日志信息数据到备份目录，然后使用tar命令对日志信息数据进行打包；通过修改crontab，制定计划任务，实现日志信息数据的定期打包备份；在crontab中添加计划任务，通过scp命令将每周的打包日志信息数据上传到集群节点的分布式文件系统HDFS中。

根据本发明优选的，所述的一种基于并行化关联规则算法的教育云应用统计方法中，步骤二的具体步骤如下：

1)建立教育云应用和访问者访问路径的对应关系：建立如表1所示的应用名称与访问路径映射表，对应关系为：{(01,高中教学,/union/senior/index.html),(02,初中教学,/union/junior/index.html),(03,小学教育,/union/primary/index.html),(04,儿童教育,/union/child/index.html),(05,网络磁盘,/union/disk/index.html),(06,在线影音,/union/media/index.html),(07,在线编辑,/union/edit/index.html),(08,在线考试,/union/test/index.html)}；

表1 应用名称与访问路径映射表

ID应用名称访问路径01高中教学/union/senior/index.html02初中教学/union/junior/index.html03小学教育/union/primary/index.html04儿童教育/union/child/index.html05网络磁盘/union/disk/index.html06在线影音/union/media/index.html07在线编辑/union/edit/index.html08在线考试/union/test/index.html

2)以存储在HDFS中的日志信息数据作为源数据，日志信息数据逐行存储，每一行记录了访问者访问教育云平台的信息，每一行的格式为<remotehost,ident,authuser,date,request,status,bytes,referrer,agent>，其中remotehost为访问主机地址或者已解析的域名，ident为标示符，authuser为授权访问者，用于记录访问者进 行身份验证时提供名字，date为日期时间，request为请求资源的URL，包括请求类型、请求资源、协议版本号，status为状态码，表示服务器的响应状态，bytes为传输的字节数，referrer为来源页面的URL，表示浏览者在访问该页面之前所浏览的页面，agent为访问者的详细信息；编写shell脚本，使用awk命令分割每一行，获取每行的<remotehost,date,request,referrer>四个字段，再存入分布式文件系统HDFS中；

3)基于分割所获取的字段生成访问序列：基于字段date获取同一时间段的记录<remotehost,request,referrer>，其中request和referrer字段根据表1所示的应用名称与访问路径映射表映射为相应的ID，然后基于字段remotehost进行排序，同一remotehost视为同一访问者；

4)针对每个访问者的访问序列生成数据项集；每行的访问序列的格式为<referrer,request>，其中referrer为来源页面的URL，request为请求资源的URL，基于MapReduce进行单表连接。

根据本发明优选的，所述的一种基于并行化关联规则算法的教育云应用统计方法中，步骤二的步骤4)，具体方法如下：

a)输入访问序列；

b)在map阶段，将读入数据分割成referrer和request后，将request设置成key，referrer设置成value进行输出，并作为输出左表，在输出value的开始处加上字符“L”，表示左表，这样输出左表的数据格式为<request,<”L”,referrer,request>>；

数据以列存储的形式，存储在HBase中，在HBase中，Key‐Value存储以KeyValue类进行表示，Key‐Value包括四部分：Key、TimeStamp、Type和Value四部分；

c)在map阶段，将读入数据分割成referrer和request后，将referrer设置成key，request设置成value进行输出，并作为输出右表，在输出value的开始处加上字符“R”，表示右表，这样输出右表的输出数据格式为<referrer,<”R”,referrer,request>>,数据以列存储的形式存储在HBase中；

d)在shuffle阶段完成排序和连接：首先把输出左表和输出右表根据key值进行排序，排序后再把输出左表和输出右表中key值相同的项进行连接，放在一起，生成value‐list；

e)在reduce阶段，会接收到shuffle连接的结果，取出每个key的value‐list进行解析，对输出左表和输出右表的value计算笛卡尔积，求出部分页面跳转序列；

f)循环迭代map和reduce过程，对步骤二的步骤4)中的步骤e)中输出的结果继续进行连接，得到完整的页面跳转序列，此时，完整的页面跳转序列中的key代表步骤二中步骤1)中表1所示的应用名称与访问路径映射表中某个应用对应的ID，value为对应ID的完整的页面跳转序列；

g)根据日志信息数据，对不同的访问者，即对不同的remotehost执行步骤二中 步骤4)中的步骤a)到步骤f)，得到指定时间段内所有访问者的访问序列，形成数据项集，所述数据项集的数据格式如下：

01，03，06，02，04，07，08

02，03，06，09，04，10，08，06

02，04，07，08

04，03，09，02，07

06，08，04，03，01，02，09

01，03，05，07，09，06，04

02，04，06，03，05，09，08

04，03，02，06，08，05，08

02，031，05，07，09，03，02。

根据本发明优选的，所述的一种基于并行化关联规则算法的教育云应用统计方法中，步骤三的具体步骤如下：

5)扫描一次数据项集，将数据项集中的每个项目都看作是一个属性，计算数据项集中出现的项目的个数，所述的项目为所有访问者访问过的应用对应的ID；

6)如果一个事务包含某个项目，即该访问者访问了这个应用，那么相应的那个属性值就是1，否则就是0；设数据项集为T＝{t₁,t₂,……,t_n}，项目集为I＝{i₁,i₂,……i_m}，对于数据项集中的每一项D，有f：D‐>r_ij，f(D)＝r_ij，r_ij定义为：

$r_{\mathrm{ij}}=\left(\begin{array}{cc}1,& i_j\in t_k\\ 0,& i_j\notin t_k\end{array}\right)$

7)构造数据项集对应的布尔矩阵，包括m个数据项集记录和n个项目，即m行n列，通过一次扫描获得下面的布尔矩阵：

$\left(\begin{array}{ccccc}\mathrm{TID}& I_1& I_2& ...& I_n\\ T1& r_{11}& r_{12}& ...& r_{1n}\\ T2& r_{21}& r_{22}& ...& r_{2n}\\ .& .& .& & .\\ .& .& .& & .\\ .& .& .& & .\\ \mathrm{Tm}& r_{m1}& r_{m2}& ...& r_{\mathrm{mn}}\end{array}\right)$

r_ij取1，表示第i个数据项集记录包含第j个项目，r_ij取0，表示第i个数据项集记录不包含第j个项目；

8)采用稀疏矩阵的存储方式，在布尔矩阵文件中只存储非零数值：在存储的时候采用三元组记录矩阵中的每一个元素，存储矩阵的文件每一条记录的结构如下：

(i,j,A[i,j])

其中，第一个字段i为行标签，第二个字段j为列标签，第三个字段A[i,j]表示该元素的值，值为0的元素在存储矩阵的文件中不存储；

9)生成的布尔矩阵存储在分布式文件系统HDFS中。

根据本发明优选的，所述的一种基于并行化关联规则算法的教育云应用统计方法中，步骤四的步骤10)的具体步骤如下：

关联规则的定义如下：两个不相交的非空集合X、Y，如果有X‐‐>Y，就说X‐‐>Y是一条关联规则。频繁项集是指频繁出现的数据项记录，支持度的定义为：集合X与集合Y中的项在一条记录中同时出现的次数/数据记录的个数。

$\mathrm{support}=\frac{(X\cup Y).\mathrm{count}}{n}$

置信度的定义为：集合X与集合Y中的项在一条记录中同时出现的次数/集合X出现的个数。

$\mathrm{confidence}=\frac{(X\cup Y).\mathrm{count}}{X.\mathrm{count}}$

定义最小值支持度min_support和最小置信度min_confidence，关联规则挖掘定义为：给定一个数据项集T，找出其中所有支持度support>＝min_support，置信度confidenct>＝min_confidence的关联规则。

步骤四中，步骤10)生成频繁项集的具体步骤如下：

h)扫描存储在分布式文件系统HDFS中的布尔矩阵；

i)计算所有只包含一个项目的数据项在数据项集中的支持度，据此得到初始的频繁1‐项集，即F1，所述的1‐表示该集合的基数为1，即只含有一个元素，同理x‐表示集合含有x个元素，计算过程基于Map和Reduce两个函数进行，具体计算过程如下：

①当数据传递给Map时，Map会将输入的矩阵分块进行分割，输出<key,value>形式的数对，具体的数据结构为<j,<i,j,A[i,j]>>，其中键j为矩阵列，值为三元组<i,j,A[i,j]>，三元组中：i为元素所在行号，j为元素所在列号，A[i,j]为对应的元素值，此处元素值都为1；

②Map处理的中间结果传递给Reduce时，中间结果已经通过shuffle阶段按照key进行了排序，Reduce阶段主要是将相同的key对应的value值累加，Reduce阶段将输入的key值，即矩阵列的值作为输出的key值，相同key对应的value值累加，作为输出的value值；

③由步骤②得到的<key,value>中的key对应数据项，value代表数据项对应的支持度，将每个key对应的value与最小支持度min_support比较，舍弃小于min_support的项，剩余项合并为频繁1‐项集F1；

j)对频繁1‐项集F1中的任意两项进行合并生成候选2‐项集C2，这个过程通过排列组合完成；

k)根据向下封闭原理剔除步骤j)得到的候选2‐项集C2中不满足条件的候选项，所述不满足条件的候选项为小于最小支持度的候选项，所述的向下封闭原理为如果一个集合不是频繁项集，则它的所有超集都不是频繁项集；

l)通过Map计算和Reduce计算，统计候选2‐项集中每个数据项的支持度，与最小支持度min_support进行比较，得到频繁2‐项集，具体的计算过程如下：

④在Map阶段根据候选2‐项集的字符串，在矩阵内对应的2个列向量之间做逻辑与运算，将每一行的运算结果相加得到候选2‐项集的局部支持度，若为0则丢弃，形成第一<key,value>对，所述第一<key,value>对中的key表示候选2‐项集的候选项，value代表该候选项的局部支持度；

⑤Reduce函数对Map生成的候选2‐项集的局部支持度进行合并，得到候选k‐项集的支持度，输入为第一<key,value>对，将key相同的第一<key,value>对的value进行相加，得到第二<key,value>对，所述第二<key,value>对中的key还是表示候选2‐项集的候选项，value值为候选项的支持度，将每个候选项的支持度与min_support进行比较，得到频繁2‐项集；

m)依次类推，逐级搜索，第(k‐1)轮搜索生成的频繁项集F_k-1作为种子集合产生候选项集C_k，产生的候选项集C_k再根据向下封闭原理进行剪枝，所述的剪枝为消除不满足向下封闭原理的项集；

n)将步骤四的步骤10)中，步骤h)至步骤m)生成的频繁项集写入文件并存储在分布式文件系统HDFS中。

根据本发明优选的，所述的一种基于并行化关联规则算法的教育云应用统计方法中，步骤四的步骤11)的具体步骤如下：

o)从分布式文件系统HDFS中逐行读取频繁项集；

p)对于每个频繁项集F，产生F的所有非空子集，进而生成规则，该过程通过排列组合进行计算；

q)根据置信度的计算方法，计算每个规则的置信度，然后和最小置信度min_confidence进行比较，将小于最小置信度的规则删除，剩下的即关联规则；

r)将步骤四的步骤11)中步骤q)生成的关联规则写入文件并存储在分布式文件系统HDFS中。

根据本发明优选的，所述的一种基于并行化关联规则算法的教育云应用统计方法中，步骤五的具体步骤如下：

12)从分布式文件系统HDFS中读取频繁项集文件；

13)筛选出频繁1‐项集，即只有一个元素的集合，该集合key的编号即步骤一中表1应用名称与访问路径映射表中教育云应用对应的ID，对应的value值就是该应 用的使用次数；

14)调用jfreechart类库编写java程序，把步骤五的步骤13)中的使用次数数据以柱状图和折线图的形式呈现给访问者。

本发明对原始日志数据基于分布式框架进行预处理，然后基于MapReduce框架通过数据建模对数据的关联规则进行挖掘，数据建模后采用二进制表示法，将数据项集转换成布尔矩阵，能够在进行频繁项集和关联规则挖掘之前，最大限度的减少扫描数据项集的次数，从而大大降低I/O带来的时间和空间消耗，在后面的分析处理过程中可以避免频繁的扫描数据项集，减少磁盘访问。

根据本发明优选的，所述的一种基于并行化关联规则算法的教育云应用统计方法还包括步骤六：

步骤六、基于关联规则分析教育云应用的访问者的使用喜好，向访问者推荐教育云应用，该过程的步骤如下：

15)从分布式文件系统HDFS读取关联规则文件，作为先验知识；

16)从日志信息数据获取访问者的应用访问序列，将该序列与先验知识进行比较，如果和先验知识匹配，则向访问者推荐对应的应用；

17)对于访问者频繁访问的应用，在教育云平台就近部署，即将所述频繁访问的应用的链接放在访问者界面上相邻的位置。

本发明的有益效果：

本发明的有益效果在于：对原始日志数据基于分布式框架进行预处理，然后对数据进行建模，采用二进制表示法，将数据项集转换成布尔矩阵，能够在进行频繁项集和关联规则挖掘之前，最大限度的减少扫描数据项集的次数，从而大大降低I/O带来的时间和空间消耗，在后面的分析处理过程中可以避免频繁的扫描数据项集。

将数据项集转换成布尔矩阵时，由海量数据生成的矩阵往往是大矩阵，而且是极其稀疏的，因此本发明采用稀疏矩阵的存储方式，只存储非零数值，能够节省存储空间，提高处理效率。

同时，因为矩阵很大，在内存中难以完整放入，如果不完全放入，那么由于在计算过程中需要多次将向量的一部分导入内存，会导致大量的磁盘访问，效率低。本发明采用的方法是根据MapReduce分布式处理大型数据的特点，将扫描数据项集获得的布尔矩阵按行分块，把大矩阵分解成多个小矩阵，分别存成一个小文件存储在分布式文件系统的各个数据节点中，供后面的Map迭代任务使用。

附图说明

图1是一种基于并行化关联规则算法的教育云应用统计方法流程图。

具体实施方式

下面根据说明书附图及实施例对本发明的技术方案做进一步描述，但不限于此。

实施例1、

本发明的技术方案如下：一种基于并行化关联规则算法的教育云应用统计方法，首先获取教育云应用的访问情况，对教育云应用访问情况进行数据建模，将源数据以布尔矩阵的形式存储在分布式文件系统HDFS中；其次基于MapReduce框架对关联规则算法进行并行化优化，分别编写Map函数和Reduce函数，对存储在分布式文件系统HDFS中的源数据进行挖掘分析，然后得到访问者对教育云应用的访问情况，具体步骤如下：

步骤一、从教育云服务器获取日志信息数据并定时上传到集群节点的分布式文件系统HDFS中；

步骤二、以存储在HDFS中的日志信息数据作为源数据，进行数据库数据建模；

步骤三、源数据经过建模之后，以数据项集文件的形式存储在HDFS中，每一行代表一个访问者的点击流序列；在进行频繁项集和关联规则挖掘之前，采用二进制表示法，将数据项集转换成布尔矩阵，布尔矩阵存储在分布式文件系统HDFS中；

步骤四、关联规则挖掘：基于MapReduce对传统的挖掘方法进行并行化优化，具体步骤为：

10)扫描存储在分布式文件系统HDFS中的布尔矩阵，生成频繁项集；

11)生成关联规则：由频繁项集生成关联规则；

步骤五、根据步骤四的步骤10)生成的频繁项集，以图形化形式向访问者展示教育云应用的使用情况。

实施例2、

如实施例1所述的一种基于并行化关联规则算法的教育云应用统计方法，其区别在于，步骤一的具体步骤如下：

从教育云服务器获取日志信息并定时上传，教育云服务器日志记录了访问者访问教育云应用的情况。首先编写shell脚本，通过cp命令复制日志信息数据到备份目录，然后使用tar命令对日志信息数据进行打包。通过修改crontab，制定计划任务，实现服务日志的定期打包备份。待分析的数据需要存储到分布式文件系统HDFS中，以便在分布式集群节点中进行分析，在crontab中添加计划任务，通过scp命令将每周的打包日志上传到集群节点的分布式文件系统HDFS中。

实施例3、

如实施例1所述的一种基于并行化关联规则算法的教育云应用统计方法，其区别在于，步骤二的数据库数据建模具体步骤如下：

1)建立教育云应用和访问者访问路径的对应关系。建立如表1所示的应用名称与访问路径映射表，对应关系为：{(01,高中教学,/union/senior/index.html),(02,初 中教学,/union/junior/index.html),(03,小学教育,/union/primary/index.html),(04,儿童教育,/union/child/index.html),(05,网络磁盘,/union/disk/index.html),(06,在线影音,/union/media/index.html),(07,在线编辑,/union/edit/index.html),(08,在线考试,/union/test/index.html)}。

表1 应用名称与访问路径映射表

ID应用名称访问路径01高中教学/union/senior/index.html02初中教学/union/junior/index.html03小学教育/union/primary/index.html04儿童教育/union/child/index.html05网络磁盘/union/disk/index.html06在线影音/union/media/index.html07在线编辑/union/edit/index.html08在线考试/union/test/index.html

2)以存储在HDFS中的日志信息数据作为源数据，日志信息数据逐行存储，每一行记录了访问者访问教育云平台的信息，每一行的格式为<remotehost,ident,authuser,date,request,status,bytes,referrer,agent>，其中remotehost为访问主机地址或者已解析的域名，ident为标示符，authuser为授权访问者，用于记录访问者进行身份验证时提供名字，date为日期时间，request为请求资源的URL，包括请求类型、请求资源、协议版本号，status为状态码，表示服务器的响应状态，bytes为传输的字节数，referrer为来源页面的URL，表示浏览者在访问该页面之前所浏览的页面，agent为访问者的详细信息。编写shell脚本，使用awk命令分割每一行，获取每行的<remotehost,date,request,referrer>四个字段，再存入分布式文件系统HDFS中。

3)基于分割所获取的字段生成访问序列。基于字段date获取同一时间段的记录<remotehost,request,referrer>，其中request和referrer字段根据表1所示的应用名称与访问路径映射表映射为相应的ID，然后基于字段remotehost进行排序，同一remotehost视为同一访问者。

4)针对每个访问者的访问序列生成数据项集：每行的访问序列的格式为<referrer,request>，其中referrer为来源页面的URL，request为请求资源的URL。基于MapReduce进行单表连接。

实施例4、

如实施例3所述的一种基于并行化关联规则算法的教育云应用统计方法，其区别在于，

步骤二的步骤4)的具体方法如下：

a)输入访问序列，假设序列为<<01,03>,<03,06>,<06,02>,<02,04>,<04,07>,<07,08>>，如表2所示。

表2 序列表

referrerrequest010303060602020404070708

b)在map阶段，将读入数据分割成referrer和request后，将request设置成key，referrer设置成value进行输出，并作为输出左表。为了区分左表，在输出value的开始处加上字符“L”，表示左表。这样输出左表的数据格式为<request,<”L”,referrer,request>>，步骤二的步骤4)的步骤a)中的序列输出左表为((03,(“L”,01,03)),(06,(“L”,03,06)),(02,(“L”,06,02)),(04,(“L”,02,04)),(07,(“L”,04,07)),(08,(“L”,07,08)))，如表3所示。

数据以列存储的形式，存储在HBase中。在HBase中，Key‐Value存储以KeyValue类进行表示，Key‐Value包括四部分：Key、TimeStamp、Type和Value四部分。

表3 输出左表

keyvalue03(“L”,01,03)06(“L”,03,06)02(“L”,06,02)04(“L”,02,04)07(“L”,04,07)08(“L”,07,08)

c)在map阶段，将读入数据分割成referrer和request后，将referrer设置成key，request设置成value进行输出，并作为输出右表。为了区分右表，在输出value的开始处加上字符“R”，表示右表。这样输出右表的输出数据格式为<referrer,<”R”,referrer,request>>,数据以列存储的形式存储在HBase中。步骤二的步骤4)的步骤a)中的序列输出右表为((01,(“R”,01,03)),(03,(“R”,03,06)),(06,(“R”,06,02)),(02,(“R”,02,04)),(04,(“R”,04,07)),(07,(“R”,07,08)))。如表4所示。

表4 输出右表

keyvalue01(“R”,01,03)03(“R”,03,06)06(“R”,06,02)02(“R”,02,04)04(“R”,04,07)07(“R”,07,08)

d)在shuffle阶段完成排序和连接。首先把输出左表和输出右表根据key值进行排序，排序后再把输出左表和输出右表中key值相同的项进行连接，放在一起，生成value‐list。步骤二的步骤4)中的步骤b)和步骤c)，通过shuffle后的输出为((01,(“R”,01,03)),(02,(“L”,06,02),(“R”,02,04)),(03,(“L”,01,03),(“R”,03,06)),(04,(“L”,02,04),(“R”,04,07)),(06,(“L”,03,06),(“R”,06,02)),(07,(“L”,04,07),(“R”,07,08)),(08,(“L”,07,08)))。如表5所示。

表5 shuffle阶段输出表

e)在reduce阶段，会接收到shuffle连接的结果，取出每个key的value‐list进行解析，对输出左表和输出右表的value计算笛卡尔积，就可以求出部分页面跳转序列。步骤二的步骤4)的步骤d)通过reduce后的输出为((01,(01,03)),(02,(06,02,04)),(03,(01,03,06)),(04,(02,04,07)),(06,(03,06,02)),(07,(04,07,08)),(08,(07,08)))。如表6所示。

表6 reduce阶段输出表

keyvalue01(01,03)02(06,02,04)03(01,03,06)04(02,04,07)06(03,06,02)07(04,07,08)08(07,08)

f)循环迭代map和reduce过程，对步骤二的步骤4)的步骤e)中输出的结果继续进行连接，得到完整的跳转序列(01,(01,03,06,02,04,07,08))。此时，完整的页面跳转序列中的key代表入口应用对应的ID，value为对应ID的完整的页面跳转序列。如表7所示。

表7 步骤f)循环迭代map和reduce过程后输出表

Keyvalue01(01,03,06,02,04,07,08)

g)根据日志信息数据，对不同的访问者，即对不同remotehost执行步骤二中步骤4)中的步骤a)到步骤f)，得到指定时间段内所有访问者的访问序列，形成数据项集。所述数据项集的数据格式如下：

01，03，06，02，04，07，08

02，03，06，09，04，10，08，06

02，04，07，08

04，03，09，02，07

06，08，04，03，01，02，09

01，03，05，07，09，06，04

02，04，06，03，05，09，08

04，03，02，06，08，05，08

02，031，05，07，09，03，02。

实施例5、

如实施例1所述的一种基于并行化关联规则算法的教育云应用统计方法，其区别在于，步骤三中，源数据经过建模之后，以数据项集文件的形式存储在HDFS中，每一行代表一个访问者的点击流序列。比如(01,03,06,02,04,07,08)，表示访问者依次点击了01,03,06,02,04,07,08，也即该访问者依次访问了应用高中教学、小学教育、在线影音、初中教学、儿童教育、在线编辑和在线考试。在进行频繁项集和关联规则挖掘之前，为了减少扫描数据项集的次数，降低I/O带来的时间和空间消耗，采用二进制表示法，将数据项集转换成布尔矩阵。具体步骤如下：

5)扫描一次数据项集，将数据项集中的每个项目都看作是一个属性，计算数据项集中出现的项目的个数。所述的项目为所有访问者访问过的应用对应的ID；

6)如果一个事务包含某个项目，即该访问者访问了这个应用，那么相应的那个属性值就是1，否则就是0。设数据项集为T＝{t₁,t₂,……,t_n}，项目集为I＝{i₁,i₂,……i_m}，对于数据项集中的每一项D，有f：D‐>r_ij，f(D)＝r_ij。r_ij定义为：

$r_{\mathrm{ij}}=\left(\begin{array}{cc}1,& i_j\in t_k\\ 0,& i_j\notin t_k\end{array}\right)$

7)构造数据项集对应的布尔矩阵，包括m个数据项集记录和n个项目，即m行n列，这里可以通过一次扫描获得下面的布尔矩阵：

$\left(\begin{array}{ccccc}\mathrm{TID}& I_1& I_2& ...& I_n\\ T1& r_{11}& r_{12}& ...& r_{1n}\\ T2& r_{21}& r_{22}& ...& r_{2n}\\ .& .& .& & .\\ .& .& .& & .\\ .& .& .& & .\\ \mathrm{Tm}& r_{m1}& r_{m2}& ...& r_{\mathrm{mn}}\end{array}\right)$

r_ij取1，表示第i个数据项集记录包含第j个项目，r_ij取0，表示第i个数据项集记录不包含第j个项目；

8)通过步骤三的步骤7)由海量数据生成的矩阵往往是大矩阵，而且是极其稀疏的，因此本发明采用稀疏矩阵的存储方式，在布尔矩阵文件中只存储那些非零数值。具体的，在存储的时候采用三元组记录矩阵中的每一个元素，存储矩阵的文件每一条记录的结构如下：

(i,j,A[i,j])

其中，第一个字段i为行标签，第二个字段j为列标签，第三个字段A[i,j]表示该元素的值，值为0的元素在存储矩阵的文件中不存储；

9)生成的布尔矩阵存储在分布式文件系统HDFS中。在后面的分析处理过程中可以避免频繁的扫描数据项集。

实施例6、

如实施例1所述的一种基于并行化关联规则算法的教育云应用统计方法，其区别在于，步骤四中，步骤10)生成频繁项集的具体步骤如下：

关联规则的定义如下：两个不相交的非空集合X、Y，如果有X‐‐>Y，就说X‐‐>Y是一条关联规则。频繁项集是指频繁出现的数据项记录，支持度的定义为：集合X与集合Y中的项在一条记录中同时出现的次数/数据记录的个数。

$\mathrm{support}=\frac{(X\cup Y).\mathrm{count}}{n}$

置信度的定义为：集合X与集合Y中的项在一条记录中同时出现的次数/集合X

$\mathrm{confidence}=\frac{(X\cup Y).\mathrm{count}}{X.\mathrm{count}}$

出现的个数。

定义最小值支持度min_support和最小置信度min_confidence，关联规则挖掘定义为：给定一个数据项集T，找出其中所有支持度support>＝min_support，置信度confidenct>＝min_confidence的关联规则。基于MapReduce对传统的挖掘方法进行并行化优化，步骤四中，步骤10)生成频繁项集的具体步骤如下：

h)扫描存储在分布式文件系统HDFS中的布尔矩阵，因为矩阵很大，在内存中难以完整放下，如果不完全放入，那么由于在计算过程中需要多次将向量的一部分导入内存，会导致大量的磁盘访问，效率低。本发明采用的方法是根据MapReduce分布式处理大型数据的特点，将扫描数据项集获得的布尔矩阵按行分块，把大矩阵分解成多个小矩阵，分别存成一个小文件存储在分布式文件系统的各个数据节点中，供后面的Map迭代任务使用。此处具体分解成几个小矩阵，与分布式文件系统的数据节点个数有关，假如有10个结点，则可以分解为10个小矩阵，前提是保证每个节点的内存能放下分解后的小矩阵；

i)计算所有只包含一个项目的数据项在数据项集中的支持度，据此得到初始的频繁1‐项集，即F1，(其中的“1‐”表示该集合的基数为1，也就是只含有一个元素。同理“x‐”表示集合含有x个元素)集合。计算过程基于Map和Reduce两个函数进行，具体计算过程如下：

①当数据传递给Map时，Map会将输入的矩阵分块进行分割，输出<key,value>形式的数对，具体的数据结构为<j,<i,j,A[i,j]>>，其中键j为矩阵列，值为三元组<i,j,A[i,j]>，三元组中i为元素所在行号，j为元素所在列号，A[i,j]为对应的元素值，在这里值都为1；

②Map处理的中间结果传递给Reduce时，中间结果已经通过shuffle阶段按照key进行了排序，Reduce阶段主要是将相同的key对应的value值累加。Reduce阶段将输入的key值，也就是矩阵的列作为输出的key值，然后将获得多个value值加起来，作为输出的value值；

③由步骤②得到的<key,value>中的key对应数据项，value代表数据项对应的支持度。将每个key对应的value与最小支持度min_support比较，舍弃小于min_support的项，剩余项合并为频繁1‐项集F1；

j)对频繁1‐项集F1中的任意两项进行合并生成候选2‐项集C2，这个过程通过排列组合完成。

k)根据向下封闭原理(如果一个集合不是频繁项集，则它的所有超集都不是频繁项集)剔除步骤j)得到的候选2‐项集C2中不满足条件的候选项，所述不满足条件的候选项为小于最小支持度的候选项；

l)通过Map计算和Reduce计算，统计候选2‐项集中每个数据项的支持度，与最小支持度min_support进行比较，得到频繁2‐项集，具体的计算过程如下：

④在Map阶段根据候选2‐项集的字符串，在矩阵内对应的2个列向量之间做逻辑与运算，将运算结果各位上的数相加得到候选2‐项集的局部支持度，若为0则直接丢弃，形成第一<key,value>对，所述第一<key,value>对的key表示候选2‐项集的候选项，新的value代表该候选项的局部支持度；

⑤Reduce函数对Map生成的候选2‐项集的局部支持度进行合并，得到候选k‐项集的支持度，输入为第一<key,value>对，将key相同的第一<key,value>对的value进行相加，得到第二<key,value>对，所述第二<key,value>对中的key还是表示候选2‐项集的候选项，value值为候选项的支持度。将每个候选项的支持度与min_support进行比较，得到频繁2‐项集；

m)依次类推，逐级搜索，第(k‐1)轮搜索生成的频繁项集F_k-1作为种子集合产生候选项集C_k，产生的候选项集C_k再根据向下封闭原理进行剪枝，所述剪枝是指，消除那些不满足向下封闭原理的项集。

n)将步骤四的步骤10)中，步骤h)至步骤m)生成的频繁项集写入文件并存储在分布式文件系统HDFS中。

实施例7、

如实施例1所述的一种基于并行化关联规则算法的教育云应用统计方法，其区别在于，步骤四中，步骤11)生成关联规则，由频繁项集生成关联规则的步骤如下：

o)从分布式文件系统HDFS中逐行读取频繁项集，文件中的频繁项集逐行存储，因此读取方式是逐行读取；

p)对于每个频繁项集F，产生F的所有非空子集，进而生成规则，该过程通过排列组合进行计算，假如有频繁项集(01,05,08)，则可能产生的规则有01→(05,08)，05→(01,08)，08→(01,05)，(01,05)→08，(01,05)→08，(01,05)→08。

q)根据置信度的计算方法，计算每个规则的置信度，然后和最小置信度min_confidence进行比较，将小于最小置信度的规则删除，剩下的即关联规则；

r)将步骤四的步骤11)的步骤q)生成的关联规则写入文件并存储在分布式文件系统HDFS中。

实施例8、

如实施例1所述的一种基于并行化关联规则算法的教育云应用统计方法，其区别在于，步骤五：根据频繁项集，以图形化形式向访问者展示教育云应用的使用情况；该过程具体步骤如下：

12)从分布式文件系统HDFS中读取频繁项集文件；

13)筛选出频繁1‐项集，即只有一个元素的集合，该集合key的编号即步骤一中表1应用名称与访问路径映射表中教育云应用对应的ID，对应的value值就是该应 用的使用次数；

14)调用jfreechart类库编写java程序，把步骤13)中的使用次数数据以柱状图和折线图的形式呈现给访问者。

实施例9、

如实施例1所述的一种基于并行化关联规则算法的教育云应用统计方法，其区别在于，还包括步骤六：

步骤六、基于关联规则分析教育云访问者的使用喜好，向访问者推荐访问者可能感兴趣的教育云应用。该过程的步骤如下：

15)从分布式文件系统HDFS读取关联规则文件，作为先验知识。

16)从日志信息数据获取访问者的应用访问序列，将该序列与先验知识进行比较，如果和先验知识匹配，则向访问者推荐对应的应用。

17)对于访问者频繁访问的应用，为方便访问者使用和访问，在教育云平台就近部署，即将所述频繁访问的应用的链接放在访问者界面上相邻的位置。