数据结构第四讲:树(中)

4.1 二叉搜索树

查找

最小元素在树的最左边,最大元素在树的最右边

从根结点开始,利用递归进行查找。

插入

删除

  1. 如果是叶节点,直接删

  2. 如果只有一颗子树,直接拉出来补位

  3. 有两颗子树

    这样的好处是替代结点最多只有一颗子树,变动小

4.2 平衡二叉树

每个结点都有一个平衡因子,是两个子树树深之差

平衡二叉树的调整

RR旋转

破坏者插入在发现者的右子树的右子树上

LL旋转

破坏者插入在发现者的左子树的左子树上

LR旋转

破坏者插入在发现者的左子树的右子树上

RL旋转

破坏者插入在发现者的右子树的左子树上

4.3 小白专场:是否同一个二叉搜索树

不建树的判别方法

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
t1 = [3, 1, 2, 4]
t2 = [3, 4, 1, 2]

def cmpr(t1, t2):
try:
t1_root = t1.pop(0)
except:
t1_root = None
try:
t2_root = t2.pop(0)
except:
t2_root = None

if (t1_root is None) & (t2_root is None):
return 1
elif (t1_root is None) | (t2_root is None):
return 0
elif t1_root != t2_root:
return 0

left_t1 = [i for i in t1 if i < t1_root]
right_t1 = [i for i in t1 if i > t1_root]

left_t2 = [i for i in t2 if i < t2_root]
right_t2 = [i for i in t2 if i > t2_root]

res1 = cmpr(left_t1, left_t2)
res2 = cmpr(right_t1, right_t2)
res = min(res1, res2)
return res

cmpr(t1, t2)

建一棵树,再判别其他序列是否与该树一致

线性结构之习题选讲

逆转链表

反转前k个

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
class ListNode:
def __init__(self,x):
self.value=x
self.next=None

# head = ListNode(0)
p1 = ListNode(1)
p2 = ListNode(2)
p3 = ListNode(3)
p4 = ListNode(4)
p5 = ListNode(5)
p6 = ListNode(6)

# head.next = p1
p1.next = p2
p2.next = p3
p3.next = p4
p4.next = p5
p5.next = p6

def inverselist(p, k):
head = ListNode(x = None)
head.next = p.next
tmp = p.next
tmp2 = p
if k > 1:
while k > 1:
tmp = head.next
head.next = head.next.next
tmp.next = tmp2
tmp2 = tmp
k -= 1
p.next = head.next
head.next = tmp
return head
return p

def travesal(head):
res = []
while head.next is not None:
if head.value is not None:
res.append(head.value)
head = head.next
res.append(head.value)
return res

head = inverselist(p1, 1)
travesal(head)

全部反转

循环解法

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
class ListNode:
def __init__(self,x):
self.value=x
self.next=None

# head = ListNode(0)
p1 = ListNode(1)
p2 = ListNode(2)
p3 = ListNode(3)
p4 = ListNode(4)
p5 = ListNode(5)
p6 = ListNode(6)

# head.next = p1
p1.next = p2
p2.next = p3
p3.next = p4
p4.next = p5
p5.next = p6

def travesal(head):
res = []
while head.next is not None:
if head.value is not None:
res.append(head.value)
head = head.next
res.append(head.value)
return res

def inverselist1(p):
if p is None or p.next is None:
return p

cur = p.next
pre = p
p.next = None
while cur.next is not None:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
cur.next = pre
return cur

head = inverselist1(p1)
travesal(head)

def inverselist2(p):
if p is None or p.next is None:
return p

cur = p.next
pre = p
p.next = None
while cur is not None:
h = cur
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return h

head = inverselist2(p1)
travesal(head)

递归解法

[TBC]

数据结构第三讲:树(上)

3.1 树与树的表示

查找

  • 顺序查找

    遍历,时间复杂度$O(n)$

  • 二分查找

    元素必须有序存放

    且必须放在数组中,不能放链表(单向,无法高效找到前一个节点)

    时间复杂度$O(\log n)$

    二分查找的启示:判定树

树的定义

树是保证结点连通的最小的一种连通方式

树的表示

  • 顺序结构

    难以表示结点之间的复杂关系

  • 链式结构

    各个结点结构不统一,如果采用树的度来统一每个结点的结构,则会造成空间浪费

    3.2 二叉树及存储结构

    二叉树的定义

    第三个性质的证明:

    从下往上看,除了根结点没有边,其他结点都有一条边

    从上往下看,叶结点没有边,度为1的结点有一条边,度为2的节点有两条边

    两者相等,得证。

二叉树的存储结构

顺序存储结构

链表存储

3.3 二叉树的遍历

遍历的递归实现

先序遍历

中序遍历

后序遍历

三种遍历的递归方式python实现

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
class Node:  
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树

root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))

def pretraverse(root):
if root:
print(root.value)
pretraverse(root.left)
pretraverse(root.right)

pretraverse(root)
print('------------')

def midtraverse(root):
if root:
midtraverse(root.left)
print(root.value)
midtraverse(root.right)

midtraverse(root)
print('------------')

def posttraverse(root):
if root:
posttraverse(root.left)
posttraverse(root.right)
print(root.value)

posttraverse(root)
print('------------')

三种遍历方式的关系

从代码上看,只是打印时机不同。

每个结点都会经历三次访问,第一次访问就打印是先序,第二次访问才打印是中序,第三次访问才打印是后序。

遍历的非递归实现

中序遍历

先序遍历

后序遍历

Python非递归实现二叉树的后续遍历

思路一:

  1. 使用一个栈stack保存经过的根结点,另一个栈flag保存每个结点的右子树是否遍历;
  2. 如果根结点存在,结点入栈,并把结点的右子树遍历结果置为0,代表没遍历;
  3. 把root指向左子树;
  4. 如果栈不为空,判断栈顶元素右子树是否存在以及是否已经遍历,如果存在并且没有遍历,则把root指向右子树;否则,结点出栈,并且把结点的右子树遍历标志出栈;
  5. 重复2-4直到栈空或者root不存在。

思路二:

后续遍历根结点,先遍历左子树,然后遍历右子树,此时反过来考虑:先遍历根结点,然后遍历右子树,最后是左子树,这样就可以转化为和先序遍历一个类型了,最后只把遍历结果逆序输出就ok了,而先序遍历是之前写过并且比较好理解的。

  1. 使用栈存储结点;
  2. 当结点存在或者栈不为空,判断结点;
  3. 当结点存在,结点值保存,结点入栈,并将指针指向结点的右子树;
  4. 当栈不为空,结点出栈,并将指针指向左子树;
  5. 重复2-4直到结果产生;
  6. 逆序输出结果,利用Python列表的-1.

三种遍历的非递归python实现

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
class Node:  
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树

root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))

def pretraverse(root):
stack = []
v = root
while (v is not None)|(len(stack) > 0):
while v is not None:
stack.append(v)
print(v.value)
v = v.left

if stack:
v = stack.pop()
v = v.right

pretraverse(root)
print('------------')

def midtraverse(root):
stack = []
v = root
while (v is not None) | (len(stack) > 0):
while v is not None:
stack.append(v)
v = v.left

if len(stack) > 0:
v = stack.pop()
print(v.value)
v = v.right

midtraverse(root)
print('------------')

def posttraverse_method1(root):
v = root
stack = []
flag = []
while (v is not None) | (len(stack) > 0):
while v is not None:
stack.append(v)
flag.append(0)
v = v.left

if len(stack) > 0:
v = stack[-1]
t = v.right
if (t is not None) & (flag[-1] is 0):
v = t
flag[-1] = 1
else:
flag.pop()
print(stack.pop().value)
v = None

posttraverse_method1(root)
print('------------')

def posttraverse_method2(root):
v = root
stack = []
res = []
while (v is not None) | (len(stack) > 0):
while v is not None:
res.append(v.value)
stack.append(v)
v = v.right

if len(stack) > 0:
v = stack.pop()
v = v.left
return res[::-1]

posttraverse_method2(root)
print('------------')

层序遍历

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
class Node:  
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树

root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))

def level_order_traversal(root):
res = []
queue = []
if root is not None:
queue.append(root)
else:
return res
while len(queue) > 0:
v = queue.pop(0)
res.append(v.value)
if v.left is not None:
queue.append(v.left)
if v.right is not None:
queue.append(v.right)
return res

level_order_traversal(root)

应用实例

遍历二叉树的应用:输出二叉树中的叶子结点

在遍历基础上判断打印结点是否为叶子结点即可

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
class Node:  
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树

root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))

def leaf_traversal(root):
res = []
queue = []
if root is not None:
queue.append(root)
else:
return res
while len(queue) > 0:
v = queue.pop()
if v.left is not None:
queue.append(v.left)
if v.right is not None:
queue.append(v.right)

if (v.left is None) & (v.right is None):
res.append(v.value)
return res

leaf_traversal(root)

求二叉树的高度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Node:  
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树

root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))

def getdepth(root):
if root is not None:
l_d = getdepth(root.left)
r_d = getdepth(root.right)
return max(l_d, r_d) + 1
else:
return 0

getdepth(root)

二元运算表达式树及其遍历

由两种遍历序列确定二叉树

必须要有中序遍历才行

3.4 小白专场: 树的同构

题意理解

求解思路

  1. 二叉树表示
  2. 建二叉树
  3. 同构判别

二叉树表示

这样的结构数组叫做静态链表

判别根结点:

哪个下标在数组里没有出现就是root

程序框架搭建

如何建二叉树

如何判别两二叉树同构

Python实现

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
import numpy as np
t1 = [['A', 'B', 'C', 'D', 'E', 'G', 'F', 'H'], [(1,2), (3,4), (5, -1), (-1, -1), (6, -1), (7, -1), (-1,-1), (-1,-1)]]
t2 = [['B', 'C', 'A', 'D', 'E', 'F', 'G', 'H'], [(4,3), (6,-1), (1, 0), (-1, -1), (5, -1), (-1, -1), (-1,7), (-1,-1)]]

class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树

root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))

def _curtree(inds, value_list, inds_list):
tree = Node()
if inds != -1:
tree.value = value_list[inds]
else:
return tree
if inds_list[inds][0] != -1:
tree.left = _curtree(inds_list[inds][0], value_list, inds_list)
if inds_list[inds][1] != -1:
tree.right = _curtree(inds_list[inds][1], value_list, inds_list)
return tree

def maketree(t):
leaf_inds = set(np.array(t[-1]).flatten())
root_inds = [i for i in range(len(t[0])) if i not in leaf_inds][0]
print(leaf_inds, root_inds)

value_list = t[0]
inds_list = t[1]

return _curtree(root_inds, value_list, inds_list)


def cmprtrees(t1, t2):
if (t1 is None) & (t2 is None):
return 1
elif (t1 is None) | (t2 is None):
return 0
elif t1.value != t2.value:
return 0
res1 = cmprtrees(t1.left, t2.left) & cmprtrees(t1.right, t2.right)
res2 = cmprtrees(t1.left, t2.right) & cmprtrees(t1.right, t2.left)
res = max(res1, res2)
return res

tree1 = maketree(t1)
tree2 = maketree(t2)

cmprtrees(tree1, tree2)

数据结构第二讲:线性结构

在线课程 MOOC浙江大学数据结构课程

2.1 线性表及其实现

多项式表示

问题: 如何表示一个多项式?

方法:

  • 顺序存储结构直接表示

  • 顺序存储结构表示非零项

  • 链表结构存储非零项

两个多项式相加过程:

  • 对于顺序存储直接表示,对应位相加即可
  • 对于只存储非零项的情况,需要依次比较大小,寻找同指数项系数相加

链式存储和顺序存储的区别

顺序存储要求物理相邻

  • 求表长,$O(1)$
  • 查找值, 遍历比对,时间复杂度$O(n)$
  • 在指定位置插入值,先移动后面的值再插入,时间复杂度$O(n)$
  • 删除指定位置的值,查找到后先删除再前移,时间复杂度$O(n)$

    链式存储通过建立链来确定逻辑关系,不要求逻辑相邻

  • 求表长,遍历i计数,时间复杂度$O(n)$

  • 查找,遍历比对,时间复杂度$O(n)$
  • 插入,先找到位置再插入,$O(n)$
  • 删除,先找到位置再删除,$O(n)$

广义表

对于线性表而言,每个元素都是基本的单元素。在广义表中,这些元素不仅可以是单元素还可以是另一个广义表。

2.2 堆栈

顺序存储实现堆栈

头部和尾部只是个概念,数组的两端完全可以做栈底。

单向链表实现堆栈

栈顶指针Top只能在链表头。因为如果在链表尾,一旦执行删除操作,单向链表没有办法找到该结点前一个位置。

中缀表达式转成后缀表达式

2.3 队列的实现

什么是队列

数据结构第一讲:基本概念

在线课程 MOOC浙江大学数据结构课程

1.1 什么是数据结构

书架放书

需要解决

  1. 新书插入
  2. 查找某本书的问题

方法:

  1. 随机按顺序放
    • 插入很简单,直接放最后
    • 查找很困难,一本一本找
  2. 按书名拼音顺序放
    • 插入困难,需要把所有拼音顺序在之后的书都后移
    • 二分查找
  3. 先分类,在按拼音顺序放
    • 小范围的插入和查找同上
    • 需要选择合适的类别数,太大则归类困难

打印数列

给定一个数N,一次打印从1到N.

方法:

  1. 遍历打印

    1
    2
    3
    4
    5
    6
    7
    def f1(n):
    for i in range(1, n+1):
    print(i)
    return

    print('f1-------')
    f1(10)
  2. 递归打印

    1
    2
    3
    4
    5
    6
    7
    8
    def f2(n):
    if n > 1:
    f2(n-1)
    print(n)
    return

    print('f2-------')
    f2(10)

看起来递归更加简洁,但是当n过大时,会挤爆空间!

多项式计算

程序实现
$$
f(x) = a_0 + a_1x + a_2x^2 + … + a_nx^n
$$
方法:

  1. 简单实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    def f1(x, n, a=None):
    if a is None:
    return
    y = a[0]
    for i in range(n):
    y += a[i+1] * x**(i+1)
    return y

    f1(2, 3,[1,2,3,4])
  2. 递归
    $$
    f(x) = a_0 + x(a_1 + x(…(a_{n-1} + x(a_n))…))
    $$

1
2
3
4
5
6
7
8
9
def f2(x, n, a=None):
if a is None:
return
y = a[-1]
for i in range(n, 0, -1):
y = y * x + a[i-1]
return y

f2(2, 3,[1,2,3,4])

加减法不耗资源,主要考虑乘除法的元素次数。

方法1做了$n + (1+2+…+(n-1)) = (n^2 + n)/2$次乘法运算

方法2做了n次乘法运算

优劣立现!

什么是数据结构

数据对象在计算机中的组织方式

  • 逻辑结构
  • 物理存储结构

抽象数据类型

  • 数据对象集
  • 操作集

1.2 什么是算法

  • 空间复杂度S(n)
  • 时间复杂度T(n)

1.3 最大子列和问题

问题:
$$
给定N个整数的序列{A_1, A_2, …, A_N},求函数f(i, j) = \max{\{0,\sum_{k=i}^j A_k\}}的最大值
$$

方法:

  1. 暴力破解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    def f1(a):
    s = 0
    inds1 = -1
    inds2 = -1
    for i in range(len(a)):
    for j in range(i, len(a)):
    t = 0
    # t = sum(a[i:j+1])
    for k in range(i, j+1):
    t += a[k]
    if t >= s:
    s = t
    inds1 = i
    inds2 = j
    return s, inds1, inds2

    f1([1,5,-6,7,2,-3,-4,8,-9,2])

    一开始使用sum函数,误以为时间复杂度是$O(n^2)$,其实sum本身也有复杂度,真实复杂度是$O(n^3)$。不要过度依赖函数,要看计算本质!

  1. 暴力破解优化

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    def f2(a):
    s = 0
    inds1 = -1
    inds2 = -1
    for i in range(len(a)):
    t = 0
    for j in range(i, len(a)):
    t += a[j]
    if t >= s:
    s = t
    inds1 = i
    inds2 = j
    return s, inds1, inds2

    f2([1,5,-6,7,2,-3,-4,8,-9,2])

    时间复杂度$O(n^2)$

  1. 分而治之

    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
    def f3_0(a, l, u):
    if l > u:
    return 0
    if l == u:
    return max(a[l], 0)
    mid = (l + u) // 2
    lmax = s = 0
    for i in range(mid, l-1, -1):
    s += a[i]
    lmax = max(lmax, s)
    rmax = s = 0
    for i in range(mid+1, u+1):
    s += a[i]
    rmax = max(rmax, s)
    return max(lmax+rmax, f3_0(a, l, mid), f3_0(a, mid+1, u))

    def f3(a):
    return f3_0(a, 0, len(a)-1)

    # 求三个数最大值方法
    def getmax(x, y, z):
    if (x >= y) & (x >= z):
    return x
    return getmax(y, z, x)

    f3([1,5,-6,7,2,-3,-4,8,-9,2])

  1. 在线处理

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    def f4(a):
    s = 0
    t = 0
    inds1 = -1
    inds2 = -1
    for i in range(len(a)):
    t = t + a[i]
    if t >= s:
    s = t
    if inds1 == -1:
    inds1 = i
    inds2 = i
    elif t > 0:
    continue
    else:
    t = 0
    inds1 = -1
    return s, inds1, inds2

    f4([1,5,-6,7,2,-3,-4,8,-9,2])

    在线处理的逻辑核心其实是一种链式增强的传播效应。

    用索引指代对应的数,符号指代其正负(e.g. (0)+表示第一位为正数)。当(0)+,(0+1)+,那么必然有(0+1+2)>=(1+2)。

注意循环的边界,什么时候j+1,什么时候不要。从i开始还是i+1开始。

需要注意细节处理,条件是否取等号影响到是否取到的是最短子列,以上实现取到的都是最后出现的最短子列。

大腕——冯小刚

电影名: 大腕

导演: 冯小刚

评分: 7

剧情: 尤优给大导演摄影记录了他的每一天。大导苦恼于无法拍出他想要的电影,突发重病昏迷。由于已经授权,尤优开始准备他的葬礼。由于资金缺乏,从而踏上了一条疯狂吸引广告的道路。最终大导醒来,将葬礼准备过程拍成了一场电影。

没完没了——冯小刚

电影名: 没完没了

导演: 冯小刚

评分: 7

剧情: 韩冬给大伟提供包车服务,但大伟一直拖欠账款。韩冬讨要无果,将装劫持大伟女友小莲。未曾想大伟不为所动。小莲对大伟的无动于衷很生气,于是和韩冬一起导演了一场绑架戏进一步试探大伟。

非诚勿扰——冯小刚

电影名:非诚勿扰

导演: 冯小刚

评分: 7

剧情: 秦奋相亲认识了笑笑,并被深深吸引。笑笑深爱已婚之夫,却又深知没有结果。邀请勤奋去北海道旅游,以此来忘记前任接受秦奋。最后依旧难以忘怀跳海殉情。。。

error&solution

hexo exists Template render error

在使用hexo g时出现Template render error错误。最后发现是.md文件中一些格式比如\{\{\}\}不被hexo支持解析。

如果不在代码块中,那么直接加转义符形如\{\{\}\即可,在typera中展示时不会出现转义符。

如果是在代码块中,也是通过加上转义符破坏\{\{形式,至于是每个括号都加转义符还是只加一个随意,比如这样{\{}\}。不好的地方是在代码块中会原样展现在typera的预览页面上。

hexo s failed, generate error

Troubleshooting

transformer

transformer模块为特征工程模块,encoder为其基本单元,encoder的作用为进行特征变换。

此文档用于规范encoder类的编写,同时列出各个encoder的参数列表。

编写规范

  1. 类取名应该清晰易懂, 符合一般规范(各单词首字母大写),以Encoder结尾, 例如BaseEncoder, WOEEncoder。对于只适用于cont的Encoder类应该以Cont作为类名开头,对于只适用于cate的Encoder类应该以Cate作为类名开头。

  2. 类必须包含__init__fittransformer方法,transformer模块也只会调用这三个方法

  3. fit方法必须形如:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    # 形式1
    def fit(self, df, y=None):
    ···

    # 形式2
    def fit(self, df, y):
    ···

    # 不需要return
  4. transformer方法必须形如:

    1
    2
    3
    4
    5
    6
    7
    8
    def transform(self, df):
    # 一系列处理过程
    df_final = df.copy()
    ...
    df_final.columns = df.columns
    return df.final

    # return必须是pandas.DataFrame,不能乱序,顺序必须和传入的df一致(最好保持index和传入的df一致,目前会在外部再做一次index对齐处理防止index不一致,最后列名也需要复原出来,因为某些方法会删掉列名)
  5. 异常处理和错误抛出规范:不要使用try...except...进行异常跳出,目前只需要正常让程序自行报错即可

  6. 必须有类注释,形如:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    """
    用于剔除缺失值严重列,同值严重列,不同值严重cate列(字符串列如果取值太过于分散,则信息量过低)。

    适用于cont和cate,支持缺失值, 建议放置在encoder序列第一位次

    Parameters
    ----------
    missing_thr: 0.8, 缺失率高于该值的列会被剔除

    same_thr: 0.8, 同值率高于该值的列会被剔除

    caate_thr: 0.9, 取值分散率高于该值的字符串列会被剔除

    Attributes
    ----------
    missing_cols: list, 被剔除的缺失值列

    same_cols: list, 被剔除的同值列

    cate_cols: list, 被剔除的取值分散字符串列

    exclude_cols: list, 被剔除的列名
    """
  7. 完成后必须进行单元测试,自测通过

BaseEncoder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
"""
用于剔除缺失值严重列,同值严重列,不同值严重cate列(字符串列如果取值太过于分散,则信息量过低)。

适用于cont和cate,支持缺失值, 建议放置在encoder序列第一位次

Parameters
----------
missing_thr: 0.8, 缺失率高于该值的列会被剔除

same_thr: 0.8, 同值率高于该值的列会被剔除

caate_thr: 0.9, 取值分散率高于该值的字符串列会被剔除

Attributes
----------
missing_cols: list, 被剔除的缺失值列

same_cols: list, 被剔除的同值列

cate_cols: list, 被剔除的取值分散字符串列

exclude_cols: list, 被剔除的列名
"""

NothingEncoder

1
2
3
4
5
"""
原样返回,不做任何处理。本用于测试,现在transformer支持在encoders序列为空情况下原样返回,此类已无实际用途。

适用于cont和cate,支持缺失值
"""

DropEncoder

1
2
3
4
5
"""
此类用于返回空df,换言之删除所有字段。

适用于cont和cate, 支持缺失值
"""

ContImupterEncoder

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
"""
此类继承自sklearn.preprocessing.Imputer,fit与基类完全一致,transform方法返回变为pandas.DataFrame。

仅适用于cont, 支持缺失值

Parameters
----------
missing_values : integer or "NaN", optional (default="NaN")
The placeholder for the missing values. All occurrences of
`missing_values` will be imputed. For missing values encoded as np.nan,
use the string value "NaN".

strategy : string, optional (default="mean")
The imputation strategy.

- If "mean", then replace missing values using the mean along
the axis.
- If "median", then replace missing values using the median along
the axis.
- If "most_frequent", then replace missing using the most frequent
value along the axis.

axis : integer, optional (default=0)
The axis along which to impute.

- If `axis=0`, then impute along columns.
- If `axis=1`, then impute along rows.

verbose : integer, optional (default=0)
Controls the verbosity of the imputer.

copy : boolean, optional (default=True)
If True, a copy of X will be created. If False, imputation will
be done in-place whenever possible. Note that, in the following cases,
a new copy will always be made, even if `copy=False`:

- If X is not an array of floating values;
- If X is sparse and `missing_values=0`;
- If `axis=0` and X is encoded as a CSR matrix;
- If `axis=1` and X is encoded as a CSC matrix.

Attributes
----------
enc : 实例化的Imputer对象

enc.statistics_ : array of shape (n_features,)
The imputation fill value for each feature if axis == 0.

Notes
-----
- When ``axis=0``, columns which only contained missing values at `fit`
are discarded upon `transform`.
- When ``axis=1``, an exception is raised if there are rows for which it is
not possible to fill in the missing values (e.g., because they only
contain missing values).
"""

ContBinningEncoder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
"""
将连续型变量转化为离散型

仅适用于cont, 支持缺失值

Parameters
----------
diff_thr: 20, 不同取值数高于该值才进行离散化处理,不然原样返回

binning_method: 'dt',分箱方法, 可用取值为'dt''qcut''cut'

bins: 10, 分箱数目, 当binning_method='dt'时,该参数失效

**kwargs: 决策树分箱方法使用的决策树参数

"""

WOEEncoder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
"""
woe变换

适用于cont和cate,但对多取值cont无效,支持缺失值

Parameters
----------
diff_thr: 20, 不同取值数小于等于该值的才进行woe变换,不然原样返回

woe_min: -20, woe的截断最小值

woe_max: 20, woe的截断最大值

nan_thr: 0.01, 对缺失值采用平滑方法计算woe值,nan_thr为平滑参数

"""

手机——冯小刚

电影名: 冯小刚

导演: 手机

评分: 7

剧情: 因为手机被发现婚外情。其中的情感纠葛。

手机,本应该让人与人之间的距离从远变近,却适得其反。太近了就没有了秘密,丑陋暴露的更加直接。怀疑、不信任也更容易变现。

王牌保镖——帕特里克·休斯

电影名: 王牌保镖

导演: 帕特里克·休斯

评分: 7

剧情: 为了不让黑暗政权首脑再次执政,检方条件交换,使得职业杀手充当证人。在护送杀手前去作证的路上,警方行动组被伏击。作为王牌保镖的男主受身为行动组长的前女友所托,和杀手一路协作,突破围杀,顺利抵达法庭。