​ 要了解深拷贝和浅拷贝，首先要明确python中的可变类型和不可变类型。

不可变数据类型

• Number（数字）
• String（字符串）
• Tuple（元组）

可变数据类型

• List（列表）
• Dictionary（字典）
• Set（集合）

深拷贝和浅拷贝

浅拷贝

​ 浅拷贝直接

1.对于不可变类型 Number String Tuple,浅复制仅仅是地址指向，不会开辟新空间。

2.对于可变类型 List、Dictionary、Set，浅复制会开辟新的空间地址(仅仅是最顶层开辟了新的空间，里层的元素地址还是一样的)，进行浅拷贝

3.浅拷贝后，改变原始对象中为可变类型的元素的值，会同时影响拷贝对象的；改变原始对象中为不可变类型的元素的值，只有原始类型受影响。

深拷贝

1.除了顶层拷贝，还对子元素也进行了拷贝

2.经过深拷贝后，原始对象和拷贝对象所有的元素地址都没有相同的了

1.用一条语句查询出每门课都大于80分的学生姓名

解法一：

1
2
3

select distinct name from table where name not in (
	select distinct name from table where score<=80
)

解法二：

1

select name from table groupby name having min(fenshu)>80

2.删除除了自动编号不同外，其他都相同的学生冗余信息

1

delete tablename where 自动编号 not in (select min(自动编号) groupby 学号，姓名，课程编号，课程名称，课程分数)

3.有两个表A 和B ，均有key 和value 两个字段，如果B 的key 在A 中也有，就把B 的value 换为A 中对应的value

1

update b set b.value=(select a.value from a where a.key=b.key) where b.id in (select b.id from b,a where b.key=a.key);

5.查询表A中存在ID重复三次以上的记录

1

select * from(select count(ID) as count from table group by ID)T where T.count>3

6.取出每个班级成绩前两名的同学，表结构为sno、sname、class、score

1
2
3

select sname,class,score from grade where (
  select count(*) from grade as f where f.class==grade.class and f.score>=grade.score
) <=2

6.经典的学习成绩问题

已知关系模式：

​ s (sno,sname) 学生关系。sno 为学号，sname 为姓名
​ c (cno,cname,cteacher) 课程关系cno 为课程号，cname 为课程名，cteacher 为任课教师
​ sc(sno,cno,scgrade) 选课关系。scgrade 为成绩

1．找出没有选修过“李明”老师讲授课程的所有学生姓名

1

select sname from s where cno in (select cno from c where cteacher=='李明')

2．列出有二门以上（含两门）不及格课程的学生姓名及其平均成绩

1
2

3．列出既学过“1”号课程，又学过“2”号课程的所有学生姓名
4．列出“1”号课成绩比“2”号同学该门课成绩高的所有学生的学号
5．列出“1”号课成绩比“2”号课成绩高的所有学生的学号及其“1”号课和“2”号课的成绩

Map reduce

Map 阶段

1、先将HDFS中的输入文件file按照一定的标准进行切片

2、调用自己编写的map逻辑，将输入的键值对变成

3、按照一定的规则对输出的键值对进行分区

4、对每个分区中的键值对进行排序。

Reduce 阶段

1、对多个Mapper任务的输出，按照不同的分区，通过网络拷贝到不同的Reducer节点上进行处理，将数据按照分区拷贝到不同的Reducer节点之后，对多个Mapper任务的输出在进行合并，排序。

2、调用自己的reduce逻辑，将键值对变为.在这里注意：每一个键值对都会调用一次reduce函数。

3、将Reducer任务的输出保存到指定的文件中。

​ 最近在面试中遇到问python代码效率优化的问题，感觉答的很混乱，所以想来整理下python代码优化的常见手段。

1.尽量使用python内置函数

​ Python 的标准库中有很多内置函数，它们的运行效率都很高。因为很多标准库是使用 C 语言编写的。

2.字符串拼接使用python的标准式

​ python字符串的连接方式主要有：

1.使用”+”做字符串拼接

​ 在 Python 中，字符串变量在内存中是不可变的。如果使用 “+” 拼接字符串，内存会先创建一个新字符串，然后将两个旧字符串拼接，再复制到新字符串。

2.使用%运算符连接

1 2 3 4 5

> fir = 'hello' > sec = 'monkey' > result = '%s, %s' % (fir, sec) > print(result) >

>

3.使用format格式化连接

1 2 3 4 5

> fir = 'hello' > sec = 'monkey' > result = '{}, {}'.format(fir, sec) > print(result) >

>

4.使用join的方式

​ 这是一种技巧型方法，一般用于连接列表获元组中的字符串。

1 2 3 4

> list = ['1', '2', '3'] > result = '+'.join(list) > print(result) >

​ 选用后面三种方式替代”+”字符串拼接

3.需要单次遍历的迭代的数组采用生成器替代

​ 生成器拥有惰性计算的特点，并不不会一次性生成全部的值存储在内存中，而是在运行时生成值，因此可以大大节省内存空间。

4.使用while 1代替while True(在python2中)

​ 由于Python2中，True/False不是关键字，因此我们可以对其进行任意的赋值，这就导致程序在每次循环时都需要对True/False的值进行检查；而对于1，则被程序进行了优化，而后不会再进行检查。

5.条件语句规范化，使用if x代替if x==True

​ x==True会多出一步比较操作

HTTP协议

HTTP协议组成

请求报文包含三部分：

• 请求行：包含请求方法、URI、HTTP版本信息
• 请求首部字段
• 请求内容实体

post和get区别

区别一：

• get重点在从服务器上获取资源。
• post重点在向服务器发送数据。

区别二：

• get传输数据是通过URL请求，以field（字段）= value的形式，置于URL后，并用”?”连接，多个请求数据间用”&”连接，如http://127.0.0.1/Test/login.action?name=admin&password=admin，这个过程用户是可见的。
• post传输数据通过Http的post机制，将字段与对应值封存在请求实体中发送给服务器，这个过程对用户是不可见的。

区别三：

• Get传输的数据量小，因为受URL长度限制，但效率较高。
• Post可以传输大量数据，所以上传文件时只能用Post方式。

区别四：

• get是不安全的，因为URL是可见的，可能会泄露私密信息，如密码等。
• post较get安全性较高。

区别五：

• get方式只能支持ASCII字符，向服务器传的中文字符可能会乱码。
• post支持标准字符集，可以正确传递中文字符。

为什么说HTTP协议是无状态协议？怎么解决无状态问题

无状态协议对于事务处理没有记忆能力。缺少状态意味着如果后续处理需要前面的信息

解决办法： 1、Cookie 2、通过Session会话保存。

说一下Http协议中302状态(阿里经常问)

http协议中，返回状态码302表示重定向。

这种情况下，服务器返回的头部信息中会包含一个 Location 字段，内容是重定向到的url。

在浏览器中输入url后的过程

1.DNS解析：会根据URL逐层查询DNS服务器缓存，直到找到目标IP地址

2.三次握手，TCP连接

3.发送HTTP请求报文

4.返回HTTP响应报文页面

5.根据HTTP页面内容请求页面中的js、xss等，进行页面渲染

6.断开TCP连接，四次挥手

SYN攻击：

​ 在三次握手过程中，服务器发送SYN-ACK之后，收到客户端的ACK之前的TCP连接称为半连接(half-open connect).此时服务器处于Syn_RECV状态.当收到ACK后，服务器转入ESTABLISHED状态.
Syn攻击就是 攻击客户端 在短时间内伪造大量不存在的IP地址，向服务器不断地发送syn包，服务器回复确认包，并等待客户的确认，由于源地址是不存在的，服务器需要不断的重发直 至超时，这些伪造的SYN包将长时间占用未连接队列，正常的SYN请求被丢弃，目标系统运行缓慢，严重者引起网络堵塞甚至系统瘫痪。

Cookie和Seesion

​ Cookie是服务器发给浏览器的特殊信息，并会以文本形式存在浏览器中，所以我们点击浏览器的清除记录，往往会问我们是否清理Cookie，当清理之后下次再访问网页就会需要我们重新登录。如果浏览器中存在Cookie，那么提交请求就会一起提交过去服务器在接收到后就会解析Cookie生成与客户端相对应的内容，实现自动登录，Cookie带有我们的比较重要信息，所以一般不要给被人获取

　　Session是在服务器上保存的信息，当服务器需要为客户创建Session的时候，就会解析客户端请求查看请求是否包含session id，如果包含那么就表明此前已经为客户端创建过session，不包含则创建一个对应的session id，而后回发给客户端，使得客户端下次能带有session id。然后按需保存状态

　　所以最终的区别总结起来就是：Cookie数据存放在客户浏览器上，Session数据存放在服务器上，Session相对应Cookie安全，而使用Cookie会给服务器减负

什么是HTTPS？和HTTP协议相比优势在哪里？

HTTPS就是HTTP加上加密处理（一般是SSL安全通信线路）+认证+完整性保护

​ 1.通信内容不加密，内容可能被窃听

​ 2.不验证通信对方的方式，可能遭到伪装

​ 3.无法验证报文的完整性，可能被篡改

常见状态码

200 OK 客户端请求成功

400 Bad Request 由于客户端请求有语法错误，不能被服务器所理解。

401 Unauthonzed 请求未经授权。这个状态代码必须和WWW-Authenticate报头域一起使用

403 Forbidden 服务器收到请求，但是拒绝提供服务。服务器通常会在响应正文中给出不提供服务的原因

404 Not Found 请求的资源不存在，例如，输入了错误的URL。

500 Internal Server Error 服务器发生不可预期的错误，导致无法完成客户端的请求。

503 Service Unavailable 服务器当前不能够处理客户端的请求，在一段时间之后，服务器可能会恢复正常

DNS协议

DNS协议功能：完成域名->IP的映射

端口：53

域名解析顺序

1.浏览器内部缓存

​ 浏览器自身的DNS缓存，缓存时间比较短，大概只有1分钟，且只能容纳1000条缓存

2.Chrome会搜索操作系统自身的DNS缓存

​ 如果浏览器自身的缓存里面没有找到对应的条目，那么Chrome会搜索操作系统自身的DNS缓存,如果找到且没有过期则停止搜索解析到此结束

3.尝试读取host文件

​ 如果在Windows系统的DNS缓存也没有找到，那么尝试读取hosts文件， 看看这里面有没有该域名对应的IP地址，如果有则解析成功。

4.先访问系统配置的首选DNS服务器

​ 浏览器就会发起一个DNS的系统调用，就会向本地配置的首选DNS服务器（一般是电信运营商提供的，也可以使用像Google提供的DNS服务器）发起域名解析请求

5.如果首DNS服务器不能解析,则由首选DNS服务器代替向各个DNS(迭代式)
(1)首先访问根域名服务器(DNS服务器内一般都会内置13台根域名服务器的地址)，查询完整域名的ip地址（www.baidu.com），但是根域名会回答不知道完整域名的地址，但知道顶级域名(.com)的ip地址

​ (2)再去访问对应顶级域名的ip地址，尝试查询完整域名的ip地址，但是顶级域名服务器告诉运营商的DNS我不知道完整域名（www.baidu.com）这个域名的IP地址，但是我知道baidu.com这个域的DNS地址

​ (3)这样无限迭代，直到查到完整域名的ip地址

DNS劫持

​ DNS劫持就是通过劫持了DNS服务器，通过某些手段取得某域名的解析记录控制权，进而修改此域名的解析结果，导致对该域名的访问由原IP地址转入到修改后的指定IP，其结果就是对特定的网址不能访问或访问的是假网址，从而实现窃取资料或者破坏原有正常服务的目的。DNS劫持通过篡改DNS服务器上的数据返回给用户一个错误的查询结果来实现的。

解决办法：换用高可信的DNS服务器，比如GoogleDNS 8.8.8.8

DNS污染

​ DNS污染，指的是用户访问一个地址，国内的服务器(非DNS)监控到用户访问的已经被标记地址时，服务器伪装成DNS服务器向用户发回错误的地址的行为。范例，访问Youtube、Facebook之类网站等出现的状况。

​ DNS污染症状：目前一些被禁止访问的网站很多就是通过DNS污染来实现的，例如YouTube、Facebook等网站。

经典题目

1、海量日志数据，提取出某日访问百度次数最多的那个IP。

分析:IP的数目还是有限的，共2^32个，因此可以直接进行hash map

解决方案:

​ 首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最大的IP中，找出那个频率最大的IP，即为所求。

2.有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。

3.有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。

方案：顺序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件（记为x0,x1,…x4999）中。这样每个文件大概是200k左右。

　　如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。 对每个小文件，统计每个文件中出现的词以及相应的频率（可以采用trie树/hash_map等），并取出出现频率最大的100个词（可以用含100个结点的最小堆），并把100个词及相应的频率存入文件，这样又得到了5000个文件。下一步就是把这5000个文件进行归并（类似与归并排序）的过程了。

4.给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？

方案1：

​ 可以估计每个文件的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

　　遍历文件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个小文件（记为a0,a1,…,a999）中。这样每个小文件的大约为300M。

　　遍历文件b，采取和a相同的方式将url分别存储到1000小文件（记为b0,b1,…,b999）。这样处理后，所有可能相同的url都在对应的小文件（a0vsb0,a1vsb1,…,a999vsb999）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。

　　求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。

5.在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。

方案1：

​ 采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。

1.10M内存完成一个100G文件的排序

利用内存和硬盘共同进行排序，每个内存

2.高考满分750，有100w个考生的成绩，求第一百名的成绩（要求最优）。

使用字典，桶排序

海量数据处理题目常用方法

1.Hashing

​ 适用范围：快速查找，删除的基本数据结构，通常需要总数据量可以放入内存

问题实例：

（1).海量日志数据，提取出某日访问百度次数最多的那个IP(经典题目一)。

2.bit-map

​ 适用范围：可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下

​ 基本原理及要点：使用bit数组来表示某些元素是否存在，比如8位电话号码

问题实例：

1)已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。

　　8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。

2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。

　　将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map。

3.堆

​ 适用范围：海量数据前n大，并且n比较小，堆可以放入内存

​ 基本原理及要点：最大堆求前n小，最小堆求前n大。方法，比如求前n小，我们比较当前元素与最大堆里的最大元素，如果它小于最大元素，则应该替换那个最大元素。这样最后得到的n个元素就是最小的n个。适合大数据量，求前n小，n的大小比较小的情况，这样可以扫描一遍即可得到所有的前n元素，效率很高。

问题实例：

1)100w个数中找最大的前100个数。

​ 用一个100个元素大小的最小堆即可。

4.外排序

​ 适用范围：大数据的排序，去重

　基本原理及要点：外排序的归并方法，置换选择败者树原理，最优归并树

问题实例

1) 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。

分析:因为是计算频数，因此肯定没有办法用位图法，然后考虑是否能用hashing法，内存限制仅为1M，因此也不行，因此考虑外排序法。

方案：顺序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件（记为x0,x1,…x4999）中。这样每个文件大概是200k左右。

　　如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。 对每个小文件，统计每个文件中出现的词以及相应的频率（可以采用trie树/hash_map等），并取出出现频率最大的100个词（可以用含100个结点的最小堆），并把100个词及相应的频率存入文件，这样又得到了5000个文件。下一步就是把这5000个文件进行归并（类似与归并排序）的过程了。

trie树

问题实例：

　1).有10个文件，每个文件1G，每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序。

　2).1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。请问怎么设计和实现？

　3).寻找热门查询：查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个，每个不超过255字节。　　

第一步、先对这批海量数据预处理，在O（N）的时间内用Hash表完成排序；然后，第二步、借助堆这个数据结构，找出Top K，时间复杂度为N‘logK。 即，借助堆结构，我们可以在log量级的时间内查找和调整/移动。因此，维护一个K(该题目中是10)大小的小根堆，然后遍历300万的Query，分别和根元素进行对比所以，我们最终的时间复杂度是：O（N） + N’*O（logK），（N为1000万，N’为300万

​ 在日常使用中我们常常会用到ping和traceroute，正好在面试中遇到了这个问题，特来整理一下，下面我们将对这两个协议的具体工作原理进行总结。

Ping

​ Ping 是 ICMP 的一个重要应用，主要用来测试两台主机之间的连通性。Ping 的原理是通过向目的主机发送 ICMP Echo 请求报文，目的主机收到之后会发送 Echo 回答报文。Ping 会根据时间和成功响应的次数估算出数据包往返时间以及丢包率。

ping完成的工作流程

构造ICMP数据包—>构造IP数据包—>构造以太网数据帧——物理传输到目标主机——>获取以太网数据帧—>解析出IP数据包—>解析出ICMP数据包—>发送回送应答报文

Traceroute

​ Traceroute 是 ICMP 的另一个应用，用来跟踪一个分组从源点到终点的路径。有2种实现方案：基于UDP实现和基于ICMP实现。

基于UDP的实现

​ 在基于UDP的实现中，客户端发送的数据包是通过UDP协议来传输的，使用了一个大于30000的端口号，服务器在收到这个数据包的时候会返回一个端口不可达的ICMP错误信息，客户端通过判断收到的错误信息是TTL超时还是端口不可达来判断数据包是否到达目标主机。

1. 源主机向目的主机发送一连串的 IP 数据报（UDP报文）。第一个数据报 P1 的生存时间 TTL 设置为 1，当 P1 到达路径上的第一个路由器 R1 时，R1 收下它并把 TTL 减 1，此时 TTL 等于 0，R1 就把 P1 丢弃，并向源主机发送一个 ICMP 时间超过差错报告报文；
2. 源主机接着发送第二个数据报 P2，并把 TTL 设置为 2。P2 先到达 R1，R1 收下后把 TTL 减 1 再转发给 R2，R2 收下后也把 TTL 减 1，由于此时 TTL 等于 0，R2 就丢弃 P2，并向源主机发送一个 ICMP 时间超过差错报文。
3. 不断执行这样的步骤，直到最后一个数据报刚刚到达目的主机，主机不转发数据报，也不把 TTL 值减 1。但是因为数据报封装的是无法交付的 UDP，因此目的主机要向源主机发送 ICMP 终点不可达差错报告报文。
4. 之后源主机知道了到达目的主机所经过的路由器 IP 地址以及到达每个路由器的往返时间。

如何获得路过的各个路由信息？

从1开始，每个TTL+1，到每个路由时TTL到0就会回复超时，这样客户端就可以得到每个路过的路由

基于ICMP的实现

​ 直接发送一个ICMP回显请求（echo request）数据包，服务器在收到回显请求的时候会向客户端发送一个ICMP回显应答（echo reply）数据包。流程与上面相似，只是最后判断结束上为目标主机（而不是中间经过的主机或路由器）返回一个ICMP回显应答，则结束。

1.二叉树前、中、后、层次非递归写法

2.排序算法(尤其是快排)

3.100000个数中找出最大的k个数

算法：

1.模型的评价指标计算公式

​ 精确率：判黑真正为黑的占判黑总数的比例

​ 召回率：正确判黑的占黑样本总数的比例

​ ROC曲线：在各个阈值下模型以FPR为横坐标、TPR为纵坐标，画的曲线

​ AUC：ROC曲线线下面积

2.AUC指标详解

计算公式：ROC曲线的线下面积

概率解释：在正负样本中随机取一对正负样本，其中正样本得分大于负样本得分的概率

AUC是否受正负样本比例的影响？

​ AUC不受正负样本比例的影响，用正负采样过后的测试集和用不进行采样的测试集AUC基本不变

AUC和其他评价指标相比的优势在哪里？为什么？

​ 改评价指标不受测试集正负样本比例的影响，相比于其他评估指标，例如准确率、召回率和F1值，负样本下采样相当于只将一部分真实的负例排除掉了，然而模型并不能准确地识别出这些负例，所以用下采样后的样本来评估会高估准确率；因为采样只对负样本采样，正样本都在，所以采样对召回率并没什么影响。这两者结合起来，最终导致高估F1值！

3.word2vec介绍，如何进行训练？有那两种区别是什么？大数据情况下那种更适合？

a.介绍

​ 一种词向量的表达，能使词的表达具有一定的上下文信息，原始的word2vec是一个浅层神经网络，首先把全部词进行one-hot，那么每个词将对应着一个特征向量，

​ （1）.首先是一个线性的Embedding层。在word2vec进行训练的时候，将输入2k个词的词向量，通过一个共享的D*V（V是词典大小，D是Embebdding的向量维度）的矩阵C，映射为2k个分布式的词向量。C矩阵例存储了要学习的word2cev向量

​ （2）.忽略上下文的序列信息：输入所有的词向量都汇总到一个Embedding layer(加和取平均)

​ （3）.用softmax进行映射，得到这个词是各个词的概率

​ （4）.然后根据这个词本身的情况来进行更新

​ c.有那几种？区别是什么？

​ Cbow：每次用前后k个词词来预测中间的1个词 词向量更新n词，时间复杂度较低

​ Skip-gram：用1个词预测前后k个词 词向量更新kn词，时间复杂度较高 更适合数据较少的情况

​ d.大数据情况下更适合哪种？为什么？

​ 更适合适用Cbow，因为效率较高

​ e.有哪几种优化方式？具体讲一下哈弗曼树方式如何进行训练和预测

​ 分层softmax：

​ 负采样：

​ f.局限性

​ （1）.只能考虑局部的词之间的关联性

​ （2）.没有考虑词之间的内在联系

​ g.实质

​ 计算输入向量和输出向量的余弦相似度

4.SVM

1.公式推导

2.损失函数

​ hinge(折页损失函数)+正则

3.映射到的核函数空间有什么要求(核函数要求)？

​ 过某非线性变换 φ( x) ，将输入空间映射到高维特征空间，在低维输入空间存在某个函数 K(x, x′) ，恰好等于在高维空间中这个内积，即K( x, x′) =<φ( x) ⋅φ( x′) > (这样的函数K被称作核函数)

4.点到向量距离公式推导

5..生成模型和判别模型

1.定义

​ 生成模型：学习得到数据的联合分布P(x,y)，然后求联合分布。能够学习到数据的生成机制。

​ 判别模型：学习的到概率的条件分布P(y|x)

2.区别

​ 数据量和准确率：生成模型的数据量需求比较大，在数据量足够多的时一般生成模型效果较好，因为联合分布能够提供更多的有效信息；而判别模型需要的数据量较小，引起直接面向预测在小数据条件下一般效果比生成模型效果好

​ 速度：生成模型收敛速度较快

​ 隐变量情况：生成模型能够应付(高斯混合模型就是生成模型的隐变量形式)

3.常见的生成模型和判别模型

​ 生成模型：隐马尔科夫链、朴素贝叶斯

​ 判别模型：csrf

6.xgboost

XGBoost的损失函数是什么，节点划分准则是什么？

​ 损失函数：

​ 节点划分准则：

​ 分类树：信息增益获信息增益比

​ 回归树：最大均方误差

整体流程：

Xgboost和GBDT算法时间复杂度是多少？

​ 针对每个特征，把属于该节点的训练样本根据该特征值升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的最大收益（采用最佳分裂点时的收益）

​ 时间复杂度:O(nlogn d m)(n是样本个数，d是特征个数,m是树的深度)

xgboost是如何进行剪枝的？

​ xgboost采用后剪枝的方式进行剪枝，即 从顶到底建立所有可以建立的子树，再从底到顶反向进行剪枝，这样不容易陷入局部最优解。

xgboost和gbdt的区别：

​ 1.xgboost是gbdt的工程化实现

​ 2.xgboost加入了正则化信息

​ 3.xgboost允许使用自定义的损失函数

​ 4.xgboost损失函数加入了二阶导数信息，下降的更快更准

​ 5.xgboost支持和随机森林一样的列抽样

​ 6.xgboost支持并行化，但是并不是树与树之间的并行化，而是在最费时的特征排序截断进行并行化，将排序结果进行分桶保存，各个树生成时复用

​ 7.xgboost基模型除了支持gbdt支持的CART树外还支持其他的基模型

7.样本不平衡问题处理办法

8.L1正则化和L2正则化

极大似然和最大熵

​ 异常检测，是指在大量正常的行为中找出少量的异常行为。

常见异常检测方式

无监督异常检测

​ 无监督的异常检测模型整体上可以划分为5大类：统计和概率模型、线性模型、基于相似度衡量的模型、集成异常检测和模型融合、特定领域的异常检测。

• 统计和概率模型：分为假设和检验两部分，假设数据的分布与检测异常。例如对一维数据假设符合高斯分布，然后将3 sigma以外的数据划分为异常；对于高维数据，假设特征之间是独立的，可以计算每个特征维度的异常值并相加，如果特征之间是相关的则可以假设多为高斯分布，可以用马氏距离衡量异常度。

  • 代表检测算法：分位点法、Z-score算法。

• 线性模型：假设数据在低维空间有嵌入，那么在低位空间投影后表现不好的数据则认为是异常点。例如PCA算法有两种异常检测思路，一种是将数据映射到低维空间，然后在特征空间不同维度上查看每个数据点和其他数据点的偏差，另一种是看重构误差，想映射到低维然后再映射回高维，异常点的重构误差更大。

  • 代表检测算法：PCA、OneClassSVM

• 基于相似度衡量的检测模型：异常点因为和正常点的分布不同，因此相似度较低，由此衍生出了一些根据密度、距离、划分超平面等相似度衡量指标进行异常检测的模型。

  • 代表检测算法：KNN、Local Outlier Factor（局部相对密度）、Isolation Forest（划分超平面）

• 集成异常检测与融合模型

1.分位点法

​ 超过四分位点之外的数据可以认为是异常数据

2.Z-score(高斯分布)

​ 使用情况：一维或低维空间的异常检测算法

该技术是假定数据时高斯分布，异常值是分布尾部的数据点，因此原理数据的平均值

3.孤立森林

略

python实现：

1
2
3
4
5
6
7

from sklearn.ensemble import IsolationForest
import pandas as pd

clf = IsolationForest(max_samples=100, random_state=42)
table = pd.concat([input_table['Mean(ArrDelay)']], axis=1)
clf.fit(table)
output_table = pd.DataFrame(clf.predict(table))

4.聚类

​ 最常采用的方式就是聚类的方式，根据不同聚类算法的特点，使用各种聚类算法时也有不同的方法和应用场景，下面来具体介绍一下我对聚类在异常检测中的常见做法

Kmeans

​ 注意：Kmeans法做异常检测注意一定要做归一化

使用方法一

​ 聚类完成后，使用距离中心点最远的第n个点到中心点的距离为阈值，大于阈值则为异常点

使用方法二

​ 使用历史的全部数据进行聚类，使用这个聚类模型可以将数据中离质心最远的点找出来，将这个点到质心的距离设置为阈值，当有新数据进来时，判断这个数据到其质心的距离是否大于阈值，超过这个阈值则认为是异常。

​ 问题：历史数据并非全部为正常数据，也包含了异常数据

​ 解决 : 可以先将各个类中距离最远的那部分数据进行人工查看，确定不存在异常

DBSAN

​ 直接对数据进行聚类，将不属于任意一类的样本作为异常样本

【参考文献】

• 无监督异常检测模型原理与安全实践

​ 本文重点介绍UEBA概念、UEBA在国内外各大厂商的引用情况、机器学习技术在UEBA产品中如何进行应用等方面来对UEBA介绍，作为近段时间UEBA相关工作调研的总结。

UEBA

​ UEBA用户实体行为分析，

UEBA的核心点

1.跨越SIEM/ROC产品，UEBA产品考虑更多的数据源。

​ 从网络设备、系统、应用、数据库和用户处收集数据,有更多的数据，是其成功的条件之一。

2.数据驱动，但并不是单纯依靠数据驱动。一般都是数据驱动+专家驱动的混合系统。

单纯的数据驱动的问题：

​ 1.在学习之处很难拿到十分完善的数据，每当有新的数据源都需要重新进行学习，对于工程化来说是一场灾难

​ 2.增加features很难做到快速部署

​ 3.机器学习的到的结果是黑盒，不能解释说明，因此用户很难直接根据机器学习的结果直接进行响应和判别

3.并不是单纯的依靠机器学习，而是机器学习和统计学习相结合。

异常主要来源于两个方面：

​ 1.统计特征。例如用户访问文件夹数量异常、是否第一词访问某个较敏感的文件夹等

​ 2.可以输出确信度很高的机器学习结果。如DGA域名机器学习检测结果

异常并不会直接给用户告警，而是作为下一步机器学习的元数据features，根据这些features再利用及机器学习模型快速确定不同features对应的风险值，风险值大于一定的阈值才会进行告警。

4.必须针对特定的应用场景才能起到很好的效果

各大厂商应用情况和业内共识

常用解决的问题

1.账号失陷检测

2.主机失陷检测

3.数据泄漏检测

4.内部用户滥用

5.提供事件调查的上下文

UEBA建立的关键点

1.定义需要解决的风险场景

2.采集高质量多种类的数据

3.专家驱动和数据驱动相结合

4.其他系统平台进行集成

内部威胁检测

1.基于历史登录行为异常检测

2.基于同组成员分析判别文件拷贝行为违反DLP(数据泄露防护)

3.是否存在上传敏感行为

UEBA建立流程：

1、通过使⽤深度学习和建模技术，⼚商给异常检测模型（即⽆监督式模型）提供训练数据，使模型能够决定哪些变量对分析⽽⾔⾮常重要。这就是所谓的特征抽取过程。

2、接着，异常检测模型将识别出排在前列的异常值，发送给安全⼈员进⾏评审和标识，例如，算作“好的”或“坏的”事件。（发送多少异常值给安全⼈员取决于他们评审的能⼒。）

3、这个标识过程将被填充到监督式学习模块中，构建监督式模型。随着新标识不断增加，此模型也将持续得到优化和验证。

4、⼀旦监督式模型经过优化和测试，将会被⽴即部署，⽤来预测输⼊数据。根据⽤户设置的⻛险阈值以及⽤户的评审能⼒，向⽤户发送所预测到的威胁。
5、随着数据不断更新，以上2到4步会继续重复。

业界应用情况

瀚斯科技

应用场景：企业内部

核心思想：1.企业内部的管理相对规范，员工行为轨迹有迹可循

​ 2.不应该过分强调算法，为各个应用场景量身定做更重要

​ 3.规则、黑白名单、机器学习协同工作

部署方式：与 SIEM/态势感知平台进行结合，将其采集到的行为类数据，应用系统日志、人员/权限数据导入 UEBA 分析引擎中进行实时处理。

实例

内部员工窃取敏感数据

​ 通过 DLP 日志和流量分析导致账号异常的具体行为，发现内部高权限账号10月22号拷贝自己简历，10月23号凌晨1点大量拷贝这个工作目录下的合作项目材料，涉及财务报表、项目管理月报、资产负载表等累计 540 份。

异常特征包括：

​ 1.高权限用户是否存在拷贝简历行为(可能存在拷贝简历出卖信息跳槽风险)

​ 2.对高权限用户日常访问工作目录进行记录，日常访问、拷贝、删除财务报表、项目管理月报、资产负载表等文件的个数建立日常行为基线(根据全部同一个群组的用户的最高次数)

启明星辰

应用场景：

核心思想：1.UEBA并不是安全分析的全部，仅仅是交互式安全分析的一个环节

​ 2.行为分析要与规则分析紧密结合，行为分析要充分利用情境(Context)数据，包括情报、地理位置信息、漏洞、身份信息和业务属性等。

两种异常行为分析的方式

1.建立异常行为模型

​ 针对特定种类的攻击行为，根据人工经验构建一攻击行为指标，基于行为指标简历机器学习模型，从而识别异常行为。

​ 缺陷：需要对攻击有充分的理解

2.建立正常行为模型

​ 针对波保护对象进行实体行为进行”画像”，建立一套对实体行为刻画的指标，基于这些指标简历及机器学习模型，通过数据与正常的模式的偏离程度来识别异常。

思科

​ 有安全分析报告，没法下载，论文不翻墙没找到，下周我先看看能不能找个可用的vps翻个墙出去找找

机器学习在UEBA中的应用

1.非监督学习

​ 非监督学习主要应用在异常检测阶段通过聚类发现异常和划分群组。例如将数据使用Kmeans进行聚类，然后根据所属类别元素的大小确定群组风险大小，通过DBSCAN发现异常点等。

2.监督学习

​ 监督学习主要用于将各个子模型检测的异常进行汇总，然后采用监督学将各个异常结果进行综合，确定是否粗发报警。

这里各家都没有特别具体的用法，都比较含蓄，下周翻墙去看看论文上有没有这方面的研究

总结

1.UEBA中异常主要是通过统计分析、其他安全产品结果、非监督学习等方式来触发异常，而报警可以通过有监督学习和人工设定阈值的方式。

2.异常常常由各种统计模型、基线模型产生，而由产生的异常则作为特征交给机器学习模型来进行监督学习，从而确定哪些将产生告警。

3.应用场景常常是在使用UEBA系统产生异常和告警，对告警内容进行可视化展示，安全人员查看先关内容确定是否进行响应。

​