التفاصيل البيبلوغرافية
| العنوان: |
Joint Cluster Analysis of Attribute Data and Relationship Data: The Connected κ-Center Problem, Algorithms and Applications. |
| المؤلفون: |
Ge, Rong, Ester, Martin, Gao, Byron J., Zengjian Hu, Bhattacharya, Binay, Ben-Moshe, Boaz |
| المصدر: |
ACM Transactions on Knowledge Discovery from Data; Jul2008, Vol. 2 Issue 2, p7-7:35, 35p, 5 Diagrams, 7 Charts, 1 Graph |
| مصطلحات موضوعية: |
CLUSTER analysis (Statistics), ALGORITHMS, DATA, SOCIAL networks, MATHEMATICAL programming, MARKET segmentation |
| مستخلص: |
Attribute data and relationship data are two principal types of data, representing the intrinsic and extrinsic properties of entities. While attribute data have been the main source of data for cluster analysis, relationship data such as social networks or metabolic networks are becoming increasingly available. It is also common to observe both data types carry complementary information such as in market segmentation and community identification, which calls for a joint cluster analysis of both data types so as to achieve better results. In this article, we introduce the novel Connected κ-Center (CκC) problem, a clustering model taking into account attribute data as well as relationship data. We analyze the complexity of the problem and prove its NP-hardness. Therefore, we analyze the approximability of the problem and also present a constant factor approximation algorithm. For the special case of the CκC problem where the relationship data form a tree structure, we propose a dynamic programming method giving an optimal solution in polynomial time. We further present NetScan, a heuristic algorithm that is efficient and effective for large real databases. Our extensive experimental evaluation on real datasets demonstrates the meaningfulness and accuracy of the NetScan results. [ABSTRACT FROM AUTHOR] |
|
Copyright of ACM Transactions on Knowledge Discovery from Data is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Complementary Index |
