K-означава; EWST Превод

  • Четене на хартия с K-средства (PS) или хартия с K-средства (PDF) .
  • Забележка: наскоро подобен резултат, макар и независим, беше привлечен на вниманието ни. Преди нашата работа. За завършване можете да прочетете и това.
  • Четене на хартия с X хартия (PS) или X хартия (PDF) .
  • Внедряването на X-средства и K-средства в двоична форма вече е достъпно за изтегляне! В момента има версии за Linux, OS X и MS-Windows. Те се разпространяват при следните условия:
    • Софтуерът може да се използва само за експериментални и изследователски цели.
    • Софтуерът не може да се разпространява на никого и не може да се продава изцяло или частично в по-голям софтуерен продукт, било то в източник или в двоична форма.
    За да го изтеглите, просто изтеглете файла за вас в секцията за изтегляне .
  • X-средството е достъпно за изследователите във източник. Кодът е в стандартен C и може да се изпълнява независимо или чрез пакет MATLAB. Известна е компилация под GCC (на Linux, Cygwin, OS X, Solaris и FreeBSD) и MSVC ++.
    • В допълнение към средствата X, този код включва и бърза поддръжка за средствата K. Той ще ускори приложението K-mean, при условие че:
      • Вашите данни не са по-големи от 15 размера. Можете обаче да получите и използвате кода, ако случаят не е такъв, но не очаквайте да бъде особено бърз. Кодът включва проста реализация на K средства, които не използват KD дървета.
      • Можете да изчислите евклидовите разстояния между която и да е от двете точки с данни и това разстояние е значително по някакъв начин за вас.Това всъщност е предпоставка за всеки алгоритъм на K-средства.
    • За да получите достъп, попълнете празните места в това лицензионно споразумение и ги изпратете обратно на Дан Пелег (да, има знак плюс, оставете го и думите преди и след - работи). По принцип всичко, което се казва, е, че не можете да използвате тази търговска програма. Можете да кандидатствате за него - вече предоставихме около 800 лиценза на хора от възможно най-много институции и винаги съм щастлив да имам повече потребители. Няма да продавам, давам под наем, разпространявам или използвам по друг начин вашия имейл адрес за каквато и да е цел, освен за да ви дам инструкции за изтегляне.
    • Съществува и пощенски списък с K-средства и пощенски списък с X-средства .
  • По-долу сме подготвили „ръководство за карикатура“ за K-средства:

Ето набор от данни в 2 измерения, с 8000 точки в него. Ще изпълним 5 средства върху него (K-средства с K = 5). В допълнение към точките, които виждаме, K-означава избрани 5 случайни точки за центровете на класа. Това са точките от синьо, зелено, червено, черно и лилаво. Забележете, че както съществува шансът, те не отговарят на Гаусите (всъщност трябваше да принудя програмата да създаде тези „първи“ изходни точки - доста добре е да получа „правилните“ изходни точки) .

Сега програмата преминава през точки от данни, свързвайки всяка с центъра на класа най-близо до нея. Точките, които виждате, са оцветени според центъра, в който са свързани. Забележете синьо-зелената граница в горния десен ъгъл. Тази (теоретична) линия от точки, които са на еднакво разстояние от зеления и синия център, определя къде принадлежат.

Следващата стъпка от алгоритъма е пренасочване на центровете на класовете. Зеленият център ще бъде поставен в центъра на таблицата на всички зелени точки и т.н. Както се оказа, зеленият център ще се премести надясно и нагоре. Черната линия, излизаща от зеления център, показва това. Забележете, че черните и червените центрове споделят половината от Гауса вляво (и около половината от Гауса, в който се намират), така че и двамата "питат" вляво. Движението на лилавия център е много малко.

Кликнете върху изображението, за да видите по-голяма версия. Можете да го отворите в нов прозорец на браузъра, за да можете да продължите да четете текста.

Зелено-лилавата граница се движи нагоре и надясно; показва, че зеленото ще има само "своите точки", а лилавото ще има два гауса. В долния ляв ъгъл изглежда, че червеното е загубило състезанието от черно (черното е повече вляво).

Червеният тръгна надясно. Така той спечели повече лилави точки. Тъй като всички лилави точки са вдясно, този ефект се засилва. Следователно лилавото губи точки към червеното и също се движи надясно (и нагоре).

Въведение в KD дърветата

Отново нашият набор от 8000 точки генерира произволно от 5-гаусово разпределение. Трябва да видите основните Гауси. Синята граница означава "корен" възел kd. Той обхваща всички точки.

Сега виждате бабите и дядовците на корена. Всеки от тях е подразделение на своя родител, по оста X този път.

Ето първите седем слоя от дървото KD, всички на една снимка.

Правенето на K-бързо означава с KD дървета

Всички обяснения в демонстрацията на K-значи по-горе бяха верни за традиционните K средства. „Традиционен“ означава, че когато излезете и решите кой център е най-близо до всяка точка (например, определете цветовете), направете наивния: за всяка точка изчислете разстоянията до всички центрове и намерете минимума. Тогава нашата програма е много по-умна. Първо изградете kd-дърво за точки (тази, която видяхте по-рано). Сега приемете, че kd възел е изцяло собственост на център. Това означава, че следващото централно движение ще бъде повлияно от центъра на масата на точките в този kd-възел (и техния брой). Така че, като предварително изчислим центъра на масата на всеки kd възел и го съхраним във възела, можем да спестим много неща. [показва, че възел е изцяло собственост на център, също може да се направи ефективно - вижте бързи хартиени K-средства].

Този тип бързо изчисление се проведе зад кулисите по време на демонстрацията. Винаги, когато се показваше, че възел е изцяло собственост на център, програмата рисува правоъгълник на възела. За целите на визуализацията той също привлича точките в него, но няма нужда от „истинска“ програма. Използвайте само много малък постоянен брой аритметични операции, за да изчислите ефекта, който ще има определен kd-възел. Това се противопоставя на сумирането на координатите на всяка точка вътре в този правоъгълник, т.е. цена, която е линейна по броя точки в правоъгълника.

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

Друго интересно нещо, което трябва да се отбележи, е как тези правоъгълници стават по-малки, когато се приближаваме до теоретичната гранична линия, за която говорихме по-рано. Следвайте червено-лилавата граница. Когато се приближаваме към това, все по-трудно големите и дебели възли се задържат изцяло от червено или лилаво. Ако се замислите за тях, те не могат да бъдат изцяло собственост на нито един от центровете, ако тази граница ги пресича. Така че колкото по-близо се приближаваме до границата, толкова по-малки са правоъгълниците. И има много отделни точки много близо до границата.

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