一种动态数据环境下的数据流概念漂移可视化方法

摘要

本发明涉及智能信息处理技术领域，公开了一种动态数据环境下的数据流概念漂移可视化方法，包括：对数据流进行静态化处理，针对不同的概念漂移模式建立不同概念表达方式并保存到概念池中，当新数据块到来时利用KL散度算法，在概念池中寻找相似的概念表达，若存在则对其进行统计，否则将其加入到概念池中作为新的概念进行保存。本发明可以针对各种数据流改变漂移类型进行检测，并且通过统计能够充分分析数据流中概念漂移过程。最后根据统计结果利用贝叶斯方法绘制出概念漂移转移图，将其可视化，为后续在概念层面对数据挖掘提供帮助。

说明书

技术领域

本发明涉及智能信息处理技术领域，特别涉及一种动态环境下的数据流概念漂移可视化法，适用于网络入侵检测，网络安全监控、传感器数据监控和电网供电等方面。 

背景技术

随着信息技术的深入发展，传统数据挖掘方法正面临着新的挑战，首当其冲的就是数据形式的变化，由传统静态数据转变为动态数据流形式，因此如何对数据流进行有效挖掘，提取出内部所包含的知识越来越受到工业界的关注。 

与静态数据不同，数据流本身具有三个特点：海量性、实时性和动态变化性。这三个特点就要求传统数据挖掘模型必须进行调整和改变，以适应数据流的变化和特点，因此目前很多针对数据流模型和方法，都是围绕数据流本身的数据属性进行展开，例如数据流分类模型、聚类模型、降维模型等等。但是对于数据流中所包含的概念层面进行挖掘，目前仍然没有相对应的研究方法和技术。 

目前仅存的数据流概念相关的技术，主要是针对数据流中存在概念漂移现象，进行实时检测或者分类，为后续工作提供支持，而对于概念漂移可视化问题在学术界以及工业界仍然属于空白。尽管概念漂移可视化目前仍然是探索阶段，但由于概念是数据的高级表现形式，因此对于理解数据以及提取数据知识方法具有重要的意义。借鉴其他可视化方法，例如，流形图，圆圈表示法等等方式，在获取概念特征的前提下，对概念漂移进行可视化，可以为后续工作提供一个直观的数据表达方式，这将有利于后续工作的顺利而有效的进行。本领域中存在对提供动态环境数据流概念漂移可视化方法的需要。 

发明内容

本发明的目的是：为解决上述现有技术中存在的问题，以及对于概念漂移可视化方法研究的不足，提供一种动态环境下的数据流概念漂移可视化方法。 

为达到上述目的，本发明采用的技术方案是：提供了一种动态数据环境下的数据流概念漂移可视化方法，具体包括以下步骤： 

步骤1：动态数据流收集模块102从海量实时数据流101中按照时间顺序收集数据；

步骤2：数据流划分模块103读取步骤1中的数据流数据，并根据数据流中数据到达的先后顺序对数据流进行划分；所述数据流划分模块103划分得到的数据块中，包含N条记录；N是固定变量，由使用者提前设定；

步骤3：将使用数据流划分模块103划分后得到静态数据块，输入到kdq树模块104中构建kdq树；其中，所述kdq树对应的阈值使用基于KL散度的自助法计算给出或由使用者直接给定；

步骤4：将kdq树模块104所建立的kdq树、kdq树对应的阈值放入概念池106中保存；

步骤5：概念检测模块105在数据流划分模块103得到一个新的数据块，并检测新数据块是否是新的概念，概念检测模块105的检测结果根据由原始数据块、新数据块的KL散度值与概念池106中保存的kdq树对应阈值的比较结果给出；在计算KL散度时需要对原始数据块进行离散化，离散化的结果由数据块通过kdq树的结果给出；

步骤6：当数据流划分模块103获取新的数据块时，将此数据块与概念池106中所保存的概念进行比较，如果找到相似的概念，则对概念统计模块107进行更新；否则将此数据块作为新的概念加入概念池106中；

步骤7：重复步骤1-6直至数据流结束。此时将概念统计模块107中的统计信息进行汇总，计算出概念池106中每个概念的统计信息；

步骤8：将上述统计信息输入到概念转移图模块108，利用贝叶斯公式构建概念转移图，完成概念漂移可视化过程。

其中，所述步骤3中建立kdq树包括以下子步骤： 

步骤3.1：首先选定数据块中第一个属性作为当前属性，在当前维度中寻找中位数值v，能够对数据块进行划分，使得划分后得到的两个子集中的样本数量基本相等，即当前属性的数值大于v的数据以及当前属性的数值小于或等于v的数据的数量基本相等；

步骤3.2：在上述所得到的子集中，在后继属性中寻找能够满足划分条件的属性，并选择此属性作为当前属性，重复寻找中位数值的过程，继续划分数据子集；

步骤3.3：重复以上过程，直到满足终止条件为止；

所述划分条件为：当前维度数据的最大值与小值之差大于变量ε，且ε值由用户指定；

所述终止条件为：当前数据块的数据规模小于n_min，或者每一维度的最大最小值之差均小于ε，其中于n_min值由用户提前指定。

其中，所述步骤4中，kdq树模块104采用自助法给定kdq树对应的相关阈值，包括以下步骤： 

步骤4.1：从原始数据块中有放回的抽取N条数据，即所抽取的数据并不从原始数据块中删除，利用抽取的数据构成新的数据块；

步骤4.2：利用kdq树对新数据块进行划分得到离散化结果；

步骤4.3：根据所述KL散度的计算公式计算新数据块与原始数据块的KL散度值，将计算结果加入队列中；

所述KL散度的计算公式为：

                          (1)

                            (2)

在公式(1)中， kl₁表示数据块C_a和数据块C_b之间数据分布的KL散度，Pc_a(x)表示数据块C_a离散化后的概率分布，Pc_b(x)表示数据块C_b离散化后的概率分布；w_b,j表示数据块C_b离散化后在第j个区间的数据规模，w_a,j表示数据块C_a离散化后在第j个区间的数据规模，N_b表示数据块C_b的总数据规模；T表示对数据块离散化后共能得到T个区间；所述数据块的离散化结果由kdq树得到；

在公式(2)中，kl₂表示数据块C_a和数据块C_b之间带标签的数据分布的KL散度，Pc_a(Y|x)表示数据块C_a离散化后的每种标签的概率分布，Pc_b(Y|x)表示数据块C_b离散化后的标签的概率分布；w_b,i,j表示数据块C_b离散化后在第j个区间中标签为i的数据规模，w_a,i,j表示数据块C_a离散化后在第j个区间中标签为i的数据规模，N_b表示数据块C_b的总数据规模；T表示对数据块离散化后共能得到T个区间，|Y|表示数据共有|Y|种不同的标签；所述数据块的离散化结果由kdq树得到；

步骤4.4：重复步骤4.1至步骤4.3，共重复k次；其中，k值是用户提前设定的常数；

步骤4.5：对队列中的数据值按照大小进行排序，取第1-α 大的值作为阈值。

其中，所述α表示发生概念漂移的置信度，其中α大于0小于1，由使用者提前指定。 

其中，所述步骤4.2利用kdq树对新数据块进行划分得到离散化结果，包括以下步骤： 

步骤4.2.1：将新数据块中数据按照kdq树各个节点的决策值进行划分，若数据指定维度的值小于等于kdq树中节点的决策值则进入根节点的左子树，否则进入根节点的右子树；

步骤4.2.2：重复所述决策过程直到数据块中所有数据都划分到kdq树的叶子节点时停止，至此得到针对此数据块的划分结果；

步骤4.2.3：对于kdq树针对当前数据块的划分结果，计算每个划分区域中的样本数量除以数据块整体样本数量，则得到当前数据块针对kdq树的离散化结果的概率分布及。

其中，所述步骤5中概念检测模块105检测概念漂移，包括以下子步骤： 

步骤5.1：将数据块通过kdq树的结果，得到kdq树对数据块的离散化结果；

步骤5.2：利用KL散度计算公式，计算新数据块kdq树离散结果与概念池模块106中保存的各个概念kdq离散结果的KL散度值。

步骤5.3：将上述KL散度值与kdq树对应的阈值进行比较，若计算得到的KL散度值小于kdq树对应的阈值，则表示概念漂移没有发生，否则表示概念漂移实际发生。 

其中，所述步骤6包括以下子步骤： 

步骤6.1：将新数据块的kdq树离散值分别与概念池模块106中保存的概念，计算KL散度值。

步骤6.2：将所获得的KL散度值进行排序，若最小的KL散度值仍然大于概念检测模块所设定的阈值，则表示概念池模块106中，没有该数据块所对应的概念，即此数据块表示为一种新概念，那么将此数据块的kdq树离散化结果保存于概念池模块106中，作为新的概念出现。若找到满足阈值的概念，则在概念统计模块107中对此概念的相关统计数据进行更新。 

其中，所述步骤8包括以下子步骤： 

步骤8.1：将概念统计模块107中对于保存于概念池模块106中每一个概念统计信息进行汇总；

步骤8.2：利用贝叶斯公式计算不同概念之间相互转移概率；

                  

其中P(C_i) 表示第i个概念出现的概率，P(C_j) 表示第j个概念出现的概率，P(C_j|C_i)表示当第i个概念出现时，发生第j个概念的概率。

步骤8.3：将计算得到每个概念相互转移概率进行统计，输入到数据流概念转移图模块108，绘制出数据流概念漂移图，完成可视化过程。 

其中，所述数据流101包括：网络入侵监测、网络安全监控、传感器数据监控及电网供电各个方面数据。

本发明的有益效果是：本发明利用kdq树以及KL散度检测概念漂移，可以检测不同类型的概念漂移，并将不同类型的概念存储于概念池中；通过将新数据块与概念池中保存的概念进行比较，可以统计数据流中概念出现的次数以及不同概念之间的转移关系；并最终构建出概念转移图，完成数据流概念漂移可视化任务。 

附图说明

图1为本发明一种动态数据环境下的概念漂移可视化方法的流程框图。 

图2为本发明利用数据流划分模块对数据流进行划分的一种具体实施例。 

图3为本发明kdq树模块在建立kdq树过程中的流程图。 

图4为本发明自助法求取kdq树对应的阈值的具体实施流程。 

图5为本发明概念池中概念检测模块对数据块进行概念检测的一种具体实施例。 

图6为本发明一种动态数据环境下的概念漂移转移图。 

附图标识：101-数据流，102-数据流收集模块，103-数据流划分模块，104-kdq树模块，105-概念检测模块，106-概念池模块，107-概念统计模块，108-数据流概念转移图模块。 

具体实施方式

下面结合附图和实施例对本发明进行详细说明。 

参照图1，本发明一种动态数据环境下的数据流分类方法的框架，包括数据流101，数据流收集模块102，数据流划分模块103，kdq树模块104，概念检测模块105，概念池模块106，概念统计模块107，数据流概念转移图模块108；包括以下步骤： 

步骤1：数据流收集模块102从数据流101中按照时间顺序收集数据。数据流101包括对本领域普通技术人员已知的任何类型的数据流，特别包括网络入侵检测数据流，网络安全监控数据流、传感器数据监控数据流和电网供电数据流。数据流通常是实时产生的，因此对数据流数据的计算、存储都将变得很困难。

步骤2：数据流划分模块103从数据流收集模块102中读取数据，并根据提前设定的数据块容量按照时间顺序将数据流依次进行划分。所述数据流划分模块（103）划分得到的数据块中，包含N条记录；N是固定变量，由使用者提前设定。kdq树模块104，概念检测模块105以及概念池模块108所需的当前数据块均由数据流划分模块103的划分结果给出。 

步骤3：将使用数据流划分模（103划分后得到静态数据块，输入到kdq树模块104中构建kdq树；其中，所述kdq树对应的阈值使用基于KL散度的自助法计算给出或由使用者直接给定； 

步骤4：将kdq树模块（104）所建立的kdq树、kdq树对应的阈值放入概念池模块（106）中保存；

步骤5：概念检测模块（105）在数据流划分模块（103）得到一个新的数据块，并检测新数据块是否是新的概念，概念检测模块（105）的检测结果根据由原始数据块、新数据块的KL散度值与概念池模块（106）中保存的kdq树对应阈值的比较结果给出；在计算KL散度时需要对原始数据块进行离散化，离散化的结果由数据块通过kdq树的结果给出；

步骤6：概念检测模块105使用KL散度方法，将新数据块的kdq树表示形式与概念池106中保存的概念进行比较，寻找相似概念。若找到相似概念，则更新概念统计模块107中此概念所对应的相关统计信息，否则表示新数据块为新的概念，则将新数据块所对应的kdq树结构以及kdq阈值保存于概念池中。

步骤7：重复步骤1-6直至数据流101结束，当数据流101被完全处理完毕，则将概念统计模块中的信息进行汇总，按照不同概念进行划分，并计算不同概念之间的转移概率。 

步骤8：将上述信息输入概念漂移转移图模块108，利用贝叶斯公式绘制概念漂移可视图，完成概念漂移可视化过程。 

所述数据流收集模块102、数据流划分模块103、kdq树模块104，概念检测模105块，概念池模块106，概念统计模块107，数据流概念转移图模块108均存储于计算机系统的存储器中。 

参照图2，为图1利用数据流划分模块103对数据流进行分块的一种具体实施，数据流划分模块103按照数据流收集模块102中数据流到来的先后顺序对数据流进行了分块，按顺序分为第一数据块、第二数据块、…第m数据块，每个数据块包含N条数据，且N值可以根据数据流的特征由数据流划分模块103进行动态调整。 

图3为步骤3中kdq树模块104构建kdq树的过程，如下所述： 

步骤3.1：选定数据块中的第一个维度作为当前维度，在当前维度中寻找中位数值v，中位数值的寻找，要求将数据块中样本按照数量划分为等规模的两个子集，当前维度的数值大于v的数据以及当前维度的数值大于、小于或者等于v的数据数量基本相等；

步骤3.2：在上述所得到的子集的后继维度中寻找满足划分条件的属性，并且使用满足条件的维度作为当前维度，重复寻找中位数值的过程，继续划分数据子集，

步骤3.3：重复步骤3.1和步骤3.2，直到满足终止条件为止；

当前维度满足划分条件为：当前维度数据的最大值小值之差大于ε，ε值由用户指定；

所述终止条件为：当前数据块的数据规模小于n_min，或者每一维度的最大最小值之差均小于ε。当满足停止条件时，得到对原始数据块的一种划分。

若将每次划分的结果作为当前属性值节点的左右决策结果，则可以得到对数据划分的一种树形结构，即kdq树。kdq树的特点是可以对原始数据块的划分结果（离散化结果）近似均等。当数据流环境比较稳定时、即没有发生概念漂移时、对当前数据块也可以获取近似相等的离散化结果。 

参照图4，在步骤4中，kdq树模块104采用自助法给定kdq树对应的相关阈值，包括以下步骤： 

步骤4.1：从原始数据块中有放回的抽取N条数据，即所抽取的数据并不从原始数据块中删除，每次抽取的过程是完全随机的，并且抽取样本之间是相互独立的。利用抽取的数据构成新的数据块；

步骤4.2：重复所述抽取过程直到新数据块中的数据规模达到m，且总共得到k个新数据块，利用kdq树对新数据块进行划分得到离散化结果； 

步骤4.3：根据所述KL散度的计算公式计算新数据块与原始数据块的KL散度值，将计算结果加入队列中进行排序；

在具体实施例中使用KL散度进行数据块之间相似度的判断，所述KL散度的计算公式为：

        (1)

        (2)

在公式(1)中， kl₁表示数据块C_a和数据块C_b之间数据分布的KL散度，Pc_a(x)表示数据块C_a离散化后的概率分布，Pc_b(x)表示数据块C_b离散化后的概率分布；w_b,j表示数据块C_b离散化后在第j个区间的数据规模，w_a,j表示数据块C_a离散化后在第j个区间的数据规模，N_b表示数据块C_b的总数据规模；T表示对数据块离散化后共能得到T个区间；所述数据块的离散化结果由kdq树得到。

在公式(2)中，kl₂表示数据块C_a和数据块C_b之间带标签的数据分布的KL散度，Pc_a(Y|x)表示数据块C_a离散化后的每种标签的概率分布，Pc_b(Y|x)表示数据块C_b离散化后的标签的概率分布；w_b,i,j表示数据块C_b离散化后在第j个区间中标签为i的数据规模，w_a,i,j表示数据块C_a离散化后在第j个区间中标签为i的数据规模，N_b表示数据块C_b的总数据规模；T表示对数据块离散化后共能得到T个区间，|Y|表示数据共有|Y|种不同的标签；所述数据块的离散化结果由kdq树得到； 

步骤4.4：重复步骤4.1至步骤4.3，共重复k次；其中，k值是用户提前设定的常数。

步骤4.5：对队列中的数据值按照大小进行排序，取第1-α 大的值作为阈值，（α表示发生概念漂移的置信度，其中α大于0小于1，由使用者提前指定。）得到置信度为α的kdq树所对应的阈值，即表示，若此时有一个新数据块与原始数据块的KL散度值大于所述阈值，则表示所述新数据块有1-α的概率发生了概念漂移。 

当新的数据块到来时，利用概念检测模块105对新的数据块进行概念漂移检测，检测的过程如下所述：将当前数据块通过当前kdq树得到当前数据块针对当前kdq树的离散化结果，利用KL散度计算公式得到当前数据块与原始数据块的KL散度值并与kdq树对应的阈值进行比较，若计算得到的KL散度值小于kdq树对应的阈值则表示概念漂移没有发生，否则表示新的概念产生了。 

在步骤4.2中，利用kdq树对新数据块进行划分得到离散化结果，包括以下步骤： 

步骤4.2.1：将新数据块中数据按照kdq树各个节点的决策值进行划分，若数据指定维度的值小于等于kdq树中节点的决策值则进入根节点的左子树，否则进入根节点的右子树；

步骤4.2.2：重复所述决策过程直到数据块中所有数据都划分到kdq树的叶子节点时停止，至此得到针对此数据块的划分结果；

步骤4.2.3：对于kdq树针对当前数据块的划分结果，计算每个划分区域中的样本数量除以数据块整体样本数量，则得到当前数据块针对kdq树的离散化结果的概率分布及。

参照图5，所述概念漂移检测整体过程应用举例。首先将数据流101使用数据划分模块103进行划分，得到了不同数据块例如A，B等，此时我们不知道数据块所代表的概念。将此数据块输入kdq树模块104中进行划分，然后将划分后的数据块与概念池模块106中保存的概念进行比较。比较的过程中，使用KL散度方法，并且是由自助法选取相似性阈值。且每一个新数据块与概念池模块106保存的数据块分别进行比较，最终判断该新数据块是否为新概念。 

图5将表示A概念的数据块与概念池106中概念进行比较。发现概念池中已经有A概念了，则更新概念统计模块107中关于A概念的相关统计信息。若没有找到相似概念，例如数据块包含概念E，但是概念池106中并没有相关概念，则将概念E加入到概念池106中，并且在概念统计模块107中对概念E进行添加，为后续统计做准备。 

对于上述过程进行重复，重复的次数与数据流长度有关，直至数据流整体被处理完毕，或者达到提前设定的结束参数。 

参照图6，为本发明利概念转移图模块108最终输出的概念转移可视化图举例。其中圆圈表示不同的概念，并且使用C1，C2等标识。每个概念之间的边表示不同概念转移之间的关系，且边上的权值表示任意两种概念之间的转移概率。概念转移包含两种方式，自转移和外转移，其中自转移表示相邻数据块之间是同一种概念，即概念没有变化，是自己转向自己的形式。而外转移则表示，发生新的概念，因此由旧概念向新概念转移。在实例中，我们使用5000样本作为可视化条件，因此每5000条样本输出一次概念转移可视化图。在每个子图中双圆圈表示当前概念，也就是截止时候最近的概念。 

以上是本发明的优选实施方式，本发明的保护范围并不仅局限于上述实施例，凡属于本发明思路下的技术方案均属于本发明的保护范围。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明的前提下的若干改进和润饰，应当视为本发明的保护范围。