面向图结构聚类why问题的溯源解释问题

图是描述现实世界各类复杂系统的一种普适模型，具有很强的表述能力。在现实世界中，很多应用将数据和数据之间的关系表示为一个图，比如说社交网络，信息网络，协作网络，电子商务网络，通信网络，生物蛋白质网络等。从数据管理角度出发，对大规模数据进行按需加载，将会节省大量计算资源，图的聚类为上述需求提供了解决途径，有利于大规模图的分析，理解和可视化。

在围绕图结构聚类算法展开研究时，我们发现图结构聚类算法主要存在的两个问题，第一是数据存在质量问题，第二是聚类方法存在参数不合理的问题。

1.图数据质量问题：图数据存在质量问题分为4个小点，第一点是由于图数据源存在缺失信息和错误的现象导致的，如由于人为因素，机器故障或位置确定技术的限制，移动设备用户的位置信息有时不准确或丢失，第二点是图数据抽取存在错误，如网页抽取数据时，大部分抽取方法不但速度慢，容易出错而且难以维护，第三点是图数据在提取时发生重复错误的现象，如在线服务中，一个用户可能有多个账号，造成有多个用户的假象，第四点是图数据的集成错误导致的质量问题，在整合多源数据时，对于同一个事实，不同的数据源有不同的判断，造成了数据冲突和不确定。图结构聚类方法对数据时敏感的，如果数据中存在质量问题，那么聚类结果就不能满足用户的需求

2.聚类参数不合理问题：图结构聚类方法对聚类参数是非常敏感的，由于用户专业知识有限，所提交的聚类参数也许并不能表达用户的真实聚类请求，此时图数据库系统返回的聚类结果就会不同于用户的期望，无法满足用户的需求。在此情况下，用户可能会通过提交多次聚类操作来满足自己的查询请求，或者放弃在该数据集上继续操作。因而会造成数据资源的浪费，降低图数据的可用性，间接造成巨大的经济损失。

在以上问题的出现后，我们提出了why问题。什么是why问题，why问题就是指，第一，为什么非期望数据会出现在查询结果中。第二，如何做才能使得非期望数据不出现在查询结果当中。我们希望图结构聚类系统能够支持这样的溯源解释功能，为图结构聚类结果提供溯源解释能够有效解决因为数据敏感和参数敏感带来的聚类结果令用户不满意的问题。

下面基于不同的查询请求，介绍通过查询精炼解释why-not问题和why问题现在所用的方法。

（1）SQL查询。对于关系数据SPJA(Select-Project-Join-Aggregation)查询的why-not问题，提出了基于查询精炼的解释方法ConQueR，该方法要求修改后查询的查询结果要包含原有的查询结果和期望的why-not数据。Albarrack等人还提出了一个半自动的SQL调试器来解释SQL查询的缺失数据，并提供了一些建议来修复原来的SQL查询使得这些查询能够返回期望的数据，而Freire等人研究解决了链接查询上why问题的解释方法。

为了解释SQL查询的统计结果，他们首先提出了干预的概念，即从数据库中移除对查询结果影响最大的元组。然后提出了基于干预的方法来解释SQL查询中统计信息的why问题和why-not问题。Salimi等人基于因果关系和责任研究了数据库中查询结果的因果关系，基于拒绝约束的数据修复和基于一致性的诊断这三个方面的联系，然后讨论了查询结果的因果关系，诱发性诊断和视图更新问题之间的联系，并定义了存在完整性约束的查询结果因果关系的概念。

(2) Top-k查询。对于数据集来说，top-k查询是一个能够为用户只显示重要数据的有效方式。由于用户对数据集缺乏必要的专业知识，他们提交的top-k查询可能并不能表达他们真正的查询意图，如他们期望的数据没有出现在查询结果中。为了解释这类问题，通过精炼原来的top-k查询解释了top-k查询的why和why-not问题。但是该解决方法只考虑了精炼后查询对原来查询的影响，并没有考虑精炼后查询对原来查询结果的影响。

（3）Skyline查询。过去几十年来，Skyline查询已经获得了数据研究人员极大的关注，而且证明了该类查询对于多标准决策支持非常有价值，为了让用户理解为什么某些有趣的点没有出现在查询结果中，Chester等人提出了sky-not查询，解释了skyline查询的why和why-not问题。在查询数据库时，如果查询结果不能满足用户的需求，用户反馈信息能够帮助发现用户查询的真正意图。基于此，Liu等人提出了一个有效的灵活的交互式查询解释框架FlexIQ

（4）Graph查询。随着图数据库技术的快速发展，图数据库在帮助用户存储和支持复杂的查询的同时，也带来了一些额外的代价即查询可能回导致结果集为空或者结果集很大。为了解决图查询的why和why-not问题，Vasilyeva等人介绍了一种新的图查询类型，成为差异查询，该查询解释了一个查询图中哪一部分是在数据图中显示出来，哪一部分是确实了。接着他们又提出了一个基于子图的方法来解释图查询结果中为什么空和为什么这么多的我我呢提。查询失败即查询结果为空在图数据库的模式匹配查询处理中是一个主要问题。

虽然上述研究成果已经解决了很多种查询请求的溯源解释问题，但仍然不能满足用户的需求，如已有研究成果无法直接用于图结果聚类的溯源解释问题。因此，在基于参数敏感的溯源解释研究中，还需要研究面向参数敏感的图结构聚类溯源解释问题。

我会在以后继续研究why问题，会把学习成果继续写出来，谢谢。

更多相关文章

随机推荐