CourseraのMachine Learningコースで、ある課題に対してSubmitされた4万人分のコードを可視化したというブログ エントリーを紹介。
上のグラフではノードは各Submissionで、エッジが構文的に類似したノード間に引かれています。色はユニットテストに対する 成績に対応しています（赤色はすべてのテストにパス）。
どのように作成したのか
- We parsed each of 40,000 student submissions into an Abstract Syntax Tree (AST) data structure by adapting the parsing module from the Octave source code. ASTs allow us to capture the structure of each student's code while ignoring irrelevant information such as whitespace and comments (as well as, to some extent, variable names).
- We next computed the tree edit distance between every pair of unique trees, which counts the minimum number of edit operations (e.g., deletes, inserts, replaces) required to transform one tree into the other
- Reasoning that small edit distances between ASTs are meaningful while larger distances less so, we finally dropped edges whose edit distances were above a threshold and and used gephi to visualize the resulting graph.
- 4万人分のOctaveのソースコードをパースして抽象構文木（AST）というデータ構造に変換する。ASTにすることで、空白やコメント（や変数名）などの重要ではない情報を無視してソースコードの構造を捉える事ができる。
- 全てのペアについて、木構造の編集距離（一方の木構造を削除、挿入、置き換えをしてもう一方の木構造に変形したときの編集操作の最小回数）を計算。
- 編集距離が小さい場合は重要、大きい場合はあまり重要ではないと考え閾値以上のエッジをgephiを使って描画。
何に使えるか（使うと良いか）
いくつかアイデアがある模様。
- 問題に対する典型的なアプローチの発見
- 編集距離が近いエッジをクラスタリングすれば見つけられる
- よくある失敗とか同じ問題に対する複数の正解アプローチもわかる
まとめ
ソースコードの構文木の編集距離をグラフ化、結果をクラスタリングして問題に対する典型的なアプローチを発見するというアイデアは面白いと思いました。 より詳細な情報は論文等にあるようですので、そちらも参照してみてください。
