##[[TOC]]大数据挖掘与分析-面试准备材料

一、基本算法

1.1 k-means聚类（划分式聚类算法）

1.1.1 核心

核心：预先指定聚类数据或聚类中心，反复迭代逐步降低目标函数误差值直至收敛，得到最终结果。

1.1.2 算法流程

经典k-means聚类的算法流程：

1. 随机地选择k个样本值，每个样本对象初始地代表了一个簇的中心。
2. 对剩余的每个样本值，根据其与各簇中心的距离，将它赋给最近的簇。
3. 重新计算每个簇的平均值，更新为新的簇中心。
4. 不断重复2、3，直到准则函数收敛。

1.1.3 复杂度分析

时间复杂度：O(迭代次数x簇数x样本点数x维数)
空间负责度：O(样本点维数x(样本点数+簇数))

1.1.3 k-means的缺点：

• K各样本值受人为干扰大。
• 对初始的簇中心敏感。
• 异常值与野值影响大。
• 不太适合太分散的类。

1.1.4 聚类的评价指标

（1）聚类纯度（Purity） 总体思想：用聚类正确的样本数除以总体样本数，被称为聚类的准确率。

（2）兰德系数与F值——查准率、查全率

查准率：$Precision=\frac{TP}{TP+FP}Precision=\backslash frac\{TP\}\{TP+FP\}$Precision=TP+FPTP​

查全率：$Recall=\frac{TP}{TP+FN}Recall=\backslash frac\{TP\}\{TP+FN\}$Recall=TP+FNTP​

F值：$F_{\beta }=(1+{\beta }^2)\frac{Precision\cdot Recall}{{\beta }^2\cdot Precision+Recall}F\_\backslash beta=(1+\backslash beta^2)\backslash frac\{Precision·Recall\}\{\backslash beta^2·Precision+Recall\}$Fβ​=(1+β2)β2⋅Precision+RecallPrecision⋅Recall​

二、SQL部分

2.1 SQL的查询顺序及性能优化

1. SQL的查询顺序：

(7)     SELECT 
(8)     DISTINCT <select_list>
(1)     FROM <left_table>
(3)     <join_type> JOIN <right_table>
(2)     ON <join_condition>
(4)     WHERE <where_condition>
(5)     GROUP BY <group_by_list>
(6)     HAVING <having_condition>
(9)     ORDER BY <order_by_condition>
(10)    LIMIT <limit_number>

• FROM：对FROM子句中的前两个表执行笛卡尔积（Cartesian product)(交叉联接），生成虚拟表VT1
• ON：对VT1应用ON筛选器。只有那些使<join_condition>为真的行才被插入VT2。
• OUTER(JOIN)：如果指定了OUTER JOIN（相对于CROSS JOIN 或(INNER JOIN),保留表（preserved --- - table：左外部联接把左表标记为保留表，右外部联接把右表标记为保留表，完全外部联接把两个表都标记为保留表）中未找到匹配的行将作为外部行添加到 VT2,生成VT3.如果FROM子句包含两个以上的表，则对上一个联接生成的结果表和下一个表重复执行步骤1到步骤3，直到处理完所有的表为止。
• WHERE：对VT3应用WHERE筛选器。只有使<where_condition>为true的行才被插入VT4.
• GROUP BY：按GROUP BY子句中的列列表对VT4中的行分组，生成VT5.
• CUBE|ROLLUP：把超组(Suppergroups)插入VT5,生成VT6.
• HAVING：对VT6应用HAVING筛选器。只有使<having_condition>为true的组才会被插入VT7.
• SELECT：处理SELECT列表，产生VT8.
• DISTINCT：将重复的行从VT8中移除，产生VT9.
• ORDER BY：将VT9中的行按ORDER BY 子句中的列列表排序，生成游标（VC10).
• TOP：从VC10的开始处选择指定数量或比例的行，生成表VT11,并返回调用者。

2.2 SQL的优化

• 用什么查什么：避免全表扫描，首先考虑WHERE及ORDER BY涉及的列建立索引。
• 什么类型查什么：不要做时间转换，内容转换，尽量保证SQL的原子性。
• 能BETWEEN不IN、NOT IN：以防触发全表扫描。
• WHERE中，不用OR、!=、NOT NULL：理由同上。

2.3 SQL中的窗口函数

（1）row_number() over(patition by fieldname order b fieldname desc/asc)：为查询出来的每一行添加一个序号，可以理解为行号，即序号不同，按照patition排名，不存在重复

• partition by是用来限定排序的范围，若不写，则全表排序。
• over是依据某一列排序，如果存在order by，则按照其排序。
• 示例如下：

（2）rank() over(partition by filename order by fieldname desc/asc)：rank函数常用来返回结果集中的分区内每一行的排名，这里的排序可能出现重复，即排序的结果相同时，序号不变（并列名次），由于存在重复排名，因此会出现“跳跃排名”。

（3）dense_rank() over(partition by fieldname order by fieldname desc/asc)：和rank()的不同是——序号不变（并列名次），虽然存在重复排名，但不会“跳跃排名”。

（4）ntile() over()：可以对序号进行分组处理，之后按照规则将序号划分到不同的切片里，并且返回切片号，一般排在前面的切片个数相同，最后一组切片会动态调整。

三、问题探究

3.1 数据不平衡的处理方法

如果正样本有100条，负样本有1W条，如何解决样本不均衡的问题。

3.1.1 欠采样

（1）简单欠采样 正样本的100条全部用上，负样本的随机采样为1000条或者更少，控制比例进行挖掘。出现的问题是：样本丢失，模型损失。

（2）迭代欠采样

• 把所有的正样本和从负样本中选取的100条负样本去训练第一轮分类器；
• 用第一轮分类器去预测剩下的9900条数据，把9900条负样本中预测为正样本（预测错误）的条数中随机采样100条和第一轮训练的数据放到一起训练第二轮分类器；
• 同样的方法，第二轮分类器去预测剩下的9800条数据，知道训练的第N轮分类器可以识别全部负样本候选集。

（3）过采样 过采样不会损失样本。正样本100条，负样本1W条，将正样本有放回的采样，知道获取1W条正样本，然后再进行分析

3.2 过拟合问题及解决方案

3.2.1 过拟合定义

过拟合（overfitting）是指在模型参数拟合过程中的问题，由于训练数据包含抽样误差，训练时，复杂的模型将抽样误差也考虑在内，将抽样误差也进行了很好的拟合。 具体表现就是最终模型在训练集上效果好；在测试集上效果差。模型泛化能力弱。

3.2.2 过拟合解决方案

（1）扩增数据|且清洗数据：

• 扩增数据，让模型看到尽可能多的情况，对自身进行修正。
• 对误差值、野值等干扰因素进行清洗剔除。

（2）Early stopping

• 当模型的Accuaray稳定或者不在提升时，提前结束训练。

（3）正则化 $C=C_0+\frac{\lambda }{2n}.{\sum }_i{w}_i^{2}C\; =\; C\_0\; +\; \backslash frac\{\backslash lambda\}\{2n\}\; .\; \backslash sum\_i\; w\_i^2$C=C0​+2nλ​.∑i​wi2​

L2范数是指向量各元素的平方和然后求平方根。可以使得W的每个元素都很小，都接近于0，但不会让它等于0，而是接近于0。 L2正则项起到使得参数W变小加剧的效果，关于它为什么能防止过拟合简答的理解为：更小的参数值W意味着模型的复杂度更低，对训练数据的拟合刚刚好，不会过分拟合训练数据，从而使得不会过拟合，以提高模型的泛化能力

3.3 KS检验

3.3.1 介绍

Kolmogorov-Smirnov检验是基于累计分布函数的，用于检验一个分布是否符合某种理论分布或比较两个经验分布是否有显著差异。

• 单样本K-S检验是用来检验一个数据的观测经验分布是否符合已知的理论分布。

• 两样本K-S检验由于对两样本的经验分布函数的位置和形状参数的差异都敏感，所以成为比较两样本的最有用且最常用的非参数方法之一。

3.3. KS检验步骤

（1）提出假设：

• $H_0:F_n\left(x\right)=F\left(x\right)H\_0:\; F\_n(x)\; =\; F(x)$H0​:Fn​(x)=F(x)
• $H_1:F_i\left(x\right)\ne F\left(x\right)H\_1:\; F\_i(x)\; \backslash neq\; F(x)$H1​:Fi​(x)​=F(x)

（2）由样本数据计算经验分布函数与理论分布函数，带入KS计算，得到$D_{n}D\_n$Dn​

（3）查表确定临界值$D_n\left(\alpha \right)D\_n(\backslash alpha)$Dn​(α)

（4）做出判断：若样本计算得$D_n>D_n\left(\alpha \right)D\_n\; >\; D\_n(\backslash alpha)$Dn​>Dn​(α)，则拒绝$H_{0}H\_0$H0​假设，否则就接受$H_{0}H\_0$H0​假设。

3.4 进程与线程

3.4.1 进程与线程的关系

（1）从CPU资源使用角度来说：

• 进程是资源CPU资源分配的最小单位。
• 线程是CPU调度的最小单位。

（2）从CPU的处理过程来说：进程和线程都是一个是极端的描述，是CPU工作时间段的描述，不同的是他们的颗粒度大小不同，进程是CPU上执行的一次活动，有PID，线程是CPU上执行进程活动的某一片。

3.4.2 线程——死锁

3.4.2.1 死锁的定义：

由于两个或两个以上的线程互相持有对方需要的资源，导致这些线程处于等待状态，无法执行。

3.4.2.2 产生死锁的四个必要条件：

• 请求和保持条件：一个线程对请求被占有资源发生阻塞时，对已获得的资源不释放。
• 不剥夺：一个线程在释放资源前，其他的线程无法剥夺使用。
• 循环等待：发生线程死锁时，线程进入死循环，永久阻塞。
• 互斥性：线程对资源的占有具有排他性，一个资源只能被一个线程占有，直到释放。

3.4.2.3 产生死锁的原因

（1）竞争不可抢占资源：p1已经打开F1，想去打开F2，p2已经打开F2，想去打开F1，但是F1和F2都是不可抢占的，这是发生死锁。

（2）竞争可消耗资源：进程间通信，如果顺序不当，会产生死锁，比如p1发消息m1给p2，p1接收p3的消息m3，p2接收p1的m1，发m2给p3，p3，以此类推，如果进程之间是先发信息的那么可以完成通信，但是如果是先接收信息就会产生死锁。

（3）进程推进顺序不当：进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。

3.4.2.4 避免死锁的方法：

（1）破坏“请求和保持”条件：

• 线程申请资源前，要释放自己拥有的资源。
• 线程申请资源时，当被申请的资源被占用，就让线程等待。

（2）破坏“不可抢占”条件： 即允许进程进行抢占：

• 如果去抢占资源，被拒绝，就释放自己的资源。
• 提升线程的优先级，对资源进行抢占。

（3）破坏“循环等待”条件： 将系统资源统一编号，进程可在任何时候提出资源申请，但所有申请必须安好资源的编号顺序进行。

3.4.2.5 死锁的解除：

（1）抢占资源，从一个或多个进程中抢占足够数量的资源，分配给死锁进程，以接触死锁状态。

（2）终止死锁进程，打破循环回路。

3.4.3 线程——加锁

import threading
import time

class Account:
    # 定义构造器
    def __init__(self, account_no, balance):
        # 封装账号和金额
        self.account_no = account_no
        self._balance = balance
        self.lock = threading.RLock()
    
    # 因为账户余额不能随意修改，所以值提供getBalance方法：
    def getBalance(self):
        return self._balance
    
    # 通过线程所来取钱
    def draw(self, draw_amount):
        self.lock.acquire()
        try:
            # 判断账户余额和取钱数目的大小
            if self._balance >= draw_amount:
                print(threading.current_thread().name + '取得钞票：' + str(draw_amount))
                time.sleep(0.001)
                # 修改余额
                self._balance -= draw_amount
                print('\t余额为：'+str(self._balance))
            else:
                print(threading.current_thread().name + '取钱失败！余额不足！')
        finally:
            # 取钱完成，释放锁
            self.lock.release()

# 定义一个函数来模拟取钱操作
def draw(account, draw_amount):
    # 直接调用account对象的draw()方法来执行取钱操作
    account.draw(draw_amount)
# 创建一个账户
acct = Account("1234567" , 1000)
# 模拟两个线程对同一个账户取钱
threading.Thread(name='甲', target=acct.draw , args=(800,)).start()
threading.Thread(name='乙', target=acct.draw , args=(800,)).start()

上面程序中的定义了一个 RLock 对象。在程序中实现 draw() 方法时，进入该方法开始执行后立即请求对 RLock 对象加锁，当执行完 draw() 方法的取钱逻辑之后，程序使用 finally 块来确保释放锁。

程序中 RLock 对象作为同步锁，线程每次开始执行 draw() 方法修改 self.balance 时，都必须先对 RLock 对象加锁。当该线程完成对 self._balance 的修改，将要退出 draw() 方法时，则释放对 RLock 对象的锁定。这样的做法完全符合“加锁→修改→释放锁”的安全访问逻辑。

当一个线程在 draw() 方法中对 RLock 对象加锁之后，其他线程由于无法获取对 RLock 对象的锁定，因此它们同时执行 draw() 方法对 self._balance 进行修改。这意味着，并发线程在任意时刻只有一个线程可以进入修改共享资源的代码区（也被称为临界区），所以在同一时刻最多只有一个线程处于临界区内，从而保证了线程安全。

为了保证 Lock 对象能真正“锁定”它所管理的 Account 对象，程序会被编写成每个 Account 对象有一个对应的 Lock（就像一个房间有一个锁一样）。

上面的 Account 类增加了一个代表取钱的 draw() 方法，并使用 Lock 对象保证该 draw() 方法的线程安全，而且取消了 setBalance() 方法（避免程序直接修改 self._balance 成员变量），因此线程执行体只需调用 Account 对象的 draw() 方法即可执行取钱操作。