Discuss the advantages and disadvantages of treating clustering as an opti- mization problem. Among other factors, consider efficiency, non-determinism, and whether an optimization-based approach captures all types of clusterings that are of interest.

What will be an ideal response?

Two key advantage to treating clustering as an optimization problem are

that (1) it provides a clear definition of what the clustering process is do-
ing, and (2) it allows the use of powerful optimization techniques that have

been developed in a wide variety of fields. Unfortunately, most of these op-
timization techniques have a high time complexity. Furthermore, it can be

shown that many optimization problems are NP hard, and therefore, it is
necessary to use heuristic optimization approaches that can only guarantee
a locally optimal solution. Often such techniques work best when used with
random initialization, and thus, the solution found can vary from one run to
another. Another problem with optimization approaches is that the objective
functions they use tend to favor large clusters at the expense of smaller ones.