枯燥乏味之离散数学集合

1. 集合

  话不多说，先甩一张图。

---

1.1 集合定义

  由上图可知，集合通常有三种表示方法。

• 列举法：无疑是最没有技术含量的，一股脑把集合中的元素全部写出来。如：$\mathrm{A}$ = {0, 1, 2, 3, 4, 5} 是阿拉伯数字的集合；$\mathrm{N}$ = {0, 1, 2,…} 是自然数的集合；
• 描述法：有些地方叫谓词法。如：$\mathrm{A}$ = { $x$ ∈ $\mathrm{N}$ | $x$ mod 2 = 1};
• 韦恩图：通常用一个圆来代表一个集合;

  问题来了：集合 $\mathrm{A}$ = {0, 1, {0, 1} , {1, 2}} 有几个元素? 机器学习中, 这类形式的集合有什么优点和缺点?

1. 用 $card$ 表示有限集 $\mathrm{A}$ 中的元素个数，$card$($\mathrm{A}$) = 3。
2. 在机器学习中，我们通常会用自然数表示分类任务中的标签。例如，0 通常表示第一类，1 表示第二类，依次类推。集合 $\mathrm{A}$ 通常会被用在多标签分类任务中。一个实例可能有一个或多个标签，类似于选择题中的不定项选择题。对于集合 $\mathrm{A}$，我们可以认为它的标签数目不是固定的，有的一个标签，有的有两个标签，但是标签的总数是固定的，有 3 类。我们在标签编码时，可以使用标签补齐的方法，将缺失的标签全部用 0 标记，这样就不能使用 one-hot 编码了。例如，标签总数为 10，编号 0-9，一张图片中包含 0，3，9 号标签，那么这张图片的标签编码为：1 0 0 1 0 0 0 0 0 1。而且在多标签分类任务中，最后一层的输出就不能看成一个分布了，因为加起来不为 1，可以把输出层每个神经元看作一个二项分布，这相当于将一个多标签问题转化为在每个标签上的二分类问题。

---

1.2 基数

1.2.1 无穷集合比较大小

  说到基数，先提一下无穷集合比较大小。

  首先提出一个问题 “自然数的个数和正偶数的个数哪个多呢？” 有人说，当然是自然数的个数多，因为自然数包括正偶数；也有人说这两类数的个数都是无穷大，所以应该是一样多。

  这里面引出来一个很本质的问题，到底比较两个集合元素个数多少的标准是什么？虽然我们还是孩子的时候，就知道自己分了一个苹果而其他小朋友分到了两个苹果是不公平的，但是直到19世纪末，才由伟大的集合论开创者康托尔提出集合元素个数之间严格比较大小的标准。

  我们平时一般靠数数来记录一个集合元素的个数，再比较这两个数字大小来确定两个集合之间谁的元素更多，实际上这是在拿一个集合的元素去与自然数集合的元素做对应。如果某个集合中的元素能够与从小到大排列的自然数某个子集建立一一对应，那么就认为这个集合中元素的个数就是自然数子集中最大的那个数。

  再提出一个问题？下面的两条线段哪一条中包含的点更多？
          
  我第一次看到这个问题就觉得肯定有鬼。肯定不是下面这条长，应该是一样长，但是又不知道为什么它们一样长。我的导师直接画了两条线，我就恍然大悟了。
          
  下面那条线中的任一点总能在上面那一条线找到一一对应的点。这就是康托尔提出集合之间元素个数多少的判定标准，集合之间元素个数多少的比较，本质上在于集合间的对应（映射）。

  如果两个集合 A 和 B 之间能够建立一一对应（集合论中将这种对应叫做双射），那么就说这两个集合的元素个数一样多，记作 $|\mathrm{A}|$ = $|\mathrm{B}|$；如果能够建立 A 到 B 的单射（指每个 A 中的元素都对应一个 B 中的元素，且不同的 A 中元素对应的B中元素也不同），那么就说集合 B 的元素个数不少于 A 的元素个数，记作 $|\mathrm{A}|\le$ $|\mathrm{B}|$ 或 $|\mathrm{B}|\ge$ $|\mathrm{A}|$ 。

  对于元素个数有限的有限集来说，这种判定标准与日常人们熟悉的“数数”判定标准是一样的。一个有着100个元素的集合肯定能够与另外一个也有着100个元素的集合建立一一对应，但是绝不能与一个有着101个元素的集合建立起一一对应。

  设 $\mathrm{N}$ = {1, 2, 3, …} 是自然数集合，$\mathrm{E}$ = {2, 4, 6,…} 是正偶数集合，$n\in$ $\mathrm{N}$，$e\in$ $\mathrm{E}$，则建立集合 $\mathrm{N}$ 到 $\mathrm{E}$ 之间的映射 $f$：$\mathrm{N}$ $\to$ $\mathrm{E}$ 为 $e=f(n)=2n$。由此我们知道了，自然数的个数与正偶数的个数是一样多的。

---

1.2.2 基数

  有了前面关于集合元素个数比较大小的标准，我们就可以定义一个概念 —— 集合的基数。作为普及性文章，我们没有必要给出严格的基数定义，描述性的来说，

基数就是一个集合元素的个数（集合的基数有时也被叫做集合的势）。

  显然，对于有限集合来说，其基数就是这个集合的元素的个数，必然是一个自然数。但是对于无限集合来说，由于其元素个数无穷多，没有一个自然数能够表示，我们需要定义一些新的 “数”。我们首先定义自然数的个数是 ℵ₀ （这个符号来自于希伯来字母，可以读作阿列夫，自然数的个数就是阿列夫零）。显然，我们知道有理数、整数、奇数、偶数、代数数的个数都是 ℵ₀ 。

  那么问题来了，∅ 的基数是多少? { ∅ } 呢?

  $card(\varnothing )$ = 0; $card$( {∅} ) = 1

---

1.3 笛卡尔积

  我们最常用的是笛卡尔坐标系，一维数轴可表示为 $\mathbb{R}$，二维平面可表示为 $\mathbb{R}$ $\times$ $\mathbb{R}$ = ${\mathbb{R}}^2$，$n$ 维空间当然就是 ${\mathbb{R}}^n$ 了。

一维数轴上的点就是一个实数 $x$ ∈ $\mathbb{R}$
二维数轴上的点就是一个实数对 $(x,y)$ ∈ ${\mathbb{R}}^2$
一维数轴上的点就是一个向量($x_1,x_2,...,x_n)$ ∈ ${\mathbb{R}}^n$

  设 $\mathrm{A}$ 和 $\mathrm{B}$ 是两个集合，称集合 $\mathrm{A}$ $\times$ $\mathrm{B}$ = {<$x,y$> | ($x\in$ $\mathrm{A}$) $\wedge$ ($y\in$ $\mathrm{B}$) } 为集合 $\mathrm{A}$ 与 $\mathrm{B}$ 的笛卡尔积。

由笛卡尔积定义可以看出：

1. 设 $\mathrm{A}$, $\mathrm{B}$ 是任意两个集合，则不一定有 $\mathrm{A}$ $\times$ $\mathrm{B}$ = $\mathrm{B}$ $\times$ $\mathrm{A}$，即笛卡尔积不满足交换律；
2. $\mathrm{A}$ $\times$ $\mathrm{B}$ = ∅ 当且仅当 $\mathrm{A}$ = ∅ 或者 $\mathrm{B}$ = ∅；
3. 设 $\mathrm{A}$, $\mathrm{B}$, $C$ 是任意三个集合，则不一定有 $\mathrm{A}$ $\times$ $(\mathrm{B}$ $\times$ $C)$ = （$\mathrm{A}$ $\times$ $\mathrm{B}$) $\times$ $C$，即笛卡尔积不满足结合律；
4. 当集合 $\mathrm{A}$, $\mathrm{B}$ 都是有限集时，$|\mathrm{A}$ $\times$ $\mathrm{B}|$ = $|\mathrm{B}$ $\times$ $\mathrm{A}|$ = $|\mathrm{A}|$ $\times$ $|\mathrm{B}|$;
5. 笛卡尔积对并运算和交运算满足分配律。

  上述 4 在机器学习中最为常见，可以完美地表示混合类型的数据。任何实例都可以使用这种元素描述，但反过来，并非所有的元素都对应于数据集中的一个实例，即数据不会填满整个空间， 甚至通常在这个空间内是非常稀疏的。找出数据在空间中的分布规律，这也是数据挖掘的基本意义。

  说到数据集，这里介绍两种表示方法。

1. 矩阵表示法：
   当各个属性都为实型值时，数据集可表示为 $D$ ∈ ${\mathbb{R}}^{n\times m)}$ ，它表示每个实际的数据集，都是 $n\times m$ 维空间的一个点而已。如果记 $D=(x_1,x_2,...,x_n{)}^T$，则 $x_i$ ∈ ${\mathbb{R}}^m$;
2. 集合与向量混合法
   $D$ = { $x_1,x_2,...,x_n$}，则 $x_i$ ∈ ${\mathbb{R}}^m$;

---

优缺点

1. 集合与向量混合法中，元素可以随意交换顺序，这与现实数据的独立性一致。
2. 集合与向量混合法中，不允许两个元素相同，这与现实情况不一致。
3. 矩阵表示法可以支持矩阵的相乘,，易于表示加权等操作,，用于神经网络， 线性回归时方便。

注意：在机器学习中，经常用一个列向量表示一个实例。

---

1.4 幂集

  设 $\mathrm{A}$ 为任意集合，以 $\mathrm{A}$ 的子集为元素所组成的集合，称为 $\mathrm{A}$ 的幂集。

$P(\mathrm{A})=$ { $x|$ $x\subseteq \mathrm{A}$}; 若 $|\mathrm{A}|$ = $n$，则 $|P(\mathrm{A})|=$ $2^n$

---

举例：
$P(\varnothing )$ = { $\varnothing$}
$P$({ $\varnothing$}) = { $\varnothing$, { $\varnothing$}}
$P$({1, {2, 3}}) = { $\varnothing$, {1}, {2,3}, {1, {2, 3}}}

  幂集不仅限于有穷集，对于任意无穷集也有效。

---

2. 二元关系

  其实不用想得太复杂，关系就是关系。比如，1 < 2 是二元关系，我爱学习也是二元关系。我认为如果两个东西之间有联系，并且说明了联系的方式，那就可以称之为关系。

  另外，两个集合的笛卡尔积是遍历了所有的 “对”，之所以是子集是因为上述 “联系的描述” 可能对某些对有效，对某些对无效。

  在平面直角坐标系中, 等于关系就是 45 度方向的一条线 ($x=y$)；小于关系就是这条线的左上部分 ($x<y$)；同理，大于关系就是这条线的右下部分 ($x>y$)。

---

3. 函数

  函数也叫映射、变换或对应。但是我们需要区别函数与方程的区别以及与关系的区别。

  函数定义：设 $f$ 是集合 $\mathrm{A}$ 到 $\mathrm{B}$ 的关系，如果对每个 $x\in \mathrm{A}$，都存在唯一的 $y\in \mathrm{B}$，使得 <$x,y$> ∈ $f$，则称关系 $f$ 为 $\mathrm{A}$ 到 $\mathrm{B}$ 的函数，记作 $f$: $\mathrm{A}\to \mathrm{B}$。$\mathrm{A}$ 为函数 $f$ 的定义域，$f(\mathrm{A})$ 为函数 $f$ 的值域。

注意：

1. $f(x)$ 表示一个变值，$f$ 代表一个集合。因此 $f\ne f(x)$。
2. $f(x)$ 是 $\mathrm{B}$ 的子集，即 $\mathrm{B}$ 中有些元素跟 $\mathrm{A}$ 不对应也可以。
3. 如果存在元素 $a\in \mathrm{A}$，在 $\mathrm{B}$ 中没有对应元素，那么关系 $f$ 就不是函数。
4. 如果存在元素 $a\in \mathrm{A}$，在 $\mathrm{B}$ 中有两个或两个以上对应的元素，那么关系 $f$ 就不是函数。

辨别函数与方程：从本质上，方程就是一个等式，而函数是一个对应关系。

辨别函数与关系的联系与区别

1. 在离散数学中，函数可以看作是一种特殊的二元关系
2. 从 $\mathrm{A}$ 到 $\mathrm{B}$ 的不同的关系有 2|$\mathrm{A}$||$\mathrm{B}$|个，但从 $\mathrm{A}$ 到 $\mathrm{B}$ 不同的函数却只有 |$\mathrm{A}$||$\mathrm{B}$| 个。(每个 $\mathrm{B}$ 中的元素都可以有 $|\mathrm{A}|$ 个 $\mathrm{A}$ 中元素匹配)。
3. 关系的第一个元素可以相同；函数的第一个元素一定是互不相同的。

  举个栗子，令函数的定义域为 $D$, 值域为 $V$，可以认为函数 $D\times V$ 的子集，也就是一种特殊的关系。如 $x^2+y^2=1$，它是二维平面 ${\mathbb{R}}^2$ 中的一个单位圆，为若干平面中的元素 (点) 所构成, 因此为 $\mathbb{R}$ 上（即定义域、值域均为 $\mathbb{R}$）的二元关系。但它不是一个函数。$y=\sqrt{1-x^2}$ 就既是函数，也是二元关系。

  在机器学习中，单标签任务学习器可以看做一个函数（毫无疑问）。对于多标签分类器，一个实例 $x$ 虽然同时拥有多个标签，但是可以把多个标签看作一个标签组合，每个实例对应的标签组合是唯一的，所以多标签分类器仍然是一个函数。

---

4. 元组（tuple）

  百度百科中提到。元组是关系库中的基本概念，关系是一张表，表中的每行（即数据库中的每条记录）就是一个元组，每列就是一个属性。在二维表中，元组也称为行或记录。

  笛卡尔积中每一个元素 $(d_1,d_2,...,d_n)$，叫做一个 $n$ 元组或简称为元组。
​
  以 Python 为例。元组也是一种序列，元组使用小括号表示，元素中各元素之间用逗号隔开。元组不支持修改或删除其所包含的元素。这也是与列表最本质的区别，列表是动态数组，如果想要修改元组中的元素，可先将其转换成列表。

  C++中也引入了元组 tuple, 可以定义任意多个类型的对象的组合，下面是 C++ tuple 的栗子。

#include <iostream>  
#include <vector>  
#include <string>  
#include <tuple>  
  
using namespace std;  
  
std::tuple<std::string, int>  
giveName(void)  
{
     
    std::string cw("Caroline");  
    int a(2013);  
    std::tuple<std::string, int> t = std::make_tuple(cw, a);  
    return t;  
}  
  
int main()  
{
     
    std::tuple<int, double, std::string> t(64, 128.0, "Caroline");  
    std::tuple<std::string, std::string, int> t2 =  
            std::make_tuple("Caroline", "Wendy", 1992);  
  
    //返回元素个数  
    size_t num = std::tuple_size<decltype(t)>::value;  
    std::cout << "num = " << num << std::endl;  
  
    //获取第1个值的元素类型  
    std::tuple_element<1, decltype(t)>::type cnt = std::get<1>(t);  
    std::cout << "cnt = " << cnt << std::endl;  
  
    //比较  
    std::tuple<int, int> ti(24, 48);  
    std::tuple<double, double> td(28.0, 56.0);  
    bool b = (ti < td);  
    std::cout << "b = " << b << std::endl;  
  
    //tuple作为返回值  
    auto a = giveName();  
    std::cout << "name: " << get<0>(a)  
            << " years: " << get<1>(a) << std::endl;  
  
    return 0;  
} 

输出结果：

num = 3  
cnt = 128  
b = 1  
name: Caroline years: 2013  

转载：https://blog.csdn.net/qq_41033011/article/details/116322404