欢迎访问欧博亚洲(Allbet Game)!

首页科技正文

张家口百姓网:【硬核】使用替罪羊树实现KD-Tree的增删改查

admin2020-04-1653

本文始发于小我私家民众号:TechFlow,原创不易,求个关注


今天是机械学习的第16篇文章,我们来继续上周KD-Tree的话题。

若是有没有看过上篇文章或者是最新关注的小伙伴,可以点击一下下方的传送门:

【硬核】机械学习与数据结构的完善连系——KD-Tree

旋转不可行剖析

上周我们实现了KD-Tree建树和查询的焦点功效,然后我们留了一个问题,若是我们KD-Tree的数据集发生转变,应该怎么办呢?

最质朴的设施就是重新建树,然则显然我们每次数据发生更改都把整棵树重修显然是不科学的,由于绝大多数数据是没有转变的,而且我们重新建树的成本很高,若是更改稍微频仍一些会导致大量的开销,这显著是不合理的。

另一个思绪是借鉴平衡树,好比AVL或者是红黑树等树结构。在这些树结构当中,当我们新增或者是删除节点导致树发生不平衡的情形时,平衡树会举行旋转操作在不改变二叉搜索树性子的前提下维护树的平衡。看起来这是一个对照好的方式,然则遗憾的是,这并不太可行。由于KD-Tree和二叉搜索树差别,KD-Tree中的节点存储的元素都是高维的。每一棵子树的权衡的维度都差别,这会使得旋转操作变得异常贫苦,甚至是不可行的。

我们来看下面这张图:

这是平衡树当中经典的左旋操作,它旋转前后都知足平衡树的性子,即左子树上所有元素小于根节点,小于右子树上所有元素。通过旋转操作,我们可以调换树结构,然则不影响二叉搜索树的性子。

问题是KD-Tree当中我们在差别深度判断元素巨细的维度差别,我们旋转之后节点的树深会发生转变,会导致判断尺度发生转变。这样会导致旋转之后不再知足KD-Tree的性子。

我们用适才的图举个例子:

我们给每个节点标上了数据,在树深为0的节点当中,划分维度是0,树深为1的节点划分维度是1。当我们旋转之后,很显著可以发现KD-Tree的性子被打破了。

好比D节点的第0维是2,B节点是1,然则D却放在了B的左子树。再好比A节点的第1维是3,E节点的第1维是7,然则E同样放在了A的左子树。

这还只是二维的KD-Tree,若是维度更高,会导致情形加倍庞大。

通过这个例子,我们证实了平衡树旋转的方式不适合KD-Tree

那么,除了平衡树旋转的方式之外,另有其他方式可以保持树平衡吗?

别说,还真有,这也是本篇文章的正主——替罪羊树。

替罪羊树

替罪羊树实在也是平衡二叉树,然则它和通俗的平衡二叉树差别,它维护平衡的方式不是旋转,而是重修

为什么叫替罪羊树呢,替罪羊是圣经里的一个宗教术语,原本指的是将山羊献祭作为赎罪的仪式,厥后才衍生出了代人受过,背锅侠的意思。替罪羊树的意思是一个节点的转变可能会导致某一个子树或者是整棵树被摧毁并重修,相当于整棵子树充当了某一个节点的”替罪羊“。

替罪羊树的里异常简朴粗暴,不强制保证所有子树完全平衡,允许一定水平的不平衡存在。当我们插入或者删除使得某一棵子树的节点跨越平衡底线的时刻,我们将整棵树拍平后重修。

好比下图红框当中示意一棵不平衡的子树:

很显著,它不平衡地十分严重,跨越了我们的底线。于是我们将整棵子树拍平,拍平的意思是将子树当中所有的元素所有取出,然后重修该树。

拍平之后的结果是:

拍平之后重修该子树,获得:

我们把重修的这棵子树插回到原树上,取代之前不平衡的部门,这样就保证了树的平衡。

整个原理应该异常简朴,底层的细节也只有一个,就是我们怎么权衡什么时刻应该执行拍平重修的操作呢

这一点在替罪羊树当中也异常简朴粗暴,我们维护每一棵子树中的节点数,然后通过一个参数alpha来控制。当它的某一棵子树的节点数的占比跨越alpha的时刻,我们就以为不平衡性跨越了限度,需要举行拍平和重修操作了。

一样平常alpha的取值在0.6-0.8之间。

删除

在替罪羊树当中删除节点有许多种方式,然则多数大同小异,焦点的头脑是我们删除节点并不是真的删除,而是给节点打上符号,符号这个节点在查询的时刻不会被思量进去。

然则节点被打上符号而不是真的删除虽然实现起来简朴,然则也有隐患,究竟一个节点被删除了,我们把它留在树上一段时间还可以接受,一直留着显然就有问题了。不仅会占用空间,也会给盘算增添肩负

针对这种情形,也有几种差别的解决计谋。一种计谋是不用剖析,守候某一次插入的时刻发现树不平衡,举行拍平重构的时刻将已经删除的节点移除。另一种计谋是我们也删除设置一个参数,当某棵子树上被删除的元素的比例跨越这个阈值的时刻,我们也同样举行子树的拍平重修。然则岂论选择哪一种,本质上来说都是惰性操作

所谓的惰性操作一样平常是通过符号取代原本庞大的运算,守候以后需要的时刻执行。这个所谓需要的时刻可以是以后查询到的时刻,也可以是积累到一定阈值的时刻。总之通过这样的设计,我们可以简化删除操作,由于加上符号不会影响树结构,以是也不用忧郁不平衡的问题。

新增和修改

对于KD-Tree的通例实现来说,修改和新增是一回事,由于我们会通过删除新增来取代修改。这么做的缘故原由也很简朴,由于修改某一个节点的数据可能会影响整个树结构,尤其是KD-Tree中的数据是多维的,以是我们是不能随意修改一个节点的

现实上不只是KD-Tree云云,许多平衡树都不支持修改,好比我们之前先容过的LSMT就不支持。固然不支持的缘故原由多种多样,本质上来说都是由于性价比太低。

我们再来看新增操作,二叉搜索树的纯新增操作实在是很简朴的,我们只需要遍历树找到可以插入的位置即可。KD-Tree当中的新增也是云云,虽然KD-Tree当中是多个维度,然则查找节点的逻辑和之前相差并不大。我们就顺着树结构遍历,找到需要插入的叶子节点即可。由于我们使用替罪羊树的原理来维护树的平衡,以是我们在插入的是时刻也需要维护子树当中节点的数目,以及会不会出发拍平操作。

若是存在子树违反了平衡条件,我们需要找到最上层的知足拍平条件的子树来举行拍平,否则的话底层的子树平衡了,然则上层的子树可能仍然需要拍平。注重这两个细节即可,其他的原理和通俗的二叉树插入节点一致。

我们来看下代码,寻找更多细节:

def _insert_data(self, node, data):
    # 子树节点的数目+1
    node.size += 1
    axis = node.axis
    new_axis = (axis + 1) % self.K
    flat = False
    # 当前节点的判断条件
    # 小于即是则进入左子树,否则进入右子树
    if data[axis] <= node.boundray:
        # 若是子节点为空,说明已经到叶子节点,建立新节点
        if node.lchild is None:
            new_node = KDTree.Node(
                data[new_axis], data, new_axis, node.depth + 11NoneNone)
            new_node.father = node
            node.lchild = new_node
        else:
            # 递归
            self._insert_data(node.lchild, data)
            # 回溯的时刻判断是否引发树不平衡
            if node.lchild.size >= self.alpha * node.size:
                self.rebuildNode = node
    else:
        # 逻辑同上,找到叶子节点,回溯的时刻判断是否不平衡
        if node.rchild is None:
            new_node = KDTree.Node(
                data[new_axis], data, new_axis, node.depth + 11NoneNone)
            new_node.father = node
            node.rchild = new_node
        else:
            self._insert_data(node.rchild, data)
            if node.rchild.size >= self.alpha * node.size:
                self.rebuildNode = node

我们再来看下拍平的逻辑,拍平实在就是拿到子树当中所有的节点。若是是二叉搜索树,我们可以通过中序遍历保证元素的有序性,然则在KD-Tree当中,元素的维度太多,再加上存在被删除的节点,以是有序性无法保证,以是我们可以忽略这点,拿到所有数据即可。

def flat_data(self, node, data):
    if node is None:
        return
    # 跳过删除元素
    if not node.deleted:
        data.append(node.value)
    self.flat_data(node.lchild, data)
    self.flat_data(node.rchild, data)

拿到所有数据之后也简朴,我们只需要挪用之前的建树函数,获得一棵新子树,然后将新子树插回到原树上对应的位置。

def rebuild(self):
    data = []
    # 拍平以rebuildNode节点为根的子树
    node = self.rebuildNode
    if node is None:
        return
    # 拿到所有数据
    self.flat_data(node, data)
    # 塞回到父节点当中去取代旧子树
    father = node.father
    if father is None:
        # 若是父节点为空说明是整棵树重修了
        self.root = self._build_model(data, node.depth)
        self.set_father(self.root, None)
    else:
        # 判断是左孩子照样右孩子
        position = 'left' if node == father.lchild else 'right'
        node = self._build_model(data, node.depth)
        if position == 'left':
            father.lchild = node
        else:
            father.rchild = node
        self.set_father(node, father)

这样一来,我们带增删改查功效的KD-Tree就实现好了。到这里,我们另有一个问题没有解决,就是庞大度的问题。

这样做看起来可行,真的庞大度会降低吗?很遗憾,这个问题涉及到异常庞大的数学证实,我暂时还没有找到靠谱的证实历程,然则可以一定的是,虽然我们每一次重修树都需要nlogn次盘算,然则并不是每一次插入和删除都市引发重修。若是假设发生大量操作的话,那么我们拍平重修的盘算会分摊到每一次查询上,分摊之后可以获得级别的插入和删除。现实上分摊的思绪异常常见,像是红黑树也是利用了分摊操作。

总结

到这里关于替罪羊树在KD-Tree的应用就竣事了,虽然这是一个全新的数据结构,而且和对照难题的平衡树有关,但实在焦点的思绪并不难题,非但不难题,而且有些过于简朴了,然则效果却又云云神奇,能解决一个云云棘手的问题,不得不说算法的魅力实在是无限。

另外,网络上绝大多数关于KD-Tree的博客都只有建树和查询的部门,虽然现实场景当中,这也基本上足够了。然则我小我私家以为,学习的历程应该是饱和式的,不能仅仅停留在够用上。究竟我们起劲保持学习的目的,并不只是为了让这些知识派上用场,更是为了可以拥有更强的能力,成为一个更优异的人。

最后,我把完整的代码放在ubuntu.paste当中,在民众号里回复'kd-tree2',我把完整代码发给你,和你一起学习。

若是你也这么以为,请随手点个关注或者转发吧,你们的举手之劳对我来说很主要。

,

Sunbet

Sunbet www.cangzhoujinchang.com Sunbet简单方便,游戏种类繁多,现推出手机客户端app,在sunbet即可下载,随时随地体验游戏带来的精彩!

转载声明:本站发布文章及版权归原作者所有,转载本站文章请注明文章来源:欧博亚洲(Allbet Game)!

本文链接:https://www.chen-eyes.com/post/697.html

网友评论

最新评论

  • 联博开奖 10/24 说:

    AllbetAPP下载欢迎进入AllbetAPP下载(www.aLLbetgame.us):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。真不错,很有深度

  • UG环球客户端 10/24 说:

    apple developer enterprise account for rentproviding apple enterprise developer accounts for rent, rent your own enterprise account for app signing. with high quality, stable performance and affordable price.让人惊叹呀

  • 环球UG 10/24 说:

    Allbet Gmaing欢迎进入欧博Allbet官网(www.aLLbetgame.us):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。总之就是精彩

  • 环球UG客户端下载 10/23 说:

    Allbet Gmaing开户欢迎进入Allbet Gmaing开户(www.aLLbetgame.us):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。想穿越进去

  • UG环球网址 10/23 说:

    欧博注册欢迎进入欧博注册(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。今天下雨,躲在家里看

  • UG环球官网开户网址 10/23 说:

    欧博亚洲手机版下载欢迎进入欧博亚洲手机版下载(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。就是很好,谁损也没用

  • UG环球代理 10/23 说:

    欧博亚洲客户端下载欢迎进入欧博亚洲客户端下载(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。666高级网文

  • AllbetGmaing开户 10/22 说:

    Allbet Gmaing代理欢迎进入Allbet Gmaing代理(www.aLLbetgame.us):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。不会吧,这也太意外了