来源:百度文库 编辑:
偶看新闻 时间:2024/05/11 18:36:49
摘 要:文本聚类是搜索引擎和语义web的基本技术,本文和大家一起学习一下简单的文本聚类算法,可能不能直接用于实际应用中,但对于想学搜索技术的初学者还 是有一定入门作用的。这里会用到TF/IDF权重,用余弦夹角计算文本相似度,用方差计算两个数据间欧式距离,用k-means进行数据聚类等数学和统计 知识。关于这些概念可以去google,或者参考文本后的参考链接。 数据挖掘交友
思路:计算两篇文档的相似度,最简单的做法就是用提取文档的TF/IDF权重,然后用余弦定理计算两个多维向量的距离。能计算两个文本间的距离后,用标准的k-means算法就可以实现文本聚类了。 数据挖掘实验室
测试:首先我们准备以下数据
===================
奥运 拳击 入场券 基本 分罄 邹市明 夺冠 对手 浮出 水面
股民 要 清楚 自己 的 目的
印花税 之 股民 四季
杭州 股民 放 鞭炮 庆祝 印花税 下调
残疾 女 青年 入围 奥运 游泳 比赛 创 奥运 历史 两 项 第一
介绍 一 个 ASP.net MVC 系列 教程
在 asp.net 中 实现 观察者 模式 ,或 有 更 好 的 方法 (续)
输 大钱 的 股民 给 我们 启迪
Asp.Net 页面 执行 流程 分析
运动员 行李 将 “后 上 先 下” 奥运 相关 人员 行李 实名制
asp.net 控件 开发 显示 控件 内容
奥运 票务 网上 成功 订票 后 应 及时 到 银行 代售 网点 付款
某 心理 健康 站 开张 后 首 个 咨询 者 是 位 新 股民
ASP.NET 自定义 控件 复杂 属性 声明 持久性 浅析
==================
很明显以上数据可以分为三类:asp.net,奥运和股民,我们就写程序来实现它,各种算法的原理网上都有,我就大概只贴代码,声明一下,部分代码是从网 上直接抄的,k-means代码是我从一篇文章的java示例代码转换过来的,我给代码加了不少注释,希望能帮助大家理解。 数据挖掘论坛
以下是入口函数 数据挖掘论坛
static void Main(string[] args)
{ 数据挖掘实验室
//1、获取文档输入 string[] docs = getInputDocs("input.txt"); 数据挖掘论坛
if (docs.Length < 1)
{ 数据挖掘交友
Console.WriteLine("没有文档输入");
Console.Read();
return;数据挖掘交友
}
//2、初始化TFIDF测量器,用来生产每个文档的TFIDF权重 数据挖掘工具 TFIDFMeasure tf = new TFIDFMeasure(docs, new Tokeniser());
int K = 3; //聚成3个聚类数据挖掘交友
//3、生成k-means的输入数据,是一个联合数组,第一维表示文档个数,
//第二维表示所有文档分出来的所有词 数据挖掘交友 double[][] data = new double[docs.Length][];
int docCount = docs.Length; //文档个数 数据挖掘研究院 int dimension = tf.NumTerms;//所有词的数目 for (int i = 0; i < docCount; i++) 数据挖掘实验室
{
for (int j = 0; j < dimension; j++) 数据挖掘论坛
{
data[i] = tf.GetTermVector2(i); //获取第i个文档的TFIDF权重向量 数据挖掘工具 } } 数据挖掘研究院
//4、初始化k-means算法,第一个参数表示输入数据,第二个参数表示要聚成几个类 WawaKMeans kmeans = new WawaKMeans(data, K);数据挖掘研究院
//5、开始迭代 kmeans.Start();
数据挖掘论坛
//6、获取聚类结果并输出 WawaCluster[] clusters = kmeans.Clusters;
foreach (WawaCluster cluster in clusters) 数据挖掘实验室
{
List members = cluster.CurrentMembership;数据挖掘工具
Console.WriteLine("-----------------");
foreach (int i in members)数据挖掘交友
{
Console.WriteLine(docs[i]);数据挖掘论坛
}
} Console.Read(); 数据挖掘研究院
}
数据挖掘实验室
以下是分词器的主要代码
数据挖掘工具
/**//// 数据挖掘工具/// 以空白字符进行简单分词,并忽略大小写,
/// 实际情况中可以用其它中文分词算法
/// 数据挖掘交友
/// /// public IList Partition(string input) 数据挖掘研究院
{
Regex r=new Regex("([ \\t{}():;. \n])"); 数据挖掘工具
input=input.ToLower() ;
String [] tokens=r.Split(input); 数据挖掘工具
List filter=new List() ;数据挖掘研究院
for (int i=0; i < tokens.Length ; i++)数据挖掘工具
{
MatchCollection mc=r.Matches(tokens[i]);数据挖掘论坛
if (mc.Count <= 0 && tokens[i].Trim().Length > 0
&& !StopWordsHandler.IsStopword (tokens[i]) ) 数据挖掘论坛
filter.Add(tokens[i]) ;
}
return filter.ToArray();数据挖掘工具
}
以下是kmeans算法的基本代码 数据挖掘研究院
略。。 数据挖掘研究院
数据挖掘论坛
以下是聚类实体类的定义数据挖掘研究院
internal class WawaCluster
{数据挖掘论坛
public WawaCluster(int dataindex,double[] data)
{ 数据挖掘论坛
CurrentMembership.Add(dataindex);
Mean = data;
}数据挖掘研究院
/**//// 数据挖掘研究院
/// 该聚类的数据成员索引
///
internal List CurrentMembership = new List();数据挖掘论坛
/**////
/// 该聚类的中心 数据挖掘研究院
///
internal double[] Mean;
/**//// 数据挖掘工具
/// 该方法计算聚类对象的均值
///
/// 数据挖掘研究院
public void UpdateMean(double[][] coordinates)
{数据挖掘交友
// 根据 mCurrentMembership 取得原始资料点对象 coord ,该对象是 coordinates 的一个子集;
//然后取出该子集的均值;取均值的算法很简单,可以把 coordinates 想象成一个 m*n 的距阵 ,
//每个均值就是每个纵向列的取和平均值 , //该值保存在 mCenter 中 数据挖掘交友
for (int i = 0; i < CurrentMembership.Count; i++)数据挖掘交友
{
double[] coord = coordinates[CurrentMembership[i]]; 数据挖掘实验室
for (int j = 0; j < coord.Length; j++)
{数据挖掘工具
Mean[j] += coord[j]; // 得到每个纵向列的和;
} 数据挖掘论坛
for (int k = 0; k < Mean.Length; k++)
{数据挖掘研究院
Mean[k] /= coord.Length; // 对每个纵向列取平均值
} 数据挖掘实验室
}
}
}数据挖掘工具
数据挖掘工具
计算TF/IDF和利用余弦定理计算相似度的代码见完整版的代码下载,那两部分都是外国人写的,里面有它的联系方式,不懂的可以问他,反正我差不多懂了。 数据挖掘论坛
下面看看咱们的测试结果:
Iteration 0...
Iteration 1...
Iteration 2...
-----------------
奥运 拳击 入场券 基本 分罄 邹市明 夺冠 对手 浮出 水面
杭州 股民 放 鞭炮 庆祝 印花税 下调
残疾 女 青年 入围 奥运 游泳 比赛 创 奥运 历史 两 项 第一
运动员 行李 将 “后 上 先 下” 奥运 相关 人员 行李 实名制
奥运 票务 网上 成功 订票 后 应 及时 到 银行 代售 网点 付款
-----------------
股民 要 清楚 自己 的 目的
印花税 之 股民 四季
输 大钱 的 股民 给 我们 启迪
某 心理 健康 站 开张 后 首 个 咨询 者 是 位 新 股民
-----------------
介绍 一 个 ASP.net MVC 系列 教程
在 asp.net 中 实现 观察者 模式 ,或 有 更 好 的 方法 (续)
Asp.Net 页面 执行 流程 分析
asp.net 控件 开发 显示 控件 内容
ASP.NET 自定义 控件 复杂 属性 声明 持久性 浅析聚 类聚的非常准确,而且只迭代了3次,模型就收敛了,当然了这是最理想的效果,其实聚类的结果受好多种因素制约,提取特征的算法,随机初始化函数, kmeans算法的实现等,都有优化的地方,不信你把输入的数据的顺序改改,聚类结果就不一样了,或者把随机数的种子变一下,结果也不一样,k- means算法加入一些变异系数的调整,结果也不一样,提取特征的地方不用TF/IDF权重算法用别的,结果肯定也不一样。数据挖掘交友
完整代码里还有另一组测试数据,结果也很不错,我的意思是我的算法不是针对一组测试数据,而是针对好多数据都有不错的结果。 数据挖掘交友
总结:数学和英语真是写程序之根本呀,弄这个东西遇到了好多英语单词不会,查还查不出来,也理解不了,最后google一看,是个数学专用词,再搜索这个数学专用词的中文解释,发现还是理解不了那数学原理。所以还是得多学习数学和英语。 数据挖掘研究院
参考链接:
K-MEANS算法
http://beauty9235.javaeye.com/blog/161675
什么是变异系数
http://zhidao.baidu.com/question/15013015.html
TF/IDF实现
http://www.codeproject.com/KB/cs/tfidf.aspx
源码下载:WawaTextCluster.zip