180 lines
3.6 KiB
C++
180 lines
3.6 KiB
C++
|
#include <iostream>
|
|||
|
|
#include <vector>
|
|||
|
|
#include <algorithm>
|
|||
|
|
#include <string>
|
|||
|
|
using namespace std;
|
|||
|
|
|
|||
|
|
struct Point
|
|||
|
|
{
|
|||
|
|
vector<double> val;
|
|||
|
|
int id;
|
|||
|
|
string tag;
|
|||
|
|
};
|
|||
|
|
|
|||
|
|
int N,Attr,K,MaxIteration;
|
|||
|
|
vector<Point> vec;
|
|||
|
|
|
|||
|
|
vector<Point> center;
|
|||
|
|
vector<vector<int>> Clusters;
|
|||
|
|
|
|||
|
|
|
|||
|
|
double getDistance(Point& a,Point& b)
|
|||
|
|
{
|
|||
|
|
if(a.val.size()!=b.val.size()) return -1;
|
|||
|
|
double dis=0;
|
|||
|
|
size_t sz=a.val.size();
|
|||
|
|
for(size_t i=0;i<sz;i++)
|
|||
|
|
{
|
|||
|
|
dis+=pow(a.val.at(i)-b.val.at(i),2);
|
|||
|
|
}
|
|||
|
|
dis=sqrt(dis);
|
|||
|
|
return dis;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
bool ClusterCmp(vector<int>& a,vector<int>& b)
|
|||
|
|
{
|
|||
|
|
double sumA=0,sumB=0;
|
|||
|
|
for(auto idx:a) ///<2F><>Ⱥ<EFBFBD>еĸ<D0B5><C4B8><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
|
{
|
|||
|
|
for(auto idPos:vec.at(idx).val) /// <20><><EFBFBD><EFBFBD>ÿ<EFBFBD><C3BF>ά<EFBFBD><CEAC>
|
|||
|
|
{
|
|||
|
|
sumA+=idPos;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
for(auto idx:b)
|
|||
|
|
{
|
|||
|
|
for(auto idPos:vec.at(idx).val)
|
|||
|
|
{
|
|||
|
|
sumB+=idPos;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
return sumA<sumB;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
void KMeans()
|
|||
|
|
{
|
|||
|
|
for(int IterTime=0;IterTime<MaxIteration;IterTime++)
|
|||
|
|
{
|
|||
|
|
vector<vector<int>> newCluster(center.size());
|
|||
|
|
for(size_t i=0;i<vec.size();i++)
|
|||
|
|
{
|
|||
|
|
int minID=-1;
|
|||
|
|
double minDistance=INT_MAX;
|
|||
|
|
|
|||
|
|
for(size_t j=0;j<center.size();j++)
|
|||
|
|
{
|
|||
|
|
double dis=getDistance(vec.at(i),center.at(j));
|
|||
|
|
if(minDistance>dis)
|
|||
|
|
{
|
|||
|
|
minID=j;
|
|||
|
|
minDistance=dis;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
newCluster.at(minID).push_back(i);
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
sort(newCluster.begin(),newCluster.end(),ClusterCmp);
|
|||
|
|
|
|||
|
|
#ifdef _OUTPUT_ITER
|
|||
|
|
cout<<"===============Iteration "<<IterTime<<"================="<<endl;
|
|||
|
|
for(size_t i=0; i<newCluster.size(); i++)
|
|||
|
|
{
|
|||
|
|
cout<<"Cluster "<<i<<":"<<endl;
|
|||
|
|
for(size_t j=0; j<newCluster.at(i).size(); j++)
|
|||
|
|
{
|
|||
|
|
cout<<"Point "<<vec.at(newCluster.at(i).at(j)).id<<" Tag="<<vec.at(newCluster.at(i).at(j)).tag<<endl;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
#endif
|
|||
|
|
|
|||
|
|
if(newCluster==Clusters)
|
|||
|
|
{
|
|||
|
|
break;
|
|||
|
|
}
|
|||
|
|
else
|
|||
|
|
{
|
|||
|
|
Clusters=newCluster;
|
|||
|
|
for(size_t i=0;i<Clusters.size();i++)/// i <20><>Ⱥ
|
|||
|
|
{
|
|||
|
|
for(int j=0;j<Attr;j++) /// j <20><><EFBFBD><EFBFBD>ά<EFBFBD><CEAC>
|
|||
|
|
{
|
|||
|
|
double sum=0;
|
|||
|
|
for(size_t k=0;k<Clusters.at(i).size();k++) /// k <20><>Ⱥ<EFBFBD>еĵ<D0B5>
|
|||
|
|
{
|
|||
|
|
sum+=vec.at(Clusters.at(i).at(k)).val.at(j);
|
|||
|
|
}
|
|||
|
|
center.at(i).val.at(j)=sum/Clusters.at(i).size();
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
cout<<"End"<<endl;
|
|||
|
|
|
|||
|
|
|
|||
|
|
for(size_t i=0;i<Clusters.size();i++)
|
|||
|
|
{
|
|||
|
|
cout<<"Cluster "<<i<<":"<<endl;
|
|||
|
|
for(size_t j=0;j<Clusters.at(i).size();j++)
|
|||
|
|
{
|
|||
|
|
cout<<"Point "<<vec.at(Clusters.at(i).at(j)).id<<" Tag="<<vec.at(Clusters.at(i).at(j)).tag<<endl;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
|
|||
|
|
int main()
|
|||
|
|
{
|
|||
|
|
cout<<"Please Input N,Attr,K,MaxIteration"<<endl;
|
|||
|
|
cin>>N>>Attr>>K>>MaxIteration;
|
|||
|
|
for(int i=0;i<N;i++)
|
|||
|
|
{
|
|||
|
|
Point p;
|
|||
|
|
for(int j=0;j<Attr;j++)
|
|||
|
|
{
|
|||
|
|
double tmp;
|
|||
|
|
cin>>tmp;
|
|||
|
|
p.val.push_back(tmp);
|
|||
|
|
}
|
|||
|
|
cin>>p.tag;
|
|||
|
|
p.id=i;
|
|||
|
|
|
|||
|
|
vec.push_back(p);
|
|||
|
|
}
|
|||
|
|
cout<<"Please Select Seed From Input..."<<endl;
|
|||
|
|
for(int i=0;i<K;i++)
|
|||
|
|
{
|
|||
|
|
int temp;
|
|||
|
|
cin>>temp;
|
|||
|
|
center.push_back(vec.at(temp));
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
KMeans();
|
|||
|
|
return 0;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
/**
|
|||
|
|
15 3 3 100
|
|||
|
|
1 1 0.5 <EFBFBD>й<EFBFBD>
|
|||
|
|
0.3 0 0.19 <EFBFBD>ձ<EFBFBD>
|
|||
|
|
0 0.15 0.13 <EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
|
0.24 0.76 0.25 <EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
|
0.3 0.76 0.06 ɳ<EFBFBD><EFBFBD>
|
|||
|
|
1 1 0 <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
|
1 0.76 0.5 <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
|
1 0.76 0.5 <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
|
0.7 0.76 0.25 <EFBFBD><EFBFBD><EFBFBD>ȱ<EFBFBD><EFBFBD><EFBFBD>˹̹
|
|||
|
|
1 1 0.5 ̩<EFBFBD><EFBFBD>
|
|||
|
|
1 1 0.25 Խ<EFBFBD><EFBFBD>
|
|||
|
|
1 1 0.5 <EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
|
0.7 0.76 0.5 <EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
|
0.7 0.68 1 <EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
|
1 1 0.5 ӡ<EFBFBD><EFBFBD>
|
|||
|
|
1 9 12
|
|||
|
|
*/
|