LostMemories

後輩から、縦型探索をするために有利なグラフの標準形について教えてもらいました。今の研究テーマと少し違っているので、忘れてしまう可能性大。せっかくなので、ここにメモしておきます。

ここに、今から述べるグラフの例を示します。この図に書かれた2つのグラフは、パッと見れば分かると思いますが同じものです。ですが、計算機でグラフを探索する場合は、このような全体像が分かっているわけがないので、あるノードから順番に探索を行っていくことになります。左のグラフでは「B」と書かれたノード、右のグラフでは「A」と書かれたノードから始めることにします。

ここで注意しておきたいのが、グラフの探索方法が縦型であるということ。左側では、「B」→「A」→（「B」）→「C」と探索していくのに対し、右側では「A」→「B」→「C」と探索することになります。縦型探索を行う場合、なるべくならばロールバック（つまり、すでに探索したノードに戻る作業）は発生しない方がいいので、右側のグラフを標準形としたいことになります。

さて、これまでの話を踏まえた上で、標準形を選び出すための表記方法を述べます。上図のように、探索する順番がすでに最後まで分かっていて、それをノードの番号とします。その上で、１つの新しいノードに到達する探索工程を１単位と定めます。１単位での表記法は、「（ノード番号）（全体のノード数 - そのノードとつながっている探索済みのノード番号）」です。このように表記し、昇順に並べたときに最も先頭に来るものが標準形とします。左のグラフでは「22 32」、右のグラフでは「22 31」となり、右のグラフが標準形になります。

データマイニングツールWEKAを利用していると、たまにメモリ不足で不正終了してしまうことがあります。これは、WEKAに割り当てられているヒープ領域（メモリの大きさ）が十分でないために起こる現象です。これを回避するためには、ヒープ領域を十分に割り当ててやる必要があります。

これ以降は、Windows環境（GUI）を前提にします。他のOS向けのWEKAを利用している場合は、普通のjavaアプリケーションの時と同様に、-Xmxオプションでヒープ領域を大きめに指定してください。

Windows上でWEKAのヒープ領域を大きくするには、設定ファイルの設定を変更する方が簡単です。インストールされているフォルダ（一般的には「C:\Program Files\Weka-○-○」）を開き、RunWeka.iniというファイルをテキストエディタで開きます。その中に、maxheapという項目がありますので、その値を大きくしてください。（例えば、512mなど）

その後、プログラムを起動させることで改善されると思います。

WEKAでは、非常に多彩なマイニングアルゴリズムを試すことができます。ここでは、WEKAを用いて多層パーセプトロン（multilayer perceptron）を試す方法を示します。

まず、WEKAを起動させ、「Explorer」を選択します。するとExplorerが起動するので、「Open file...」を選択し、訓練データを選択します。その後、「Classify」タブを選択→「Choose」を選択して現れる分類器の「functions」→「MultilayerPerceptron」を選択します。

「Test Options」では、「Cross-validation」（交差検定）を選択します。Foldsでは、推定する回数（訓練データの分割数）を指定できます。また、多層パーセプトロンの出力属性は、「Start」の上のプルダウンメニューで選択することが可能です。設定し終わったら「Start」をクリックして、モデルを生成します。このモデル生成には時間がかかる場合があります。

モデルを生成したら、今度はテストデータを設定します。「Test options」で「Supplied test set」を選択し、「Set」ボタンをクリックしてファイルを指定します。もし複数のファイルに分かれている場合は、「Set」でそれぞれ指定することで、同じデータファイルのように扱うことができます。

テストファイルを指定したら、「Result list」の項目を選択して右クリックしてください。現れたメニューの中から、「Re-evaluate model on current test set」を選択します。すると、テストを行った結果が右側に現れます。

データマイニングツールWEKAに与えるデータは、CSV形式のほかにarff形式のファイルを指定することもできます。（むしろ、こちらのほうがよく対応しています。）CSV形式とよく似ていますが、データの情報を追加できる点が違います。

まず、arff形式の具体的なサンプルを示したほうがイメージしやすいと思うので、以下に例を示します。

@RELATION iris

@ATTRIBUTE sepallength  NUMERIC
@ATTRIBUTE sepalwidth   NUMERIC
@ATTRIBUTE petallength  NUMERIC
@ATTRIBUTE petalwidth   NUMERIC
@ATTRIBUTE class        {Iris-setosa,Iris-versicolor,Iris-virginica}

@DATA
5.1,3.5,1.4,0.2,Iris-setosa
4.9,3.0,1.4,0.2,Iris-setosa
4.7,3.2,1.3,0.2,Iris-setosa
4.6,3.1,1.5,0.2,Iris-setosa
5.0,3.6,1.4,0.2,Iris-setosa
5.4,3.9,1.7,0.4,Iris-setosa
4.6,3.4,1.4,0.3,Iris-setosa
5.0,3.4,1.5,0.2,Iris-setosa
4.4,2.9,1.4,0.2,Iris-setosa
4.9,3.1,1.5,0.1,Iris-setosa

この例は、ワイカオ大学のウェブページから引用したものです。実際のデータは、「@DATA」以降に書かれます。ちなみに、「@XXX」の部分は大文字と小文字を区別しません。

@relationには、データの名前を指定します。また、@attributeにはそれぞれの列のデータ形式と名前を指定します。フォーマットを以下に示します。

@relation <relation-name>
@attribute <attribute-name> <datatype>

<datatype>には、以下のデータ形式を指定します。

numeric （数字。つまり整数か実数）
<nominal-specification>　（有限の記号。例えば、YESとNOとか。）
string （文字列）
date [<date-format>]　（日時。<date-format>は省略可能。省略した場合は、"yyyy-MM-dd'T'HH:mm:ss"）

nominal-specificationは、中カッコ「{ }」で囲んで、コンマで区切ります。例は上記にある通りです。YESとNOなら、{YES,NO} といった感じです。

[web] Weka 3
[web] Attribute-Relation File Format

データマイニングを手早く利用したい人のために用意されたツールとして、WEKAというものがあります。cvs形式ファイルでデータを読み込み、準備されたマイニングスキーマで処理をさせることができます。

[web] WEKAの日本語情報
[web] Machine Learning Project（WEKAの本家）

WEKAはもともとニュージーランドの大学（ワイカト大学）で開発されているツールです。そのため、ダウンロードしてきてそのまま起動させると、英語のメニューが現れます。ちょっと使いづらいですが、我慢しましょう。（日本語パッチに期待。。。）

簡単な使い方については、「weka」で検索することでいろいろと出てきますが、とりあえず下のURLなんかが役に立つでしょう。

[web] How to use Weka tool box

続きを読む

信頼度・支持度と単純に書くと、選挙とかの候補者が関係してきそうですが、今回取り上げる用語はそういう意味では使いません。データマイニングでは、もう少し違った意味になります。

ここで説明する前に、もう少し前提を定義しておきます。「トランザクション」は、ある「アイテム」の組み合わせで構成される１つの単位です。「アイテム」は、データマイニングで知識発見をするための一番小さな単位で、具体的なオブジェクトになることがおおいです。「アイテム」の例として、お店のさまざまな商品（野菜とか果物とか）が当てはまります。この例では「トランザクション」は、１人のお客さんがかごに入れる商品になります。

さて、ここでX、Yをあるアイテムとします。信頼度とは、「X,Yを含むトランザクション数 / Xを含むトランザクション数 」になります。つまり、Xを含むならYも含まれる割合になります。

支持度は、「X,Yを含むトランザクション数 / 全トランザクション数 」です。これは単純に、全体でX,Yが現れる割合になります。

リフト値は、「X,Yを含むトランザクション数 / Yを含むトランザクション数 」です。これは、Xを前提としたときとしないときの、Yが出現する倍率となります。リフト値が１より大きいなら、Xを前提としたほうがYが出現する割合が多くなることを示します。

ちなみに信頼度(確信度)はConfidence、支持度はSupport、リフト値はLiftとも書かれます。