Определить расстояние между точками на плоскости или в пространстве нетрудно. Гораздо сложнее изобрести адекватную метрику, вычисляющую "расстояние" между двумя текстовыми документами.
Задача кластеризации формулируется следующим образом. Дается множество объектов и количество кластеров, то есть "ящиков", по которым элементы исходного множества можно распределять. Требуется "раскидать" объекты по кластерам так, чтобы в одном кластере оказалиь элементы, наиболее близкие друг к другу в соответствии с данной метрикой.
В качестве примера можно привести результат кластеризации множества двумерных точек. Количество кластеров равно пяти.
Enter number of poins 20
Enter number of clasters 5
0 : 9 0
0 : 9 3
0 : 8 1
1 : 12 3
1 : 14 4
1 : 14 4
1 : 13 4
2 : 15 1
2 : 17 3
2 : 18 4
2 : 16 0
3 : 3 3
3 : 3 2
3 : 1 0
3 : 1 4
3 : 0 4
3 : 2 0
4 : 5 4
4 : 6 4
4 : 5 3
Здесь показан результат кластеризации выведенный программой консольного вида. Но нами будет написана и программа в которой результат кластеризации будет выведен в виде точек, нарисованных в окне в стиле Windows.
Для кластеризации произвольной коллекции можно использовать например несложный алгоритм C-Means:
приписать каждый элемент коллекции случайному кластеру
ЦИКЛ
найти центроид (центральный элемент) каждого кластера
приписать каждый объект кластеру, с наиболее близким к объекту центроидом
ПОКА происходят изменения
Для разминки можно запрограммировать алгоритм C-Means для точек на плоскости.
Задача
На первом шаге программа должна считывать из входного файла cmeans.txt координаты точек коллекции, принимать с клавиатуры число формируемых кластеров M и по алгоритму C-Means "раскидывать" точки по M кластерам. Полученные кластеры следует визуализировать.
Решение
Здесь мы рассмотрим только решение задачи кластеризации методом C-Means. Алгоритм KNN используется в задачах 6.3 и 6.4 и приводить один и тот же фрагмент кода мне кажется излишним.
Хотя по условию задачи требуется написать программу, выполняющую кластеризацию двумерных точек, обобщенная версия алгоритма выглядит ненамного сложнее.
Пусть элементы произволного типа Type находятся в некотором контейнере. Считается, что в программе определена функция расстояния
double Distance(const Type& lhs, const Type& rhs)
возвращающая расстояние между любыми двумя объектами типа Type.
Наша задача написать функцию Cluster(), по заданным итераторам начала и конца диапазона объектов и количеству кластеров М формирующую требуемые кластеры:
template <class Iterator>
vector<list <typename Iterator::value_type> > Cluster(const Iterator begin, const Iterator end, int M)
Возвращаемое значение представляет собой вектор, каждый элемент которого является отдельным кластером - списком объектов типа Iterator::value_type.
Для начала нам потребуется несложная служебная функция Centroid(), возвращающая центроид набора объектов, задаваемого итераторами begin и end:
template <class Iterator>
// double minDist = numeric_limits
for(Iterator current = begin; current != end; current++){
if(Dist < MinDist) {
double MinDist = 5000;
Iterator::value_type Element;
for(Iterator c = begin; c != end; c++)
Element = *current;
return Element;
Функция Cluster() реализует алгоритм, приведенный в постановке задачи на псевдокоде:
приписать каждый элемент коллекции случайному кластеру
ЦИКЛ
найти центроид (центральный элемент) каждого кластера
приписать каждый объект кластеру, с наиболее близким к объекту центроидом
ПОКА происходят изменения
Функция Cluster()
template <class Iterator>
vector<list <typename Iterator::value_type> > Cluster(const Iterator begin, const Iterator end, int M){
// создать М кластеров
vector<list<Iterator::value_type> > Clusters(M);
// приписать каждый элемент коллекции (объект) случайному кластеру
//точнее заполнить кластера случайными значениями
for(Iterator c = begin; c != end; c++)
Clusters[rand_0toN1(M)].push_back(*c);
//массив центроидов
vector<Iterator::value_type> Centroids(M);
bool modified;
do{
//заполним массив центроидов данными (собственно в каждом элементе
// массива центроидов будет одно значение)
for(int z = 0; z < M;z++){
Centroids[z] = Centroid(Clusters[z].begin(), Clusters[z].end());
}
modified = false;
vector<list<Iterator::value_type> > NewClusters(M);
for(int OldCl = 0; OldCl < M; OldCl++){
for(Iterator c =Clusters[OldCl].begin(); c!= Clusters[OldCl].end(); c++){
double MinDist = 50000;
int ClusterNo;
for(int centroid = 0; centroid < M; centroid++){
double Dist = Distance(*c, Centroids[centroid]);
if(Dist < MinDist){
MinDist = Dist;
ClusterNo = centroid;
}
}
if(ClusterNo != OldCl) modified = true;
NewClusters[ClusterNo].push_back(*c);
}
}
Clusters = NewClusters;
}//do
while(modified);//пока происходят изменения
return Clusters;
}
Чтобы применить функцию Cluster() к двумерным точкам, осталось описать структуру "точка на плоскости" и запрограммировать простые функции Distance() и main():
int main(int args,char* argv[]){
list vector<list<Point> > Clusters = Cluster(lp.begin(), lp.end(), M);
// просмотреть этот инициализированный случайным образом массив кластеров
return 0;
struct Point{
double Distance(const Point& p1, const Point p2){
int N, M;
cout << "Enter number of poins ";
cin >> N;
cout << "Enter number of clasters ";
cin >> M;
for(int i = 0; i < N; i++){
p.x = rand_0toN1(20);
p.y = rand_0toN1(5);
lp.push_back(p);
for(i = 0; i < M; i++)
Результат :
Enter number of poins 20
Enter number of clasters 5
0 : 9 0
0 : 9 3
0 : 8 1
1 : 12 3
1 : 14 4
1 : 14 4
1 : 13 4
2 : 15 1
2 : 17 3
2 : 18 4
2 : 16 0
3 : 3 3
3 : 3 2
3 : 1 0
3 : 1 4
3 : 0 4
3 : 2 0
4 : 5 4
4 : 6 4
4 : 5 3
Естественно результат при каждом новом запуске программы будет различным. Программа отсортировала введенные случайным образом данные по пяти кластерам. Теперь можно модифицировать программу так, чтобы все найденные ею точки были выведены на экран.
Полный текст оттестированной консольной программы смотрите на следующей странице.
Назад |
Начало урока |
Вверх |
Вперед
Содержание
