索引、切片

基本切片、索引

• 基本切片[Slice]start:stop:step（基本同原生类型切片）

  • start、stop负值时，按维度长取正模
  • step>0时，start缺省为0、stop缺省为维度长N
  • step<0时，start缺省为N-1、stop缺省为-N-1
  • stop、start可以超过维度长N

• Ellipsis/...：放在切片中表示选择所有

  • ...存在的场合，结果总是数组而不是数组标量，即使其 没有大小

• np.newaxis/None：为切片生成数组在所在位置添加长度为 1的维度

• 切片可以用于设置数组中的值

• 基本切片可认为是依次对各维度切片，若靠前维度为索引，则 可以把靠前维度独立出来
• 基本切片生成的所有数组始终是原始数组的视图，也因此存在 切片引用的数组内存不会被释放
• 注意：基本索引可用于改变数组的值，但是返回值不是对数组 中对应值的引用

高级索引

• 选择对象为以下类型时会触发高级索引

  • 非元组序列
  • ndarray（整形或boolean类型）
  • 包含至少一个序列、ndarray（整型或boolean类型）的 元组

• 高级索引总是返回数据的副本

  • 高级索引结果不能保证任何内存布局

整数索引

• 整数索引X[obj]允许根据其各维度索引选择数组X任意元素

  • 各整数索引（数组）表示对应维度的索引
  • 各维度索引迭代、连接得到各元素位置：zip(obj*)
  • 索引维数小于数组维数时，以子数组作为元素 （可以理解为索引和数组高维对齐后广播）

• 整数索引结果shape由obj中各维度索引shape决定

  • 整数索引obj中各维度索引数组会被广播
    • 各维度索引shape可能不同
    • 为保证各维度索引能正常迭代选取元素，各维度索引 shape需要能被广播、符合广播要求
  • 则高级索引出现场合
    • “普通索引（标量值）”不存在，必然被广播
    • 切片能够共存

• 切片（包括np.newaxis）和高级索引共存时

  • 高级索引特点导致其结果维度不可割
    • “标量索引”本应削减该维度
    • 而高级索引整体（广播后）决定唯一shape
  • 高级索引结果维度应整体参与结果构建
    • 高级索引被切片分割：高级索引结果维度整体提前
    • 高级索引相邻：高级索引结果维度填充至该处

• 高级索引操作结果中无元素，但单个维度索引越界的错误未定义
• 高级索引结果内存布局对每个索引操作有优化，不能假设特定 内存顺序

1
2
3
4
5
6
7
8

X = np.array([[0,1,2],[3,4,5],[6,7,8],[9,10,11]])
rows = [0, 3]
cols = [0, 2]
 # 整数索引
X[np.ix_(rows, cols)]
 # 整数索引数组
X[[[1,2],[2,1]],:]
X.take([[1,2],[2,1]], axis=0)

Boolean索引

• Boolean索引obj选择其中True处位置对应元素

  • 索引obj维数较数组X小，直接抽取子数组作为元素 （可以理解为索引和数组高维对齐后广播）
  • 索引obj在超出数组X.shape范围处有True值，会引发 索引错误
  • 索引obj在X.shape内未填充处等同于填充False

• Boolean索引通过.nonezero方法转换为高级整数索引实现

  • Boolean索引等价于True数量长的1维整数索引
    • X[..,bool_obj,..]等价于 X[..,bool_obj.nonzero(),..]
    • Boolean索引总是削减对应索引，展开为1维
  • Boolean索引、高级整数索引共同存在场合行为诡异
    • Boolean索引转换为等价的整数索引
    • 整数索引需要广播兼容转换后整数索引
    • 整数索引、转换后整数索引整体得到结果

• 索引obj和数组X形状相同计算速度更快

字段名称形式访问

• ndarray中元素为结构化数据类型时，可以使用字符串索引 访问
  • 字段元素非子数组时
    • 其shape同原数组
    • 仅包含该字段数据
    • 数据类型为该字段数据类型
  • 字段元素为子数组时
    • 子数组shape会同原数组shape合并
  • 支持字符串列表形式访问
    • 返回数组视图而不是副本（Numpy1.6后）

K-dimentional Tree

Kd树：循环遍历各维度，按该维度取值二分数据

• 对高维数据进行快速搜索二叉树

  • 超平面都垂直于轴的BSPTree

• Kd树对样本点的组织表示对k维空间的划分

  • 每个节点对应k维空间中超矩形区域
  • 构造kd树相当于用垂直于坐标轴超平面不断划分k维空间， 得到一系列超矩形区域

• Kd树构建目标

  • 树应该尽量平衡，即分割应尽量均匀
  • 最大化邻域搜索的剪枝

建树

• 输入：数据点$X_i, i=1,2,\cdots,N$

• 确定划分维度（轴）
  • 选择方差最大的轴，使得数据尽量分散
  • 按次序循环遍历所有轴：方便查找时定位轴
• 选择该维度上数值中位数作为划分点
  • 中位数查找方法
    • 各维度统一全体排序、记录
    • 抽样，使用样本中位数
  • 小于中位数的数据点划分至左子树，否则划分至右子树
• 递归建立左、右子树直至无法继续划分
  • 节点中包含数据项数量小于阈值

查找K近邻

• 输入：Kd树、目标点x

• 在Kd树中找出包含目标点x的叶节点，以之为近邻点

  • 从根节点出发，与节点比较对应坐标值，递归访问至叶节点 为止
  • 目标点在训练样本中不存在，必然能够访问到叶节点

• 沿树回溯，检查节点是否距离目标点更近，尝试更新

• 检查该节点另一子区域是否可能具有更近距离的点

  • 即考察以目标点为圆心、当前近邻距离为半径圆，同划分轴 是否相交
  • 则只需比较目标点同相应切分平面距离、近邻距离

• 若目标点同该对应切分平面距离小于近邻距离

  • 则将目标节点视为属于该子区域中的点
  • 从节点未访问子树开始重复以上步骤，进行近邻搜索

• 否则继续回退

• 退回到根节点时，搜索结束，近邻点

• 回溯过程中需要盘对子域是否访问过，可以通过标记、比较相应 轴坐标等方式判断
• k>1的情况类似，不过检测时使用最远近邻，新近邻需要和所有 原近邻依次比较

其他操作

插入新节点

• 从根节点出发，根据待插入节点、当前节点在对应维度取值确定 插入左、右子树
• 遍历直至叶子节点，插入

删除节点

• 简单方法：将待删除节点子节点组成新集合，对其重新构建， 将新子树挂载在原被删节点位置

• 分类讨论：设删除节点T对应划分维度为D

  • 节点无子树：直接删除
  • 节点有右子树
    • 在右子树寻找维度D取值最小节点P，替换被删除节点T
    • 在右子树递归处理删除节点P
  • 节点无右子树有左子树
    • 在左子树寻找维度D取值最小节点P，替换被删除节点T
    • 将T的左子树作为P的右子树
    • 在右子树递归处理删除节点P

查找维度D最小点

• 若当前结点切分维度为D：只需查找左子树
• 否则需要对左、右子树分别递归搜索

Vantage Point Tree

VP树：任选样本点，按照数据点与该点距离二分数据

• 对高维数据进行快速搜索二叉树

• VP树对样本点的组织表示对k维空间的划分

  • 每个节点对应k维空间中一个球形划分
  • 构造kd树相当于用以给定样本点为球心不断划分k维空间， 得到一系列球内、球外区域

建树

• 输入：数据$X_i, i=1,2,\cdots,n$

• 选择某数据点$X_v$作为划分球心
• 计算其他数据点距离$D_i = d(X_i, X_v)$
• 求出$D_i$中位数$M$
  • 与$X_v$距离$D_i \leq M$的数据点$D_i$划分至左子树
  • 与$X_v$距离$D_i \gt M$的数据点$D_i$划分至右子树

Rectangle Tree

R树：将空间划分为有重叠的

• B树高维推广
  • 类似B树将一维区间划分为多个不重叠的子区间
  • 同样是平衡树，所有叶子位于同一层上

• R树退化至1维有分割区间重叠问题，效果不如B树

性质

• $M$：节点中最大键数量
• $m \leq \frac M 2$：节点中条目最小数量

• 非根叶节点包含$m-M$索引记录：$I$表示可在空间中完全覆盖 节点中条目点的MBR

• 非根、非叶节点包含$m-m$个子节点：$I$表示可在空间中完全 覆盖节点中条目矩形的MBR

• 根节点条目数$[2, m]$，除非为叶子节点

• minimal bounding rectangle：MBR，最小边界矩形

节点结构

• 叶子节点结构：$(I, tuple-ids)$

  

  • $I((s_1, e_1), (s_2, e_2), \cdots, (s_n, e_n))$： n维空间中矩形
  • $tuple-ids$：节点包含的记录

• 非叶节点：$(I, child-pointer)$

操作

建树

矩形搜索

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

SearchRect(T, S, ret):
	// 利用R树搜索矩形范围中包含的记录点
	// 输入：R树根节点T、待搜索矩形S
	// 输出：矩形S覆盖的条目

	if T.I join S == NULL:
		return

	// 若T不是叶子节点，检查其每个条目E
	if not T.is_leaf():
		for E in T.entries:
			// 对与S相交E.I对应条目E，递归调用搜索
			if T.I join S != NULL:
				SearchRect(E, S, ret)

	// 若T是叶子节点且T.I与S相交，检查其每个记录点
	elif T.I join S != NULL:
		for E in T.entries:
			if E in S:
				ret.add(E)

选择所属叶子

1
2
3
4
5
6
7
8
9
10
11
12
13

ChooseLeaf(T, E):
	// 在R树中寻找新索引条目所属叶子节点
	// 输入：R树根节点T、索引条目E
	// 输出：E所属R树中叶子节点

	if T.is_leaf():
		Assert(E.is_subset(T))
		return T

	else:
		for T_E in T.entries:
			if E.is_subset(T_E)
				return ChooseLeaf(T_E, E) or T_E

插入新条目

1
2
3
4
5
6
7
8
9
10
11
12

Insert(T, E):
	// 向R树中插入新条目
	// 输出：R树根T、新条目E

	L = ChooseLeaf(T, E)
	if L.has_slot():
		L.add(E)
	else:
		LL = L.split()
		L.add(E)
		P = L.get_parent()
		

调整树

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

AdjustTree(T, L):
	// 从不满足节点开始调整R树至满足要求
	// 输入：R树根T、不满足要求节点L
	// 输出：

	if L.is_root():
		return

	P = L.get_parent_node()
	if L.splitted():
		NN = L.get_split_node()
		if P.
	// 调整节点L在父节点中矩形框I大小
	addjust_I(P.L.I)

R*-tree

X-tree

SS-tree

SR-Tree

Metric-tree

相似性检索

相似性检索：从指定目标集合中检索出与给定样本相似的目标

• range searches：范围检索，给定查询点、检索距离阈值
• K-neighbor searches：K近邻检索，给定查询点、检索结果 数量

• 待检索目标、样本：以指定feature space中的高维数据点 表示

• 相似性检索则在相应metric space中搜索样本点最近邻作为 检索结果

• 关键：对待检索的目标建立有效的相似性索引

  • 对待检索目标进行预划分，在对给定样本进行检索时，只需 对比相似索引中给出的可能相似的目标
  • 减少相似性检索的对比次数、I/O，让相似性检索在大规模 数据集中应用成为可能

Tree-Based Index

基于树结构的索引

• 向量维度大于20之后，仍然需要扫描整个向量集合的大部分， 与线性扫描没有太大差别

• 包括

  • kd-tree
  • R-tree
  • R*-tree
  • X-tree
  • SS-tree
  • SR-tree
  • VP-tree
  • metric-trees

Hasing-Based Index

基于哈希的索引技术：利用LSH函数简化搜索

• locality sensitive hashing：LSH，局部敏感哈希，特征 向量越接近，哈希后值越可能相同

  • 局部敏感哈希值能够代表代替原始数据比较相似性
  • 支持对原始特征向量进行非精确匹配

• hash技术能从两个方面简化高维数据搜索

  • 提取特征、减小特征维度

    • 在损失信息较小的情况下对数据进行降维
    • hash函数（特征提取方法）选择依赖于对问题认识
    • 一般都归于特征提取范畴

  • 划分特征空间（哈希桶）、缩小搜索空间

    • 将高维特征映射到1维先进行近似搜索得到候选集， 然后在候选集中进行精确搜索
    • hash函数的选择取决于原始特征表示、度量空间
    • 一般LSH都是指此类哈希技术

提取特征

• average hashing：aHash，平均哈希
• perceptual hashing：pHash，感知哈希
• differantiate hashing：dHash，差异哈希

划分空间

• MinHashing：最小值哈希，基于Jaccard系数
• 基于汉明距离的LSH
• 基于曼哈顿距离的LSH
• Exact Euclidean LSH：E2LSH，基于欧式距离

Visual Words Based Inverted Index

向量化方法：将向量映射为标量，为（图像）特征建立 visual vocabulary

• 基于K-means聚类（层级K-means、近似K-means）
• 在图像检索实际问题中取得了一定成功
• K-means聚类算法的复杂度与图像特征数量、聚类数量有关
  • 图像规模打达到百万级时，索引、匹配时间复杂度依然较高

• visual vocabulary：视觉词库，代表聚类类别整体
• visual word：视觉单词，每个代表一个聚类类别