OpenCVの内部関数partitionをPython3.xで焼き直す
能書き
OpenCVについて以前調べているとき、内部関数partitionの存在を知った。
簡易なクラスタリングを行う汎用関数のようだ。
個人的には、こいつはとんでもなく使い勝手が良い関数だと思う。
ただし残念なことに、この関数はユーザに開放されていないのだ。*1
そいつを、自力で焼き直して解決してみた話。
こんなときにお勧め
- クラスタリングではあるが、問題が簡単なのでサクッと書きたい
- 同属条件がルールベースで表現でき、学習を求めていない
- クラスタ数が事前に予測できない (でもx-meansを使うほどでもない)
- ラムダ式を覚えたばかりで使いたくてたまらない
How to Use
大抵の読者にとって、『どのように実現するか』は関心の外にあるだろう。
差が1以内の要素を同一グループにする
連続する要素を同一のクラスタに振り分ける。
from partition import partition
my_list = [i for i in range(20)]
del my_list[3:6]
del my_list[4:8]
print(my_list) # [0, 1, 2, 6, 11, 12, 13, 14, 15, 16, 17, 18, 19]
part1 = partition(my_list, lambda x, y: abs(x-y) <= 1)
print(part1) # [0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2]
偶奇をグループ分けする
偶数／奇数にそれぞれ0／1のラベルを与える。
part2 = partition(my_list, lambda x, y: x % 2 == y % 2)
print(part2) # [0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
結果に応じて分割する
意外と煩雑な処理が必要なので、関数gen_groupを用意しておいた。
from partition import gen_group
for group in gen_group(my_list, part1):
print(group)
"""出力
[0, 1, 2]
[6]
[11, 12, 13, 14, 15, 16, 17, 18, 19]
"""
for group in gen_group(my_list, part2):
print(group)
"""出力
[0, 2, 6, 12, 14, 16, 18]
[1, 11, 13, 15, 17, 19]
"""
実装
本家のpartitionに倣って、UnionFind木を利用する。
素集合データ構造（そしゅうごうデータこうぞう、英: disjoint-set data structure）は、データの集合を素集合（互いにオーバーラップしない集合）に分割して保持するデータ構造。
自力で組むのも良い勉強になるだろうが...
ここではパフォーマンスを優先して既存のコードを利用する。*2
今回書いたpartition.pyは次のとおり。Gist
from itertools import product, groupby
import operator
from UnionFind import UnionFind
def _renumber(id_list):
id_set = set(id_list)
replace_dict = dict(zip(
sorted(list(id_set)),
[i for i, _ in enumerate(id_set)]
))
return [replace_dict[elem] for elem in id_list]
def partition(src_list, predicate_func):
src_len = len(src_list)
uf = UnionFind(src_len)
loop_obj = product(src_list, src_list)
for ij, (ei, ej) in enumerate(loop_obj):
i, j = divmod(ij, src_len)
if ei is ej:
continue
if not predicate_func(ei, ej):
continue
uf.union(i, j)
return _renumber(uf._id)
def gen_group(src_list, cluster_list):
groups = groupby(
sorted(
zip(src_list, cluster_list),
key=operator.itemgetter(-1)
),
key=operator.itemgetter(-1)
)
return (
[e[0] for e in elems] for _, elems in groups
)
この中で強いて解説するなら_renumber関数だろう。
この関数は野放図に振られたクラスタIDを、0からの連番に変更する。
>>> from partition import _renumber
>>> _renumber([0, 2, 4, 4, 6])
[0, 1, 2, 2, 3]
日頃行っているパズルのようなコーディングも、案外役に立つものだ。
おまけ - このモジュールを書いた経緯
もともと『近い点を同一視』する処理を実現するために書いた。
このように新たな発見があるものだから、teratailは面白い。*3
そこそこ便利なので、PyPIにアップする練習に使っても良いかもしれない。
どうせ既に似たようなモジュールがあるんだろうけど。
追記：2018/01/26
more_itertools.partitionという同様の関数が存在することが発覚。
ただし、これは２クラス分類しか出来ないようだ。セーフセーフ。
more_itertools.partition(pred, iterable)
Returns a 2-tuple of iterables derived from the input iterable. The first yields the items that have pred(item) == False. The second yields the items that have pred(item) == True.
