homework.md

Домашно №1/1 по СДП-практикум за КН2, 8гр.

Това е единственото домашно по СДП-практикум за студентите, посещаващи практикума на група 8. Срокът му е до след края на семестъра, като дотогава са позволени неограничен брой предавания. За всяко предадено по-рано домашно ще давам кратка обратна връзка. Домашното може да ви донесе най-много 20т., като има възможности за бонус (т.е. изкарване на >100%).

Условието на домашното е просто - реализирайте алгоритъм за клъстеризация (k-means clustering) върху произволен тип данни - например, точки в равнината или пространството. За дадено множество от данни и брой желани клъстери, в които да се "разпределят" данните, и извършва следната последователност от действия:

1. Тъй като всеки клъстер трябва да си има "център", първата стъпка е да се изберат тези центрове спрямо данните. Един вариант е да се изберат на произволен принцип k на брой елемента от множеството като първоначални центрове.

2. Всеки елемент от данните се включва към този клъстер, чийто център е най-близо. Това означава, че трябва да имате функция, която да изчислява колко "близки" са два елемента от вашите данни - например, квадратът на евклидовото разстояние между точките ^{_{(ако не е на квадрат, е възможно алгоритъмът да не конвергира)}}.

3. За всеки клъстер се изчислява неговия нов център. Например, ако работим с точки в n-мерно пространство, един вариант е да вземем медицентъра на всички точки в даден клъстер (неговите координати са средно-аритметичното на координатите на всички точки в клъстера). Друг вариант е да изберем този елемент от клъстера, за който сумата от разстоянията до всички останали в същия клъстер е най-малка. Забележете, че новите центрове не е задължително да бъдат част от първоначалните данни - няма никакъв проблем в това.

4. goto стъпка 2 - спрямо новите центрове данните се "клъстеризират" отново и т.н. Алгоритъмът приключва в момента, в който се достигне стабилно състояние - иначе казано, между две последователни итерации нито един елемент от данните не си сменя клъстера, в който участва.

Една примерна имплементация би била следната:

#include<vector>
#include<utility> // std::pair

// точките в равнината очевидно са наредени двойки от координатите си;
// можем да използваме std::pair и за дадена точка p
// да достъпваме нейните коодринати с p.first и p.second
using Point = std::pair<double,double>;

void clusterize(const std::vector<Point>& points, size_t k)
{
    // do the heavy lifting here
    // накрая просто cout-ваме за всеки клъстер кои точки му принадлежат
}

От една страна, това домашно има множество начини да бъде усложнено, и не е проблем да променяте аргументите или типа на връщане на тази функция. Един вариант за изкарване на бонус е данните да се четат от файл, или пък резултатите да се записват във файл. Друг вариант е да се реализира алгоритъма върху по-сложни данни (примерно std::string-ове и Levenshtein distance между тях ^{(отново най-добре на квадрат)}). Трета възможност (продължение на горната) е да шаблонизирате по подходящ начин функцията така, че да работи за произволни типове данни и методи за изчисляване на данни между тях, и да я извикваме по подобен начин:

std::vector<Point> points = /*...*/;
double distFun1(const Point& p1, const Point& p2) { /*...*/}

clusterize(points, 3, distFun1); // с конкретна функция за разстояние
clusterize(points, 3, [](const Point& p1, const Point& p2){ /*...*/ }); // lambda

От друга страна, не се изисква от вас да се дълбаете в научна литература, за да достигнете до най-най-доброто алгоритмично решение. Вашите домашни ще бъдат оценявани по няколко критерия:

• коректност на решението (алгоритъма) (8т.)
• добре подбрани структури от данни (12т.) Обърнете внимание, че трябва да пазите и самите клъстери по някакъв начин, да помните центровете и т.н. Ще бъде поощрено, ако избегнете преизчисляването на едни и същи неща по няколко пъти, както и да използвате ненужно комплексни структури от данни като мап от вектори от стрингове към списъци от интове и т.н.
• добре подреден код и спазване на добри практики за писане на кода (можете да спечелите или загубите точки оттук)

За повече обяснения как работи алгоритъма, както и за обяснения "в картинки" добър (но не и перфектен) начален източник е Уикипедия.

Относно предаването

Подробности за предаването на работите можете да намерите тук - моля да ги прочетете внимателно. Крайният срок е 00:00 на 30 януари, но по-ранното предаване се насърчава силно.

Примерен вход и изход

Файл с примерни входни данни можете да откриете тук. Представлява списък от коодринати на точки в равнината, горе-долу разпределени на четири групи. Оптималното разпределение на 4 клъстера (т.е. примерния изход) можете да намерите тук. Забележете, че подредбата на точките в един и съш клъстер е произволна - важно е коя с коя е в един и същ клъстер.

Важно: Имайте предвид, че поради естеството на алгоритъма оптималния резултат понякога не се достига! Иначе казано, възможно е вашият изход да не съвпада с примерния. Това не е показател за грешка в алгоритъма - най-добре пуснете алгоритъма няколко пъти, и в зависимост от първоначално избраните центрове може при някое рестартиране да достигнете оптималното разпределение.

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