Question

Suppose that you are to allocate a number of automatic teller machines (ATMs) in a given region so as to satisfy a number of constraints. Households or places of work may be clustered so that typically one ATM is assigned per cluster. The clustering, however, may be constrained by two factors: (1) obstacle objects, i.e., there are bridges, rivers, and highways that can affect ATM accessibility, and (2) additional user-specified constraints, such as each ATM
should serve at least 10,000 households. How can the ? -means clustering algorithm be
modified for quality clustering under both constraints?

Data mining

Answer 1

Constraint algorithms can be modified in the following aspects to allow for constraint-based clustering

1. Microcluster : Objects are clustered locally into microclusters. In a microcluster, no obstacle can appear between any two other objects in the microcluster.
2. Distance measurement: Distance between two objects should be adjusted if obstacles occur between them. In such cases, reachable distance, instead of direct distance, should be used. Reachable distance gives the minimal ( or estimated minimal) distance between two objects with consideration of obstacles.
3. Medoid-based: For every district, initialize k clusters, where k is between the minimum and maximum number of ATMs allowed in the district. Suppose a medoid is going to be moved across a district border.If after such a move the source district has fewer ATMS than required, or the destination district has more ATMs than expected, then the center can only be moved within the border to the point closest to the corresponding point in the other region