К-значи; EWSTпреведи

  • Прочитајте хартија со средства K (PS) или хартија со средства K (PDF) .
  • Белешка: неодамна, сличен резултат, иако независен, беше привлечен кон нашето внимание. Пред нашата работа. За завршување, исто така можете да го прочитате ова.
  • Прочитајте X-хартија (PS) или X-хартија (PDF) .
  • Имплементацијата на X-средства и K-средства во бинарна форма е сега достапна за преземање! Во моментов, постојат верзии за Linux, OS X и MS-Windows. Тие се дистрибуираат под следниве услови:
    • Софтверот може да се користи само за експериментални и истражувачки цели.
    • Софтверот не може да се дистрибуира на никого и не може да се продава во целина или делумно во поголем софтверски производ, или во изворна или бинарна форма.
    За да ја преземете, едноставно преземете ја датотеката за вас во делот за преземање .
  • Х-средствата им се достапни на истражувачите во изворна форма. Кодот е во стандарден C и може да се изврши самостојно или преку пакет MATLAB. Позната е компилацијата под GCC (на Linux, Cygwin, OS X, Solaris и FreeBSD) и MSVC ++.
    • Во прилог на средствата X, овој код исто така вклучува и брза поддршка за средствата K. Тој ќе ја забрза апликацијата K-mean, под услов:
      • Вашите податоци не се поголеми од 15 големини. Сепак, можете да го добиете и користите кодот ако не е така, но не очекувајте дека ќе биде особено брз. Кодот вклучува едноставна имплементација на K средства што не користат дрвја KD.
      • Можете да ги пресметате евклидовските растојанија помеѓу која било од двете точки на податоци и ова растојание е значајно на некој начин за вас.Ова е всушност предуслов за кој било алгоритам за K-средства.
    • За да добиете пристап, пополнете ги празнините во овој Договор за лиценца и вратете ги на Дан Пелег (да, има знак плус, оставете го и зборовите пред и потоа - работи). Во суштина, сè што вели е дека не можете да ја користите оваа комерцијална програма. Можете да го побарате тоа - веќе доделивме околу 800 лиценци на луѓе од што повеќе институции и секогаш сум среќен што имам повеќе корисници. Јас нема да продавам, изнајмувам, дистрибуирам или на друг начин ќе ја користам вашата е-адреса за која било друга цел освен да ви дадам упатства за преземање.
    • Исто така, постои список за испраќање на средства K и список за испраќање X-средство .
  • Подолу, подготвивме „водич за цртани филмови“ за К-средства:

Еве еден сет на податоци во 2 димензии, со 8000 поени во него. Ние ќе извршуваме 5 средства на неа (K-значи со K = 5). Покрај точките што ги гледаме, К-значи избра 5 случајни поени за одделенските центри. Ова се точки на сина, зелена, црвена, црна и виолетова боја. Забележете дека, како што има шанса, тие не одговараат на Гаусите (всушност, јас морав да ја принудам програмата да ги произведе оние „први“ почетни точки - добро е да се добијат „точните“ почетни точки) .

Сега, програмата поминува низ точки на податоци, асоцирајќи ја секоја со центарот за класа што е најблиску до него. Точките што ги гледате се обоени според центарот во кој се поврзани. Забележете ја сино-зелената граница во горниот десен агол. Оваа (теоретска) линија на точки што е еднакво оддалечена од зелените и сините центри одредува каде припаѓаат.

Следниот чекор на алгоритмот е повторно поставување на центрите на класите. Зелениот центар ќе биде поставен во центарот на табелата на сите зелени точки, итн. Како што се испостави, зелениот центар ќе се премести надесно и нагоре. Црната линија што излегува од зелениот центар го покажува тоа. Забележете дека црно-црвените центри имаат секоја половина од Гаузиецот од лево (и околу половина од Гаусиецот во кој се наоѓаат), така што и двајцата се „потребни“ лево. Движењето на пурпурниот центар е многу мало.

Кликнете на сликата за да видите поголема верзија. Може да го отворите во нов прозорец на прелистувачот за да можете да продолжите да го читате текстот.

Зелено-виолетовата граница се движи нагоре и надесно; покажува дека зелената ќе има само „свои поени“, а виолетовата ќе има двајца Гауси. Во долниот лев агол, се чини дека црвената ја изгуби трката до црна (црната боја е повеќе лево).

Црвеното помина десно. Така заработи повеќе пурпурни поени. Бидејќи сите пурпурни точки се десно, овој ефект се интензивира. Следствено, виолетовата боја губи поени на црвена боја, а исто така се движи десно (и нагоре).

Вовед во дрвјата КД

Повторно, нашата база на податоци од 8000 точки генерирана по случаен избор од 5-гаусова дистрибуција. Треба да ги видите основните Гауси. Сината граница го означува јазолот "корен" kd. Ги опфаќа сите точки.

Сега ги гледате бабите и дедовците на коренот. Секој од нив е поделба на својот родител, по X-оската овој пат.

Еве ги првите седум слоја на дрвото КД, сите на една фотографија.

Изработка на К-брзи средства со дрвја КД

Сите објаснувања во демо-верзијата К-средства погоре беа точни за традиционалните средства за К. „Традиционално“ значи дека кога ќе излезете и одлучите кој центар е најблизу до секоја точка (на пример, утврдете ги боите), направете наивна: за секоја точка, пресметајте ги растојанијата до сите центри и пронајдете го минимумот. Нашата програма е тогаш многу попаметна. Прво изградете kd-дрво за поени (оној што го видовте порано). Сега претпоставиме дека kd јазолот е целосно во сопственост на центар. Ова значи дека на следното централно движење ќе влијае центарот на масата на точките во овој kd-јазол (и нивниот број). Значи, со претходно пресметување на центарот на масата на секој kd јазол и складирање во јазолот, можеме да заштедиме многу работи. [што покажува дека еден јазол е во целосна сопственост на центар, исто така, може да се направи ефикасно - видете брзи средства за хартија K].

Овој тип на брза пресметка се одвиваше зад сцената за време на демо-то. Секогаш кога се покажа дека еден јазол е во целосна сопственост на центар, програмата го нацрта правоаголникот на јазолот. За визуелизација, таа ги привлече и точките во неа, но нема потреба од „вистинска“ програма. Користете само многу мал постојан број на аритметички операции за да го пресметате ефектот што ќе го има одреден kd-јазол. Ова е спротивно на собирање на координатите на секоја точка во тој правоаголник, односно трошок што е линеарен по бројот на точки во правоаголникот.

Забележете колку беше лесно да се пресметаат црно-сините центри на маса. Блек зеде само два јазли и околу 50 дополнителни поединечни поени. Сината зеде 5 јазли, плус околу 10 поени. Споредете го ова со приближно 8000/5 = 1600 поени што ги има секој (и прави 5 растојанија за секое!).

Друга интересна работа што треба да се забележи е како овие правоаголници стануваат сè помали кога се приближуваме до теоретската гранична линија за која порано зборувавме. Следете ја црвено-виолетовата граница. Како што се приближуваме на ова, се потешко и потешко е големите, дебели јазли да се држат целосно или со црвена или со виолетова боја. Ако размислите за нив, тие не можат да бидат во целосна сопственост на кој било од центрите доколку оваа граница ги пресекува. Значи, колку е поблиску до границата, толку се помали правоаголниците. И има многу индивидуални точки многу близу до границата.

Овој материјал се базира на работа поддржана од Националниот фонд за наука, грант бр. 0121671.