Глава 6
Исходники и exe-файл программы находятся ЗДЕСЬ
Программа, демострирующая кластеризацию по алгоритму C-Means
#include <string>
#include <iostream>
#include<vector>
#include<list>
#include <time.h>
#include<math.h>
#include<algorithm>
using namespace std;
// Generate a random integer from 0 to N-1.
int rand_0toN1(int n) {
return rand() % n;
}
struct Point{
int x, y;
};
double Distance(const Point& p1, const Point p2){
return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}
//------------------------------
template <class Iterator>
Iterator::value_type Centroid(const Iterator begin, const Iterator end){
// double minDist = numeric_limits::max();
double MinDist = 5000;
Iterator::value_type Element;
for(Iterator current = begin; current != end; current++){
double Dist = 0;
for(Iterator c = begin; c != end; c++)
Dist += Distance(*current, *c);
if(Dist < MinDist) {
MinDist = Dist;
Element = *current;
}
}
return Element;
};
//--------------------------------
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;
}
//-------------------------------------
int main(int args,char* argv[]){
srand(time(NULL)); // Set seed for random numbers.
int N, M;
cout << "Enter number of poins ";
cin >> N;
cout << "Enter number of clasters ";
cin >> M;
list lp;
for(int i = 0; i < N; i++){
Point p;
p.x = rand_0toN1(20);
p.y = rand_0toN1(5);
lp.push_back(p);
}
vector<list<Point> > Clusters = Cluster(lp.begin(), lp.end(), M);
// просмотреть этот инициализированный случайным образом массив кластеров
for(i = 0; i < M; i++)
for(list::iterator p = Clusters[i].begin(); p!= Clusters[i].end();p++)
cout << i << " : " << p->x << " " << p->y << endl;
return 0;
}// end main
Результат :
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
Исходники и exe-файл программы находятся ЗДЕСЬ
Назад |
Начало урока |
Вверх |
Вперед
Содержание