Data Science

个人面经(百度、腾讯、鹏元数据、行云智能数据岗)

记录自找工作以来个人的面试经历与一些思考。 百度数据挖掘一面(电话面) 介绍项目 问题 基础知识:java的多态、map和垃圾回收 如何用网络知识让抢火车票更快 快排的思想、时间和空间复杂度、如果是整数排序有没有O(n)的解法 逻辑回归线性回归区别 linux怎么查看某文件当前被哪些进程访问 vim如何查找替换 百度运维一面(电话面) 聊项目 python字符串的替换 SQL的优化 LInux 如何找进程杀进程 百度运维二面(现场面) 聊项目 手写冒泡 行云智能一面(现场面) 遇到面试官是西电校友 聊项目 CNN的思想:pooling的方式、卷积的思想 设计模式有什么了解 多线程多进程的了解 快排的思想 手写代码二叉树删除 中科乐创一面(现场面) 最尴尬的一次,面试官是南洋理工的,聊了聊我的项目就似乎对我不感兴趣,就开始和我聊家常。。。 鹏元数据一面(现场面) 聊项目 做了张试卷如 推导极大似然估计 聚类与分类区别,列举常用聚类算法及程序包 一些简单的SQL命令 编程题:列举一串数字内奇偶数出现次数及引申出的结合他们业务的评级转换矩阵的打印 腾讯基础研究一面(现场面) 聊项目 聚类与分类区别,常用聚类算法思考:诸如此类列举算法的问题,最好是迅速流利的列举出多个,不要有迟疑,不过对于其基本含义要有了解。 场景题,两个含有数字的文件,找出同时出现在两个文件内的数字;若文件太大放不进内存该怎么办?思考:这种问题可小可大,可难可易。因为哪怕再小的问题在规模变大也就是涉及到大数据都是不简单的,这个问题,对于小文件,两三行代码即可搞定,那么你写出来之后,面试官基本上就会进一步问你:如果文件很大,无法同时把这两个文件装进内存,怎么办?我当时回答的是用Pandas的read_csv分块读取,这是个很不好的回答,因为掉包不是基本功。我回头想了想,也许这个答案是用generator比较好。  

Sort Algorithms of Linear Time Complexity

常用排序算法如归并、快排、堆排序等基于比较的排序方法都是不能突破$O(n log n)$时间复杂度的,本文着重介绍几种线性时间复杂度的排序方法。 基于比较的排序为何不能突破$O(n log n)$时间复杂度?因为$N$个数有$N!$个可能的排列情况,也就是说基于比较的排序算法的判定树有$N!$个叶子结点,比较次数至少为$log(N!)= O(N log N)$ (斯特林公式) 而线性复杂度的排序方法通常来说有计数排序、桶排序和基数排序三种。 计数排序 计数排序(Counting sort)是一种稳定的线性时间排序算法,Θ(n + k)的时间复杂度。n 是待排序数组的大小,k 是辅助数组 count 的大小。 因为它并不是基于比较的的排序算法,所以它没有O(NlogN)的下限。并且在一定的条件下,使用该算法比使用快排能带来更好的效率。例如在基数排序中就运用了计数排序,因为它只需要额外的10个元素大小的辅助数组,线性的效率,并保证了稳定性。 原理 计数排序的主要思想是将待排序元素的值作为下标,利用辅助数组 count 记录所有的元素出现的次数。即 count[i] 的值代表元素 i 在原始数组中出现的次数。这样,原始数组的所有元素就被有有序地记录下来。 当然,只知道某个元素出现的次数是不足以排序的。仔细观察 count 数组,发现对 count 数组进行累加(count[i] += count[i-1])后,count[i] 的含义就变成了原始数组 i 前面有 count[i]个数是不大于它的。最后就可以根据 count 数组中的排名去构造一个已排序的数组了。 下面以原始数组d = {8, 13, 0, 3, 20, 16, 9, 7, 11, 5} 去演示上述的过程: …

Sort Algorithms of Linear Time Complexity Read More »

Explanation of Convolutional Neural Networks

卷积神经网络(Convolutional Neural Network),简称CNN,是机器视觉领域的主要神经网络模型。本文主要对CNN做一个简明全面的介绍。 上图是90年代的LeNet的结构,当时主要用于字符的识别,当前有许多的新的CNN结构,但是大体上都是采用了与LeNet类似的主要思想。本文主要以LeNet为例来做讲解。 LeNet的主要组成部分: 卷积层 非线性变换(ReLU) 池化层或者下采样 分类(全连接) 图片就是矩阵 在讲卷积与卷积层之前,我们首先介绍一下图片的相关的概念。本质上,每张图片都是像素值的矩阵。 彩色图片具有三个通道,所谓的RGB图片,也就是在红色、绿色和蓝色三个颜色的矩阵,每个像素值都是[0,255]的值。灰度图片只有一个通道,所以只有一个矩阵。 卷积层 CNN由卷积而得名,那么什么是卷积呢?先来看图片 首先我们有如下的5*5的矩阵,它的每个像素值都由0或者1组成 再来一张如下的3*3的矩阵 用这个33的矩阵对以上55的矩阵进行卷积,可以表示为如下的过程, 上述过程可以描述成,33的矩阵首先定位到55的矩阵的左上角,两者覆盖重叠到的部位进行点乘再求和,得到的值是新的矩阵的左上角第一个元素,接着33矩阵向右移动一个像素,也叫一个stride,进行下一次卷积操作,知道遍历完毕,得到一个新的矩阵。在CNN中,这个33的矩阵叫做滤波器或者卷积核,得到的新的矩阵叫做特征映射。可以说,卷积核的作用就是从原图片中发现特征。所以对于同一张图片,我们可以用不同的卷积核去操作,得到完全不同的特征映射。考虑如下的图片, 我们用不同的卷积核进行操作,得到的结果如下, 另一个例子如下, 如图,两个非常相似但是方向不同的卷积核对同一张图片进行卷积,得到的不同的结果。在训练过程中,CNN会自动学习到这些卷积核的参数,但是我们还有一些超参数需要手动确定,如卷积核个数、大小以及网络的结构等等。而特征映射的大小由三个参数来确定, Depth:也就是卷积核的个数,我们用几个卷积核进行操作,那么就可以得到多少个重叠着的特征映射,也就是特征映射的深度。 Stride:卷积时每步移动的大小,容易得知,步子越大,那么卷积的次数也就越小,那么特征映射矩阵也就越小。 Zero-Padding:指的是是否在原图像周围补上零再进行卷积,,这样也是控制特征映射大小的方法,带有Padding和不带有Padding的卷积分别叫做宽卷积和窄卷积。 非线性映射(ReLU) ReLU函数是什么?初一看它的全称Rectified Linear Unit好像特别高大上,其实它的函数形式非常简单,就是 $$output = max(0, input)$$ 也就是将原输入的负值全部替换为0。顺便一说,深度学习业界充斥着这种现象,如多层感知机与神经网络、甚至是Deep Learning这个称号本身都是这样改过来的“好名字”,不得不说,起个好名字对于成功也是非常主要的啊! 话说回来,用ReLU处理过的图片的效果如下: 除ReLU之外,还有sigmoid函数和tanh双曲函数等非线性变换,但是ReLU被证明表现更加,所以也就更常用。 池化层 池化(pooling)也就是信号处理领域的下采样Downsampling,其作用是对特征映射保留主要信息的同时进行降维。根据计算方式的不同可以有Max、Average、Sum等多种pooling方式。 以上展示了使用2*2的窗口对经过卷积和非线性映射的矩阵的Max pooling操作。这里的stride是2个像素,对每个区域采用最大值。在网络中,pooling是对每个特征映射单独操作的,于是我们会得到相同数目的输出。 下图展示了pooling操作, pooling操作显著地减小了输入的空间大小,除此之外, 使得输入更加小,更加容易计算 减小网络的复杂程度,有利于对抗过拟合 使得网络对于扰动等噪音更加鲁棒,因为微小的扰动对于pooling结果没有影响 有益于物体探测的准确性 全连接层 经过两轮的卷积-ReLU-pooling操作,接下来就是标准的全连接神经网络结构了,所谓全连接,也就是上一层的每个神经元都与下一层的每个神经元有连接,倒数第二层的输出是每个类的概率,再经过一个softmax层进行归一化处理,我们得到了最终的输出:和为1的每个分类的概率。 训练过程 上面把CNN拆开了讲,接下来我们把各个组件合起来看一下CNN的训练过程。比如我们的输入是一张船的图片,而输出则是属于船的概率是1,如[0,0,1,0]。 那么训练过程如下 步骤1:以随机值初始化卷积核和权重参数 步骤2:网络得到输入,进行前向的计算(卷积、ReLU和pooling)得到最终各分类的概率,假设是[0.1, 0.3, 0.2, …

Explanation of Convolutional Neural Networks Read More »

Deep Learning Interview

整理一些关于Deep Learning的面试问题。 问题列表 CNN最成功的应用是在CV,那为什么NLP和Speech的很多问题也可以用CNN解出来?为什么AlphaGo里也用了CNN?这几个不相关的问题的相似性在哪里?CNN通过什么手段抓住了这个共性? 以上几个不相关问题的相关性在于,都存在局部与整体的关系,由低层次的特征经过组合,组成高层次的特征,并且得到不同特征之间的空间相关性。如下图:低层次的直线/曲线等特征,组合成为不同的形状,最后得到汽车的表示。 CNN抓住此共性的手段主要有四个:局部连接/权值共享/池化操作/多层次结构。 局部连接使网络可以提取数据的局部特征; 权值共享大大降低了网络的训练难度,一个Filter只提取一个特征,在整个图片(或者语音/文本) 中进行卷积; 池化操作与多层次结构一起,实现了数据的降维,将低层次的局部特征组合成为较高层次的特征,从而对整个图片进行表示。 为什么很多做人脸的Paper会最后加入一个Local Connected Conv? 如果每一个点的处理使用相同的Filter,则为全卷积,如果使用不同的Filter,则为Local-Conv。 后接了3个Local-Conv层,这里是用Local-Conv的原因是,人脸在不同的区域存在不同的特征(眼睛/鼻子/嘴的分布位置相对固定),当不存在全局的局部特征分布时,Local-Conv更适合特征的提取。 什么样的资料集不适合用深度学习? 数据集太小,数据样本不足时,深度学习相对其它机器学习算法,没有明显优势。 数据集没有局部相关特性,目前深度学习表现比较好的领域主要是图像/语音/自然语言处理等领域,这些领域的一个共性是局部相关性。图像中像素组成物体,语音信号中音位组合成单词,文本数据中单词组合成句子,这些特征元素的组合一旦被打乱,表示的含义同时也被改变。对于没有这样的局部相关性的数据集,不适于使用深度学习算法进行处理。举个例子:预测一个人的健康状况,相关的参数会有年龄、职业、收入、家庭状况等各种元素,将这些元素打乱,并不会影响相关的结果。 对所有优化问题来说, 有没有可能找到比現在已知算法更好的算法? No Free Lunch定律:不存在一个通用普适的模型,对于所有的学习问题都能做到性能最佳。 对于训练样本(黑点),不同的算法A/B在不同的测试样本(白点)中有不同的表现,这表示:对于一个学习算法A,若它在某些问题上比学习算法 B更好,则必然存在一些问题,在那里B比A好。 也就是说:对于所有问题,无论学习算法A多聪明,学习算法 B多笨拙,它们的期望性能相同。 但是:没有免费午餐定力假设所有问题出现几率相同,实际应用中,不同的场景,会有不同的问题分布,所以,在优化算法时,针对具体问题进行分析,是算法优化的核心所在。 用贝叶斯机率说明Dropout的原理 Dropout as a Bayesian Approximation: Insights and Applications 何为共线性, 跟过拟合有啥关联? Multicollinearity-Wikipedia 共线性:多变量线性回归中,变量之间由于存在高度相关关系而使回归估计不准确。 共线性会造成冗余,导致过拟合。 解决方法:排除变量的相关性/加入权重正则。 说明如何用支持向量机实现深度学习(列出相关数学公式) 广义线性模型是怎被应用在深度学习中? A Statistical View of Deep Learning (I): Recursive GLMs ← …

Deep Learning Interview Read More »

Amdahl’s law

关于Amdahl’s law。 Amdahl’s law,又叫做阿姆达尔定律,其意义在于表示了计算机并行计算处理任务的加速的极限。 简略证明 解释如下,假设一个任务需要时间$T$来完成,而其中可以被并行处理加速的部分比例为$p$,那么不能被并行计算加速的部分就为$1-p$,比如从磁盘上读取程序段就不能并行加速,而读取完成到内存中就可以开多个进程或者利用分布式的方法并行处理来加速。 $$T = (1-p)T + pT$$ 开启加速后,可以加速的部分时间减少至原来的 $frac {p} {s}$ $$T’ = (1-p)T + frac p s T$$ 则加速比就为 $$S_{text{latency}}(s) = frac {T} {T’} = frac{1}{1 – p + frac p s}$$ 意义 Amdahl’s law揭示了不管如何的进行并行计算,只要任务包含无法被并行加速的部分,那么加速比是有上限的,因为 $$lim_{s rightarrow infty} S_{text{latency}}(s) = frac {T} {T’} = frac{1}{1 – p}$$ 例如如下图中的例子,如果任务的95%可以并行,那么加速的极限约为20倍。  

数据挖掘流程:数据可视化与预处理

数据挖掘的第一步,当我们手中拿到一份数据,当然是对数据进行观察与预处理了。本文主要对这两个方面做一个个人的总结。 import 掉包? 第0步,调包。。 通常numpy、pandas、scipy、seaborn已经matplotlib是必须的 为防止烦人的warning,还需要 12 import warningswarnings.filterwarnings('ignore') 因为我们不管warning只管error,哈哈 seaborn的设置颜色格式 1 sns.set_style('whitegrid') 以及 1 %matplotlib inline 观察与可视化 一般来说,我们应该首先观察标签的分布以及特征的分布,对于前者通常使用pandas Dataframe的columns,对于后者则是value_counts()和describe()来展示。如 1 df_train.columns 1 int_level = train_df['interest_level'].value_counts() 1 df_train['SalePrice'].describe() describe()会给出标签的各种数值信息,如 123456789 count 1460.000000mean 180921.195890std 79442.502883min 34900.00000025% 129975.00000050% 163000.00000075% 214000.000000max 755000.000000Name: SalePrice, dtype: float64 同时也可以借助于seaborn图来显示 1 sns.distplot(df_train['SalePrice']); 接下来可以看看标签的偏度和峰度(skewness and kurtosis) 12 print("Skewness: %f" % df_train['SalePrice'].skew())print("Kurtosis: %f" % …

数据挖掘流程:数据可视化与预处理 Read More »

Devide and Conquer Counting Inversions with Python

本文主要内容关于python归并排序求逆序数的算法。 解决问题:给定有限长度的无重复乱序数组,求其逆序数个数。简单来说我们可以用两个循环来解决,但是复杂度为$O(N^2)$,若利用归并排序,复杂度就降为了$O(N log(N))$。以下给出一个实现, 123456789101112131415161718192021222324252627282930313233343536373839404142 class Ivrs_num(object): def __init__(self, filename): self.count = 0 self.filename = filename def load_txt(self): '''载入txt文件保存为list''' int_list = [] with open(self.filename) as f: for line in f: int_list.append(int(line)) return int_list def merge(self, ListA, ListB): '''将两个已经排序好的数组合并成新的排序好的数组 顺便计算逆序数''' newList = [] while ListA and ListB: if int(ListA[0]) > int(ListB[0]): self.count += len(ListA) newList.append(ListB.pop(0)) else: newList.append(ListA.pop(0)) …

Devide and Conquer Counting Inversions with Python Read More »