Subspace Clustering Meets Dense Subgraph Mining: A Synthesis of Two Paradigms
Subspace Clustering Meets Dense Subgraph Mining: A Synthesis of Two Paradigms
复制标题
DOI：
10.1109/icdm.2010.95
复制
发表时间：
2010-12
期刊：
影响因子：
--
通讯作者：
Stephan Günnemann;Ines Färber;Brigitte Boden;T. Seidl
中科院分区：
文献类型：
--
作者：
Stephan Günnemann;Ines Färber;Brigitte Boden;T. Seidl
今天的应用程序处理多种类型的信息：表示对象之间关系的图形数据和表征单个对象的属性数据。同时分析这两个数据源可以提高挖掘方法的质量。最近，引入了组合聚类方法，该方法检测一个大型图中的密集连接节点集，这些节点集根据其所有属性值也显示出高相似性。然而，对于属性数据，这种全空间聚类往往导致聚类结果不佳。因此，子空间聚类被引入到确定每个集群的属性的局部相关子集。在这项工作中，我们提出了一种方法，通过加入子空间聚类和密集的子图挖掘的范例，即我们确定的节点集，显示出高相似性的子集，其尺寸，以及密集连接在给定的图中找到同质组。我们的双重集群根据其密度，大小和相关维度的数量进行了优化。我们开发的冗余模型将聚类限制在一个可管理的大小，只有最有趣的集群。我们介绍了我们的聚类的有效计算的算法Gamer。在合成和真实的世界的数据进行了全面的实验，我们表明，Gamer实现了低运行时间和高聚类质量。
Today's applications deal with multiple types of information: graph data to represent the relations between objects and attribute data to characterize single objects. Analyzing both data sources simultaneously can increase the quality of mining methods. Recently, combined clustering approaches were introduced, which detect densely connected node sets within one large graph that also show high similarity according to all of their attribute values. However, for attribute data it is known that this full-space clustering often leads to poor clustering results. Thus, subspace clustering was introduced to identify locally relevant subsets of attributes for each cluster. In this work, we propose a method for finding homogeneous groups by joining the paradigms of subspace clustering and dense sub graph mining, i.e. we determine sets of nodes that show high similarity in subsets of their dimensions and that are as well densely connected within the given graph. Our twofold clusters are optimized according to their density, size, and number of relevant dimensions. Our developed redundancy model confines the clustering to a manageable size of only the most interesting clusters. We introduce the algorithm Gamer for the efficient calculation of our clustering. In thorough experiments on synthetic and real world data we show that Gamer achieves low runtimes and high clustering qualities.