精华内容
下载资源
问答
  • import org.apache.spark.ml.clustering.{KMeans, LDA} import org.apache.spark.SparkConf import org.apache.spark.ml.feature.VectorAssembler import org.apache.spark.sql.SparkSession import scala.util....

    一、环境配置

    1.spark2.1.0-cdh5.7.0(自编译)

    2.cdh5.7.0

    3.scala2.11.8

    4.centos6.4

    二、环境准备

    参考https://blog.csdn.net/u010886217/article/details/90312617

    三、代码实现

    1.测试数据集iris样例

    5.1,3.5,1.4,0.2,Iris-setosa
    4.9,3.0,1.4,0.2,Iris-setosa
    4.7,3.2,1.3,0.2,Iris-setosa
    4.6,3.1,1.5,0.2,Iris-setosa
    5.0,3.6,1.4,0.2,Iris-setosa
    5.4,3.9,1.7,0.4,Iris-setosa
    4.6,3.4,1.4,0.3,Iris-setosa
    5.0,3.4,1.5,0.2,Iris-setosa
    4.4,2.9,1.4,0.2,Iris-setosa
    4.9,3.1,1.5,0.1,Iris-setosa
    5.4,3.7,1.5,0.2,Iris-setosa
    4.8,3.4,1.6,0.2,Iris-setosa
    4.8,3.0,1.4,0.1,Iris-setosa
    4.3,3.0,1.1,0.1,Iris-setosa
    5.8,4.0,1.2,0.2,Iris-setosa
    ...

    2.Kmeans算法

    package sparktest
    
    import org.apache.spark.ml.clustering.{KMeans, LDA}
    import org.apache.spark.SparkConf
    import org.apache.spark.ml.feature.VectorAssembler
    import org.apache.spark.sql.SparkSession
    
    import scala.util.Random
    
    object cluster_kmeans {
      def main(args: Array[String]): Unit = {
        val conf = new SparkConf().setMaster("local").setAppName("iris")
        val spark = SparkSession.builder().config(conf).getOrCreate()
    
        val file = spark.read.format("csv").load("iris.data")
        file.show()
    
        import spark.implicits._
        val random = new Random()
        val data = file.map(row => {
          val label = row.getString(4) match {
            case "Iris-setosa" => 0
            case "Iris-versicolor" => 1
            case "Iris-virginica" => 2
          }
    
          (row.getString(0).toDouble,
            row.getString(1).toDouble,
            row.getString(2).toDouble,
            row.getString(3).toDouble,
            label,
            random.nextDouble())
        }).toDF("_c0", "_c1", "_c2", "_c3", "label", "rand").sort("rand")
        val assembler = new VectorAssembler()
          .setInputCols(Array("_c0", "_c1", "_c2", "_c3"))
          .setOutputCol("features")
    
        val dataset = assembler.transform(data)
        val Array(train, test) = dataset.randomSplit(Array(0.8, 0.2))
        train.show()
    
        val kmeans = new KMeans().setFeaturesCol("features").setK(3).setMaxIter(20)
        val model = kmeans.fit(train)
        model.transform(train).show()
    
      }
    }
    

    3.LDA算法

    package sparktest
    
    import org.apache.spark.ml.clustering.{KMeans, LDA}
    import org.apache.spark.SparkConf
    //import org.apache.spark.ml.evaluation.ClusteringEvaluator
    import org.apache.spark.ml.feature.VectorAssembler
    import org.apache.spark.sql.SparkSession
    
    import scala.util.Random
    
    object cluster_lda {
      def main(args: Array[String]): Unit = {
        val conf = new SparkConf().setMaster("local").setAppName("iris")
        val spark = SparkSession.builder().config(conf).getOrCreate()
    
        val file = spark.read.format("csv").load("iris.data")
        file.show()
    
        import spark.implicits._
        val random = new Random()
        val data = file.map(row => {
          val label = row.getString(4) match {
            case "Iris-setosa" => 0
            case "Iris-versicolor" => 1
            case "Iris-virginica" => 2
          }
    
          (row.getString(0).toDouble,
            row.getString(1).toDouble,
            row.getString(2).toDouble,
            row.getString(3).toDouble,
            label,
            random.nextDouble())
        }).toDF("_c0", "_c1", "_c2", "_c3", "label", "rand").sort("rand")
        val assembler = new VectorAssembler()
          .setInputCols(Array("_c0", "_c1", "_c2", "_c3"))
          .setOutputCol("features")
    
        val dataset = assembler.transform(data)
        val Array(train, test) = dataset.randomSplit(Array(0.8, 0.2))
        train.show()
    
    
        val lda = new LDA().setFeaturesCol("features").setK(3).setMaxIter(40)
        val model = lda.fit(train)
        val prediction = model.transform(train)
        //prediction.show()
        val ll = model.logLikelihood(train)
        val lp = model.logPerplexity(train)
    
        // Describe topics.
        val topics = model.describeTopics(3)
        prediction.select("label","topicDistribution").show(false)
        println("The topics described by their top-weighted terms:")
        topics.show(false)
        println(s"The lower bound on the log likelihood of the entire corpus: $ll")
        println(s"The upper bound on perplexity: $lp")
      }
    }

     

     

    展开全文
  • 不知哪日,无意中未来的同学潘潘聊到了图像处理,聊到了她的论文《基于LDA的行人检测》,出于有一年半工作经验的IT男人的本能,就一起开始学习研究这篇“论文”了。众所周知,老师给学生设置论文题目的,起初都是...

    题记:2012年4月1日回到家,南大计算机研究僧复试以后,等待着的就是独坐家中无聊的潇洒。不知哪日,无意中和未来的同学潘潘聊到了图像处理,聊到了她的论文《基于LDA的行人检测》,出于有一年半工作经验的IT男人的本能,就一起开始学习研究这篇“论文”了。众所周知,老师给学生设置论文题目的,起初都是很模糊的——自己没有思考清楚实践上的可行性和具体思路,仅从理论了解上就给学生设置一些“难以实现”的论文任务。几经修改和商讨,最后的论文实际上就是“基于SIFT+Kmeans+LDA的图片分类器的实现”了。至此,代码已经编写完毕,图片分类的效果还算满意。

    ——copyright:由于是一起学习研究的结果,相关所有内容潘潘童鞋可以以第一作者身份使用!1. 实现思路2. 软件环境3. Step1——SIFT应用4. Step2——Kmeans应用5. Step3——数词频的实现6. Step4——LDA应用7. 参考

    一、实现思路

    分类器的功能是:输入一组图片,给定需要分类的类别数lda_k(>1);输出lda_k个文件夹,每个文件夹内的图片为一类图片。

    第一步是SIFT特征提取:输入图片,输出图片的特征点集,即feature列表,每个feature代表一个图片的某个局部特征,每个feature的数据结构由一个128维浮点数组表示。至此,可以将一幅图片转换成一个feature集。

    第二步是Kmeans聚类:输入是所有图片的feature集的综合,给定参数km_k代表需要聚类的类别数;输出是km_k个feature,在LDA的视角看来就是“单词表”,用“单词表”中的一个“单词”(类中的质心feature)代表kmeans聚类里面一类的所有feature。

    第三步是统计词频:(对每个图片)输入是图片的feature集和“单词表”,分别计算该图片feature集中每个feature对应的“单词”,并统计每个“单词”在该feature集中出现的次数即词频;输出是词频统计数据。

    最后一步是LDA训练潜在主题:输入是所有图片文件的词频统计数据,以及给定的需要训练出来的主题类别数lda_k;LDA输出参数较多,其中最有用的就是文档-主题条件概率矩阵(theta矩阵),即举证中每个元素表示P(主题k|文档m)——在文档m中,主题是k的概率——通过该概率即可判断当前文档最可能的主题,实现了将所有文档分类为lda_k个主题。

    总之,理论上LDA研究的实体是一组文档,每个文档由若干单词组成,通过无监督学习,能够发现lda_k个主题,并且确定theta矩阵——文档确定的情况下生成主题k的概率,以及phi矩阵——主题确定的情况下生成单词v的概率。分类器通过SIFT算法将图片转换为若干feature,即将图片看成是“文档”feature看成是“单词”。而仅通过SIFT处理后的feature并不能直接单做“单词”作为LDA的输入,因为几乎每个feature都不一样,还需要Kmeans算法对所有图片的feature集的总和做一次聚类,得到km_k个类别的中心feature,即生成km_k个“单词”的“单词表”,并以此中心feature代替一个类别内的所有其他feature,从而将一个图片“文档”中的所有feature均在“单词表”中能够找到代表它的“单词”,这样图片就真正转换为了LDA能够处理的“文档”。

    [Go Top]

    二、软件环境

    VS2010,MFC,C++。

    安装并配置Opencv,参见VS2010+Opencv-2.4.0的配置攻略。

    下载并集成SIFT源码,参见在VS2010中应用SIFT(C)源码。

    下载并集成LDA源码,参见在VS2010中应用LDA(C)源码。

    Kmeans为Opencv自带函数,无需应用其他源码。建立好自己的工程,集成算法源码后,工程文件夹大致结构应为下图所示:

    设计好自己的例程界面,并关联好响应函数和成员变量,本例程界面如下:

    [Go Top]

    三、Step1——SIFT应用

    在该步骤内,程序依据“图片源目录”给出的图片目录路径,扫描目录内的所有图片文件,对每个执行如下操作:

    ...

    n= _sift_features(img, &features, SIFT_INTVLS/*3*/, SIFT_SIGMA/*1.6*/, SIFT_CONTR_THR/*0.04*/,

    SIFT_CURV_THR/*10*/, SIFT_IMG_DBL/*1*/, SIFT_DESCR_WIDTH/*4*/, SIFT_DESCR_HIST_BINS/*8*/); //SIFTfeature提取

    ...

    export_features(out_file_name, features, n);//将features导出为文件

    ...if(勾选了“保存SIFT特征图”)

    {

    draw_features(img, features, n);//在img图片上标记出features

    cvSaveImage(out_img_name, img, NULL); //将标记后的图片保存

    }

    ...

    其中最主要的三个函数就是_sift_features(…), export_features(…), draw_features(…)均为sift源码所提供。(注:feature有两种类型——OXFD和LOWE,本程序只涉及LOWE类型,所有OXFD相关格式均自动忽略。)

    _sift_features(…)函数第一个参数img为传入图片的IplImage指针格式,为Opencv所定义的图片数据结构;features后面的参数均为SIFT算法的输入参数,具体含义见作者的源码注释。

    需要注意和理解的是features这个参数,其指向的为一个结构体feature的数组,feature结构为:/**

    Structure to represent an affine invariant image feature. The fields

    x, y, a, b, c represent the affine region around the feature:

    a(x-u)(x-u) + 2b(x-u)(y-v) + c(y-v)(y-v) = 1*/

    structfeature

    {double x; /**< x coord*/

    double y; /**< y coord*/

    double a; /**< Oxford-type affine region parameter*/

    double b; /**< Oxford-type affine region parameter*/

    double c; /**< Oxford-type affine region parameter*/

    double scl; /**< scale of a Lowe-style feature*/

    double ori; /**< orientation of a Lowe-style feature*/

    int d; /**< descriptor length*/

    double descr[FEATURE_MAX_D]; /**< descriptor*/

    int type; /**< feature type, OXFD or LOWE*/

    int category; /**< all-purpose feature category*/

    struct feature* fwd_match; /**< matching feature from forward image*/

    struct feature* bck_match; /**< matching feature from backmward image*/

    struct feature* mdl_match; /**< matching feature from model*/CvPoint2D64f img_pt;/**< location in image*/CvPoint2D64f mdl_pt;/**< location in model*/

    void* feature_data; /**< user-definable data*/};

    其中x,y表示feature在图片中的坐标,scl, ori表示在图中标记特征的强度和方向,descr是最重要的特征信息即128维的特征向量(FEATURE_MAX_D==128)。实际上所保存的特征文件里面也只保存了feature的这些信息。features就是feature的一个数组,包含了SIFT算法所提取的图片的所有feature,返回值n表示features数组中有多少个feature元素。

    export_features(…)就是将上一步中的features保存为文件,文件格式如下:441 128

    178.616459 111.621902 34.241822 1.292619

    0 0 0 0 0 0 0 0 12 0 0 0 1 3 0 8 140 4 0 0

    0 0 0 30 43 3 0 0 0 0 0 2 0 0 0 0 2 9 0 0

    94 0 0 0 8 72 6 37 172 15 0 0 0 2 1 119 122 5 0 0

    0 0 0 12 0 0 0 0 0 2 0 0 57 5 0 0 2 73 9 14

    172 133 0 0 0 11 3 14 128 45 0 0 0 0 0 0 0 0 0 0

    0 0 0 0 4 1 2 2 4 13 0 1 172 152 2 4 4 6 0 2

    145 116 0 0 0 0 0 0

    220.732993 432.886679 20.895674 -1.740551

    6 0 0 1 168 133 17 5 60 0 0 1 37 20 24 25 3 0 0 0

    14 26 17 3 0 0 0 0 0 0 0 0 7 0 0 0 168 144 2 1

    123 0 0 0 80 38 2 15 13 0 0 0 12 44 4 4 0 0 0 0

    0 0 0 0 2 0 0 1 168 67 0 0 121 13 0 2 144 16 0 3

    22 2 0 4 30 7 0 0 0 0 0 0 1 0 0 0 0 0 0 0

    168 81 0 0 87 9 0 1 125 38 2 5 24 2 0 3 20 16 2 2

    0 0 0 0 1 3 0 0……

    其中第一行的第一个int表示文件中feature的个数,第二个int表示feature的维数。接下来每段132个浮点数(后128个近似为整数)为一个feautre,前4个分别为x, y, scr, ori,后128个为表征feature的128维向量。

    draw_features(…)就是将feature信息示例性地标注在图上了,图片如下:

    cvSaveImage(…)是Opencv的函数,将加过标注的图片保存为文件。

    这一步实际上要做的重点就是输入为图片,输出为SIFT算法后为每张图片生成的feature文件集:

    这样每张图片就相当于一个“文档”,而feature就是“文档”中的“预备单词”。

    [Go Top]

    四、Step2——Kmeans应用

    Step1里面的feature只是“预备单词”,在成为单词之前还要通过Step2生成“单词表”和Step3将“文档”中的“预备单词”找到“单词表”中最相近的“单词”替换之(并不是真正操作上的替换,只是当成“单词表”中的“单词”统计出来而已)。

    在Step2中,关键操作如下:

    ...

    CvMat*samples=cvCreateMat(featureNum, dims, CV_32FC1); //包含所有图片的所有feature信息的矩阵,featureNum个feature,每个feature为dims(128)维向量,每一维的元素类型为32位浮点数

    CvMat *clusters=cvCreateMat(featureNum, 1, CV_32SC1); //每个feature所在“质心”的指针(实际上本例程中没有用到该信息)

    CvMat *centers=cvCreateMat(k, dims, CV_32FC1); //“质心”信息的数组,k个“质心”每个质心都是dims(128)维向量,每一维的元素类型为32位浮点数

    cvSetZero(clusters); //将矩阵初始化为0

    cvSetZero(centers); //将矩阵初始化为0

    while(file.ReadString(strLine))

    {

    ...

    n= import_features(CIni::CStrToChar(fileName), FEATURE_LOWE, &features); //导入feature文件,n为导入的feature个数

    ...//将feature文件内所有feature信息存入samples矩阵结构内

    for(int i = 0; i < n; i++)

    {for(int j = 0; j < dims; j++)

    {

    samples->data.fl[temp++] =features[i].descr[j];

    }

    }

    }

    cvKMeans2(samples, k, clusters,cvTermCriteria(CV_TERMCRIT_EPS,10,1.0), 3, (CvRNG *)0, KMEANS_USE_INITIAL_LABELS, centers); //Kmeans聚类

    ...

    cvSave(CIni::CStrToChar(ini.getWordListFilePath()), centers);//保存单词表

    ...

    其中关键函数当然是import_features(...)和cvKMeans2(...),前者是sift源码里的方法,用来导入feature文件使之成为内存数据结构,后者是Opencv里的kmeans算法之一(cvKMeans2(...)内部调用了kmeans(...))。

    在说明他们之前首先要了解Opencv内部通用数据结构——用来存储矩阵类型的CvMat,其声明如下:

    typedefstructCvMat

    {inttype;intstep;/*for internal use only*/

    int*refcount;inthdr_refcount;

    union

    {

    uchar*ptr;short*s;int*i;float*fl;double*db;

    } data;

    #ifdef __cplusplus

    union

    {introws;intheight;

    };

    union

    {intcols;intwidth;

    };#else

    introws;intcols;#endif}

    其中最重要的就是用来存储元素信息的一维数组data,data为一个联合体,包含了各种通用类型。data虽然是一维结构,但通过rows, cols标识,可以将data看成二维的矩阵结构,type就标识了元素类型,而step就标识了一行的步长(占用字节数)。

    cvCreateMat(int rows, int cols, inttype);包含了三个参数,rows和cols分别表示data二维矩阵的行数和列数,type表示元素的类型。元素类型通过宏来定义,CV_32FC1中的32表示元素的位数,F表示是浮点数,Cn表示通道数,C1表示1通道,C3表示3通道(只有在类似RGB的三元表示一个像素点颜色时才用到多通道,而通道实际上就是说一个元素应该由几列来表示)。

    有了上面的知识,就知道了samples矩阵是featureNum行,128列的矩阵,而矩阵元素类型为32位浮点数。featureNum的值为所有图片所有feature的总和,也就是说把所有的feature文件里面的feature信息都读入到samples矩阵内用来作为Kmeans的输入。clusters矩阵是featureNum行1列的矩阵,实际上就是featureNum个int元素的数组,每个int元素都相当于一个下标,标识对应feature(一行)属于centers中的哪个类(“质心”),而本程序里面没有使用到clusters提供的信息,featuresNum个feature分别对应于哪个“质心”是在Step3算词频里面实现的。centers就是保存“单词表”信息的矩阵了,k行128列的32位浮点矩阵,即k个feature,每个feature都是一类feature的“质心”——该类所有feature中最中间那个(通过欧式距离来计算的)feature。

    关键操作来了,import_features(...)就是将feature文件读入内存,使之成为feature的内存数据结构。int import_features(char* filename, int type, struct feature**feat)第一个参数就是feature文件的路径,第二个参数是feature的类型,本文是FEATURE_LOWE类型,第三个参数就是传出参数feature数组了,返回值为读入内存的feature个数。在接下来的操作中就需要把features里面的数据全部拷贝到samples矩阵结构内,这样所有文件的feature信息都拷贝到samples内后就完成了kmeans传入数据的工作。

    cvKMeans2(...)是Opencv在kmeans(...)之上封装的一个函数,参数含义可以参照Hongquan的博客中的《OpenCV中kmean算法的实现》,本文需要说明的几个参数是:第一个参数samples——传入所有图片feature信息的总和;第二个参数k即kmeans的聚类个数(本程序通过界面的类别数设置);第七个参数flags表示生成随机数的方式,可能每次运行程序对相同的输入输出的单词表都不同,那么就跟这个参数相关;第八个参数centers,这就是我们需要的输出了,即“单词表”信息,每一行就是一个feature也就是一个“单词”。

    这样,读入Step1中输出的所有feature文件,然后综合起来并输入参数k(聚类类别数),然后就可以生成一张包含k个“单词”的“单词表”了,用Opencv的cvSave(...)函数把这张“单词表”保存为yml文件,就是本步骤的主要输出了。输出“单词表”文件wordList.yml格式类似:%YAML:1.0wordList:!!opencv-matrix

    rows:80cols:128dt: f

    data: [1.64593754e+001, 2.11062511e+001, 30.,3.48312492e+001, 2.39375000e+001, 1.28156252e+001,1.25531254e+001, 1.16812506e+001, 4.92906265e+001,3.61625023e+001, 2.94968758e+001, 23., 1.70375004e+001,1.12718754e+001, 1.71968746e+001, 3.13437500e+001,3.27593765e+001, 2.25156250e+001, 2.02625008e+001,2.26406250e+001, 2.73750000e+001, 1.90531254e+001,2.41375008e+001, 2.85156250e+001, 1.92875004e+001,

    ............................................. ]

    [Go Top]

    五、Step3——数词频的实现

    前面已经说过,Step2是生成“单词表”,而Step3就是通过计算欧式距离来确定原始feature文档中每个feature对应“单词表”中的哪个“单词”,然后统计出来,生成对应的统计文件——词频文件wordF.data。主要操作如下:

    ...

    FileStorage readfs(CIni::CStrToChar(ini.getWordListFilePath()), FileStorage::READ);//以只读的形式打开yml。

    Mat wordList; //单词表矩阵

    readfs[CIni::CStrToChar(CIni::removeSuffix(CIni::getFileNameFromPath(ini.getWordListFilePath())))] >> wordList; //读取单词表

    ...while(“对于每个feature文档”)

    {

    ...int n = import_features(CIni::CStrToChar(fileName), FEATURE_LOWE, &features);

    ...for(int i = 0; i < n; i++)

    {

    ...

    distMin= normL2Sqr_(pa, pb, dims); //计算欧式距离

    ...for(int j = 1; j < wordNum; j++)

    {

    ...

    dist= normL2Sqr_(pa, pb, dims); //计算欧式距离

    ...

    }

    }

    }

    ...

    显而易见,前三个操作就是利用Opencv的函数,将Step2中生成的“单词表”读入矩阵结构(Mat)的变量wordList中。而对于每个feature文档,通过sift源码的import_features(...)函数读入以feature结构体为元素的数组features中。接下来对于每个feature计算它与wordList中哪个“单词”最接近,最后统计出该文档中包含的单词及其个数。

    normL2Sqr_(pa, pb, dims)是Opencv中计算欧式距离的函数,其中pa指向一个feature,而pb指向单词表中的一个“单词”(“单词”也是feature),dims表示待计算数据的维数,在这里就是128了。

    经过上面的操作,统计好每个图片文档中每个“单词”出现的次数后,统一保存为一个词频文档,即将所有图片文档的词频信息保存在一个文件wordF.data内,其文件结构为:72 0:3 1:4 2:3 3:39 4:6 5:10 6:1 7:4 8:4 9:30 10:8 11:3 13:5 14:7 15:20 16:3 17:2 18:5 19:6 20:7 21:2 22:8 23:11 24:15 25:8 26:9 27:9 28:4 29:3 30:14 31:2 34:4 35:4 36:3 37:4 38:8 39:7 40:15 42:7 44:6 45:4 46:8 47:15 48:9 49:3 50:3 51:1 53:4 54:2 55:3 56:2 57:3 58:9 59:1 60:1 61:8 62:4 63:4 64:7 65:3 66:1 68:3 69:1 70:4 71:1 72:1 73:1 74:6 76:2 77:6 78:5 79:3

    60 0:2 1:1 3:29 4:3 5:13 6:1 7:1 8:5 9:30 10:4 11:2 13:1 14:2 15:17 17:1 18:4 19:2 20:1 22:3 23:3 24:4 25:2 26:4 27:4 28:1 29:2 30:8 31:1 32:3 34:1 35:3 36:4 37:4 38:4 39:6 40:15 42:3 44:3 45:2 47:13 48:6 49:3 51:1 52:2 54:2 56:1 57:2 58:13 61:2 63:3 64:6 66:1 67:2 71:1 73:1 74:1 76:1 77:2 78:1 79:4

    75 1:3 2:2 3:30 4:4 5:7 6:1 7:3 8:2 9:32 10:9 11:3 12:3 13:9 14:2 15:22 16:5 17:2 18:5 19:1 20:3 21:3 22:1 23:11 24:6 25:2 26:11 27:6 28:3 29:9 30:5 31:2 32:5 34:3 35:6 36:2 37:10 38:2 39:8 40:20 42:8 43:1 44:7 45:4 46:2 47:14 48:3 49:3 50:3 51:4 52:2 53:5 54:2 55:2 56:1 57:3 58:12 59:1 60:2 61:1 62:4 64:2 65:4 66:4 67:3 68:1 69:1 70:5 71:3 72:2 73:1 74:3 76:5 77:2 78:6 79:4

    73 0:2 1:2 2:1 3:29 4:8 5:6 6:4 7:6 8:3 9:26 10:10 11:2 12:2 13:6 14:1 15:16 16:2 17:8 18:5 19:3 20:2 21:6 22:5 23:4 24:5 25:5 26:12 27:2 28:1 29:10 30:6 31:1 32:2 33:1 34:2 35:9 36:2 37:7 39:5 40:16 42:6 43:1 44:4 46:2 47:17 48:9 49:2 50:3 52:5 53:1 54:2 55:3 56:2 57:3 58:9 59:2 60:1 62:2 63:3 64:1 65:4 66:2 67:1 68:3 69:3 70:7 72:2 73:1 74:3 75:1 76:7 78:8 79:5

    70 0:1 1:5 3:23 4:5 5:2 6:2 7:4 8:5 9:27 10:11 11:2 12:1 13:6 14:4 15:15 16:4 17:4 18:5 19:6 20:4 21:4 22:6 23:7 24:4 25:2 26:12 27:3 28:2 29:13 30:7 31:1 32:4 33:2 34:5 35:12 36:4 37:8 38:3 40:21 42:6 43:1 44:5 45:4 46:3 47:14 48:6 49:5 50:3 51:1 52:6 53:2 54:3 55:2 57:7 58:12 59:2 62:3 63:4 65:5 66:3 67:3 69:1 70:5 71:2 72:3 73:4 74:3 76:6 78:8 79:2

    70 0:1 1:2 2:2 3:25 4:2 5:6 7:1 8:3 9:35 10:7 12:1 13:4 14:4 15:17 16:2 17:7 18:7 19:3 20:3 21:2 22:6 23:5 24:1 25:2 26:9 27:4 28:1 29:7 31:1 32:2 34:3 35:4 36:1 37:8 38:1 39:1 40:19 42:6 44:5 45:2 47:15 48:7 49:5 51:2 52:4 53:1 54:2 55:2 56:2 57:3 58:16 59:2 60:1 61:3 62:4 63:6 65:3 66:3 67:2 68:1 69:1 70:3 71:3 72:4 73:3 74:4 76:2 77:3 78:7 79:9其中每一行代表一个文档(图片文档),%d:%d的结构表示单词ID:单词个数,第一个数字表示后面的元素项个数。这些数据就是Step3统计词频的输出了,也是Step4LDA运算的输入。

    [Go Top]

    六、Step4——LDA应用

    作者对LDA的实现并不是像sift和kmeans那样由一个函数通过参数传入传出来给出,而是作者的main函数的一个实现过程。本例程LDA的主要过程为:

    ...int topic_num = lda_k; //LDA分类数

    struct corpus *cps;structest_param param;

    ...

    cps= read_corpus(data); //读取训练集

    init_param(cps,&param,topic_num); //初始化参数//迭代计算

    while (1)

    {//对每个文档使用sampling方法计算

    for (int m=0; mnum_docs; m++)

    {

    ...for (int l=0; ldocs[m].length; l++)

    {for (int c=0; cdocs[m].words[l].count; c++)

    {

    param.z[m][word_index]= sampling(m,word_index,cps->docs[m].words[l].id,topic_num,cps,&param,alpha,beta,p,s_talpha,vbeta); //sampling计算

    ...

    }

    }

    }if ((iter_time >= burn_in_num) && (iter_time % SAMPLE_LAG == 0))

    {

    calcu_param(&param, cps,topic_num,alpha,beta); //计算参数

    ...

    }//迭代结束条件

    if (sample_time ==sample_num)

    {break;

    }

    }

    average_param(&param, cps,topic_num,alpha,beta,sample_num); //计算theta,phi平均值

    save_model(cps,&param,model_name,alpha,beta,topic_num,sample_num); //保存结果数据

    ...

    对于没有接触过LDA的人要看懂函数过程还是很困难的,但对于有语言功底的程序员,如果只是应用LDA过程,只需要了解几个主要的LDA概念就行了。(其他部分请参考作者代码注释)1、LDA的输入。LDA的输入除了Step3生成的词频统计信息外,还需要一些参数。这些参数一般设置为通用参数就行了,本例程只有lda_k为界面输入,表示LDA训练的主题个数。

    read_corpus(data)方法中,data为字符串,表示输入数据的路径,该方法将文件读取为struct corpus的格式。corpus结构体表示的是一个文档集,其结构可以从声明中看出:structword

    {intid;intcount;

    };structdocument

    {int id; //文档id

    int num_term; //文档包含的单词个数(count的总和)

    int length; //文档包含的单词类别个数(id:count结构的个数)

    struct word*words;

    };structcorpus

    {struct document*docs;int num_docs; //文档个数

    int num_terms; //单词表中单词总数(实际上是所有单词中最大id+1)

    };

    对比Step3中生成的词频文件,不难看懂上面这些结构体的意义。2、LDA的输出。LDA的输出包含很多数据,由save_model(...)函数输出为文件:

    lda.other文件保存参数alpha, beta, topic_num, sample_num的值。lda.topic_assgin文件保存z矩阵,z[m][n]==k表示文档m中的单词n所对应的主题为k。lda.theta文件保存theta矩阵,theta[m][k]表示在文档为m时,生成主题k的概率,即条件概率p(主题k|文档m)。lda.phi文件保存phi矩阵,phi[k][v]表示在主题为k时,生成单词v的概率,即条件概率p(单词v|主题k)。

    其中需要关注的只有theta和phi两个矩阵,而本例程只用到了theta矩阵的信息。theta矩阵和phi矩阵的例子如下表:

    P(Topic_k|Doc_m)

    Topic1

    Topic2

    Doc10.45

    0.55Doc20.1

    0.9Doc30.6

    0.4P(Word_v|Topic_k)

    Word1

    Word2

    Word3

    Word4

    Topic10.45

    0.15

    0.2

    0.2Topic20.1

    0.5

    0.3

    0.1theta矩阵 phi矩阵

    其中的Topic都是由LDA通过无监督学习得到的潜在主题,只需要用户告诉LDA主题数目就行了。从上面的表格中不难看出,在theta矩阵中,我们知道了每个文档生成每个主题的概率,通过比较概率大小就可以确定文档所对应的主题了。3、LDA算法及其运算所需结构体struct est_param。structest_param

    {int **z; //z[m][n] stands for topic assigned to nth word in mth document

    double **theta; //theta[m][k] stands for the topic mixture proportion for document m

    double **phi; //phi[k][v] stands for the probability of vth word in vocabulary is assigned to topic k//count statistics

    int **nd; //nd[m][k] stands for the number of words assigned to kth topic in mth document

    int **nw; //nw[k][t] stands for the number of kth topic assigned to tth term

    int *nd_sum; //nd_sum[m] total number of word in mth document

    int *nw_sum; //nw_sum[k] total number of terms assigned to kth topic

    };

    该结构体内theta和phi二维数组是我们熟悉的输出,z数组也是前面提到的输出之一,后面的四个变量是LDA运算中间过程的必备临时变量。LDA算法,如果了解了相关的变量名和LDA过程,通过下面这幅图是不难了解算法过程的:

    综上,知道了每个图片文档对应哪个主题的概率最大后,就可以根据主题个数新建lda_k个文件夹,然后把分类到对应主题的图片拷贝过去,从而实现了对图片的LDA分类。分类效果如图:

    [Go Top]

    七、参考

    【Opencv】

    Opencv下载:http://sourceforge.net/projects/opencvlibrary/files/

    Opencv教程:http://www.opencv.org.cn/index.php

    【SIFT】

    SIFT源码下载:http://blogs.oregonstate.edu/hess/code/sift/

    SIFT源码使用方法:http://www.open-open.com/lib/view/1325332699514

    【Kmeans】Kmeans为Opencv自带函数。

    OpenCV中kmean算法的实现:http://blog.hongquan.me/?p=8

    【LDA】

    LDA源码下载:http://code.google.com/p/lsa-lda/

    gibbs的LDA实现:http://sourceforge.net/projects/gibbslda/

    【Bag-of-words模型】

    SIFT算法的应用--目标识别之Bag-of-words模型:http://blog.csdn.net/v_JULY_v/article/details/6555899

    [Go Top]

    源码下载:http://www.pudn.com/downloads464/sourcecode/graph/texture_mapping/detail1949366.html

    展开全文
  • 基于SIFT+Kmeans+LDA的图片分类器的实现  posted @ 2012-04-24 20:36 from [FreedomShe] 题记:2012年4月1日回到家,南大计算机研究僧复试以后,等待着的就是独坐家中无聊的潇洒。不知哪日,无意中...

    基于SIFT+Kmeans+LDA的图片分类器的实现

     posted @ 2012-04-24 20:36 from [FreedomShe]

    题记:2012年4月1日回到家,南大计算机研究僧复试以后,等待着的就是独坐家中无聊的潇洒。不知哪日,无意中和未来的同学潘潘聊到了图像处理,聊到了她的论文《基于LDA的行人检测》,出于有一年半工作经验的IT男人的本能,就一起开始学习研究这篇“论文”了。众所周知,老师给学生设置论文题目的,起初都是很模糊的——自己没有思考清楚实践上的可行性和具体思路,仅从理论了解上就给学生设置一些“难以实现”的论文任务。几经修改和商讨,最后的论文实际上就是“基于SIFT+Kmeans+LDA的图片分类器的实现”了。至此,代码已经编写完毕,图片分类的效果还算满意。

    ——copyright:由于是一起学习研究的结果,相关所有内容潘潘童鞋可以以第一作者身份使用!

    1. 实现思路
    2. 软件环境
    3. Step1——SIFT应用
    4. Step2——Kmeans应用
    5. Step3——数词频的实现
    6. Step4——LDA应用
    7. 参考


    一、实现思路

      分类器的功能是:输入一组图片,给定需要分类的类别数lda_k(>1);输出lda_k个文件夹,每个文件夹内的图片为一类图片。

      第一步是SIFT特征提取:输入图片,输出图片的特征点集,即feature列表,每个feature代表一个图片的某个局部特征,每个feature的数据结构由一个128维浮点数组表示。至此,可以将一幅图片转换成一个feature集。

      第二步是Kmeans聚类:输入是所有图片的feature集的综合,给定参数km_k代表需要聚类的类别数;输出是km_k个feature,在LDA的视角看来就是“单词表”,用“单词表”中的一个“单词”(类中的质心feature)代表kmeans聚类里面一类的所有feature。

      第三步是统计词频:(对每个图片)输入是图片的feature集和“单词表”,分别计算该图片feature集中每个feature对应的“单词”,并统计每个“单词”在该feature集中出现的次数即词频;输出是词频统计数据。

      最后一步是LDA训练潜在主题:输入是所有图片文件的词频统计数据,以及给定的需要训练出来的主题类别数lda_k;LDA输出参数较多,其中最有用的就是文档-主题条件概率矩阵(theta矩阵),即举证中每个元素表示P(主题k|文档m)——在文档m中,主题是k的概率——通过该概率即可判断当前文档最可能的主题,实现了将所有文档分类为lda_k个主题。

      总之,理论上LDA研究的实体是一组文档,每个文档由若干单词组成,通过无监督学习,能够发现lda_k个主题,并且确定theta矩阵——文档确定的情况下生成主题k的概率,以及phi矩阵——主题确定的情况下生成单词v的概率。分类器通过SIFT算法将图片转换为若干feature,即将图片看成是“文档”feature看成是“单词”。而仅通过SIFT处理后的feature并不能直接单做“单词”作为LDA的输入,因为几乎每个feature都不一样,还需要Kmeans算法对所有图片的feature集的总和做一次聚类,得到km_k个类别的中心feature,即生成km_k个“单词”的“单词表”,并以此中心feature代替一个类别内的所有其他feature,从而将一个图片“文档”中的所有feature均在“单词表”中能够找到代表它的“单词”,这样图片就真正转换为了LDA能够处理的“文档”。

    [Go Top]


    二、软件环境

      VS2010,MFC,C++。
      安装并配置Opencv,参见VS2010+Opencv-2.4.0的配置攻略
      下载并集成SIFT源码,参见在VS2010中应用SIFT(C)源码
      下载并集成LDA源码,参见在VS2010中应用LDA(C)源码

      Kmeans为Opencv自带函数,无需应用其他源码。建立好自己的工程,集成算法源码后,工程文件夹大致结构应为下图所示:

      设计好自己的例程界面,并关联好响应函数和成员变量,本例程界面如下:

    [Go Top]


    三、Step1——SIFT应用

      在该步骤内,程序依据“图片源目录”给出的图片目录路径,扫描目录内的所有图片文件,对每个执行如下操作:

    复制代码
    ...
    n = _sift_features(img, &features, SIFT_INTVLS/*3*/, SIFT_SIGMA/*1.6*/, SIFT_CONTR_THR/*0.04*/,
        SIFT_CURV_THR/*10*/, SIFT_IMG_DBL/*1*/, SIFT_DESCR_WIDTH/*4*/, SIFT_DESCR_HIST_BINS/*8*/); //SIFTfeature提取
    ...
    export_features(out_file_name, features, n); //将features导出为文件
    ...
    if(勾选了“保存SIFT特征图”)
    {
      draw_features(img, features, n); //在img图片上标记出features
      cvSaveImage(out_img_name, img, NULL); //将标记后的图片保存
    }
    ...
    复制代码

      其中最主要的三个函数就是_sift_features(…), export_features(…), draw_features(…)均为sift源码所提供。(注:feature有两种类型——OXFD和LOWE,本程序只涉及LOWE类型,所有OXFD相关格式均自动忽略。)

      _sift_features(…)函数第一个参数img为传入图片的IplImage指针格式,为Opencv所定义的图片数据结构;features后面的参数均为SIFT算法的输入参数,具体含义见作者的源码注释。

    需要注意和理解的是features这个参数,其指向的为一个结构体feature的数组,feature结构为:

    复制代码
    /**
    Structure to represent an affine invariant image feature.  The fields
    x, y, a, b, c represent the affine region around the feature:
    a(x-u)(x-u) + 2b(x-u)(y-v) + c(y-v)(y-v) = 1
    */
    struct feature
    {
        double x;                      /**< x coord */
        double y;                      /**< y coord */
        double a;                      /**< Oxford-type affine region parameter */
        double b;                      /**< Oxford-type affine region parameter */
        double c;                      /**< Oxford-type affine region parameter */
        double scl;                    /**< scale of a Lowe-style feature */
        double ori;                    /**< orientation of a Lowe-style feature */
        int d;                         /**< descriptor length */
        double descr[FEATURE_MAX_D];   /**< descriptor */
        int type;                      /**< feature type, OXFD or LOWE */
        int category;                  /**< all-purpose feature category */
        struct feature* fwd_match;     /**< matching feature from forward image */
        struct feature* bck_match;     /**< matching feature from backmward image */
        struct feature* mdl_match;     /**< matching feature from model */
        CvPoint2D64f img_pt;           /**< location in image */
        CvPoint2D64f mdl_pt;           /**< location in model */
        void* feature_data;            /**< user-definable data */
    };
    复制代码

      其中x,y表示feature在图片中的坐标,scl, ori表示在图中标记特征的强度和方向,descr是最重要的特征信息即128维的特征向量(FEATURE_MAX_D==128)。实际上所保存的特征文件里面也只保存了feature的这些信息。features就是feature的一个数组,包含了SIFT算法所提取的图片的所有feature,返回值n表示features数组中有多少个feature元素。

      export_features(…)就是将上一步中的features保存为文件,文件格式如下:

    复制代码
    441 128
    178.616459 111.621902 34.241822 1.292619
     0 0 0 0 0 0 0 0 12 0 0 0 1 3 0 8 140 4 0 0
     0 0 0 30 43 3 0 0 0 0 0 2 0 0 0 0 2 9 0 0
     94 0 0 0 8 72 6 37 172 15 0 0 0 2 1 119 122 5 0 0
     0 0 0 12 0 0 0 0 0 2 0 0 57 5 0 0 2 73 9 14
     172 133 0 0 0 11 3 14 128 45 0 0 0 0 0 0 0 0 0 0
     0 0 0 0 4 1 2 2 4 13 0 1 172 152 2 4 4 6 0 2
     145 116 0 0 0 0 0 0
    220.732993 432.886679 20.895674 -1.740551
     6 0 0 1 168 133 17 5 60 0 0 1 37 20 24 25 3 0 0 0
     14 26 17 3 0 0 0 0 0 0 0 0 7 0 0 0 168 144 2 1
     123 0 0 0 80 38 2 15 13 0 0 0 12 44 4 4 0 0 0 0
     0 0 0 0 2 0 0 1 168 67 0 0 121 13 0 2 144 16 0 3
     22 2 0 4 30 7 0 0 0 0 0 0 1 0 0 0 0 0 0 0
     168 81 0 0 87 9 0 1 125 38 2 5 24 2 0 3 20 16 2 2
     0 0 0 0 1 3 0 0
    ……
    复制代码

      其中第一行的第一个int表示文件中feature的个数,第二个int表示feature的维数。接下来每段132个浮点数(后128个近似为整数)为一个feautre,前4个分别为x, y, scr, ori,后128个为表征feature的128维向量。

      draw_features(…)就是将feature信息示例性地标注在图上了,图片如下:

      cvSaveImage(…)是Opencv的函数,将加过标注的图片保存为文件。

      这一步实际上要做的重点就是输入为图片,输出为SIFT算法后为每张图片生成的feature文件集:

      这样每张图片就相当于一个“文档”,而feature就是“文档”中的“预备单词”。

    [Go Top]


    四、Step2——Kmeans应用

      Step1里面的feature只是“预备单词”,在成为单词之前还要通过Step2生成“单词表”和Step3将“文档”中的“预备单词”找到“单词表”中最相近的“单词”替换之(并不是真正操作上的替换,只是当成“单词表”中的“单词”统计出来而已)。

      在Step2中,关键操作如下:

    复制代码
    ...
    CvMat *samples=cvCreateMat(featureNum, dims, CV_32FC1); //包含所有图片的所有feature信息的矩阵,featureNum个feature,每个feature为dims(128)维向量,每一维的元素类型为32位浮点数
    CvMat *clusters=cvCreateMat(featureNum, 1, CV_32SC1); //每个feature所在“质心”的指针(实际上本例程中没有用到该信息)
    CvMat *centers=cvCreateMat(k, dims, CV_32FC1); //“质心”信息的数组,k个“质心”每个质心都是dims(128)维向量,每一维的元素类型为32位浮点数
    cvSetZero(clusters); //将矩阵初始化为0
    cvSetZero(centers); //将矩阵初始化为0
    while(file.ReadString(strLine)) 
    {
        ...
        n = import_features(CIni::CStrToChar(fileName), FEATURE_LOWE, &features); //导入feature文件,n为导入的feature个数
        ...
        //将feature文件内所有feature信息存入samples矩阵结构内
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < dims; j++)
            {
                samples->data.fl[temp++] = features[i].descr[j];
            }
        }
    }
    cvKMeans2(samples, k, clusters,cvTermCriteria(CV_TERMCRIT_EPS,10,1.0), 3, (CvRNG *)0, KMEANS_USE_INITIAL_LABELS, centers); //Kmeans聚类
    ...
    cvSave(CIni::CStrToChar(ini.getWordListFilePath()), centers); //保存单词表
    ...
    复制代码

      其中关键函数当然是import_features(...)和cvKMeans2(...),前者是sift源码里的方法,用来导入feature文件使之成为内存数据结构,后者是Opencv里的kmeans算法之一(cvKMeans2(...)内部调用了kmeans(...))。

      在说明他们之前首先要了解Opencv内部通用数据结构——用来存储矩阵类型的CvMat,其声明如下:

    复制代码
    typedef struct CvMat
    {
        int type;
        int step;
    
        /* for internal use only */
        int* refcount;
        int hdr_refcount;
    
        union
        {
            uchar* ptr;
            short* s;
            int* i;
            float* fl;
            double* db;
        } data;
    
    #ifdef __cplusplus
        union
        {
            int rows;
            int height;
        };
    
        union
        {
            int cols;
            int width;
        };
    #else
        int rows;
        int cols;
    #endif
    }
    复制代码

      其中最重要的就是用来存储元素信息的一维数组data,data为一个联合体,包含了各种通用类型。data虽然是一维结构,但通过rows, cols标识,可以将data看成二维的矩阵结构,type就标识了元素类型,而step就标识了一行的步长(占用字节数)。
      cvCreateMat(int rows, int cols, int type);包含了三个参数,rows和cols分别表示data二维矩阵的行数和列数,type表示元素的类型。元素类型通过宏来定义,CV_32FC1中的32表示元素的位数,F表示是浮点数,Cn表示通道数,C1表示1通道,C3表示3通道(只有在类似RGB的三元表示一个像素点颜色时才用到多通道,而通道实际上就是说一个元素应该由几列来表示)。
      有了上面的知识,就知道了samples矩阵是featureNum行,128列的矩阵,而矩阵元素类型为32位浮点数。featureNum的值为所有图片所有feature的总和,也就是说把所有的feature文件里面的feature信息都读入到samples矩阵内用来作为Kmeans的输入。clusters矩阵是featureNum行1列的矩阵,实际上就是featureNum个int元素的数组,每个int元素都相当于一个下标,标识对应feature(一行)属于centers中的哪个类(“质心”),而本程序里面没有使用到clusters提供的信息,featuresNum个feature分别对应于哪个“质心”是在Step3算词频里面实现的。centers就是保存“单词表”信息的矩阵了,k行128列的32位浮点矩阵,即k个feature,每个feature都是一类feature的“质心”——该类所有feature中最中间那个(通过欧式距离来计算的)feature。

      关键操作来了,import_features(...)就是将feature文件读入内存,使之成为feature的内存数据结构。
      int import_features(char* filename, int type, struct feature** feat)第一个参数就是feature文件的路径,第二个参数是feature的类型,本文是FEATURE_LOWE类型,第三个参数就是传出参数feature数组了,返回值为读入内存的feature个数。在接下来的操作中就需要把features里面的数据全部拷贝到samples矩阵结构内,这样所有文件的feature信息都拷贝到samples内后就完成了kmeans传入数据的工作。

      cvKMeans2(...)是Opencv在kmeans(...)之上封装的一个函数,参数含义可以参照Hongquan的博客中的《OpenCV中kmean算法的实现》,本文需要说明的几个参数是:第一个参数samples——传入所有图片feature信息的总和;第二个参数k即kmeans的聚类个数(本程序通过界面的类别数设置);第七个参数flags表示生成随机数的方式,可能每次运行程序对相同的输入输出的单词表都不同,那么就跟这个参数相关;第八个参数centers,这就是我们需要的输出了,即“单词表”信息,每一行就是一个feature也就是一个“单词”。

      这样,读入Step1中输出的所有feature文件,然后综合起来并输入参数k(聚类类别数),然后就可以生成一张包含k个“单词”的“单词表”了,用Opencv的cvSave(...)函数把这张“单词表”保存为yml文件,就是本步骤的主要输出了。输出“单词表”文件wordList.yml格式类似:

    复制代码
    %YAML:1.0
    wordList: !!opencv-matrix
       rows: 80
       cols: 128
       dt: f
       data: [ 1.64593754e+001, 2.11062511e+001, 30.,
           3.48312492e+001, 2.39375000e+001, 1.28156252e+001,
           1.25531254e+001, 1.16812506e+001, 4.92906265e+001,
           3.61625023e+001, 2.94968758e+001, 23., 1.70375004e+001,
           1.12718754e+001, 1.71968746e+001, 3.13437500e+001,
           3.27593765e+001, 2.25156250e+001, 2.02625008e+001,
           2.26406250e+001, 2.73750000e+001, 1.90531254e+001,
           2.41375008e+001, 2.85156250e+001, 1.92875004e+001,
           ............................................. ]
    复制代码

    [Go Top]


    五、Step3——数词频的实现

      前面已经说过,Step2是生成“单词表”,而Step3就是通过计算欧式距离来确定原始feature文档中每个feature对应“单词表”中的哪个“单词”,然后统计出来,生成对应的统计文件——词频文件wordF.data。主要操作如下:

    复制代码
    ...
    FileStorage readfs(CIni::CStrToChar(ini.getWordListFilePath()), FileStorage::READ); //以只读的形式打开yml。
    Mat wordList; //单词表矩阵
    readfs[CIni::CStrToChar(CIni::removeSuffix(CIni::getFileNameFromPath(ini.getWordListFilePath())))] >> wordList; //读取单词表
    ...
    while(“对于每个feature文档”) 
    {
      ...
      int n = import_features(CIni::CStrToChar(fileName), FEATURE_LOWE, &features);
      ...
      for(int i = 0; i < n; i++)
      {
        ...
        distMin = normL2Sqr_(pa, pb, dims); //计算欧式距离
        ...
        for(int j = 1; j < wordNum; j++)
        {
          ...
          dist = normL2Sqr_(pa, pb, dims); //计算欧式距离
          ...
        }
      }
    }
    ...
    复制代码

      显而易见,前三个操作就是利用Opencv的函数,将Step2中生成的“单词表”读入矩阵结构(Mat)的变量wordList中。而对于每个feature文档,通过sift源码的import_features(...)函数读入以feature结构体为元素的数组features中。接下来对于每个feature计算它与wordList中哪个“单词”最接近,最后统计出该文档中包含的单词及其个数。

      normL2Sqr_(pa, pb, dims)是Opencv中计算欧式距离的函数,其中pa指向一个feature,而pb指向单词表中的一个“单词”(“单词”也是feature),dims表示待计算数据的维数,在这里就是128了。

      经过上面的操作,统计好每个图片文档中每个“单词”出现的次数后,统一保存为一个词频文档,即将所有图片文档的词频信息保存在一个文件wordF.data内,其文件结构为:

    复制代码
    72 0:3 1:4 2:3 3:39 4:6 5:10 6:1 7:4 8:4 9:30 10:8 11:3 13:5 14:7 15:20 16:3 17:2 18:5 19:6 20:7 21:2 22:8 23:11 24:15 25:8 26:9 27:9 28:4 29:3 30:14 31:2 34:4 35:4 36:3 37:4 38:8 39:7 40:15 42:7 44:6 45:4 46:8 47:15 48:9 49:3 50:3 51:1 53:4 54:2 55:3 56:2 57:3 58:9 59:1 60:1 61:8 62:4 63:4 64:7 65:3 66:1 68:3 69:1 70:4 71:1 72:1 73:1 74:6 76:2 77:6 78:5 79:3
    60 0:2 1:1 3:29 4:3 5:13 6:1 7:1 8:5 9:30 10:4 11:2 13:1 14:2 15:17 17:1 18:4 19:2 20:1 22:3 23:3 24:4 25:2 26:4 27:4 28:1 29:2 30:8 31:1 32:3 34:1 35:3 36:4 37:4 38:4 39:6 40:15 42:3 44:3 45:2 47:13 48:6 49:3 51:1 52:2 54:2 56:1 57:2 58:13 61:2 63:3 64:6 66:1 67:2 71:1 73:1 74:1 76:1 77:2 78:1 79:4
    75 1:3 2:2 3:30 4:4 5:7 6:1 7:3 8:2 9:32 10:9 11:3 12:3 13:9 14:2 15:22 16:5 17:2 18:5 19:1 20:3 21:3 22:1 23:11 24:6 25:2 26:11 27:6 28:3 29:9 30:5 31:2 32:5 34:3 35:6 36:2 37:10 38:2 39:8 40:20 42:8 43:1 44:7 45:4 46:2 47:14 48:3 49:3 50:3 51:4 52:2 53:5 54:2 55:2 56:1 57:3 58:12 59:1 60:2 61:1 62:4 64:2 65:4 66:4 67:3 68:1 69:1 70:5 71:3 72:2 73:1 74:3 76:5 77:2 78:6 79:4
    73 0:2 1:2 2:1 3:29 4:8 5:6 6:4 7:6 8:3 9:26 10:10 11:2 12:2 13:6 14:1 15:16 16:2 17:8 18:5 19:3 20:2 21:6 22:5 23:4 24:5 25:5 26:12 27:2 28:1 29:10 30:6 31:1 32:2 33:1 34:2 35:9 36:2 37:7 39:5 40:16 42:6 43:1 44:4 46:2 47:17 48:9 49:2 50:3 52:5 53:1 54:2 55:3 56:2 57:3 58:9 59:2 60:1 62:2 63:3 64:1 65:4 66:2 67:1 68:3 69:3 70:7 72:2 73:1 74:3 75:1 76:7 78:8 79:5
    70 0:1 1:5 3:23 4:5 5:2 6:2 7:4 8:5 9:27 10:11 11:2 12:1 13:6 14:4 15:15 16:4 17:4 18:5 19:6 20:4 21:4 22:6 23:7 24:4 25:2 26:12 27:3 28:2 29:13 30:7 31:1 32:4 33:2 34:5 35:12 36:4 37:8 38:3 40:21 42:6 43:1 44:5 45:4 46:3 47:14 48:6 49:5 50:3 51:1 52:6 53:2 54:3 55:2 57:7 58:12 59:2 62:3 63:4 65:5 66:3 67:3 69:1 70:5 71:2 72:3 73:4 74:3 76:6 78:8 79:2
    70 0:1 1:2 2:2 3:25 4:2 5:6 7:1 8:3 9:35 10:7 12:1 13:4 14:4 15:17 16:2 17:7 18:7 19:3 20:3 21:2 22:6 23:5 24:1 25:2 26:9 27:4 28:1 29:7 31:1 32:2 34:3 35:4 36:1 37:8 38:1 39:1 40:19 42:6 44:5 45:2 47:15 48:7 49:5 51:2 52:4 53:1 54:2 55:2 56:2 57:3 58:16 59:2 60:1 61:3 62:4 63:6 65:3 66:3 67:2 68:1 69:1 70:3 71:3 72:4 73:3 74:4 76:2 77:3 78:7 79:9
    复制代码

      其中每一行代表一个文档(图片文档),%d:%d的结构表示单词ID:单词个数,第一个数字表示后面的元素项个数。这些数据就是Step3统计词频的输出了,也是Step4LDA运算的输入。

    [Go Top]


    六、Step4——LDA应用

      作者对LDA的实现并不是像sift和kmeans那样由一个函数通过参数传入传出来给出,而是作者的main函数的一个实现过程。本例程LDA的主要过程为:

    复制代码
    ...
    int topic_num = lda_k; //LDA分类数
    struct corpus *cps;
    struct est_param param;
    ...
    cps = read_corpus(data); //读取训练集
    init_param(cps,&param,topic_num); //初始化参数
    //迭代计算
    while (1)
    {
      //对每个文档使用sampling方法计算
      for (int m=0; m<cps->num_docs; m++)
      {
        ...
        for (int l=0; l<cps->docs[m].length; l++)
        {
          for (int c=0; c<cps->docs[m].words[l].count; c++)
          {
            param.z[m][word_index] = sampling(m,word_index,cps->docs[m].words[l].id,topic_num,cps,&param,alpha,beta,p,s_talpha,vbeta); //sampling计算
            ...
          }
        }
      }
      if ((iter_time >= burn_in_num) && (iter_time % SAMPLE_LAG == 0))
      {
        calcu_param(&param, cps,topic_num,alpha,beta); //计算参数
        ...
      }
      //迭代结束条件
      if (sample_time ==sample_num)
      {
        break;
      }
    }
    average_param(&param, cps,topic_num,alpha,beta,sample_num); //计算theta,phi平均值
    save_model(cps,&param,model_name,alpha,beta,topic_num,sample_num); //保存结果数据
    ...
    复制代码

      对于没有接触过LDA的人要看懂函数过程还是很困难的,但对于有语言功底的程序员,如果只是应用LDA过程,只需要了解几个主要的LDA概念就行了。(其他部分请参考作者代码注释)

    1、LDA的输入。LDA的输入除了Step3生成的词频统计信息外,还需要一些参数。这些参数一般设置为通用参数就行了,本例程只有lda_k为界面输入,表示LDA训练的主题个数。
      read_corpus(data)方法中,data为字符串,表示输入数据的路径,该方法将文件读取为struct corpus的格式。corpus结构体表示的是一个文档集,其结构可以从声明中看出:

    复制代码
    struct word
    {
        int id;
        int count;
    };
    
    struct document
    {
        int id; //文档id
        int num_term; //文档包含的单词个数(count的总和)
        int length; //文档包含的单词类别个数(id:count结构的个数)
        struct word* words;
    };
    
    struct corpus
    {
        struct document* docs;
        int num_docs; //文档个数
        int num_terms; //单词表中单词总数(实际上是所有单词中最大id+1)
    };
    复制代码

      对比Step3中生成的词频文件,不难看懂上面这些结构体的意义。

    2、LDA的输出。LDA的输出包含很多数据,由save_model(...)函数输出为文件:


      lda.other文件保存参数alpha, beta, topic_num, sample_num的值。lda.topic_assgin文件保存z矩阵,z[m][n]==k表示文档m中的单词n所对应的主题为k。lda.theta文件保存theta矩阵,theta[m][k]表示在文档为m时,生成主题k的概率,即条件概率p(主题k|文档m)。lda.phi文件保存phi矩阵,phi[k][v]表示在主题为k时,生成单词v的概率,即条件概率p(单词v|主题k)。

      其中需要关注的只有theta和phi两个矩阵,而本例程只用到了theta矩阵的信息。theta矩阵和phi矩阵的例子如下表:

    P(Topic_k|Doc_m)

    Topic1

    Topic2

    Doc1

    0.45

    0.55

    Doc2

    0.1

    0.9

    Doc3

    0.6

    0.4

     

    P(Word_v|Topic_k)

    Word1

    Word2

    Word3

    Word4

    Topic1

    0.45

    0.15

    0.2

    0.2

    Topic2

    0.1

    0.5

    0.3

    0.1

    theta矩阵   phi矩阵

      其中的Topic都是由LDA通过无监督学习得到的潜在主题,只需要用户告诉LDA主题数目就行了。从上面的表格中不难看出,在theta矩阵中,我们知道了每个文档生成每个主题的概率,通过比较概率大小就可以确定文档所对应的主题了。

    3、LDA算法及其运算所需结构体struct est_param。

    复制代码
    struct est_param
    {
        int **z; //z[m][n] stands for topic assigned to nth word in mth document
        double **theta; // theta[m][k] stands for the topic mixture proportion for document m
        double **phi; // phi[k][v] stands for the probability of vth word in vocabulary is assigned to topic k 
        // count statistics
        int **nd; //nd[m][k] stands for the number of words assigned to kth topic in mth document
        int **nw; //nw[k][t] stands for the number of kth topic assigned to tth term
        int *nd_sum; //nd_sum[m] total number of word in mth document
        int *nw_sum; //nw_sum[k] total number of terms assigned to kth topic
    };
    复制代码

      该结构体内theta和phi二维数组是我们熟悉的输出,z数组也是前面提到的输出之一,后面的四个变量是LDA运算中间过程的必备临时变量。LDA算法,如果了解了相关的变量名和LDA过程,通过下面这幅图是不难了解算法过程的:

      综上,知道了每个图片文档对应哪个主题的概率最大后,就可以根据主题个数新建lda_k个文件夹,然后把分类到对应主题的图片拷贝过去,从而实现了对图片的LDA分类。分类效果如图:

    [Go Top]


    七、参考

    【Opencv】
    Opencv下载:http://sourceforge.net/projects/opencvlibrary/files/
    Opencv教程:http://www.opencv.org.cn/index.php

    【SIFT】
    SIFT源码下载:http://blogs.oregonstate.edu/hess/code/sift/ 
    SIFT源码使用方法:http://www.open-open.com/lib/view/1325332699514

     【Kmeans】Kmeans为Opencv自带函数。
    OpenCV中kmean算法的实现:http://blog.hongquan.me/?p=8

    【LDA】
    LDA源码下载:http://code.google.com/p/lsa-lda/ 
    gibbs的LDA实现:http://sourceforge.net/projects/gibbslda/

     【Bag-of-words模型】
    SIFT算法的应用--目标识别之Bag-of-words模型:http://blog.csdn.net/v_JULY_v/article/details/6555899

    [Go Top]


    源码下载:http://www.pudn.com/downloads464/sourcecode/graph/texture_mapping/detail1949366.html

    From:[Yuanbo She's BLOG], NJU LAMDA. 欢迎转载,但请尊重作者劳动注明出处!
    展开全文
  • 目录二、KMeans 聚类2.1 ...为了方便前面 LDA 主题模型对比,我们依然使用同一份数据集,对数据的前期处理保持一致。 二、KMeans 聚类 2.1 加载数据集 df = pd.read_csv('/content/drive/My Drive/cnews.train.txt',.
    
    

    第一篇内容中,我们介绍了 LDA 主题模型,这一篇,我们将介绍经典的 KMeans 聚类算法在文本上的表现。为了方便和前面 LDA 主题模型对比,我们依然使用同一份数据集,对数据的前期处理保持一致。

    二、KMeans 聚类

    2.1 加载数据集

    df = pd.read_csv('/content/drive/My Drive/cnews.train.txt', delimiter="\t", header=None, names=["label", "data"])
    print(df.label.unique())
    
    ['体育' '娱乐' '家居' '房产' '教育' '时尚' '时政' '游戏' '科技' '财经']
    

    2.2 数据清洗

    中间几个步骤略,与上一篇处理方式完全一致。

    data_words_bigrams = make_bigrams(train_st_text)
    

    为了方便后续的处理,我们将分词后的数组拼接起来

    corpus = [' '.join(line) for line in data_words_bigrams]
    
    ['马晓旭 意外 受伤 国奥 警惕 无奈 大雨 格外 青睐 殷家 傅亚雨 沈阳 报道 来到 沈阳 国奥队 依然 摆脱 雨水 困扰 下午 国奥队 日常 训练 再度 大雨 干扰 无奈_之下 队员 慢跑 分钟 草草收场 上午 国奥队 奥体中心 外场 训练 阴沉沉 气象预报 显示 当天 下午 沈阳 大雨 幸好 队伍 上午 训练 干扰 下午 点当 球队 抵达 训练场 大雨 几个 小时 丝毫 停下来 试一试 态度 球队 当天 下午 例行_训练 分钟 天气 转好 迹象 保护 球员 国奥队 中止 当天 训练 全队 返回 酒店 训练 足球队 来说 稀罕 奥运会 即将 全队 变得 娇贵 沈阳 一周 训练 国奥队 保证 现有 球员 不再 出现意外 伤病 情况 影响 正式 比赛 这一 阶段 控制 训练 受伤 控制 感冒 疾病 队伍 放在 位置 抵达 沈阳 后卫 冯萧霆 训练 冯萧霆 长春 患上_感冒 参加 塞尔维亚 热身赛 队伍 介绍 冯萧霆 发烧_症状 两天 静养 休息 感冒 恢复 训练 冯萧霆 例子 国奥队 对雨中 训练 显得 特别 谨慎 担心 球员 受凉 引发 感冒 非战斗 减员 女足 队员 马晓旭 热身赛 受伤 导致 无缘 奥运 前科 沈阳 国奥队 格外 警惕 训练 嘱咐 队员 动作 再出 事情 工作人员 长春_沈阳 雨水 一路 伴随 国奥队 长春 几次 训练 大雨 搅和 没想到 沈阳 碰到 事情 国奥 球员 雨水 青睐 不解']
    

    2.3 文本向量化

    文本的向量化表示采用三种方式:使用 IDF 权重的哈希向量化表示、不使用 IDF 权重的哈希向量化表示以及 TFIDF 向量化表示,由于文本词量较大,因此在做 hash 处理的时候,我们把特征数设定为 25 万,TFIDF 中我们没设定,使用全部词量。

    from sklearn.pipeline import make_pipeline
    from sklearn.feature_extraction.text import TfidfTransformer
    
    # Perform an IDF normalization on the output of HashingVectorizer
    hasher = HashingVectorizer(n_features=250000, alternate_sign=False, norm=None)
    vectorizer_hash_idf = make_pipeline(hasher, TfidfTransformer())
    
    vectorizer_hash = HashingVectorizer(n_features=250000, alternate_sign=False, norm='l2')
    
    vectorizer_tfidf = TfidfVectorizer(max_df=0.5, min_df=2, use_idf=True)
    
    X_hash_idf = vectorizer_hash_idf.fit_transform(corpus)
    X_hash = vectorizer_hash.fit_transform(corpus)
    X_tfidf = vectorizer_tfidf.fit_transform(corpus)
    
    print(X_hash_idf.shape)
    print(X_hash.shape)
    print(X_tfidf.shape)
    
    (50000, 250000)
    (50000, 250000)
    (50000, 207705)
    

    对于数据维度过高,我们可以使用一些维度压缩技术进行处理,如 PCA、SVD 等,此处我们使用的是 SVD 及正则化处理,此处的输出维度我们限定到 100,如果压缩的目的是为了可视化,那么最常见的是压缩到 2 维。

    from sklearn.decomposition import TruncatedSVD
    from sklearn.preprocessing import Normalizer
    
    print("Performing dimensionality reduction using LSA")
    # Vectorizer results are normalized, which makes KMeans behave as
    # spherical k-means for better results. Since LSA/SVD results are
    # not normalized, we have to redo the normalization.
    svd = TruncatedSVD(100)
    normalizer = Normalizer(copy=False)
    lsa = make_pipeline(svd, normalizer)
    
    X_hash_idf_lsa = lsa.fit_transform(X_hash_idf)
    X_hash_lsa = lsa.fit_transform(X_hash)
    X_tfidf_lsa = lsa.fit_transform(X_tfidf)
    
    explained_variance = svd.explained_variance_ratio_.sum()
    print("Explained variance of the SVD step: {}%".format(
        int(explained_variance * 100)))
    
    print()
    
    Performing dimensionality reduction using LSA
    Explained variance of the SVD step: 11%
    
    print(X_hash_idf_lsa.shape)
    print(X_hash_lsa.shape)
    print(X_tfidf_lsa.shape)
    
    (50000, 100)
    (50000, 100)
    (50000, 100)
    

    2.4 文本聚类

    此处使用两种算法,普通的 KMeans 算法以及同类的更具扩展性的 MiniBatchKMeans 算法,我们将两种算法分别应用于上面 6 种不同的数据处理结果上,共 12 组测试:

    minikm_X_hash_idf_lsa = MiniBatchKMeans(n_clusters=10, init='k-means++', n_init=1, init_size=1000, batch_size=1000, verbose=False)
    minikm_X_hash_idf_lsa.fit(X_hash_idf_lsa)
    minikm_X_hash_lsa = MiniBatchKMeans(n_clusters=10, init='k-means++', n_init=1, init_size=1000, batch_size=1000, verbose=False)
    minikm_X_hash_lsa.fit(X_hash_lsa)
    minikm_X_tfidf_lsa = MiniBatchKMeans(n_clusters=10, init='k-means++', n_init=1, init_size=1000, batch_size=1000, verbose=False)
    minikm_X_tfidf_lsa.fit(X_tfidf_lsa)
    
    minikm_X_hash_idf = MiniBatchKMeans(n_clusters=10, init='k-means++', n_init=1, init_size=1000, batch_size=1000, verbose=False)
    minikm_X_hash_idf.fit(X_hash_idf)
    minikm_X_hash = MiniBatchKMeans(n_clusters=10, init='k-means++', n_init=1, init_size=1000, batch_size=1000, verbose=False)
    minikm_X_hash.fit(X_hash)
    minikm_X_tfidf = MiniBatchKMeans(n_clusters=10, init='k-means++', n_init=1, init_size=1000, batch_size=1000, verbose=False)
    minikm_X_tfidf.fit(X_tfidf)
    
    km = KMeans(n_clusters=10, init='k-means++', max_iter=100, n_init=1, verbose=False)
    km_X_hash_idf_lsa = km.fit(X_hash_idf_lsa)
    km = KMeans(n_clusters=10, init='k-means++', max_iter=100, n_init=1, verbose=False)
    km_X_hash_lsa = km.fit(X_hash_lsa)
    km = KMeans(n_clusters=10, init='k-means++', max_iter=100, n_init=1, verbose=False)
    km_X_tfidf_lsa = km.fit(X_tfidf_lsa)
    
    km = KMeans(n_clusters=10, init='k-means++', max_iter=100, n_init=1, verbose=False)
    km_X_hash_idf = km.fit(X_hash_idf)
    km = KMeans(n_clusters=10, init='k-means++', max_iter=100, n_init=1, verbose=False)
    km_X_hash = km.fit(X_hash)
    km = KMeans(n_clusters=10, init='k-means++', max_iter=100, n_init=1, verbose=False)
    km_X_tfidf = km.fit(X_tfidf)
    

    下面我们结合数据集的真实标签及聚类结果标签,给出一些聚类算法中比较常见的评估指标,每种指标的含义及具体计算方法可以参考 scikit-learn 的官方用户手册

    from sklearn import metrics
    
    labels = df.label
    
    Xs = [X_hash_idf_lsa, X_hash_lsa, X_tfidf_lsa, 
         X_hash_idf, X_hash, X_tfidf, 
         X_hash_idf_lsa, X_hash_lsa, X_tfidf_lsa,
         X_hash_idf, X_hash, X_tfidf]
    
    for index, method in enumerate([minikm_X_hash_idf_lsa, minikm_X_hash_lsa, minikm_X_tfidf_lsa,
              minikm_X_hash_idf, minikm_X_hash, minikm_X_tfidf,
              km_X_hash_idf_lsa, km_X_hash_lsa, km_X_tfidf_lsa,
              km_X_hash_idf, km_X_hash, km_X_tfidf]):
        X = Xs[index]
        print("Homogeneity: %0.3f" % metrics.homogeneity_score(labels, method.labels_))
        print("Completeness: %0.3f" % metrics.completeness_score(labels, method.labels_))
        print("V-measure: %0.3f" % metrics.v_measure_score(labels, method.labels_))
        print("Adjusted Rand-Index: %.3f"
              % metrics.adjusted_rand_score(labels, method.labels_))
        print("Silhouette Coefficient: %0.3f"
              % metrics.silhouette_score(X, method.labels_, metric='euclidean'))
        # print("Calinski-Harabaz Index: %0.3f"
        #       % metrics.calinski_harabasz_score(X.toarray(), km.labels_))     # toarray 内存直接搞死
        print("----------------------------------------------------------------")
    
    Homogeneity: 0.649
    Completeness: 0.704
    V-measure: 0.675
    Adjusted Rand-Index: 0.499
    Silhouette Coefficient: 0.130
    ----------------------------------------------------------------
    Homogeneity: 0.600
    Completeness: 0.632
    V-measure: 0.616
    Adjusted Rand-Index: 0.508
    Silhouette Coefficient: 0.115
    ----------------------------------------------------------------
    Homogeneity: 0.629
    Completeness: 0.660
    V-measure: 0.644
    Adjusted Rand-Index: 0.511
    Silhouette Coefficient: 0.121
    ----------------------------------------------------------------
    Homogeneity: 0.510
    Completeness: 0.615
    V-measure: 0.557
    Adjusted Rand-Index: 0.259
    Silhouette Coefficient: 0.012
    ----------------------------------------------------------------
    Homogeneity: 0.470
    Completeness: 0.557
    V-measure: 0.510
    Adjusted Rand-Index: 0.243
    Silhouette Coefficient: 0.024
    ----------------------------------------------------------------
    Homogeneity: 0.467
    Completeness: 0.642
    V-measure: 0.541
    Adjusted Rand-Index: 0.223
    Silhouette Coefficient: 0.009
    ----------------------------------------------------------------
    Homogeneity: 0.689
    Completeness: 0.738
    V-measure: 0.713
    Adjusted Rand-Index: 0.561
    Silhouette Coefficient: 0.146
    ----------------------------------------------------------------
    Homogeneity: 0.609
    Completeness: 0.634
    V-measure: 0.621
    Adjusted Rand-Index: 0.496
    Silhouette Coefficient: 0.133
    ----------------------------------------------------------------
    Homogeneity: 0.693
    Completeness: 0.729
    V-measure: 0.711
    Adjusted Rand-Index: 0.589
    Silhouette Coefficient: 0.124
    ----------------------------------------------------------------
    Homogeneity: 0.507
    Completeness: 0.616
    V-measure: 0.556
    Adjusted Rand-Index: 0.248
    Silhouette Coefficient: 0.013
    ----------------------------------------------------------------
    Homogeneity: 0.497
    Completeness: 0.601
    V-measure: 0.544
    Adjusted Rand-Index: 0.257
    Silhouette Coefficient: 0.026
    ----------------------------------------------------------------
    Homogeneity: 0.536
    Completeness: 0.623
    V-measure: 0.577
    Adjusted Rand-Index: 0.279
    Silhouette Coefficient: 0.013
    ----------------------------------------------------------------
    

    我们简单分析一下上面的实验结果,一共 12 组实验,前 6 组是使用的是 MiniBatchKmeans 算法,后 6 组使用的是常规的 KMeans 算法,两个大组下前三组均为经过 lsa 降维处理的数据,后三组保持高维数据:

    • 轮廓系数不太适用于高维数据,具有维度灾难现象,详见上面的 4、5、6 及 10、11、12 组实验
    • V-measure 和 Adjusted Rand-Index 是基于信息论的评估分数,官方文档中提到二者不受维度影响,但实测结果也有较大差距,其中 Adjusted Rand-Index 差不多小一半
    • 同等数据情况下,KMeans 结果比 MiniBatchKMeans 结果要略好一丢丢,但是计算量较高,因此大数据量下推荐使用后者。
    • 除轮廓系数外,其他几个指标均需要数据的真实标签,然而这种情况实际中几乎不可能(否则做监督学习它不香么?)

    更多评估指标及各个指标的优缺点可以参考 scikit-learn 的用户手册。

    2.5 关键词展示

    对于使用 TFIDF 向量化的文本,我们在聚类后可以展示每个聚类结果中的一些高频词汇

    # minikm-tfidf-lsa
    print("Top terms per cluster:")
    original_space_centroids = svd.inverse_transform(minikm_X_tfidf_lsa.cluster_centers_)
    order_centroids = original_space_centroids.argsort()[:, ::-1]
    terms = vectorizer_tfidf.get_feature_names()
    
    for i in range(10):
        print("Cluster %d:" % i, end='')
        for ind in order_centroids[i, :10]:
            print(' %s' % terms[ind], end='')
        print()
    
    Top terms per cluster:
    Cluster 0: 银行 陈水扁 贷款 信用卡 客户 吴淑珍 理财产品 业务 检方 台湾
    Cluster 1: 游戏 玩家 中国 学生 留学 大学 美国 活动 工作 发展
    Cluster 2: 电影 导演 影片 拍摄 观众 演员 角色 新浪_娱乐 上映 香港
    Cluster 3: 生活 美国 中国 英国 孩子 活动 工作 设计 时间 喜欢
    Cluster 4: 比赛 球队 球员 火箭 热火 篮板 奇才 防守 时间 赛季
    Cluster 5: 市场 房地产 项目 企业 价格 公司 中国 亿元 投资 开发商
    Cluster 6: 基金 投资 公司 市场 债券 投资者 股票 收益 经理 下跌
    Cluster 7: 搭配 时尚 性感 组图 黑色 装扮 外套 设计 造型 可爱
    Cluster 8: 科学家 发现 研究 地球 美国 人类 时间 英国 动物 研究_人员
    Cluster 9: 空间 色彩 设计 客厅 风格 装饰 卧室 家居 家具 白色
    
    # minikm-tfidf
    print("Top terms per cluster:")
    order_centroids = minikm_X_tfidf.cluster_centers_.argsort()[:, ::-1]
    terms = vectorizer_tfidf.get_feature_names()
    
    for i in range(10):
        print("Cluster %d:" % i, end='')
        for ind in order_centroids[i, :10]:
            print(' %s' % terms[ind], end='')
        print()
    
    Top terms per cluster:
    Cluster 0: 移民 投资 加拿大 申请 申请人 签证 美国 澳洲 技术移民 澳大利亚
    Cluster 1: 基金 投资 公司 债券 市场 投资者 收益 股票 经理 发行
    Cluster 2: 奇才 阿联 易建联 沃尔 比赛 球队 刘易斯 阿里_纳斯 麦基 莱切
    Cluster 3: 市场 房地产 银行 项目 投资 房价 企业 开发商 中国 亿元
    Cluster 4: 学生 大学 学校 申请 美国 专业 课程 留学 学院 学习
    Cluster 5: 留学 学生 留学生 中国 学校 教育 签证 申请 美国 大学
    Cluster 6: 游戏 玩家 中国 美国 活动 发现 时间 陈水扁 工作 世界
    Cluster 7: 电影 导演 影片 票房 观众 拍摄 演员 上映 新浪_娱乐 角色
    Cluster 8: 比赛 火箭 热火 球队 球员 篮板 科比 防守 湖人 詹姆斯
    Cluster 9: 搭配 时尚 设计 风格 色彩 组图 黑色 性感 白色 装扮
    
    # km-tfidf-lsa
    print("Top terms per cluster:")
    original_space_centroids = svd.inverse_transform(minikm_X_tfidf_lsa.cluster_centers_)
    order_centroids = original_space_centroids.argsort()[:, ::-1]
    terms = vectorizer_tfidf.get_feature_names()
    
    for i in range(10):
        print("Cluster %d:" % i, end='')
        for ind in order_centroids[i, :10]:
            print(' %s' % terms[ind], end='')
        print()
    
    Top terms per cluster:
    Cluster 0: 银行 陈水扁 贷款 信用卡 客户 吴淑珍 理财产品 业务 检方 台湾
    Cluster 1: 游戏 玩家 中国 学生 留学 大学 美国 活动 工作 发展
    Cluster 2: 电影 导演 影片 拍摄 观众 演员 角色 新浪_娱乐 上映 香港
    Cluster 3: 生活 美国 中国 英国 孩子 活动 工作 设计 时间 喜欢
    Cluster 4: 比赛 球队 球员 火箭 热火 篮板 奇才 防守 时间 赛季
    Cluster 5: 市场 房地产 项目 企业 价格 公司 中国 亿元 投资 开发商
    Cluster 6: 基金 投资 公司 市场 债券 投资者 股票 收益 经理 下跌
    Cluster 7: 搭配 时尚 性感 组图 黑色 装扮 外套 设计 造型 可爱
    Cluster 8: 科学家 发现 研究 地球 美国 人类 时间 英国 动物 研究_人员
    Cluster 9: 空间 色彩 设计 客厅 风格 装饰 卧室 家居 家具 白色
    
    # km-tfidf
    print("Top terms per cluster:")
    order_centroids = km_X_tfidf.cluster_centers_.argsort()[:, ::-1]
    terms = vectorizer_tfidf.get_feature_names()
    
    for i in range(10):
        print("Cluster %d:" % i, end='')
        for ind in order_centroids[i, :10]:
            print(' %s' % terms[ind], end='')
        print()
    
    Top terms per cluster:
    Cluster 0: 中国 发展 移民 经济 企业 人民币 投资 美国 合作 国家
    Cluster 1: 基金 投资 公司 债券 市场 投资者 股票 经理 收益 发行
    Cluster 2: 比赛 火箭 球队 热火 球员 奇才 篮板 防守 湖人 新浪_体育讯
    Cluster 3: 学生 留学 大学 学校 申请 留学生 美国 中国 专业 教育
    Cluster 4: 空间 设计 色彩 家具 风格 家居 装饰 装修 客厅 卧室
    Cluster 5: 房地产 市场 银行 房价 项目 开发商 楼市 土地 亿元 投资
    Cluster 6: 游戏 玩家 开发 系统 活动 pc 系列 模式 体验 公布
    Cluster 7: 电影 导演 影片 票房 观众 演员 拍摄 上映 新浪_娱乐 角色
    Cluster 8: 美国 发现 陈水扁 时间 活动 科学家 北京 工作 公司 中国
    Cluster 9: 搭配 时尚 黑色 性感 组图 装扮 外套 设计 点评 款式
    

    最后我们计算一下每个簇的文档数,真实数据中每个类别均为 5000。可以看到下面结果中索引为 6 的簇中文档最多,而根据上面的关键词 ”Cluster 6: 游戏 玩家 中国 美国 活动 发现 时间 陈水扁 工作 世界“,我们发现这个类下至少包含”游戏“和”时政“两个类别下的高频词,聚类结果不够理想。

    result = list(minikm_X_tfidf.predict(X_tfidf))
    print ('Cluster distribution:')
    print (dict([(i, result.count(i)) for i in result]))
    print(-minikm_X_tfidf.score(X_tfidf))
    
    Cluster distribution:
    {6: 24837, 8: 3624, 2: 748, 7: 4377, 4: 1245, 3: 5499, 9: 5616, 1: 2259, 5: 1382, 0: 413}
    48097.83211562563
    

    2.6 判定最佳聚类数

    一种简单的方法是绘制一系列聚类结果的 SSE。我们找图中的拐点。如下如所示,拐点因该在 11 附近。

    tfidf = TfidfVectorizer(min_df=5, max_df=0.95)
    tfidf.fit(corpus)
    text = tfidf.transform(corpus)
    
    def find_optimal_clusters(data, max_k):
        iters = range(5, max_k+1, 2)
        
        sse = []
        for k in iters:
            sse.append(MiniBatchKMeans(n_clusters=k, init="k-means++", init_size=1024, batch_size=2048, random_state=20).fit(data).inertia_)
            
        f, ax = plt.subplots(1, 1)
        ax.plot(iters, sse, marker='o')
        ax.set_xlabel('Cluster Centers')
        ax.set_xticks(iters)
        ax.set_xticklabels(iters)
        ax.set_ylabel('SSE')
        ax.set_title('SSE by Cluster Center Plot')
        
    find_optimal_clusters(text, 20)
    

    在这里插入图片描述

    参考文档

    展开全文
  • 在使用mahout之前要安装并启动hadoop集群 ...常用聚类算法有:canopy聚类,k均值算法(kmeans),模糊k均值,层次聚类,LDA聚类等 常用分类算法有:贝叶斯,逻辑回归,支持向量机,感知器,神经网络等 ...
  • 一、概述刚开始想要学习LDA主题模型的建模方法,学习的过程中发现应用到了EM算法,所以还是打算由浅及深地进行,发现EM算法虽然简单只有E步M步的不断迭代,但其应用却很广泛,比较有名的有GMM算法本博文要将的...
  • 在使用mahout之前要安装并启动hadoop集群 ...常用聚类算法有:canopy聚类,k均值算法(kmeans),模糊k均值,层次聚类,LDA聚类等 常用分类算法有:贝叶斯,逻辑回归,支持向量机,感知器,神经网络等
  • 在我知道LSA(和LDA)也是主题建模技术。与聚类的区别在于,文档属于多个主题,但只属于一个集群。我不明白为什么LSA会在K-Means集群的上下文中使用。在示例代码:from sklearn.feature_extraction.t...
  • spark kmean学习 demo

    2019-07-08 16:41:05
    Spark的MLlib库提供了许多可用的聚类方法的实现,如 KMeans、高斯混合模型、Power Iteration Clustering(PIC)、隐狄利克雷分布(LDA) 以及 KMeans 方法的变种 二分KMeans(Bisecting KMeans 流式KMeans...
  • 使用高级分析算法(如大规模机器学习、图形...介绍了大规模分布式机器学习在欺诈检测、用户行为预测(稀疏逻辑回归)中的实际应用,以及英特尔在LDA、Word2Vec、CNN、稀疏KMeans和参数服务器等方面的一些支持或优化工
  • NLP初步学习算法

    千次阅读 2018-05-08 15:38:49
    word2vecword2ve是词聚类模型...LDA和doc2vec更与对比性。LDA很耗时,商业不喜欢用。FastText可以参考的博客地址FastText是facebook开源的一个词向量与文本分类工具,模型简单且训练速度快。FastText使用的模型与wo...
  • 7月20日下一步工作

    2012-07-20 13:31:00
    2、层次聚类和kmeans 的具体理解,包括 (1)如何降维,仅仅靠tf-idf吗,除此以外还有没有别的方法? (2)对层次聚类中每种参数和变量的设置,探讨其对结果的影响,选出最优的参数设置,并写成报告;对其绘图的...
  • 本文主要是记录下Exploring Bikesharing Travel Patterns and Trip Purposes Using...文章主要是利用刷卡数据POI数据利用聚类和LDA主题模型探究了共享单车出行目的出行模式。 详细思路 首先爬取了POI数据,然后将P
  • 秋招面试题复习——机器学习

    千次阅读 2019-07-29 23:36:53
    目录: 1.LR的推导,损失函数 2.逻辑回归怎么实现多分类 3.SVM中核函数选择? 4.SVM使用对偶计算的目的是什么,如何推出来的,手写推导 ...5.生成模型判别模型基本形式,...11.KMeans算法讲讲,有什么缺点,K怎么...
  • Mahout 算法

    千次阅读 2013-11-08 16:59:55
    kmeans、Fuzzy-kmeans 、Mean shift 、Dirichlet process 、LDA聚类;奇异值分解;并行频繁项集挖掘;补充的贝叶斯分类、随机森林决策树分类。 一、分类算法 (一)Logistic 回归(SGD) (二)...
  • ​ 注:机器学习注重原理理解、算法对比及场景使用,应加强算法公式推导及多场景实战。...11.DBSCAN和Kmeans对比 12.LDA原理 13.PCA与SVD的关系 14.推荐系统常用模型 15.协同过滤适用场景及冷启动 1
  • 这两天在学习word2vec模型原理的时候,看到了两篇文章,一篇是关于使用word2vec进行情感分类,另一篇是通过tf-idf这种方式运用LDA或者直接kmeans进行主题分类。 从这两篇文章中,相对与自然语言处理的模型来说, 我...

空空如也

空空如也

1 2 3
收藏数 46
精华内容 18
关键字:

lda和kmeans