玩命的数据分析学习日志（一） - 关联性分析

devilogic

---

话说有天下午和邹老师讨论数据处理方面的东西，这方面我就知道几个名词，什么haddop、hbase之类的，属于哄骗爸妈的那种级别。我问邹老师为啥非关系型数据库例如：mongodb比起关系型数据库例如：mysql要快呢？

邹老师给我解释了半天行存储与列存储之间的关系，我听的是云山雾罩的。大意就是关系型数据库中，数据是以表的形式行进行存储的。要查关联数据时首先要检索到行然后提取出行的某个字段或者说是特性吧。然后做关联查询。而列存储呢？是按照列存储的，就要比行的快。（记不太清楚，邹老师是如何表达的了）。总之是要快。

其实这个弄得我是很晕的。为啥列存储要比行存储检索要快呢？如果从矩阵的角度来看。行矩阵是列矩阵的转置而已，并无什么其他的优点。但是从另外一个角度看就是。无论行还是列存储，如果都按行取出，那么前者取出的是某条完整记录而按照后者取出的是某个特性的全部集合。一条完整的记录拥有很多特性，这些特性之间没法进行统一的运算。而固定某个特性是可以进行统一批量的运算的，之后我直接这样安慰自己。

直到最近的日子，业余时间研究机器学习，想起了正交性这样的概念。尝试的从这个角度理解列存储检索的速度比行的快。

这里需要补充一些基本的数学知识，虽然我不想在一篇技术日志中扩展的来记录数学知识，但是基本概念还是在这里列出，以保持文章的完整。

什么是正交性

引用教科书上的一段话。

两个线段的夹角为直角的充要条件是两个向量对应的标量积为零。一般的若$V$为定义了标量积的向量空间，且$V$中的两个向量的标量积为零，则称它们正交(orthogonal)。

其中标量积就是两个向量的内积，就是一个行向量乘以一个列向量，这样得出的并不是第三个向量，而是一个标量。即$\mathbf{x}$向量与$\mathbf{y}$向量的乘积等于$\mathbf{x}^T\mathbf{y}=x_1y_1+x_2y_2+\cdots+x_ny_n$

也就是说当$\mathbf{x}^T\mathbf{y}=0$时，我们称之为正交。

欧几里德长度

$$||x||=(\mathbf{x}^T\mathbf{x})^{1/2}= \begin{cases} \sqrt{x_1^2 + x_2^2} & \mathbf{x} \in R^2 \\ \sqrt{x_1^2 + x_2^2 + x_3^2} & \mathbf{x} \in R^3 \\ \end{cases}$$

那么两个向量$\mathbf{x}$与$\mathbf{y}$均为$R^2$或$R^3$中的向量。则它们之间的距离定义为数值$||\mathbf{x} - \mathbf{y}||$

求两个向量的夹角

若$\mathbf{x}$和$\mathbf{y}$为$R^2$或$R^3$中的两个非零向量，且$\theta$为它们的夹角，则

$$\mathbf{x}^T\mathbf{y}=||\mathbf{x}||\,||\mathbf{y}||\,cos\theta$$
若$\mathbf{x}$和$\mathbf{y}$为非零向量，则可以通过构造以下单位向量，给出它们的方向：
$$\mathbf{u}=\frac{1}{||\mathbf{x}||}\mathbf{x} \\ \mathbf{v}=\frac{1}{||\mathbf{y}||}\mathbf{y}$$

若$\theta为\mathbf{x}$和$\mathbf{y}$的夹角，则

$$cos\theta = \frac{\mathbf{x}^T\mathbf{y}}{||\mathbf{x}||\,||\mathbf{y}||}$$

举个例子

好吧，有了以上数学知识后，就可以探讨邹老师的那个问题了。例如：我有一个数据库存储了$6$份文档分别为$M_1$到$M_6$，而在每个文档下记录了其中关键字所出现的频率。如果使用列存储则表示为：

$$\begin{array}{c|cccccc} \text{关键字} & \text{文档1} & \text{文档2} & \text{文档3} & \text{文档4} & \text{文档5} & \text{文档6}\\ \hline hacker & 0 & 1 & 3 & 5 & 0 & 0 \\ fuck & 3 & 0 & 1 & 3 & 4 & 6 \\ hooker & 6 & 0 & 2 & 3 & 0 & 0 \\ dick & 5 & 2 & 0 & 6 & 0 & 0 \\ \end{array}$$

表格中的数据为文档出现关键字的次数。假如我们有一个关键字要进行查询，例如：查询fuck,hooker,dick这三个关键字。那么我们只需要构造一个向量，其中要查询向量位置不为$0$，其他元素均为$0$。并且做单位向量处理，需要将搜索向量的各行乘以$\frac{1}{\sqrt{3}}$。这是因为$\sqrt{3} = \sqrt{0^2 + 1^2 + 1^2 + 1^2}$。同样的道理作用于以上的矩阵，归一化处理可将数据统一到一个量级里进行计算，而不使得某个数据过大而引起最终计算结果的导向。
使用以上数据库矩阵，我们称为$\mathbf{M}$乘以搜索向量$\mathbf{s}$，则得到一个结果向量$\mathbf{r}$，这个向量的每一值都是与之相关的夹角的$cos$值。$\mathbf{r}=\mathbf{M}\mathbf{s}$，而$r_i=\mathbf{m_i}^{T}\mathbf{s}=cos\theta_i$
这个值越接近$1$说明两个向量越接近，越接近$0$则说明相关性越远。

R语言的实现

norml <- function(v) {
    u <- v^2
    r <- sum(u)
    return(v / sqrt(r))
}
foo <- function(M, s) {
    mat <- as.matrix(M)
    count <- nrow(mat)
    for (i in 1:count) {
        mat[i,] <- norml(mat[i,])
    }
    v <- norml(s)
    r <- t(mat) %*% t(t(v))
    return(r)
}
v <- c(0,3,6,5,1,0,0,2,3,1,2,0,5,3,3,6,0,4,0,0,0,6,0,0)
mat <- matrix(v, nrow=4, ncol=6)
s <- norml(c(0,1,1,1))
r <- abs(foo(mat, s) - 1)
#print(r)
print(which(r == min(r)))

最终求出是$1$号文档。

后话

其实我也不知道这到底是不是行存储与列存储的区别。其实行列存储只是从一个特性一致的变量可以批量进行计算的角度来看，可以进行大量数据的并行运算。