К-медијанска кластеризација

Из Википедије, слободне енциклопедије

У статистици и анализи података, к-медијанска кластеризација је алгоритам груписања података . Он је варијација k-means кластера где уместо израчунавања mean за сваки кластер да би одредили његов центроид, уместо тога израчунава се медиана. Ово има ефекат смањења грешке над свим кластерима поштујући 1-норма метричког растојања, за разлику од квадрата 2-норма метричког растојања (што k-means ради.)

Ово се директно повезује са k-медиа проблемом који је проблем проналажења k центара такав да кластери формирани од њих су највише компактни. Формално, дате су тачке скупа x, k центри ci треба да буду изабрани тако да смање суму растојања од сваког x до најближег ci.

Критеријум функције формулисан на овај начин је понекад бољи од критеријума уk-means clustering алгоритму, у ком је коришћена сума квадратног растојања. Сума дистанци је веома коришћена у апликацијама као што је facility location.

Предложени алгоритам користи Лојдов стил понављања, који алтернира између очекиване вредности (E) и максимално (M) корака, правеци Expectation–maximization алгоритам. У Е кораку сви предмети су додељени њиховом најближем медијану. У М кораку, медијане су поново израчунате користећи медијану у свакој димензији понаособ.

Медиане и медоиди[уреди]

Како је медијан израчунат у свакој димензији понаособ, појединачна својства ће се видети из скупа, чинећи овај алгоритам поузданијим за дискретне или чак бинарне скупове података. Међутим, средства нису неопходно случајеви из скупа података, док својства могу доћи из различитих случајева. Овај алгоритам је често збуњен k-медоид алгоритмом. Међутим, медиан мора да буде случај из скупа података, док за (мултиваријантну) медиану ово важи за појединачна својства вредности. Медиана према томе може бити комбинација вишеструких својстава. Дати су вектори (0,1), (1,0) и (2,2), медиана је очигледно (1,1) и не постоји у оригиналном скупу и према томе не може бити медоид.

Софтвер[уреди]

  • ELKI includes various k-means variants, including k-medians.
  • GNU R includes k-medians in the "flexclust" package.

Види остало[уреди]

Референце[уреди]