LineId：每条记录的id号 1到658923
Label：有null、appread、kerndtlb、kernsock、kerntsp、kernterm等值
Timestamp：时间戳 1117838570到1136390405
Date：包含年月日的日期2005.06.03到2001.01.04
Node：节点
Time：包含年月日时分秒微秒毫秒的日期 2005-06-03-15.42.50.527847到2006-01-04-08.00.05.167045
Type：只有ras一种值
Component：只有kernel(内核)和app两种值
Level：只有info类和fatal类
Content：对事件的简单描述
EventId：事件的id，与content对应

2.将其分为定量属性和定性属性：

定量属性：Timestamp、Time、Date
定性属性：LineId、Label、Node、Type、Component、Level、Content、EventId

3.经研究分析，定量属性里的Timestamp、Time、Date虽然属于可以直接放入聚类算法里计算的数值型，但是时间数值在本次聚类任务中并无实际价值

本次聚类任务应用EvenId作为最后的评估标准，然后用除EventId以外的属性作为聚类信息。
经分析与最后评估标准有关联的属性只有Content，但是Content属性值是string类型，不能直接用于聚类，如何将其用one-hot等方法转换成向量形式而保留其内含信息是关键。

1.1.2 数据集dataset-2 HDFS

1.该数据集包含的内容是日志信息，包含的属性有：

LineId：每条记录的id号1到748093
Date：只有81109、81110和81111三种值
Time：时间戳203519到111353
Level：只有info一种值
Component：只有dfs.DataNode$DataXceiver、dfs.DataNode、dfs.FSNamesystem、dfs.DataNode$PacketResponder等值
Content：对事件的描述
EventId：事件的id，与content对应

2.将其分为定量属性和定性属性：

定量属性：Time、Date
定性属性：LineId、Level、Component、Content、EventId

3.经研究分析，定量属性里的Timestamp、Date虽然属于可以直接放入聚类算法里计算的数值型，但是时间数值在本次聚类任务中并无实际价值

本次聚类任务应该是用EvenId作为最后的评估标准，然后用除EventId以外的属性作为聚类的依据。
经分析与最后评估标准有关联的属性只有Content，但是Content属性值是string类型，不能直接用于聚类，如何将其用one-hot等方法转换成向量形式而保留其内含信息是关键。

1.1.3 数据集dataset-5 Epileptic Seizure Recognition

1.被试者共有500人，每个人的记录时间从开始到结束被分为23秒，每秒有178个数据点(可以理解成每个人头上贴了178个感应点)，每个数据点保存的是EEG记录值
该数据集包含的内容是癫痫发作识别数据，包含的属性有

X1-X178：178个数据采集点
Y：表示发作情况1表示癫痫病发作，2345表示不发作(应该化成二分类)
- 5-眼睛睁开，是指当他们记录大脑的EEG信号时，患者的眼睛是睁开的
- 4-闭眼，指患者在记录脑电图信号时闭上眼睛
- 3-记录健康大脑区域的脑电图(已知有肿瘤的大脑)
- 2-记录肿瘤所在区域的脑电图
- 1-发作

2.在数据集的说明文档中建议处理时应该化成二分类，1表示癫痫病发作，2345表示不发作。

3.关于X1.V1、X1.V1.1和X1.V1.631，X1表示都是在第一秒的数据，后面的V1或者V1.XX或者V13等都是用来识别不同人的编码(这个可能需要自己重新排序)，即以X1开头的有500个数据，而一共有23个不同的X开头代表的是记录了23秒。

4.该数据集的数据都是数值型，因此可以直接构造向量进行聚类，最后用Y的值进行评估。

1.2 数据预处理

1.数据挖掘中数据预处理的任务应该包括以下四项：

数据清理：填写空缺的值，平滑噪声数据，识别并删除孤立点，解决不一致性
数据集成：集成多个数据文件，即实体消歧，将来自不同数据源的同一实体合并
数据归约：得到数据的压缩表示，它应该小得多但是可以得到和原来数据一样或相近的结果
数据变换：规范化和聚集，数据离散化(通过概念分成和离散化来规约数据，对数字型特别重要)(算法要求输入是离散的才需要)

2.由于本次数据集已经进行了大量的预处理操作，因此该处理阶段的任务主要是：如何在使得包含的信息损失尽量小的情况下将数据转换成可以输入算法计算的数值型，需要分别对三个数据集有用数据特点进行分析。

1.2.1数据集dataset-1 BGL和数据集dataset-2 HDFS

1.有用信息为string类型，不能直接转成向量

方案一：采用one-hot编码，先遍历每个字符串，将其中出现过的词分别记录下来作为编码字典，然后重新遍历每个字符串按出现为1不出现为0的规则将其转换成one-hot向量。
- 缺点：
  - (1)忽略了类似delete和deleted同一词的不同形态之间具有的关联信息
  - (2)构建的矩阵太过稀疏，效率较低
方案二：采用word2vec先生成词向量，然后采用平均词向量的方法进一步得到每个字符串的句向量。

1.2.2数据集dataset-5 Epileptic Seizure Recognition

1.有用信息为double类型，可以直接用于聚类算法计算，标签信息遵循数据集的说明文档建议，将其分为1（发作）和2（不发作）两类。

2 算法模型和评估标准

1.本次实验采用四种不同聚类算法，其中除了报告要求的基于密度的DBSCAN算法、基于划分的K-means算法和基于层次的Cure算法，还增添了基于K-means基础上进行改进的K-means++算法
评估标准采用归一性、完整性和轮廓系数。

2.1 基于密度的DBSCAN算法

1.DBSCAN是一个比较有代表性的基于密度的聚类算法。它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。DBSCAN需要设置两个参数，分别为一个点周围临近区域的半径和临近区域内至少包含的点数。

2.首先进行DBSACN进行初始化，将半径，领域最小数据点数量传入聚类算法类，读取文件，把数据信息读入写进算法类数据集合中。

bool ClusterAnalysis1::Init(double radius, int minPTs){
    this->radius = radius;        //设置半径
    this->minPTs = minPTs;        //设置领域最小数据个数
    this->dimNum = DIME_NUM1;    //设置数据维度
    ifstream fin("dataset/dataset1_vec.csv"); //打开文件流操作
    if (! fin.is_open())                //若文件已经被打开，报错误信息
    {
        cout << "Error opening file\n";    //输出错误信息
        exit (-1);                        //程序退出
    }
    unsigned long i=0;            //数据个数统计
    string line;
    while (getline(fin, line)){   //整行读取，换行符“\n”区分，遇到文件尾标志eof终止读取
        if(i >= 1000) break; //测试用减少数据规模，如果.csv文件已经处理好可以直接去掉这一行
        istringstream sin(line); //将整行字符串line读入到字符串流istringstream中
        DataPoint1 tempDP;                //临时数据点对象
        string field;
        vector<double> tempDimData;
        while (getline(sin, field, ',')){ //将字符串流sin中的字符读入到field字符串中，以逗号为分隔符
            tempDimData.push_back(stod(field)); //将刚刚读取的字符串添加到向量fields中
        }
        
        tempDP.SetDimension(tempDimData);    //将维度信息存入数据点对象内
        tempDP.SetDpId(i);                    //将数据点对象ID设置为i
        tempDP.SetVisited(false);            //数据点对象isVisited设置为false
        tempDP.SetClusterId(-1);            //设置默认簇ID为-1
        dadaSets.push_back(tempDP);            //将对象压入数据集合容器
        i++;        //计数+1
    }
    cout << dadaSets.size() << endl;
    fin.close();
    dataNum =i;            //设置数据对象集合大小为i
    for(unsigned long k=0; k<dataNum;k++)
    {
        SetArrivalPoints(dadaSets[k]);            //计算数据点领域内对象
    }
    return true;    //返回
}

3.运行算法进行聚类操作

int ClusterAnalysis1::DoDBSCANRecursive(){
    clusterId=0;
    noise_point = 0;                        //聚类id计数，初始化为0
    for(unsigned long i=0; i<dataNum;i++)            //对每一个数据点执行
    {
        DataPoint1& dp=dadaSets[i];                    //取到第i个数据点对象
        if(!dp.isVisited() && dp.IsKey())            //若对象没被访问过，并且是核心对象执行
        {
            dp.SetClusterId(clusterId);                //设置该对象所属簇ID为clusterId
            dp.SetVisited(true);                    //设置该对象已被访问过
            KeyPointCluster(i,clusterId);            //对该对象领域内点进行聚类
            clusterId++;                            //clusterId自增1
        }
        /*if(!dp.IsKey()) {
            cout <<"噪声点"<<i<< endl;
            k++;
        }*/
    }
    for(unsigned long j=0; j<dataNum;j++)
    {
        DataPoint1& dptemp=dadaSets[j];
        if(dptemp.GetClusterId()!=-1); //cout << "数据点"<< dptemp.GetDpId()<< " 聚类ID为"<< dptemp.GetClusterId() << endl;
        else
        {
            //cout <<"噪声点"<<j<< endl;
            noise_point++;
        }
    }
    return noise_point;    //返回
}

4.对数据点领域内的数据进行DFS聚类

void ClusterAnalysis1::KeyPointCluster(unsigned long dpID, unsigned long clusterId ){
    DataPoint1& srcDp = dadaSets[dpID];        //获取数据点对象
    if(!srcDp.IsKey())    return;
    vector<unsigned long>& arrvalPoints = srcDp.GetArrivalPoints();        //获取对象领域内点ID列表
    for(unsigned long i=0; i<arrvalPoints.size(); i++)
    {
        DataPoint1& desDp = dadaSets[arrvalPoints[i]];    //获取领域内点数据点
        if(!desDp.isVisited())                            //若该对象没有被访问过执行
        {
            //cout << "数据点"<< desDp.GetDpId()<<" 聚类ID为" <<clusterId << endl;
            desDp.SetClusterId(clusterId);        //设置该对象所属簇的ID为clusterId，即将该对象吸入簇中
            desDp.SetVisited(true);                //设置该对象已被访问
            if(desDp.IsKey())                    //若该对象是核心对象
            {
                KeyPointCluster(desDp.GetDpId(),clusterId);    //递归地对该领域点数据的领域内的点执行聚类操作，采用深度优先方法
            }
        }
    }
}

2.2 基于划分的K-means算法

1.K-Means算法是无监督的聚类算法，它实现起来比较简单，聚类效果也不错，因此应用很广泛。k-means算法中的k表示聚类为k个簇，means代表取每一个聚类中数据的均值作为该簇的中心（质心）即用每一个类的质心对该簇进行描述。

2.载入文件，读取数据至K-means对象

void Kmeans::loaddata(string file_name){
    ifstream fin(file_name); //打开文件流操作
    string line;

    while (getline(fin, line))   //整行读取，换行符“\n”区分，遇到文件尾标志eof终止读取
    {
        //if(trainX.size() >= 500) break; //调整数据大小
        istringstream sin(line); //将整行字符串line读入到字符串流istringstream中
        vector<double> fields; //声明一个字符串向量
        string field;
        while (getline(sin, field, ',')) //将字符串流sin中的字符读入到field字符串中，以逗号为分隔符
        {
            fields.push_back(stod(field)); //将刚刚读取的字符串添加到向量fields中
        }
        trainX.push_back(fields);
    }
    fin.close();
}

3.输入聚类数目和最大迭代次数，进行聚类操作

vector<Cluster> Kmeans::runserver(uint k, uint maxepoches){
    const uint row_num = trainX.size();
    const uint col_num = trainX[0].size();
    kindNum = k;
    /*初始化聚类中心*/
    vector<Cluster> clusters(k);
    uint seed = (uint)time(NULL);
    for (uint i = 0; i < k; i++){
        srand(seed);
        int c = rand() % row_num;
        clusters[i].centroid = trainX[c];
        seed = rand();
    }
/*多次迭代直至收敛，本次试验迭代maxepoches次*/
    for (uint it = 0; it < maxepoches; it++)
    {
        /*每一次重新计算样本点所属类别之前，清空原来样本点信息*/
        for (uint i = 0; i < k; i++)
        {
            clusters[i].samples.clear();
        }
        /*求出每个样本点距应该属于哪一个聚类*/
        for (uint j = 0; j < row_num; j++)
        {
            /*都初始化属于第0个聚类*/
            uint c = 0;
            double min_distance = cal_distance(trainX[j],clusters[c].centroid);
            for (uint i = 1; i < k; i++)
            {
                double distance = cal_distance(trainX[j], clusters[i].centroid);
                if (distance < min_distance)
                {
                    min_distance = distance;
                    c = i;
                }
            }
            clusters[c].samples.push_back(j);
        }
        /*更新聚类中心*/
        for (uint i = 0; i < k; i++)
        {
            vector<double> val(col_num, 0.0);
            for (uint j = 0; j < clusters[i].samples.size(); j++)
            {
                uint sample = clusters[i].samples[j];
                for (uint d = 0; d < col_num; d++)
                {
                    val[d] += trainX[sample][d];
                    if (j == clusters[i].samples.size() - 1)
                        clusters[i].centroid[d] = val[d] / clusters[i].samples.size();
                }
            }
        }
    }
    clusters_out = clusters;
    return clusters;
}

2.3 基于层次的Cure算法

1.层次聚类方法是一种发展比较早、应用广泛的聚类方法，绝大多数聚类算法或者擅长处理球形和相似大小的聚类，或者在存在孤立点时变得比较脆弱。 CURE采用了一种新颖的层次聚类算法，该算法选择基于质心和基于代表对象方法之间的中间策略。它不同于单个质心或对象来代表一个类，而是选择数据空间中固定数目的具有代表性的点。一个类的代表点通过如下方式产生：首先选择类中分散的对象，然后根据一个特定的分数或收缩因子“收缩”或移动它们。在算法的每一步，有最近距离的代表点对(每个点来自于一个不同的类)的两个类被合并。每个类有多于一个的代表点使得CURE可以适应非球形的几何形状。类的收缩或凝聚可以有助于控制孤立点的影响。因此，CURE对孤立点的处理更加健壮，而且能够识别非球形和大小变化比较大的类。

2.载入数据，保存为内部数据成员格式

int Cure1::LoadPatterns(){
    ifstream fin("dataset/dataset1_vec.csv"); //打开文件流操作
    string line;
    int i = 0;
    while (getline(fin, line))   //整行读取，换行符“\n”区分，遇到文件尾标志eof终止读取
    {
        if(i >= NUMPATTERNS1) break;
        istringstream sin(line); //将整行字符串line读入到字符串流istringstream中
        string field;
        int j = 0;
        while (getline(sin, field, ',')) //将字符串流sin中的字符读入到field字符串中，以逗号为分隔符
        {
            Pattern[i][j] = stod(field); //将刚刚读取的字符串添加到向量fields中
            j++;
        }
       i++;
    }
    data_cluster = vector<int> (Pattern.size());
    fin.close();
    return SUCCESS;
}

3.运行聚类主操作

void Cure1::RunCure1(){
    int k,u,v;
    ClustNode1 *w;
    BuildClustList();//找到每个点最近的点
    k=NUMPATTERNS1;//初始簇的个数为实验的个数
    for(; k > NUMCLUSTERS1; k--){
        u=MinClust(); //找出簇中相邻最近的两个簇
        v=p[u]->closet;
        w=Merge(p[u],p[v]);//将两个簇合并 成一个新的簇
        delete p[u];delete p[v];//删除原先的两个簇
        p[u]=w;   //将u,v移除
        p[v]=NULL;
        updateMinDist(u,v); //更新所有点最近距离
    }
}

创建新的簇，簇结构体定义如下

struct ClustNode1 {
    vector<int>          Member = vector<int> (NUMPATTERNS1);  //类中的数据项
    int          NumMembers;//表示类中数据点的个数
    double       Means[SIZEVECTOR1];  //均值点
    double       Pre[NUMPRE1][SIZEVECTOR1];//代表点
    int          PreMember[NUMPRE1];//作为代表点的数据项
    int          closet;  //最近的簇
    double       MinDist;//与最近的簇之间的距离
};

找到与每个点相距最近的点

void  Cure1::BuildClustList(){
    int i,j;
    for(i=0; i < NUMPATTERNS1; i++){
        p[i]=new ClustNode1;//创建新的簇类节点
        p[i]->NumMembers=1;//簇中成员个数
        p[i]->Member[0]=i;//成员
        p[i]->PreMember[0]=i;//簇的代表点
        for(j=0; j < SIZEVECTOR1; j++){
            p[i]->Means[j]=Pattern[i][j];//均值
        }
        for(j=0; j < SIZEVECTOR1; j++){
            p[i]->Pre[0][j]=Pattern[i][j]+ (SHRINK1) * (p[i]->Means[j] - Pattern[i][j]);//计算代表点
        }
    }
    updateMinDist();//更新各个簇之间的距离
}

找出簇间距离最小的两个簇

int Cure1::MinClust(){
    int i,Index;
    double MinDist=9.9e+99;
    for(i=0; i < NUMPATTERNS1; i++){
        //如果簇已被合并，则为空
        if(p[i]==NULL)
            continue;
        //判断是否为距离最小的簇
        if(p[i]->MinDist<MinDist){
            MinDist=p[i]->MinDist;
            Index=i;
        }
    }
    //返回这个簇的下标
    return Index;
}

合并两个簇

ClustNode1 * Cure1::Merge(ClustNode1 *u, ClustNode1 *v){
    int i,j,MaxPoint;
    double MaxDist,dist;
    //由两个簇生成一个新的簇
    ClustNode1 *w = createNode(u, v);
    if(w->NumMembers <= NUMPRE1){
        //如果簇中的成员点的数量不大于代表点的数量
        for(i=0;i<w->NumMembers;i++){
            w->PreMember[i]=w->Member[i]; //成员点即为代表点
        }
    }else{
        //簇中成员点多于代表点，则重新计算代表点
        bool checkUsed[w->NumMembers];
        memset(checkUsed,false,w->NumMembers);
        for(i=0; i < NUMPRE1; i++){
            MaxDist=0;
            for(j=0;j<w->NumMembers;j++){
                int temple_size = Pattern[w->Member[j]].size();
                double temple[temple_size];
                for(int temple_i = 0; temple_i < Pattern[w->Member[j]].size(); temple_i++) temple[temple_i] = Pattern[w->Member[j]][temple_i];
                if(i==0){
                    //第一个代表点为距离中值最远的点
                    //dist=EucNorm(w->Means,Pattern[w->Member[j]]);//计算欧氏距离
                    dist=EucNorm(w->Means, temple);//计算欧氏距离
                }else{
                    //剩余的代表点为距离前一个代表点最远的点
                    if(checkUsed[j])//防止代表点重复
                        continue;
                    //计算欧氏距离
                    //dist=EucNorm(w->Pre[i-1],Pattern[w->Member[j]]);
                    dist=EucNorm(w->Pre[i-1],temple);
                }
                //选择距离前一个代表点最远的点为新的代表点
                if(dist>=MaxDist){
                    MaxDist=dist;
                    MaxPoint=j;
                    //设置选择标记
                    checkUsed[j] = true;
                }
            }
            //设置新的代表点
            w->PreMember[i] = MaxPoint;
        }
    }
    //收缩代表点
    SHRINK2Pre(w);
    //返回代表点
    return w;
}

更新所有点的最近点信息

void Cure1::updateMinDist(const int w, const int v){
    double MinDist,d;
    p[w]->closet = 0;
    p[w]->MinDist = 9.9e+99;
    for(int i=0; i < NUMPATTERNS1; i++){
        if(NULL == p[i] || w == i)
            continue;
        if(v == p[i]->closet || w == p[i]->closet)
        {
            p[i]->MinDist=9.9e+99;
            //遍历所有的簇，计算他们的距离
            for(int j=0; j < NUMPATTERNS1; j++){
                //如果这个簇已经被合并，则跳过。
                if(p[j]==NULL)
                    continue;
                    //如果这个簇是自身，也跳过
                else if(i==j)
                    continue;
                else{
                    //计算簇之间的距离
                    d=dist(p[i],p[j]);
                    //更新最近的簇和距离
                    //if(d < p[i]->MinDist && p[i]->NumMembers + p[j]->NumMembers < NUMPATTERNS1/2 )
                    //if(d < p[i]->MinDist  && p[i]->NumMembers + p[j]->NumMembers < 75 )
                    if(d < p[i]->MinDist)
                    {
                        p[i]->closet=j;
                        p[i]->MinDist=d;
                    }
                }
            }
        }
        double temp = dist(p[i],p[w]);
        //	if( temp < p[w]->MinDist && p[i]->NumMembers + p[w]->NumMembers < NUMPATTERNS1/2)
        //	if( temp < p[w]->MinDist && p[i]->NumMembers + p[w]->NumMembers < 75)
        if( temp < p[w]->MinDist)
        {
            p[w]->closet = i;
            p[w]->MinDist = temp;
        }
    }
}

2.4 基于划分的K-means++算法

1.K-means算法是采用最开始随机选取数据集中K个点作为聚类中心，而K-means++按照如下的思想选取K个聚类中心：核心思想是聚类中心互相离得越远越好，这个改进非常有效，既减少了结果收敛前的迭代次数，更提供了聚类质量。

假设已经选取了n个初始聚类中心(0<n<K)，则在选取第n+1个聚类中心时：距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心
第一个聚类中心(n=1)时，同K-means一样样使用随机的方法

2.获取数据集中保存的数据

void KMeans_plus1<Real, Dim1>::dataGenerator(string file_name, Real radius, vector<KmPoint1> &pts){
    ifstream fin(file_name); //打开文件流操作
    string line;
    int i = 0;
    while (getline(fin, line))   //整行读取，换行符“\n”区分，遇到文件尾标志eof终止读取
    {
        //if(i >= 2000) break;
        istringstream sin(line); //将整行字符串line读入到字符串流istringstream中
        string field;
        int j = 0;
        KmPoint1 p;
        vector<double> temple;
        while (getline(sin, field, ',')) //将字符串流sin中的字符读入到field字符串中，以逗号为分隔符
        {
            p[j] = stod(field); //将刚刚读取的字符串添加到向量fields中
            temple.push_back(p[j]);
            j++;
        }
        i++;
        data_content.push_back(temple);
        pts.push_back(p);
    }
    data_cluster = vector<int> (pts.size());
    fin.close();
}

保存数据的类KmPoint定义在.h文件中

class KM_API KMeans_plus1{
public:
    typedef KmPoint1<Real, Dim1> KmPoint1;
public:
    vector<int> data_cluster;
    vector<vector<double>> data_content;
    KMeans_plus1(){ srand((unsigned)time(0)); }
    Real randf(Real m){
        return m * rand() / (RAND_MAX - 1.);
    }

    Real dist(KmPoint1 &a, KmPoint1 &b){
        Real len = 0;
        for(int i = 0; i < Dim1; ++i){
            len += (a[i] - b[i]) * (a[i] - b[i]);
        }
        return len;
    }
    
    void dataGenerator(string filename, Real radius, vector<KmPoint1> &pts);
    int nearest(KmPoint1 &pt, vector<KmPoint1> &cents, Real &d);
    void kpp(vector<KmPoint1> &pts, vector<KmPoint1> &cents);
    void kmcluster(vector<KmPoint1> &pts, int k, vector<KmPoint1> &outCents, vector<vector<KmPoint1>> &outPts);
    void serialize(vector<vector<KmPoint1>> &outPts);
};

3.进行聚类操作

void KMeans_plus1<Real, Dim1>::kmcluster(vector<KmPoint1> &pts, int k, vector<KmPoint1> &outCents, vector<vector<KmPoint1>> &outPts){
    if(outCents.size() <= 0)
        outCents.resize(k);
    if(outPts.size() <= 0)
        outPts.resize(k);
    kpp(pts, outCents);
    int changed;
    do{
        for(int i = 0; i < (int)outCents.size(); ++i){
            for(int j = 0; j < Dim1; ++j)
                outCents[i][j] = 0;
            outCents[i].setId(0);
        }
        vector<int> cnt(k, 0);
        for(int i = 0; i < (int)pts.size(); ++i){
            int k = pts[i].id();
            for(int j = 0; j < Dim1; ++j)
                outCents[k][j] += pts[i][j];
            cnt[k]++;
        }
        for(int i = 0; i < (int)outCents.size(); ++i){
            for(int j = 0; j < Dim1; ++j)
                outCents[i][j] /= cnt[i];
        }
        changed = 0;
        for(int i = 0; i < (int)pts.size(); ++i){
            int min_i = nearest(pts[i], outCents, *(new Real));
            if(min_i != pts[i].id()){
                changed++;
                pts[i].setId(min_i);
            }
        }
    }while(changed > 0.001 * pts.size());
    for(int i = 0; i < (int)outCents.size(); ++i)
        outCents[i].setId(i);
    for(int i = 0; i < (int)pts.size(); ++i) {
        data_cluster[i] = pts[i].id();
        outPts[pts[i].id()].push_back(pts[i]);
    }
}

选取簇间距离最远的作为簇初始化依据

void KMeans_plus1<Real, Dim1>::kpp(vector<KmPoint1> &pts, vector<KmPoint1> &cents){
    Real sum = 0;
    vector<Real> d;
    d.resize(pts.size());
    cents[0] = pts[rand() % pts.size()];
    vector<KmPoint1> tmpCents;
    tmpCents.push_back(cents[0]);
    for(int k = 1; k < (int)cents.size(); ++k){
        sum = 0;
        for(int i = 0; i < (int)pts.size(); ++i){
            nearest(pts[i], tmpCents, d[i]);
            sum += d[i];
        }
        sum = randf(sum);
        for(int i = 0; i < (int)pts.size(); ++i){
            if((sum -= d[i]) > 0)	continue;
            cents[k] = pts[i];
            tmpCents.push_back(cents[k]);
            break;
        }
    }
    for(int i = 0; i < (int)pts.size(); ++i){
        int id = nearest(pts[i], cents, *(new Real));
        pts[i].setId(id);
    }
}

找距离最近的点的调用函数

int KMeans_plus1<Real, Dim1>::nearest(KmPoint1 &pt, vector<KmPoint1> &cents, Real &d){
    int i, min_i;
    Real d1, min_d;
    min_d = HUGE_VAL;
    min_i = pt.id();
    for(i = 0; i < (int)cents.size(); ++i){
        KmPoint1 c = cents[i];
        if(min_d > (d1 = dist(c, pt))){
            min_d = d1;
            min_i = i;
        }
    }
    d = min_d;
    return min_i;
}

2.5 评估指标

2.5.1 归一性和完整性

1.聚类性能度量亦称有效性指标，分为：

外部指标，聚类完成后将聚类结果与某个参考模型进行比较，是基于预先指定的结构评判聚类算法结果，这种结构反映了人们对数据结构的直观认识或先验知识。
内部指标，直接考察聚类结果而不利用任何参考模型。

2.由于本次实验采用的三个数据集都有确定的标签，因此本次聚类评估采用外部指标中的归一性和完整性来进行评估：

均一性（Homogeneity）指每个簇中只包含单个类别的样本。如果一个簇中的类别只有一个，则均一性为1；如果有多个类别，计算该类别下的簇的条件经验熵H(C|K)，值越大则均一性越小。
完整性（Completeness）指同类别样本被归类到相同的簇中。如果同类样本全部被分在同一个簇中，则完整性为1；如果同类样本被分到不同簇中，计算条件经验熵H(K|C)，值越大则完整性越小。
单独考虑均一性或完整性都是片面的，因此引入两个指标的加权平均V-measure。如果β>1则更注重完整性，如果β<1则更注重均一性。

2.5.2 轮廓系数

1.轮廓系数的计算并不依赖于数据集的真实标签，其取值范围为[-1, 1]，值越大，表示聚类的效果越好。轮廓系数旨在将某个对象与自己的簇的相似程度和与其他簇的相似程度作比较，值最高的簇的数量表示簇的数量的最佳选择。该系数综合考虑了内聚度和分离度两种因素。为了度量聚类的质量，我们可以使用数据集中所有对象的轮廓系数的平均值。

读取每个数据点的id、对应的类id和该数据点的维度信息

bool Silhouette::addClusterData(int _cluster_index, double* _data,int _data_index)
{
    vector<double> temp(_data,_data+dim);
    index_cluster[_cluster_index].push_back(_data_index);
    o_clustor[_cluster_index].push_back(temp);
    return true;
}

计算分别计算轮廓系数并统合

double Silhouette::calSilhouette(){
    double tempSo = 0;
    for(int i = 0; i < cluster_num ; i++)
    {
        int count = o_clustor[i].size();

        for(int j = 0;j < count;j++)
        {
            double tempAo = 0;
            //对象o到自身簇内的平均距离a(o)
            for(int k = 0; k < count ;k++)
            {
                if(j == k)
                    continue;
                tempAo += dist(o_clustor[i][j],o_clustor[i][k]);
            }
            if(count > 1)
                tempAo = tempAo / (count - 1);
                
            double min = 9.9e+99;
            //对象o到不属于o的簇的最小平均距离b(o)
            for(int ii = 0; ii < cluster_num ; ii++)
            {
                if(i == ii) continue;
                int icount = o_clustor[ii].size();
                double tempBo = 0;
                for(int k = 0; k < icount ;k++)
                {
                    tempBo += dist(o_clustor[i][j],o_clustor[ii][k]);
                }
                tempBo = tempBo / icount;
                if(tempBo < min)
                {
                    min = tempBo;
                }
            }
            tempSo += (min - tempAo) / (tempAo > min ? tempAo : min);
        }
    }
    return tempSo/size;
}

3 实验

给出算法实现的源代码，对于每部分所实现的功能给出详细注释

3.1实验环境

1.设备规格：Intel(R) Core(TM) i7-10700K CPU @ 3.80GHz 3.79 GHz处理器16.0 GB内存64位操作系统

2.编程语言：C++（实现聚类算法）、Python(批量处理数据)

3.编译器：CLion 2021、Pycharm 2021

3.2数据集规模设置

1.数据集dataset-1 BGL：原数据集具有658923条数据，经测试即使忽略信息损失将句向量维度降到4维在运行聚类算法时也会出现内存不足导致程序崩溃等错误，并且考虑到句向量维数过低会出现隐藏信息损失而导致聚类效果较差，本次实验随机抽取其中5000条数据并取句向量维度为128进行实验。

2.数据集dataset-2 HDFS：同数据集dataset-1 BGL一样，原数据集具有748093条数据，经测试即使忽略信息损失将句向量维度降到4维在运行聚类算法时也会出现内存不足导致程序崩溃等错误，并且考虑到句向量维数过低会出现隐藏信息损失而导致聚类效果较差，本次实验同样随机抽取其中5000条数据并取句向量维度为128进行实验。

3.数据集dataset-5 Epileptic Seizure Recognition：经测试该数据集因为维度178仍然存在着在基于层次的聚类算法Crue和基于密度的聚类算法DBSCAN中运行时间过长、内存不足等问题，因此做随机抽样处理，随机抽取2000条数据进行实验。

3.3数据集dataset-1 BGL：

3.3.1 基于密度的DBSCAN

1.DBSCAN聚类区别于其他三种聚类算法，它事先并没有规定最终要聚类的类别个数，而是通过调整邻近区域半径和区域内包含点数的值来自发聚类，并将过于偏离聚类中心的点划分为噪声点，将其忽略。多次调整参数，在dataset-1 BGL数据集上的实验结果如下：

邻域半径	0.5	2	5	8
噪声值	461	102	42	29
聚类个数	91	87	70	43
归一性	0.0769	0.0919	0.0856	0
完整性	0.1559	0.1596	0.1596	0.1596
轮廓系数	0.4498	0.803432	0.7911	0.7721
运行时间	3.186s	3.168s	3.216s	3.196s

2.由此可知随着实验设定的邻近区域半径的增加聚类个数和噪声值属递减趋势，经事先统计本次随机抽样得到的dataset-1 BGL样本集实际具有109个不同标签，但如果设定领域半径过小的而驱使聚类数量接近109是会将大部分数据点识别为噪声，并不可取。经归一性完整性和簇间不相似度指标轮廓系数的值变化可以得，当领域半径取5时，聚类结果最好。由本次实验也可看出，DBSCAN在对孤立点进行聚类识别时效果不好，往往会直接将其直接视为噪声忽略，因此在已经经过噪声处理的数据集中，不太适合采用该算法进行聚类。

3.3.2 基于划分的K-means

1.经事先统计本次随机抽样得到的dataset-1 BGL样本集实际具有109个不同标签，因此理论上应将K值的最佳选取应该也为109，但考虑到标签不同的类也有可能相似度较高，因此增加了K值为50和200的对比实验，同时为比较最大迭代次数对运行时间和聚类效果的影响，设置了50、100、1000多个对比实验。

K值	50	109	109	109	200
迭代次数	100	50	100	1000	100
归一性	0.5800	0.7615	0.8257	0.8165	0.8600
完整性	0.1560	0.1560	0.1560	0.1560	0.1560
轮廓系数	0.3420	0.3676	0.3835	0.3939	0.4457
运行时间	84.266s	91.953s	185.552s	1843.540s	338.168s

2.由此可知，在本次实验的dataset-1 BGL样本集上K值选取109能取得更好结果，值得一提的是，由于K值与实际标签类别数量相同可以看出归一性指标非常高，但与之相对的完整性指标则不太理想，而轮廓系数不算特别好的原因来自于日志数据集本身的标签设置上，因为往往会出现实际上两个数据非常相似，在聚类向量空间中的距离非常接近，但它们的标签不同由此理论上它俩应该被分成不同的类，这就导致了这样聚出来的类的簇间距离非常接近从而导致轮廓系数不够理想，由此也能看出轮廓系数仅能表示聚类结果内部的理想程度，而与外部标签无关，甚至在数据集具有标签的情况下，轮廓系数还会与综合聚类效果指标背道而驰。

3.而迭代次数过高固然能获得较为理想的聚类结果，但是运行时间也呈正比增长，开销过大而结果相较提升过小，因此本次实验也不考虑使用1000次迭代作为实验结果，而采用100次迭代既能保证一定聚类质量，又能将运行时间控制在可接受范围内。而将K值设置为200时，从指标上看要优于109，但实际上在200个类里具有多个不含任何数据点的空簇，且运行时间几乎是K=109时的两倍，因此K值最优选择仍是109。

3.3.3 基于层次的Cure

1.本次实验使用的Cure算法采用收缩率作为调整参数来进行对比实验，为增加说服性同样设置聚类个数为50、109、200的对比实验。

聚类个数	50	109	109	109	200
收缩率	1	0.5	1	2	1
归一性	0.6800	0.9817	0.8624	0.6973	0.9800
完整性	0.1560	0.1560	0.1560	0.1560	0.1560
轮廓系数	0.4993	-0.3834	0.7951	0	0.7609
运行时间	105.099s	111.95s	108.563s	99.402s	104.288s

2.可以看出随着收缩率的减小归一性指标有显著提升，但轮廓系数快速下降表明簇间距离非常接近，聚类效果不够好。而聚类个数采用50和实际标签数109得到的结果比不上采用200得到的结果，综上所述采用200作为聚类个数、收缩率采用1时Cure聚类效果最好。

3.3.4 基于划分的K-means++

1.同K-means一样，K-meas++算法的K值理论上也应选取应该也为109，但考虑到标签不同的类也有可能相似度较高，因此增加了K值为50和200的对比实验。

K值	50	109	200
归一性	0.4600	0.7315	0.9200
完整性	0.1560	0.1560	0.1560
轮廓系数	0.4798	0.5128	0.5300
运行时间	10.109s	46.277s	133.492s

1.由此可知，在本次实验的dataset-1 BGL样本集上K-meas++的K值同样是选取109能取得更好结果。K-means++具有和K-means相同的问题：迭代次数过高的话运行时间会显著增加，而导致开销过大而结果相较提升过小，由于之前已在K-means上进行过类似实验，这里就不再赘述，最终要求实验既能保证一定聚类质量，又能将运行时间控制在可接受范围内，而K值选择过大也会大大增加运行时间。

2.可以看出相比K-means而言，K-means++的运行时间大幅降低，因为在选取新的聚类中心时以远处为初始化比起随机初始化更能贴近最后迭代收敛的结果，在实际运行时大大减少了时间复杂度。

3.3.5 不同算法实验结果对比

算法	DBSCAN	K-means	Cure	K-means++
归一性	0.0856	0.8257	0.9800	0.7315
完整性	0.1596	0.1560	0.1560	0.1560
轮廓系数	0.7911	0.3835	0.7609	0.5128
运行时间	3.216s	185.552s	104.288s	46.277s

1.经上述对比可知DBSCAN在本次实验的dataset-1 BGL样本集上能取得最佳结果，不仅时间最短、轮廓系数也最高，但DBSCAN的致命缺点在于它剔除了一些噪声点以及不能设置理想的聚类个数，而其他算法则克服了这一缺点，其余三个算法中时间开销最小K-means++、聚类质量最高Cure。

3.4数据集dataset-2 HDFS：

3.4.1 基于密度的DBSCAN

1.DBSCAN聚类区别于其他三种聚类算法，它事先并没有规定最终要聚类的类别个数，而是通过调整邻近区域半径和区域内包含点数的值来自发聚类，并将过于偏离聚类中心的点划分为噪声点，将其忽略。多次调整参数，在dataset-2 HDFS数据集上的实验结果如下：

邻域半径	0.5	2	5	8
噪声值	339	31	1	0
聚类个数	720	33	15	13
归一性	1	1	1	0.8462
完整性	0.0625	0.0625	0.0625	0.0625
轮廓系数	0.8691	0.8040	0.8593	0.8792
运行时间	74.854s	75.651s	74.809s	74.796s

2.由此可知随着实验设定的邻近区域半径的增加聚类个数和噪声值属递减趋势，经事先统计本次随机抽样得到的dataset-2 HDFS样本集实际具有16个不同标签，在考虑到归一性完整性和簇间不相似度指标轮廓系数的值变化可以得，当领域半径取5时，聚类结果最好。由本次实验也可看出，DBSCAN在对孤立点进行聚类识别时效果不好，往往会直接将其直接视为噪声忽略，因此在已经经过噪声处理的数据集中，不太适合采用该算法进行聚类。

3.4.2 基于划分的K-means

1.经事先统计本次随机抽样得到的dataset-2 HDFS样本集实际具有16个不同标签，因此理论上应将K值的最佳选取应该也为16，但考虑到标签不同的类也有可能相似度较高，因此增加了K值为5和30的对比实验，同时为比较最大迭代次数对运行时间和聚类效果的影响，设置了50、100、1000多个对比实验。

K值	5	16	16	16	30
迭代次数	100	50	100	1000	100
归一性	0.4000	0.6875	0.6250	0.6875	0.9000
完整性	0.0625	0.0625	0.0625	0.0625	0.0625
轮廓系数	0.3998	0.4896	0.4151	0.5261	0.2651
运行时间	9.507s	14.227s	27.928s	273.205s	51.183s

2.由此可知，在本次实验的dataset-2 HDFS样本集上K值选取16能取得更好结果，值得一提的是，当K值取30时归一性指标非常高，但轮廓系数则不太理想。

3.而迭代次数过高固然能获得较为理想的聚类结果，但是运行时间也呈正比增长，开销过大而结果相较提升过小，因此本次实验也不考虑使用1000次迭代作为实验结果，而采用100次迭代既能保证一定聚类质量，又能将运行时间控制在可接受范围内。

3.4.3 基于层次的Cure

1.本次实验使用的Cure算法采用收缩率作为调整参数来进行对比实验，为增加说服性同样设置聚类个数为5、16、30的对比实验。

聚类个数	5	16	16	16	30
收缩率	1	0.5	1	2	1
归一性	0.400	0.9375	1	0.8125	1
完整性	0.0625	0.0625	0.0625	0.0625	0.0625
轮廓系数	0.5153	-0.3654	0.8570	0.7282	0.8534
运行时间	139.748s	43.631s	138.508s	55.534s	138.166s

2.可以看出随着收缩率的减小归一性指标有显著提升，但轮廓系数快速下降表明簇间距离非常接近，聚类效果不够好。而聚类个数采用5和30得到的结果比不上采用实际标签数16得到的结果，综上所述采用16作为聚类个数、收缩率采用1时Cure聚类效果最好。

3.4.4 基于划分的K-means++

1.同K-means一样，K-meas++算法的K值理论上也应选取应该也为16，但考虑到标签不同的类也有可能相似度较高，因此增加了K值为5和30的对比实验。

K值	5	16	30
归一性	0.4000	0.8125	0.9667
完整性	0.0625	0.0625	0.0625
轮廓系数	0.6161	0.7329	0.4157
运行时间	0.77s	1.811s	4.926s

2.由此可知，在本次实验的dataset-2 HDFS样本集上K-meas++的K值同样是选取16能取得更好结果。K-means++具有和K-means相同的问题：迭代次数过高的话运行时间会显著增加，而导致开销过大而结果相较提升过小，由于之前已在K-means上进行过类似实验，这里就不再赘述，最终要求实验既能保证一定聚类质量，又能将运行时间控制在可接受范围内，而K值选择过大也会大大增加运行时间。

3.可以看出相比K-means而言，K-means++的运行时间大幅降低，因为在选取新的聚类中心时以远处为初始化比起随机初始化更能贴近最后迭代收敛的结果，在实际运行时大大减少了时间复杂度。

3.4.5 不同算法实验结果对比

算法	DBSCAN	K-means	Cure	K-means++
归一性	1	0.6250	1	0.8125
完整性	0.0625	0.0625	0.0625	0.0625
轮廓系数	0.8593	0.4151	0.8570	0.7329
运行时间	74.809s	27.928s	138.508s	1.811s

1.经上述对比可知K-means++在本次实验的dataset-2 HDFS样本集上能取得最佳结果，不仅时间最短、轮廓系数和归一性也较高，除此之外DBSCAN和Cure的聚类结果也较理想，而K-means虽然时间开销很小，但是聚类质量明显比不上其他三者。

3.5数据集dataset-5 Epileptic Seizure Recognition：

值得一提的是由于数据集的标签经处理后只有1（发作）和2（不发作），因此完整性在四个算法中都会很差，因此不列入考虑范围。

3.5.1 基于密度的DBSCAN

1.DBSCAN聚类区别于其他三种聚类算法，它事先并没有规定最终要聚类的类别个数，而是通过调整邻近区域半径和区域内包含点数的值来自发聚类，并将过于偏离聚类中心的点划分为噪声点，将其忽略。多次调整参数，在dataset-5 Epileptic Seizure Recognition数据集上的实验结果如下：

邻域半径	500	700	900	1100	1300	1500
噪声值	1285	739	504	424	370	327
聚类个数	19	10	5	4	4	6
归一性	0.5263	0.7000	0.8000	0.7500	0.2500	0.500
轮廓系数	-0.0091	0.0876	0.1606	0.3165	0.3895	0.3875
运行时间	15.647s	15.936s	15.758s	15.762s	15.838s	15.744s

2.由此可知随着实验设定的邻近区域半径的增加聚类个数和噪声值大体上属递减趋势，经事先统计本次随机抽样得到的dataset-5 Epileptic Seizure Recognition样本集实际具有2个不同标签，在考虑到归一性完整性和簇间不相似度指标轮廓系数的值变化可以得，当领域半径取1100时，聚类结果最好。由本次实验也可看出，DBSCAN在对孤立点进行聚类识别时效果不好，往往会直接将其直接视为噪声忽略，因此在已经经过噪声处理的数据集中，不太适合采用该算法进行聚类。

3.5.2 基于划分的K-means

1.经事先统计本次随机抽样得到的dataset-5 Epileptic Seizure Recognition样本集实际具有2个不同标签，因此理论上应将K值的最佳选取应该也为2，但考虑到标签不同的类也有可能相似度较高，因此增加了K值为1和5的对比实验，同时为比较最大迭代次数对运行时间和聚类效果的影响，设置了50、100、1000多个对比实验。

K值	1	2	2	2	5
迭代次数	100	50	100	1000	100
归一性	0	0	0	0	0.2000
轮廓系数	1	0.0663	0.0891	0.06079	0.0898
运行时间	1.292s	1.148s	2.09s	20.108s	4.727s

2.由此可知，在本次实验的dataset-5 Epileptic Seizure Recognition样本集上K值选取2和5能取得更好结果，但轮廓系数都不太不太理想。值得一提的是，归一性指标在分类次数多时会提高，而完整性在分类次数较小时、一个类含较多数据时明显不理想。而当K为1时，所有的点都被包含在该类中，归一性自然为1，完整性自然为0，不具有参考意义。

4.经过实验发现，k-means方法在该数据集上的聚类效果较差。

3.5.3 基于层次的Cure

1.本次实验使用的Cure算法采用收缩率作为调整参数来进行对比实验，为增加说服性同样设置聚类个数为1、2、5的对比实验。

聚类个数	1	2	2	2	5
收缩率	1	0.5	1	2	1
归一性	0	0.5000	0.5000	0.5000	0.8000
轮廓系数	1	0.7652	0.7652	0.7652	0.7492
运行时间	68.925s	20.04s	67.635s	21.319s	67.362s

2.可以看出Cure算法在该数据集上的表明显优于DBSCAN和K-means，轮廓系数能达到0.76更说明其聚类效果的优秀，综上结果采用2作为聚类个数时，收缩率的设置不同对聚类结果的影响基本可以忽略不计，唯一影响就是采用1时Cure聚类会比采用0.5和2时花费更多时间。

3.5.4 基于划分的K-means++

1.同K-means一样，K-meas++算法的K值理论上也应选取应该也为16，但考虑到标签不同的类也有可能相似度较高，因此增加了K值为1和5的对比实验。

K值	1	2	5
归一性	0	0	0.6000
轮廓系数	1	0.0586	0.6286
运行时间	0.121s	0.48s	0.0295s

2.由此可知，在本次实验的dataset-5 Epileptic Seizure Recognition样本集上K-meas++的K值同样是选取16能取得更好结果。K-means++具有和K-means相同的问题：迭代次数过高的话运行时间会显著增加，而导致开销过大而结果相较提升过小，由于之前已在K-means上进行过类似实验，这里就不再赘述，最终要求实验既能保证一定聚类质量，又能将运行时间控制在可接受范围内，而K值选择过大也会大大增加运行时间。

3.5.5 不同算法实验结果对比

算法	DBSCAN	K-means	Cure	K-means++
归一性	0.7500	0.2000	0.5000	0.6000
轮廓系数	0.3165	0.0898	0.7652	0.6286
运行时间	15.762s	4.727s	20.04s	0.0295s

1.经上述对比可知Cure和Kmeans++在本次实验的dataset-5 Epileptic Seizure Recognition样本集上能取得较好结果，不仅时间最短、轮廓系数也较高。

2.值得注意的是在该数据集上，四个算法的表现都不够好聚类质量明显较差，推测可能是数据本身聚类属性不佳和标签只有两类导致聚类个数较少不适合这几种算法计算。

4 总结

1.本次聚类任务有三个数据集分别是具有658923条记录的日志数据集dataset-1 BGL：原数据集具有658923条数据、具有748093条记录的日志数据集dataset-2 HDFS和具有11500条记录的癫痫发作数据集dataset-5 Epileptic Seizure Recognition。三个数据集都是已经经过一定预处理操作后的结果，不需要我们再进行填写空缺的值、平滑噪声数据、识别并删除孤立点、解决不一致性、实体消歧等一系列操作。

2.在聚类实验中通过多次调整参数发现：

算法的时间开销很大程度也取决于聚类对象自身具有的信息，例如dataset1和dataset2在本次实验中数据规模和数据维度都一样，但执行DBSCAN算法时dataset2花了近100s，而dataset1只用了5s左右，而当执行K-means和K-means++算法时该情况又反了过来，dataset2的执行时间明显比dataset1更短。因此在以后执行聚类任务中，根据数据集本身数据的特点来选择不同的数据集可以极大地减少程序开销。
通过对dataset3的聚类结果分析可知，四个算法在其上的聚类效果都不理想，推测是由于dataset3自身的数据聚类特征不明显和聚类个数太少导致。
经对比发现dataset-2 HDFS在四种算法上得到的聚类结果都较为优秀，且时间开销也较小也侧面说明了在算法执行时迭代次数较少，可以得出该数据集具有很好的聚类特征的结论。
因为dataset1和dataset2都需要使用Word2Vec将字符串转换成句向量，在聚类过程中发现如果句向量的维度低于16的话聚类效果会显著降低，由此可以推断出Word2Vec将字符串转换成句向量的过程中输出的数据维度越低其内包含的信息损失越严重，低于16维时会损失用于聚类判断的重要信息。但是维度过高又会带来时间开销剧增的现象，因此在以后进行类似的转换时需权衡好时间开销和数据信息损失。

3.本次聚类实验在最后评测方面还有值得改进的地方，例如归一性和完整性的评测函数实现过于简单，后续可以加入条件经验熵和加权系数的实现部分。

目录

1 数据认知及预处理

1.1 数据认知

1.1.1 数据集dataset-1 BGL