D&C

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://leen2010.blogbus.com/logs/124631640.html

前几天讨论班我讲了基于PCA的人脸识别，当时我自己其实也只是知道这个算法流程，然后基于该算法利用c++实现了，效果还不错。后来跟师兄一起讨论的时候，才发现这个PCA还是有相当深刻的意义。
PCA的算法：矩阵C=AA^T，A的每一列是一张人脸^注（将一张人脸图片用一个列向量表示，即对于128*128的图片，将视为16384维的列向量），A的列数就是图片的张数。算法就是求矩阵C的特征向量，每个向量称之为特征脸^[1]。为了简单，只取其中部分的特征向量，这些特征向量对应于某些特征值，通常是前M个大的特征值。这样便得到了M个特征向量。接下来就是将每张图片在这M个特征向量上做投影，得到一个M维的权重向量w=（w₁,…w_M），一个人可能有多张图片，于是将对应于这个人的权重向量做一个平均作为这个人的权重向量。然后对于每个新来的人脸，先求得一个权重向量，然后与人脸库中每个人的权重向量做比较，如果小于某个阈值，则认为他是人脸库中的这个人；否则视为unknown。当然，文章中还给出了另外一个判断一张图像是否是人脸的方法，这里不再讨论。对于计算的时候我们实际上求的是A^TA，至于二者的关系，可以参考文章[1]，因为与后面讨论的关系不大，这里不细说了。
有个上述简介，我们就大概知道了PCA到底是怎么做的了。刨根问底一下，C到底是什么，C的特征向量又到底是什么，对应于特征值大的特征向量有有什么意义。
1.C到底是什么？我们先看一下C的（i,j）元素是什么。很简单，就是A的第i行与A^T的第j列的乘积。那么A的第i行又是什么呢？就是每张图片的第i个像素构成的一个向量。则C的（i,j）元素就是每张图片的第i个像素构成的向量与每张图片的第j个像素构成的向量的乘积。回忆一下概率论中的协方差cov(x,y)=E((x-x^–)(y- y^–)),这里x^– 是x的平均。如果我们把图片的第i个像素视为一个随机变量X_i，那么人脸库中的每张人脸的第i个像素的取值即为这个随机变量的所有取值。根据注，A的第i行的每个值都已经减去了X_i的均值，因此C的（i,j）元素就是随机变量X_i与X_j的协方差。到此，我们已经知道C是什么了。
2.C的特征向量是什么。我们知道对C求特征向量是找到一个可逆矩阵Q，使得Q^-1CQ是一个对角阵D，D的元素即为特征值，Q中的每一列即为特征向量，与特征值所在的列一一对应。注意，因为C是实对称阵，故必然可以对角化。由于C是对称的，C的特征向量是正交的，因此Q便是一个正交阵，故Q^-1即为Q^T。先从简单的角度来看，假设C已经是一个对角阵了，并且对角元素依次递减。即随机变量X_i与X_j(i!=j)时是不相关的，而X_i的方差则随着i的增大而减小。也就是前几个像素是方差比较大的像素，即在第一个像素上，每张图片的值变化最大，第二个像素次之，依此类推。举个例子，假设第一个像素表示人脸的额头上的某个点（也许你会问，第一个像素不是图片的最左上角的那个像素吗？为什么会是额头上的某个点，后面会说明为什么可以这么假设），而在这个点上，有些人有痣，有些人没有，那么这一点的方差就会比相邻的额头上的其他点大，因为其他点上，每个人的额头都差不多，因此其像素值也差不多，方差就小了。现在来考虑Q^TAA^TQ=D,这里依然假设D中的元素依次递减。对于Q^TA，Q^T的每一行是一个特征向量，Q^T的第i行与A的每一列相乘得到Q^TA的每一行，从矩阵的角度也可以看作是用Q^T对A做一个变换。记住这里的Q^TA可以看做前面讨论的A，那么变换的结果就是使得Q^TA前面的行对应的是方差大的像素，而且这个变换会把方差最大的放到了第一行（因为D的降序排列），这里也就解释了为什么前面那个例子可以认为第一个像素是额头上的某个点，因为做了变换。我们选择了Q^T的前M行作为特征向量，因为他们对应了前M个大的特征值。这里可以举一个直观但是不一定恰当的例子，人的头发部分对应的那些像素，经过Q^T变换后回到某个像素上，那么这个像素会是Q^TA中的哪个位置呢，我认为应该是Q^TA的列中靠下面的像素，因为在头发这个像素的地方每个人基本都是头发（这句话很别扭，我是想说，对于比较正规的人脸库，即每张人脸不会有太大的变化，某个人头发的对应的那几个像素对于其他人来说也都是头发，因此变换后这个像素对于每个人都差不多，方差小，固然会在比较靠后的位置了）。Q^TA的每一列的前M个元素对应的就是每张人脸的权重向量w。因此每张人脸的权重向量的同一个分量可以看作是新的像素，这些新的像素对应着方差依次减小的像素。对于一张新来的人脸，让他在特征向量上作投影得到权重向量，在这些方差大的像素处，如果跟某个人的比较接近，则认为是这个人，这个也是合理的。至此，也许没能讲清楚特征向量是什么，但我想对应于特征值大的特征向量有什么意义这一点也交代的差不多了。
3.2中交代了说了，这里想不到有什么需要补充的了。
理解了这几个问题之后，PCA简洁明了（这本来就是的）而又有深刻意义了。我突然发现原来看似简单的理论其实水深的很，o(︶︿︶)o ！我看文章实在是不够认真，如果没有师兄提问，估计我也不会去想这个问题。再次感谢WF师兄。
 
[1]Eigenfaces for Recognition. Matthew Turk,Alex Pentland 1991
注：A的每一列是一张人脸，这里的人脸是每张人脸减去了所有人脸的平均后的人脸

原文见：

http://blog.csdn.net/silenough/article/details/7040028

 
A. 给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数(在文件中至少缺少一个这样的数—为什么？)。在具有足够内存的情况下，如何解决该问题？如果有几个外部的“临时”文件可用，但是仅有几百字节的内村，又该如何解决该问题？
因为2^32 大于40亿，所以文件中至少缺失一个整数。我们从表示每个整数的32位的视角来考虑二分搜索，算法的第一趟（最多）读取40亿个输入整数，并把起始位为0的整数写入一个顺序文件，把起始位为1的整数写入另一个顺序文件。这两个文件中，有一个文件最多包含20亿个整数，接下来将该文件用作当前输入并重复探测过程，但这次探测的是第二个位。如果原始的输入文件包含n个元素，那么第一趟将读取n个整数，第二趟最多读取n/2个整数，第三趟最多读取n/4个整数，依次类推，所以总的运行时间正比于n。
如果内存足够，采用位图技术，通过排序文件并扫描，也能够找到缺失的整数，但是这样做会导致运行时间正比于nlog(n).
1. 考虑查找给定输入单词的所有变位词的问题。仅给定单词和字典的情况下，如何解决该问题？如果有一些时间和空间可以在响应任何查询之前预先处理字典，又会如何？
首先计算给定单词的标识，若果不允许预处理，那么久只能顺序读取整个文件，计算每个单词的标识，并于给定单词的标识进行比较。
 

如果允许进行预处理，我们可以在一个预先计算好的结构中执行二分查找，该结构中包含按标识排序的(标识，单词)对。
2. 给定包含4300 000 000 个32位整数的顺序文件，如何找出一个出现至少两次的整数？
 方法一：
二分搜索通过递归搜索包含半数以上整数的子区间来查找至少出现两次的单词。因为4300000000  > 2^32，所以必定存在重复的整数，搜索范围从[0, 2^32）开始，中间值mid为2^31，若区间[0, 2^31)内的整数个数大于2^31个，则调整搜索区间为[0, 2^31)，反之则调整搜索区间为[2^31， 2^32)，然后再对整个文件再遍历一遍，直到得到最后的结果。这样一共会有log2(n)次的搜索，每次遍历n个整数（每次都是完全遍历），总体的复杂度为o(nlog2(n))。
 

 
   方法二：
 

3. 前面涉及了两个需要精巧代码来实现的向量旋转算法，将其分别作为独立的程序实现。在每个程序中，i和n的最大公约数如何实现？
采用辗转相除法求两个整数的最大公约数。
 

 
 
方法一：海豚算法
 

方法二：块交换算法
 

方法三：求逆算法
根据矩阵的转置理论，对于矩阵AB，要得到BA，则分别求A和B的转置A’, B’，然后对(A’B’)转置，即(A’B’)’ = BA。同理，可以得到另一种一维向量向左旋转的算法。将要被旋转的向量x看做两部分ab，这里a代表x中的前rotdistance个元素。首先对a部分进行反转，再对b部分进行反转，最后对整个向量x进行反转即可。
对于字符串“abcdefgh”, rotdistance = 3, len = 8:
reverse(1, rotdistance);          //cbadefgh
reverse(rotdistance+1, len);  //cbahgfed
reverse(1, len);                       //defghabc
 

 
5. 向量旋转函数将向量ab变为ba。如何将向量abc变成cba？(这个交换非相邻内存块的问题进行了建模)
可以将bc看做一个整体，然后运用向量旋转算法，得到bca。然后对bc运用向量旋转算法，得到cb。最后变换后的向量为即cba.
 

6. 如何实现一个以名字的按键编码为参数，并返回所有可能的匹配名字的函数
用按键编码标识每一个名字，并根据标识排序，然后顺序读取排序后的文件并输出具有不同名字的相同标识。为了检索出给定按钮编码的名字，可以使用一种包含编码标识和其他数据的结构。然后对该结构排序，使用二分搜索查询按键编码。
7. 转置一个存储在磁带上的4000×4000的矩阵(每条记录的格式相同，为数十个字节)。如何将运行的时间减少到半个小时？
给每条记录插入列号和行号，然后调用系统的磁带排序程序先按列排序再按行排序，最后使用另一个程序删除列号和行号。
8. 给定一个n元实数集合、一个实数t和一个整数k，如何快速确定是否存在一个k元子集，其元素之和不超过t？
对n元实数集合先进行排序，然后计算前k个元素的和既可以确定是否存在这样一个子集。若采用快速排序，时间复杂度为nlog10(n)。
9. 顺序搜素和二分搜索代表了搜索时间和预处理时间之间的折中。处理一个n元表格时，需要执行多少次二分搜索才能弥补对表进行排序所消耗的预处理时间？
对于顺序搜索，搜索k次的时间复杂度为O(kn);若采用二分搜索则需要先排序，则二分搜索的时间复杂度为O(nlog10(n)+log2(n))
变位词程序的实现
 

 
 
使用sort程序将具有相同标识的单词归拢到一起，形成一个新的文件。最后调用squash()函数将具有相同变位词的单词在同一行输出。