庄志惠,　岑　健,　刘　娟，　赵　晓，　王艺璇

(1.广东技术师范学院自动化学院,广州 510665； 2.国网南阳供电公司,河南 南阳 473000)

0　引　言

传统的技术对于不确定性数据的处理效率低下，这使得研究人员都致力于设计新的数据管理技术应用到不确定性数据,根据数据特点的区别[1-4]，针对一些结构特性的不确定数据给出了相应的处理模型;依据数据特点的区别，针对一些结构特性的不确定数据给出了相应的处理模型;针对时间快速流动的数据，设计了滑动窗口模型；针对不同语义与应用背景的多种查询方法设计了如：Top-k与Skyline等查询方法[5-9]。近2年来随着研究的不断深入，不确定数据方面的研究水平有了显著改进，而与此同时随着各种模型与查询方法的设计与改进，其处理的效果也有很大的提升[10-12]。然而如数据测量有误，影响到整个传输过程等；相关人员没有准确的处理数据等方面的问题依然需要进一步发展，在相关学术界的研究中发现在不确定数据元组的数目很大时，现有的发展模型基本上不可能得到有效的查询结果[13,5,7]，本文基于这一方向的考虑，进一步改进不确定数据Top-k查询的有效结果，采用控制集合方法完成了不确定数据查询算法的改进及优化验证，这一研究对于大元组不确定的数据管理具有显著的理论和实践价值。

1　控制集合方法实现算法的改进设计

U-Topk、Uk-Ranks、PT-k以及Pk-Topk是当前不确定数据的4种Top-k查询算法，这4种算法的共同点是要将数据元组中最大分值的k个找出，不同的是它们在语义上和处理方式是有区别的，各有各的特点。与最初的处理方法相比，这几种方法的处理效果确实有很大的提升，但是仍有一些地方还需要改进，这里主要针对PT-Tok查询算法进行改进。

1.1　改进算法的数据查询

普通关系的数据查询是对数据进行精确或完全相同的查询处理，而DRA关系的查询则有所不同，它的相关查询是基于数据库存在不确定性，所查询的对象是不确定性数据。精确查询与设计的DRA查询是设计的DRA模型两种的查询操作，精确查询所指的是在设计的DRA关系R=(U,B,V,M)中，设定y为此关系中所要查询的目标，查询结果可分为两种，即典型结果集合M与边界结果集合N：M(y)=Gd([y]),N(y)=Bv([y])；而另一种查询操作则指的是在设计的DRA关系R=(U,B,V,M)中，设定y依然是此关系中所要查询的目标，查询结果一样可分为两种，即典型结果集合M与边界结果集合N：M(y)={Gv([y]):[y]⊆Cy}，N(y)={Nv([y]):[y]⊆Nn(y)}。

1.2　PT-Tok查询中算法实现过程

表1　相互独立的不确定数据元组

这里以上表中的数据进行算法设计的实现过程分析。根据大小对几率值进行排序，从而得出PT-k的结果。

(1)

(2)

(3)

根据上述算法改进设计,表1中的数据便可获得表2的结果。

表2　PT-k查询处理结果

2　实验设计验证

以下是采用上述模型城市的负荷数据天气进行实验应用。

2.1　城市负荷预测应用结果

这里针对20天的城市的负荷数据天气特征值进行低21天的数据预测，图1所示算法数据应用预测结果，图2则相应给出了实际情况的预报误差，实际例证结果表明,算法训练速度快、时间短、收敛效果好。为了进一步详细说明算法设计的有效价值及应用效果，下面通过java进行虚拟实验对比及详细分析。

图1　预测结果

图2　预报误差

2.2　jav数据的算法实验对比

2.2.1实验数据

对java中的random函数进行调用而随机生成的实验数据，其分值范围为0～2 000，概率值范围为0～1。由于在可能世界实例中，分值一样的情况无法对排序进行明确，因此在当前的研究中，两个独立的元组有着一样的分值的情况并不在考虑之列。故这里所研究的情况并未将分值相等考虑其中，实验中所采用的数据表一共有100张，其中有10份数据是元组个数，分别为：100，200，300，400，500，600，700，800，900，1 000；而这10份数据实验结果的平均值即为该实验结果。

2.2.2实验对比结果

图3所示为查询在数据量与k值不同的情况下，所获得的控制集合中元组的数目，由图4可知，随着数据量的增大控制集合的数目也有不太明显的变化(稍增)，因为即便原始数据有所增大因为上文中已经对控制集合以外的元组成为查询结果的可能性为0进行了论证，因此当控制集合较小时，该方法的的优势更为明显。

图3　控制集合的数据量

图4、5所表示的是采用DRA方法，当k保持不变时，查询的结果也会保持不变，数据更新对查询结果无影响的概率则是1—194 860/200 000=2.57%。由图可以看到，控制集合中的元组随着k值的增大而变大，查询结果受影响的概率降低。

图4k不同时更新数据需要重查的概率

图5数据量不同时更新数据需要重查的概率

图6所示为采用现有方法与改进后的方法处理PT-k查询时所需处理的平均元组数。由图6可知，这两种方法的差距随着数据量的变大而变大，造成这种现象的主要原因是使用现有的方法需对所有元组成为PT-k结果的可能性进行计算，接着再将成为PT-k查询结果不小于阈值P的概率值取出，再根据由大到小的顺序对这些概率值进行排序,而相应的元组也就是最后的查询结果，而改进后的方法在阈值P>0.25时控制集合中比阈值p小的元组概率值是无需考虑的，这是由于PT-k查询所要查找的是在全部可能世界实例中排在前k位的概率总和不小于阈值P的元组，而任一元组排在全部可能世界实例中前k位的概率总和不可能大于这一元组的存在性概率值，因此，存在性概率值比阈值P小的元组成为PT-k的查询结果是不存在的，前面已经对仅在查询阈值比0.25大的情况进行了论证，PT-k查询只能用于基于控制集合的方法，故如果阈值超过0.25，控制集合中可能成为PT-k的查询结果仅仅是存在性概率值比0.25大的元组。实验室中分别将0.3、0.5、0.7作为3个阈值，因为所取阈值不一样，所需计算的元组也会有所变化，但比现有方法所处理的元组数要少的多，因此，图中所显示的这3种情况差不多。

图6　数据量不同时对PT-k查询的影响

3　结　语

对于不确定数据，相关研究人员已经提出了许多数据模型。而这些数据模型的共同点就是其核心思想都是基于可能世界模型而产生的。所谓的可能世界实例指的是可能世界模型由一个或一个以上的不确定数据源演化为多个确定的数据库实例，其中全部实例的几率总和为1。虽然可以先对每个实例的查询结果进行分别计算，再将中间结果合并从而得到最终查询结果，但可能世界实例比不确定性数据库的规模要大的多，因此，该方法并不适用。本文对此作了具体说明，将100份数据结果的平均值作为实验结果，同时，对现有方法进行了全面的对比，这样可更加客观的对该方法的改进进行评价。

参考文献(References)：

[1]陈爱东,刘国华,肖瑞,等. 均匀分布下不确定数据的关联规则变粒度查询[J]. 计算机工程与科学,2013(10):79-88.

[2]陈爱东,刘国华,费凡,等. 满足均匀分布的不确定数据关联规则挖掘算法[J]. 计算机研究与发展,2013(S1):186-195.

[3]黄娜,王洪涛,范辞冬,等. 基于不确定度和敏感度分析的LCA数据质量评估与控制方法[J]. 环境科学学报,2012(6):1529-1536.

[4]王意洁,李小勇,祁亚斐,等. 不确定数据查询技术研究[J]. 计算机研究与发展,2012(7):1460-1466.

[5]祁亚斐,王意洁,李小勇. 基于高斯模型的不确定数据流Skyline查询方法[J]. 计算机研究与发展,2012(7):1467-1473.

[6]周逊,李建中,石胜飞. 不确定数据上两种查询的分布式聚集算法[J]. 计算机研究与发展,2010(5):762-771.

[7]王悦,唐常杰,杨宁,等. 在不确定数据集上挖掘优化的概率干预策略[J]. 软件学报,2011(2):285-297.

[8]汪金苗,张龙波,邓齐志,等. 不确定数据频繁项集挖掘方法综述[J]. 计算机工程与应用,2011(20):121-125.

[9]白梅,信俊昌,东韩,等. 不确定数据流上的概率反轮廓查询处理[J]. 计算机研究与发展,2011(10):1842-1849.

[10]孙永佼,袁野,王国仁. P2P环境下面向不确定数据的Top-k查询[J]. 计算机学报,2011(11):2155-2164.

[11]王爽,王国仁. 面向不确定感知数据的频繁项查询算法[J]. 计算机学报,2013(3):571-581.

[12]蒋涛,高云君,张彬,等. 不确定数据查询处理[J]. 电子学报,2013(5):966-976.

[13]卢鑫,陈华辉,董一鸿,等. MapReduce框架下的不确定数据Top-k查询计算[J]. 模式识别与人工智能,2013(7):695-704.