Loading...
Please wait, while we are loading the content...
Similar Documents
Clustering with prior information.
| Content Provider | CiteSeerX |
|---|---|
| Author | Allahverdyan, Armen E. Galstyan, Aram Steeg, Greg Ver |
| Abstract | A fundamental issue in clustering concerns one’s ability (and limitation) to detect clusters, assuming they are built-in to the model that generates the data [1, 4]. Results for the planted partition graph models suggest that clusters can be recovered with arbitrary accuracy if sufficient data (link density) is available [2]. More recently, this problem of cluster detectability has been addressed theoretically for sparse graphs, by formulating it through a certain Ising–Potts Hamiltonian [6]. It was shown that clustering in the sparse planted partition model is characterized by a phase transition from detectable to undetectable regimes as one increases the overlap between the clusters [6]. Specifically, for sufficiently large inter–cluster coupling, the underlying (planted) cluster structure has no impact on the optimal (minimum–energy) configuration of the Hamiltonian. Here we examine the cluster–detection problem in semi–supervised settings, when one has some background knowledge about the clusters. Generally speaking, such information can be in form of pair-wise constraints (via must – and cannot links), or, alternatively, via known cluster assignments for a fraction of nodes. Here we consider the latter scenario defined on a planted bisection graph model [2]. Namely, consider two clusters containing N–nodes each. Each pair of nodes within the same cluster is linked with probability α/N, where α is the average within–cluster connectivity. Also, each pair of nodes in different clusters is linked with probability γ/N, where γ is inter–cluster connectivity. We assign weights J and K to within–cluster and inter–cluster links, and define the |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Prior Information Undetectable Regime Fundamental Issue Cluster Detectability Cluster Connectivity Certain Ising Potts Hamiltonian Cluster Structure Phase Transition Different Cluster Minimum Energy Sufficient Data Background Knowledge Pair-wise Constraint Inter Cluster Connectivity Planted Partition Graph Model Inter Cluster Link Latter Scenario Partition Model Cluster Detection Problem Large Inter Cluster Coupling Arbitrary Accuracy Sparse Graph Cluster Assignment Planted Bisection Graph Model |
| Content Type | Text |
