查看: 7069|回复: 7

机器学习11周作业--文本聚类

[复制链接]
论坛徽章:
47
mysql徽章
日期:2019-04-11 15:18:42spark徽章
日期:2018-05-03 15:46:21金融徽章
日期:2018-04-12 14:26:28mysql徽章
日期:2017-12-22 16:01:10python徽章
日期:2017-08-17 17:09:36Kafka徽章
日期:2017-07-20 17:21:14nosql徽章
日期:2017-06-15 17:32:54bash徽章
日期:2017-06-01 17:10:16HBase徽章
日期:2017-04-20 17:16:25Hadoop研习者初级
日期:2017-04-20 17:15:22股票徽章
日期:2018-08-24 10:51:37股票徽章
日期:2018-08-30 15:33:52
发表于 2014-12-8 00:13 | 显示全部楼层 |阅读模式
本帖最后由 lwqhp 于 2014-12-8 00:23 编辑

文本聚类,是指将文本集合分组成多个类或簇,使得在同一个簇中的文本内容具有较高的相似度,而不同簇中的文本内容差别较大。其是搜索引擎和语义web的基本技术,会用到 TF/IDF权重,用余弦夹角计算文本相似度,用方差计算两个数据间欧式距离,用k-means进行数据聚类。

应用场景:计算两篇文档的相似度

最简单的做法就是用提取文档的TF/IDF权重,然后用余弦定理计算两个多维向量的距离。能计算两个文本间的距离后,用标准的k-means算法实现文本聚类。

参考资料:
1)TF-IDF(term frequency–inverse document frequency)
     这是一种用于信息检索的一种常用加权技术。它是一种统计方法,用以评估一个字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加,但同时会随着它在语料库中出现的频率成反比下降。

假如一篇文件的总词语数是100个,而词语“母牛”出现了3次,那么“母牛”一词在该文件中的词频就是 0.03 (3/100)。一个计算文件频率 (DF) 的方法是测定有多少份文件出现过“母牛”一词,然后除以文件集里包含的文件总数。所以,如果“母牛”一词在1,000份文件出现过,而文件总数是 10,000,000份的话,其文件频率就是 0.0001 (1000/10,000,000)。最后,TF-IDF分数就可以由计算词频除以文件频率而得到。以上面的例子来说,“母牛”一词在该文件集的TF- IDF分数会是 300 (0.03/0.0001)。这条公式的另一个形式是将文件频率取对数。

具体的计算原理,请参考维基百科tf–idf条目。下面是基本的计算步骤:

1,文档预处理:1)文档分词;2)移除停用词;3)单词正规化处理
2,分出的单词就作为索引项(或单词表),它们代表的就是向量空间的项向量
3,计算项权值:这包括要计算1)词频 ; 2)倒排文件频率;3)TF-IDF权值
4,计算文档之间的相似度,一般用余弦相似度(cosine similarity)一同使用于向量空间模型中,用以判断两份文件之间的相似性。


2)变异系数:
(1)变异系数是相对数形式表示的变异指标。它是通过变异指标中的全距、平均差或标准差与平均数对比得到的。常用的是标准差系数。
(2)变异系数的应用条件是:当所对比的两个数列的水平高低不同时,就不能采用全距、平均差或标准差百行对比分析,因为它们都是指标,其数值的大小不仅受各单位标志值差异程度的影响;为了对比分析不同水平的变量数列之间标志值的变异程度,就必须消除水平高低的影响,这时就要计算变异系数。

========================
使用C#实现文本聚类算法:

1,首先我们准备以下数据
奥运 拳击 入场券 基本 分罄 邹市明 夺冠 对手 浮出 水面
股民 要 清楚 自己 的 目的
印花税 之 股民 四季
杭州 股民 放 鞭炮 庆祝 印花税 下调
残疾 女 青年 入围 奥运 游泳 比赛 创 奥运 历史 两 项 第一
介绍 一 个 ASP.net MVC 系列 教程
在 asp.net 中 实现 观察者 模式 ,或 有 更 好 的 方法 (续)
输 大钱 的 股民 给 我们 启迪
Asp.Net 页面 执行 流程 分析
运动员 行李 将 “后 上 先 下” 奥运 相关 人员 行李 实名制
asp.net 控件 开发 显示 控件 内容
奥运 票务 网上 成功 订票 后 应 及时 到 银行 代售 网点 付款
某 心理 健康 站 开张 后 首 个 咨询 者 是 位 新 股民
ASP.NET 自定义 控件 复杂 属性 声明 持久性 浅析


  1. static void Main(string[] args)
  2. {
  3.     //1、获取文档输入
  4.     string[] docs = getInputDocs("input.txt");
  5.     if (docs.Length < 1)
  6.     {
  7.         Console.WriteLine("没有文档输入");
  8.         Console.Read();
  9.         return;
  10.     }

  11.     //2、初始化TFIDF测量器,用来生产每个文档的TFIDF权重
  12.     TFIDFMeasure tf = new TFIDFMeasure(docs, new Tokeniser());

  13.     int K = 3; //聚成3个聚类

  14.     //3、生成k-means的输入数据,是一个联合数组,第一维表示文档个数,
  15.     //第二维表示所有文档分出来的所有词
  16.     double[][] data = new double[docs.Length][];
  17.     int docCount = docs.Length; //文档个数
  18.     int dimension = tf.NumTerms;//所有词的数目
  19.     for (int i = 0; i < docCount; i++)
  20.     {
  21.         for (int j = 0; j < dimension; j++)
  22.         {
  23.             data[i] = tf.GetTermVector2(i); //获取第i个文档的TFIDF权重向量
  24.         }
  25.     }

  26.     //4、初始化k-means算法,第一个参数表示输入数据,第二个参数表示要聚成几个类
  27.     WawaKMeans kmeans = new WawaKMeans(data, K);
  28.     //5、开始迭代
  29.     kmeans.Start();

  30.     //6、获取聚类结果并输出
  31.     WawaCluster[] clusters = kmeans.Clusters;
  32.     foreach (WawaCluster cluster in clusters)
  33.     {
  34.         List<int> members = cluster.CurrentMembership;
  35.         Console.WriteLine("-----------------");
  36.         foreach (int i in members)
  37.         {
  38.             Console.WriteLine(docs[i]);
  39.         }

  40.     }
  41.     Console.Read();
  42. }
复制代码

分词器的主要代码
  1. /// <summary>
  2. /// 以空白字符进行简单分词,并忽略大小写,
  3. /// 实际情况中可以用其它中文分词算法
  4. /// </summary>
  5. /// <param name="input"></param>
  6. /// <returns></returns>
  7. public IList<string> Partition(string input)
  8. {
  9. Regex r=new Regex("([ \\t{}():;. \n])");  
  10. input=input.ToLower() ;

  11. String [] tokens=r.Split(input);         

  12. List<string> filter=new  List<string>() ;

  13. for (int i=0; i < tokens.Length ; i++)
  14. {
  15.   MatchCollection mc=r.Matches(tokens[i]);
  16.   if (mc.Count <= 0 && tokens[i].Trim().Length > 0      
  17.    && !StopWordsHandler.IsStopword (tokens[i]) )        
  18.    filter.Add(tokens[i]) ;
  19.         }

  20. return filter.ToArray();
  21. }
复制代码

kmeans算法的基本代码
  1. public class WawaKMeans
  2. {
  3.     /// <summary>
  4.     /// 数据的数量
  5.     /// </summary>
  6.     readonly int _coordCount;
  7.     /// <summary>
  8.     /// 原始数据
  9.     /// </summary>
  10.     readonly double[][] _coordinates;
  11.     /// <summary>
  12.     /// 聚类的数量
  13.     /// </summary>
  14.     readonly int _k;
  15.     /// <summary>
  16.     /// 聚类
  17.     /// </summary>
  18.     private readonly WawaCluster[] _clusters;

  19.     internal WawaCluster[] Clusters
  20.     {
  21.         get { return _clusters; }
  22.     }

  23.     /// <summary>
  24.     /// 定义一个变量用于记录和跟踪每个资料点属于哪个群聚类
  25.     /// _clusterAssignments[j]=i;// 表示第 j 个资料点对象属于第 i 个群聚类
  26.     /// </summary>
  27.     readonly int[] _clusterAssignments;
  28.     /// <summary>
  29.     /// 定义一个变量用于记录和跟踪每个资料点离聚类最近
  30.     /// </summary>
  31.     private readonly int[] _nearestCluster;
  32.     /// <summary>
  33.     /// 定义一个变量,来表示资料点到中心点的距离,
  34.     /// 其中—_distanceCache[i][j]表示第i个资料点到第j个群聚对象中心点的距离;
  35.     /// </summary>
  36.     private readonly double[,] _distanceCache;
  37.     /// <summary>
  38.     /// 用来初始化的随机种子
  39.     /// </summary>
  40.     private static readonly Random _rnd = new Random(1);

  41.     public WawaKMeans(double[][] data, int K)
  42.     {
  43.         _coordinates = data;
  44.         _coordCount = data.Length;
  45.         _k = K;
  46.         _clusters = new WawaCluster[K];
  47.         _clusterAssignments = new int[_coordCount];
  48.         _nearestCluster = new int[_coordCount];
  49.         _distanceCache = new double[_coordCount,data.Length];
  50.         InitRandom();
  51.     }

  52.     public void Start()
  53.     {
  54.         int iter = 0;
  55.         while (true)
  56.         {
  57.             Console.WriteLine("Iteration " + (iter++) + "");
  58.             //1、重新计算每个聚类的均值
  59.             for (int i = 0; i < _k; i++)
  60.             {
  61.                 _clusters[i].UpdateMean(_coordinates);
  62.             }

  63.             //2、计算每个数据和每个聚类中心的距离
  64.             for (int i = 0; i < _coordCount; i++)
  65.             {
  66.                 for (int j = 0; j < _k; j++)
  67.                 {
  68.                     double dist = getDistance(_coordinates[i], _clusters[j].Mean);
  69.                     _distanceCache[i,j] = dist;
  70.                 }
  71.             }

  72.             //3、计算每个数据离哪个聚类最近
  73.             for (int i = 0; i < _coordCount; i++)
  74.             {
  75.                 _nearestCluster[i] = nearestCluster(i);
  76.             }

  77.             //4、比较每个数据最近的聚类是否就是它所属的聚类
  78.             //如果全相等表示所有的点已经是较佳距离了,直接返回;
  79.             int k = 0;
  80.             for (int i = 0; i < _coordCount; i++)
  81.             {
  82.                 if (_nearestCluster[i] == _clusterAssignments[i])
  83.                     k++;

  84.             }
  85.             if (k == _coordCount)
  86.                 break;

  87.             //5、否则需要重新调整资料点和群聚类的关系,调整完毕后再重新开始循环;
  88.             //需要修改每个聚类的成员和表示某个数据属于哪个聚类的变量
  89.             for (int j = 0; j < _k; j++)
  90.             {
  91.                 _clusters[j].CurrentMembership.Clear();
  92.             }
  93.             for (int i = 0; i < _coordCount; i++)
  94.             {
  95.                 _clusters[_nearestCluster[i]].CurrentMembership.Add(i);
  96.                 _clusterAssignments[i] = _nearestCluster[i];
  97.             }
  98.             
  99.         }

  100.     }

  101.     /// <summary>
  102.     /// 计算某个数据离哪个聚类最近
  103.     /// </summary>
  104.     /// <param name="ndx"></param>
  105.     /// <returns></returns>
  106.     int nearestCluster(int ndx)
  107.     {
  108.         int nearest = -1;
  109.         double min = Double.MaxValue;
  110.         for (int c = 0; c < _k; c++)
  111.         {
  112.             double d = _distanceCache[ndx,c];
  113.             if (d < min)
  114.             {
  115.                 min = d;
  116.                 nearest = c;
  117.             }
  118.       
  119.         }
  120.         if(nearest==-1)
  121.         {
  122.             ;
  123.         }
  124.         return nearest;
  125.     }
  126.     /// <summary>
  127.     /// 计算某数据离某聚类中心的距离
  128.     /// </summary>
  129.     /// <param name="coord"></param>
  130.     /// <param name="center"></param>
  131.     /// <returns></returns>
  132.     static double getDistance(double[] coord, double[] center)
  133.     {
  134.         //int len = coord.Length;
  135.         //double sumSquared = 0.0;
  136.         //for (int i = 0; i < len; i++)
  137.         //{
  138.         //    double v = coord[i] - center[i];
  139.         //    sumSquared += v * v; //平方差
  140.         //}
  141.         //return Math.Sqrt(sumSquared);

  142.         //也可以用余弦夹角来计算某数据离某聚类中心的距离
  143.         return 1- TermVector.ComputeCosineSimilarity(coord, center);

  144.     }
  145.     /// <summary>
  146.     /// 随机初始化k个聚类
  147.     /// </summary>
  148.     private void InitRandom()
  149.     {
  150.         for (int i = 0; i < _k; i++)
  151.         {
  152.             int temp = _rnd.Next(_coordCount);
  153.             _clusterAssignments[temp] = i; //记录第temp个资料属于第i个聚类
  154.             _clusters[i] = new WawaCluster(temp,_coordinates[temp]);
  155.         }
  156.     }
  157. }
复制代码

聚类实体类的定义
  1. internal class WawaCluster
  2. {
  3.     public WawaCluster(int dataindex,double[] data)
  4.     {
  5.         CurrentMembership.Add(dataindex);
  6.         Mean = data;
  7.     }

  8.     /// <summary>
  9.     /// 该聚类的数据成员索引
  10.     /// </summary>
  11.     internal List<int> CurrentMembership = new List<int>();
  12.     /// <summary>
  13.     /// 该聚类的中心
  14.     /// </summary>
  15.     internal double[] Mean;
  16.     /// <summary>
  17.     /// 该方法计算聚类对象的均值
  18.     /// </summary>
  19.     /// <param name="coordinates"></param>
  20.     public void UpdateMean(double[][] coordinates)
  21.     {
  22.         // 根据 mCurrentMembership 取得原始资料点对象 coord ,该对象是 coordinates 的一个子集;
  23.         //然后取出该子集的均值;取均值的算法很简单,可以把 coordinates 想象成一个 m*n 的距阵 ,
  24.         //每个均值就是每个纵向列的取和平均值 , //该值保存在 mCenter 中

  25.         for (int i = 0; i < CurrentMembership.Count; i++)
  26.         {
  27.             double[] coord = coordinates[CurrentMembership[i]];
  28.             for (int j = 0; j < coord.Length; j++)
  29.             {
  30.                 Mean[j] += coord[j]; // 得到每个纵向列的和;
  31.             }
  32.             for (int k = 0; k < Mean.Length; k++)
  33.             {
  34.                 Mean[k] /= coord.Length; // 对每个纵向列取平均值
  35.             }
  36.         }
  37.     }
  38. }
复制代码

测试结果:
Iteration 0...
Iteration 1...
Iteration 2...
-----------------
奥运 拳击 入场券 基本 分罄 邹市明 夺冠 对手 浮出 水面
杭州 股民 放 鞭炮 庆祝 印花税 下调
残疾 女 青年 入围 奥运 游泳 比赛 创 奥运 历史 两 项 第一
运动员 行李 将 “后 上 先 下” 奥运 相关 人员 行李 实名制
奥运 票务 网上 成功 订票 后 应 及时 到 银行 代售 网点 付款
-----------------
股民 要 清楚 自己 的 目的
印花税 之 股民 四季
输 大钱 的 股民 给 我们 启迪
某 心理 健康 站 开张 后 首 个 咨询 者 是 位 新 股民
-----------------
介绍 一 个 ASP.net MVC 系列 教程
在 asp.net 中 实现 观察者 模式 ,或 有 更 好 的 方法 (续)
Asp.Net 页面 执行 流程 分析
asp.net 控件 开发 显示 控件 内容
ASP.NET 自定义 控件 复杂 属性 声明 持久性
浅析聚类聚的非常准确,而且只迭代了3次,模型就收敛了,当然了这是最理想的效果,其实聚类的结果受好多种因素制约,提取特征的算法,随机初始化函数,kmeans算法的实现等,都有优化的地方,比如把输入的数据的顺序改改,聚类结果就不一样了,或者把随机数的种子变一下,结果也不一样,k-means算法加入一些变异系数的调整,结果也不一样,提取特征的地方不用TF/IDF权重算法用别的,结果肯定也不一样。


回复

使用道具 举报

新浪微博达人勋 niho  未实名认证
论坛徽章:
10
R研习者中级
日期:2015-05-21 14:30:32知识图谱徽章
日期:2018-09-29 11:02:45数据展示徽章
日期:2016-06-23 11:26:00Java徽章
日期:2016-06-08 14:15:55Oracle研习者初级
日期:2016-03-03 15:30:52数据挖掘徽章
日期:2015-12-17 11:55:20数据陷阱解读徽章
日期:2015-08-13 15:21:45机器学习徽章
日期:2015-07-09 11:01:46推荐系统徽章
日期:2015-07-02 12:40:47Kaggle徽章
日期:2019-01-17 14:41:44
发表于 2015-6-4 14:29 | 显示全部楼层
谢谢分享,有更详细的介绍吗
回复 支持 反对

使用道具 举报

论坛徽章:
1
统计徽章
日期:2015-11-05 16:36:41
发表于 2015-6-4 21:38 | 显示全部楼层
聚类分析是什么意思?相关性分析与回归性分析的含义及区别是什么?
回复 支持 反对

使用道具 举报

论坛徽章:
11
Oracle研习者初级
日期:2014-09-19 14:06:28机器学习徽章
日期:2015-03-02 18:03:11数据挖掘徽章
日期:2014-12-18 12:07:12linux徽章
日期:2014-11-06 15:15:45DOE徽章
日期:2014-11-06 15:07:55树莓派
日期:2014-10-08 17:38:40R研习者初级
日期:2014-09-19 14:23:08R研习者中级
日期:2014-09-19 14:21:24R研习者中级
日期:2014-09-19 14:20:24R研习者中级
日期:2014-09-19 14:19:25SAS研习者初级
日期:2015-06-25 11:43:15
发表于 2015-6-4 22:46 | 显示全部楼层
感谢分享,学习学习。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册 新浪微博登陆

本版积分规则

 

GMT+8, 2019-8-25 00:34 , Processed in 0.147530 second(s), 61 queries .

关闭

扫一扫加入
本版微信群