数据空间中异质异构相关数据集合挖掘方法

摘要

本发明提供一种数据空间中异质异构相关数据集合挖掘方法，首先，根据用户活动日志文件，计算出两个活动对象之间的相关值，并将活动对象之间相关值大于第一阈值的活动对象关系保存在活动相关性分析文件中；根据活动相关性分析文件中的对象关系构造数据关联图G；根据数据关联图构造隐对象图GS；当隐对象所代表的数据对象集的相关值满足限定的条件时，根据所述隐对象图GS构造一个新的隐对象图Gs'；输出新隐对象图Gs'中的每一个隐对象所代表的数据对象集合。本发明可以发现异质异构数据的关联，挖掘出异质异构相关数据对象集合。

说明书

技术领域

本发明涉及一种数据空间中异质异构相关数据集合挖掘方法。

背景技术

数据空间是与主体相关的数据及其关系的集合,关联数据查询是数据 空间重要的查询技术，而数据空间中的数据可能来自多个不同的数据源，其 格式可能多种多样，因此，挖掘数据空间中异质异构相关数据集合是实现关 联数据查询的重要基础。

目前对数据空间的研究主要在个人数据空间（PSD），国外主要有Dittrich 等人研发的iMeMex[3-5]和Xin Dong等人研发的SEMEX原型系统，国内主 要有孟小峰等人研发的OrientSpace的个人数据空间。其中，Dittrich等用一 个单一逻辑图模型iDM表示内部的无结构数据，半结构化数据和结构化数 据，通过iMeMex的AJAX接口为用户提供导航，查询和搜索功能。提出用 pay-as-you-go的信息集成思想，在搜索引擎中加入权重hint来丰富松散的 数据源间的关联，定义了iTrails的查询模型和查询策略，iTrails可执行简单 的关键词查询和语义查询。Xin Dong等提出了逻辑三元组Triples(object, attribute,value)来表示异构数据和不同对象之间的关联关系，并为数据空间 中的异构数据建立一个基于图模型的全局数据视图，以管理多源异构数据； 在查询方向，SEMEX不仅考虑了上下文语义信息等数据集成机制，还提出 了利用用户反馈来进化数据集成匹配和查询结果。孟小峰等根据用户的习惯 来组织数据，提出一种活动静态模型TaskSpace，用于描述活动的组成要素； 同时根据在用户数据集合中，只有一部分核心任务的数据项被经常使用，引 入了核心数据空间模型CoreSpace(只包括与用户紧密联系的相关任务及所 涉及的数据项)。该原型系统主要特点是引入了任务空间和核心空间，提供 了基于任务的查询、XML关键词查询及基于串匹配的近似搜索。寇月等提 出一种基于语义的数据空间资源搜索策略，将数据资源搜索过程分为：查询 预处理，资源对象关联评估和语义关联评估，实现不同级别的语义查询，现 有的语义分析，或图像分析等方法只能发现同一类型数据对象的关联，不能 发现异质异构数据的关联，所以不能挖掘出异质异相关数据对象集合。

发明内容

本发明要解决的技术问题，在于提供一种数据空间中异质异构相关数据 集合挖掘方法，可以发现异质异构数据的关联，挖掘出异质异构相关数据对 象集合。

本发明是这样实现的：一种数据空间中异质异构相关数据集合挖掘方 法，包括如下步骤：

步骤10、根据用户活动日志文件，分别计算两个活动窗口的相关度， 再根据相关度计算出两个活动对象之间的相关值，并将活动对象之间相关值 大于第一阈值的活动对象关系保存在活动相关性分析文件中，所述一个活动 窗口包括一个活动对象；

步骤20、根据活动相关性分析文件中的对象关系构造数据关联图G；

步骤30、根据数据关联图构造隐对象图G^S；

步骤40、当隐对象所代表的数据对象集的相关值满足限定的条件时， 根据所述隐对象图G^S构造一个新的隐对象图G^s'；

步骤50、输出新隐对象图G^s'中的隐对象所代表的相关数据对象集合。

进一步地，所述步骤10中相关度包括：活动窗口的标题语义相关度、 内容交互相关度、窗口切换相关度及活动时间相关度，所述活动对象关系为 两个活动对象及其相关值。

进一步地，所述步骤20进一步具体为：

步骤21、对于结构化和半结构化数据对象，根据其内部结构建立连接 相应节点的边，并赋予权重；

步骤22、依次读取活动相关性分析文件中所保存的对象关系，建立连 接相应节点的边，并将该对象之间的相关值作为边权重。

进一步地，所述步骤30进一步具体为：

步骤31、创建隐对象：以数据对象为节点，对于数据关联图G的每一 个节点v_p，在与其相关值大于第二阈值并且不属于其他隐对象的节点中找出 相关值最大的节点v_q，创建一个隐对象表示{v_p,v_q}；

步骤32、建立连接隐对象的边：对于G^S中任意两个不同的隐对象s_i和 s_j，根据它们所代表的数据对象之间的相关度，计算隐对象s_i和s_j之间的相 关值，若s_i和s_j之间的相关值大于0，则建立连接节点s_i和s_j的边；否则不 建立。

进一步地，所述步骤40进一步具体为：

步骤41、创建G^s'的隐对象：对于隐对象图G^S中的每一个隐对象s_p， 在与其相关值大于第三阈值并且不属于G^s'的隐对象的其他隐对象中找出相 关值最大的隐对象s_q，在G^s'中创建一个隐对象代表s_p和s_p所代表的所有数 据对象。

步骤42、建立连接G^s'的隐对象的边：对于G^S'中任意两个不同的隐对 象s'_i和s'_j，根据它们所代表的数据对象之间的相关度，计算隐对象s'_i和s'_j之间的相关值，若s'_i和s'_j之间的相关值大于0，则建立连接节点s_i和s_j的 边，否则不建立。

进一步地，所述隐对象为数据对象集，即相关的异质异构数据集合。

进一步地，所述相关数据对象集合为相关的异质异构数据集合。

本发明具有如下优点：通过捕获用户活动信息，发现不同数据对象的关 联，包括异质异构数据的关联，然后利用所发现的关联，挖掘出异质异相关 数据对象集合。

具体实施方式

一种数据空间中异质异构相关数据集合挖掘方法，包括如下步骤：

步骤10、根据用户活动日志文件，分别计算两个活动窗口的相关度， 再根据相关度计算出两个活动对象之间的相关值，并将活动对象之间相关值 大于第一阈值的活动对象关系保存在活动相关性分析文件中，所述一个活动 窗口包括一个活动对象；所述两个活动窗口的相关度包括：活动窗口的标题 语义相关度、内容交互相关度、窗口切换相关度及活动时间相关度，所述活 动对象关系为两个活动对象及其相关值。

步骤20、根据活动相关性分析文件中的对象关系构造数据关联图G； 所述步骤20进一步具体为：

步骤21、对于结构化和半结构化数据对象，根据其内部结构建立连接 相应节点的边，并赋予权重；

步骤22、依次读取活动相关性分析文件中所保存的对象关系，建立连 接相应节点的边，并将该对象之间的相关值作为边权重。

步骤30、根据数据关联图构造隐对象图G^S；所述步骤30进一步具体 为：

步骤31、创建隐对象：以数据对象为节点，对于数据关联图G的每一 个节点v_p，在与其相关值大于第二阈值并且不属于其他隐对象的节点中找出 相关值最大的节点v_q，创建一个隐对象表示{v_p,v_q}；

步骤32、建立连接隐对象的边：对于G^S中任意两个不同的隐对象s_i和 s_j，根据它们所代表的数据对象之间的相关度，计算隐对象s_i和s_j之间的相 关值，若s_i和s_j之间的相关值大于0，则建立连接节点s_i和s_j的边；否则不 建立。

步骤40、当隐对象所代表的数据对象集的相关值满足限定的条件时， 根据所述隐对象图G^S构造一个新的隐对象图G^s'，所述步骤40进一步具体 为：

步骤41、创建G^s'的隐对象：对于隐对象图G^S中的每一个隐对象s_p， 在与其相关值大于第三阈值并且不属于G^s'的隐对象的其他隐对象中找出相 关值最大的隐对象s_q，在G^s'中创建一个隐对象代表s_p和s_p所代表的所有数 据对象。

步骤42、建立连接G^s'的隐对象的边：对于G^S'中任意两个不同的隐对 象s'_i和s'_j，根据它们所代表的数据对象之间的相关度，计算隐对象s'_i和s'_j之间的相关值，若s'_i和s'_j之间的相关值大于0，则建立连接节点s_i和s_j的 边，否则不建立。；

步骤50、输出新隐对象图G^s'中的每一个隐对象所代表的数据对象集合， 所述相关数据对象集合为相关的异质异构数据集合。

所述数据对象包括结构化数据对象、半结构化数据对象及无结构数据对 象。

设有数据空间的数据对象集合V和用户活动日志文件A。其中，每一 个数据对象用一个三元组v(vid,vtype,vvalue)表示，其中vid表示数据对象 的ID，vtype表示数据对象的数据类型，vvalue表示数据对象的描述。对于 结构化的数据对象，vvalue用元组的属性值表示；半结构化数据对象的 vvalue用标签和元素值共同表示，无结构的文本文档则将文档标题作为此数 据对象的vvalue。每一个用户活动日志记录包含活动时间（开始和结束时 间）、活动窗口标题和用户的粘贴复制操作。

首先，根据用户活动日志文件A，分别计算两个活动窗口的标题语义相 关度、内容交互相关度、窗口切换相关度和活动时间相关度，然后综合这四 个相关度，计算出两两活动对象之间的相关值，并将活动对象之间相关值大 于指定阈值的活动对象关系保存在活动相关性分析文件中。

第二步，构造数据关联图G。以数据对象为节点，分两步建立连接节点 的边：

（1）对结构化和半结构化数据，根据其内部结构，如关系数据库中元 组和元组之间的引用关系、XML文档中元素之间的父子关系，建立连接相 应节点的边，并赋予权重。

（2）依次读取活动相关性分析文件中所保存的对象关系，建立连接相 应节点的边，并将该对象之间的相关值作为边权重。

第三步，构造隐对象图G^S。构造过程分为下列两步：

（1）创建隐对象：对于数据关联图G的每一个节点v_p，在与其相关值 大于指定阈值并且不属于其他隐对象的节点中，找出相关值最大的节点v_q， 创建一个隐对象代表{v_p，v_q}。

（2）建立连接隐对象的边：对于G^S中任意两个不同的隐对象s_i和s_j， 根据它们所代表的数据对象之间的相关度，计算隐对象s_i和s_j之间的相关值。 如果s_i和s_j之间的相关值大于0，则建立连接节点s_i和s_j的边。

第四步，当隐对象所代表的数据对象集的相关度满足指定的条件时，用 下列迭代方法，由隐对象图G^S，构造一个新的隐对象图G^s’。

（1）创建G^s’的隐对象：对于隐对象图G^S的每一个隐对象s_p，在与其 相关度大于指定阈值并且不属于G^s’的新隐对象的隐对象中，找出相关度最 大的隐对象s_q，创建一个G^s’的新隐对象代表s_p和s_p所代表的所有数据对象。

（2）建立连接新隐对象的边：对于G^S'中任意两个不同的隐对象s'_i和 s'_j，根据它们所代表的数据对象之间的相关度，计算隐对象s'_i和s'_j之间的 相关度。如果s'_i和s'_j之间的相关值大于0，则建立连接节点s'_i和s'_j的边。

最后，输出相关的数据对象集合：上一步所得到的隐对象图中，每一个 隐对象所代表的数据对象集就是一个相关的异质异构数据集合。取出并输出 每一个隐对象所代表的数据对象集。

本发明为挖掘异质异构相关数据集合提供了一种有效选择解决方案，为 实现数据空间关联数据查询打下基础。

要实现数据空间关联数据查询，必须挖掘异质异构相关数据集合。本发 明利用结构化和半结构化数据内部的关联关系，结合用户活动中蕴涵的潜在 的数据之间的关联关系，来挖掘异质异构相关数据集合。

收集数据空间的用户活动信息：为了捕获用户活动信息，本文开发了一 个用户活动信息收集子系统。该子系统捕获数据空间的用户活动信息，并将 这些信息保存在一个用户活动日志文件中。保存的用户活动信息包括活动的 开始和结束时间、活动所涉及的数据对象（窗口标题内容）和用户对数据对 象的粘贴复制操作。

数据准备：在数据空间中加入下列结构化、半结构化和无结构数据：

结构化数据：Microsoft SQL SERVER自带的关系数据库pubs和 Northwind。

半结构化数据：http://research.cs.wisc.edu/niagara/data.html网站‘XML  data bank’提供的XML文档及一些网页（HTML文档）

无结构数据：文本文档20-Newsgroup data，一些JPEG文件、BMP文 件、Window Media音频文件等多媒体文件。

以上述用户活动日志文件和数据空间中的数据对象集合作为输入，按下 列处理步骤挖掘相关的异质异构数据集合：

可以表示如下：

步骤1:执行算法1，从用户活动日志文件中发现潜在的数据对象之间 的关联关系。

活动相关性分析

输入：用户活动日志文件A

输出：活动相关性分析文件B

对于日志文件任意两个不同的活动对象v_i和v_j，作下列处理：

根据两个对象活动窗口标题内容，计算v_i和v_j的语义相关度sim(v_i，v_j)；

根据两个对象活动窗口粘贴复制动作，计算v_i和v_j的内容交互相关度 intact(v_i，v_j);

根据两个对象活动窗口互相切换的次数，计算v_i和v_j的切换相关度 toggle(v_i，v_j);

根据两个对象活动时间的重叠，计算v_i和v_j的时间相关度time(v_i，v_j);

计算v_i和v_j的相关值：

r(v_i,v_j)=w₁*sim(v_i，v_j)+w₂*intact(v_i，v_j)+w₃*toggle(v_i，v_j)+w₄*time(v_i， v_j)，其中w₁为sim(v_i，v_j)的权重，w₂为intact(v_i，v_j)的权重，w₃为toggle(v_i， v_j)的权重，w₄为time(v_i，v_j)的权重。

如果r(v_i,v_j)大于第一阈值δ，则将活动对象v_i和v_j及其相关值r(v_i,v_j)写 入活动相关性分析文件B;

步骤2：构造一个以数据对象为节点，以数据关系为边，以[0，1]区间 实数为边权重的赋权图。

构造数据关联图

输入：数据空间的数据对象集V，活动相关性分析文件B

输出：数据关联图G

对于数据对象集V中的每一个数据对象v_i，作下列处理：

如果v_i是关系元组，则获取与v_i存在引用关系的数据对象v_j，将e(v_i,v_j) 的权重设置为1，其中e(v_i,v_j)表示节点v_i和节点之间v_j的边;

如果v_i是XML或HTML元素，则获取v_i的父结点v_j，设置e(v_j,v_i)相应 的权重，其中e(v_i,v_j)表示节点v_i和节点之间v_j的边;

对于活动相关性分析文件B的每一个记录，作下列处理：

读取数据对象v_i和v_j的活动相关值r(v_i,v_i)；在e(v_p,v_q)的权重加入r(v_i,v_i) （权重最大取1）;

步骤3：构造隐对象图G^S。

构造隐对象图

输入：数据关联图G

输出：隐对象图G^S

对于G的每一个数据对象v_p，作下列处理：

在与v_p邻接且边权大于指定阈值并且不属于其他隐对象的节点中，取 出边权最大的节点v_q，创建一个隐对象s_i代替{v_p，v_q}。

对于G^s中的每一对隐对象s_i和s_j（i≠j），作下列处理：

根据s_i和s_j所代表的数据对象之间的边权，计算e(s_i,s_j)的权重，其中 e(s_i,s_j)表示节点s_i和节点之间s_j的边;

如果e(s_i,s_j)的权重大于0，则建立连接节点s_i和s_j的边；

步骤4：在隐对象所代表的数据对象集的相关值满足指定的条件的情况 下，用迭代方法由一个隐对象图G^S，构造一个更优的新隐对象图G^s'（新的 隐对象代表更多的相关数据对象）。完成迭代后，新隐对象图的每一个隐对 象代表一个相关数据对象集合。

从隐对象图挖掘相关数据对象集合

输入：隐对象图G^S

输出：相关数据对象集

当隐对象代表的相关数据对象集满足指定条件时，作下列处理：

对于G^s的每一个s_p，作下列处理：

在与s_p相关值大于指定阈值并且不属于G^s’的新隐对象的隐对象中，找 出相关值最大的隐对象s_q，创建G^s’的一个新隐对象来代表s_p和s_p所代表的 所有数据对象；

对于G^s'的每一对隐对象s'_i，和s'_j（i≠j），作下列处理：

根据它们所代表的数据对象之间的相关度，计算隐对象s'_i和s'_j之间的 相关值；

如果s'_i和s'_j之间的相关值大于0，则建立连接s'_i和s'_j的边；

将G^s'存入G^s；

对于G^s的每一个s_p，取出s_p所代表的所有数据对象，作为一个相关数 据对象集输出。

也可以表示如下：

步骤1:执行算法1，从用户活动日志文件中发现潜在的数据对象之间的 关联关系：

算法1：活动相关性分析

输入：用户活动日志文件A

输出：活动相关性分析文件B

1、for(日志文件任意两个不同的活动对象v_i和v_j)

2、{根据两个对象活动窗口标题内容，计算v_i和v_j的语义相关度sim(v_i， v_j)；

3、根据两个对象活动窗口粘贴复制动作，计算v_i和v_j的内容交互相关 度intact(v_i，v_j);

4、根据两个对象活动窗口互相切换的次数，计算v_i和v_j的切换相关度 toggle(v_i，v_j);

5、根据两个对象活动时间的重叠，计算v_i和v_j的时间相关度time(v_i， v_j);

6、计算v_i和v_j的相关值：r(v_i,v_j)=w₁*sim(v_i，v_j)+w₂*intact(v_i， v_j)+w₃*toggle(v_i，v_j)+w₄*time(v_i，v_j)，，其中w₁为sim(v_i，v_j)的权重，w₂为 intact(v_i，v_j)的权重，w₃为toggle(v_i，v_j)的权重，w₄为time(v_i，v_j)的权重

7、if(r(v_i,v_j)>δ){将活动对象v_i和v_j及其相关值r(v_i,v_j)写入活动相关性 分析文件B};

8、}

步骤2:执行算法2，构造一个以数据对象为节点，以数据关系为边， 以[0，1]区间实数为边权重的赋权图。

算法2：构造数据关联图

输入：数据空间的数据对象集V，活动相关性分析文件B

输出：数据关联图G

1、for(每一个数据对象v_i∈V)

2、{if(v_i是关系元组){获取与v_i存在引用关系的数据对象v_j;设e(v_i,v_j) 的权重为1,其中e(v_i,v_j)表示节点v_i和节点之间v_j的边}；

3、if(v_i是XML或HTML元素){获取v_i的父结点v_j;设置e(v_j,v_i)相应 的权重}；

4、}；

5、for(活动相关性分析文件B的每一个记录)

6、{读取数据对象v_i和v_j的活动相关值r(v_i,v_i);在e(v_p,v_q)的权重加入 r(v_i,v_i)（权重最大取1）};

步骤3:执行算法3，构造隐对象图G^S。

算法3：构造隐对象图

输入：数据关联图G

输出：隐对象图G^S

1、for(G的每一个数据对象v_p)

2、{在与v_p邻接且边权大于第二阈值并且不属于其他隐对象的节点中， 取出边权最大的节点v_q，创建一个隐对象s_i代替{v_p，v_q}。

3、for(每一个G^s中的隐对象s_i)

4、for(每一个s_j且i≠j)

5、{根据s_i和s_j所代表的数据对象之间的边权，计算e(s_i,s_j)的权重，其 中e(s_i,s_j)表示节点s_i和节点之间s_j的边;

6、if(e(s_i,s_j)的权重>0){建立连接节点s_i和s_j的边}

7、}

步骤4：执行算法4，在隐对象所代表的数据对象集的相关值满足指定 的条件的情况下，用迭代方法由一个隐对象图G^S，构造一个更优的新隐对 象图G^s'（新的隐对象代表更多的相关数据对象）。完成迭代后，新隐对象图 的每一个隐对象代表一个相关数据对象集合。

算法4：从隐对象图挖掘相关数据对象集合

输入：隐对象图G^S

输出：相关数据对象集

1、While(隐对象代表的相关数据对象集满足指定条件)do

2、{for(G^s的每一个s_p)

3、{在与s_p相关值大于第三阈值并且不属于G^s'的新隐对象的隐对象中， 找出相关值最大的

4、隐对象s_q，创建G^s'的一个新隐对象来代表s_p和s_p所代表的所有数 据对象}；

5、for(G^s'的每一个s'_i)

6、for(G^s'中的每一个s'_j且i≠j)

7、{根据它们所代表的数据对象之间的相关度，计算隐对象s'_i和s'_j之间的相关值；

8、If（s'_i和s'_j之间的相关值>0）{建立连接s'_i和s'_j的边}

9、}

10、G^s=G^s';

11、}

12、for(G^s的每一个s_p){取出s_p所代表的所有数据对象，作为一个相关 数据对象集输出}

对于如上所述的实例数据的挖掘结果，本文通过计算被加入到相关数据 集的数据的正确率进行评估。当迭代次数大于8时，正确率趋于稳定，达到 98.45%。为测试算法的时间性能，本文对不同数量的数据对象集进行测试。 对于包含999个数据对象和11250条关联边的数据集合，算法的执行时间约 3.7秒。当据增加到1779个数据对象和23755条关联边时，算法的执行时间 增加约1秒。还测试了包含2000多个数据对象和3000多个数据对象的数据 集合，算法的执行时间都没有随着数据对象数量的增长而成倍增长。实验结 果表明了本算法的可行性。

本发明具有如下优点：通过捕获用户活动信息，发现不同数据对象的关 联，包括异质异构数据的关联，然后利用所发现的关联，挖掘出异质异相关 数据对象集合。

虽然以上描述了本发明的具体实施方式，但是熟悉本技术领域的技术人 员应当理解，我们所描述的具体的实施例只是说明性的，而不是用于对本发 明的范围的限定，熟悉本领域的技术人员在依照本发明的精神所作的等效的 修饰以及变化，都应当涵盖在本发明的权利要求所保护的范围内。