Mining of Massive Dataset 笔记

//2019.06.03

一、概述

1、这本书是关于“data mining”的，但是它的关注点是在大数据挖掘上，它的观点是“在大数据上应用算法去挖掘信息，而不是使用ML去训练大数据”

Data mining is about applying algorithms to data, rather than using data to “train” a machine-learning engine of some sort.

2、目录

• 分布式文件系统和Map-reduce
• 相似搜索（包括minhashing和locality-sensitive hashing）
• 流数据处理
• 搜索引擎技术（Google PageRank,Link-spam detection,hubs-and-authorities approach）
• Frequent-itemset mining
• 降维算法
• 网络应用的两个关键问题
• 大规模图结构的分析算法

---

CH3:Finding Similar Items

一、概述

• data-mining的一个关键问题就是检测“相似”项目的数据 。--->如何检测（document---(shingling)-->sets--(minhashing)-->short signatures）
  

• 当我们搜索任何类似的项目时出现的另一个重要问题是，可能有太多的项目对来测试每一对的相似程度 ，即使计算任何一对的相似性可以非常容易。---->减少项目（locality-sensitive）

• 判断相似的方法

二、近邻搜索的应用（Applications of Near-Neighbor Search）

1、集合相似性--->Jaccard similarity

2、Similarity of Documents

Jaccard相似性很好地解决的一类重要问题是在诸如Web或新闻文章集合之类的大型语料库中找到文本上类似的文档 。

但是我们这里强调的是“character-level similarity”，不是“similar meaning”，这要求我们去检测文档间的单词或者他们使用的单词。逐词比较，看是否一致，但在很多应用中，基本是不同的。

• 抄袭（找文本相似性）
• 镜像页面（Mirror Pages）:镜像页面间是很相似的，很少有不同
• 相同来源的文章

3、协同过滤（Collaborative Filtering as a Similar-Sets Problem）

这是一类常见的应用，在推荐中常被应用，具体如下：

• 在线购物（On-Line Purchases）：商品推荐
• 电影评级（Movie Ratings）

三、Shingling of Documents(步骤1：document--->set)

1、K-shingles:Define a k-shingle for a document to be any substring oflength k found within the document.

Example:D is "abcdabd" ,k = 2, 2-shingles for D is**{ab,bc,cd,da,bd}**

Note that the substring ab appears twice within D, but appears only once as a shingle. A variation of shingling produces a bag, rather than a set, so each shingle would appear in the resultas many times as it appears in the document. However, we shall not use bags of shingles here.（理解:应该是指子串的类型吧，该shingle应该是出现了多次）

2、k大小的选择设定

k的设定取决于典型文档的长度和典型字符的集合大小，重点要记住，k的选取的足够大以保证任何给定的shingles出现在任何文档的概率很低。

例如：对于emails，k=5

3、Hashing Shingles(Key technoogy)

在整个过程中，不是将子串直接作为元祖，而是选择哈希函数，将长度为k的子串映射到一系列buckets上，然后将相关bucket的标号作为shingle.那么表示的文档的结合是一个整数集合，那个整数，就是k-shingles所在的桶标号。这样使得数据被压缩，存储量大大减少

4、shingles bulit from words

在寻找相似新闻或者文章时，因为写作风格等原因，有些停用词（如“and”,"you"等）对我们的主题判断没有任何意义，，所以我们想忽略这些词，那么对于这个问题，我们要去找有用的shingles.

方法：找到一个shingle为定义的“stop word”，那么紧跟的两个词，不管是不是停用词，都形成了一组有用的shingles

Example:"A spokesperson for the Sudzo Corporation revealed today that studies have shown it is
good for people to buy Sudzo products.”

Here, we have italicized all the likely stop words,there are nine shingles from the sentence:

A spokesperson for

for the Sudzo

the Sudzo Corporation

that studies have

have shown it

it is good

is good __for

for people to

to buy Sudzo

四、Similarity-Preserving Summaries of Sets（set----- >signatures）

元组的集合太大了，尽管用标号来表示，也还是会很大。因而我们想减少他的存储量，这里引入“Signatures”,利用Signature 来比较两个集合的相似度。

1、集合的矩阵表示

column:sets

rows:elements of the universal set from which elements of the sets are drawn

但是注意：矩阵不太可能作为数据的存储方式，因为它总是稀疏的，存储太浪费了，但是它可以用作数据的可视化。

2、Minhashing

(1)原理：对矩阵进行置换行排序，对于不同的行有不同minhash值，每次选择colum值为1的最小置换序号
（例如对上图进行置换排列，顺序如左图）

那么对于minhash(S1)=a,minhash(S2)=C,minhash(S3)=b,minhash(S4)=a

3、Minhashing and Jaccard Similarity

（1）所有随机顺序的的minhash最后产生的相同的概率值，与两个集合的Jaccard 相似度值相同。

（2）一般我们是用其来估计，选择100过或几百个来做，而不是把所有情况都给列出来。‘

（3）但是（2）中方式并不合理，明确置换是不可行的，每次做都要遍历一遍大数据集，这样非常耗时。

*但我们可以通过随机散列 函数来模拟 随机排列的效果，该函数将行数映射到和行数一样多的桶中

那么我们不需要置换列，只需要计算一次就可以把所有的请款计算得到
（这里的行号可能会冲突）

那么此时我们就遍历一遍，每次都计算其minhash，每次更新，其值

a)初始状态

b)第一行（这两个函数的计算都是1，那么他们的minhash肯定是1，记录下来，但是S2,S3在此取不到minhash值，所以不用管）

c)第二行（此时只有S3能取到一个排列的序号值，所以此时他的minhash是2，4）

d)第三行（这里S2,S4取到，更新S2,但是S4取到的h值大于原来，所以不更新）

e)第四行(S1,S3,S4)

f）第五行

五、Locality-Sensitive Hashing for documents(LSH)

尽管用minhash将大的文档压缩成小的signature，来保存文档对的相似性，但是有特别多的文档pairs时，去寻找相似度还是不够高效的。但是如果目标是要计算每一个pair对，那么即使用同步计算，工作量也没有减少。

那么此时更换角度，大多数情况下，我们是想要计算那些高度相似或者说相似度高于某个值的pair对的相似度，换句话说，看起来可能相似 的那些pair对的相似度，有些看起来就不相似的，其实可以忽略。

--->Locality-sensitive hashing(LSH)或者叫做near-neighbor search

（1）LSH的方法：通用方法是对项目多次hash，使得类似项目 更可能被散列到相同的桶(排除了部分不相似的pair) 。然后，考虑任何hash到同一个桶中的buckets是一个候选对，检查这些候选对的相似性。(我们希望，在这个桶里不相似的pair尽可能的少，即FP小，同时希望那些FN尽可能的小)

（2）choose hashing:

*把signature 矩阵划分为b bands(每个段有r行)，那么我们对每个band设置一个hash 函数，采用r个整数的向量（该band内一列 的部分行），并将其散列到一些桶中。可以对每个band使用相同的hash,但是我们为每个band 使用单独的桶 阵列，因此在不同band中具有相同矢量的列将不会hash到同一个桶（避免了一些不必要的相似错误）--->条带策略使得相似的列更可能成为候选pair

（3）Banding Technique 分析

计算这些文档成为候选pair的概率

问题：s不是相似度吗？？为什么会用相似度来表示概率？？

regardless of the chosen constants b and r, this function has the form of an S-curve。

Example3.11:b=20,r=5，假定signature 长度是100。

*从表中可以看出来，中途上升的s只是略大于0.5

*表中数据可以得到，这条曲线并不是在阈值处从0跳到1的理想阶跃函数，但是中间曲线的斜率是明显的。（从s = 0.4到s = 0.6，它上升了0.6以上，因此中间的斜率大于3。）

*如果s=0.8,那么1-0.8^{5就是0.627，那么增加到它的20次方，是0.00035，那么用1减去这个值，大概是0.99965.因此我们考虑两个相似度为80%的文档，那么在每一个band中，大约只有33%的机会在所有5行中达成一致成为候选pair(0.8}5),然而在这有20个band，20个机会成为候选。那这样看，仅仅1/3000的80%相似的对会成为FN

(4)Combine the techniques

*找候选pair集的方法：

————————————————————————————————

ch9 Recommendation Systems(321)

一、概述

1、推荐系统分为两类

• Content-based systems :examineproperties of the items recommended**.Similarity of items** is determined by measuring the similarity in their properties.
• Collaborative filtering systems:recommend items based on similarity measures between users and/or items.

2、推荐系统模型（based on a utility matrix of preferences:偏好的效用矩阵）

（1）Utility Matrix

在推荐系统应用中有两类实体：users & items.(user会偏好items,那么将其转化为数据（user-item），即为utility matrix)

The goal of a recommendation system is topredict the blanks in the utility matrix.

(2)The Long Tail

A concept :解释了在线供应商优于传统的实体供应商的优势

The long-tail phenomenon forces on-line institutions to recommend items
to individual users.

“长尾理论”是网络时代兴起的一种新理论，由于成本和效率的因素，当商品储存、流通、展示的场地和渠道足够宽广，商品生产成本急剧下降以至于个人都可以进行生产，并且商品的销售成本急剧降低时，几乎任何以前看似需求极低的产品，只要有卖，都会有人买。这些需求和销量不高的产品所占据的共同市场份额，可以和主流产品的市场份额相当，甚至更大。

(3)Applications

• Product Recommendations
• Movie Recommedations
• News Articles

(4)Populating the Utility Matrix(填充矩阵)

• ask users to rate items
• make inferences from user's behavior

3、Content-Based Recommendations

（1）Item Profiles:a record or collection of records representing important characteristics of that item.

（2）Discovering Features of Documents:

*可以去掉常用的停用词，然后计算剩余词的TF.IDF,用得分高的词来表征文档的特征；

*也可以设置一个阈值，获取更多的特征。

--->文档用特征集合表示，那么测量两个文档的相似性，自然而然就有两种测量方法：

• Jaccard distance(3.5.3)
• cosine distance(3.5.4):对于该计算，可以将分数看做是一个向量，每一个单词都有一个分量。

注意：这里的相似与之前提到的相似概念不同，之前，两者相似，只要里面大部分内容一致相似即可；但是在推荐系统中我们仅关注于某些重要的词 是否一致，即使大部分内容都不相同。

（3）Obtaining Item Features From Tags

（4）Representing Item Profile

*基于内容推荐的最终目标是基于utility matrix建立一个既包含属性值对的item profile 有包含用户特征属性的profile

*我们可以用一个0-1向量，1表示包含了文档中高分的词。因为文档的特征全是词，所以很容易表示profile.同时，将该方法应用 到其它所有特征中，其中布尔向量不太可读，他们是一些数字特征，是真实的数字，加入这些失去了结构，有时这些数字特征并没有那么重要；

*数字特征应由表示项目的向量的单个分量表示。 这些组件保存该功能的确切值，如果向量的某些组件是布尔值而其他组件是实值或整数值，则没有坏处。 我们仍然可以计算向量之间的余弦距离，但是如果我们这样做，我们应该考虑非布尔组件的适当缩放，这样它们既不会支配计算也不会无关紧要。

最后一列代表评级，其中的α代表缩放因子，cosine计算The dot product is 2 + 12α2, and the
lengths of the vectors are . Thus, the cosine of the
angle between the vectors is（计算理解：(1²⁺¹2+1²⁺¹2+1^2+(3 α**)²⁾1/2）,相乘应该是点乘，和二维向量应该是一样的。**

（补充cosine 距离：余弦相似度用向量空间中两个向量夹角的余弦值作为衡量，两个个体间差异的大小。相比距离度量，余弦相似度更加注重两个向量在方向上的差异，而非距离或长度上。公式如下：）

*α取值不同，得到的cosine值也不同，很难知道哪个α是对的，但是可以可以知道其是影响我们的相似度的

（4）使用Profiles

*我们不仅要常见描述item的向量，还需要描述用户特征的向量。用utility matrix来表示user和item之间的关系。

*对于nonblank matrix 实体可以是1表示用户购买或者有个相似的连接；或者可以是任意的数字表示一个打分或者用户对item的喜爱程度。

综上，我们可以估计用户喜欢的item

Example

*如果效用矩阵不是0-1，而是一个打分，例如1-5，那么我们可以将效用矩阵向量加权来表示item的profile。那么通过减去平均值来规则化这个效用矩阵是有意义的。（避免了0）

（5）推荐过程（Recommending Items to Users Based on Content）

profile vectors for both users and items:we can estimate the degree to which a userwould prefer an item by computing the cosine distance between the user’s and item’s vectors.

• random-hyperplanes
• LSH

-->to determine in which buckets we must look for items that might have a small cosine distance from the user.

(6)分类算法

常见的分类器：决策树（decision trees）

*决策树：是一个节点的集合，用二叉树的方式排列，其叶节点是相应的决策。像在上面列举的例子中，决策是“like”or"dislike".每一个内部节点是分类对象的条件，例如，在上面的举例中，这些条件就是相关一些谓词的选择。那么要进行分类，从根节点出发，并将应用中的项目应用于谓词，如果为true，移动到左支，如果为false,移动到右支，重复这个过程，最后到达叶子节点。

*构建决策树：构建决策树，需要为每个节点选择谓词。当两个节点同构时，我们可以停止或者创建一个left.

*与此同时，我们希望对每一组有很多决策，而不是单单一个决策（因为一个小组决策信息不好统计）

--》决策树集合（overfitted）

4、协同过滤（Collaborative Filtering）

*与前面截然不同的推荐方法，不是根据item的特征来决定他们的相似性，而是关注两个事物间用户的相似度。

*表示：不再为用户抽取特征向量，而是用效用矩阵的行向量来表示，如果根据指标距离判断两个向量相似，那么两个用户是相似的

*过程：为U用户推荐，那么首先找到与U 类似的用户V，然后将V的内容推荐给U，而整个过程叫做协同过滤。

（1）Measuring Similarity(:how tomeasure similarity of users or items from their rows or columns in the utility matrix)

这个数据集有点小，会有点缺陷，比如我们如果计算的话，会认为AC两个用户相似，但是实际上他俩的意义相反，并不相似。

• Jaccard Distance:忽略了矩阵的值，仅仅关注了评判的相关个数，如果这个效用矩阵仅仅是0-1表示的是否（布尔矩阵），那么将是一个很好的选择。但这里JD忽略了重要的信息。

针对于上图的分析计算：

• Cosine Distance：可以将空白的设置为0，但是0是有问题的，因为0的含义是不喜欢。

针对上图的分析计算：

The cosine of the angle between A and B is

The cosine of the angle between A and C is

Since a larger (positive) cosine implies a smaller angle and therefore a smaller distance, this measure tells us thatA is slightly closer to B than to C.

改进：

• Rounding the data: 可以舍掉评级来舍掉高评分电影和低评分电影之间的相似性，例如可以将3，4，5设置为1；1，2设置为空，那么上面的效用矩阵就可以等价为下面的矩阵
  

在这种情况下，用JD计算出来的数值是正确的。

• Nomalizing Ratings：每个数减去平均得分，将低评分转换成负的数值，高评分转化成正数，然后使用cosine distance,会发现不同观点的两个用户的向量是相反的，且会尽可能的远；而具有相同看法的用户的角度会尽可能的小

规范化后的矩阵为

compute the cosine of the angle between A and B:

The cosine of the angle between between A and C is

（2）The Duality of Similarity

效用矩阵可以是关于用户的、或者关于item的或者两者都有的，上面所说的寻找相似用户的技术，是可以用在效用矩阵的列来寻找相似item 的。在实践中，有两种方式来破坏这种对称性（？？？破坏对称性是什么意思？）

• 可以使用一些用户的信息来推荐item:给定一个用户，找到与其最相似的一些用户，然后可以根据这些相似用户做出决策或建议。但是这个没有对称性，即是我们找到了相似的物品对，我们也需要采取额外的步骤将items推荐给用户。
• 用户和item的行为是有差异的，直观上看，item往往可以用简单属于进行分类（例如，音乐往往是单一类型的）

----》a)找到相似的用户，然后推荐item;b)根据item的相似性来估计用户和item

注意：不管是用那种方法，仅仅找到一个条目是远远不够的！ 同时，不管采取哪种方法，都应为每一个用户预先计算首选项目。

（3）Clustering Users and Items

*当我们的效用矩阵有很少的user-item对信息时，我们很难找出相同的item或者user.解决这种陷阱的方式是对用户或者item聚类 ！(使用距离测量方法来实施聚类)，然而，没有理由立刻应用在很小的集群上，相反，使用一个多层的方法，使得一些集群保留还没有合并的分层作为第一步就可以了。

*例如，我们会留下一半的集群作为item

合并后修改效用矩阵，其中的值为原来的平均值 ，注意原来为blank的，合并后还是blank

*我们可以再用修改后的效用矩阵去聚合用户 ，再次利用我们认为合适的距离。那么最后使得用户行对应于相应的用户群，item对应于相应的items类别群

*这个过程可以不断重复。

*最后定下效用矩阵，就可以估计原始矩阵的item了。具体如下：

• 找到原始矩阵中所要预测的U/I，然后看它属于哪个类别，记为C/D
• 如果相应的C-D集群在效用矩阵所对应的不是空白，那就用该值来替代原来的空白值
• 如果C-D集群在效用矩阵中对应的是空白值，那么根据上面一节的方式去估计该C-D所对应的值，然后再将该估计值赋给U/I.

5、降维（Dimensionality Reduction）

*估计效用矩阵空白处的一种完全不同的方法是两个长而细的向量的乘积。这种计算方式在用户较多，item较多情况下才有意义。

*在这里描述了一种寻找这两个细长矩阵 的方法：UV-decomposition，它是SVD(奇异矩阵分解) 的一般理论的实例。

（1）UV-Decompositon概念

*以电影为例，用户可能会有一些特征，比如喜欢的电影类型、电影演员、或者导演等等。如果有一个关于用户和电影的效用矩阵M，它有n行m列，然后我们可以找到一个矩阵U（n行d列）和一个矩阵V（d行m列），然后UV不为空的地方近似于M，那么我们就可以用UV来估计M，这个过程就叫做“UV-decomposition of M”.

(2)Root-Mean-Square Error(标准差)

计算UV与M的误差，典型方法是计算其标准差。

左为M,右为UV,计算两者的RMSE

• 用M每一行减去UV的每一行，每项平方且求和

3 0 2 2 1 -->18

1 - 1 0 2 -1--->7

0 1 -1 2---->6

0 3 2 1 3--->23

2 2 3 2 --->21

• 将每行的平方差的和相加 18+7+6+23+21=75
• 取平均且开根号（因为中间有2个空，所以总共有23项）--->

(3)Incremental Computation of a UV-Decomposition

*目标：找到一个是RMSE最小的一个UV分解

**先选择一个任意的U、V

**重复调整U、V使得RMSE最小

---->这里仅考虑对UV单个元素进行调整（尽管原则上可以有更复杂的调整），不论做什么样的调整，在一个典型的例子中可能会有一些局部最小值点使得RMSE不会变小。但在这些局部最小中，只有一个是我们所需要的全局最小（注意：从未保证最后的局部最小就是全局最小 ！）。那么为了增加我们找到全局最小的机会，我们需要从不同的开始点出发，即选择不同的U\V作为初始矩阵。

*先选择一个初始矩阵U、V（全1），然后在每个数上做调整，找到可以最可能改变RMSE的条目的值。

Example

假设选定u11去做调整，那么得到的新UV和之前的M,就可以列出REMS的计算式，该计算式是包含x的一个函数，

该sum值可以简化为

那么我们的目标就是要将该式子最小化，那么可以通过求导，让导数等于0来做。

最后求得x=2.6,那么相应的U、V、UV做了改变，

假设下一个选定的要改变的量是v11,其过程和上面差不多

sum求和为

化简得到

对上式子进行求导:

最后求得y=1.617,其改进后的矩阵如下

（4）Optimizing an Arbitrary Element(最优化任意元素)

根据上面单个值的修改，总结出修改通式 。

假定M是一个nm的效用矩阵（中间有一些空白项），U、V分别是nd,dm的矩阵，用mij,uij,vij表示其元素，设P=UV，pij表示其元素。

那么假设想要改变urs的值，可以最小化RMSE的值，（注意urs仅影响P=UV），那么，仅仅关心下面的元素即可。

对于所有j值，mrj是非空的（如果是空值，则没有贡献），在上面的表达式中，我们用x替换了urs的值，并且对该式做了约定。

对上面的式子进行求导，并使得导数为0，求解RMSE的最小值。

可以删去-2这个公共因子，然后进行求解，最终

同理，可以得到y相应的最佳改变值

（Here, Pi is shorthand for the sum over all i such that mis is nonblank, and Pk6=r is the sum over all values of k between 1 and d, except for k = r.）

（5）Building a Complete UV-Decomposition Algorithm（根据上面的介绍，构建完整的分解算法）

• Preprocessing of matrix M:

*M中的元素对决定M中缺失的元素很重要，要消除相关的影响。

*具体做法：规范化M，将M中每个非空的mij减去每个user i的均分，然后在结果矩阵中，再减去item j 的项目均分。（或者两个顺序反过来：注意：两个顺序得到的结果可能不同，但是会比较相近）；还有一种选择是mij减去平均值来归一化（即：减去用户平均值和项目平均值和的一半）

*如果选择将M标准化，那么在对M进行预测的时候要撤销这个标准化。（即得到的预测值e要再加上刚刚规则化时减去的值）

• Initialization

*在求解时存在一些最优性是至关重要的，因为有一些局部最小存在，所以我们要初始化不同的UV，以找到最优的解

*对于U、V一个简单的开始点是将其所有的元素设置相同的值， 这个值很好的一个选择是给出的UV值是M中空白元素的平均值

（如果已经规范化了M，那么这个值必然是0；如果我们选择了d作为U、V短边的长度，a是M的非空元素平均值那么U、V的值应该是（a/d）^1/2）

*如果有多个起点U、V，那么可以随机且独立的对每个元素，扰动 （a/b）^(1/2)(??????随机扰动什么意思？？？)

*有许多扰动方法：差异的分布（例如：可以为每个元素添加随机一个正态分布，均值为0，一些选择标准方差）；或者为某些数值c,添加一个[-c,+c]范围内的值

• Performing the Optimization

*为了到达最小值，我们需要选定一个U、V的访问顺序,(最简单的是选定某个循序，逐行的去访问遍历row-by-row

（注意：我们仅仅是优化了一个元素，这并不意味着，我们已经找到了最后的值，因此需要不断的重复访问元素，直到我们认为不需要再改进了）

• Converging to a Minimum（收敛到最小值）

*理想状况下，RMSE应该要为0，但是我们大多数情况下是做不到的（由于M中通常存在的非空元素多于U和V中的元素，因此我们无权期望将RMSE降低到0。）

*那我们需要定一个标准：何时收敛？

---》我们可以跟踪在一轮优化中获得的RMSE的改进量 ，并在该改进低于阈值 时停止。

• Avoiding Overfitting

*在执行UV分解的过程中常出现的一个问题是：我们得到了一些很好的局部最小值，但是却不能反映数据的处理过程。

---》即，我们得到了很小的RMSE,但是去不能很好的预测未来的数据 ！

*解决方法

**避免优先考虑优化的第一个组件（？？？），通过仅将组件的值，从当前值向其优化值移动一半

**在收敛前，避免重新访问U、V的元素

**采取几种不同UV分解，当预测M的元素时，采用每次分解结果的平均值

————————————————————————————————————————————————

ch11 Dimensionality Reduction(降维)

*有许多原数据可以被看做是一个大的矩阵，与此同时，在很多矩阵的应用中，矩阵可以通过找到在某种意义上接近原始矩阵 的“较窄”矩阵 来概括。

（这些较窄矩阵仅仅有少量的行或者少量的列，因此会比原来大的矩阵更高效）

找到这个“窄矩阵”的过程 叫做*“dimensionality reduction”**

*ch9中UV-decomposition是降维的一个初步例子

*更细致的讨论分析：

• 特征值以及在主成分分析（PCA:principal component analysis）中的用法
• 奇异分解（一个更强大的分解版本）
• CUR-decomposition(奇异分解的一种变体，如果原始矩阵是稀疏的，那么它会保持分解后的稀疏性)

1、Eigenvalues and Eigenvectors（特征值和特征向量）

（1）定义（略）Me=ce

*矩阵乘以一个常数，只会改变向量的长度，但不会改变其方向

*为了避免长度的模糊性，我们常使用单位矩阵（unit vector）

*一般要求特征向量第一个非0元素是正的

Example:

（2）计算特征值和特征向量

*寻找特征值和特征向量对的方法：从任意长度的向量出发，迭代计算，直到收敛

*当M是一个随机矩阵时，用幂迭代寻找最大特征值向量及其对应的特征值，虽然主特征值值不是1，但是随着增长，会靠近主特征值（？？？？）

*将采用幂迭代方法推广来找所有的特征对

*(除了幂迭代)有一个运行时间为O(n^3)准确计算方法：

理解：就按照正常求解特征值和特征向量的方法正常求解就可以

（让这个矩阵长度为0，求解这个常数的值）

（然后分别带入Me=ce,求解相关向量，并且使其变为单位矩阵）

（3）Finding Eigenpairs by Power Iteration（寻找特征值和特征向量）

（4）特征向量矩阵

2、主成分分析（PCA:Principal-Component Analysis）

*PCA:is a technique for taking a dataset consisting of a set of tuples representing points in a high-dimensional space and finding the directions along which the tuples line up best.

*思想：将一系列元祖组成一个矩阵M，然后找的特征向量。这些特征向量被看做是对高维空间的转换

*对原始数据应用这种变换时，与主要特征向量对应的轴是点最大程度“展开”的轴，更准确地说，该轴是数据方差最大化的轴。

（换句话说，这些点最好被视为沿着该轴放置，与该轴的偏差很小。 同样地，对应于第二特征向量的轴（对应于第二大特征值的特征向量）是与第一轴的距离的方差最大的轴，等等。）

*我们可以将PCA看做是数据挖掘 技术。高维的数据可以投影到一些重要的轴 上特带原来的数据。这些轴对应一些大的特征值。

（因此，原始数据由具有更少维度 的数据近似，这很好地总结了原始数据。）

（1）实例

如上图，有4个二维的点，他们沿着45度点排列成一个简单图案。为了预测结果，可以最好地将这些点视为沿着45度角的轴线，并且在垂直方向上具有小的偏差。（这样就从二维变成了一维），具体处理如下：（先画出相关矩阵，然后计算MTM,然后求解该矩阵的特征值；然后根据特征值求解相应的单位特征向量）

再将特征向量组合

（其实就是求其正交单位矩阵，那么乘以该正交矩阵，即表示轴的旋转？）

那么如上图数描述，M*E即表示将M旋转了45度

得到如下观点：

• 距离：第一个点和第二个点投影到该直线上，在原系统中的顶点表示为（1.5，1.5)其在原空间中距离原点为，而第一个点变换后的坐标值就是，在原系统中，第一个点和投影点的距离为，那么x,y与之相对应成立
  

（2）使用特征向量进行降维

*从上面的实例抽取出一般原则：如果M是一个矩阵，其行代表空间中具有任意数量维度 的每个点（理解：就相当于行是点坐标），我们可以计算并计算其特征对。

*做法：

• 用E来表示其特征向量的矩阵（特征值由大到小）；用L来表示特征值矩阵
• 由于每个特征向量e的及其对应的特征值λ，因此遵循
• ME是M变换之后的对应空间，在这个空间里，第一个轴是最重要的，即沿轴线的是方差最大的
• That is, let Ek be the first k columns of E. Then MEk is a k-dimensional representation of M

*举例说明（忽略做法）
其特征向量为，对应的λ = 58 and λ = 2.
（11.3仅仅是投影到某一维上去了）

（3）矩阵距离

There is a strong relationship**** between the eigenvalues of MTM and MMT .
Suppose e is an eigenvector of MTM; that is, MTMe = λe

---》Multiply both sides of this equation by M on the left. Then MMT (Me) = Mλe = λ(Me)

在原式子基础上乘以M，那么只要Me不为0，那么就可以得到MTM的特征向量,反过来也是这样。

===》我们得出结论，MMT的特征值是MTM的特征值加上额外的0。（前提是维度大于MTM,即特征值多了两个0 ）
如果MMT的维数小于MTM的维数，那么相反的情况就是如此; MTM的特征值将是MMT加上额外的0的特征值。

（？？？？？）

3、Singular-Value Decomposition(svd:奇异分解)

（1）SVD的定义

设M是m*n的矩阵，设其秩为r.然后我们可以得到如下矩阵：

这些矩阵有如下性质：

U：是m*r列正交矩阵(column-orthonormal matrix),每一个列是单位向量，任意两列的点乘是0

V：是n*r的列正交矩阵，但是一般使用其转置形式

is a diagonal matrix

（1）（2）（3）（4）丢失

（5）使用概念查询

*了解SVD如何帮助我们高效准确地回答某些查询。

*建设我们已经有了原始的电影评价（11.6），现在想对矩阵外的用户进行电影评价预测，找到其喜欢的电影。假设其只看过一个电影，评分是4，那么我嫩可以用 q = [4, 0, 0, 0, 0]来表示，就像它是原矩阵中的一行。

*如果是用协同过滤来查找，我们要找到与其相似的用户，然后进行比较预测

*这里和协同过滤相反，我们通过将该向量与V相乘，使其映射到“概念空间”，qV = [2.32, 0].

(6)计算SVD

*矩阵M的SVD强烈连接到对称矩阵 MTM和MMT的特征值 。从两者的关系中，找到最终的分解

*，

• 那么带入上式
• 是对角矩阵，所以它的转置是不变的，所以
• 那么
• 又因为U是列正交矩阵，所以为单位矩阵，则原式子化简为
• 在上式中，在等号的左边乘以一个V,那么
• 因为V也是正交矩阵，所以又可以简化为
• 因为是对角矩阵，那么它的平方仍为对角矩阵，只不过相应的位置的数平方即可

---》那么我们可以说，V其实就是MTM的特征相连，是对应的特征值的矩阵

因此，我们可以得到计算SVD的方法：

• 
• （U是MMT的的特征向量）我们需要去

4、CUR分解

*SVD是有问题的，在实际的大数据应用中，M为稀疏矩阵很正常，我们无法处理很大的密集的矩阵，但即使M是稀疏的，在SVD中，UV也会是密集矩阵。

*考虑另一种分解：CUR---->比起SVD，其优点在于其分解的CR也是稀疏的，只有中间是密集的，但这个矩阵很小，所以密度不大

*只要参数r至少与矩阵M的秩一样大，它就给出精确的分解，无论我们做多大r，CUR分解都是近似值。

（1）CUR的定义

M是mn的矩阵，选择一个概念数量r.一个CUR分解，就是随机选择M的r列，形成mr的矩阵C，然后随机选择r行，形成rn的矩阵R，然后依旧有一个rr的矩阵U，使得：

（2）行列的选择

*虽然说行列是随机选择的,但是在选择时要有偏重，以使得更加重要的行或列有更大的机会被选择

*该偏重使用的重要度量是Frobenius范数的平方，即行或列的元素的平方和。
设，然后，每当我们选择一行时，我们选择第i行的概率 pi

*同理可以的列的概率

（这种设置偏重的方法存在一定的问题，会使得选择不均匀）

*选择了M的列之后，将选择了M的每一列后，通过将每个列的元素除以该列被选中的预期次数的平方根 来缩放每列。

（也就是说，如果选择了M的第j列的元素，则用√rqj划分。 M的缩放列成为C列。）同理，对M进行行处理。

例子,对11.2进行分解：（qi,qj是计算出来的概率）

（3）中间矩阵的创建

U是一个r*r的矩阵，我们用一个大小相同的矩阵W来创建U。W的第i行第j列所对应的元素是M中对应的元素，其行是R中的行，列是C中选中的列。

（4）消除重复的行列

*可以将行进行组合，组合成单行，同样的也可以组合成单列。但对于行或列，剩余的向量应该使其每个元素乘以√k。