極大２部クリーク列挙アルゴリズムの実装とビジネスキャリア形成支援への応用

2006/02/10

谷研究室 重田 琴美

018/25

目次

１：研究目的

２：極大２部クリーク

３：対象データとなる求人情報

４：プログラム実験の概要

５：考察

018/25

目次

１：研究目的

２：極大２部クリーク

３：対象データとなる求人情報

４：プログラム実験の概要

５：考察

018/25

研究動機

転職はなぜする？

キャリアアップを計る為

今の勤務形態への不満

今のキャリアからどんな転職先が

あるの？

１：研究目的

もっと条件の良い職業に

転職するには今のキャリアと何か必要なものがあるのではないか？

018/25

データマイニング

求人データ

求人データの中の

有益なデータを発見！

キャリアと求人職種の関係を

知りたい

データマイニング法

１：研究目的

018/25

目次

１：研究目的

２：極大２部クリーク

３：対象データとなる求人情報

４：プログラム実験の概要

５：考察

018/25

グラフ理論

グラフ理論の基礎 ー ２部グラフ

２：極大2部クリーク

018/25

グラフ理論

グラフ理論の基礎 ー ２部クリーク

２：極大2部クリーク

018/25

グラフ理論

グラフ理論の基礎 ー ２部クリーク

２：極大2部クリーク

018/25

グラフ理論

グラフ理論の基礎 ー 極大２部クリーク

２：極大2部クリーク

18/25

客Ａ

客Ｂ

客Ｃ

客Ｄ

ビール

紙おむつ

たばこ

客

・

・

・

・

・

・

・

・

・

・

・

・

商品

２：極大2部クリーク

極大2部クリークとデータマイニング

18/25

客Ａ

客Ｂ

客Ｃ

客Ｄ

ビール

紙おむつ

たばこ

客

・

・

・

・

・

・

・

・

・

・

・

・

商品

２：極大2部クリーク

極大2部クリークとデータマイニング

18/25

目次

１：研究目的

２：極大２部クリーク

３：対象データとなる求人情報

４：プログラム実験の概要

５：考察

18/25

求人情報

年齢幅：

最終学歴：

年収幅：

経験していると望ましい 業界・職種
（最大３つまで）：

資格：

求人データＡ

参考資料：

キャリアデザインセンター

３：対象データとなる求人情報

18/25

１９歳

求人データB

求人データC

求人データA

１８歳

２０歳

２１歳

２２歳

年齢幅

三百万円

四百万円

五百万円

六百万円

年収幅

高卒

短大卒

専門卒

大卒

最終学歴

基本情報

秘書

簿記

資格

高卒

短大卒

専門卒

大卒

最終学歴

業界：情報

職種：SE

経験していると

望ましい職種

業界：情報

職種：PM

など･･･

など･･･

・・・

・・・

・

・

・

求人情報の２部グラフ化

３：対象データとなる求人情報

18/25

求人データ

求人条件

目次

１：研究目的

２：極大２部クリーク

３：対象データとなる求人情報

４：プログラム実験の概要

５：考察

18/25

極大二部クリーク列挙アルゴリズムの紹介

国立情報学研究所：宇野毅明 先生

『大規模2 部グラフに対する

極大クリーク列挙アルゴリズムの改良と実装』(2003)

４：プログラム実験の概要

極大２部クリーク一つあたり、

計算量

列挙により、複数の極大２部クリークを比べられる

列挙 ： 一つ一つとりあげて出力する

18/25

極大２部クリーク列挙アルゴリズム

3

1

4

3

5

3

2

6

深さ優先探索により，極大２部クリークを列挙していく

3

1

4

3

3

2

3

1

4

3

3

2

3

1

4

3

3

2

3

4

6

3

4

3

5

3

2

3

4

3

5

3

2

3

4

5

6

3

4

3

5

3

2

3

4

5

6

４：プログラム実験の概要

18/25

全く同じ極大２部クリーク

を出力しない工夫

ある条件を満たさなければ

列挙しない

入力データ

入力ファイル ：

求人データ数：６０１件

４：プログラム実験の概要

18/25

プログラムの概要

Excelデータから一行ごとにデータを取り出し、

二部グラフ化

宇野助教授のアルゴリズムを用いて

二部グラフから極大２部クリークを列挙していく

開発言語 ：

４：プログラム実験の概要

プログラムの設計図 ： クラス図

18/25

実行結果

４：プログラム実験の概要

・

・

・

18/25

ＣＰＵ：Ｐｅｎｔｉｕｍ４ ３．２ＧＨｚ

メモリ：1GByte

実行時間：2分56秒

１５１２９の組み合わせ！！

目次

１：研究目的

２：極大２部クリーク

３：対象データとなる求人情報

４：プログラム実験の概要

５：考察

18/25

実験結果考察

年齢・年収の組み合わせが多い。
→年齢・年収のデータには幅があった為。

同じ業界・職種を経験していて、ある一定の年齢幅だと、似たような年収結果となった。
→

２７、２８才が１番求人条件で多い
→転職しやすい年齢が２７、２８歳だと分かる。

５：考察

ある年齢までに、どのような業界・職種を経験しておけば、高収入になれるのかが分かる。

出力結果で、年収・年齢・経験職種が揃ったデータが最も価値があるように思える。

18/25

今後の課題・活用例

活用例

出力結果から現代の採用状況・傾向が分かる

出力された求人データの傾向を参考に自分のキャリアアップを計る事が出来る

５：考察

18/25

出て来たデータが多すぎる（１５１２９件）
→出てきた結果に対してさらなるデータマイニングをする

今後の課題

お わ り

お疲れ様でした

ありがとうございました

18/25

付録！！
極大2部クリーク列挙アルゴリズム
の詳細！

極大２部クリーク列挙アルゴリズム

極大２部クリーク列挙アルゴリズム

極大２部クリーク列挙アルゴリズム

極大２部クリーク列挙アルゴリズム

極大２部クリーク列挙アルゴリズム

極大２部クリーク列挙アルゴリズム

極大２部クリーク列挙アルゴリズム

極大２部クリーク列挙アルゴリズム

極大２部クリーク列挙アルゴリズム

極大２部クリーク列挙アルゴリズム

3

1

4

3

5

3

2

6

極大2部クリーク列挙アルゴリズム

3

1

4

3

5

3

2

6

3

1

4

3

3

2

3

1

4

3

3

2

3

1

4

3

3

2

極大2部クリーク列挙アルゴリズム

3

1

4

3

5

3

2

6

3

1

4

3

3

2

3

1

4

3

3

2

3

1

4

3

3

2

極大2部クリーク列挙アルゴリズム

3

1

4

3

5

3

2

6

3

1

4

3

3

2

3

1

4

3

3

2

3

1

4

3

3

2

3

4

6

極大2部クリーク列挙アルゴリズム

3

1

4

3

5

3

2

6

3

1

4

3

3

2

3

1

4

3

3

2

3

1

4

3

3

2

3

4

6

極大2部クリーク列挙アルゴリズム

3

1

4

3

5

3

2

6

3

1

4

3

3

2

3

1

4

3

3

2

3

1

4

3

3

2

3

4

6

3

4

3

5

3

2

極大2部クリーク列挙アルゴリズム

3

1

4

3

5

3

2

6

3

1

4

3

3

2

3

1

4

3

3

2

3

1

4

3

3

2

3

4

6

3

4

3

5

3

2

極大2部クリーク列挙アルゴリズム

3

1

4

3

5

3

2

6

3

1

4

3

3

2

3

1

4

3

3

2

3

1

4

3

3

2

3

4

6

3

4

3

5

3

2

3

4

3

5

3

2

極大2部クリーク列挙アルゴリズム

3

1

4

3

5

3

2

6

3

1

4

3

3

2

3

1

4

3

3

2

3

1

4

3

3

2

3

4

6

3

4

3

5

3

2

3

4

3

5

3

2

3

4

5

6

極大2部クリーク列挙アルゴリズム

3

1

4

3

5

3

2

6

3

1

4

3

3

2

3

1

4

3

3

2

3

1

4

3

3

2

3

4

6

3

4

3

5

3

2

3

4

3

5

3

2

3

4

5

6

極大2部クリーク列挙アルゴリズム

3

1

4

3

5

3

2

6

3

1

4

3

3

2

3

1

4

3

3

2

3

1

4

3

3

2

3

4

6

3

4

3

5

3

2

3

4

3

5

3

2

3

4

5

6

3

4

3

5

3

2

3

4

5

6

１では研究目的をまずお話して、

２で今回アルゴリズムで使用した極大２部クリークの説明をし、

３で対象データとなる求人情報をどのように集め、そのデータをどのように２部グラフにしたかをお話します。

４でプログラムについて簡単にお話し、実装したものをお見せしたいと思います。

最後に５で、今回の実験の考察をして終わりです。

まずは最初に１の研究目的です。

近年は、転職をするという事が当たり前の時代です。

厚生労働省の調査によると、転職する理由は

この２つが大部分を占めています。

１・・・・・

２・・・・・

しかし転職サイト等を見てみると、数ある仕事から仕事を探す時、勤務地や業界・職種等の、仕事の条件でのしぼり込みで探すところがほとんどです。

しぼり込みではなくて、

「今のキャリアでどんな転職先があるのか」や

「条件の良い仕事に就く為のプラスアルファ的な条件・キャリア」

と考えました。

膨大な求人情報からキャリアと就ける職業の関係性が何かわからないだろうか？

さて、ここで膨大なデータをグループ化したり、抽出したりし、有益なデータを発見する事をデータマイニングといいます。

データマイニング法にも様々な種類があります。

今回はその中のひとつ、極大２部クリーク列挙アルゴリズムを使ったデータマイニング法により、求人データの中から、転職先とキャリアの関係を取り出す事を目的とします。

なぜ、数あるデータマイニング法からこのマイニング法を使ったのかの説明は次の章でご説明します。

ではまず極大２部クリークとは何か？という説明をして、

極大２部クリークを使ったデータマイニングの特徴をお話したいと思います。

まずはグラフ理論の２部グラフを説明します。

グラフGの頂点V、辺Eとした時に、

グラフ中の頂点集合VをV1、V2に分けて、任意のV1の頂点同士の組、および任意のV2の頂点同士の組に辺を持たないグラフを２部グラフといいます。

次にに２部クリークです。

２部グラフで、V1の部分集合をS1、V2の部分集合をS2とした時に、任意のS１、任意のS２に辺があるグラフを２部クリークといいます。

図の様なv2v3v5も２部クリークですし、

この様なv2v3v4v5もs1とs2の間に全て辺を持つのでこれも２部クリークです。

ではいよいよ極大２部クリークです。

極大２部クリークとは２部クリークで、他の２部クリークに完全に含まれない２部クリークの事をいいます。

図の様なv2v3v4v5が極大２部クリークです。

他の２部クリークを含んではいますが、含まれてはいません。

では実際の例を使って、極大２部クリークを使ったデータマイニング法の特徴をお話します。

あるスーパーで客がなにを買ったのか、というデータに対し、

極大２部クリークを使ったデータマイニングをした場合はどのような結果が得られるのでしょうか。

まず、データを２部グラフ化します。

客をＶ１の頂点、商品をＶ２の頂点に振り分け、客とその客が買った商品との間に、辺を持たせ２部グラフとします。

ここから極大２部クリークを取り出すと、この図のような極大２部クリークが出てきました。

ここから何が分かるかというと、ビールと紙おむつとたばこをセットで買う客がいる、という事が分かります。

このセットで買う客が複数いるのならば、

ビールコーナーの横にたばこ販売の案内を出したりすると、売り上げが上がるかもしれない、という事が分かったります。

このように、極大２部クリークを抜き出す事により、そのデータの傾向や特徴を発見出来る事が極大二部クリークを用いたデータマイニングの特徴です。

では本研究の対象となるデータはどの様なものかご説明します。

今回、株式会社キャリアデザインセンターの求人データを参考に、データを集めました。

集めた内容は、募集している仕事の年齢幅、最終学歴、年収幅、経験していると望ましい業界・職種を最大３つまで、と資格です。

このデータを２部グラフにすると、

このように２部グラフ化します。

求人データそのものをｖ１の頂点とし、求人条件をｖ２の頂点とします。

求人データとその求人データの中のこの職業に就く為に必要とされる条件とに辺を持たせます。

また、求人データには、募集年齢と年収は幅があるので、１歳ごと、１００万ごとに辺を持たせました。

４では極大２部クリークを使ったアルゴリズムの紹介をしてから、実際の実装結果をお見せします。

今回使用したアルゴリズムは

国立情報学研究所の宇野助教授の「大規模２部グラフに対する極大クリーク列挙アルゴリズム」を応用しました。

このアルゴリズムは極大２部クリークを列挙する事によって、複数の極大２部クリークを比べられる、という特徴があります。

今回は時間がないので、簡単にアルゴリズムの説明をしたいと思います。

列挙方法として、深さ優先探索で、極大２部クリークを列挙していきます。

その際、ある条件を満たさないグラフは列挙されない、などと、同じ極大２部クリークが複数列挙されない工夫もされてれいます。

では、いよいよプログラムの実行の発表に入ります。

実際の入力データです。

このようにエクセルファイルで手入力により作成しました。

今回集めたデータ数は６０１件です。

今回の開発言語はａｖａを使いました。

エクセルデータから１行ごとにデータを取り出して２部グラフにし、宇野助教授

のアルゴリズムを使って２部グラフから極大２部クリークを列挙します。

右の図はＪａｖａを使ったプログラムの設計図です。

職業と条件で２部グラフを構成し、それに

極大２部クリークでデータマイニングをする、という構成になっています。

では次にプログラム実行結果をお見せします。

このように実行結果が現れました。

データ数６０１に対し、３９２の条件があり、

全部で１５１２９の組み合わせが列挙されました。

今回の実験の考察に入ります。

今後の課題

Ｖ１側の数に下限・上限を与えてみたが、それでも５０００件程にしか絞れず、

もっと良い絞り込み条件はないだろうか

次に、極大２部クリーク列挙アルゴリズムで使われる記号N(S)について説明します。

N(s)とはSの任意の頂点と隣接する頂点の集合を指します。

例をみてみましょう。

v4をSとしたときに、v4と隣接する頂点はv1v2v3です。

N({v4})はv1v2v3です。

同じ様にv4v5をSとした時はN({v4v5})=v2v3です。

X(i,S)は極大２部クリークを求めるアルゴリズムです。

このSは２部クリークを指します。

Sに値を入れると、極大２部クリークが求まります。

i の説明は後程します。

まず、始点のSはV２側の頂点とします。

この図だとv4でもv5でもv6でも良いのですが、今はv5を考えてみましょう。

Sを v5とします。

ここでv5の隣接した頂点v２v３を加えます。

さらにそのv２v３と隣接するv４v５を加えます。

これまでで、グラフの極大２部クリークがもとまります。

さらにここで5より大きい添字を削除します。

これが、添字5より小さい頂点からなる極大２部クリークです。

これは、 添字iiまでの頂点を使った極大２部クリーク、i極大2部クリークを求めるアルゴリズムです。

これから説明する極大２部クリーク列挙を使ったデータマイニングのアルゴリズムはこのi 極大２部クリークを求めるアルゴリズムのSになりうる２部クリークを求めていく事を繰り返して、このアルゴリズムを適用し)極大２部クリークを求めていくアルゴリズムである、という事を頭において説明を聞いて下さい。

次に極大２部クリーク列挙アルゴリズムについて説明します。

先程のアルゴリズムのSに入るのはS2の最小添字とします。

こうして２部極大クリークSi を求めます。

ここで、次のSに入る２部クリークの候補を決めます。

この候補を作れる可能性があるのがJのリストです。

Jのリストの条件は添え字がi以上で、S_1の全てではない頂点と隣接している

(全てと隣接しているものはクリークに含まれるから)頂点の添え字です。

Si からこのJリストの最大の添え字の一つ前までの添え字を削除します。

そこへ

Jリストの最大添え字の頂点を加え、この頂点と隣接しない頂点を削除します。

この時、Jのリストから加えた添え字を削除します。

こうして出来た２部クリークをS'とします。ここで２部極大クリークであるか、アルゴリズムに当てはめて判定します。これは２度同じ２部極大クリークを列挙しない為に行ないます。

２部極大クリークであれば、再帰にかける、という作業をしていくと、

２部極大クリークが求まっていきます。

ではこのグラフを例に実際に列挙する様子を見ていきます。

注意する点は同じ極大２部クリークを２度列挙しない様にする点です。

まず、V2側の頂点を入れて極大２部クリークを求めます。

１番小さいものから入れていきます。

v４ を入れ、極大２部クリークを求めます。

では、実際の例を見て説明していきましょう。

列挙するときに、同じものを２度以上出力しないようにします。

では、実際の例を見て説明していきましょう。

列挙するときに、同じものを２度以上出力しないようにします。

では、実際の例を見て説明していきましょう。

列挙するときに、同じものを２度以上出力しないようにします。

では、実際の例を見て説明していきましょう。

列挙するときに、同じものを２度以上出力しないようにします。

では、実際の例を見て説明していきましょう。

列挙するときに、同じものを２度以上出力しないようにします。

では、実際の例を見て説明していきましょう。

列挙するときに、同じものを２度以上出力しないようにします。

では、実際の例を見て説明していきましょう。

列挙するときに、同じものを２度以上出力しないようにします。

では、実際の例を見て説明していきましょう。

列挙するときに、同じものを２度以上出力しないようにします。

極大２部クリークを用いたビジネスキャリア形成支援プログラムの実装・有効性の調査

重田 琴美

2006-01-31T19:31:26

太 福澤

太 福澤