文本聚类 一个文本的中心怎么表示
发布网友
发布时间：2022-04-29 18:50
共2个回答
懂视网
时间：2022-04-08 15:32
简介
鉴于基于划分的文本聚类方法只能识别球形的聚类，因此本文对基于密度的文本聚类算法展开研究。DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种典型的基于密度的聚类方法，可以找出形状不规则的聚类，而且聚类时无需事先知道聚类的个数。
基本概念
DBSCAN算法中有两个核心参数：Eps和MinPts(文献与程序中经常使用)。前者定义为邻域半径，后者定义为核心对象的阈值。本文为了描述方便，下文将Eps和MinPts分别简记为E和M。
(1) E 邻域：给定对象半径E内的区域成为该对象的E邻域。该E邻域为球形，其半径的界定可以采用距离（欧式距离）、余弦相似度、Word2Vec等表征，本文实现采用余弦相似度来表征。
(2) 核心对象：若给定对象E 邻域内的对象（样本点）个数大于等于M，则称该对象为核心对象。
(3) 直接密度可达：给定一个对象集合D，若对象p在q的E 邻域内，且q是一个核心对象，则称对象p从对象q出发是直接密度可达的（directly density-reachable）。
(4) 密度可达：给定一个对象集合D，若存在一个对象链p1，p2，p3，...，pn，p1=q，pn=p，对于pi属于D，i属于1~n，p（i+1）是从pi关于E和M直接密度可达的，则称对象p从对象q关于E和M密度可达的。
(5) 密度相连：给定一个对象集合D，若存在对象o属于D，使对象p和q均从o关于E和M密度可达的，那么对于对象p到q是关于E和M密度相连的。
(6) 边界对象：给定一个对象集合D，若核心对象p中存在对象q，但是q对象自身并非核心对象，则称q为边界对象。
(7) 噪声对象：给定一个对象集合D，若对象o既不是核心对象，也不是边界对象，则称o为噪声对象。
图1 集合对象
如图1所示，其设定M=3，红色节点为核心对象，黄色节点为边界节点，蓝色为噪声节点。
DBSCAN算法不仅能对对象进行聚类，同时还能识别噪声对象，即不属于任何一个聚类。需要指出：密度可达是直接密度可达的传递闭包，这种关系是非对称的，只有核心对象之间相互密度可达；但是，密度相连是一种对称的关系。
DBSCAN的核心思想：寻找密度相连的最大集合，即从某个选定的核心对象（核心点）出发，不断向密度可达的区域扩张，从而得到一个包含核心对象和边界对象的最大化区域，区域中任意两点密度相连。
算法伪代码（参考维基百科）：
1 DBSCAN(D, eps, MinPts) {
2 C = 0
3 for each point P in dataset D {
4 if P is visited
5 continue next point
6 mark P as visited
7 NeighborPts = regionQuery(P, eps)
8 if sizeof(NeighborPts) < MinPts
9 mark P as NOISE
10 else {
11 C = next cluster
12 expandCluster(P, NeighborPts, C, eps, MinPts)
13 }
14 }
15 }
16
17 expandCluster(P, NeighborPts, C, eps, MinPts) {
18 add P to cluster C
19 for each point P‘ in NeighborPts {
20 if P‘ is not visited {
21 mark P‘ as visited
22 NeighborPts‘ = regionQuery(P‘, eps)
23 if sizeof(NeighborPts‘) >= MinPts
24 NeighborPts = NeighborPts joined with NeighborPts‘
25 }
26 if P‘ is not yet member of any cluster
27 add P‘ to cluster C
28 }
29 }
30
31 regionQuery(P, eps)
32 return all points within P‘s eps-neighborhood (including P)
程序源代码如下：
1 import java.util.List;
2
3 import com.gta.cosine.ElementDict;
4
5 public class DataNode {
6 private List<ElementDict> terms;
7 private boolean isVisited;
8 private int category;
9
10 public DataNode(List<ElementDict> terms)
11 {
12 this.terms = terms;
13 this.isVisited = false;
14 this.category = 0;
15 }
16
17
18 public void setVisitLabel(boolean isVisited)
19 {
20 this.isVisited = isVisited;
21 }
22
23
24 public void setCatagory(int category)
25 {
26 this.category = category;
27 }
28
29
30 public boolean getVisitLabel()
31 {
32 return isVisited;
33 }
34
35
36 public int getCategory()
37 {
38 return category;
39 }
40
41
42 public List<ElementDict> getAllElements()
43 {
44 return terms;
45 }
46
47 }
1 import java.util.List;
2 import java.util.ArrayList;
3
4 import com.gta.cosine.TextCosine;
5 import com.gta.cosine.ElementDict;
6
7 public class DBScan {
8 private double eps;
9 private int minPts;
10 private TextCosine cosine;
11 private int threshold;
12 private List<DataNode> dataNodes;
13 private int delta;
14
15 public DBScan()
16 {
17 this.eps = 0.20;
18 this.minPts = 3;
19 this.threshold = 10000;
20 this.cosine = new TextCosine();
21 this.delta = 0;
22 dataNodes = new ArrayList<DataNode>();
23 }
24
25
26 public DBScan(double eps, int minPts, int threshold)
27 {
28 this.eps = eps;
29 this.minPts = minPts;
30 this.threshold = threshold;
31 this.cosine = new TextCosine();
32 this.delta = 0;
33 dataNodes = new ArrayList<DataNode>();
34 }
35
36
37 public void setThreshold(int threshold)
38 {
39 this.threshold = threshold;
40 }
41
42
43 public int getThreshold()
44 {
45 return threshold;
46 }
47
48
49 public double getEps()
50 {
51 return eps;
52 }
53
54
55 public int getMinPts()
56 {
57 return minPts;
58 }
59
60
61 public List<DataNode> getNeighbors(DataNode p, List<DataNode> nodes)
62 {
63 List<DataNode> neighbors = new ArrayList<DataNode>();
64 List<ElementDict> vec1 = p.getAllElements();
65 List<ElementDict> vec2 = null;
66 double countDistance = 0;
67 for (DataNode node : nodes)
68 {
69 vec2 = node.getAllElements();
70 countDistance = cosine.analysisText(vec1, vec2);
71 if (countDistance >= eps)
72 {
73 neighbors.add(node);
74 }
75 }
76 return neighbors;
77 }
78
79
80 public List<DataNode> cluster(List<DataNode> nodes)
81 {
82 int category = 1;
83 for (DataNode node : nodes)
84 {
85 if (!node.getVisitLabel())
86 {
87 node.setVisitLabel(true);
88 List<DataNode> neighbors = getNeighbors(node, nodes);
89 if (neighbors.size() < minPts)
90 {
91 node.setCatagory(-1);
92 }
93 else
94 {
95 node.setCatagory(category);
96 expandCluster(neighbors, category, nodes);
97 }
98 }
99 category ++;
100 }
101
102 return nodes;
103 }
104
105
106 public void expandCluster(List<DataNode> neighbors, int category, List<DataNode> nodes)
107 {
108 for (DataNode node : neighbors)
109 {
110 if (!node.getVisitLabel())
111 {
112 node.setVisitLabel(true);
113 List<DataNode> newNeighbors = getNeighbors(node, nodes);
114 if (newNeighbors.size() >= minPts)
115 {
116 expandCluster(newNeighbors, category, nodes);
117 }
118 }
119
120 if (node.getCategory() <= 0) // not be any of category
121 {
122 node.setCatagory(category);
123 }
124 }
125 }
126
127
128 public void showCluster(List<DataNode> nodes)
129 {
130 for (DataNode node : nodes)
131 {
132 List<ElementDict> ed = node.getAllElements();
133 for (ElementDict e: ed)
134 {
135 System.out.print(e.getTerm() + " ");
136 }
137 System.out.println();
138 System.out.println("所属类别： "+ node.getCategory());
139 }
140 }
141
142
143 public void addDataNode(String s)
144 {
145 List<ElementDict> ed = cosine.tokenizer(s);
146 DataNode dataNode = new DataNode(ed);
147 dataNodes.add(dataNode);
148 delta ++;
149 }
150
151
152 public void analysis()
153 {
154 if (delta >= threshold)
155 {
156 showCluster(cluster(dataNodes));
157 delta = 0;
158 }
159 }
160 }
关于计算余弦相似度及其源代码，见本系列之文本挖掘之文本相似度判定。本文考虑到随着文本数量的递增，文本聚类结果会分化，即刚开始聚类的文本与后面文本数据相差甚远，本文非常粗略采用门限值进行限定，本文后续系列联合KMeans和DBSCAN进行解决，若有更好的方法，请联系我。
作者：志青云集
出处：http://www.cnblogs.com/lyssym
如果，您认为阅读这篇博客让您有些收获，不妨点击一下右下角的【推荐】。
如果，您希望更容易地发现我的新博客，不妨点击一下左下角的【关注我】。
如果，您对我的博客所讲述的内容有兴趣，请继续关注我的后续博客，我是【志青云集】。
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接。
文本挖掘之文本聚类（DBSCAN）
标签：
热心网友
时间：2022-04-08 12:40
为一种无监督的机器学习方法，聚
类由于不需要训练过程，以及不需要预先对文本手工标注类别，因此具有一定的灵活性和较高的自动化处理能力，已经成为对文本信息进行有效地组织、摘要和导航
的重要手段，为越来越多的研究人员所关注。一个文本表现为一个由文字和标点符号组成的字符串,由字或字符组成词,由词组成短语,进而形成句、段、节、章、
篇的结构。要使计算机能够高效地处理真是文本，就必须找到一种理想的形式化表示方法，这种表示一方面要能够真实地反应文档的内容(主题、领域或结构等)，
另一方面，要有对不同文档的区分能力。目前文本表示通常采用向量空间模型(vector space model,VSM)。
VSM法即向量空间模型
(Vector Space
Model)法，由Salton等人于60年代末提出。这是最早也是最出名的信息检索方面的数学模型。其基本思想是将文档表示为加权的特征向
量：D=D(T1，W1；T2，W2；…；Tn，Wn)，然后通过计算文本相似度的方法来确定待分样本的类别。当文本被表示为空间向量模型的时候，文本的
相似度就可以借助特征向量之间的内积来表示。最简单来说一个文档可以看成是由若干个单词组成的，每个单词转化成权值以后,
每个权值可以看成向量中的一个分量，那么一个文档可以看成是n维空间中的一个向量，这就是向量空间模型的由来。单词对应的权值可以通过TF-IDF加权技 术计算出来。
TF-IDF（term frequency–inverse document frequency）是一种用于资讯检索与文本挖掘的常用加权技术。TF-IDF是一种统计方法，用以评估一字词对于一个文件集或一个语料库中的
其中一份文件的重要程
度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。TF-IDF加权的各种形式
常被搜索引擎应用，作为文件与用户查询之间相关程度
的度量或评级。除了TF-IDF以外，互联网上的搜寻引擎还会使用基于连结分析的评级方法，以确定文件在搜寻结果中出现的顺序。
原理:
以上式子中 ni,j 是该词在文件dj中的出现次 数，而分母则是在文件dj中所 有字词的出现次数之和。
逆向文件频率（inverse document frequency，IDF）是一个词语普遍重要性的度量。某一特定词语的IDF，可以由总文件数目除以包含该词语之文件的数目，再将得到的商取对数得到：
其中
|D|：语料库中的文件总数
： 包含词语ti的文件数目（即的
文件数目）
然后
某一特定文件内的高词语频率，以及该词语在整个文件集合中的低文件频率，可以产生出高权重的TF-IDF。因此，TF-IDF倾向于过滤掉常见的词 语，保留重要的词语。
例子
有很多不同的数学公式可以用来计
算TF-IDF。这边的例子以上述的数学公式来计算。词频
(TF)
是一词语出现的次数除以该文件的总词语数。假如一篇文件的总词语数是100个，而词语“母牛”出现了3次，那么“母牛”一词在该文件中的词频就是
0.03 (3/100)。一个计算文件频率 (DF)
的方法是测定有多少份文件出现过“母牛”一词，然后除以文件集里包含的文件总数。所以，如果“母牛”一词在1,000份文件出现过，而文件总数是
10,000,000份的话，其逆向文件频率就是
9.21 ( ln(10,000,000 / 1,000) )。最后的TF-IDF的分数为0.28( 0.03 * 9.21)。
TF-IDF权重计算方法经常会和余
弦相似度（cosine similarity）一同使用于向 量空间模型中，用以判断两份文件之间的相
似性。学过向量代数的人都知道，向量实际上是*空间中有方向的线段。如果两个向量的方向一致，即夹角接近零，那么这两个向量就相近。而要确定两 个向量方向是否一致，这就要用到余弦定理计算向量的夹角了。
余弦定理对我们每个人都不陌生，它描述了三角形中任何一个夹角和三个边的关系，换句话说，给定三角形的三条边，我们可以用余弦定理求出三角形各个角的角 度。假定三角形的三条边为 a, b 和 c，对应的三个角为 A, B 和 C，那么角 A 的余弦 --
如果我们将三角形的两边 b 和 c 看成是两个向量，那么上述公式等价于
其中分母表示两个向量 b 和 c 的长度，分子表示两个向量的内积。举一个具体的例子，假如文本 X 和文本 Y 对应向量分别是
x1,x2,...,x64000 和
y1,y2,...,y64000,
那么它们夹角的余弦等于，
当两条文本向量夹角的余弦等于一时，这两个文本完全重复（用这个办法可以删除重复的网页）；当夹角的余弦接近于一时，两个文本相似，从而可以归成一类；夹 角的余弦越小，两个文本越不相关。
我们在中学学习余弦定理时，恐怕很难想象它可以用来对文本进行分类。
最后我们在对文本进行聚类时要用到数据挖掘中的Kmeans算法，聚类算法有很多种，这篇文章主要介绍Kmeans算法。K-MEANS算法:
k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对 象”（引力中心）来进行计算的。
k-means 算法的工作过程说明如下：
首先从n个 数据对象任意选择 k
个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然
后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数.
k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。
处理流程：
（ 1 ） 从 c 个 数据对象任意选择 k 个
对象作为初始聚类中心；
（ 2 ） 循 环（ 3 ） 到（ 4 ）
直到每个聚类不再发生变化为止；
（ 3 ） 根 据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；
（ 4 ） 重 新计算每个（有变化）聚类的均值（中心对象)
到这里这个文本聚类的小程序的核心思想就讲完了，总的来说大致步骤如 下：
(1)对各个文本分词,去除停用词
(2)通过TF-IDF方法获得文本向量的权值(每个文本向量的维数是 相同的,是所有文本单词的数目,这些单词如果有重复那只算一次,所以如果文本越多，向量的维数将会越大)
(3)通过K-means算法对文本进行分类
本人的文本小程序的结 果还算令人满意，对下面的实验用例的聚类结果还算是理想，但是每次执行的结果都不一样。其实聚类的结果受好多种因素制约，提取特征的算法，随机初始化函 数，kmeans算法的实现等，都有优化的地方，不信你把输入的数据的顺序改改，聚类结果就不一样了，或者把随机数的种子变一下，结果也不一样，k-
means算法加入一些变异系数的调整，结果也不一样，提取特征的地方不用TF/IDF权重算法用别的，结果肯定也不一样。
实验用例：
奥运拳击入场券基本分罄邹市明夺冠对手浮出水面
股民要清楚自己的目的
印花税之股民四季
杭州股民放鞭炮庆祝印花税下调
残疾女青年入围奥运游泳比赛创奥运历史两项第一
介绍一个ASP.netMVC系列教程
在asp.net中实现观察者模式,或有更好的方法(续)
输大钱的股民给我们启迪
Asp.Net页面执行流程分析
运动员行李将"后上先下"奥运相关人员行李实名制
asp.net控件开发显示控件内容
奥运票务网上成功订票后应及时到银行代售网点付款
某心理健康站开张后首个咨询者是位新股民
ASP.NET自定义控件复杂属性声明持久性浅析
以下是我在网上参考的资料：
http://www.cnblogs.com/onlytiancai/archive/2008/05/10/1191557.html
http://hi.baidu.com/zhumzhu/blog/item/fc49ef3d19b0a4c09f3d62a3.html
