مسألة $k$ مركزThe $k$-center problem ←

إن مسألة تحديد أوجه التشابه والأختلاف في كميات البيانات الضخمة أمراً شائعاً للغاية، تسعى الشركات لتصنيف العملاء ذوي سلوك الشراء المتقارب في مجموعات، ويُجمّع مستشارو السياسة الدوائر الانتخابية بناء على أنماط التصويت فيها، كما تُصنّف محركات البحث صفحات الويب في مجموعات استناداّ إلى تشابه مواضيعها.

The problem of finding similarities and dissimilarities in large amounts of data is ubiquitous: companies wish to group customers with similar purchasing behavior, political consultants group precincts by their voting behavior, and search engine group webpages by their similarity of topics.

يُشار عادة إلى هذه العملية بـ "عنقدة البيانات"، وقد حظيت مسألة التوصّل إلى تصنيفات فعالة ومناسبة لهذه العناقيد بدراسات مستفيضة.

Usually we speak of clustering data, and there has been extensive study of the problem of finding good clusterings.

نتناول هنا نمطً محدداً من أنماط العنقدة يسمى "مسألة $k$ مركز".

Here we consider a particular variant of clustering, the $k$-center problem.

حيث يعطى في هذه المسألة - كمدخل - بياناً تاماً غير موجهاً $G = (V, E)$ ، مع وجود مسافة $d_{i,j} >= 0$ بين كل زوج من العقد $i, j \in V$ . ونفترض أن $d_{ii} = 0$ وأن $d_{ij} = d_{ji}$ لأي $i, j \in V$ ، وأن المسافات تخضع لمتارجحة المثلث، أي أنه لكل ثلاثية من العقد $i, j, l \in V$ يتحقق الشرط $d_{ij} + d_{jl} >= d_{il}$ .

In this problem, we are given as input an undirected, complete graph $G = (V, E)$, with a distance $d_{ij} >= 0$ between each pair of vertices $i, j \in V$. We assume $d_{ii} = 0$, $d_{ij} = d_{ji}$ for each $i,j \in V$, and that the distances obey the triangle inequality: for each triple $i,j,l \in V$, it is the case that $d_{ij} + d_{jl} >= d_{il}$.

حيث تعبر المسافات في هذه المسألة عن مدى التشابه، فالعقد المتقاربة تكون أكثر تشابهاً، بينما تكون العقد المتباعدة أقل تشابهاً.

In this problem, distances model similarity: vertices that are closer to each other are more similar, whereas those farther apart are less similar.

يعطي في هذه المسألة - كمدخل إضافي - عدد صحيحاً $k$ ، ويكون الهدف في هذه المسألة هو تحديد $k$ عنقوداً من خلال تجميع العقد الأكثر تشابهاً (تقارباً) مع بعضها البعض من عنقود واحد.

We are also given a positive integer $k$ as input. The goal is to find $k$ clusters, grouping together the vertices that are most similar into cluster together.

سنختار في هذه المسألة مجموعة $S \subseteq V$ (بحيث يكون حجمها $|S| = k$ ) لتكون مراكزاً ل $k$ عنقود.

In this problem, we will choose a set $S \subseteq V$, $|S| = k$, of $k$ cluster centers.

ستقوم كل عقد بتحديد أقرب مركز مجموعة للإنضمام إليها، مما يؤدي إلى تقسيم العقد إلى $k$ عنقود مختلف.

Each vertex will assign itself to its closest cluster center, grouping the vertices into $k$ different clusters.

يتمثل الهدف في مسألة " $k$ مركز" في تصغير أقصى مسافة تفصل أي عقدة عن مركز مجموعتها إلى أدنى حد ممكن.

For the $k$-center problem, the objective is to minimize the maximum distance of a vertex to its cluster center.

يكمن الهدف من الناحية الهندسة في إيجاد مركز لـ $k$ دائرة متساوية نصف القطر تغطي جميع العقد، بحيث يكون نصف القطر أصغر ما يمكن.

Geometrically speaking, the goal is to find the centers of $k$ different balls of the same radius that cover all points so that the radius is as small as possible.

وبصيغة أكثر دقة، نعرّف المسافة التي تفصل العقدة $i$ عن مجموعة العقد $S \ subseteq V$ بأنها $d(i, S) = min_{j \in S}d_{ij}$ .

More formally, we define the distance of a vertex $i$ from a set $S \ subseteq V$ of vertices to be $d(i, S) = min_{j \in S}d_{ij}$.

مسألة kkk مركزThe $k$-center problem ←

مسألة $k$ مركزThe $k$-center problem ←