Pattern Recognition, 4th Edition

The Algorithms

In this section, we discuss agglomerative algorithms based on graph theory concepts. More specifically, we consider graphs, G, of N nodes with each node corresponding to a vector of X. Clusters are formed by connecting nodes together, and this leads to connected subgraphs. Usually, an additional graph property, h(k), must be satisfied by the subgraphs in order to define valid clusters. In this context, the function g involved in GAS is replaced by g^h(k), where h(k) is the graph property. Some typical properties that can be adopted are [Jain 88, Ling 72].

• Node connectivity. The node connectivity of a connected subgraph is the largest integer k such that all pairs of nodes are joined by at least k paths having no nodes in common. ...