M
2010-9-17
16
特征选择(2)
term的熵：该值越大，说明分布越均匀，越有可能出 现在较多的类别中；该值越小，说明分布越倾斜，词 可能出现在较少的类别中
Entropy(t ) = ∑ P(ci | t ) log P(ci |KL距离(Kullback-Leibler divergence) ，反映了文本类别的概率分布和在出现了 某个特定词汇条件下的文本类别的概率分布之间的距 离，该值越大，词对文本类别分布的影响也大。 P(ci | t ) CE (t ) = ∑ P( ci | t ) log P(ci ) i
ij ij
2010-9-17
logN
∑[
j =1
N
TF TF ij log( ij )]) DF DF i i
15
特征选择(1)
基于DF
Term的DF小于某个阈值去掉(太少，没有代表性) Term的DF大于某个阈值也去掉(太多，没有区分度)
信息增益(Information Gain, IG)：该term为整 个分类所能提供的信息量(不考虑任何特征的 不考虑任何特征的 考虑该特征后的熵的差值) 熵和考虑该特征后的熵 考虑该特征后的熵
同义词：开心 高兴 兴奋 相关词cluster，word cluster：葛非/顾俊
N-gram，N元组：中国 国人 人民 民银 银行 某种规律性模式：比如某个window中出现的固 定模式
2010-9-17 12
主要的分词方法
最大匹配法（ MM法）：选取包含 选取包含6 最大匹配法（Maximum Matching method, MM法）：选取包含6-8个 汉字的符号串作为最大符号串， 汉字的符号串作为最大符号串，把最大符号串与词典中的单词条目 相匹配，如果不能匹配，就削掉一个汉字继续匹配， 相匹配，如果不能匹配，就削掉一个汉字继续匹配，直到在词典中 找到相应的单词为止。匹配的方向是从右向左。 找到相应的单词为止。匹配的方向是从右向左。 逆向最大匹配法（ RMM法）：匹配方向 逆向最大匹配法（Reverse Maximum method, RMM法）：匹配方向 MM法相反 是从左向右。实验表明：对于汉语来说， 法相反， 与MM法相反，是从左向右。实验表明：对于汉语来说，逆向最大匹 配法比最大匹配法更有效。 配法比最大匹配法更有效。 双向匹配法（BiBM法）：比较MM法 比较MM 双向匹配法（Bi-direction Matching method, BM法）：比较MM法 RMM法的分词结果 从而决定正确的分词。 法的分词结果， 与RMM法的分词结果，从而决定正确的分词。 最佳匹配法（ OM法）：将词典中的单 最佳匹配法（Optimum Matching method, OM法）：将词典中的单 词按它们在文本中的出现频度的大小排列，高频度的单词排在前， 词按它们在文本中的出现频度的大小排列，高频度的单词排在前， 频度低的单词排在后，从而提高匹配的速度。 频度低的单词排在后，从而提高匹配的速度。 联想-回溯法（AssociationAB法）：采用 联想-回溯法（Association-Backtracking method, AB法）：采用 联想和回溯的机制来进行匹配。 联想和回溯的机制来进行匹配。
TSV ( t , c j ) = r * log
P (t | c j ) , r 为出现 t 的 c j 类文档个数 P (t | c j )
log P ( t | c j ) log( 1 P ( t | c j )) | c j )) log P ( t | c j )
其他
Odds: log( 1 P ( t Term Strength:
2010-9-17 3
文本挖掘的背景（续）
文本挖掘与数据挖掘的区别： 文本挖掘：文档本身是半结构化的或非结构 化的，无确定形式并且缺乏机器可理解的语 义； 数据挖掘：其对象以数据库中的结构化数据 为主，并利用关系表等存储结构来发现知识 因此，数据挖掘的技术不适用于文本挖掘， 或至少需要预处理。
2010-9-17 4
提纲
文本挖掘的背景 文本挖掘的过程 特征抽取 特征选择 文本分类 文本聚类 模型评价
2010-9-17
5
文本挖掘的过程
特征的 建立
文档集
特征集 的缩减
学习与知识 模式的提取
模式质量 的评价
知识模式
文本挖掘的一般处理过程
2010-9-17
6
提纲
文本挖掘的背景 文本挖掘的过程
特征抽取 特征选择 文本分类 文本聚类 模型评价
V ( d ) = (t1, w1( d );...; ti , wi (d );...; tn , wn( d ))
权重计算，N个训练文档
WM*N= (wij)
词项的权重: tf(词频 词频=term 词项的权重: {0,1}, tf(词频=term frequency), tf*idf,
2010-9-17
10
文本表示
词频矩阵 行对应关键词t，列对应文档d 行对应关键词t，列对应文档d向量 将每一个文档视为空间向量v 将每一个文档视为空间向量v 向量值反映单词t与文档d 向量值反映单词t与文档d的关联度 矩阵元素可以是词频，也可以是布尔型。
表示文档词频的词频矩阵
d1 t1 t2 t3 t4
2010-9-17
国内外研究状况
2010-9-17 7
文本特征抽取
定义：文本特征指的是关于文本的元数据 分类：
描述性特征：文本的名称、日期、大小、类型等。 语义性特征：文本的作者、标题、机构、内容等。
V ( d ) = ( t 1, w1( d );...; t i , w i ( d );...; t n , w n ( d ))
d2
85 90 33 140
d3
35 76 160 70
d4
69 57 48 201
d5
15 13 221 16
d6
320 370 26 35
11
322 361 25 30
中文特征词(Term)的粒度
Character，字：中 Word，词：中国 Phrase，短语：中国人民银行 Concept，概念 Concept
Gain(t) = Entropy ( S ) Expected Entropy( S t ) = { ∑ i =1 P ( ci ) log P (ci )}
M
[ P ( t ){ ∑ i =1 P ( ci | t ) log P (ci | t )} +
M
P ( t ){ ∑ i =1 P ( ci | t ) log P (ci | t )}]
2010-9-17
13
英文特征词
一般采用keyword,无需分词,单词之间有空格分开。 停用词（stop word），指文档中出现的连词，介词，冠词等并无太 停用词 大意义的词。例如在英文中常用的停用词有the，a, it等；在中文中 常见的有“是”，“的”，“地”等。 索引词（标引词，关键祠）:可以用于指代文档内容的预选词语,一 般为名词或名词词组。 词干提取 countries => country，interesting => interest
∑ [TF
k
kj
* log( N / DFk )] 2
aij =
log(TFij + 1.0) * log( N / DFi )
∑ [log(TF
k
kj
+ 1.0) * log( N / DFk )]2
基于熵概念的权重(Entropy weighting)
称为term i的某种熵 如果term分布极度均匀：熵等于-1 只在一个文档中出现：熵等于0 a = log(TF + 1.0) * 1 + 1
2010-9-17
8
特征抽取(feature extraction)
预处理
去掉html一些tag标记 禁用词(stop words)去除、词根还原(stemming) (中文)分词、词性标注、短语识别、…
词频统计
TFi,j: 特征i在文档j中出现次数，词频(Term Frequency) DFi:所有文档集合中出现特征i的文档数目，文档频率(Document Frequency)
奇异值分解(SVD)：A=(aij)=UΣVT
AM*N, UM*R, ΣR*R(对角阵), VN*R, R<=MIN(M,N)
取Σ对角上的前k个元素，得Σk
Ak= UkΣkVkT, Uk由U的前k列组成，Vk由V的前k列组成 文档d在LSI对应的向量d’=dTUkΣ-1
在已有的LSI中增加新的word或者document，不需要 重新计算
m i =1
2010-9-17
I AVG (t ) = ∑ P (ci ) I (t , ci )
I MAX (t ) = max im 1 P(ci ) I (t , ci ) =
18
特征选择(4)
Robertson & Sparck Jones公式
RSJ ( t , c j ) = c j中出现 t 的概率 非 c j中出现 t 的概率 = log P (t | c j ) P (t | c j )
Folding-in 方法 SVD-updating方法
2010-9-17 23
提纲
文本挖掘的背景 文本挖掘的过程
数据清洗：去掉不合适的噪声文档或文档内垃圾数据
文本表示
向量空间模型
降维技术
特征选择(Feature Selection) 特征重构(Re-parameterisation，如LSI)
2010-9-17 9
文本表示
向量空间模型(Vector Space Model)