数据挖掘中一种基于集合覆盖的元素重要性估计算法

对给定数据集合的元素重要性进行估计是数据挖掘领域中的一项重要应用。现有的技术都是通过排序或选择来发现重要元素,其主要缺点是没考虑高排名对象可能非常相似甚至完全相同这一事实,忽略了高排名对象间的冗余性。因此,在强调多样性的场合,该方法性能有限。本文通过将排序和选择相结合,提出一种基于集合覆盖的元素重要性估计算法。该算法不仅考察单个集合覆盖的解,而且计算元素参与的高质量集合覆盖数量,进而为元素分配重要性分值。基于实际数据的实验和用户学习结果表明,本文算法性能高效,元素重要性评估结果的有用性高,且与人类感知相一致。

An Importance of Elements Estimation Algorithm Based on Set-Cover in Data Mining

For a given set of data elements, the importance estimation is an important application in data mining. The existing work identifies important entities either by ranking or by selection. The major shortcoming of such approaches is that they ignore the redundancy between high-ranked entities, which may in fact be very similar or even identical. Therefore, in scenarios where diversity is desirable, such methods perform poorly. In this paper, by the combination of the sort and selection, we propose an importance of elements estimation algorithm based on the set cover, Instead of looking at a single set-cover solution, our algorithm computes the importance of entities by counting of the number of good set covers an entity participates. In a user study and an experimental evaluation on real data, we demonstrate that our framework is efficient and provides useful and intuitive results.