【Python】networkx + PyGraphvizで有向非巡回グラフ(Directed acyclic graph)をプロットする
昨日書いたコードで、「有向非巡回グラフ(Directed acyclic graph)をきれいにプロットする」ということが課題として残っていました。
ところが、よく考えたらDAGはワークフローエンジン等でよく使われている概念で、ワークフローエンジンで、タスクの順番をきれいに可視化する機能はよくあります。
例えば、以下の記事でも次のような紹介があります。
ジョブ依存関係の可視化
Hashだけだとジョブの全体図が分かり辛いのでgraphviz形式でジョブの全体図を出力できます。
graphサブコマンドにジョブネットのクラス名を渡します
上で使われているGraphviz
を使えば、自分のグラフもきれいにプロットできそうです。調べたところ、networkx
からPyGraphviz
ライブラリを経由してGraphviz
を呼び出せることがわかりました。
Drawing — NetworkX 1.11 documentation
brew install graphviz pip install pygraphviz
これを使えば、簡単にDAGがプロットできます。画像はフィクションです。
【Python】仕事の依存関係を有向非巡回グラフ(Directed acyclic graph)として整理するツールを作りました
特にデータ分析周りの仕事で、
といったような、タスクの依存関係がひどくて整理のつかない状態に陥ってしまいがちなため、それを解消するために作ったツールです。
集合・位相入門の半順序集合の章を読んでいるときに思いつきました。 元々は、Haskellの練習として、Ord型クラスで半順序集合を表現するようなコードを書いていましたが、グラフの扱いが慣れた言語でないと案外難しかった(また、冗談みたいですがYamlのパース方法が分からなかった)のでPythonで書きました。
↑のようなタスクの依存関係をひたすら以下のようなyamlファイルに書き出して、
# tasks.yml - name: write product code deps: - fix design - choose programing language - request for budget(ringi) - make a mock-up - name: choose programing language - name: request for budget(ringi) - talk to legal department - name: talk to legal department - name: releace deps: - write product code - code review - name: code review - write product code - name: make a mock-up deps: - choose programming language
コマンドを実行すれば、
# save as NetworkX graph ordmap tasks.yml tasks.png # save as pajek format # see also https://networkx.github.io/documentation/networkx-1.9/reference/readwrite.html ordmap tasks.yml tasks.net --save_as pajek
以下のような図や有向グラフを表したファイルが出力されます。
*vertices 8 1 "write product code" 0.0 0.0 ellipse 2 "fix design" 0.0 0.0 ellipse 3 "choose programing language" 0.0 0.0 ellipse 4 "request for budget(ringi)" 0.0 0.0 ellipse 5 "make a mock-up" 0.0 0.0 ellipse 6 releace 0.0 0.0 ellipse 7 "code review" 0.0 0.0 ellipse 8 "choose programming language" 0.0 0.0 ellipse *arcs 1 2 1.0 1 3 1.0 1 4 1.0 1 5 1.0 5 8 1.0 6 1 1.0 6 7 1.0
「このタスクの前にこのタスク」という関係を枝で繋いでいるだけではなく、「Cの前にB」「Bの前にA」「Cの前にA」という関係のときに「A→B→C」という関係まで簡略化されます(A→Cの枝が省略されます)。要するに、半順序集合のハッセ図をプロットしています。
この作業をtransitive reduction(推移簡約)というそうです。Pythonのグラフ理論を扱うライブラリのNetworkXでは開発中のver2.0に実装されていたので、それを参考に実装しました。
また、NetworkX(と裏で動いているmatplotlib)でUTF-8をプロットする方法が案外面倒なようなので、いまのところ日本語を入れると文字化けするし、ハッセ図をそれなりによくプロットする方法が分からなかったので図示はかなり酷いと思います。
ただ、うまくいけば分析基盤周りのバッチ処理(このデータの前にこのデータを用意しなきゃいけないとかややこしいですよね?)を整理する際も、同じような発想でできるんじゃないかなと妄想しています。もうあるのかもしれないですけど。
順序集合(Ord型)で仕事のロードマップ(Loadmap)を作るという意味でordmapという名前にしたのですが、Haskellじゃなくなったので微妙かもしれません。
【Python】urllibでマルチバイト文字のURLのhttps通信が失敗する
サラリーマンたるもの、日々の情報収集は欠かせません。
そのため、気になる業界ニュースをチャットに通知するクローラーを実装して使っているのですが、度々未知のエラーが出てしまいます。
叩いたら粉まみれ。PCデポ決算修正の内容とは https://t.co/9HEJywe6Fp pic.twitter.com/ja9YyK96ps
— 株の教科書.com (@kabunokyoukasyo) June 5, 2017
今朝は、こちらのニュースをクローリングしようとして、
from urllib import request request.urlopen('https://xn--u9j460nu9a58aw75c.com')
すると、以下のようなエラーが出てしまっていました。
CertificateError: hostname '株の教科書.com' doesn't match either of 'xn--u9j460nu9a58aw75c.com', 'www.xn--u9j460nu9a58aw75c.com'
利用しているPythonのバージョンは3.6.1です。
$ python3 -V Python 3.6.1
ここで2点可能性があるのですが、
- 証明書の認証に失敗している
- マルチバイト文字のURLの比較で失敗している
requests
ライブラリを利用した場合はエラーが出ないため、2. の可能性が濃厚です。
import requests requests.get('https://xn--u9j460nu9a58aw75c.com')
暫定的な対処
18.2. ssl — ソケットオブジェクトに対する TLS/SSL ラッパー — Python 3.6.1 ドキュメント
ssl.match_hostname(cert, hostname)(原文)
(SSLSocket.getpeercert() が返してきたようなデコードされたフォーマットの) cert が、与えられた hostname に合致するかを検証します。HTTPS サーバの身元をチェックするために適用されるルールは RFC 2818, RFC 6125 で概説されているものです。HTTPS に加え、この関数は他の SSL ベースのプロトコル、例えば FTPS, IMAPS, POPS などのサーバの身元をチェックするのに相応しいはずです。
失敗すれば CertificateError が送出されます。成功すれば、この関数は何も返しません:
今回はアクセスするURLが安全なものだとわかっているので、こちらのページに従い「証明書のチェックを行わない」という設定をして、一時的な対処を行いました。ただし、いろいろとセキュリティの問題が出てきそうなので今後はこの設定は使いたくありません。
import ssl from urllib import request ssl._create_default_https_context = ssl._create_unverified_context request.urlopen('https://xn--u9j460nu9a58aw75c.com')
TODO::
urllib
ライブラリのエラーが出ている箇所のコードをチェックする。- バージョンアップでの対処やイシューが出ているかどうかを調べる。
【情報検索】文章スコアのTF-IDFとBM25についてポインタを残しておく
OSSの検索エンジンであるSolr/Luceneの勉強会に行っていました。
この中の発表『Solrで多様なランキングモデルを活用するためのプラグイン開発』で、
- SimilarityにはTF-IDFとBM25の二種類あり、Solr6からはBM25がデフォルトになっている
- SolrのTF-IDFは、同じ単語が大量に出てきた際にスコアが極端に大きくならないように、TFが補正されている(√がかかっている)
という話があり、私は情報検索については不勉強なので、BM25は初めて聞く単語でした。
特徴
[改訂第3版]Apache Solr入門には次のように書かれています。271ページからの引用です。
また、こちらのブログには次のように書かれています。また、『Information Retrieval: Imple- menting and Evaluating Search Engines』という教科書に詳しく解説されているという記述があります。
BM25って何? という質問には「文書長正規化したTF-IDF」と答えるようにしており,経験的に性能が良いことが知られている,という情報を加えれば使う分には十分だと思っている.
ただBM25を教科書で見かけると「背景には確率的情報検索てものがあってな」という記述を何度か見かけるし,一応検索をやってますというような人間がBM25が生まれた背景や,その背景とされる確率的情報検索について知りません,というわけにもいかない.
アプリケーションとして利用するには、とりあえずこのことを把握しておけば良さそうです。ただ、もしきちんと理解したいなら、鈍器のような本を読まなきゃいけなさそうです。
Python実装
文章の特徴量というと、検索エンジンだけでなく、データマイニング方面での実装も気になりますね。
ただし、機械学習や統計処理で使うライブラリでは、scikit-learn
ではTfIdfVectorizer
のような形では実装されていませんでした。ただし、以下のライブラリを代わりに作成した方がいるようですね。
トピックモデル用のライブラリgensim
では使われてるようですね。
ただ、テキストマイニングでは統計モデルの特徴量としてTF-IDFを使うので、「同じ単語が大量に出てきた際にスコアが極端に大きくならないようにTFを補正したり、BM25を利用する」ようなモチベーションはあるのでしょうか?
参考文献
こちらの本を引用しています。
[改訂第3版]Apache Solr入門――オープンソース全文検索エンジン (Software Design plus)
- 作者: 打田智子,大須賀稔,大杉直也,西潟一生,西本順平,平賀一昭,株式会社ロンウイット,株式会社リクルートテクノロジーズ
- 出版社/メーカー: 技術評論社
- 発売日: 2017/04/27
- メディア: 大型本
- この商品を含むブログを見る
【本】最近読んでいる本(特に不動産関連)
最近はあまり本を読んでいませんが、一応何冊かは読んだので。
テキストマイニングを使う技術/作る技術(那須川哲哉)
最近、業務でテキストマイニングで業務支援を行う案件にアサインされており、ゴリゴリコードを書くことになりそうだったので読んでいます。
社内の研究部署の方から「IBMの那須川さんの論文は読んでおくといいよ」と紹介いただいたのがきっかけです(日本語の論文でよかった!)。
エキスパートの素顔:第13回 那須川 哲哉 | IBM ソリューション ブログ
世界的にも有名な研究者である那須川さんのデータ分析を間近で見ているのですが、何といいますか、分析そのものが本当に「エレガント」なのです。決して難しいことをやっているようには見えないのですが、とにかく驚くような結果を出すのです。例えば、データ分析を通し、コールセンターのエージェントの方の質を見抜いてしまう、製品の不具合を世に出る前に発見してしまう。また、研究会の活動のひとつとして最近取り組んでいるのが、グルメサイトにランキングされない美味しい日本酒のお店探しです。ソーシャルメディアを分析した結果を、実際に皆で出かけては「確かめる」のですが、本当に有名ではないがすごいお店に行き着くのです。
いろいろ検索している中でこの紹介を見て、「これはエンジニアやデータ分析者として信頼できる」と思って本も買いました。さすがに紹介されている事例はそのまま適用できそうにありませんが、限られた精度のデータの中で、いかに実務に役立つ分析を行うのかというハックの仕方は勉強になります。
テキストマイニングを使う技術/作る技術―基礎技術と適用事例から導く本質と活用法
- 作者: 那須川哲哉
- 出版社/メーカー: 東京電機大学出版局
- 発売日: 2006/11
- メディア: 単行本
- 購入: 4人 クリック: 146回
- この商品を含むブログ (11件) を見る
不動産格差(長嶋修)
@fds_infoで引っかかって気になって購入。
不動産コンサルタントの長嶋修さんの新刊で、今〜少し先の不動産の状況が概観できる本です。本の内容については以下のブログを参考にしてください。
特に印象に残った文章がこれです。ITエンジニアとしても、それぞれのドメインにおいて以下のような意見には耳を貸す必要があります。ビッグデータだのAIだの言われても、元になるデータが不十分では限界があるという話です。
日本で行われているこうした取り組み(←不動産テックのこと)には限界があります。というのは、日本で行う価格推定の根拠となるのは、国の成約価格情報を利用してはいるものの、全体の一部に過ぎず、主にインターネット上に出ている物件情報をロボットでクロールしてかき集めたものだからです。つまり、もともと不透明な価格情報を加工しているに過ぎません。(中略)
不動産総合データベースが本格稼働すれば、こうした課題も解消されます。データベースを利用できるのは、当初は宅建業者だけの予定ですが、国土交通省は民間への情報公開を見据えています。
- 作者: 長嶋修
- 出版社/メーカー: 日本経済新聞出版社
- 発売日: 2017/05/12
- メディア: 新書
- この商品を含むブログを見る
お客さま、そのクレームにはお応えできません!(三浦展)
これも同じく不動産ネタ。一応小説の体は取っているものの、不動産管理業者のあるあるネタをまとめた事例集みたいな感じのユニークで面白い本でした。
【書評】お客さま、そのクレームにはお応えできません!|不動産投資の健美家(けんびや)
テーマごとに一人の問題入居者が紹介されるのではない。それぞれに複数人、多い章(特にクレーマーたち)では数十人のトラブル事例がゾロゾロと出てくるのだから、驚く。現場のスタッフたちの苦労が偲ばれるというものだ。
また、本書には、不動産賃貸業の第一線で活躍するプロたちの頭の中や、トラブルを最小限で食い止めるためのノウハウを知ることができるという面白さもある。
お客さま、そのクレームにはお応えできません! [小説]不動産屋店長・滝山玲子の事件簿 (知恵の森文庫)
- 作者: 三浦展
- 出版社/メーカー: 光文社
- 発売日: 2017/03/09
- メディア: 文庫
- この商品を含むブログを見る
ブロックチェーン入門(森川夢佑斗)
さすがにそろそろブロックチェーンを無視し続けることはできないなと思ってとりあえず本を読みました。
- 作者: 森川夢佑斗
- 出版社/メーカー: ベストセラーズ
- 発売日: 2017/05/11
- メディア: Kindle版
- この商品を含むブログを見る
純粋関数型データ構造(Chris Okasaki)
関数型言語界隈やデータ構造界隈(どちらも怖いね!)で非常に評判が良い本です。
私は最近Haskellを読み書きできるようになり、「変数って全部イミュータブルでいいんだ」「Rubyの変数に全てfreezeして回る病」にかかってしまっていたのですが、少なくとも効率のいいデータ構造が必要だということは分かりました。
ところが、私は大学でもきちんといわゆる『アルゴリズムとデータ構造』の分野を学んだことが無いためか、逆にそちらの記述で詰まるところが多く、一旦この本を読むことを諦め、はてなの人が薦めてたCouseraのコースを勉強しています。
- 作者: Chris Okasaki,稲葉一浩,遠藤侑介
- 出版社/メーカー: KADOKAWA
- 発売日: 2017/04/28
- メディア: 単行本
- この商品を含むブログを見る
【Python】辞書のキーにデフォルト値をセットする
最近Pythonで自然言語処理をしていて、複数のライブラリを利用していると、どうしてもリストや辞書のややこしい変換が増えてきます。
categories = ['サーバル', 'かばん', 'サーバル'] lines = [ ['ここ', 'は', 'さばんな', 'ちほー'], ['食べ', 'ない', 'で', 'ください'], ['すっごーい!'] ]
これを、キャラクターごとに利用している単語を集計したいと思います。具体的には、以下のような辞書に変換したいとします。
{ 'サーバル': ['ここ', 'は', 'さばんな', 'ちほー', 'すっごーい!'], 'かばん': ['食べ', 'ない', 'で', 'ください'] }
Rubyであれば、nilガードを使って、サクッとハッシュの値を初期化すると思います。
# Ruby categories.zip(lines).each_with_object({}) do |(c, l), hash| hash[c] ||= [] hash[c].concat(l) end
ところが、Pythonで同じことをやろうとすると、「キーが存在しないときに初期化する」という処理で、どうしても冗長になってしまいます。
result = {} for c. l in zip(catagories, lines): if not c in result: result[c] = [] result[c] += l
こんなときは、collections.defaultdict
を使うと良さそうです。指定の型のデフォルト値(この場合は空のリスト)で初期化した値を辞書のキーに持たせることができます。
from collections import defaultdict result = defaultdict(list) for c, l in zip(catagories, lines): result[c] += l
厳密にはdict型ではないものの、defaultdictはdict型のサブクラスで、メソッドもほぼ共通しています。
参考:
8.3. collections — コンテナデータ型 — Python 3.6.1 ドキュメント
このような「オブジェクトの操作に向いているデータ型を使おう」といった感覚は、ケント・ベックのSmalltalk本に詳しく書かれていました。
言語はSmalltalkですが、Pythonでもよく使われるSet型についての解説(値の重複チェックはオブジェクトにまかせてしまおう!)もあり、オブジェクトの操作の感覚をつかむのに勉強になりました。
ケント・ベックのSmalltalkベストプラクティス・パターン―シンプル・デザインへの宝石集
- 作者: ケントベック,Kent Beck,梅沢真史,皆川誠,小黒直樹,森島みどり
- 出版社/メーカー: ピアソンエデュケーション
- 発売日: 2003/03
- メディア: 単行本
- 購入: 7人 クリック: 94回
- この商品を含むブログ (55件) を見る