1. 关于特征提取

0x1：什么是特征提取

特征提取研究的主要问题是，如何在数据集未明确表示结果的前提下，从中提取出重要的潜在特征来。和无监督聚类一样，特征提取算法的目的不是为了预测，而是要尝试对数据进行特征识别，以此得到隐藏在数据背后的深层次意义。

回想一下聚类算法的基本概念，聚类算法将数据集中的每一行数据分别分配给了某个组（group）或某个点（point），每一项数据都精确对应于一个组，这个组代表了组内成员的平均水平。

特征提取是这种聚类思想更为一般的表现形式，它会尝试从数据集中寻找新的数据行，将这些新找到的数据行加以组合，就可以重新构造出数据集。和原始数据集不一样，位于新数据集中的每一行数据并不属于某个聚类，而是由若干特征的组合构造而成的。

从特征提取的这个原理来看，特征提取也可以理解为一种泛化的降维概念。

在这篇文章中，笔者会尝试从底层的数学原理出发，阐述这些概念之间的联系和区别。其实不论是特征提取、降维、聚类，都只是从不用的角度解决同一类问题，其背后的原理都是共通的。

0x2：独立特征提取的典型应用场景

1. 鸡尾酒宴会问题

这是一个如何在多人谈话时鉴别声音。人类听觉系统的一个显著特征就是：在一个人声鼎沸屋子里，尽管有许多不同的声音混杂在一起涌入我们的耳朵，可我们还是能够从中鉴别出某个声音来，大脑非常擅长于从听到的所有噪声中分离出单独的声音。

同样的目标，通过本文将要讨论的独立特征提取技术，计算机就有可能完成同样的任务。

2. 新闻主题分类

独立特征提取的一个重要应用是，对重复出现于一组文档中的单词使用组合进行模式识别（word-usage pattern recognition），这可以帮助我们有效地识别出，以不同组合形式出现于各个文档中的主题。从文档中提取出的这些主题，就可以作为一个泛化的一般化特征，用于概括一整类文旦。同时，通过对文档进行独立特征识别，我们会发现，一篇文章可以包含不止一个主题，同时，同一个主题也可以用于不止一篇文章。

例如，对于某个重大新闻，往往会有多家报社从不同角度都进行了报道，虽然各家报社的侧重点各有不同，但是不可避免会有一些公共主题是交叉的。具体来说，例如美国大选特朗普当选总统，CNN和纽约时报都进行了报道，两家报纸的侧重点各有不同，但是都不约而同地谈到了特朗普过去的从商经历等。

需要特别注意的是，必须要保证要搜索的文档中存在内容重叠的主题（acrossover topic），如果没有任何文档存在共同之处，那么算法将很难从中提取出重要的通用特征，如果强行提取则最终得到的特征将会变得毫无意义（这也体现了独立特征提取技术的降维和聚类本质）。

3. 股票市场数据分析

股票市场是一个集体智慧共同作用的典型场景，在股市经济活动中，每一个自然人都遵循最大收益原则开展活动（凯恩斯的开不见的手宏观经济理论），通俗地说就是，每个投资者做每项投资的目的都是为了使自己的收益最大化。整个社会千千万万个投资者共同形成了一个股票市场。

基于这个前提下，我们假设股票市场数据背后潜藏着诸多原因，正是这些原因共同组成的结果，导致了证券市场的各具。我们可以将独立特征提取算法应用于这些数据，寻找数据背后的原因，以及它们各自对结果所构成的影响。

独立特征提取技术可以用来对股市的成交量进行分析。所谓成交量，就是指在某一给定时间段内所买卖的股票份数，下图是Yahoo!股票的走势图，

位于最上方的线代表了收盘价，下面的柱状图则给出了成交量。

我们发现，当股票价格有较大变化时，成交量在那几天往往就会变得很高。这通常会发生在公司发表重要声明或发布财务报告的时候。此外，当有涉及公司或业界新闻报道时，也会导致价格出现”突变“。在缺少外部事件影响的情况下，对于某只股票而言，成交量通常（但不总是）保持不变的。

从成交量中提取出的独立特征，基本上就是明面上或者背后的某些”利好“或”不好“事件。 

Relevant Link: 

《集体智慧编程》Toby segaran - 第10章

 

2. 非负矩阵因式分解（non-negative matrix factorization，NMF）

0x1：以文章矩阵为例简要说明NMF

NMF是一个非常数学化的概念，我们本章会详细讨论其底层数学原理，不过，笔者希望通过一个简单易懂的例子来为读者朋友先建立一个感性的直观概念，为之后的原理讨论作铺垫。

假设我们现在通过词频语言模型，已经将一个文档集（很多篇文章）转换为了一个【M，N】矩阵，M代表有M篇文章，N代表有N个词，元素的数值代表该单词在对应文章中的词频计数。

我们的目标是要对着个矩阵进行因式分解，即，找到两个更小的矩阵，使得二者相乘以得到原来的矩阵。这两个矩阵分别是特征矩阵和权重矩阵。

【特征矩阵】

在该矩阵中，每个特征对应一行，每个单词对应一列。矩阵中的数字代表了某个单词相对于某个特征的重要程度。

由于每个特征都应该对应于在一组文章中出现的某个主题，因此假如有一篇文章报道了一个新的电视秀节目，那么也许我们会期望这篇文章相对于单词”television“能够有一个较高的权重值。

一个特征矩阵示例

由于矩阵中的每一行都对应于一个由若干单词联合组成的特征，因此很显然，只要将不同数量的特征矩阵按行组合起来，就有可能重新构造出文章矩阵来。

而如何组合不同的特征矩阵，用多少特征矩阵来组合，就是由权重矩阵来控制。 

【权重矩阵】

该矩阵的作用是，将特征映射到文章矩阵，其中每一行对应于一篇文章每一列对应于一个特征。矩阵中的数字代表了每个特征应用于每篇文章的程度。

一个权重矩阵示例

下图给出了一个文章矩阵的重构过程，只要将权重矩阵与特征矩阵相乘，就可以重构出文章矩阵，

 

遵照矩阵乘法法则，特征矩阵的行数和权重矩阵的列数必须要相等。如果特征数量与文章数量恰好相等，那么最理想的结果就是能够为每一篇文章都找到一个与之完美匹配的特征。

在独立特征提取领域中，使用矩阵因式分解的面对，是为了缩减观测数据（例如文章）的集合规模，并且保证缩减之后足以反映某些共性特征。理想情况下，这个较小的特征集能够与不同的权重值相结合，从而完美地重新构造出原始的数据集。但实际情况中，这种可能性是非常小的，因此算法的目标是要尽可能地重新构造出原始数据集来。

笔者思考：

笔者这里带领大家用形象化的思维来理解一下矩阵因式分解，我们将其想象为我们吃月饼，从中间将其掰开为两半，一半是特征矩阵，一半是权重矩阵。特征矩阵和权重矩阵原本都不存在，因为我们一掰，凭空出现了2个小的月饼。那接下来的问题来了，我们能否随意的掰这个月饼呢？答案是不行！这个月饼有自己的法则，只允许我们按照有限几种方案来掰，因为该法则要求掰开后的两半还必须能够完美的拼回一个完整的月饼。

回到矩阵因式分解上来，矩阵的因式分解类似于大数的质因分解，一个矩阵只存在少量几种因式分解方法。而要找到这几种分解方案，就需要使用一些非常精巧的算法，例如本文要介绍的乘法更新法则（multiplicative update rules）。

0x2：乘法更新法则（multiplicative update rules）- 寻找矩阵因式分解的一种算法

我们的目标很明确，希望找到两个矩阵（满足M和N的约束即可），这两个矩阵相乘要尽可能接近原始目标矩阵，我们也建立了损失函数difcost，通过计算最佳的特征矩阵和权重矩阵，算法尝试尽最大可能来重新构造文章矩阵。我们通过difcost函数来度量最终的结果与理想结果的接近程度。

一种可行的优化方法是将其看作是一个优化问题，借助模拟退火或者遗传算法搜索到一个满意的题解，但是这么做的搜索成本可能过于庞大（随着原始矩阵尺寸的上升），一个更为有效的方法是，使用乘法更新法则（multiplicative update rules）。

这些法则产生了4个更新矩阵（update matrices），这里我们将最初的文章矩阵称为数据矩阵。

• hn：经转置后的权重矩阵与数据矩阵相乘得到的矩阵
• hd：经转置后的权重矩阵与原权重矩阵相乘，再与特征矩阵相乘得到的矩阵
• wn：数据矩阵与经转置后的特征矩阵相乘得到的矩阵
• wd：权重矩阵与特征矩阵相乘，再与经转置后的特征矩阵相乘得到的矩阵

为了更新特征矩阵和权重矩阵，算法需要做如下几个操作，

• 首先将上述所有矩阵都转换成数组
• 然后将特征矩阵中的每一个值域hn中的对应值相乘，并除以hd中的对应值
• 再将权重矩阵中的每一个值域wn中的对应值相乘，并除以wd中的对应值

from numpy import *
import numpy as np

def difcost(a,b):
  dif=0
  for i in range(shape(a)[0]):
    for j in range(shape(a)[1]):
      # Euclidean Distance
      dif+=pow(a[i,j]-b[i,j],2)
  return dif

def factorize(v,pc=10,iter=50):
  ic=shape(v)[0]
  fc=shape(v)[1]

  # Initialize the weight and feature matrices with random values
  w=matrix([[random.random() for j in range(pc)] for i in range(ic)])
  h=matrix([[random.random() for i in range(fc)] for i in range(pc)])

  # Perform operation a maximum of iter times
  for i in range(iter):
    wh=w*h
    
    # Calculate the current difference
    cost=difcost(v,wh)
    
    if i%10==0: print cost
    
    # Terminate if the matrix has been fully factorized
    if cost==0: break
    
    # Update feature matrix
    hn=(transpose(w)*v)
    hd=(transpose(w)*w*h)
  
    h=matrix(array(h)*array(hn)/array(hd))

    # Update weights matrix
    wn=(v*transpose(h))
    wd=(w*h*transpose(h))

    w=matrix(array(w)*array(wn)/array(wd))  
    
  return w,h


if __name__ == '__main__':
  l1 = [[1,2,3], [4,5,6]]
  m1 = matrix(l1)
  m2 = matrix([[1,2], [3,4], [5,6]])
  print "np.shape(m1*m2): ", np.shape(m1*m2)
  w, h = factorize(m1*m2, pc=3, iter=100)
  print "w: ", w
  print "h: ", h

  print "w*h: ", w*h
  print "m1*m2: ", m1*m2

可以看到，算法成功地找到了权重矩阵和特征矩阵，使得这两个矩阵相乘的结果与原始矩阵几乎完美匹配。 

值得注意的是，MUR方法要求我们明确指定希望找到的特征数。例如，在一段录音中的两个声音，或者是当天的5大新闻主题。 

0x3：理论概述

1. 算法形式化描述

有了前两节的铺垫，现在我们来讨论一些NMF的理论概念。 

NMF（Non-negative matrix factorization），即对于任意给定的一个非负矩阵V，其能够寻找到一个非负矩阵W和一个非负矩阵H，满足条件V=W*H。从而将一个非负的矩阵分解为左右两个非负矩阵的乘积。其中，

• V矩阵中每一列代表一个观测(observation)，每一行代表一个特征(feature)
• W矩阵称为基矩阵，即特征矩阵
• H矩阵称为系数矩阵或权重矩阵，这时用系数矩阵H代替原始矩阵，就可以实现对原始矩阵进行降维，得到数据特征的降维矩阵，从而减少存储空间（从【M*N】降到【M*K】维） 

分解过程如下图所示，

2. 损失函数形式

对于如何衡量因式分解的效果，有3种损失函数形式，其中第一种我们上前面的例子中已经使用到了简化版本。

【squared frobenius norm】

 

其中： 

 

α为L1&L2正则化参数，