Probabilistic Distance Clustering: Algorithm and Applications - Clustering Challenges in Biological Network - page 48

Table 2.5. Data for Example 2.7

These data points are shown in Fig. 2.6(a). The PDQ algorithm, with =0 . 001
(in Step 4), required 14 iterations to determine the three clusters, with approximate
centers. The final centers, computed after the clusters were determined, are shown
in Fig. 2.6(b). In the top left cluster, the facility practically coincides with one of
the customers.

50 50

40 40

30 30

20 20

10 10

0 0

0 10 20 30 40 50 0 10 20 30 40 50

(a) The 15 customers (b) The final facilities and clusters

Fig. 2.6. Illustration of Example 2.7

Example 2.8. Figure 2.7 shows a data set with N = 1000 random points in
[ 10 , 10] 2 , representing the customers. It is required to locate K =4facili-

ties to serve the customers. The algorithm starts with 4 random initial locations
(centers.) Using different symbols: o, x, +, * for 4 clusters, Fig. 2.7(a) illustrates
the convergence from arbitrary initial points. The final clusters, obtained by trun-
cating the cluster probabilities, allow better estimates of the facilities locations
(centers), see Sec. 2.3, Remark (d).

−

Figure 2.7(b) shows the final clusters and

facilities.

The PDQ Algorithm also solves Capacitated MFLP 's, where the cluster sizes
q k in (2.30) play the role of the facility capacities. When these are given, we
have a capacitated MFLP, and the PDQ Algorithm simplifies further, see Sec. 2.3,
Remark (c). This is illustrated in Example 2.9 and Fig. 2.8 below.