文本挖掘理论（二）

    # -*- coding: utf-8 -*-
    '''
    02 feature_engineering
    
    ===分词与词性标注===
    
    ==分词基本方法==
    基于词典的方法
    	最大匹配法：利用索引加速，正向/逆向【汉语更有效】/双向最大匹配，最佳匹配（词典中的单词按照他们在文本种出现频次的大小）、联想-回溯法
    	最大概率法：（1）一个待切分的汉字串可能包含多种分词结果（2）将其中概率最大的那个作为该字串的分词结果.基于独立性假设、一元语法，P(W1) = P(有) * P(意见) * P(分歧)
    	最短路径法：在词图上选择一条词数最少的路径（好于单向最大匹配）
    	未登录词识别方法：数字（正则表达式、有限状态转移）/命名实体/形式词、离合词；识别一般方法：规则、概率统计
    基于标注的方法
    	由字构词(组词)
    	考虑了文字词语出现的频率信息，同时考虑上下文语境
    	基本步骤：
    		学习（训练）：所有的字根据预定义的特征进行词位特性的学习，获得一个训练模型；
    		词位标注：对待分串的每个字进行词位标注；
    		组合：根据词位定义获得最终的分词结果。
    	学习方法：
    		支持向量机（SVM）
    		最大熵（Maximum Entropy）
    		隐马模型（HMM）
    		最大熵隐马模型（MEMM）
    		条件随机场（CRFs）
    	优缺点：
    		优点：对歧义词和未登录词的识别都具有良好的效果；
    		缺点：训练周期较长，计算量较大。
    		
    ==词性标注==
    自动词性标注就是用计算机来自动地给文本中的词标注词性。
    	兼类词：具有多种词性的词
    标注技术路线
    	基于概率统计
    		根据同现概率来标注词性，以舍弃同现概率低的可能性前提的
    	基于规则：依靠上下文来判断兼类词、词性连坐
    	将统计方法和规则方法结合被认为是解决词性标注问题的最佳手段
    停用词
    	常用词
    	虚词
    	领域实词（数据库）
    词形变化
    '''
    '''
    ===文档模型===
    	布尔模型
    		每个词在一篇文档中是否出现，对应权值为0或1
    		文档检索->布尔逻辑运算
    		扩展布尔模型：p-norm模型[Salton et al.1983]
    	向量空间模型(VSM)
    		将文档表达为向量空间中的一个矢量或一个点
    		Term weights reflect the (estimated) importance of each term
    		tf-idf
    	概率模型（？）
    	统计语言模型(SLM)
    		语言就是其字母表上的某种概率分布，该分布反映了任何一个字母序列成为该语言的一个句子（或其他语言单元）的可能性，这个概率分布即为该语言的统计语言模型
    		词项序列的概率分布
    			n元模型（n-gram）:一个词的出现与否仅仅与其前面的n-1个词有关
    			三元模型（Trigram）(n=3)任何一个词的出现仅仅与前两个词有关
    			二元模型（Bigram）(n=2)仅仅与前一个词有关
    			一元模型（Unigram）(n=1)各词互相独立
    		数据稀疏问题->数据平滑
    			基本思想：从已发生事件的概率中扣除一部分，然后把这些“多余”的概率重新分配给那些未发生的事件（和已发生事件）
    				线性插值平滑(Linear Interpolated Smoothing)
    				退化平滑(Backing-off Smoothing)
    ===相似度计算===
    	基于VSM的相关度计算方法
    		欧氏距离（很少用）
    		向量内积值
    		向量间夹角余弦值
    			大量计算两两文档间相似都时，为降低计算量，先对文档进行向量进行单位化
    		Jaccard相似度
    		Disadvantages
    			assumption of term independence
    			lack the control of Boolean model
    	基于概率模型的相关度
    		Okapi系统
    '''
    '''
    ===文本序列分析===
    
    ==序列比较==
    四种基本情况：
    	（1）两条长度相近的序列相似找出序列的差别
    	（2）一条序列是否包含另一条序列(子序列)
    	（3）两条序列中是否有非常相同的子序列
    	（4）一条序列与另一条序列逆序相似
    相似度：
    	它是两个序列的函数，其值越大，表示两个序列越相似
    距离：
    	距离越大，则两个序列的相似度就越小
    	海明距离
    		直接距离计算的不足?反序、子序列、漂移等关系不能发现
    	编辑距离
    		用来计算从原串（s）转换到目标串(t)所需要的最少的插入，删除和替换的数目
    编辑操作
    	字符编辑操作可将一个序列转化为一个新序列
    	编辑操作的代价
    通过点矩阵进行序列比较
    
    ==Topic Segmentation（对文档分段）==
    	to search for parts of a text where the vocabulary shifts from one subtopic to another.
    	TextTiling method
    		先把文档分成块（tile），每块k个句子。
    		计算相邻块之间的相似度，用标准的文档相似度计算公式。
    		用结果绘图。非常相似处会出现波峰，很不相似的地方出现波谷。选择波谷处作为分界线，把块组成段，这些段很可能是有关同一个Sub topic的
    '''
    '''
    ===特征变换===
    ==隐语义分析(Latent Semantic Analysis，LSA)==
    	中心思想：用概念（或特征）代替词
    	基本方法：利用矩阵理论中的“奇异值分解（singular value decomposition,SVD）”技术，将词频矩阵转化为奇异矩阵（K×K）
    	基本步骤
建立词频矩阵，frequency matrix
    			词频矩阵：矩阵表示一组文档
    				行对应关键词t，列对应文档d向量
    				将每一个文档视为空间的一个向量
    				向量值反映单词t与文档d的关联度
计算frequency matrix的奇异值分解
    			分解frequency matrix成3个矩阵U，S，V。U和V是正交矩阵（U T U=I），S是奇异值的对角矩阵（K×K）
对于每一个文档 d，用排除了SVD中消除后的词的新的向量替换原有的向量
    			SVD基本思想：先旋转坐标轴在进行选维
用转换后的文档索引和相似度计算
    	
    ==LDA(Latent Dirichlet Allocation)==
    Topic model
    用一组词及其词频分布来刻画主题，并认为文本片段是从一个概率模型中生成的。
    '''