一种基于海量不完备数据集的skyline偏好查询方法

摘要

本发明涉及一种基于海量不完备数据集的skyline偏好查询方法，本方法根据用户偏好按属性重要程度将不完备数据集IS进行投影，对于投影得到的两个数据集IS’和IS”分别进行严格聚类和松散聚类，聚类后分别执行两种不同的skyline偏好查询算法，分别得到基于严格聚类的skyline结果集SSRS和基于松散聚类的skyline结果集RSRS，最后执行一次基于信息熵计算的skyline偏好查询结果选择策略，得到满足用户偏好的skyline查询结果集。有效解决了在海量不完备数据集上提取个性化信息的问题并提高了skyline查询算法在海量不完备数据集上的效率。

说明书

技术领域

本发明涉及一种基于海量不完备数据集的skyline偏好查询方法，属于物联网和大数据处理技术领域。

背景技术

物联网(Internet of things，loT)是新一代信息技术的重要组成部分，也是信息化时的重要发展阶段。目前物联网领域中主要使用传感器和监测设备来获取数据，由于传感器和监测设备故障、误差和存在着的实际数据获取限制，数据理解有误或数据漏读等多种情况，使得数据集的不完备性普遍存在。这种有缺失数据的数据集，称为不完备数据集。随着物联网应用的发展与普及，以满足用户需求为目标的个性化推荐成为物联网数据处理的热点。例如，根据智能手环、智能手表等可穿戴设备中获取的用户信息，不同的厂商可以针对不同的用户推荐其产品。skyline查询作为一种典型的多目标优化问题的处理方法，在决策制定、市场分析、环境监视、数据挖掘、数据库可视化和计量经济学等应用中发挥着重要作用。因此，对物联网海量不完备数据进行skyline偏好查询处理是解决个性化推荐问题新的视角和切入点。以往对不完备数据的skyline查询是先将数据集进行清洗、修复等预处理，然后再进行skyline查询。但预处理消耗系统资源过多，修复后的数据存在一定的误差，导致查询结果不准确。并且对于一些时效性问题，如流感时期的数据，对这些强实效性数据进行预处理可能会导致数据失效。

发明内容

本发明针对现有技术的不足，摒弃了传统方法中的预处理阶段，提出了根据用户偏好将维度按重要程度分成两部分分别进行查询处理的策略：基于海量不完备数据集的skyline偏好查询(skyline preference query)，使得skyline查询在海量不完备数据集上的执行效率有了较大提升，并且得到满足用户偏好的个性化数据。

本发明是通过下述技术方案实现的：

一种基于海量不完备数据集的skyline偏好查询方法，包括以下步骤：

(1)根据数据集中各属性重要程度将不完备数据集IS进行投影，得到重要属性投影后的数据集IS’和不重要属性投影后的数据集IS”(以下简称数据集IS’和数据集IS”)；

(2)针对数据集IS’和数据集IS”分别进行元组编码；

(3)针对数据集IS’进行严格聚类，所述的严格聚类策略(或者方法)包括根据聚类编码的定义进行严格聚类和聚类后每个类中被支配的数据元组被剔除两个流程；

(4)针对数据集IS”进行松散聚类；所述的松散聚类策略(或者方法)包括根据元组编码和每个聚类的编码的包含关系的定义进行松散聚类和聚类后每个类中被支配的数据元组被剔除两个流程；

(5)将步骤(3)中，严格聚类并完成数据剔除的数据集，执行基于属性值排序的skyline偏好查询算法，得到基于严格聚类的skyline查询结果集SSRS(以下简称SSRS)；

(6)将步骤(4)中，松散聚类并完成数据剔除的数据集，执行基于支配程度计算的skyline偏好查询算法，得到基于松散聚类的skyline查询结果集RSRS(以下简称RSRS)；

(7)将步骤(5)、步骤(6)得到的SSRS与RSRS取交集，如果交集不为空集，那么交集中的元组就是最终的skyline查询结果；

(8)如果步骤(7)的交集为空集，分别计算SSRS与RSRS中元组的信息熵，将SSRS和RSRS中的元组进行信息熵的计算后得出最终的skyline查询结果反馈给用户。

所述(2)针对数据集IS’和数据集IS”进行元组编码的过程如下：

p_i′·tuple_code(p_i″·tuple_code)＝M_i，M_i＝(m₁，m，…，m_k)；

若p_i′·v_k(p_i″·v_k)＝*，M_i·m_ik＝0；若p_i′·v_k(p_i″·v_k)≠*，M_i·m_ik＝1，

其中k∈[1，λ]([λ+1，d]).

其中，IS’和IS”分别是IS在前λ维上的投影和后d-λ维上的投影，d是不完备数据集IS的维数，p_i′和p_i″分别是元组p_i前λ维上的投影和后d-λ维上的投影，Mi是元组p_i的编码，λ是维度的分割常数，λ∈[1，d]；

所述步骤(3)严格聚类中的聚类编码过程如下：

对于如果存在cc_j≠p′_i·tuple_code，那么CS′＝CS′∪{p_i′·tuple_code}

其中，CS’是严格聚类编码集合，cc_j是聚类编码。

所述步骤(5)中执行基于属性值排序的skyline偏好查询过程，得到严格聚类结果集SSRS的具体过程如下：

(5.1)：对数据集IS’中的各维度按照元组属性值非降序排序，使得更有可能支配其他元组的元组优先被处理；每维经过排序后都会生成一个数组Di，i∈[1，λ]，对于每个数组Di都有Di[j]＞＝Di[j+1]，j∈[1，|IS′|)，其中|IS′|代表IS’中的元组个数；对于在第i维上存在缺失属性值的元组是不会加入数组Di中的，为了节省存储空间，数组Di中存储的只是元组id，而不是真正的元组；设立一个指向数组Di的指针ptri，经过严格聚类后没有被支配的元组都纳入候选集Candidate_Set；随机选择一个数组Di，处理数组Di中指针ptri指向的元组；每个在候选集中的元组都会维护两个值，一个是元组被处理的次数，记为processedCount，一个是元组编码中1的个数即非缺失属性维数，记为dimCount；

(5.2)：对于当前被选中的元组p，有以下几种情况：

①，如果元组p′没有被处理过且元组p′还在候选集Candidate_Set中，就将它与除自己以外没有跟它比较过的元组p_j′进行比较，即使p_j′已经被之前处理过的元组所支配；若候选集中存在元组支配p′，元组p′就被移出候选集；

②：如果元组p′没有被处理过但是被之前处理过的元组支配，即已不在候选集Candidate_Set中，p′就只与还在候选集Candidate_Set中并且没有与p′比较过的元组比较；在以上两种情况下，候选集中被元组p′支配的元组会被移出候选集；

③：如果元组p′已经被处理过了就不进行任何比较；

④：其中i≠j，p′_i和p′_j可比较的维度少于个，在这些可比较的维度上，若p′_i在至少一维上的值比p′_j“好”，剩余维度上的值不比p′_j“差”就认为p′_i弱支配p′_j，记为p_i′＞*p_j′

如果两个元组p_i′与p_j′之间具有弱支配关系，还需要比较这两个元组的重量；若满足p_i′的重量大于p_j′的重量，才认为p_i′支配p_j′；综合考虑非缺失属性值及其被用户所赋予的权重，元组重量计算公式(1)，如下所示：

(5.3)：当候选集中的元组p的比较次数达到了其非缺失属性维数dimCount，就将这个元组从候选集移到严格skyline结果集SSRS中；

(5.4)：当候选集为空或者所有元组都被处理过至少一次时，把候选集Candidate_Set中的其余元组都放入严格聚类skyline结果集SSRS中，此时基于属性值排序的skyline偏好查询过程结束。

所述步骤(6)中执行支配程度计算skyline偏好查询算法，得到松散聚类结果集RSRS的具体过程如下：

(6.1)：对于每一个元组判断它聚于哪一个类是通过元组编码与聚类编码的匹配来完成的；严格聚类规则是对元组编码和聚类编码执行完全匹配，只有当一个元组的编码与一个聚类的编码完全一致时才认为将这个元组聚于这个类中；松散聚类规则是对元组编码和聚类编码执行不完全匹配，即凡是元组编码与聚类编码符合包含关系就认为该元组可以聚于这个类中；下面是对元组编码与聚类编码之间包含关系的定义：

令d₁＝λ，d₂＝d-λ.p_i″.tuple_code＝M_i″，M_i″＝(m_ik，m_ik+1，…，m_id)，如果并且i≠j，cc_j＝(c_jk，c_jk+1，…，c_jd)，对于m_ik≤c_jk，p_i″被放在聚类编码为cc_j的对应类中，p_i″与cc_j之间的包含关系用p_i″→cc_j表示；如果对于m_ik＞c_jk，那么cc_j→p_i″并且这个聚类的编码将被更新为p_i″·tuple_code，cc_j将被移出CS″；如果p_i″·tuple_code与cc_j之间没有包含关系或者CS″是空集。除p_i″将被放于聚类编码为cc_j这种情况之外，都要更新CS″；

CS″＝CS″∪{p_i″·tuple_code}

其中，CS”是松散聚类编码集合；

当出现一个元组同时满足多个包含关系时，它可以放于多个聚类中，使得具有较大相似程度的元组尽可能充分的进行比较，进而将一些被其他元组支配的元组剔除；

(6.2)：聚类中的部分元组之间可能不具有支配关系，这些无法互相支配的元组都会作为skyline查询结果返回给用户，用户还需要在这些结果中进行筛选，并且有一部分查询结果并不符合用户需求；

出于对该问题的考虑，本发明将用户偏好作为决定支配关系时的一个重要因素。提出了一种支配程度计算方法减少了skyline查询结果集中的冗余数据。与传统skyline查询过程中元组之间的支配关系不同，带有用户偏好的数据据元组之间的支配关系由它们之间的支配程度决定。支配程度的定义如下：

任意两元组之间可以比较的维属性值之差可视作这一维上两元组的支配距离。那么同一聚类中任意两个元组的支配程度可记为可比较维度上支配距离与权重乘积的和。令w_λ+1，w_λ+2，...，w_d为各维权值，元组p_i的各维非缺失属性值记为

v_ij，j∈[λ+1，d]，

那么任意两元组p_i对p_j的支配程度记为：其中k代表元组之间可以比较的维度，如果domain_i，j＞0，then>i＞p_j，如果domain_i，j＜0，p_j＞p_i，如果domain_i，j＝0，p_i与p_j不可相互支配。

根据上文支配程度的定义，在每个聚类中计算任意两个元组的支配程度，将一些被支配的元组剔除后，把每个聚类中的元组放入松散skyline查询结果集RSRS；

所述步骤(8)中信息熵的计算公式如下：

其中，E(p_i)代表元组p_i的信息熵，h′代表元组属性标准化后的值，n代表元组的维数。

本发明的有益效果：

1、摒弃了一般缺失数据skyline查询处理中的预处理阶段，提出了一种基于维度重要程度将数据分为两部分分别直接进行skyline查询的策略，有效解决了海量缺失数据执行skyline查询时间耗费巨大的问题。

2、结合用户偏好，在重要性高的维度上严格聚类，并通过计算具有弱支配关系元组之间的重量得到更准确符合用户个性化需求的skyline查询结果；在重要性低的维度上松散聚类，并在每个聚类中通过计算元组之间的支配距离决定元组之间的支配关系，有效解决了缺失元组之间支配关系难以判断的问题。

3、提出了一种基于信息熵理论的选择策略，根据信息论中的熵的计算公式，信息熵大的缺失元组被信息熵小的缺失元组所支配，合理解决了重要程度高的维度上的skyline查询结果与重要程度低的维度上的skyline查询结果交集为空的问题。

附图说明

图1为基于海量不完备数据集的skyline偏好查询方法执行流程图。

图2为不完备数据集示例。

图3为维度排序结果。

图4为松散聚类结果示例。

具体实施方式

下面结合附图和具体实施方式对本发明进行详细说明。

本发明方法的设计构思如下：根据用户偏好按属性重要程度将不完备数据集IS进行投影，对于投影得到的两个数据集IS’和IS”分别进行严格聚类和松散聚类，聚类后分别执行两种不同的skyline偏好查询算法，分别得到基于严格聚类的skyline结果集SSRS和基于松散聚类的skyline结果集RSRS，最后执行一次基于信息熵计算的skyline偏好查询结果选择策略，得到满足用户偏好的skyline查询结果集。

具体执行流程图如图1所示，包括如下步骤：

(1)根据数据集中各属性重要程度将不完备数据集IS进行投影，得到重要属性投影后的数据集IS’和不重要属性投影后的数据集IS”；

(2)针对数据集IS’和数据集IS”分别进行元组编码；

(3)针对数据集IS’进行严格聚类，所述的严格聚类包括根据聚类编码的定义进行严格聚类和聚类后每个类中被支配的数据元组被剔除两个流程；

(4)针对数据集IS”进行松散聚类；所述的松散聚类包括根据元组编码和每个聚类的编码的包含关系的定义进行松散聚类和聚类后每个类中被支配的数据元组被剔除两个流程；

(5)将步骤(3)中，严格聚类并完成数据剔除的数据集，执行基于属性值排序的skyline偏好查询算法，得到基于严格聚类的skyline查询结果集SSRS；

(6)将步骤(4)中，松散聚类并完成数据剔除的数据集，执行基于支配程度计算的skyline偏好查询算法，得到基于松散聚类的skyline查询结果集RSRS；

(7)将步骤(5)、步骤(6)得到的SSRS与RSRS取交集，如果交集不为空集，那么交集中的元组就是最终的skyline查询结果；

(8)如果步骤(7)的交集为空集，分别计算SSRS与RSRS中元组的信息熵，将SSRS和RSRS中的元组进行信息熵的计算后得出最终的skyline查询结果反馈给用户。

本发明首先提出了一种编码和聚类策略。该策略基于以下考虑：完备数据集上元组之间的支配关系是传递的。例如，元组p_i支配p_j，p_j又支配p_k，进而p_i支配p_k。不完备数据集中元组之间的支配关系不具有传递性，这种不具有传递性的支配关系导致了环支配，环支配又导致了skyline查询的结果集为空。假设，数据集中只有三个元组p_i，p_j，p_k，p_i＝(4，*，2，3)，p_j＝(2，3，*，3)，p_k＝(*，2，4，3)，p_i在第1和第4维上支配p_j，p_j在第2和第4维上支配p_k，但是p_i却不能在任一维上支配p_k，相反p_k在第3和第4维上支配p_i。这就使得支配关系形成了一个环，最后没有哪个元组可以成为skyline点。为了解决不完备数据集上支配关系的不可传递性和环支配问题，本发明提出了该编码聚类策略。为了能够对元组进行聚类，首先为元组进行编码，定义1给出了不完备数据集上元组编码的形式化描述：

定义1：元组编码

p_i′·tuple_code(p_i″·tuple_code)＝M_i，M_i＝(m₁，m，…，m_k)；若p_i′·v_k(p″_i·v_k)＝*，M_i·m_ik＝0；若p_i′·v_k(p_i″·v_k)≠*，Mi·m_ik＝1，

其中k∈[1，λ]([λ+1，d]).

其中，IS’和IS”分别是IS在前λ维上的投影和后d-λ维上的投影，d是不完备数据集IS的维数，p_i′和p_i″分别是元组p_i前λ维上的投影和后d-λ维上的投影，M_i是元组p_i的编码，λ是维度的分割常数，λ∈[1，d]。现假设有不完备数据集IS，用图2表示。由7个10维不完备元组构成，其中“*”表示某元组在该维度上的缺失值。设数据集已经按维度重要程度从大到小进行了排序，因此图2中的各维重要程度为D1＞D2＞...＞D10。针对维度重要性高的前λ维和维度重要性低的后d-λ维分别赋予相对权值0.5，0.4，0.3，0.2，0.1。相对权值越大用户对于这一维的偏好程度就越大。

每一个聚类都有一个对应的聚类编码，聚类编码保存在一个集合中。下面是对聚类编码的定义：

定义2聚类编码

对于如果存在cc_j≠p′_i·tuple_code，那么CS′＝CS′∪{p_i′·tuple_code}

其中，CS’是严格聚类编码集合，cc_j是聚类编码。

本发明的聚类策略基于以下几个方面的考虑。首先，元组编码个数在[1，2^d]之间，随着维数的增长，元组编码个数会呈指数倍增长。这将会极大降低skyline查询的效率，因为执行skyline算法的执行次数与聚类个数成正比。其次，被用户赋予高重要程度的维度在进行skyline查询时应当比被用户赋予低重要程度的维度得到更多的考虑，并且为了提升skyline查询的效率，本发明将依据维度重要性将整个不完备数据集划分成两部分，分别进行两种不同的skyline偏好查询方法。

下面是对元组编码与聚类编码之间包含关系的定义：

定义3包含关系

令d₁＝λ，p_i″·tuple_code＝M_i″，M_i″＝(m_ik，m_ik+1，…，m_id)，如果并且i≠j，cc_j＝(c_jk，c_jk+1，…，c_jd)，对于m_ik≤c_jk，p_i″被放在聚类编码为cc_j的对应类中，p_i″与cc_j之间的包含关系用p_i″→cc_j表示；如果对于m_ik＞c_jk，那么cc_j→p_i″并且这个聚类的编码将被更新为p_i″·tuple_code，cc_j将被移出CS″；如果p_i″·tuple_code与cc_j之间没有包含关系或者CS″是空集。除p_i″将被放于聚类编码为cc_j这种情况之外，都要更新CS″；

CS″＝CS″∪{p_i″·tuple_code}

其中，CS”是松散聚类编码集合；

当出现一个元组同时满足多个包含关系时，它可以放于多个聚类中，使得具有较大相似程度的元组尽可能充分的进行比较，进而将一些被其他元组支配的元组剔除。

对于数据集合中的任意一个元组p_i，对p_i′执行严格聚类规则，对p_i″执行松散聚类规则。下面利用图2举例说明严格聚类和松散聚类的过程：p₁′＝(3，3，*，2，5)，

p₁′·tuple_code＝(1，1，0，1，1)，p₃′＝(2，1，*，4，8)，p₃·tuple_code＝(1，1，0，1，1)，

根据严格聚类规则，p₁′和p₃′加入到同一个聚类中，聚类编码记为cc₀＝(1，1，0，1，1)，当前CS＝{cc₀}。

p₄′＝(10，4，2，*，5)，p₄′·tuple_code＝(1，1，1，0，1)，p₇′＝(4，2，6，*，*)，p₇′·tuple_code＝(1，1，1，0，0)，p₄′·tuple_code≠p₇′·tuple_code

p₄′和p₇′需要分开聚类，聚类编码分别记为cc₁＝(1，1，1，0，1)和cc₂＝(1，1，1，0，0)，CS′＝CS′∪{cc₁，cc₂}.对于松散聚类过程，设有三个元组p₁″、p₅″和p₆″，p₁″＝(2，*，1，2，5)，p₁″·tuple_code＝(1，0，1，1，1)，p₅″＝(9，*，3，3，2)，p₅″.

tuple_code＝(1，0，1，1，1)，且

而，p₆″＝(*，*，1，*，5)，p₆″·tuple_code＝(0，0，1，0，1)，因此，p₁″、p₅″和p₆″都聚于类编码为10111的类中。

本发明所述的skyline偏好查询方法有两种，一种是针对属性重要程度较高的数据集投影执行基于严格聚类的skyline偏好查询方法，另一种是针对属性重要程度较低的数据集投影执行基于松散聚类的skyline偏好查询方法。

其一，基于严格聚类的skyline偏好查询方法分为两步执行，首先是对IS’执行严格聚类，然后是对经过严格聚类后没被剔除的元组执行基于属性值排序的skyline偏好查询算法(以下简称为SAVO算法)。上文中已经详细阐述了严格聚类的执行流程，现在将SAVO算法的具体执行流程阐述如下：

(1)：对数据集IS’中的各维度按照元组属性值非降序排序，使得更有可能支配其他元组的元组优先被处理；每维经过排序后都会生成一个数组D_i，i∈[1，λ]，对于每个数组D_i都有D_i[j]＞＝D_i[j+1]，j∈[1，|IS′|)，其中|IS′|代表IS’中的元组个数；对于在第i维上存在缺失属性值的元组是不会加入数组D_i中的，为了节省存储空间，数组D_i中存储的只是元组id，而不是真正的元组；设立一个指向数组D_i的指针ptr_i，经过严格聚类后没有被支配的元组都纳入候选集Candidate_Set；随机选择一个数组D_i，处理数组D_i中指针ptr_i指向的元组；每个在候选集中的元组都会维护两个值，一个是元组被处理的次数，记为processedCount，一个是元组编码中1的个数即非缺失属性维数，记为dimCount；

(2)：对于当前被选中的元组p，有以下几种情况：

①，如果元组p′没有被处理过且元组p′还在候选集Candidate_Set中，就将它与除自己以外没有跟它比较过的元组p_j′进行比较，即使p_j′已经被之前处理过的元组所支配；若候选集中存在元组支配p′，元组p′就被移出候选集；

②：如果元组p′没有被处理过但是被之前处理过的元组支配，即已不在候选集Candidate_Set中，p′就只与还在候选集Candidate_Set中并且没有与p′比较过的元组比较；在以上两种情况下，候选集中被元组p′支配的元组会被移出候选集；

③：如果元组p′已经被处理过了就不进行任何比较；

④：p′_j∈IS′，其中i≠j，p′_i和p′_j可比较的维度少于个，在这些可比较的维度上，若p′_i在至少一维上的值比p′_j“好”，剩余维度上的值不比p′_j“差”就认为p′_i弱支配p′_j，记为p_i′＞*p_j′

如果两个元组p_i′与p_j′之间具有弱支配关系，还需要比较这两个元组的重量；若满足p_i′的重量大于p_j′的重量，才认为p_i′支配p_j′；综合考虑非缺失属性值及其被用户所赋予的权重，元组重量计算公式(1)，如下所示：

(3)：当候选集中的元组p的比较次数达到了其非缺失属性维数dimCount，就将这个元组从候选集移到严格skyline结果集SSRS中；

(4)：当候选集为空或者所有元组都被处理过至少一次时，把候选集Candidate_Set中的其余元组都放入严格聚类skyline结果集SSRS中，此时基于属性值排序的skyline偏好查询过程结束。

为了清楚详细阐述SAVO算法的执行流程，我们以一个数据集示例进行展示。首先，本发明以图2中的数据举例说明元组重量的计算方法，

对于p₂′＝(*，*，3，5，*)，p₄′＝(10，4，2，*，5)，p₂与p₄′只有第三维是可以比较的，且p₂′·v₃＞p₄′·v₃，具有弱支配关系，还需计算

p₂′·weight＝3*0.3+5*0.2＝1.9，p₄′·weight＝10*0.5+4*0.4+2*03+5*0.1＝7.7，

由于1.9＜7.7，p₂′不可以支配p₄′。

然后，利用图2不完备数据集示例详细描述基于属性值排序的skyline偏好查询算法。IS’按各维排序后的结果如图3所示。现在，ptr1指针指向数组D1的一个元组p₄，p₄是被处理的第一个元组且在候选集Candidate_Set中，p₄与除自己之外的p₁-p₃，p₅-p₇比较。p₄＞p₁，p₂弱支配p₄，经计算，p₂·weight＜p₄·weight，p₂是不可以支配p₄的。p₄与p₃之间没有支配关系，p₄支配p₅，p₄与p₆和p₇没有支配关系。p₄.processedCount＝1，p₁和p₅从候选集Candidate_Set中移出。然后ptr2指针指向数组D2的第一个元组p₄，由于p₄已经被处理过，不用跟任何元组比较了，p₄.processedCount＝2。接着被处理的是数组D3中的元组p₇，p₇与p₁-p₃，p₅，p₆比较，p₁与从候选集中移出的p₁和p₅比较没有被这两个元组所支配；p₇与候选中的元组比较时，p₇弱支配p₂，并且p₇·weight＞p₂·weight，所以p₇支配p₂，同时p₇支配p₂，p₃，p6，p₂，p₃，p₆从候选集Candidate_Set中被移出。当迭代进行到第4次时，处理元组p₆，p₆首先跟被移出候选集中的元组比较，发现p₆没有被这些元组所支配；由于p₆还在在候选集中，此时候选集中的元组是p₄与p₇，都已经与p₆比较过了，p₆.processedCount＝1。直到第12次迭代，p₇.processedCount＝p₇.dimCount，p₇从候选集Candidate_Set中移到严格skyline查询结果集SSRS中。到第20次迭代，p₄也从候选集中移到SSRS中。所以，经过严格聚类和基于属性值排序的skyline偏好查询算法，我们得到了p₄和p₇两个候选skyline点。

其二，基于松散聚类的skyline偏好查询方法分为两步执行，首先是对IS”执行松散聚类，然后是对经过松散聚类后没被剔除的元组执行基于支配程度计算的skyline偏好查询算法。

根据上文所述的松散聚类规则及包含关系的定义，我们得到了松散聚类的结果，即若干个包含不被支配元组的聚类。但是聚类中的元组之间可能不具有支配关系，这些无法互相支配的元组都会作为skyline查询结果返回给用户，用户还需要在这些结果中进行筛选，并且有一部分查询结果并不符合用户需求。因此，本发明提出了一种通过计算元组之间的支配程度来决定元组之间的支配关系的方法。综合以上几点的考虑，支配程度的定义如下所示：

定义4支配程度

任意两元组之间可以比较的维属性值之差可视作这一维上两元组的支配距离；那么同一聚类中任意两个元组的支配程度可记为可比较维度上支配距离与权重乘积的和；令w_λ+1，w_λ+2，...，w_d为各维权值，元组p_i的各维非缺失属性值记为v_ij，j∈[λ+1，d]，那么任意两元组p_i对p_j的支配程度记为：其中k代表元组之间可以比较的维度，如果domain_i，j＞0，then>i＞p_j，如果domain_i，j＜0，p_j＞p_i，如果domain_i，j＝0，p_i与p_j不可相互支配；

在每个聚类中计算任意两个元组的支配程度，将一些被支配的元组剔除后，把每个聚类中的元组放入松散skyline查询结果集RSRS中。

经过前文所述的两种skyline偏好查询方法，我们分别得到了严格聚类结果集SSRS和松散聚类结果集RSRS，对SSRS与RSRS取交集，如果交集不为空集，那么交集中的元组就是最终的skyline查询结果；如果交集为空集，分别计算SSRS和RSRS中元组的信息熵。根据信息熵的概念，变量的不确定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大。一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高。所以，信息熵也可以说是系统有序化程度的一个度量。一个元组也可以看作是具有若干影响因素的系统，元组的属性就是系统的影响因素。某个缺失属性代表着这个影响因素的不确定性，缺失属性越多影响因素就越不确定，使得这个元组更加混乱和无序，元组的信息熵就越大。因此，信息熵大的元组被信息熵小的元组所支配。下面给出信息熵的计算公式：

其中，E(p_i)代表元组p_i的信息熵，h′代表元组属性标准化后的值，n代表元组的维数。将SSRS和RSRS中的元组进行信息熵的计算后得出最终的skyline查询结果反馈给用户。

下面还是以图2中的数据为例，结合聚类编码、包含关系以及聚类规则，对基于松散聚类的skyline偏好查询方法进行展示。图2中元组的松散聚类结果如图4所示。

在cluster 10111中计算：

domain_1，5＝0.5*(2-9)+0.3*(1-3)+0.2*(2-3)+0.1*(5-2)＝-4＜0，所以p₅＞p₁；domain_5，6＝0.3*(3-1)+0.1*(2-5)＝0.3＞0，所以p₅＞p₆；

在cluster 11101中计算：

domain_2，3＝0.5*(3-5)+0.4*(2-5)+0.3*(1-4)+0.1*(2-9)＝-3.8＜0，p₃＞p₂；同理，计算出domain_2，6＜0，p₆＞p₂；domain_3，6＞0，p₃＞p₆；

cluster 11011和cluster 11110中分别得到p₄和p₇。

由此，RSRS＝{p5，p3，p4，p7}，SSRS＝{p4，p7}，最终的skyline查询结果为p4和p7。