고귀양이의 노트.

flask-admin을 사용할때, 특정 그룹의 사용자 ( admin? ) 가 아니면 admin 페이지에 접근 못하게 막고 싶을 수 있다.

(아니 대부분의 경우 막아야 한다!)

그럴때 사용하면 된다.

class MyAdminIndexView(AdminIndexView):
    def is_accessible(self):
      #블라블라 허용된 그룹의 사용자인지 판별 
      # session['id'] 가져와서 판별 등등.
      return False

admin = Admin(app, name='flask', template_mode='bootstrap3', index_view = MyAdminIndexView())

바로 is_accessible() 메소드를 오버라이드 하여 막으면 된다.

근데 이 코드는 문제가 있다. 딱 index 페이지만 막힌 모습이다. model 별 url을 입력하면 통과해서 확인 가능하다.

이럴때는 ModelView를 추가할때, 동일하게 is_accessible() 메소드를 오버라이드 해주면 처리할 수 있다.

class MyModelView(ModelView):
  def is_accessible(self):
      #블라블라 허용된 그룹의 사용자인지 판별 
      # session['id'] 가져와서 판별 등등.
      return False

  column_display_pk = True

  def __init__(self, cls, session, **kwargs):
    super(MyModelView, self).__init__(cls, session, **kwargs)

admin = Admin(app, name='flask', template_mode='bootstrap3', index_view = MyAdminIndexView())
admin.add_view(MyModelView(TestTable, db.session))

이는 is_accessible() 메소드가 다음과 같은 class diagram에서 최상위 클래스인 'BaseView'에 있기 때문이다.

그래서 Index용과 그 외 ModelView용 페이지 인가 제어 ( 이 부분도 일반화되어 교체 가능하게 해도 되고 )

ModelView 클래스를 만들고, 모든 model view 만들때 상속시켜주면 이제 진짜 인가된 사용자 그룹만

허용 시킬 수 있게 된다. 

ball tree도 kd tree와 마찬가지로 knn(k-nearest neighbor) search에 많이 쓰이는 트리이다.

kd tree보다는 초기 트리 구성에 비용이 크지만, kd tree의 경우 차수가 아주 크면

query했을때 검색이 매우 느려지는데, ball tree는 kd tree보다 훨씬 빠르게 결과를 도출한다.

a(1,1550), b(900,440), c(2500,330), d(4000,2), e(5000,1)

위와 같은 데이터가 주어졌을때의 트리의 구성은 그림과 같다.

먼저 가장 범위가 큰 차수로 정렬을 시키고 (위 데이터에서는 1번째 차원의 범위가 1~5000이므로 가장 크다)

중간값을 취하고 왼쪽, 오른쪽으로 나눈 뒤 다시 재귀적으로 트리를 구성하도록 한다.

검색에 활용하도록 반지름 값도 구하는데 자식 노드중 가장 멀리 떨어진 노드와의 거리가 반지름이 된다.

이때, leaf size가 1보다 큰 경우 중간값을 size만큼의 개수를 취한다.

(leaf size는 검색 결과에 영향은 없지만 검색 속도에 영향이 있을 수 있다.)

예시 데이터를 기반으로 'ball'을 그려보면 다음과 같을 것이다.

알고리즘 설명및 코드의 한글 자료는 거의 전무하여 (내 검색 능력이 모자른 것일 수도)

위키백과와 사이트의 내용을 참고하였다.

import numpy as np

class Node:
    def __init__(self, data, radius, depth, left_child=None, right_child=None):
        self.left_child = left_child
        self.right_child = right_child
        self.data = data
        self.radius = radius
        self.depth = depth

    def printALL(self):
        print(self.radius, self.data, self.depth)
        if self.left_child != None:
            self.left_child.printALL()
        if self.right_child != None:
            self.right_child.printALL()

def balltree(ndata, depth):
    if ndata.shape[0] < 1:
        return None

    # element가 한 개일 경우
    if ndata.shape[0] == 1:
        return Node(
            data=np.max(ndata, 0).tolist(),
            radius=0,
            depth=depth,
            left_child=None,
            right_child=None
        )
    else:
        # 범위가 가장 큰 dimension에 따라 정렬
        largest_dim = np.argmax(ndata.max(0) - ndata.min(0))
        i_sort = np.argsort(ndata[:, largest_dim])
        ndata[:] = ndata[i_sort, :]

        nHalf = int(ndata.shape[0] / 2)
        loc = ndata[nHalf, :]
        data = loc.tolist()

        # 중간 값(data)에서 가장 멀리 떨어진 값 까지의 거리
        radius = np.sqrt(np.max(np.sum((ndata - loc) ** 2, 1)))

        return Node(
            data=data,
            radius=radius,
            depth=depth,
            left_child=balltree(ndata[:nHalf], depth+1),
            right_child=balltree(ndata[nHalf+1:], depth+1)
        )

if __name__ == '__main__':
    X = [[1,1550], [900,440], [2500,330], [4000,2], [5000,1]]
    X = np.asarray(X)

    tree = balltree(X, 0)
    tree.printALL()

역시 파이썬 패키지중 sklearn에서 balltree의 생성 및 검색을 간편하게 할 수 있다.

결과로 가장 유사한 데이터의 인덱스 번호와 거리를 반환한다.

import numpy as np
from sklearn.neighbors import BallTree

X = [[1,1550], [900,440], [2500,330], [4000,2], [5000,1]]
X = np.asarray(X)

# 트리 생성
tree = BallTree(X)

# 테스트 데이터 쿼리
dist, ind = tree.query([[1, 1551]], 1)

print(dist, ind)

-----------------------------------------------------------------------------------------------------------------------------------

참고

https://en.wikipedia.org/wiki/Ball_tree

https://www.astroml.org/book_figures/chapter2/fig_balltree_example.html

kd 트리는 이진 트리로, 모든 트리의 노드가 k차원으로 이루어져 있다.

최근 30차원의 데이터를 다루며 검색 및 존재 하지 않을 경우 유사도(유클리디안 거리)를 구하기 위해

보게 되었는데, 아쉽게도 트리를 구성하는 데이터가 10만개가 넘다보니 오래 걸렸다. (내 컴퓨터가 구린 것일 수도...)

어쨌든 간단하게 살펴보면,

a(7,2), b(5,4), c(9,6), d(4,7), e(8,1) 이 순으로 데이터가 트리가 삽입된다 하자

먼저 k=2가 된다.

a는 트리가 비어 있으므로 루트노드가 된다.

a의 x좌표를 비교하여 작은 애들은 왼쪽으로 큰 애들은 오른쪽으로 분류한다.

따라서 b는 a의 왼쪽 노드, c는 오른쪽 노드가 된다.

d의 x좌표는 a의 x좌표보다 작으므로 왼쪽으로 가지만 이미 b가 있으므로 이번에는 y좌표를 비교한다.

b의 y좌표보다 d의 y좌표가 크므로 오른쪽에 위치한다. 동일하게 e도 배치하면 위 그림과 같이 트리가 구성된다.

데이터 순서에 따라 트리의 구성이 달라지고 그에 따라 검색 속도도 천차만별로 바뀌게 된다.

이것을 막고자 트리 구성시 정렬 후 중간값을 취하도록 하는 방법도 있다.

from operator import itemgetter

class Node:
    def __init__(self, data, depth, left_child=None, right_child=None):
        self.left_child = left_child
        self.right_child = right_child
        self.data = data
        self.depth = depth
    def printALL(self):
        print(self.depth, self.data)
        if self.left_child != None:
            self.left_child.printALL()
        if self.right_child != None:
            self.right_child.printALL()


def kdtree(point_list, depth=0):
    if not point_list:
        return None

    k = len(point_list[0])
    axis = depth % k

    point_list.sort(key=itemgetter(axis))
    median = len(point_list) // 2

    return Node(
        data=point_list[median],
        depth=depth,
        left_child=kdtree(point_list[:median], depth + 1),
        right_child=kdtree(point_list[median + 1:], depth + 1)
    )

if __name__ == '__main__':
    point_list = [(7, 2), (5, 4), (9, 6), (4, 7), (8, 1), (2, 3)]
    tree = kdtree(point_list)
    tree.printALL()

위 코드는 위키백과의 것을 알기 쉽게 수정한 것이다.

트리 구성시 정렬하여 중간값을 취하고 재귀적으로 왼쪽과 오른쪽을 구하고 있다.

또한 python의 scipy라이브러리내 kdtree의 생성과 검색을 제공하고 있다.

from scipy import spatial

if __name__ == '__main__':
    point_list = [(7, 2), (5, 4), (9, 6), (4, 7), (8, 1), (2, 3)]
    tree = spatial.KDTree(point_list)

    print(tree.query((2, 3)))
    print(tree.query((2, 3.5)))

트리의 인자값으로 넣을 컨테이너로써 튜플이나 리스트외에도

DataFrame과 ndarray도 넣을 수 있다. query메소드로 검색하면 결과로

유클리디안 거리와 가장 유사한 노드의 인덱스 번호를 반환한다.