某酒店预定系统的数据库中包含以下数据表，具体信息如下：

• customer表：包含顾客id和顾客名字

  

• hotel表：包含酒店id和酒店名

  

• room_type表：包含房型id，房型名，对应的酒店id

  

• room_info表：房间信息id，日期，当前日期价格，剩余数量，对应房型id

  

• hotel_order表：订单id，订单对应的房型id，入店日期，离店日期，预定数量，订单价格，订单创建日期，发起订单的顾客id

  

• rating表：评价id，评价分数，评价对应的订单id，发起评价的顾 客id

  

P1

查询所有房型的具体信息，包括room_id, Room_name, hotel_id；

1
2

SELECT *
FROM room_type;

P2

查询所有酒店名称中包含“希尔顿”的酒店，返回酒店名称和酒店id。

1
2
3

SELECT *
FROM hotel
WHERE hotel_name LIKE '%希尔顿%';

P3

查询订单总价在9000元及以上的所有订单详情，包括订单编号、 酒店编号、房型编号及居住时长。

1
2
3
4
5
6
7
8

SELECT hotel_order.order_id,
    hotel.hotel_id,
    hotel_order.room_id,
    (hotel_order.leave_date - hotel_order.start_date) AS period
FROM hotel_order
LEFT OUTER JOIN room_type ON room_type.room_id = hotel_order.room_id
LEFT OUTER JOIN hotel ON hotel.hotel_id = room_type.hotel_id
WHERE hotel_order.payment >= 9000;

P4

查询所有房型的订单情况，包括房型编号，房型名称，订单编号、 价格

1
2
3
4
5
6

SELECT hotel_order.room_id,
    room_type.room_name,
    hotel_order.order_id,
    hotel_order.payment
FROM hotel_order
    LEFT OUTER JOIN room_type ON room_type.room_id = hotel_order.room_id;

P5

创建启悦酒店的订单视图。

1
2
3
4
5
6

CREATE OR REPLACE VIEW qiyue_hotel AS
SELECT hotel_order.*
FROM hotel_order
    LEFT OUTER JOIN room_type ON room_type.room_id = hotel_order.room_id
    LEFT OUTER JOIN hotel ON hotel.hotel_id = room_type.hotel_id
WHERE hotel.hotel_name = '启悦酒店';

P6

在订单表的总价字段上创建降序的普通索引。索引名为 orderpayment. 用\di 命令查看创建的索引。

1

CREATE INDEX order_payment ON hotel_order(payment DESC);

P7

创建函数：查询给定日期，给定酒店所有房型的平均价格。 执行函数，输入参数为2020-11-14，希尔顿大酒店

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

CREATE OR REPLACE FUNCTION get_average_price_on_date_hotel(DATE, VARCHAR(255))
RETURNS DECIMAL(10, 2)
AS $$
    DECLARE average_price DECIMAL(10, 2);

    BEGIN
        SELECT AVG(room_info.price) INTO average_price
        FROM room_info
            LEFT OUTER JOIN room_type ON room_type.room_id = room_info.room_id
            LEFT OUTER JOIN hotel ON hotel.hotel_id = room_type.hotel_id
        WHERE room_info.date = $1
            AND hotel.hotel_name = $2;
        RETURN average_price;
    END
$$ LANGUAGE plpgsql;

SELECT get_average_price_on_date_hotel('2020-11-14', '希尔顿大酒店') AS avg_price;

P8

创建存储过程：从订单表中统计指定酒店、指定日期的各种房型 的预订情况，返回酒店名，房型，预定数量。执行存储过程：统计希尔顿大酒店2020-11-14当天各个房型预定情况

1
2
3
4
5
6
7
8
9
10
11

CREATE OR REPLACE PROCEDURE
getOrderSitu(para1 date, para2 cvarchar(255)) as 
BEGIN

SELECT hotel.hotel_name, room_type.room_name,SUM(hotel_order.amount)
FROM hotel, room_type, hotel_order
WHERE hotel.hotel_id=room_type.hotel_id AND room_type_room_id=hotel_order_id AND hotel_order.start_date=para1 AND hotel.hotel_name=para2
GROUP BY hotel.hotel_name, room_type.room_name;
END;

call getOrderSitu(para1:'2020-11-14', para2:'希尔顿大酒店');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

CREATE OR REPLACE PROCEDURE get_room_type_order_on_date_hotel(para1 DATE, para2 VARCHAR(255))
AS
    CURSOR c IS
        SELECT FIRST(hotel.hotel_name) AS hotel_name,
            hotel_order.room_id,
            FIRST(room_type.room_name) AS room_name,
            SUM(hotel_order.amount) AS amount
        FROM hotel_order
            LEFT OUTER JOIN room_type ON room_type.room_id = hotel_order.room_id
            LEFT OUTER JOIN hotel ON hotel.hotel_id = room_type.hotel_id
        WHERE hotel_order.create_date = $1
            AND hotel.hotel_name = $2
        GROUP BY hotel_order.room_id;

    hotel_name VARCHAR(255);
    room_id INT;
    room_name VARCHAR(255);
    amount INT;

    BEGIN
        OPEN c;
        LOOP
            FETCH c INTO hotel_name, room_id, room_name, amount;
            EXIT WHEN c%notfound;
            RAISE INFO 'hotel_name: %', hotel_name;
            RAISE INFO 'room_id:    %', room_id;
            RAISE INFO 'room_name:  %', room_name;
            RAISE INFO 'amount:     %', amount;
            RAISE INFO '';
        END LOOP;
        CLOSE c;
    END
;

CALL get_room_type_order_on_date_hotel('2020-11-14', '希尔顿大酒店');

P9

查找同时评价了2次及以上的用户信息。

1
2
3
4
5
6
7
8

SELECT *
FROM customer
WHERE uid IN (
    SELECT uid
    FROM rating
    GROUP BY uid
    HAVING COUNT(*) >= 2
);

P10

查询评价过所有总统套房的顾客姓名。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

SELECT DISTINCT customer.uname
FROM customer
JOIN rating ON customer.uid=rating.uid
JOIN hotel_order ON rating.order_id=hotel_order.order_id
JOIN room_type ON hotel_order.room_id=room_type.room_id
WHERE room_type.room_name='总统套房';

Select customer.uname 
from customer
where customer.uid in(
   select uid 
   from  rating left outer join hotel_order on rating.order_id = hotel_order.order_id
   where hotel_order.room_id = 7 or hotel_order.room_id =12 or hotel_order.room_id =16
   group by rating.uid
   having count(distinct hotel_order.room_id) = 3
)
;

P11

若要预定11.14-16日每天房间数量4间。查询满足条件（时 间区间，将预定房间数）的房型及其平均价格，并按平均价格从 低到高进行排序。查询结果应包含酒店，房型及平均价格信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

SELECT FIRST(hotel.hotel_name) AS hotel_name,
FIRST(room_type.room_name) AS room_name,
AVG(room_info.price) AS average_price
FROM room_info
LEFT OUTER JOIN room_type ON room_type.room_id = room_info.room_id
LEFT OUTER JOIN hotel ON hotel.hotel_id = room_type.hotel_id
WHERE room_info.room_id IN (
    SELECT room_id
    FROM room_info
    WHERE room_id IN (
        SELECT room_id
        FROM room_info
        WHERE DATE = '2020-11-14'
            AND remain >= 4
    )
    INTERSECT
    (
        SELECT room_id
        FROM room_info
        WHERE DATE = '2020-11-15'
            AND remain >= 4
    )
    INTERSECT
    (
        SELECT room_id
        FROM room_info
        WHERE DATE = '2020-11-16'
            AND remain >= 4
    )
)
GROUP BY room_info.room_id;

P12

编写触发器：完成预订房间，包括创建订单和更新房型信息。

该订单为预订11月14号-15号4号房型4间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

CREATE OR REPLACE PROCEDURE order_room(t_start_date DATE, t_leave_date DATE, t_room_id INT, t_amount INT, t_customer_id INT)
AS
    BEGIN
        INSERT INTO hotel_order
        VALUES (
            (
                SELECT MAX(order_id) + 1
                FROM hotel_order
            ),
            t_room_id,
            t_start_date,
            t_leave_date,
            t_amount,
            (
                SELECT SUM(price) * t_amount
                FROM room_info
                WHERE room_id = t_room_id
                    AND date IN (
                        SELECT a
                        FROM generate_series(
                            t_start_date::DATE,
                            t_leave_date::DATE,
                            '1 day'
                        ) s(a)
                    )
            ),
            NOW(),
            t_customer_id
        );
    END
;

CREATE OR REPLACE FUNCTION check_remain()
RETURNS TRIGGER
AS $$
    DECLARE total_count INT;
    DECLARE available_count INT;

    BEGIN
        SELECT COUNT(*) INTO total_count
        FROM room_info
        WHERE room_id = new.room_id
            AND date IN (
                SELECT a
                FROM generate_series(
                    new.start_date::DATE,
                    new.leave_date::DATE,
                    '1 day'
                ) s(a)
            );
        SELECT COUNT(*) INTO available_count
        FROM room_info
        WHERE room_id = new.room_id
            AND date IN (
                SELECT a
                FROM generate_series(
                    new.start_date::DATE,
                    new.leave_date::DATE,
                    '1 day'
                ) s(a)
            )
            AND remain >= new.amount;

        IF available_count < total_count THEN
            RAISE EXCEPTION 'Not enough rooms';
        END IF;

        RETURN new;
    END
$$ LANGUAGE plpgsql;

DROP TRIGGER IF EXISTS check_remain_trigger ON hotel_order;
CREATE TRIGGER check_remain_trigger
BEFORE INSERT ON hotel_order
FOR EACH ROW
EXECUTE PROCEDURE check_remain();

-- 在创建订单后，要减少房间余量。
CREATE OR REPLACE FUNCTION update_remain()
RETURNS TRIGGER
AS $$
    DECLARE CURSOR c IS
        SELECT info_id, remain
        FROM room_info
        WHERE room_id = new.room_id
            AND date IN (
                SELECT a
                FROM generate_series(
                    new.start_date::DATE,
                    new.leave_date::DATE,
                    '1 day'
                ) s(a)
            );

    DECLARE t_info_id INT;
    DECLARE now_remain INT;

    BEGIN
        OPEN c;
        LOOP
            FETCH c INTO t_info_id, now_remain;
            EXIT WHEN c%notfound;

            UPDATE room_info
            SET remain = now_remain - new.amount
            WHERE info_id = t_info_id;
        END LOOP;
        CLOSE c;
        RETURN new;
    END
$$ LANGUAGE plpgsql;

DROP TRIGGER IF EXISTS update_remain_trigger ON hotel_order;
CREATE TRIGGER update_remain_trigger
AFTER INSERT ON hotel_order
FOR EACH ROW
EXECUTE PROCEDURE update_remain();

CALL order_room('2020-11-14', '2020-11-15', 4, 10, 2019018);

Mahalanobis Distance

Definition

条件：

• 对于两个服从同分布的样本点，它们的特征向量为${x,y}$
• 分布的均值向量为$\mu$
• 协方差矩阵为$\Sigma$可逆

Trait

• 尺度无关：不同特征的量纲和大小不会影响马氏距离的计算。
• 考虑特征的相关性：如果特征之间存在相关性，可以通过协方差矩阵来调整特征间的”权重”。
• 分布敏感：马氏距离适合于服从多元正态分布的数据

Description

• Mahalanobis Distance常用于异常检测、分类和聚类等领域。
• 由于它可以有效地衡量样本间的相似性，特别是在特征空间中，样本点不是均匀分布时，马氏距离相比于其他距离度量方法更加有效。
• 在使用马氏距离时需要注意协方差矩阵必须是非奇异的（也就是可逆的），否则不能计算逆矩阵。

第四章：数据仓库和联机分析处理

• 构建数据仓库： 数据清理，数据集成，数据变换
• 数据仓库提供OLAP工具

4.1 数据仓库：基本概念

4.1.1 什么是数据仓库

• 面向问题
• 集成的
• 时变的
• 非易失的
• 支持管理者的决策过程
• 更新驱动的：将多个异构数据库的信息预先集成，重新组织到语义一致的数据存储（不必像查询驱动方法，和局部数据源竞争资源）

4.1.2 操作数据库系统与数据仓库的区别

• 联机事务处理OLTP：联机事务，查询处理
• 联机分析处理OLAP:用不同格式组织数据
• 区别：
  • OLTP面向顾客，OLAP面向市场
  • OLTP数据琐碎难以用于决策，OLAP汇总集成数据，有利于决策
  • OLTP采用ER数据模型（实体-联系）和面向应用的数据库设计，OLAP通常采用星形或雪花模型和面向主题的数据库设计
  • OLTP主要关注企业当前数据，OLAP常常跨越数据库模式
  • 访问模式：OLTP主要由原子事务组成，OLAP大量只读操作

4.1.3 为什么需要分离的数据仓库

• 在操作数据库上进行OLAP查询，可能会使得操作任务性能降低
• OLAP查询对汇总数据记录进行只读访问，不适用操作数据库的多事务的并发处理
• 两种数据库路的结构内容和用法不相同

4.1.4 数据仓库：一种多层体系结构

• 底层： 仓库数据服务器
• 中间层：OLAP服务器
• 前端客户层

4.1.5 数据仓库模型：企业仓库、数据集市和虚拟仓库

• 企业仓库：搜集了关于主题的全部信息
• 数据集市：范围限定与选定主题
• 虚拟仓库：操作数据库上视图的集合

4.1.6 数据提取、变换和装入

• 利用后端工具加载和刷新数据
• 数据提取，清理，变换，装入，刷新

4.1.7 元数据库

• 数据仓库结构的描述
• 操作元数据
• 用于汇总的算法
• 由操作环境到数据仓库的映射
• 关于系统性能的数据
• 商务元数据

4.2 数据仓库建模：数据立方体与OLAP

4.2.1 什么是数据立方体：一种多为数据模型

• 维，维表
• 事实，事实表
• 基本方体，顶点方体：诸维每个可能子集形成方体的格
• 

4.2.2 星形，雪花形和事实星座：多为数据模型的模式

• 星形模式：
  
• 事实星座：
  

4.2.3 维：概念分层的应用

• 模式分层：形成数据库模式中的属性的全序和偏序的概念分层
• 集合分组分层：将给定位或属性的值离散化

4.2.4 度量的分类和计算

度量根据所用的聚集函数分为3类

• 分布式：聚集函数例如sum(),min(),max(),count()函数用于划分数据集的得到的聚集值的结果和函数用于不划分的数据集结果一致
• 代数的：聚集函数可以用让若干参数计算，这些参数可以用分布聚集函数求得，比如avg=sum()/count()
• 整体的：不存在有限个参数的代数函数可以计算出来，比如median(),mode(),rank()

4.2.5 典型的OLAP操作

• 上卷
• 下钻
• 切片
• 转轴

4.2.6 查询多为数据库的星网查询模型

4.3 数据仓库的设计与使用

4.3.1 数据仓库的设计的商务分析框架

• 自顶向下视图
• 数据源视图
• 数据仓库视图
• 商务查询视图

4.3.2 数据仓库的设计过程

• 自顶向下
• 自底向上
• 二者结合的混合设计

4.3.3 数据仓库用于信息处理

三类数据仓库应用：

• 数据处理
• 分析处理
• 数据挖掘

4.3.4 从联机分析处理到多维数据挖掘

多维数据挖掘OLAM：数据挖掘与OLAP技术的集成

4.4 数据仓库的实现

4.4.1 数据立方体的有效计算：概述

• compute cube操作和维灾难
  • $\text{方体总数}=\prod(\text{关联层数}_i+1)$
• 部分物化：方体的选择计算
  • 物化一个外壳立方体：与计算少量维，其他的组合查询临时计算

4.4.2 索引OLAP数据：位图索引和连接索引

• 位图索引：
  
• 连接索引
  

4.4.3 OLAP查询的有效处理

• 确定哪些操作可以在可利用的方体执行
• 确定相关操作应该使用哪些物化的方体

4.4.4 OLAP服务器结构

• 关系OLAP服务器ROLAP
• 多维OLAP服务器HOLAP
• 混合OLAP服务器
• 特殊的SQL服务器

4.5 数据泛化：面向属性的归纳

4.5.1 数据特征的面向属性的归纳

• 基本操作：数据泛化
  • 属性删除
  • 属性泛化
    • 属性泛化阈值控制
    • 广义关系阈值控制

4.5.2面向属性归纳的有效实现

• 关系查询
• 收集初始关系的统计量
• 导出主关系P

4.5.3 类比较的面向属性归纳

如何进行类比较？

• 数据收集
• 相关维分析
• 同步泛化
• 导出比较的表示

第二章：认识数据

2.1 数据对象与属性类型

• 数据对象 = 样本/实例/数据点/对象，用属性描述

2.1.1 什么是属性

• 属性attribute，维dimension，特征feature，变量variable

2.1.2 标称属性NominalAttribute

• 标称属性的值仅仅只是不同的名字
• 众数、熵、列联相关、$\chi^2$检验是有意义的

2.1.3 二元属性BinaryAttribute

• 只有两个状态0，1
  • 对称的
  • 非对称的：重要的值通常比较少出现，通常用1表示，例如化验结果中的阳性

2.1.4 序数属性OrdinalAttribute

• 序数属性的值提供足够的信息确定对象的序
• 中值、百分位、秩相关、游程检验、符号检验是有意义的

2.1.5 数值属性NumericAttribute

• 区间属性IntervalAttribute
  • 存在测量的单位
  • 均值、标准差、皮尔逊相关、$T$检验和$F$检验是有意义的
• 比率RatioAttribute
  • 关注差和比率
  • 几何平均、调和平均、百分比变差是有意义的

2.1.6 离散属性与连续属性

• 离散属性DiscreteAttribute
  • 有限或无限可数个值
  • 常表示为整数变量或字符串变量
    连续属性ContinuousAttribute
  • 属性值为实数
  • 实践中, 实数只能用有限位数字的数度量和表示.
  • 连续属性一般用浮点变量表示.

2.2 数据的基本统计描述

2.2.1 中心度量趋势

• 均值：$avg(x)=\frac{\sum_{i=1}^{N}x_i}{N}$
• 加权均值：$avg(x)=\frac{\sum_{i=1}^{N}\omega_ix_i}{\sum_{i=1}^{N}\omega_i}$
• 截尾均值：减少极端值的影响
• 中位数：线性插值估计
  • 找到中位数区间$S=[L_1,L_1+width]
  • S区间频数为$freq_{mid}$,低于S的所有区间频数和为$\Sigma$
  • 估计$Median = L_1+ width \cdot \frac{N/2-\Sigma}{freq_{mid}}$
• 众数：对于非单峰数据，有如下经验：$mean-mode\sim 3*(mean-median)$

2.2.2 度量数据的散布

• 极差：$max-min$
• 四位分数：将数据分布划分为4个相等部分，分界点为$Q_1,Q_2(\text{中位数}),Q_3$
• 四分位数极差：给出数据中间一半的覆盖范围，$IDQ=Q_3-Q_1$
• 方差： $\sigma^2 = \frac{1}{N}\sum_{i=1}^{N}(x_i-\bar{x})^2$
• 标准差:度量均值的发散，$\sigma= \sqrt{\frac{1}{N}\sum_{i=1}^{N}(x_i-\bar{x})^2}$
• 五数概括$summary(x)=[min,Q1,median,Q3,max]$
• 盒图
  • 

2.2.3 数据的基本统计描述的图形显示

• 分位数图
  • 观察单变量数据分布
  • 每个观测值和某个百分数配对
  • 
• 分位数-分位数图
  • 刻画一个分布到另一个分布是否有漂移
  • 
• 直方图
  • 刻画数据的整体分布情况
  • numpy.hist()
  • 
• 散点图
  • 数据的具体分布（<=3维）
  • 

2.3 数据可视化

2.3.1 基于像素的可视化技术

• 空间填充曲线

2.3.2 几何投影可视化技术

• 平行坐标技术

2.3.3 基于图符的可视化技术

• Chernoff脸
• 人物线条画

2.3.4 层次可视化技术

• “World-within-world”技术
• 树图

2.3.5 可视化复杂对象和关系

• 标签云tag-cloud

2.4 度量数据的相似性和相异性

相似性和相异性都被称作邻近性

2.4.1 数据矩阵和相异性矩阵

基于内存的聚类和最邻近算法基于两种数据结构：

• 数据矩阵dataMatrix
  • 对象-属性two_mode
• 相异性矩阵dissmilaratyMatrix
  • 对象-对象single_mode
  • 对称的,对角线是0
  • $sim(i,j)=1-d(i,j)$

2.4.2 标称属性的邻近性度量

相异性计算标准：

• 不匹配率计算：$d(i,j)=\frac{p-m}{p}$
• 将标称属性用非对称的二元属性编码

2.4.3 二元属性的邻近性度量

• 对称二元属性：
  • 每个状态同样重要，$d(i,j)=\frac{r+s}{q+r+s+t}$
• 非对称二元属性：
  • 正匹配比负匹配更重要
    $d(i,j)=\frac{r+s}{q+r+s}$
• 

2.4.4 数值属性相异度：闵可夫斯基距离

对数据对象$i=(x_{i1},x_{i2},…,x_{ip}),j=(x_{j1},x_{j2},…,x_{jp})$,各维权重为$w=(w_1,w_2,…,w_p)$,Minkowski距离：$d(i,j)=\sqrt{q}{\sum_{k=1}^{p}{w_i(x_{ik}-x_{jk})^q}}$
注意，各维等价时，p=1称为Manhattan距离，p=2称为Euclidean距离

2.4.5 序数属性的相异性度量

变量$f$具有$M_f$个状态，变量的值映射为秩，即某个对象变量$f_i$，值为$x_{if}$，秩为$r_i$，相异度计算用区间标度变量处理：$z_i=\frac{r_{if}-1}{M_f-1}$，即用linspace(0,1,Mf)代表每个点

2.4.6 混合属性的相异度

数据集包括p个混合属性，指示符$\delta_{ij}^{f}=0$当且仅当$x_i,x_j$缺失或者在非对称二元属性中形成负匹配
根据属性的贡献计算

• $d(i,j)=\frac{\sum_{i=1}^{p}\delta_{ij}^{p}d_{ij}}{\sum_{i=1}^{p}\delta_{ij}^{p}}$

• f是数值的：$d_{ij}^{f}=\frac{|x_{if}-x_{jf}|}{max_hx_{hf}-min_hx_{hf}}$,h取遍f非缺失对象

• f是标称的或二元的：$d_{ij}=1\ if\ x_{if}=x_{jf}$

• f是序数的：$z_i=\frac{r_{if}-1}{M_f-1}$

2.4.7 余弦相似性

对于待比较的向量$x,y$，使用余弦度量$sim(x,y)=\frac{x\cdot y}{||x||\ ||y||}$

第三章：数据预处理

3.1 数据预处理：概述

3.1.1 为什么要进行数据的预处理

• 现实世界的数据是“肮脏的”
  • 不完整的：有些感兴趣的属性缺少属性值，或仅包含聚集数据
  • 含噪声的：包含错误或者“孤立点”
  • 不一致的：在编码或者命名上存在差异
• 没有高质量的数据，就没有高质量的挖掘结果
• 数据质量
  • 准确性
  • 完整性
  • 一致性
  • 时效性：及时更新
  • 可信性：数据是否被用户信赖
  • 可解释性：数据是否容易理解

3.1.2 数据预处理的主要任务

• 数据清理
  • 空缺值，噪声数据，删除孤立点，解决不一致性
  • 如果用户认为数据是脏的，那么可信性会降低
• 数据集成
  • 集成多个数据库、数据立方体或文件
• 数据归约
  • 得到数据集的压缩表示，但可以得到相同或相近的结果
  • 维归约：小波变换，主成分分析，属性子集选择，属性构造
  • 数值规约：参数模型，非参数模型
• 数据变换
  • 规范化和聚集
• 数据离散化
  • 将连续数据进行离散处理

3.2 数据清理

3.2.1 空缺值

• 忽略元组
  • 当类标号缺少时通常这么做（假定挖掘任务设计分类或描述），当每个属性缺少值的百分比变化很大时，它的效果非常差。
• 人工填写空缺值
  • 工作量大，可行性低
• 使用一个全局变量填充空缺值：比如使用$unknown$或$-∞$替换
  • 尽管简单，但程序可能会认为这些空缺形成了一个有趣的概念：unknown
  • 也可能会使数据有偏
• 使用属性的平均值填充空缺值
  • 可能有偏
• 使用与给定元组属同一类的所有样本的平均值
  • 可能有偏
• 使用最可能的值填充空缺值
  • 使用像Bayesian公式或判定树这样预测的方法，可能有偏
• 相当场合下，数据有空缺不意味着错误

3.2.2 噪声

• 噪声：一个测量变量中的随机错误或偏差
• 处理噪声数据
  • 分箱binning:
    • 首先排序数据，并将他们分到等深的箱中然后可以按箱的平均值平滑、按箱中值平滑、按箱的边界平滑等等
  • 回归regression：
    • 用回归函数预测
  • 离群点分析outlierAnalysis：
    • 利用聚类检测离群点

3.2.3 数据清理作为一个过程

• 偏差检测
  • 找到偏差原因：人工输入错误，糟糕的输入表单，用户有意输错，数据过时，系统错误比如编码
  • 找到元数据
  • 字段过载
  • 唯一性规则
  • 连续性规则
  • 空值规则

3.3 数据集成

困难：数据语义的多样性和结构

3.3.1 实体识别问题

• 匹配来自不同数据源的现实世界的实体
• 检测并解决数据值的冲突
  • 对现实世界中的同一实体，来自不同数据源的属性值可能是不同的
  • 可能的原因：不同的数据表示，不同的度量等等

3.3.2 冗余和相关分析

• 标称数据的$\chi^2$相关检验
  • 相依表：
  • 期望频度：$e_{ij}=\frac{N(A=a_i)N(B=b_j)}{n}$
  • 观测频度：相依表中的实际计数$\sigma_{ij}$
  • $Pearson \chi^2$统计量：$\chi^2 = \sum_{i}\sum_{j}\frac{(\sigma_{ij}^2-e_{ij})}{e_{ij}}$
• 数值数据的相关系数
  • $Pearson$积矩系数：$r_{A,B}=\frac{\sum_{i}(a_i-\bar{A})(b_i-\bar{B})}{n\sigma_A\sigma_B}$
  • $R_{A,B}=0$意味着两类属性独立
  • $R_{A,B}$越接近1，意味着某一个越可能是冗余项,越接近-1，意味着存在相互阻碍的效应
  • 相关性不蕴含因果关系
• 数据数值的协方差
  • 协方差：$Cov(A,B)=\frac{\sum_{i}(a_i-\bar{A})(b_i-\bar{B})}{n}$
  • $r_{A,B}=\frac{Cov(A,B)}{\sigma_A\sigma_B}$
  • $Cov(A,B)=E(AB)-E(A)E(B)$
  • 描述两个属性如何一起变化
  • 协方差0不蕴含独立性

3.3.3 元组重复

• 元组级检测重复
• 去规范化表的使用

3.3.4 数据值冲突的检测和处理

• 同一实体的不同数据源的属性值不同

3.4 数据规约

3.4.1 数据规约策略概述

• 用来得到数据集的归约表示，它小得多，但可以产生相同的（或几乎相同的）分析结果
  • 维归约： 减少考虑的属性个数
  • 数量规约：用较小的数据表示形式替代原数据，分为 参数的和非参数的
  • 数据压缩：使用某种变换

3.4.2 小波变换

• 离散小波变换DWT
  • 变换后的数据可以仅存放一小部分最强的小波系数
  • 对于相同的近似，DWT比DFT需要的空间少，局部性更好
  • 适合高维数据
• 属于维规约，保存小波较大的系数进行原始数据的压缩，主要用于图像分析中。
• 属于有损压缩

3.4.3 主成分分析

• PCA方法&K-L方法
  • 搜索k个最能代表数据的n维正交向量
  • 适合处理稀疏的和倾斜的数据
  • 可以作为多元回归和聚类分析的输入
• 找到一个投影，其能表示数据的最大变化
• 属于维规约

3.4.4 属性子集选择

• 特征筛选
• 检索所有可选的子集不现实，一般采用启发式算法或贪心算法，往往可以逼近最优解
  • 逐步向前选择/逐步向后删除
  • 决策树算法
  • 信息增益算法
    • 信息熵：$H(X)=-\sum_{x \in X}{p(x)logp(x)}$
    • 条件信息熵：$H(Y|X)=\sum_{x\in X}p(x)H(Y|X=x)=-\sum_{x\in X}p(x)\sum_{y \in Y}p(y|X=x)logp(y|X=x)$
    • 信息增益：描述已知X基础上节约多少信息刻画Y，$IG(Y|X)=H(Y)-H(Y|X)$
    • 选择对分类Y信息增益大的X属性X

3.4.5 回归和对数线性模型：参数化数据规约

• 回归：将数据拟合成直线
• 对数线性模型：近似离散的多维概率分布

3.4.6 直方图

• 将数据划分成不相交的桶
• 规则：
  • 等宽
  • 等深
  • V-最优
  • MaxDiff

3.4.7 聚类

• 将数据元组看成对象，将他们划分成簇，每一簇的对象互相相似
• 簇的直径越大，质量越好

3.4.8 抽样

• 无放回简单随机抽样SRSWOR
• 有放回简单随机抽样SRSWR
• 簇抽样
• 分层抽样

3.4.9 数据立方体聚集

• 联机数据分析和数据挖掘

3.5 数据变换和数据离散化

3.5.1 数据变换策略概述

• 光滑smoothing：去掉数据中的噪声，包括分箱，聚类和回归
• 属性构造：由给定属性生成新的属性
• 聚集：汇总
• 规范化：将数据落入一个小的区间
• 离散化：用原始数据用概念标签替换
• 概念分层：将属性根据标签泛化到更高的概念层

3.5.2 通过规范化变换数据

• 避免对度量单位选择的依赖
• 最大-最小化规范
  • $Normal(v)=min(A)+\frac{x-min(X)}{max(X)-min(X)}(max(A)-min(A))$
  • 将数据集X映射到区间A
• 零均值规范化
  • $Normal(v)=\frac{x-\bar X}{\sigma_X}$
  • 实际最大值最小值未知，或者离群点影响对最大最小规范化影响太大时，该方效果较好

3.5.3 通过分箱离散化

• 不使用类信息，非监督的离散化技术
• 易受离群点影响

3.5.4 通过直方图离散化

• 非监督的离散化技术
• 可以将直方图算法递归地使用

3.5.5 通过聚类 ，决策树和相关分析离散化

• 聚类
  • 自顶向下划分
  • 自底向上合并
• 决策树
  • 是监督的
• 相关性度量
  • ChiMerge方法：自底向上的策略

3.5.6 标称数据的概念分层

• 概念分层：找到属性的偏序关系
  • 模式级地说明属性的部分序
  • 显式数据分层说明分层结构的一部分
  • 说明属性集但不说明它们的偏序

聚类

Background

如果我们相信聚集在一起，有较高相似性的簇一定有有趣的知识的话，那么聚类分析就是获得数据内部结构，发现簇的意义的方法。

在讨论聚类算法时，都是在无监督学习的框架下进行的，也就是已知的数据集是没有标签可以学习的。

Content

聚类的概念

聚类：将数据分为多个簇(Clusters)，使得在同一个簇内对象之间具有较高的相似度，而不同簇之间的对象差别较大。

聚类的任务

已知无标记样本集$D={\boldsymbol{x}{1},\boldsymbol{x}{2},\ldots,\boldsymbol{x}{m}}$,聚类的算法的任务就是划分样本集成$k$个互不相交的簇，集 $D$ 划分为 $k$​ 个不相交的簇：
$$
D=\bigcup{l=1}^kC_l，C_{l^{\prime}}\bigcap C_l=\varnothing ({l^{\prime}\neq l})
$$
对样本$\boldsymbol{x}{j}$,应有唯一的下标$\lambda_j\in{1,2,\ldots,k}$,使得$x_j\in C{\lambda_j}$；

聚类的结果可用包含 $m$ 个元素的簇标记向量$\lambda=(\lambda_1;\lambda_2;\ldots;\lambda_m)$​ 表示；

聚类的功能

聚类分析是获得数据内部结构的有效方法。通过观察聚类得到的每个簇的特点，可以集中对特定的某些簇作进一步分析。

聚类分析可以作为其它算法的预处理步骤；

聚类分析可以完成噪声点/孤立点的挖掘；

聚类的有效性指标

对于聚类任务，我们希望物以类聚，直观上有两个指标：

• 「簇内相似度（intra-cluster similarity）」高
• 「簇间相似度(inter-cluster similarity)」低

外部指标

对数据集 $D={\boldsymbol{x}_1,\boldsymbol{x}_2,\ldots,\boldsymbol{x}_m}$,聚类簇划分 $\mathcal{C}={C_1$, $C_2,\ldots,C_k}$, 参考模型簇划分为$C^={C_1^,C_2^,\ldots,C_s^}$令$\lambda$ 与$\lambda^$ 分别表示与$C$ 和$C^$​ 对应的簇标记向量.

对样本配对，一定是下面四种情况之一：
$$
\begin{gathered}
a= |SS|, SS={(\boldsymbol{x}{i},\boldsymbol{x}{j})\mid\lambda_{i}=\lambda_{j},\lambda_{i}^{}=\lambda_{j}^{},i<j)}\
b= |SD|, SD={(\boldsymbol{x}{i},\boldsymbol{x}{j})\mid\lambda_{i}=\lambda_{j},\lambda_{i}^{}\neq\lambda_{j}^{},i<j)} \
c= |DS|, DS={(\boldsymbol{x}{i},\boldsymbol{x}{j})\mid\lambda_{i}\neq\lambda_{j},\lambda_{i}^{}=\lambda_{j}^{},i<j)} \
d= |DD|, DD={(\boldsymbol{x}{i},\boldsymbol{x}{j})\mid\lambda_{i}\neq\lambda_{j},\lambda_{i}^{}\neq\lambda_{j}^{},i<j)}
\end{gathered}
$$
显然，$a+b+c+d=\binom{m}{2}$

• Jaccard 系数(Jaccard Coefficient, JC)
  $$
  JC=\frac a {a+b+c}
  $$

• FMI 指数(Fowlkes and Mallows Index, FMI)
  $$
  \mathrm{FMI}=\sqrt{\frac{a}{a+b}\cdot\frac{a}{a+c}} .
  $$

• Rand指数(Rand Index, RI)
  $$
  RI= \frac{a+d}{a+b+c+d}
  $$

聚类算法的距离度量

四种方式：最小距离，最大距离，中心距离，平均距离
$$
\begin{aligned}
&dist_{min}(C_i,C_j) =\min_{p\in C_i,p^{\prime}\in C_j}{|p-p^{\prime}|} \
&dist_{max}(C_i,C_j) =\max_{p\in C_i,p^{\prime}\in C_j}{|p-p^{\prime}|} \
&dist_{mean}(C_i,C_j)=|m_i-m_j| \
& dist_{a\nu g}(C_i,C_j)=\frac1{n_in_j}\sum_{p\in C_i,p^{\prime}\in C_j}|p-p^{\prime}|
\end{aligned}
$$

聚类算法的分类

• 基于划分的办法：K-Means, K-Medoids
• 基于层次的办法：AGENS, DIANA
• 基于密度的办法：DBSCAN
• 基于网络的办法：STING