| dbo:abstract
|
- In statistics, k-medians clustering is a cluster analysis algorithm. It is a variation of k-means clustering where instead of calculating the mean for each cluster to determine its centroid, one instead calculates the median. This has the effect of minimizing error over all clusters with respect to the 1-norm distance metric, as opposed to the squared 2-norm distance metric (which k-means does.) This relates directly to the k-median problem with respect to the 1-norm, which is the problem of finding k centers such that the clusters formed by them are the most compact. Formally, given a set of data points x, the k centers ci are to be chosen so as to minimize the sum of the distances from each x to the nearest ci. The criterion function formulated in this way is sometimes a better criterion than that used in the k-means clustering algorithm, in which the sum of the squared distances is used. The sum of distances is widely used in applications such as the facility location problem. The proposed algorithm uses Lloyd-style iteration which alternates between an expectation (E) and maximization (M) step, making this an expectation–maximization algorithm. In the E step, all objects are assigned to their nearest median. In the M step, the medians are recomputed by using the median in each single dimension. (en)
- Le problème k-médiane, ou k-median en anglais, est un problème d'optimisation combinatoire, une branche de l'algorithmique. Le problème peut se décrire de façon informelle ainsi : étant donné n villes, il faut ouvrir un magasin dans k villes, tel que la moyenne des distances entre les villes et leurs plus proches magasins soit minimisée. Ce problème, proche du problème des k-moyennes, permet entre autres de faire du partitionnement de données. Une formalisation du problème est la suivante. Étant donné un ensemble de points V, de choisir un sous-ensemble de k points, appelés centres, tel que la moyenne des distances des points de V au plus proche centre soit minimisée. Le problème est le plus souvent exprimé dans un espace métrique. Il s'exprime alors naturellement comme un problème sur un graphe dont les arêtes ont des poids respectant l'inégalité triangulaire. On peut aussi considérer que les sommets sont divisés en deux catégories : les sommets ouvrables, et les sommets à couvrir. Ce problème est surtout étudié du point de vue de l'approximation. Il en existe plusieurs variantes, avec des métriques particulières, ou d'autres coûts à minimiser. (fr)
- Ме́тод -медіа́н — застосовувана в статистиці і машинному навчанні варіація методу -середніх для задач кластеризації, де для визначення центроїда кластера замість середнього обчислюється медіана. Такий підхід відповідає мінімізації похибки за всіма кластерами в метриці з 1-нормою, замість метрики з 2-нормою, використовуваною в стандартному методі -середніх. Задача визначення -медіан полягає в пошуку таких центрів, що сформовані за ними кластери будуть «найкомпактнішими». Формально, для заданих точок даних , центри слід вибрати так, щоб мінімізувати суму відстаней від кожної до найближчого . Метод іноді працює краще, ніж метод -середніх, де мінімізується сума квадратів відстаней. Критерій суми відстаней широко використовується для транспортної задачі. Ще альтернатива — метод , у якому шукають оптимальний медоїд, а не медіану кластера (медоїд є однією з точок даних, тоді як медіани такими бути не мусять). (uk)
- Метод -медиан — применяемая в статистике и машинном обучении вариация метода -средних для задач кластеризации, где для определения центроида кластера вместо среднего вычисляется медиана. Такой подход соответствует минимизации ошибки по всем кластерам в метрике с 1-нормой, вместо метрики с 2-нормой, используемой в стандартном методе -средних. Задача определения -медиан состоит в поиске таких центров, что сформированные по ним кластеры будут наиболее «компактными». Формально, при заданных точках данных , центров должны быть выбраны так, чтобы минимизировать сумму расстояний от каждой до ближайшего . Метод иногда работает лучше, чем метод -средних, где минимизируется сумма квадратов расстояний. Критерий суммы расстояний широко используется для транспортных задач. Ещё альтернатива — метод , в котором ищут оптимальный медоид, а не медиану кластера (медоид является одной из точек данных, в то время как медианы таковыми быть не обязаны). (ru)
|
| rdfs:comment
|
- In statistics, k-medians clustering is a cluster analysis algorithm. It is a variation of k-means clustering where instead of calculating the mean for each cluster to determine its centroid, one instead calculates the median. This has the effect of minimizing error over all clusters with respect to the 1-norm distance metric, as opposed to the squared 2-norm distance metric (which k-means does.) (en)
- Le problème k-médiane, ou k-median en anglais, est un problème d'optimisation combinatoire, une branche de l'algorithmique. Le problème peut se décrire de façon informelle ainsi : étant donné n villes, il faut ouvrir un magasin dans k villes, tel que la moyenne des distances entre les villes et leurs plus proches magasins soit minimisée. Ce problème, proche du problème des k-moyennes, permet entre autres de faire du partitionnement de données. (fr)
- Метод -медиан — применяемая в статистике и машинном обучении вариация метода -средних для задач кластеризации, где для определения центроида кластера вместо среднего вычисляется медиана. Такой подход соответствует минимизации ошибки по всем кластерам в метрике с 1-нормой, вместо метрики с 2-нормой, используемой в стандартном методе -средних. Метод иногда работает лучше, чем метод -средних, где минимизируется сумма квадратов расстояний. Критерий суммы расстояний широко используется для транспортных задач. (ru)
- Ме́тод -медіа́н — застосовувана в статистиці і машинному навчанні варіація методу -середніх для задач кластеризації, де для визначення центроїда кластера замість середнього обчислюється медіана. Такий підхід відповідає мінімізації похибки за всіма кластерами в метриці з 1-нормою, замість метрики з 2-нормою, використовуваною в стандартному методі -середніх. Задача визначення -медіан полягає в пошуку таких центрів, що сформовані за ними кластери будуть «найкомпактнішими». Формально, для заданих точок даних , центри слід вибрати так, щоб мінімізувати суму відстаней від кожної до найближчого . (uk)
|
