《数学之美》读书笔记-1
不知道说什么好，数学牛逼！
第9章 图论和网络爬虫
图论的起源：欧拉的哥尼斯堡七座桥问题。
图的遍历：深度优先和广度优先
图与网络爬虫：互联网中的网络之间由超链接相互链接，爬虫相当于对这一张大表进行遍历。如何记录网站是否已经被下载过了呢？用散列表（即哈希表）来记录。关于这部分详见下面的网络爬虫工程的构造。
（有个问题：哈希到底是个什么神奇的东西？？）
欧拉七桥问题
为什么走不通？如果能不重复地走遍的话，每一个点的度数都得是偶数，这样才能走出去了还能回来。哥尼斯堡的陆地有好几个都是单数座桥连通的。
网络爬虫的构建问题
三个方面，URL的获取和记录，遍历方法。（以及我认为还要注意的问题：网络通信瓶颈，分布式结构通信的锁等）
Case1.如何遍历网页？
前面说了图论主要有两种遍历方法：DFS和BFS。在网络爬虫中，由于一个页面相同级别的链接更为重要（如打开首页后，和首页直接链接的网页会更重要）。这有点儿像BFS。
而DFS也有用武之地，由于打开网站有一个和服务器的握手时间成本，以及大型网络爬虫的分布式结构。很多台电脑一起去下载同一个网站的信息，这样就会减少握手次数。在下载一个网站的时候，这个时候用到的又是BFS。（我理解的意思就是对于整体网络，先下完一个再下第二个，这是DFS思想；对于单个网站，下载的信息全部下完，这是BFS）
综上所述，不是简单的BFS或者DFS。需要有一个调度系统，为网页下载的优先级排序，随后按照这个URL队列来进行下载。
Case2.页面分析和URL提取
现在的网页超链接URL信息，由JS脚本语言自动生成，URL不易直接获取，需要有解析程序。
Case3.如何记录已经下载的URL
一个超大散列表也需要分布式存储。避免访问遇到瓶颈，需要一次多条以及明确下载服务器的分工。
“很多数学方法就是这样，看上去没有什么实际用途，但是随者时间的推移会突然派上大用场。”
第10章与第11章 搜索引擎的部分设计
在搜索中，网站的排名取决于网页本身的信息质量和与这个查询和网页之间的相关性。
网页信息质量
别的网站越多地链接到这个网站，这个网站的质量就越高。每一个网站对这个网站的表决权也不同，排名越高的网站，权重越大。这个权重（即排名）的计算，通过矩阵相乘和迭代的方法得到的。
思想：将互联网看作一个整体，并找到数学的方法和模型(图和矩阵)来表示它。
搜索与网页的相关性
TF-IDF：
TF指的是term frequency，一个单词在一篇文章中的频率。IDF指的是Inverse Document Frequency，逆文本频率指数，也就是评价单词在文章中的分布情况。（这个单词是多次出现在一篇文章中还是出现在多篇文章中，但是每篇文章中的出现次数都很少。显然，前一种情况下这个单词更重要。eg.“原子能”和“的”）
*信息论的解释方法（用熵的角度）
第12章 地图与本地搜索
本章不讨论卫星定位的问题。讨论两个问题：1.如何解析用户给出的地址 2.路径规划
分析地址
有限状态机。当然实际情况更复杂（用户的错别字等），这时需要模糊匹配，基于概率的有限状态机。
*最成功的是AT&T的三位科学家写出了有限状态机C语言工具库。
*有限状态传感器是有限状态机的一种特殊情况。它加权形式的模型较多地运用于语音识别和自然语言理解上。与一般的有限状态机不同的是，它的每一个状态都由输入输出来定义。
路径规划
运用到的是图论中的动态规划。动态规划的主要思想就是局部最优再找到全局最优。基于的一条理论是，如果a->b存在一条最短路径，那么它的子路径(a->c)也是所有a->c中最短的。
第13章 阿米特·辛格博士
他推崇简单工程思想，以及他要求（特别是针对机器学习方法）所有的优化方法都要给出原理和解释。
简单的工程思想，他发明了如搜索防作弊、搜索排序等算法。
第14章 文本分类——余弦定理
说是余弦定理的应用，其实更准确的应该是向量的应用。
主要思想（以文本分类为例）：1.提取文本的关键词，由关键词的TF-IDF，将文本转换为由数字表示的向量。2.计算向量（文本）之间的夹角，角度越小则越相似。
具体分类方法又有两种（有点像有监督学习和无监督学习）：
1.根据已知类别的特征向量进行分类。
2.迭代，自动分类（相似文本并成小类，小类之间再计算角度，再并成大类）。
（基于的理论：文本中的主题词能表示一篇文章，主题相近的文章中主题词也相近）
第15章 文本分类——奇异值分解
“一次把所有的新闻相关性计算出来。”
奇异值分解，是将一个大型矩阵$A_{MN}$（一行为一个文本）分解为三个小矩阵。三个小矩阵分别是：
1.酉矩阵$X_{MM}$，每一行代表一个词，每一列代表一个语义类
2.酉矩阵的共轭矩阵$Y_{NN}$，每一列代表一篇文章，每一行代表一个文章类
3.对角阵$B_{MN}$，反映语义词和文章类的相关性（*行代表语义词对文章类的相关性，列代表文章类对语义词的相关性。）
第16章 信息指纹
简单来说，就是“为了把一长串字符转换乘一小串二进制数字”的方法。（用作者的话说，是把一段信息通过一个随机函数映射到多维二进制空间的一个点）
具体应用可以在数据库搜索、信息加密等等。更进一步，还可以用在集合相似度判断、检测文章抄袭和视频反盗版等等。
而且信息指纹有一种特性，就是根据信息可以得到指纹，但是根据指纹很难得到信息。
产生信息指纹的关键算法叫伪随机数生成（PRNG）。PRNG中用的算法又是梅森旋转算法。另外在互联网中经常用到的是基于加密的伪随机数生成器（CSPRGN），有MD5和SHA-1等标准。
*数学拥有简洁之美！数学可以作为信息的另一种表示手段！
* 相似哈希：在判断网页相似度的一种信息指纹的算法。思想不复杂，很牛逼。
1.提取k个关键词，每一个词都有自己的n位指纹$t_k$。
2.设置网页的信息指纹$T$也为n位。
3.将T扩展为n个初始值为0的实数。
4.扫描关键词，指纹位上为0，则对应的T的实数减去权重；反之，加上权重。全部扫描完后，得到的n个实数，压缩为二进制（大于零为1，反之为0）。
后记
先写到这里，也已经有两千多字了。后面的笔记将整理到新的一篇中去，我也打算找另外的笔记形式，这样好像有点复杂。
保研成功啦，这个学期会比较空，会认真审视一下自我也好好计划一下大四这一年。
今天是中秋佳节，祝福大家平安团圆，吃月饼也也不会胖。