机器学习_分类_KNN_EM

K最近邻(kNN,k-NearestNeighbor)分类算法

在KNN中,通过计算对象间距离来作为各个对象之间的非相似性指标,避免了对象之间的匹配问题,在这里距离一般使用欧氏距离或曼哈顿距离:

步骤:
其算法的描述为:

1)计算测试数据与各个训练数据之间的距离;

2)按照距离的递增关系进行排序;

3)选取距离最小的K个点;

4)确定前K个点所在类别的出现频率;

5)返回前K个点中出现频率最高的类别作为测试数据的预测分类。

KNN算法的优点:

1)简单、有效。 
2)重新训练的代价较低(类别体系的变化和训练集的变化,在Web环境和电子商务应用中是很常见的)。 
3)计算时间和空间线性于训练集的规模(在一些场合不算太大)。 
4)由于KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。 
5)该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分。

KNN算法缺点:

1)KNN算法是懒散学习方法(lazy learning,基本上不学习),一些积极学习的算法要快很多。 
2)类别评分不是规格化的(不像概率评分)。 
3)输出的可解释性不强,例如决策树的可解释性较强。 
4)该算法在分类时有个主要的不足是,当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本,某一类的样本数量很大,那么或者这类样本并不接近目标样本,或者这类样本很靠近目标样本。无论怎样,数量并不能影响运行结果。可以采用权值的方法(和该样本距离小的邻居权值大)来改进。 
5)计算量较大。目前常用的解决方法是事先对已知样本点进行剪辑,事先去除对分类作用不大的样本。

EM算法

EM的策略就是先随便给一个条件概率p1(x1|thera),然后找到一个l(thera)的下界函数r(x1|thera),求r的最大值p2(x2|thera),再找到经过p2点的下界函数r2(x2|thera),重复该过程直到收敛到局部最大值。

灰度图分割:参考

point.h文件

#ifndef POINT_H
#define POINT_H
//point结构主要用来存储图像中节点的横坐标,纵坐标以及灰度值
struct point
{
    int row;
    int col;
    double pixVal;
    point(int row, int col, double pixVal) :row(row),col(col),pixVal(pixVal) {}
};
#endif

keams.h头文件:

#ifndef KMEANS_H
#define KMEANS_H

#include<opencv2\opencv.hpp>
#include<random>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#include<list>
#include<iostream>
#include<math.h>
#include"point.h"

using namespace cv;
using namespace std;

class Kmeans{
private:
    //存储所有点
    vector<point> points;
    //存储簇的中心点
    vector<point> centers;
    //存储每个点到相应的簇
    vector<point>* clusters;
    //向量的维数
    int dimension;
    //簇的个数
    int k;
public:
    //构造函数
    Kmeans(vector<point> points, vector<point> centers, int k, int dimension)
    {
        this->points = points;
        this->centers = centers;
        this->dimension = dimension;
        this->k = k;
        clusters = new vector<point>[k];
    }

    //析构函数
    ~Kmeans()
    {
        delete clusters;
    }

    //获取簇
    vector<point>* getClusters()
    {
        return this->clusters;
    }

    //计算两个向量之间的欧式距离
    double getDistanceBetweenTwoPoints(const point& point1, const point& point2)
    {
        double sum = 0;
        //double tmp;
        //for (int i = 0; i < dimension; i++)
        //{
        //tmp = pow(point1.pixVal - point2.pixVal,2);
        //sum += tmp;
        //}
        sum = pow(point1.pixVal - point2.pixVal, 2);
        return sqrt(sum);
    }

    //计算每个点到离它最近的簇中心点,结果保存到vector中
    vector<int> getClosetClusterCenterLabel()
    {
        double min;
        int label;
        vector<int> labels;
        for (int i = 0; i < points.size(); i++)
        {
            label = 0;
            min = getDistanceBetweenTwoPoints(points[i], centers[0]);
            for (int j = 1; j < centers.size(); j++)
            {
                double tmp = getDistanceBetweenTwoPoints(points[i], centers[j]);
                if (tmp < min)
                {
                    min = tmp;
                    label = j;
                }
            }
            labels.push_back(label);
        }
        return labels;
    }

    //将每个点放入它离的最近的中心点对应的簇中
    void computeClusters(const vector<int>& labels)
    {
        for (int i = 0; i < k; i++)
        {
            clusters[i].clear();
        }
        for (int i = 0; i < labels.size(); i++)
        {
            int label = labels[i];
            clusters[label].push_back(points[i]);
        }
    }

    //重新计算所有簇的中心点的灰度值
    void computeCenters()
    {
        centers.clear();
        for (int i = 0; i < k; i++)
        {
            double sum = 0;
            for (int j = 0; j < clusters[i].size(); j++)
            {
                sum += clusters[i][j].pixVal;
            }
            double meanVal = sum / clusters[i].size();
            point cp(-1, -1, meanVal);
            centers.push_back(cp);
        }
    }

    //确定新的中心点后重新计算一次cost
    double computeCost()
    {
        double sum = 0;
        for (int i = 0; i < k; i++)
        {
            vector<point> tmpVec=clusters[i];
            for (int j = 0; j < tmpVec.size(); j++)
            {
                sum += getDistanceBetweenTwoPoints(tmpVec[j], centers[i]);
            }
        }
        return sum / points.size();
    }

    //迭代执行k-means算法的步骤
    void kmeans()
    {
        double oldCost, newCost;
        vector<int> labels=getClosetClusterCenterLabel();
        computeClusters(labels);
        newCost = computeCost();

        computeCenters();
        labels = getClosetClusterCenterLabel();
        computeClusters(labels);
        oldCost = newCost;
        newCost = computeCost();

        while (oldCost != newCost)
        {
            oldCost = newCost;
            computeCenters();
            labels = getClosetClusterCenterLabel();
            computeClusters(labels);
            newCost = computeCost();
        }
        cout <<"Final Cost: "<< newCost << endl;
    }
};
#endif

测试的kmeans.cpp文件:

#include "kmeans.h"
//图片的存放位置
const String imageFolder = "F:\\";
//簇的个数(即k的大小,根据自己需要调整)
const int numOfCluster =4;
//最大像素值
const int MAX_PIX_VALUE = 255;
//存放所有点
vector<point> points;
//存放所有簇中心
vector<point> centers;
//存放所有点颜色特征(i,j)->i*rows+j
vector<double> pixVec;

//读取图像
Mat readImage(String imageName)
{
    String imageLoc = imageFolder + imageName;
    Mat image=imread(imageLoc);
    return image;
}

//初始化k-means聚类中心
void initializeCenters(const Mat& img)
{
    srand((unsigned)time(NULL));
    for (int i = 0; i < numOfCluster; i++)
    {
        int randomX = rand() % img.rows;
        int randomY = rand() % img.cols;
        uchar pixVal = img.at<uchar>(randomX, randomY);
        point cp(randomX, randomY, (double)pixVal);
        centers.push_back(cp);
    }
}

//将图像中的所有点装入points中
void initializePoints(const Mat& img)
{
    for (int i = 0; i < img.rows; i++)
    {
        const uchar* data = img.ptr<uchar>(i);
        for (int j = 0; j < img.cols; j++)
        {
            uchar pixVal = data[j];
            point p(i,j, (double)pixVal);
            points.push_back(p);
        }
    }
}

int main()
{
    String imageName = "lena.jpg";
    Mat img = readImage(imageName);
    cvtColor(img, img, CV_RGB2GRAY);//转化为灰度图像
    namedWindow(imageName,WINDOW_NORMAL);
    imshow(imageName, img);
    waitKey(0);
    int rows = img.rows;
    int cols = img.cols;
    initializeCenters(img);
    initializePoints(img);
    Kmeans* km=new Kmeans(points, centers, numOfCluster, 1);
    cout << "---------------k-means start-------------" << endl;
    km->kmeans();
    cout << "---------------k-means end---------------" <<endl;
    vector<point>* clusters = km->getClusters();
    Mat res(img.rows,img.cols,img.type());
    double div = MAX_PIX_VALUE / numOfCluster;
    for (int i = 0; i < numOfCluster; i++)
    {
        vector<point> tmpVec = clusters[i];
        for (int j = 0; j < tmpVec.size(); j++)
        {
            res.at<uchar>(tmpVec[j].row, tmpVec[j].col) = i*div;
        }
    }
    namedWindow("kmeansResult",WINDOW_NORMAL);
    imshow("kmeansResult", res);
    waitKey(0);
    imwrite("./segment_lena.jpg", res);
    system("pause");
}

彩色图像分割:参考

主函数:

#include "clusterImagePixels.hpp"
 
int main()
{
    Mat testImage = imread("E:\\testImage\\board.jpg");
    if (testImage.empty())
    {
        return -1;
    }
 
    ClusterPixels clusterPix(testImage,3);
 
    Mat colorResults = clusterPix.clusterColorImageByKmeans();
    Mat grayResult = clusterPix.clusterGrayImageByKmeans();
 
    if (!colorResults.empty())
    {
        hconcat(testImage, colorResults, colorResults);
        imshow("clusterImage", colorResults);
    }
 
    if (!grayResult.empty())
    {
        hconcat(testImage, grayResult, grayResult);
        imshow("grayCluster", grayResult);
    }
 
    if (waitKey() == 27)
        return 0;
}
#include <opencv.hpp>
using namespace cv;
 
 
Scalar colorTab[] =     //10个颜色
{
    Scalar(0, 0, 255),
    Scalar(0, 255, 0),
    Scalar(255, 100, 100),
    Scalar(255, 0, 255),
    Scalar(0, 255, 255),
    Scalar(255, 0, 0),
    Scalar(255, 255, 0),
    Scalar(255, 0, 100),
    Scalar(100, 100, 100),
    Scalar(50, 125, 125)
};
 
class ClusterPixels
{
private:
    Mat image;            //待聚类图像
    Mat labels;            //聚类后的标签
    int clusterCounts;    //分类数,不得大于10,只是颜色定义只有10类,并不是算法限制
 
public:
    ClusterPixels() :clusterCounts(0){}
    ClusterPixels(const Mat& src, int clusters = 5) :clusterCounts(clusters){ image = src.clone(); }
 
    void setImage(const Mat& src){ image = src.clone(); };
    void setClusters(int clusters){ clusterCounts = clusters; }
 
    Mat getLabels()    {return labels;    };        //返回聚类后的标签
 
    Mat clusterGrayImageByKmeans()
    {
        //转换成灰度图
        if (image.channels() != 1)
            cvtColor(image, image, COLOR_BGR2GRAY);
 
        int rows = image.rows;
        int cols = image.cols;
        
        //保存聚类后的图片
        Mat clusteredMat(rows, cols, CV_8UC3);
        clusteredMat.setTo(Scalar::all(0));
 
        Mat pixels(rows*cols, 1, CV_32FC1);    //pixels用于保存所有的灰度像素
 
        for (int i = 0; i < rows;++i)
        {
            const uchar *idata = image.ptr<uchar>(i);
            float *pdata = pixels.ptr<float>(0);
            for (int j = 0; j < cols;++j)
            {
                pdata[i*cols + j] = idata[j];
            }
        }
 
        kmeans(pixels, clusterCounts, labels, TermCriteria(TermCriteria::EPS + TermCriteria::MAX_ITER, 10, 0), 5, KMEANS_PP_CENTERS);
 
        for (int i = 0; i < rows;++i)
        {
            for (int j = 0; j < cols;++j)
            {
                circle(clusteredMat, Point(j,i), 1, colorTab[labels.at<int>(i*cols + j)]);        //标记像素点的类别,颜色区分
            }
        }
 
        return clusteredMat;
    }
 
    Mat clusterColorImageByKmeans()
    {
        assert(image.channels() != 1);
 
        int rows = image.rows;
        int cols = image.cols;
        int channels = image.channels();
 
        //保存聚类后的图片
        Mat clusteredMat(rows, cols, CV_8UC3);
        clusteredMat.setTo(Scalar::all(0));
 
        Mat pixels(rows*cols, 1, CV_32FC3);    //pixels用于保存所有的灰度像素
        pixels.setTo(Scalar::all(0));
 
        for (int i = 0; i < rows; ++i)
        {
            const uchar *idata = image.ptr<uchar>(i);
            float *pdata = pixels.ptr<float>(0);
 
            for (int j = 0; j < cols*channels; ++j)
            {
                    pdata[i*cols*channels + j] = saturate_cast<float>(idata[j]);            
            }
        }
 
        kmeans(pixels, clusterCounts, labels, TermCriteria(CV_TERMCRIT_EPS + CV_TERMCRIT_ITER, 10, 0), 5, KMEANS_PP_CENTERS);
 
        for (int i = 0; i < rows; ++i)
        {
            for (int j = 0; j < cols*channels; j += channels)
            {
                circle(clusteredMat, Point(j/channels,i), 1, colorTab[labels.at<int>(i*cols + (j/channels))]);        //标记像素点的类别,颜色区分
            }
        }
 
        return clusteredMat;
    }
};

opencv3代码

#include "stdafx.h"
#include "opencv2\opencv.hpp"
#include <iostream>
using namespace std;
using namespace cv;
using namespace cv::ml;

int main()
{
    Mat img = imread("E:/opencv/opencv/sources/samples/data/digits.png");
    Mat gray;
    cvtColor(img, gray, CV_BGR2GRAY);
    int b = 20;
    int m = gray.rows / b;   //原图为1000*2000
    int n = gray.cols / b;   //裁剪为5000个20*20的小图块
    Mat data,labels;   //特征矩阵
    for (int i = 0; i < n; i++)
    {
        int offsetCol = i*b; //列上的偏移量
        for (int j = 0; j < m; j++)
        {
            int offsetRow = j*b;  //行上的偏移量
            //截取20*20的小块
            Mat tmp;
            gray(Range(offsetRow, offsetRow + b), Range(offsetCol, offsetCol + b)).copyTo(tmp);
            data.push_back(tmp.reshape(0,1));  //序列化后放入特征矩阵
            labels.push_back((int)j / 5);  //对应的标注
        }

    }
    data.convertTo(data, CV_32F); //uchar型转换为cv_32f
    int samplesNum = data.rows;
    int trainNum = 3000;
    Mat trainData, trainLabels;
    trainData = data(Range(0, trainNum), Range::all());   //前3000个样本为训练数据
    trainLabels = labels(Range(0, trainNum), Range::all());

    //使用KNN算法
    int K = 5;
    Ptr<TrainData> tData = TrainData::create(trainData, ROW_SAMPLE, trainLabels);
    Ptr<KNearest> model = KNearest::create();
    model->setDefaultK(K);
    model->setIsClassifier(true);
    model->train(tData);

    //预测分类
    double train_hr = 0, test_hr = 0;
    Mat response;
    // compute prediction error on train and test data
    for (int i = 0; i < samplesNum; i++)
    {
        Mat sample = data.row(i);
        float r = model->predict(sample);   //对所有行进行预测
        //预测结果与原结果相比,相等为1,不等为0
        r = std::abs(r - labels.at<int>(i)) <= FLT_EPSILON ? 1.f : 0.f;          

        if (i < trainNum)
            train_hr += r;  //累积正确数
        else
            test_hr += r;
    }

    test_hr /= samplesNum - trainNum;
    train_hr = trainNum > 0 ? train_hr / trainNum : 1.;

    printf("accuracy: train = %.1f%%, test = %.1f%%\n",
        train_hr*100., test_hr*100.);
    waitKey(0);
    return 0;
}
最后修改:2020 年 07 月 18 日
如果觉得我的文章对你有用,请随意赞赏