決定木の理論とフルスクラッチ実装とその解説 - tomtom58’s blog
最初に 決定木の理論とフルスクラッチ実装とその解説というと、既に使い古された話題の様に感じてしまいますが、今回の記事から派生して、ランダムフォレスト、GBDT、XGboost(LightGBMは扱わないつもり)、因果木、因果フォレスト、ランダムフォレスト-learnerの理論とできる部分はフルスクラッチ実装、めんどくさいものは、理論と解説に抑えて扱っていこうと考えており、そのまず初めとして、決定木自体の理論に触れないことは、できないなと思い、決定木の記事を書こうと思った次第です。(めんどくさくなって書かないパターンも全然あり得るのでご了承ください)他の記事との差別化は、数式を含めた解説と、フルスクラッチ実装のコードと数式を絡めた解説みたいな感じで、初心者に超優しい解説記事みたいな感じで仕上げて見せると、書き始めは思っております。書いていくうちに、初心者に超優しくないじゃんみたいなことになっ
高速な文字列探索：Daachorseの技術解説 - LegalOn Technologies Engineering Blog
こんにちは。LegalForce Researchで研究員をしている神田 (@kampersanda) です。 LegalForce Researchでは現在、高速なパターンマッチングマシン Daachorse（ダークホース）を開発・運用しています。文字列処理の基礎である複数パターン検索を提供するRust製ライブラリです。以下のレポジトリで公開されています。 github.com 本記事はDaachorseの技術仕様を解説します。具体的には、 複数パターン検索に関係する基礎技術（トライ木・Aho–Corasick法・ダブル配列） Daachorseの実装の工夫と性能 を解説します。 以下のような方を読者として想定します。 文字列処理アルゴリズムやデータ構造に興味のある方 自然言語処理の要素技術に興味のある方 Rustライブラリに興味がある方 Daachorseについて 複数パターン検索の基
世界四連覇AIエンジニアがゼロから教えるゲーム木探索入門 - Qiita
はじめに 書籍化 本記事を元に ゲームで学ぶ探索アルゴリズム実践入門～木探索とメタヒューリスティクス という書籍を出版することになりました！ 本記事を読んで気になっていただけたらご購入をご検討いただけるとうれしいです！ この記事で得られる技術 ゲームルールに適した探索アルゴリズムを選択する ゲーム木探索をするのに適したクラス設計 主要なゲーム木探索アルゴリズムの実装 この記事の特徴 汎用アルゴリズムの実装例による他ゲームへの応用力と、実際に動作可能なサンプルコードによる具体的実装イメージの両視点でわかりやすくした（片方しか記載のない記事が多い） サンプルコード付き日本語記事がほぼないDUCTを解説している サンプルコードは印のついたメソッドを実装したクラスさえ書けば、アルゴリズム部分を変更せずそのまま他のゲームで動作可能になっている この記事で扱わない関連技術 探索の高速化 多様性の確保
xgboostのコードリーディング - threecourse’s blog
xgboostでどのような処理が行われているのかを、メモの意味でまとめてみました。 たぶん続きます。なお、あくまで私の理解であり、正確性の保証は無いのでご注意下さい。 ソースコードは以下を参照しています。 https://github.com/dmlc/xgboost (release_0.90を参照) 前提 以下の前提とする: ブースター(booster)はgbtree 決定木のアルゴリズム（tree_method）はexact カスタム目的関数を使わない GPUの使用、マシン並列を行わない xgboostでは、tree_methodオプションで決定木を作成するアルゴリズムを選択できる。 デフォルトではデータ数が一定未満の場合にはexact、それ以上であればapproxが適用される。 (4UL << 20UL = 4194304件が境目、GBTree::PerformTreeMethod
Segment Tree を少し速くする - Fixstars Tech Blog /proc/cpuinfo
このブログは、株式会社フィックスターズのエンジニアが、あらゆるテーマについて自由に書いているブログです。 Segment Treeと呼ばれるデータ構造があります。 プログラミングコンテストでも解法の一部として使われることが多いため、よくコンテストに参加するような人だとコピペで使えるように準備しているということも多いのではないかと思います。 このデータ構造を使うと、1次元の数列に対する以下の操作が $O(\log n)$ の時間計算量で可能となります。 query(l, r): $a_{l}\ \textrm{op}\ a_{l+1}\ \textrm{op}\ \cdots\ \textrm{op}\ a_{r-2}\ \textrm{op}\ a_{r-1}$ を求める update(i, x): $a_{i}$ に $x$ を代入する たとえば、最初に数列 $a = [ 0, 1, 2
木構造の整形表示コマンド forest を作った - Qiita
pattern1_root pattern1_root/pattern2_last_leaf root_node root_node/pattern3_non-last_leaf root_node/pattern3_non-last_leaf/sample root_node/pattern3_non-last_leaf/pattern4_non-last_node's_child root_node/leaf_node $ cat sample1.txt | forest ├ ─ pattern1_root │ └ ─ /pattern2_last_leaf └ ─ root_node ├ ─ /pattern3_non-last_leaf │ ├ ─ /sample │ └ ─ /pattern4_non-last_node's_child └ ─ /leaf_node
B TreeとB+ Treeの違い - Carpe Diem
概要 インデックスに対してMongoDBはB Treeを採用し、MySQLのInnoDBはB+ Treeを採用しています。 どうして採用しているアルゴリズムが違うのだろう？と思って調べてみました。 主な違い B+ TreeはほとんどB Treeと同じですが、以下の点が異なります。 リーフノードとリーフノードを結ぶポインタがある データはリーフノードのみに保持する 具体例 言葉だけだと分かりにくいので、Visualizeするツールを使って具体例を表示します。 [1, 2, 3, 4, 5, 6, 8, 10, 15, 18]という数列に対し、Order: 3で作ってみます。 Orderは１ノードから出る枝の数のことです。 B Tree B-Tree Visualization B+ Tree B+ Tree Visualization 先程のB Treeと違って、データはリーフノードに持つの
木の直径を求めるアルゴリズム - ペケンペイのブログ
注意：議論が洗練されておらず、真面目に読むべき記事ではありません。信頼できそうなグラフ理論の書籍を読んだほうが良いと思います。ウェブ上で閲覧できる資料としては以下があり、そこの References を辿ると良いでしょう。 http://mathworld.wolfram.com/GraphCenter.html 中心が高々 2 個であることと、2 個あるならばそれらは隣接していることは F. Harary の ''Graph Theory'' に証明があります。p. 35 の Theorem 4.2 Every tree has a center consisting of either one point or two adjacent points. がそれです。頻繁に参照される記事ではありませんので、この記事を改訂する予定は今の所ありませんが、幾らか思うところがあるので希望があれば
高次元ベクトルデータ検索技術「NGT」の性能と使い方の紹介
この結果を見て単語ベクトルが変わるとNGTの性能が変わってしまうように感じた方がいるかもしれません。しかし、実はこれらの単語ベクトルはデータの次元数や件数が違っているため、それぞれの条件をあわせてみる必要があります。興味がある方は論文を読んで見比べて欲しいと思いますが、ここで重要なことは、NGTが高い精度にも関わらず、せいぜい100ミリ秒程度で検索できるという規模感であるということです。その規模感を感じてもらうために、これらの実験結果をご紹介しました。この実験以外にも論文の中では単語ベクトルの応用としてアナロジーと呼ばれる合成ベクトルでの実験やその他の比較手法の比較、実験結果の考察などもありますが今回は割愛します。 これまで紹介した内容と同じような実験はLinux系のサーバーであれば公開しているExperimental softwareという実験プログラムを使うと簡単に試すことができます。
Introduction to Monte Carlo Tree Search - Jeff Bradberry
The subject of game AI generally begins with so-called perfect information games. These are turn-based games where the players have no information hidden from each other and there is no element of chance in the game mechanics (such as by rolling dice or drawing cards from a shuffled deck). Tic Tac Toe, Connect 4, Checkers, Reversi, Chess, and Go are all games of this type. Because everything in th
Disjoint-set data structure - Wikipedia
In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set into disjoint subsets. It provides operations for adding new sets, merging sets (replacing them by their union), and finding a representative member of a set. The
シンプルなBehaviour Treeを実装してみる | GREE Engineering
みなさまこんばんは。ちょびえです。 今日はちょっと趣向を変えてゲームのAIの勉強、なかでもBehaviour Treeについてすこし勉強してみましょう。 ゲームの世界のAIってなんだっけ？ ゲームの世界のAIといえばよくある経路探索や、特定状況下におけるNPC等のふるまいをよしなにやってくれるようなものです。AIっていわれてしまうとなんだか難しいように感じてしまいますが、ゲームという枠組みの中では時間経過や環境の変化を自立して判断したり・判断してるようにみせかけて楽しめるような仕組みとなっていれば良いと思います。 Behaviour Treeにチャレンジしてみる 細かい説明はググっていただくと色々と記載あるのでなんとなくビヘイビアツリーってわかるような、うーん・・・文章で書かれてもよくわからないですね！ということでお決まりの通りコードで書いてみましょう。 いきなりコード書いてもまったくわか
PostgreSQL プラン・ツリーの概要
このページでは PostgreSQL のプラン情報を保持するノード・ツリーの概略を解説する。 また PostgreSQL の生成するプランのノード・ツリー情報を可視化するために、Graphviz の dot ファイルとして書き出すエクステンション pg_plan_tree_dot を紹介する。 PostgreSQL 本体の改造やエクステンションを作成するために、プランを変更しようとする人向けの記事である。 現在は pg_plan_tree_dot は Linux の PostgreSQL 9.x 上でだけ動作する。 PostgreSQL の他の記事へのインデックスはここ。 更新履歴 (2014.11.30) 作成。 (2015.12.13) エクスプレッション・ノードとプラン・ノードを追加 (2016.09.24) Join と TargetEntry の説明を追加 (2017.01.07
Self-balancing binary search tree - Wikipedia
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Self-balancing binary search tree" – news · newspapers · books · scholar · JSTOR (November 2010) (Learn how and when to remove this message) An example of an unbalanced tree; following the path from the
Python で構文木を端末に描画してみる - ny23の日記
巷にある構文解析器には，解析結果を木構造で端末に表示する機能がある．あった方が良いだろうなと思いつつ，自分で実装するのはいかにも面倒そうだと感じて，今まで後回しにしていた．いい加減そろそろ無いと困ると感じるようになってきたので，先日の通勤電車の中で暇つぶしに書いたら，思いの外あっけなく実装できたので，メモ代わりに残しておく．最初 Ruby でワンライナーで書けないかなと思ったが，流石に難しかったので，練習も兼ねて Python で実装してみた． #!/usr/bin/env python # -*- coding: utf-8 -*- # Usage: lattice_to_tree.py < in.KNP # translate parser output into human-readable dependency tree structure import sys # customi
木メモ - Negative/Positive Thinking
はじめに 立派な庭師になるために、木についてちょっと調べてみたので、まとめておく。 木(構造)とは 閉路を含まない無向グラフを「森」という 連結な森を「木」という 与えられた頂点が全てつながっていて、閉路を含んでいない 閉路を含まない有向グラフは「DAG(Directed acyclic graph)」という ある頂点を根(Root)としてもつ木を「根付き木」という 2点v,wが辺を持ち、vの方が根に近い場合、vを「親」、wを「子」という 2点v,wについて、根とvとの経路にwが存在する場合、wはvの「先祖」、vはwの「子孫」という 子を持たない頂点を「葉」という 根から各点への経路の長さ(1辺を1とする)を「高さ」という 各点の子の数が常にn子の木を「n分木」という 連結グラフGについて、閉路ができなくなるまで辺を除去し続けると、残ったものは「全域木」となる 根付き木を探索などに用いるこ
決定木入門 | 開発ブログ | スパイシーラボ
こんにちは。永野と申します。スパイシーソフトでは2年弱のあいだ、CGMの事業部でアプリ★ゲットおよびマンガ★ゲットのリニューアルと保守を担当していました。現在は弊社が次に出すソーシャルゲームのログ分析の開発を担当しております。最近はまっているソーシャルゲームはモバゲーの神撃のバハムートとGREEのドラゴンコレクション、聖戦ケルベロスです。(TVCMでおなじみEXILEのカードを無課金でコンプしました。) 前述の通り現在私はログ分析を担当しています。現段階ではまずKPI算出や、離脱ページ特定、プレイヤーさんの行動および状態(ステータスやゲーム内リソース)の追跡など、基本的かつ効果が高い部分に注力して実装しているのですが、その先の一手のためにデータマイニングの再勉強をしています。今回はその中から決定木の紹介をいたします。 決定木とは分類器の一種で、データの集合から法則(変数)を発見するため
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Roulette Tree
GitHub - bacak/TrAP: TrAP is a tree averaging program. It computes medians and means of phylogenetic trees.
GitHub - alexkuz/react-json-tree: React JSON Viewer Component, Extracted from redux-devtools
