ZDD

アイテムセットマイニングの用語

m回の買い物イベント(トランザクション)があったとする n種類の商品:があったとする Tは買い物イベントの集合とする。買い物イベントのデータベースとも言う はT、すべての買い物イベントによって購入されたアイテムの「のべ総数」であり、買い物イベントデ…

演算子・メソッド一覧:ぱらぱらめくる『ZDD Ruby Package Documentation』

加算演算子 + これは集合で言えば、Union irb(main):002:0> require 'zdd' => true irb(main):003:0> univ = ZDD::itemset("a b c d e f g") => a b c d e f g irb(main):004:0> a = ZDD::itemset("a") => a irb(main):005:0> b = ZDD::itemset("b") => b ir…

チュートリアル:ぱらぱらめくる『ZDD Ruby Package Documentation』

2.1 ZDDライブラリをrequireで取り込む $ irb として対話モードで始めてみる 対話モードになったら、まず、zddをgemで入れた先をLOAD_PATHする > $LOAD_PATH.push("/home/ryamada/.gem/ruby/2.2.0/gems/zdd-1.0.0-linux/lib/nysol/") その上で > require 'zd…

準備:ぱらぱらめくる『ZDD Ruby Package Documentation』

nysol_zddのインストールはこちらを参考に rubyの本当の基礎 $ ruby myrb.rb と実行することもできるし 対話モードは $ irb とすればよい 対話モードを終了するには > quit rubyの調べもの

ぱらぱらめくる『ZDD Ruby Package Documentation』

nysolにZDDがある。それはrubyのラッパーになっているらしい rubyは初めてだけれども、やってみる Linux (Manjaro)で始める 『ZDD Ruby Package Documentation』

{0,1}行列データ

個のサンプルがある 個々のサンプルは長さのベクトルでその要素は 通りのベクトルが作れる そこから個の相互に異なるサンプルを取る、その場合の数は この本の長0,1ベクトルを、0,1分岐木の「あり、なし」としてとらえ、ZDD表現するとする それは制約付き整…

ZDD分岐木を描図する

from graphillion import GraphSet import pickle from itertools import chain import networkx as nx import matplotlib.pyplot as plt # ユニバースの要素数nに # [(1,2),(2,3),...,(n-1,n)]というユニバースとする n = 50 universe = [] for i in range(…

GraphillionのZDDデータ把持

PythonのGraphillionモジュールではユニバースと呼ぶ全体グラフを定めた上で、サブフラフの集合をZDDデータ構造として持つ その持ち方をしているのがGraphSetクラス それが実際にどういう持ち方をしているのかを確認したい 実際GraphSetクラスのオブジェクト…

ZDD Graphillionを使う 2

昨日の記事で、pythonのGraphillionパッケージを使ってみた 大まかなことが見えたので、整理し直して、チュートリアルの例から少し離れて、自分なりにGraphillionを使ってみるつもりで書いてみる python自体にも不慣れなので、その辺りも確認しながら まず、…

ZDD Graphillionを使う

超高速グラフ列挙アルゴリズム?〈フカシギの数え方〉が拓く,組合せ問題への新アプローチ?作者: ERATO 湊離散構造処理系プロジェクト,湊真一出版社/メーカー: 森北出版発売日: 2015/04/08メディア: 単行本(ソフトカバー)この商品を含むブログ (4件) を見る…

平面的なグラフ

ZDDとSimPathをやってみた(こちら) ZDDは「平面的なグラフ」で特に効果があるそうだ これは、いかにもそんな印象もあるけれど、その背景って…? 『平面分離定理』 頂点数nの平面(に描ける)グラフは、3つの頂点集合に分けることができて、その分け方ではフロ…

べたべたになぞってみる

ZDDは組み合わせの圧縮表現 Simpathはグラフの経路全網羅のためのZDD構築のアルゴリズム(こちら) アルゴリズムの説明をしてもらったけれど、どうやるのだか分らなかったのでRで、べたべたに書いてみることにする グラフがある を定める とエッジに順序を定め…

自分のイントロ ぱらぱらめくる『論理学をつくる』

論理学をつくる作者: 戸田山和久出版社/メーカー: 名古屋大学出版会発売日: 2000/10/10メディア: 単行本購入: 27人 クリック: 330回この商品を含むブログ (108件) を見る これを『ぱらぱらめくる』ことへのイントロ こちらやこちらで知識をグラフ・ハイパー…

重複していたらくっつける

Swarm intelligence(こちらとか)では、各所で勝手に「よかれ」と思ったことをやる その上で、いつの間にやら、効率的な状態にしてしまいたい ZDD(こちら)では組合せ爆発を圧縮してある 圧縮にあたっては、「使いまわせるノード」は使いまわす Swarm intellig…

CUDDパッケージ 手習い

CUDDのパッケージをとって来よう ホームパージ 圧縮ファイル Windowsでmakeやgccを動かすためにCygwinを入れよう Cygwinを入れるとLINUXコマンドがWindowsのコマンドプロンプトで動くようになる!のですね(こちらやこちら) Cygwinを入れるのもずいぶん久しぶ…

情報の劣化

昨日、ZDDでクリークを列挙する話を書いた グラフ情報(隣接関係の情報)からクリークを列挙するのは大変だ その大変さは、0/1のべき乗をZDD化するより、グラフ情報からZDD化する方が難しい(らしい)ことと関係しそうだ 超立方格子上の点のハミング距離に適当に…

CUDD

ZDDについて勉強中 グラフのクリークの演算がありそうなCUDDというのがある PDF ダウンロードなどのサイト ダウンロード用圧縮ファイル置き場が見つかりにくいけれど... こちら PDFにある記載 Graph operators Cudd_zddCliques: Finds the set of all clique…

BDDとZDD

xは行の真偽値表(2列) library(igraph) bzdd <- function(x,type="zdd"){ v <- c(x) K <- log(length(v),2) # グラフに描くときに、判断分岐の高さごとにy軸座標を与えたいので、その値 lay.y <- c() for(i in 1:K){ lay.y <- c(lay.y,rep(i,2^(i-1))) } # …

piDD 置換DD

置換集合向けの決定木ダイアグラムpiDD 資料1 資料2 BDD/ZDDは組み合わせ集合の空間の部分をうまく表現する仕組み BDDの構成アルゴリズム BDDをべたべたにRで書いてみようこちら piDDは置換(順列)の集合の空間の部分をうまく表現する仕組み(らしい) ルービ…

ZDD:ぱらぱらめくる『クヌース本4.1』

ZDD:ゼロ抑制BDD 組合せ論で力を発揮する に行きつく経路が多いときに有用である BDDと違う点 節点の解釈が違う 終点ははないこともある 節点からの2本のエッジが同一のノードに接続することもある 節点数が節約されることがある BDDではノードが「Primitiv…

BDD/ZDD

日本語総説はこちら 組合せ発散に対する、この方法の効果はこちらの動画と実行例コードで BDD:binary decision diagram 個の2分岐がの場合を作る。それを表したのが二分決定木(binary decision tree) BDDは二分決定木を簡略したグラフ の3分岐の「○、×」が…