机器学习常用数学公式汇总(一)

数据挖掘李新春 发表了文章 • 2 个评论 • 104 次浏览 • 2017-05-07 10:47 • 来自相关话题

    这次分享的是数学公式的总结,同之前的一样,由于公式的不容易编辑,采用了Latex生成了pdf文件,附件里面可以下载。而博客内容就只贴出了pdf转换的图片文件,放大之后就可以清楚看到其中内容。




 
    这次分享的是数学公式的总结,同之前的一样,由于公式的不容易编辑,采用了Latex生成了pdf文件,附件里面可以下载。而博客内容就只贴出了pdf转换的图片文件,放大之后就可以清楚看到其中内容。
formula1.png

 

Scala笔记

编程与开发王开新 发表了文章 • 4 个评论 • 84 次浏览 • 2017-05-06 21:57 • 来自相关话题

https://www.zybuluo.com/abbed/note/745613
ps:被命令式编程先入为主后再学函数式编程好难
 
https://www.zybuluo.com/abbed/note/745613
ps:被命令式编程先入为主后再学函数式编程好难
 

文本分类

数据挖掘李新春 发表了文章 • 0 个评论 • 115 次浏览 • 2017-04-30 21:24 • 来自相关话题

    由于之前在做文本分类的有关项目,这儿对文本分类的基本流程稍作总结。之前的项目是将十六万篇从WOS上下载的题录数据(包括AU、TI、ID、AB、SO、WC等字段),由于从WOS上下载数据时尽量保证了查全率,而查准率不太高,所以需要再从中挑出的确和研究主题相关的那部分题录数据。所以利用人工标注的数据当做训练集,这里的标注是指根据作者、主题、摘要等字段进行人工判断某一篇题录数据是否属于要研究的主题明确相关,所以这是个二分类问题。从这儿可以看出,其和垃圾邮件分类的基本形式差不多,自然而然就会想到文本分类的基本流程。所以下面介绍文本分类的几步操作,先说明一下,以下是对英文文本进行分类,某些地方不适合中文,但是基本流程类似(汉语难点在于分词操作)。
    文本分类有基于规则的分类和基于机器学习算法的分类两种。基于规则的大概可以理解为,通过该行业的专家制定一套规则,比如选取某些单词共现或频率高于阈值作为一个判断的依据,举个例子,比如某篇文献的题名出现了“soil”、“water”、“pollution”这三个单词,那么可以以60\%的概率断定这是一篇归为水污染主题的文章。这种基于规则的文本分类需要大量的专业知识和专业术语储备,并且费时费力。而基于机器学习的文本分类算法的主要思路则是将文本以某种方式转换为数值,然后利用朴素贝叶斯、支持向量机、决策树、集成学习、神经网络等算法进行训练。然而基于机器学习进行文本分类也是需要训练集作为支撑的,这就引发了文本分类的瓶颈--标注瓶颈问题,即需要专家事先进行人工标注数据集,这无疑也是非常耗时耗力的。当然标注瓶颈问题可以由半监督学习(Semi-supervised Learning)解决。除此之外,文本分类的另一难点就是文本到数值的转换过程和特征的提取了。
    文本分类首先要解决的是文本表示的问题,在信息检索领域,文本表示有布尔逻辑模型、向量空间模型、概率模型、潜在语义索引等表示方法。这里先给出几个名词:词(term)、文档(document)、文档集(document set)、词汇表(vocabulary)、文档向量、文档向量矩阵。词是经过分词、预处理后得到的文档最小单位,比如“dog”、“machin”,注意这里的“machin”为“machine”进行提取词干(stemming)预处理后得到的
结果;文档是一段文本或由几个字段里的文本拼凑在一起的文本进过预处理后得到的一个单词列表,比如[“cat”,“is”,“lovely”,...];文档集是所有文档的集合,可以看作是二维的矩阵;词汇表是从文档集中获取所有不重复的词构成的一个列表;文档向量是利用某种规则将文档转换为一个和词汇表一样大小的数值向量;文档向量矩阵是文档集里每一篇文档转换为文档向量之后得到的矩阵。这里个人称为文档向量和文档向量矩阵,或许有不准确之处,欢迎批评指正。下面据此,先简单介绍一下信息检索领域的几个模型:
    布尔逻辑模型: 词在文档里面出现则在构建文档向量时记为1,否则记为0。这样得到的文档向量的每一个分量全是0,1。比如词汇表为[“cat”,“dog”,“machin”,“learn”,“hard”],文档为[“machin”,“cat”],那么其转换的文档向量为[1,0,1,0,0]。在进行检索时,比如检索内容为“cat AND dog”,那么将文档向量代入得到“1 AND 0”,结果为False,所以此文档不匹配。由此可以看出布尔逻辑模型操作起来简单,但是效果不理想。
    向量空间模型(Vector Space Model): 相比于布尔逻辑模型,在构建文档向量时不仅仅只是判断其是否出现,而是利用了词在文档中出现的频次(词文档频率)、词逆向文档频率法(TF-IDF)等构建文档向量。在进行检索时,也不仅仅只是布尔操作,而是进行计算文档相似度,比如余弦相似度等。
    概率模型: 概率模型引入了贝叶斯分类,在检索时实质上是二元分类,相关或是不相关。但实际操作也没有分类的过程,而是对相关条件概率和非相关条件概率的比值进行排序,选择其排序前K个。
    潜在语义索引(Latent Semantic Indexing): 实质上是利用了奇异值分解对文档向量矩阵进行分解,选择其最大的几个奇异值对应的U和V进行分解,可以达到减少计算量和存储、降低噪声干扰等效果。关于奇异值分解,详细推导过程参见矩阵分解(一):奇异值分解。
    上面简单介绍了信息检索领域的文本表示方法。在文本分类中常用的就是词集模型(set-of-words)和词袋模型(bag-of-words),词集模型可以简单理解为布尔逻辑模型里面的文档向量表示方法,出现则为1,不出现则为0,不考虑频次等信息;词袋模型就相当于向量空间模型的文档向量表示法,最简单的就是统计词在文档中出现的频次。
    接下来便是文本分类的操作了,主要分为预处理、构建文档向量矩阵、特征选择、训练测试四个部分。
    预处理: 预处理操作包括分词、去除低频词、去除停用词(stop words)、提取词干(stemming)。在英文里面,分词主要是利用空格进行切分,同时还可考虑以分号、连字符等进行切分,当然也可以利用正则表达式进行匹配。去除低频词主要是为了提高分类效果、减少稀疏性、降低噪声影响,其主要思想是去除那些在所有文档出现频次小于某个阈值的单词,出现频次太小的单词对分类贡献不大,如不去除则会导致很多文档向量的分量为0,
另外还可以去除拼写错误的单词,降低噪声。去除停用词,即去除掉“is”、“he”等对分类无意义的词,停用词表可由网站http://www.ranks.nl/resources/stopwords.html获得;提取词干就是将“cat”,“cats”都统一变为“cat”等操作,降低数据之间的相关性。
    构建文档向量矩阵: 进过预处理操作,就得到了文档和文档集,将文档集里所有文档取并集,得到词汇表,也就是初步的特征集。根据特征集进行构建文档向量矩阵,如果只是简单采用词频法,则对每一篇文档,遍历词汇表,将词在文档中出现的频次作为文档向量对应分量的值即可。如果采用TF-IDF,其计算思想主要是:对于第i篇文档,如果词j在这个文档中出现的频次高,那么赋予其较大的权值,如果其在大部分文档中都出现了,那么其携带的分类信息就少了,那么赋予其较小的权值。用词在该文档中出现的次数即词频当作tf,用总的文档数量除以
包含该词的文档数量,再取对数,当作idf。文档i的文档向量的第j个分量w计算公式如下:






    特征选择:构建文档向量矩阵的同时也得到了词汇表,即特征集,很多时候,文档数量即样本数目很少,但是特征数量却很多。虽然经过了去除停用词、去除低频、提取词干等操作,但是仍然会有很多词汇被选入特征。特征选择是机器学习里面对预测结果影响很大的一块内容,有时通过优化算法、调参得到的模型改善却不如进行特征选择带来的改进大,由此也导致了特征选择是比较难以处理的一块内容。可以说,深度学习网络在全连接层之前进行的卷积、池化等操作就是特征提取的过程。这里,特征选择和特征提取并不是相同的概念,但二者目的相同,都是为了减少特征维数,避免维数灾难(Curse of Dimensionality)。文本特征选择的方法主要有:对于单个特征采用信息增益、ROC曲线、互信息、期望交叉熵、统计检验等,对于多个特征的选择包括顺序前向选择、顺序后向选择、浮动搜索技术等。
        信息增益:记D位标签列,对每个特征A基于以下公式进行计算,最后对每个特征的信息增益进行排序可得到前K个特征:






        ROC曲线:对每个特征A和标签D,对特征A取值的范围进行取阈值,然后以此阈值分类,计算分类结果的召回率和假阳率,得到ROC曲线上的一个点,逐步将所有的阈值得到的点进行计算得到AUC。最后对AUC进行排序,得到特征的重要性排序。
        统计检验:主要是利用卡方检验、t检验等操作判断类的可分性等。
        顺序前向选择:这是对特征子集的选取,假设现在先选择了k个特征,下面对剩下的特征进行遍历,将特征加入k个特征构成k+1维的特征集。选择使得评价函数最优的那个特征作为第k+1个特征,这里的评价函数主要包括filter和wrapper两种(目前尚未接触过这部分内容,这里先省略对其的叙述)。逐步选择,直到选择K个特征。
    其余特征选择算法不再详细叙述。特征提取算法主要包括主成分分析,即利用PCA进行降维等。
    训练测试:当文档向量矩阵构建完成以及特征提取也完成之后,就可以利用算法进行训练测试了,贝叶斯分类器、支持向量机、随机森林、集成学习算法等都是文本分类领域适用的算法,个人项目中支持向量机结果最好,随机森林次之。
    最后就是编程实现了,还好sklearn包提供了很多便捷的工具可以很快搭建出来一个小型的文本分类器。
    先贴出来代码,代码文件见附件text.py(打包在text.zip),版本是python3.5,环境是Anaconda,需要调用的包有sklearn.feature_extraction.text里的CountVectorizer、TfidfVectorizer、numpy、nltk.stem。其中nltk.stem是进行词干提取的包,在anaconda里面没有集成,下载官网为http://www.nltk.org/install.html。官网上说在windows下安装需要Python3.5并且只适用于32位,还有的博客说不能直接用pip install安装,但是实际上,在anaconda命令行下直接conda install nltk即可成功。
    程序测试用数据为['This is a book about machine learning.',  'It\'s a cat classified by manual labeling.',  'A newspaper about machine learning.',  'Cats are lovely,while dogs are not.',  'Reading books about machine learning,with a cat at hand.'],这是一个包括五篇文献的文档集。
    关键代码展示如下:其具体内容和其余实验代码以及输出结果可参考博客代码内容(代码展示效果不好)或附件text.py。
    # 综合了去除低频词、去除停用词、词干提取、tfidf的文档向量构建函数,只需传入原始文档即可
    def tfidf_stem_stop_words_vector(text_data):
    # 利用sklearn提供的TfidfVectorizer构造词向量提取器,这个类在上述函数中用到
    class StemmedTfidfVectorizer(TfidfVectorizer):
   
代码文件text.py内容:   
#coding: UTF-8
#encoding: UTF-8
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.feature_extraction.text import TfidfVectorizer
import numpy as np
import nltk.stem as ns


def get_simple_data():
    text_data = ['This is a book about machine learning.',
                 'It\'s a cat classified by manual labeling.',
                 'A newspaper about machine learning.',
                 'Cats are lovely,while dogs are not.',
                 'Reading books about machine learning,with a cat at hand.']
    return text_data
# 先不做任何处理,只是简单对文档进行分词
def simple_text_preprocess(text_data):
    vectorizer = CountVectorizer(min_df=1)                 # min_df代指单词在所有文档中出现的频率小于min_df的都被过滤掉;如果是分数,则按频率计算
    print(vectorizer)
    words_vector = vectorizer.fit_transform(text_data)     # 在文本集中进行提取词向量
    words_feature_names = vectorizer.get_feature_names()   # 得到选取的特征
    print('feature_names:',words_feature_names)
    print('words_vector:',words_vector.toarray())          # 输出词向量,不用toarray()则输出稀疏矩阵;有toarray()则输出完整矩阵
    
    new_text = ['Machine learning is hard to learn for a cat.',
                 'Cat is lazy.']
    new_words_vector = vectorizer.transform(new_text)      # 对新的文本数据进行转换
    print('new_text_words_vector:',new_words_vector.toarray())
# 去除停用词进行分词
def stop_words_text_preprocess(text_data):    
    # 去除停用词之后再进行以便操作
    vectorizer = CountVectorizer(min_df=1,stop_words='english')   # 简单加入"stop_words"即可
    words_vector = vectorizer.fit_transform(text_data)     # 在文本集中进行提取词向量
    words_feature_names = vectorizer.get_feature_names()   # 得到选取的特征
    print('remove_stopwords,feature_names:',words_feature_names)
    print('remove_stopwords,words_vector:',words_vector.toarray())          # 输出词向量,不用toarray()则输出稀疏矩阵;有toarray()则输出完整矩阵
    
    new_text = ['Machine learning is hard to learn for a cat.',
                 'Cat is lazy.']
    new_words_vector = vectorizer.transform(new_text)      # 对新的文本数据进行转换
    print('remove_stopwords,new_text_words_vector:',new_words_vector.toarray())
# 再加上提取词干
def stem_stop_text_preprocess(text_data):
    # stemming提取词干
    st = ns.SnowballStemmer('english')    # 构造提取器
    print('imaging->',st.stem('imaging'),'machine->',st.stem('machine'),'learning->',st.stem('learning'))
    
    # 根据自己构造的StemmedCountVectorizer进行对文本集提取词干
    vectorizer = StemmedCountVectorizer(min_df=1,stop_words='english')
    words_vector = vectorizer.fit_transform(text_data)     # 在文本集中进行提取词向量
    words_feature_names = vectorizer.get_feature_names()   # 得到选取的特征
    print('remove_stopwords,feature_names:',words_feature_names)
    print('remove_stopwords,words_vector:',words_vector)          # 输出词向量,不用toarray()则输出稀疏矩阵;有toarray()则输出完整矩阵
                                
    new_text = ['Machine learning is hard to learn for a cat.',
                 'Cat is lazy.']
    new_words_vector = vectorizer.transform(new_text)      # 对新的文本数据进行转换
    print('remove_stopwords,new_text_words_vector:',new_words_vector)
# 去除停用词的词向量提取器
class StemmedCountVectorizer(CountVectorizer):
    def build_analyzer(self):
        english_stemmer = ns.SnowballStemmer('english')
        analyzer = super(StemmedCountVectorizer,self).build_analyzer()
        return lambda doc: (english_stemmer.stem(w) for w in analyzer(doc))

# 自己实现TFIDF,输入参数为某个要求tfidf的单词,其所在的文档,所有文档集合
def tfidf(term,doc,corpus):
    tf = doc.count(term)/len(doc)                    # 文档频率,单词在其所属文档中出现的频率
    num_docs_with_term = len([d for d in corpus if term in d]) # 包含这个单词的文档总数
    idf = np.log(len(corpus)/num_docs_with_term)     # 文档逆频率,总的文档数除以包含这个单词的文档总数,再取对数
    return tf*idf     
# 测试自己实现的tfidf
def test_tfidf():
    doc = ['cat','cat','dog','dog','machin','learn']
    corpus = [['cat','machin','learn'],
              ['machin','learn'],
              ['cat','learn'],
              ['dog','machin','learn'],
              ['cat','cat','dog','dog','machin','learn']]
    for term in set(doc):
        print('term,tfidf:',term,tfidf(term,doc,corpus))
# 再加入tfidf进行处理
def tfidf_stem_stop_words_vector(text_data):
    # stemming提取词干
    st = ns.SnowballStemmer('english')    # 构造提取器
    print('imaging->',st.stem('imaging'),'machine->',st.stem('machine'),'learning->',st.stem('learning'))
    
    # 根据自己构造的StemmedTfidfVectorizer构造tfidf词向量
    vectorizer = StemmedTfidfVectorizer(min_df=1,stop_words='english',decode_error='ignore') # 忽略编码错误
    words_vector = vectorizer.fit_transform(text_data)     # 在文本集中进行提取词向量
    words_feature_names = vectorizer.get_feature_names()   # 得到选取的特征
    print('remove_stopwords,feature_names:',words_feature_names)
    print('remove_stopwords,words_vector:',words_vector)          # 输出词向量,不用toarray()则输出稀疏矩阵;有toarray()则输出完整矩阵
                                
    new_text = ['Machine learning is hard to learn for a cat.',
                 'Cat is lazy.']
    new_words_vector = vectorizer.transform(new_text)      # 对新的文本数据进行转换
    print('remove_stopwords,new_text_words_vector:',new_words_vector)
# 利用sklearn提供的TfidfVectorizer构造词向量提取器
class StemmedTfidfVectorizer(TfidfVectorizer):
    def build_analyzer(self):
        english_stemmer = ns.SnowballStemmer('english')
        analyzer = super(TfidfVectorizer,self).build_analyzer()
        return lambda doc: (english_stemmer.stem(w) for w in analyzer(doc))

# 简单计算欧氏距离
def dist_raw(v1,v2):
    delta = v1 - v2
    return np.linalg.norm(delta.toarray())


if __name__ == "__main__":
    text_data_1 = get_simple_data()
    #simple_text_preprocess(text_data_1)
    #stop_words_text_preprocess(text_data_1)
    #stem_stop_text_preprocess(text_data_1)
    #test_tfidf()
    tfidf_stem_stop_words_vector(text_data_1)
  
    代码文件到此结束,下面是实例输出结果:
'''
    text_preprocess(text_data_1)输出结果:
    
    CountVectorizer的详细用法:
        analyzer是表示基于word进行分词、并且以token_pattern为正则进行分词这里的u'(?u)\\b\\w\\w+\\b'
        stop_words指是否使用停用词
        lowercase是先将所有变成小写
        
    CountVectorizer(analyzer=u'word', binary=False, decode_error=u'strict',
        dtype=<type 'numpy.int64'>, encoding=u'utf-8', input=u'content',
        lowercase=True, max_df=1.0, max_features=None, min_df=1,
        ngram_range=(1, 1), preprocessor=None, stop_words=None,
        strip_accents=None, token_pattern=u'(?u)\\b\\w\\w+\\b',
        tokenizer=None, vocabulary=None)
    ('feature_names:', [u'about', u'are', u'at', u'book', u'books', u'by', u'cat', u'cats', u'classified', u'dogs', u'hand', u'is', u'it', u'labeling', u'learning', u'lovely', u'machine', u'manual', u'newspaper', u'not', u'reading', u'this', u'while', u'with'])
    ('words_vector:', array([[1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1,
        0, 0],
       [0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0,
        0, 0],
       [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0,
        0, 0],
       [0, 2, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0,
        1, 0],
       [1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0,
        0, 1]], dtype=int64))
    ('new_text_words_vector:', array([[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0,
        0, 0],
       [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0]], dtype=int64))
    
    stop_words_text_preprocess(text_data_1)输出结果:
    ('remove_stopwords,feature_names:', [u'book', u'books', u'cat', u'cats', u'classified', u'dogs', u'hand', u'labeling', u'learning', u'lovely', u'machine', u'manual', u'newspaper', u'reading'])
    ('remove_stopwords,words_vector:', array([[1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
       [0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0],
       [0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0],
       [0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1]], dtype=int64))
    ('remove_stopwords,new_text_words_vector:', array([[0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
       [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], dtype=int64))
    
    stem_stop_text_preprocess(text_data_1)输出结果:
    imaging-> imag machine-> machin learning-> learn
    remove_stopwords,feature_names: ['book', 'cat', 'classifi', 'dog', 'hand', 'label', 'learn', 'love', 'machin', 'manual', 'newspap', 'read']
    remove_stopwords,words_vector:   (0, 6) 1
      (0, 8)        1
      (0, 0)        1
      (1, 5)        1
      (1, 9)        1
      (1, 2)        1
      (1, 1)        1
      (2, 10)       1
      (2, 6)        1
      (2, 8)        1
      (3, 3)        1
      (3, 7)        1
      (3, 1)        1
      (4, 4)        1
      (4, 11)       1
      (4, 1)        1
      (4, 6)        1
      (4, 8)        1
      (4, 0)        1
    remove_stopwords,new_text_words_vector:   (0, 1)        1
      (0, 6)        2
      (0, 8)        1
      (1, 1)        1
    
    text_tfidf()输出结果:
    term,tfidf: learn 0.0
    term,tfidf: machin 0.0371905918857
    term,tfidf: cat 0.170275207922
    term,tfidf: dog 0.305430243958
    
    tfidf_stem_stop_words_vector(text_data_1)输出结果:
    imaging-> imag machine-> machin learning-> learn
    remove_stopwords,feature_names: ['book', 'cat', 'classifi', 'dog', 'hand', 'label', 'learn', 'love', 'machin', 'manual', 'newspap', 'read']
    remove_stopwords,words_vector:   (0, 0) 0.648462625687
      (0, 8)        0.538282557346
      (0, 6)        0.538282557346
      (1, 1)        0.36063832635
      (1, 2)        0.538497910106
      (1, 9)        0.538497910106
      (1, 5)        0.538497910106
      (2, 8)        0.486240416592
      (2, 6)        0.486240416592
      (2, 10)       0.726044430146
      (3, 1)        0.427992922683
      (3, 7)        0.639070441396
      (3, 3)        0.639070441396
      (4, 0)        0.40357561577
      (4, 8)        0.335004217566
      (4, 6)        0.335004217566
      (4, 1)        0.335004217566
      (4, 11)       0.500221573402
      (4, 4)        0.500221573402
    remove_stopwords,new_text_words_vector:   (0, 8)        0.408248290464
      (0, 6)        0.816496580928
      (0, 1)        0.408248290464
      (1, 1)        1.0
'''

  查看全部
    由于之前在做文本分类的有关项目,这儿对文本分类的基本流程稍作总结。之前的项目是将十六万篇从WOS上下载的题录数据(包括AU、TI、ID、AB、SO、WC等字段),由于从WOS上下载数据时尽量保证了查全率,而查准率不太高,所以需要再从中挑出的确和研究主题相关的那部分题录数据。所以利用人工标注的数据当做训练集,这里的标注是指根据作者、主题、摘要等字段进行人工判断某一篇题录数据是否属于要研究的主题明确相关,所以这是个二分类问题。从这儿可以看出,其和垃圾邮件分类的基本形式差不多,自然而然就会想到文本分类的基本流程。所以下面介绍文本分类的几步操作,先说明一下,以下是对英文文本进行分类,某些地方不适合中文,但是基本流程类似(汉语难点在于分词操作)。
    文本分类有基于规则的分类和基于机器学习算法的分类两种。基于规则的大概可以理解为,通过该行业的专家制定一套规则,比如选取某些单词共现或频率高于阈值作为一个判断的依据,举个例子,比如某篇文献的题名出现了“soil”、“water”、“pollution”这三个单词,那么可以以60\%的概率断定这是一篇归为水污染主题的文章。这种基于规则的文本分类需要大量的专业知识和专业术语储备,并且费时费力。而基于机器学习的文本分类算法的主要思路则是将文本以某种方式转换为数值,然后利用朴素贝叶斯、支持向量机、决策树、集成学习、神经网络等算法进行训练。然而基于机器学习进行文本分类也是需要训练集作为支撑的,这就引发了文本分类的瓶颈--标注瓶颈问题,即需要专家事先进行人工标注数据集,这无疑也是非常耗时耗力的。当然标注瓶颈问题可以由半监督学习(Semi-supervised Learning)解决。除此之外,文本分类的另一难点就是文本到数值的转换过程和特征的提取了。
    文本分类首先要解决的是文本表示的问题,在信息检索领域,文本表示有布尔逻辑模型、向量空间模型、概率模型、潜在语义索引等表示方法。这里先给出几个名词:词(term)、文档(document)、文档集(document set)、词汇表(vocabulary)、文档向量、文档向量矩阵。词是经过分词、预处理后得到的文档最小单位,比如“dog”、“machin”,注意这里的“machin”为“machine”进行提取词干(stemming)预处理后得到的
结果;文档是一段文本或由几个字段里的文本拼凑在一起的文本进过预处理后得到的一个单词列表,比如[“cat”,“is”,“lovely”,...];文档集是所有文档的集合,可以看作是二维的矩阵;词汇表是从文档集中获取所有不重复的词构成的一个列表;文档向量是利用某种规则将文档转换为一个和词汇表一样大小的数值向量;文档向量矩阵是文档集里每一篇文档转换为文档向量之后得到的矩阵。这里个人称为文档向量和文档向量矩阵,或许有不准确之处,欢迎批评指正。下面据此,先简单介绍一下信息检索领域的几个模型:
    布尔逻辑模型: 词在文档里面出现则在构建文档向量时记为1,否则记为0。这样得到的文档向量的每一个分量全是0,1。比如词汇表为[“cat”,“dog”,“machin”,“learn”,“hard”],文档为[“machin”,“cat”],那么其转换的文档向量为[1,0,1,0,0]。在进行检索时,比如检索内容为“cat AND dog”,那么将文档向量代入得到“1 AND 0”,结果为False,所以此文档不匹配。由此可以看出布尔逻辑模型操作起来简单,但是效果不理想。
    向量空间模型(Vector Space Model): 相比于布尔逻辑模型,在构建文档向量时不仅仅只是判断其是否出现,而是利用了词在文档中出现的频次(词文档频率)、词逆向文档频率法(TF-IDF)等构建文档向量。在进行检索时,也不仅仅只是布尔操作,而是进行计算文档相似度,比如余弦相似度等。
    概率模型: 概率模型引入了贝叶斯分类,在检索时实质上是二元分类,相关或是不相关。但实际操作也没有分类的过程,而是对相关条件概率和非相关条件概率的比值进行排序,选择其排序前K个。
    潜在语义索引(Latent Semantic Indexing): 实质上是利用了奇异值分解对文档向量矩阵进行分解,选择其最大的几个奇异值对应的U和V进行分解,可以达到减少计算量和存储、降低噪声干扰等效果。关于奇异值分解,详细推导过程参见矩阵分解(一):奇异值分解
    上面简单介绍了信息检索领域的文本表示方法。在文本分类中常用的就是词集模型(set-of-words)和词袋模型(bag-of-words),词集模型可以简单理解为布尔逻辑模型里面的文档向量表示方法,出现则为1,不出现则为0,不考虑频次等信息;词袋模型就相当于向量空间模型的文档向量表示法,最简单的就是统计词在文档中出现的频次。
    接下来便是文本分类的操作了,主要分为预处理、构建文档向量矩阵、特征选择、训练测试四个部分。
    预处理: 预处理操作包括分词、去除低频词、去除停用词(stop words)、提取词干(stemming)。在英文里面,分词主要是利用空格进行切分,同时还可考虑以分号、连字符等进行切分,当然也可以利用正则表达式进行匹配。去除低频词主要是为了提高分类效果、减少稀疏性、降低噪声影响,其主要思想是去除那些在所有文档出现频次小于某个阈值的单词,出现频次太小的单词对分类贡献不大,如不去除则会导致很多文档向量的分量为0,
另外还可以去除拼写错误的单词,降低噪声。去除停用词,即去除掉“is”、“he”等对分类无意义的词,停用词表可由网站http://www.ranks.nl/resources/stopwords.html获得;提取词干就是将“cat”,“cats”都统一变为“cat”等操作,降低数据之间的相关性。
    构建文档向量矩阵: 进过预处理操作,就得到了文档和文档集,将文档集里所有文档取并集,得到词汇表,也就是初步的特征集。根据特征集进行构建文档向量矩阵,如果只是简单采用词频法,则对每一篇文档,遍历词汇表,将词在文档中出现的频次作为文档向量对应分量的值即可。如果采用TF-IDF,其计算思想主要是:对于第i篇文档,如果词j在这个文档中出现的频次高,那么赋予其较大的权值,如果其在大部分文档中都出现了,那么其携带的分类信息就少了,那么赋予其较小的权值。用词在该文档中出现的次数即词频当作tf,用总的文档数量除以
包含该词的文档数量,再取对数,当作idf。文档i的文档向量的第j个分量w计算公式如下:

tfidf.png


    特征选择:构建文档向量矩阵的同时也得到了词汇表,即特征集,很多时候,文档数量即样本数目很少,但是特征数量却很多。虽然经过了去除停用词、去除低频、提取词干等操作,但是仍然会有很多词汇被选入特征。特征选择是机器学习里面对预测结果影响很大的一块内容,有时通过优化算法、调参得到的模型改善却不如进行特征选择带来的改进大,由此也导致了特征选择是比较难以处理的一块内容。可以说,深度学习网络在全连接层之前进行的卷积、池化等操作就是特征提取的过程。这里,特征选择和特征提取并不是相同的概念,但二者目的相同,都是为了减少特征维数,避免维数灾难(Curse of Dimensionality)。文本特征选择的方法主要有:对于单个特征采用信息增益、ROC曲线、互信息、期望交叉熵、统计检验等,对于多个特征的选择包括顺序前向选择、顺序后向选择、浮动搜索技术等。
        信息增益:记D位标签列,对每个特征A基于以下公式进行计算,最后对每个特征的信息增益进行排序可得到前K个特征:

infogain.png


        ROC曲线:对每个特征A和标签D,对特征A取值的范围进行取阈值,然后以此阈值分类,计算分类结果的召回率和假阳率,得到ROC曲线上的一个点,逐步将所有的阈值得到的点进行计算得到AUC。最后对AUC进行排序,得到特征的重要性排序。
        统计检验:主要是利用卡方检验、t检验等操作判断类的可分性等。
        顺序前向选择:这是对特征子集的选取,假设现在先选择了k个特征,下面对剩下的特征进行遍历,将特征加入k个特征构成k+1维的特征集。选择使得评价函数最优的那个特征作为第k+1个特征,这里的评价函数主要包括filter和wrapper两种(目前尚未接触过这部分内容,这里先省略对其的叙述)。逐步选择,直到选择K个特征。
    其余特征选择算法不再详细叙述。特征提取算法主要包括主成分分析,即利用PCA进行降维等。
    训练测试:当文档向量矩阵构建完成以及特征提取也完成之后,就可以利用算法进行训练测试了,贝叶斯分类器、支持向量机、随机森林、集成学习算法等都是文本分类领域适用的算法,个人项目中支持向量机结果最好,随机森林次之。
    最后就是编程实现了,还好sklearn包提供了很多便捷的工具可以很快搭建出来一个小型的文本分类器。
    先贴出来代码,代码文件见附件text.py(打包在text.zip),版本是python3.5,环境是Anaconda,需要调用的包有sklearn.feature_extraction.text里的CountVectorizer、TfidfVectorizer、numpy、nltk.stem。其中nltk.stem是进行词干提取的包,在anaconda里面没有集成,下载官网为http://www.nltk.org/install.html。官网上说在windows下安装需要Python3.5并且只适用于32位,还有的博客说不能直接用pip install安装,但是实际上,在anaconda命令行下直接conda install nltk即可成功。
    程序测试用数据为['This is a book about machine learning.',  'It\'s a cat classified by manual labeling.',  'A newspaper about machine learning.',  'Cats are lovely,while dogs are not.',  'Reading books about machine learning,with a cat at hand.'],这是一个包括五篇文献的文档集。
    关键代码展示如下:其具体内容和其余实验代码以及输出结果可参考博客代码内容(代码展示效果不好)或附件text.py。
    # 综合了去除低频词、去除停用词、词干提取、tfidf的文档向量构建函数,只需传入原始文档即可
    def tfidf_stem_stop_words_vector(text_data):
    # 利用sklearn提供的TfidfVectorizer构造词向量提取器,这个类在上述函数中用到
    class StemmedTfidfVectorizer(TfidfVectorizer):
   
代码文件text.py内容:   
#coding: UTF-8
#encoding: UTF-8
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.feature_extraction.text import TfidfVectorizer
import numpy as np
import nltk.stem as ns


def get_simple_data():
    text_data = ['This is a book about machine learning.',
                 'It\'s a cat classified by manual labeling.',
                 'A newspaper about machine learning.',
                 'Cats are lovely,while dogs are not.',
                 'Reading books about machine learning,with a cat at hand.']
    return text_data
# 先不做任何处理,只是简单对文档进行分词
def simple_text_preprocess(text_data):
    vectorizer = CountVectorizer(min_df=1)                 # min_df代指单词在所有文档中出现的频率小于min_df的都被过滤掉;如果是分数,则按频率计算
    print(vectorizer)
    words_vector = vectorizer.fit_transform(text_data)     # 在文本集中进行提取词向量
    words_feature_names = vectorizer.get_feature_names()   # 得到选取的特征
    print('feature_names:',words_feature_names)
    print('words_vector:',words_vector.toarray())          # 输出词向量,不用toarray()则输出稀疏矩阵;有toarray()则输出完整矩阵
    
    new_text = ['Machine learning is hard to learn for a cat.',
                 'Cat is lazy.']
    new_words_vector = vectorizer.transform(new_text)      # 对新的文本数据进行转换
    print('new_text_words_vector:',new_words_vector.toarray())
# 去除停用词进行分词
def stop_words_text_preprocess(text_data):    
    # 去除停用词之后再进行以便操作
    vectorizer = CountVectorizer(min_df=1,stop_words='english')   # 简单加入"stop_words"即可
    words_vector = vectorizer.fit_transform(text_data)     # 在文本集中进行提取词向量
    words_feature_names = vectorizer.get_feature_names()   # 得到选取的特征
    print('remove_stopwords,feature_names:',words_feature_names)
    print('remove_stopwords,words_vector:',words_vector.toarray())          # 输出词向量,不用toarray()则输出稀疏矩阵;有toarray()则输出完整矩阵
    
    new_text = ['Machine learning is hard to learn for a cat.',
                 'Cat is lazy.']
    new_words_vector = vectorizer.transform(new_text)      # 对新的文本数据进行转换
    print('remove_stopwords,new_text_words_vector:',new_words_vector.toarray())
# 再加上提取词干
def stem_stop_text_preprocess(text_data):
    # stemming提取词干
    st = ns.SnowballStemmer('english')    # 构造提取器
    print('imaging->',st.stem('imaging'),'machine->',st.stem('machine'),'learning->',st.stem('learning'))
    
    # 根据自己构造的StemmedCountVectorizer进行对文本集提取词干
    vectorizer = StemmedCountVectorizer(min_df=1,stop_words='english')
    words_vector = vectorizer.fit_transform(text_data)     # 在文本集中进行提取词向量
    words_feature_names = vectorizer.get_feature_names()   # 得到选取的特征
    print('remove_stopwords,feature_names:',words_feature_names)
    print('remove_stopwords,words_vector:',words_vector)          # 输出词向量,不用toarray()则输出稀疏矩阵;有toarray()则输出完整矩阵
                                
    new_text = ['Machine learning is hard to learn for a cat.',
                 'Cat is lazy.']
    new_words_vector = vectorizer.transform(new_text)      # 对新的文本数据进行转换
    print('remove_stopwords,new_text_words_vector:',new_words_vector)
# 去除停用词的词向量提取器
class StemmedCountVectorizer(CountVectorizer):
    def build_analyzer(self):
        english_stemmer = ns.SnowballStemmer('english')
        analyzer = super(StemmedCountVectorizer,self).build_analyzer()
        return lambda doc: (english_stemmer.stem(w) for w in analyzer(doc))

# 自己实现TFIDF,输入参数为某个要求tfidf的单词,其所在的文档,所有文档集合
def tfidf(term,doc,corpus):
    tf = doc.count(term)/len(doc)                    # 文档频率,单词在其所属文档中出现的频率
    num_docs_with_term = len([d for d in corpus if term in d]) # 包含这个单词的文档总数
    idf = np.log(len(corpus)/num_docs_with_term)     # 文档逆频率,总的文档数除以包含这个单词的文档总数,再取对数
    return tf*idf     
# 测试自己实现的tfidf
def test_tfidf():
    doc = ['cat','cat','dog','dog','machin','learn']
    corpus = [['cat','machin','learn'],
              ['machin','learn'],
              ['cat','learn'],
              ['dog','machin','learn'],
              ['cat','cat','dog','dog','machin','learn']]
    for term in set(doc):
        print('term,tfidf:',term,tfidf(term,doc,corpus))
# 再加入tfidf进行处理
def tfidf_stem_stop_words_vector(text_data):
    # stemming提取词干
    st = ns.SnowballStemmer('english')    # 构造提取器
    print('imaging->',st.stem('imaging'),'machine->',st.stem('machine'),'learning->',st.stem('learning'))
    
    # 根据自己构造的StemmedTfidfVectorizer构造tfidf词向量
    vectorizer = StemmedTfidfVectorizer(min_df=1,stop_words='english',decode_error='ignore') # 忽略编码错误
    words_vector = vectorizer.fit_transform(text_data)     # 在文本集中进行提取词向量
    words_feature_names = vectorizer.get_feature_names()   # 得到选取的特征
    print('remove_stopwords,feature_names:',words_feature_names)
    print('remove_stopwords,words_vector:',words_vector)          # 输出词向量,不用toarray()则输出稀疏矩阵;有toarray()则输出完整矩阵
                                
    new_text = ['Machine learning is hard to learn for a cat.',
                 'Cat is lazy.']
    new_words_vector = vectorizer.transform(new_text)      # 对新的文本数据进行转换
    print('remove_stopwords,new_text_words_vector:',new_words_vector)
# 利用sklearn提供的TfidfVectorizer构造词向量提取器
class StemmedTfidfVectorizer(TfidfVectorizer):
    def build_analyzer(self):
        english_stemmer = ns.SnowballStemmer('english')
        analyzer = super(TfidfVectorizer,self).build_analyzer()
        return lambda doc: (english_stemmer.stem(w) for w in analyzer(doc))

# 简单计算欧氏距离
def dist_raw(v1,v2):
    delta = v1 - v2
    return np.linalg.norm(delta.toarray())


if __name__ == "__main__":
    text_data_1 = get_simple_data()
    #simple_text_preprocess(text_data_1)
    #stop_words_text_preprocess(text_data_1)
    #stem_stop_text_preprocess(text_data_1)
    #test_tfidf()
    tfidf_stem_stop_words_vector(text_data_1)
  
    代码文件到此结束,下面是实例输出结果:
'''
    text_preprocess(text_data_1)输出结果:
    
    CountVectorizer的详细用法:
        analyzer是表示基于word进行分词、并且以token_pattern为正则进行分词这里的u'(?u)\\b\\w\\w+\\b'
        stop_words指是否使用停用词
        lowercase是先将所有变成小写
        
    CountVectorizer(analyzer=u'word', binary=False, decode_error=u'strict',
        dtype=<type 'numpy.int64'>, encoding=u'utf-8', input=u'content',
        lowercase=True, max_df=1.0, max_features=None, min_df=1,
        ngram_range=(1, 1), preprocessor=None, stop_words=None,
        strip_accents=None, token_pattern=u'(?u)\\b\\w\\w+\\b',
        tokenizer=None, vocabulary=None)
    ('feature_names:', [u'about', u'are', u'at', u'book', u'books', u'by', u'cat', u'cats', u'classified', u'dogs', u'hand', u'is', u'it', u'labeling', u'learning', u'lovely', u'machine', u'manual', u'newspaper', u'not', u'reading', u'this', u'while', u'with'])
    ('words_vector:', array([[1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1,
        0, 0],
       [0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0,
        0, 0],
       [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0,
        0, 0],
       [0, 2, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0,
        1, 0],
       [1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0,
        0, 1]], dtype=int64))
    ('new_text_words_vector:', array([[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0,
        0, 0],
       [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0]], dtype=int64))
    
    stop_words_text_preprocess(text_data_1)输出结果:
    ('remove_stopwords,feature_names:', [u'book', u'books', u'cat', u'cats', u'classified', u'dogs', u'hand', u'labeling', u'learning', u'lovely', u'machine', u'manual', u'newspaper', u'reading'])
    ('remove_stopwords,words_vector:', array([[1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
       [0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0],
       [0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0],
       [0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1]], dtype=int64))
    ('remove_stopwords,new_text_words_vector:', array([[0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
       [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], dtype=int64))
    
    stem_stop_text_preprocess(text_data_1)输出结果:
    imaging-> imag machine-> machin learning-> learn
    remove_stopwords,feature_names: ['book', 'cat', 'classifi', 'dog', 'hand', 'label', 'learn', 'love', 'machin', 'manual', 'newspap', 'read']
    remove_stopwords,words_vector:   (0, 6) 1
      (0, 8)        1
      (0, 0)        1
      (1, 5)        1
      (1, 9)        1
      (1, 2)        1
      (1, 1)        1
      (2, 10)       1
      (2, 6)        1
      (2, 8)        1
      (3, 3)        1
      (3, 7)        1
      (3, 1)        1
      (4, 4)        1
      (4, 11)       1
      (4, 1)        1
      (4, 6)        1
      (4, 8)        1
      (4, 0)        1
    remove_stopwords,new_text_words_vector:   (0, 1)        1
      (0, 6)        2
      (0, 8)        1
      (1, 1)        1
    
    text_tfidf()输出结果:
    term,tfidf: learn 0.0
    term,tfidf: machin 0.0371905918857
    term,tfidf: cat 0.170275207922
    term,tfidf: dog 0.305430243958
    
    tfidf_stem_stop_words_vector(text_data_1)输出结果:
    imaging-> imag machine-> machin learning-> learn
    remove_stopwords,feature_names: ['book', 'cat', 'classifi', 'dog', 'hand', 'label', 'learn', 'love', 'machin', 'manual', 'newspap', 'read']
    remove_stopwords,words_vector:   (0, 0) 0.648462625687
      (0, 8)        0.538282557346
      (0, 6)        0.538282557346
      (1, 1)        0.36063832635
      (1, 2)        0.538497910106
      (1, 9)        0.538497910106
      (1, 5)        0.538497910106
      (2, 8)        0.486240416592
      (2, 6)        0.486240416592
      (2, 10)       0.726044430146
      (3, 1)        0.427992922683
      (3, 7)        0.639070441396
      (3, 3)        0.639070441396
      (4, 0)        0.40357561577
      (4, 8)        0.335004217566
      (4, 6)        0.335004217566
      (4, 1)        0.335004217566
      (4, 11)       0.500221573402
      (4, 4)        0.500221573402
    remove_stopwords,new_text_words_vector:   (0, 8)        0.408248290464
      (0, 6)        0.816496580928
      (0, 1)        0.408248290464
      (1, 1)        1.0
'''

 

矩阵分解(一):奇异值分解

数据挖掘李新春 发表了文章 • 2 个评论 • 120 次浏览 • 2017-04-29 12:40 • 来自相关话题

    由于涉及到大量数学公式,用Latex生成pdf文件,这里贴出pdf转换出来的png图片。附件里面有完整的pdf和代码文件。



















  pdf里面并没有贴出代码,这里贴出源文件的代码,代码很简单,只是简单地对svd进行了测试。下面是代码文件和输出结果:
  svd.py文件:
import numpy as np
import time
# 利用numpy包自带的svd实现,第二个参数表示是否打印出矩阵
def np_svd(matrix,printInfo=True):
    print('np_svd:')
    start = time.clock()
    u,sigma,v = np.linalg.svd(matrix)
    end = time.clock()
    print('shape:',matrix.shape,'=',u.shape,'*',sigma.shape,'*',v.shape)
    print('time:',end-start)
    if(printInfo):
        print(matrix)
        print(u)
        print(sigma)
        print(v)
if __name__ == "__main__":
    # 测试矩阵秩为行满秩或列满秩的情况
    a = np.array([[-1,3,4],
                  [2,-5,8],
                  [-3,-7,-2],
                  [2,4,-3]])
    np_svd(a)
    
    # 测试秩小于行数和列数的矩阵
    b = np.array([[-1,3,4],
                  [2,-5,8],
                  [-2,6,8],
                  [0,1,16]])
    np_svd(b)
    
    # 测试矩阵分解的时间
    for ex in range(1,4):
        m = 3 * 10 ** ex         # 3乘以10的ex次方
        n = 4 * 10 ** ex         # 4乘以10的ex次方
        matrix = np.random.normal(size=(m,n))  # 正态分布
        np_svd(matrix,False)
    测试结果:       
'''
# 满秩情况下的测试:输入矩阵为4*3
np_svd:
shape: (4, 3) = (4, 4) * (3,) * (3, 3)
time: 0.001563813577831752
[[-1  3  4]
 [ 2 -5  8]
 [-3 -7 -2]
 [ 2  4 -3]]
[[ 0.03492724  0.50564699 -0.74831887  0.42792532]
 [ 0.80692855  0.38784734  0.40536499  0.18471597]
 [ 0.37135366 -0.7637849  -0.22588836  0.47718292]
 [-0.45797693  0.10260697  0.47399636  0.74502107]]
[ 11.06047807   8.73915881   3.36049521]
[[-0.0407835  -0.75595687  0.65334977]
 [ 0.31657696  0.61042791  0.72605564]
 [ 0.94768968 -0.23644657 -0.21442314]]
# 不满秩的分解,可以看出sigma矩阵[  2.00999029e+01   8.71744817e+00   2.11044410e-16](由于是对角矩阵,采用向量存储),可以看出第三个奇异值已经趋于零了,可以说就是零
np_svd:
shape: (4, 3) = (4, 4) * (3,) * (3, 3)
time: 0.0001338945396582858
[[-1  3  4]
 [ 2 -5  8]
 [-2  6  8]
 [ 0  1 16]]
[[ 0.21486784  0.31094848  0.90774033 -0.18207238]
 [ 0.3668635  -0.71292939  0.03774797 -0.59642095]
 [ 0.42973567  0.62189696 -0.41612219 -0.50538476]
 [ 0.79659917 -0.09103243 -0.03774797  0.59642095]]
[  2.00999029e+01   8.71744817e+00   2.11044410e-16]
[[-0.01694596  0.10872188  0.99392776]
 [-0.34191212  0.93351191 -0.10794265]
 [-0.93957913 -0.34166514  0.02135407]]
# 测试30*40 300*400 3000*4000 30000*40000矩阵的分解时间(s),分别为0.0011336715375591666、 0.03374235704779949、37.49550263636945。可见3000*4000已经用了半分钟,当测试30000*40000时,计算机全卡了,结果等了大概五分钟没有出结果,所以直接强制关机。可见矩阵分解操作计算了特别大。
np_svd:
shape: (30, 40) = (30, 30) * (30,) * (40, 40)
time: 0.0011336715375591666
np_svd:
shape: (300, 400) = (300, 300) * (300,) * (400, 400)
time: 0.03374235704779949
np_svd:
shape: (3000, 4000) = (3000, 3000) * (3000,) * (4000, 4000)
time: 37.49550263636945
'''

  查看全部
    由于涉及到大量数学公式,用Latex生成pdf文件,这里贴出pdf转换出来的png图片。附件里面有完整的pdf和代码文件。
奇异值分解1.png


奇异值分解2.png


奇异值分解3.png


奇异值分解4.png

  pdf里面并没有贴出代码,这里贴出源文件的代码,代码很简单,只是简单地对svd进行了测试。下面是代码文件和输出结果:
  svd.py文件:
import numpy as np
import time
# 利用numpy包自带的svd实现,第二个参数表示是否打印出矩阵
def np_svd(matrix,printInfo=True):
    print('np_svd:')
    start = time.clock()
    u,sigma,v = np.linalg.svd(matrix)
    end = time.clock()
    print('shape:',matrix.shape,'=',u.shape,'*',sigma.shape,'*',v.shape)
    print('time:',end-start)
    if(printInfo):
        print(matrix)
        print(u)
        print(sigma)
        print(v)
if __name__ == "__main__":
    # 测试矩阵秩为行满秩或列满秩的情况
    a = np.array([[-1,3,4],
                  [2,-5,8],
                  [-3,-7,-2],
                  [2,4,-3]])
    np_svd(a)
    
    # 测试秩小于行数和列数的矩阵
    b = np.array([[-1,3,4],
                  [2,-5,8],
                  [-2,6,8],
                  [0,1,16]])
    np_svd(b)
    
    # 测试矩阵分解的时间
    for ex in range(1,4):
        m = 3 * 10 ** ex         # 3乘以10的ex次方
        n = 4 * 10 ** ex         # 4乘以10的ex次方
        matrix = np.random.normal(size=(m,n))  # 正态分布
        np_svd(matrix,False)
    测试结果:       
'''
# 满秩情况下的测试:输入矩阵为4*3
np_svd:
shape: (4, 3) = (4, 4) * (3,) * (3, 3)
time: 0.001563813577831752
[[-1  3  4]
 [ 2 -5  8]
 [-3 -7 -2]
 [ 2  4 -3]]
[[ 0.03492724  0.50564699 -0.74831887  0.42792532]
 [ 0.80692855  0.38784734  0.40536499  0.18471597]
 [ 0.37135366 -0.7637849  -0.22588836  0.47718292]
 [-0.45797693  0.10260697  0.47399636  0.74502107]]
[ 11.06047807   8.73915881   3.36049521]
[[-0.0407835  -0.75595687  0.65334977]
 [ 0.31657696  0.61042791  0.72605564]
 [ 0.94768968 -0.23644657 -0.21442314]]
# 不满秩的分解,可以看出sigma矩阵[  2.00999029e+01   8.71744817e+00   2.11044410e-16](由于是对角矩阵,采用向量存储),可以看出第三个奇异值已经趋于零了,可以说就是零
np_svd:
shape: (4, 3) = (4, 4) * (3,) * (3, 3)
time: 0.0001338945396582858
[[-1  3  4]
 [ 2 -5  8]
 [-2  6  8]
 [ 0  1 16]]
[[ 0.21486784  0.31094848  0.90774033 -0.18207238]
 [ 0.3668635  -0.71292939  0.03774797 -0.59642095]
 [ 0.42973567  0.62189696 -0.41612219 -0.50538476]
 [ 0.79659917 -0.09103243 -0.03774797  0.59642095]]
[  2.00999029e+01   8.71744817e+00   2.11044410e-16]
[[-0.01694596  0.10872188  0.99392776]
 [-0.34191212  0.93351191 -0.10794265]
 [-0.93957913 -0.34166514  0.02135407]]
# 测试30*40 300*400 3000*4000 30000*40000矩阵的分解时间(s),分别为0.0011336715375591666、 0.03374235704779949、37.49550263636945。可见3000*4000已经用了半分钟,当测试30000*40000时,计算机全卡了,结果等了大概五分钟没有出结果,所以直接强制关机。可见矩阵分解操作计算了特别大。
np_svd:
shape: (30, 40) = (30, 30) * (30,) * (40, 40)
time: 0.0011336715375591666
np_svd:
shape: (300, 400) = (300, 300) * (300,) * (400, 400)
time: 0.03374235704779949
np_svd:
shape: (3000, 4000) = (3000, 3000) * (3000,) * (4000, 4000)
time: 37.49550263636945
'''

 

开工之笔:机器学习小论

其他李新春 发表了文章 • 0 个评论 • 81 次浏览 • 2017-04-29 12:30 • 来自相关话题

    机器学习是一门综合性很高的课程,有幸能够参加周志华老师的《机器学习导论》课程,的确学到了很多有价值的知识。机器学习涉及到数学、算法、编程。
    从数学来说,信管的学生处于劣势,没有良好的数学功底就去看那些算法证明简直是一件很痛苦的事情,这件事在我大二期间看李航老师的《统计学习方法》颇有感触。所以大三一年有60%的时间致力于提升自己的数学功底,当然都是自学(这无疑也是一件很痛苦的事情),但是如果一件事情是很容易可以做到的,那么其价值何在呢?秉承这个理念,坚持看了很多数学书,先从复习《概率论》、《运筹学与最优化》做起,再到《矩阵论》、《复变函数》等,然后《优化方法》、《现代优化方法》、《数理统计》还没看完。周志华老师曾在课堂上提到过线性代数、优化理论、概率和统计是机器学习必须的课程,然后其余的可以看一下群论、解析几何等数学。所以数学之重要也就不言而喻了。
     同时,只关注于数学并不是一件很好的事情,专注于数学而疏于机器学习领域的知识,这是不可取的,因为数学是工具,机器学习里的算法才是经典。所以也在看一些机器学习的资料,比如还是在看《统计学习方法》、《机器学习》,除此之外还看了《模式识别》、《模式分类》等,还有最近再次重新学习229和231的公开课,对深度学习也要加强学习。当然这些相比花费在数学上的时间大概有一半左右,相信这个学期可以把数学知识大概掌握,接下来就可以专注地学习机器学习的知识了,个人比较倾向于去学习图像、语音等比较复杂的相关知识。
    算法实现主要是python编程,因为现在有很多开源库可以直接调用,所以并没有花费很多时间在这上面,大概就只是学习了一下《机器学习实战》并敲了部分代码。还有就是稍微花费了一点时间做了几个项目。还有令我最困惑的是深度学习现在有很多开源库caffe、tensorflow、torch、theano、keras等,还有很多现成的模型可以直接调用。这就导致了大家做应用时只要“傻瓜”似得搭建个模型,然后调参跑数据。这大概就是各大IT企业之所以要分配调参任务了吧?周老师也曾说过,大概花十天的时间就可以基本上搞懂各种深度学习开源库,如果不论项目经验的话,大概就可以和各大IT企业的深度学习工程师差不多了。虽然有点夸张,但是这的确反映了一个问题,现在开源库都把大概的框架搭建好了,所以真正了解其内部运作原理并能够在新的问题上 加以完善以适应新问题的又有几人呢?个人认为就是谷歌、微软,当然还有开源库的开发者。这就导致了在各种比赛中很多队伍只是简单地调整一下深度学习的网络结构,然而并没有加入新的元素或新的思想,这样的话大家都会使用开源库,那么队伍之间的差别是什么呢?上述对深度学习开源库的评论只是个人看法,可能自己没有真正参加过大型项目或比赛,并没有真正了解到开源库的价值所在,可能会有评论不当之处。
    学习的过程也是遗忘的过程,特别是当同时学习很多东西的时候,很容易学了这一章的东西之后并不清楚究竟讲了什么。所以学习还需总结,一方面,笔记是总结的一种方式,以前从不做笔记的我现在认识到了笔记的重要性,这个学期才开始应该不算晚。另一种方式就是写博客,然而博客的一种不便之处就是大量的数学公式,幸好学习了Latex的使用,可以很方便的编辑公式,然而如何将内容呈现到博客上来又是一个问题。所以就只是将pdf转换成图片来呈现了,附件会附有pdf源文件。
    即便用Latex也是一件很困难的事情,有的定理证明甚至需要几页的数学推导,所以这些知识的总结就放在笔记上了。博客用来总结一些比较简单但常用的知识吧,如果能将相关的知识尽量总结进一篇博客,那么是最好不过了。 查看全部
    机器学习是一门综合性很高的课程,有幸能够参加周志华老师的《机器学习导论》课程,的确学到了很多有价值的知识。机器学习涉及到数学、算法、编程。
    从数学来说,信管的学生处于劣势,没有良好的数学功底就去看那些算法证明简直是一件很痛苦的事情,这件事在我大二期间看李航老师的《统计学习方法》颇有感触。所以大三一年有60%的时间致力于提升自己的数学功底,当然都是自学(这无疑也是一件很痛苦的事情),但是如果一件事情是很容易可以做到的,那么其价值何在呢?秉承这个理念,坚持看了很多数学书,先从复习《概率论》、《运筹学与最优化》做起,再到《矩阵论》、《复变函数》等,然后《优化方法》、《现代优化方法》、《数理统计》还没看完。周志华老师曾在课堂上提到过线性代数、优化理论、概率和统计是机器学习必须的课程,然后其余的可以看一下群论、解析几何等数学。所以数学之重要也就不言而喻了。
     同时,只关注于数学并不是一件很好的事情,专注于数学而疏于机器学习领域的知识,这是不可取的,因为数学是工具,机器学习里的算法才是经典。所以也在看一些机器学习的资料,比如还是在看《统计学习方法》、《机器学习》,除此之外还看了《模式识别》、《模式分类》等,还有最近再次重新学习229和231的公开课,对深度学习也要加强学习。当然这些相比花费在数学上的时间大概有一半左右,相信这个学期可以把数学知识大概掌握,接下来就可以专注地学习机器学习的知识了,个人比较倾向于去学习图像、语音等比较复杂的相关知识。
    算法实现主要是python编程,因为现在有很多开源库可以直接调用,所以并没有花费很多时间在这上面,大概就只是学习了一下《机器学习实战》并敲了部分代码。还有就是稍微花费了一点时间做了几个项目。还有令我最困惑的是深度学习现在有很多开源库caffe、tensorflow、torch、theano、keras等,还有很多现成的模型可以直接调用。这就导致了大家做应用时只要“傻瓜”似得搭建个模型,然后调参跑数据。这大概就是各大IT企业之所以要分配调参任务了吧?周老师也曾说过,大概花十天的时间就可以基本上搞懂各种深度学习开源库,如果不论项目经验的话,大概就可以和各大IT企业的深度学习工程师差不多了。虽然有点夸张,但是这的确反映了一个问题,现在开源库都把大概的框架搭建好了,所以真正了解其内部运作原理并能够在新的问题上 加以完善以适应新问题的又有几人呢?个人认为就是谷歌、微软,当然还有开源库的开发者。这就导致了在各种比赛中很多队伍只是简单地调整一下深度学习的网络结构,然而并没有加入新的元素或新的思想,这样的话大家都会使用开源库,那么队伍之间的差别是什么呢?上述对深度学习开源库的评论只是个人看法,可能自己没有真正参加过大型项目或比赛,并没有真正了解到开源库的价值所在,可能会有评论不当之处。
    学习的过程也是遗忘的过程,特别是当同时学习很多东西的时候,很容易学了这一章的东西之后并不清楚究竟讲了什么。所以学习还需总结,一方面,笔记是总结的一种方式,以前从不做笔记的我现在认识到了笔记的重要性,这个学期才开始应该不算晚。另一种方式就是写博客,然而博客的一种不便之处就是大量的数学公式,幸好学习了Latex的使用,可以很方便的编辑公式,然而如何将内容呈现到博客上来又是一个问题。所以就只是将pdf转换成图片来呈现了,附件会附有pdf源文件。
    即便用Latex也是一件很困难的事情,有的定理证明甚至需要几页的数学推导,所以这些知识的总结就放在笔记上了。博客用来总结一些比较简单但常用的知识吧,如果能将相关的知识尽量总结进一篇博客,那么是最好不过了。

[转载]降维方法t-SNE

数据挖掘王开新 发表了文章 • 0 个评论 • 104 次浏览 • 2017-04-16 20:43 • 来自相关话题

http://lvdmaaten.github.io/tsne/
 
第一眼就被MNIST上的效果震撼住了 查看全部
http://lvdmaaten.github.io/tsne/
 
第一眼就被MNIST上的效果震撼住了

[转载]词向量和语言模型

数据挖掘王开新 发表了文章 • 1 个评论 • 33 次浏览 • 2017-04-16 19:42 • 来自相关话题

好文转载
http://licstar.net/archives/328

[转载]推荐系统算法小结

数据挖掘王开新 发表了文章 • 0 个评论 • 35 次浏览 • 2017-04-15 16:58 • 来自相关话题

好文转载
http://bdsc.lab.uic.edu/docs/survey-critique-deep.pdf
 

[转载]CS231n卷积神经网络Lecture notes

数据挖掘王开新 发表了文章 • 0 个评论 • 79 次浏览 • 2017-04-10 11:20 • 来自相关话题

http://cs231n.github.io/convolutional-networks/
写的很详细,适合先看过一遍视频后再去复习一遍(视频在网易云课堂上有)
同时上传了份PDF版的
http://cs231n.github.io/convolutional-networks/
写的很详细,适合先看过一遍视频后再去复习一遍(视频在网易云课堂上有)
同时上传了份PDF版的

第三篇--加法模型与提升方法boost

数据挖掘韩韬 发表了文章 • 3 个评论 • 159 次浏览 • 2017-03-24 23:43 • 来自相关话题

    开始记录算法,和前两篇相比是不是有点太突然?(本文断断续续写了一天,今天上三节课都迟到了……老油条的感慨)
    了解一个领域最重要的就是知道它的思维方式以及它在做什么事情。通过一些积累和总结,我们知道了机器学习就是认为:在掌握的数据和我们的任务之间存在某一个模式,我们要利用机器,学习出这个模式。
     我们仔细审视这句话。问题一:这些数据可以表达出这样的模式吗?问题二:机器怎怎么学习?问题三:怎样判断学出的这个模式的好坏?
     这几个问题会引申出很多讨论。问题一的回答引向数据清洗、特征工程,这决定了学习机器表现的上限;问题二的回答引出算法与优化,重要性不言而喻;问题三的回答引出性能评价方法,通常从具体任务的特性中抽象出来。

     上面的话基本……额……不是今天主要的内容。
     今天想讨论问题二——算法与优化,内容并不符合正常的学习顺序





一、加法模型
(注意:不同于统计学时间序列处理的加法模型)
基本逻辑:
      生活中有很多复杂的事情,单项较弱的个人能力,解决起来总是会有盲点,因此我们就想找人商量商量,组合成强的能力——“三个臭皮匠顶个诸葛亮”嘛(一只小企鹅不行,四个小企鹅就很(。・∀・)ノ゙嗨了)。这是下面我们开展工作的自然的逻辑。数学抽象为:





(M个人每个人的重要性是β(m),γ(m)是这个人的特点,x是这个问题,此人的建议就是b(x;γ(m)))
好的,以上就是加法模型, 的确就是这么简单。下面变换个说法,用基学习器代替人,用学习器权重代替重要性,每个人的特点就是学习器的参数,x就是训练数据集。
       有时候做分类任务时,弱分类器好做,强分类器难做,就适用加法模型了。但是弱分类器不能太差(比如精度小于50%),那说明和随机猜测没什么分别,不能饥不择食。
       不过实质上,还有更多的事情需要处理。显然的两个问题:第一、找什么样人讨论?(基学习器怎么生成)第二、每个人重要性怎么定(权重怎么确定)?这就是我们需要做的真正复杂的工作。
      思考:如果学习器都有同样的优缺点,那就造成冗余,而且没有提高的可能。所以最好是什么情况:各有所长,互缺点互补。(就算是十个臭皮匠,组合之后最多也是开一个臭·皮匠の店)
       好,那我们就利用数学和算法实现这个想法。
       首先,我们量化一下所谓的缺点,它的表示形式应当是训练中预测值与真实值的差距,也就是损失函数  L( y,f(x) ) (loss between real y and prediction f(x)).我们要把它降到最小,也就是:




       这个东西怎么求最小?有求和的公式,很复杂。利用算法思想——前向分步算法。前向就是沿着计算方向向前进行,不断加入新的学习器,分步就是一步一步优化总学习器。我们只需要在第m步(m>=1)求解参数β和γ,这就方便使得新加进学习器之后模型损失最小:




(一步步积累模型,在已有的f(m-1)基础上优化 f(m-1)+βb(x;γ). 显然这是一个greedy strategy)
以下算法描述来自《统计学习方法》




损失函数如何求最小值,这就需要数学解答了。通常没有约束容易求导,会使用梯度下降;有约束条件,常用拉格朗日橙子(杠掉)乘子,转化为对偶问题(dual problem)。




二、提升方法(boost)
当你理解加法模型后,你就知道,加法模型本身就是一种提升方法。
事实上,著名的Adaboost本身就是加法模型的特例。不过Adaboost我更感觉像是从一个学习器出发,根据他的弱点构造互补型学习器,最后将其进行加权线性组合。如何根据他的弱点构造呢?就是将前任做错的事情强迫他更“认真地”去做(加大分类错误样本惩罚权重)。具体的过程很有意思,可以看一看。
提升方法中对于树模型的提升研究较多。对于错误(损失函数)和"有错就改"这个思想的表达的不同分为很多boost算法。如下图所示:




需要说明的是,提升方法太多了,后面可能会讲的模型融合方法bagging、stacking、boosting……这是一个很广泛的理念。
 
不过这里实在是写不下了,我就不写了(费马脸.jpg)
其实整个学习过程就是一个自我教育的过程,机器学习应当归属教育学。
微信阅读不是很深刻,所以留条活路,写得轻松一点。
转载请 联系 注明(字字看来皆是困,一天辛苦不寻常)
不是很烦,可以关注





  查看全部
    开始记录算法,和前两篇相比是不是有点太突然?(本文断断续续写了一天,今天上三节课都迟到了……老油条的感慨)
    了解一个领域最重要的就是知道它的思维方式以及它在做什么事情。通过一些积累和总结,我们知道了机器学习就是认为:在掌握的数据和我们的任务之间存在某一个模式,我们要利用机器,学习出这个模式。
     我们仔细审视这句话。问题一:这些数据可以表达出这样的模式吗?问题二:机器怎怎么学习?问题三:怎样判断学出的这个模式的好坏?
     这几个问题会引申出很多讨论。问题一的回答引向数据清洗、特征工程,这决定了学习机器表现的上限;问题二的回答引出算法与优化,重要性不言而喻;问题三的回答引出性能评价方法,通常从具体任务的特性中抽象出来。

     上面的话基本……额……不是今天主要的内容。
     今天想讨论问题二——算法与优化,内容并不符合正常的学习顺序

0.png

一、加法模型
(注意:不同于统计学时间序列处理的加法模型)
基本逻辑:
      生活中有很多复杂的事情,单项较弱的个人能力,解决起来总是会有盲点,因此我们就想找人商量商量,组合成强的能力——“三个臭皮匠顶个诸葛亮”嘛(一只小企鹅不行,四个小企鹅就很(。・∀・)ノ゙嗨了)。这是下面我们开展工作的自然的逻辑。数学抽象为:

1.png

(M个人每个人的重要性是β(m),γ(m)是这个人的特点,x是这个问题,此人的建议就是b(x;γ(m)))
好的,以上就是加法模型, 的确就是这么简单。下面变换个说法,用基学习器代替人,用学习器权重代替重要性,每个人的特点就是学习器的参数,x就是训练数据集。
       有时候做分类任务时,弱分类器好做,强分类器难做,就适用加法模型了。但是弱分类器不能太差(比如精度小于50%),那说明和随机猜测没什么分别,不能饥不择食。
       不过实质上,还有更多的事情需要处理。显然的两个问题:第一、找什么样人讨论?(基学习器怎么生成)第二、每个人重要性怎么定(权重怎么确定)?这就是我们需要做的真正复杂的工作。
      思考:如果学习器都有同样的优缺点,那就造成冗余,而且没有提高的可能。所以最好是什么情况:各有所长,互缺点互补。(就算是十个臭皮匠,组合之后最多也是开一个臭·皮匠の店)
       好,那我们就利用数学和算法实现这个想法。
       首先,我们量化一下所谓的缺点,它的表示形式应当是训练中预测值与真实值的差距,也就是损失函数  L( y,f(x) ) (loss between real y and prediction f(x)).我们要把它降到最小,也就是:
3.jpg

       这个东西怎么求最小?有求和的公式,很复杂。利用算法思想——前向分步算法。前向就是沿着计算方向向前进行,不断加入新的学习器,分步就是一步一步优化总学习器。我们只需要在第m步(m>=1)求解参数β和γ,这就方便使得新加进学习器之后模型损失最小:
4.2_.png

(一步步积累模型,在已有的f(m-1)基础上优化 f(m-1)+βb(x;γ). 显然这是一个greedy strategy)
以下算法描述来自《统计学习方法》
5.jpg

损失函数如何求最小值,这就需要数学解答了。通常没有约束容易求导,会使用梯度下降;有约束条件,常用拉格朗日橙子(杠掉)乘子,转化为对偶问题(dual problem)。
6.jpg

二、提升方法(boost)
当你理解加法模型后,你就知道,加法模型本身就是一种提升方法。
事实上,著名的Adaboost本身就是加法模型的特例。不过Adaboost我更感觉像是从一个学习器出发,根据他的弱点构造互补型学习器,最后将其进行加权线性组合。如何根据他的弱点构造呢?就是将前任做错的事情强迫他更“认真地”去做(加大分类错误样本惩罚权重)。具体的过程很有意思,可以看一看。
提升方法中对于树模型的提升研究较多。对于错误(损失函数)和"有错就改"这个思想的表达的不同分为很多boost算法。如下图所示:
7.jpg

需要说明的是,提升方法太多了,后面可能会讲的模型融合方法bagging、stacking、boosting……这是一个很广泛的理念。
 
不过这里实在是写不下了,我就不写了(费马脸.jpg)
其实整个学习过程就是一个自我教育的过程,机器学习应当归属教育学。
微信阅读不是很深刻,所以留条活路,写得轻松一点。
转载请 联系 注明(字字看来皆是困,一天辛苦不寻常)
不是很烦,可以关注

8.png