{"id":1896,"date":"2025-10-26T17:43:16","date_gmt":"2025-10-26T16:43:16","guid":{"rendered":"https:\/\/xeddixx.cluster029.hosting.ovh.net\/?page_id=1896"},"modified":"2025-10-27T09:43:44","modified_gmt":"2025-10-27T08:43:44","slug":"clustering-problems","status":"publish","type":"page","link":"https:\/\/www.francq.info\/index.php\/clustering-problems\/","title":{"rendered":"Clustering Problems"},"content":{"rendered":"\n

Abstract<\/strong><\/h4>\n\n\n\n

The clustering problems are a class of optimization problems where the goal is to group a set of objects in different groups, each object being assigned in one group only.<\/p>\n\n\n\n

Table of Contents<\/h5>\n\n\n\n

1. Description<\/a><\/p>\n\n\n\n

2. Constraints<\/a><\/p>\n\n\n\n

3. Criteria<\/a><\/p>\n\n\n\n

4. Algorithm Evaluation<\/a><\/p>\n\n\n\n

4.1. Adjusted\u00a0Rand\u00a0index<\/a><\/p>\n\n\n\n

4.2. Precision<\/a><\/p>\n\n\n\n

4.3. Recall<\/a><\/p>\n\n\n\n

5. Related<\/a><\/p>\n\n\n\n

References<\/a><\/p>\n\n\n\n

1. Description\u2191<\/a><\/h5>\n\n\n\n

A clustering problem, sometimes called cluster analysis, is the task to assigning a set of objects into groups (called clusters) according some criteria, each object being assigned in one group only. In general, the criteria is to group similar objects in the same cluster (using some similarity measure), where each cluster can contain as many objects as necessary. But the goal may vary.<\/p>\n\n\n\n

For example in the bin packing problem, each cluster can only group a maximal size (giving by the sum of the sizes of the object already group together), and the goal is to use as few cluster as possible.<\/p>\n\n\n\n

The rigorous definition of the problem begins with a set\u00a0\\(\\mathcal{O}\\) of\u00a0\\(|\\mathcal{O}|\\) objects to place in a set \\(G\\)<\/mathml> of \\(|\\mathcal{G}|\\) groups:<\/p>\n\n\n\n

\\[\\mathcal{O}=\\{o_{o}\\}\\quad\\quad\\forall\\,o=1,\\cdots,|\\mathcal{O}|\\]\n\n\n\n

\\[\\mathcal{G}=\\{g_{g}\\}\\quad\\quad\\forall\\,g=1,\\cdots,|\\mathcal{G}|\\]\n\n\n\n

Depending of the problem, the number of available groups can be infinite (in the bin packing problem for example) or limited (such as when some tasks must be assigned to a fixed number of workers).\u00a0<\/p>\n\n\n\n

2. Constraints\u2191<\/a><\/h5>\n\n\n\n

The clustering problems introduce several constraints, but it is always possible to define them as a member of one of the three constraints classes, namely the \u201ccapacity constraints\u201d class, the \u201chomogeneity constraints\u201d and the \u201cprofile constraints\u201d classes.<\/p>\n\n\n\n

The \u201ccapacity constraints\u201d\u00a0\\(\\mathcal{C}_{c}\\) constitute the first class. It regroups the constraints related to a given \u201ccapacity\u201d of each group. In the bin packing problem for example, each group has a maximal size. These constraints may also introduce a minimal or maximal number of objects that a group must have. In the case the assignment of tasks to workers, one constraint could be a homogeneous repartition of the task between them.<\/p>\n\n\n\n

The \u201chomogeneity constraints\u201d\u00a0\\(\\mathcal{C}_{h}\\) are the second class. These constraints specify the conditions that must be respected by an object when it is put in an existing group. This may be, for example, a minimal similarity with the objects already assigned.<\/p>\n\n\n\n

The \u201cprofile constraints\u201d\u00a0\\(\\mathcal{C}_{p}\\)\u00a0are the last class. To obtain a valid solution, the clustering must respect the \u201cwishes\u201d of each object. For example, if the goal is to assign students to work groups, a constraint could be to avoid that a given genre is represented only once in a group.<\/p>\n\n\n\n

3. Criteria\u2191<\/a><\/h5>\n\n\n\n

The criteria that should be optimized for the clustering problem vary from one problem to another. For some problems, the criteria are well defined (for example in the bin packing problem where the number of clusters should be minimized). But, in the case of the document clustering, where the goal is to regroup \u201csimilar\u201d documents in the same topic, the problem is\u00a0fuzzy:<\/em>\u00a0is it not easy to express the fact that \u201ctwo documents are similar\u201d. When several criteria must be optimized, the clustering problem is a\u00a0multiple objective one<\/a>.<\/p>\n\n\n\n

Some clustering algorithms work with one type of problems (criteria) only. The k-Means algorithm is designed to minimize the within-cluster sum of squares\u00a0[1<\/a>]. Other methods, such as the\u00a0Grouping Genetic Algorithms (GGA)<\/a>, may solve a whole range of problems.<\/p>\n\n\n\n

4. Algorithm Evaluation\u2191<\/a><\/h5>\n\n\n\n

To evaluate the performance of an algorithm, it is necessary to have an \u201cideal\u201d solution for a given problem instance and some measures to compare the \u201ccomputed\u201d solution provided by the algorithm with this \u201cideal\u201d solution. Two situations exist:<\/p>\n\n\n\n

    \n
  1. The quality of a solution depends on a computation based on the clustering. For example, in the bin packing problem, the number of clusters needed to group the objects.<\/li>\n\n\n\n
  2. The quality of a solution depends on the particular assignment of the objects.<\/li>\n<\/ol>\n\n\n\n

    In the first case, a comparison between the computation done for the \u201ccomputed\u201d and \u201cideal\u201d solution evaluates the performance of the algorithm. For the second situation, we need some measures to compare the \u201ccomputed\u201d assignments to the ideal ones (each object is assigned to an \u201cideal cluster\u201d in the \u201cideal\u201d solution). At least, three measures can be used for this latest comparison:<\/p>\n\n\n\n