ACO型時系列パターン抽出法を用いたマーケティングデータの解析

ACO

型時系列パターン抽出法を用いた

マーケティングデータの解析

Analysis of marketing data

by using ACO-based pattern mining approach

坪井一晃

1∗

_篠田孝祐

1

_諏訪博彦

2

_栗原聡

1

Kazuaki Tsuboi

1

_{Shinoda Kosuke}

1

_{Hirohiko Suwa}

2

_{Satoshi Kurihara}

1

1

_{電気通信大学大学院情報システム学研究科}

1

_{Graduate School of Informatics Systems, The University of Electro-Communications}

2

_{奈良先端科学技術大学院大学情報科学研究科}

2

_{Graduate School of Information Science, Nara Institute of Science and Technology}

Abstract: It is important to understand various consumers ’needs and clarify the target of goods

and service in marketing. As information processing technology develops, as more various data of consumer’s purchase action could be collected and accumulated. And the technology which extract the consumer ’s real intention, we call consumer insight, from the collected and accumulated data is noted. In this study, we are developing an ACO-based pattern mining method which extracts frequent purchase pattern from the information of receipt data as a purchase result of consumers ’. We consider that consumer behavior is ambiguous and always changes because of influence of the fashion and season. Then we try to use Ant Colony Optimization (ACO) algorithm which is one of collective intelligence-based approach and the optimization method which modeled the behavior of ant seeking for food in nature. ACO algorithm is famous as a solution of a traveling salesman problem having high robustness and adaptability. Like ACO algorithm, we extract frequent pattern by adding and evaporating the pheromone to the virtual graph. And we analyze the marketing data for one year in the two store in Ebetsu city, Hokkaido by using ACO-based pattern mining approach. Two kinds of experiment is made about each of the store. One is to input data to 31 December 2013, the other is to input data to 30 June 2014. Each result of experiments can be visualized by Cytoscape. the data was offered by Joint Association Study Group of Management Science.

1

はじめに

企業は顧客に対してモノやサービスを提供すること で利益を得ている．従来は，マーケットシェアを確保 したり売上を増やしたりといった量的拡大というマー ケティング戦略によって，利益を追求してきた [1]．し かし，近年，消費者に対して付加価値を提供すること で適切な収益を確保する質的拡大というマーケティン グ戦略が重要視されるようになっている． この質的拡大という戦略を採用するためには，消費 者が求める付加価値を正確に見抜くことが必要であり， 消費者ニーズの的確な理解が求められる．しかし，消 ∗_{連絡先：電気通信大学大学院情報システム学研究科}       〒 182-8585 東京都調布市調布ヶ丘 1-5-1        E-mail: [email protected] 費者ニーズは消費者自身でも気が付いていないことが 多い．この潜在的な消費者ニーズを抽出するための手 法として，情報技術の発展を背景としてデータマイニ ングが挙げられる．情報技術の発展によって，多くの企 業がデータを容易に大量に収集・蓄積できるようになっ てきた．マーケティングの業界では，POS（Point Of Sales:販売時点）システムの導入が進められた．POS シ ステムは導入当初の目的は，精算時間の短縮や誤入力 の防止など，レジでの精算の効率化であった．しかし， 近年のさらなら情報技術の発展に伴い，受発注作業の 効率化，在庫管理などといったマーケティング戦略の 意思決定時の重要な情報源として利用されている．そ こで，課題となるのが，大量に収集・蓄積された情報か ら有用な知見を得ることである．情報から有益な知見 を得るための技術として，データマイニングが注目さ 人工知能学会研究会資料 SIG-KBS-B403-04

れている．本稿では，データマイニング技術に一つで あるパターンマイニングに注目し，実際のマーケティ ングデータから頻出する購買のパターンを抽出する． そこで，消費者の行動は流行や季節の変化といったも のに応じて常に変化していることを考慮する必要があ る．本稿では，変化に対して柔軟な適応能力を有するパ ターンマイニング技術を構築するために，群知能分野 の最適化手法である ACO(Ant Colony Optimization) アルゴリズム [7] に注目する．近年の数多くの研究か らデータマイニングと群知能の組み合わせの有用性が 実証されている [2]．そこで，ACO アルゴリズムに基 づくパターンマイニング手法を用いたマーケティング データの解析を行う．なお，本稿で解析対象としたデー タは経営科学系研究部会連合協議会主催，平成 26 年度 データ解析コンペティションで提供されたものである．

2

関連研究

大量のデータから頻出するパターンを抽出する手法 がパターンマイニングである．データベース上から頻 出するアイテムセットのパターンを抽出するためのア ルゴリズムとして Apriori アルゴリズム [3] が有名であ る．Apriori アルゴリズムは小さいアイテムの集合から 順に出現回数を数える幅優先探索である．あるアイテ ム集合が頻出とならない場合，その上位となるアイテ ム集合である，そのアイテムを含むより大きなアイテ ム集合について探索する必要がなくなる．このことよ り解の探索空間を減らしている．しかし，解の候補と なるアイテム集合が生成されるたびに出現回数を数え るため，全ての入力データベースを調べなければなら なくなる．そこで，入力データベースが膨大なものと なったときに，計算時間やメモリに問題が生じる．ま た，Apriori アルゴリズムでは，アイテムの時系列を考 慮していないといった問題が指摘された． そこで，データベース上から時系列を考慮したアイ テムのパターン抽出を行うために Apriori アルゴリズ ムを拡張した AprioriAll アルゴリズム [4] や，パターン 抽出にあたって時間制約などの条件をつけることで計 算処理の高速化を図った GSP アルゴリズム [5]，lattice （格子）という概念を用いて解の候補となるアイテム セットをグループ分割しそれぞれのグループをメモリ 上に納めることで計算処理の高速化を図った SPADE アルゴリズム [6] が提案されている．これらのアルゴ リズムは計算処理の高速化を図ったものであり，入力 データを一様に等しく参照している．しかし，マーケ ティングにおける消費者の行動を考えると，流行や季 節といったものに影響を受けて行動も変化するために， 消費者の行動の変化に柔軟に対応できないという問題 が生じる． そこで着目したのが群知能分野の ACO アルゴリズ ムである．既存のデータマイニング手法では，膨大な 計算コストを要したり実装が困難な状況において，実 際に解が得られる手法として群知能の分野のアルゴリ ズムを応用する研究が行われている．実際に，群知能分 野の ACO アルゴリズムをデータマイニングのクラス タリング手法に応用した AntMiner+アルゴリズム [8] は，分類結果がわかりやすい分類器でありながら精度 が高く動的で分散した環境にも適したものである． ACO アルゴリズムとは，自然界におけるアリの採餌 行動をモデル化したもので，最適化問題である巡回セー ルスマン問題に対する解法として提案された．ACO ア ルゴリズムでは，アリは通過した経路にフェロモンを 残すことと，アリはフェロモンの濃度が濃い経路を好 んだ経路選択をするというアリの行動を前提として考 える．この前提によって，アリが集団として行動する ごとに，最短経路を通過するアリが多くなり，最短経 路に残るフェロモンの濃度が濃くなる．一方，フェロ モンは気体であり，時間経過に伴い蒸発する．結果的 に，アリが通過する頻度が少ない経路のフェロモンの 濃度が薄くなる．残量するフェロモンの濃度が濃い経 路が，最短経路問題の解となる．ACO アルゴリズムの 特徴として，どのような環境に対しても解を生成する ことができる適応性や，環境の変化に対しても柔軟に 解を再探索できる頑健性が挙げられる． ACO アルゴリズムをパターンマイニングに応用し た研究として Tamaki ら [9] の研究がある．Tamaki ら は，センサが人の行動を読み取り反応することに着目 し，連続した人の行動からセンサの隣接関係を，ACO アルゴリズムを応用することで推定する研究を行って いる．ACO アルゴリズムを応用したことで，複数の人 が同時に行動した場合のノイズや，センサが故障や移 動といった環境の変化にも対応できる． このように，もともと最適化技術として提案された 群知能分野のアルゴリズムであるが，単純な行動ルー ルに基づいたエージェントの移動と環境に対するフェ ロモンの付加・蒸発を応用することで，柔軟なシステム の構築が達成できる．本研究においても，ACO アルゴ リズムが有する適応性や頑健性に着目し，ACO に基づ くパターンマイニング手法によるマーケティングデー タの解析を試みる．

3

ACO

に基づくパターンマイニン

グ手法

本研究では，小売店における消費者の購買結果を表 すレシートの情報から，頻出する購買パターンを抽出 する．本研究における頻出する購買パターンとは，一

度の会計において同時に購入される頻度が高い商品ン の組み合わせのことである．

3.1

入力データセット

提案アルゴリズムを適用するにあたって，入力デー タセットは消費者の購買結果を表すレシートの情報で ある．一枚のレシートに記載された商品名に着目し，ア ルゴリズムを適用する．また，レシートには購入され た時刻が記載されているため，この時系列順にレシー トの情報を逐次的に入力していく 1．ct,kはレシートを 表し，添え字 t は購入年月日を表し，添え字 k は購入年 月日 t におけるレシート番号を表す．なお，レシート番 号は購入年月日 t に出現したレシートに対して時系列 順に連番が割り振られている．siは商品名を表す．図 1 を例にすると，2014 年 1 月 1 日に出現した一番最初 のレシート c20140101,1では，商品 s1,s2，s3，s4が購入 されており，同日の次のレシート c20140101,2では，s5， s6，s7が購入されているといった情報である．ただし， 一枚のレシートの中に現れた同一商品の重複について 無視し，同一商品の購入個数に着目しない． 図 1: 図の挿入例.

3.2

ACO に基づくパターンマイニングアル

ゴリズム

ACO アルゴリズムは環境へのフェロモンの付加フ ェーズと蒸発フェーズから成り立つ．そこで，店舗に おける一日分のレシートの情報を読み込み，環境への フェロモンの付加フェーズを実行する．その後，環境 に残留するフェロモンに対して蒸発フェーズを実行す る．このフェロモンの付加フェーズと蒸発フェーズを 繰り返し実行することで購買パターンの抽出を行う． まず，フェロモンを付加するための環境として，仮 想グラフ G を用意する．G = (V, E) は仮想空間上の無 向グラフである．グラフ G における各ノード vi ∈ V は実環境における各商品 si ∈ S に対応し，各エッジ ei,j ∈ E は商品 siと商品 sjを一度の会計で同時に購入 したことを表す．また，グラフ G 上に付加されるフェ ロモンの分布は τ で表す．なお，前提条件として出現す る購買パターンに対する予備知識を持たないため，フェ ロモン分布 τ の初期値は 0 とする． 次に，フェロモンの付加フェーズについて述べる．レ シート ct,kごとにレシート内に出現した商品同士の分 布関数 di,j(ct,k)∈ {0, 1} を作成する．di,j(ct,k) = 1 は， レシート ct,k内で商品 siと商品 sj が同時に購入され たことを意味する． 一日分のレシートの情報から分布関数 di,j(ct,k) を作 成し，式 1 にしたがって，フェロモン τ の更新を行う． τi,j(t) = τi,j(t− 1) + ∑ k di,j(ct−1,k) (1) フェロモンの付加フェーズを実行した後，フェロモ ンの蒸発フェーズに移行する．フェロモンの蒸発フェー ズでは，式 2 にしたがって，仮想グラフ G に残留する フェロモンを減少させる．なお蒸発は蒸発率 ρ に依存 する． τi,j(t) = τi,j× (1 − ρ) (2) このフェロモンの蒸発フェーズを実行することによ り，古い情報は少しずつ破棄される．蒸発率 ρ は情報 更新の速さに影響する．つまり，蒸発率 ρ が大きくな ると古い情報が蓄積しづらくなり，新しい情報の影響 力が強くなる． 一般に，蒸発率 ρ が小さいと解の収束は遅いが安定 した解が達成しやすくなる．逆に，蒸発率 ρ が大きい と解の収束は速いが入力情報に出力結果が影響を受け やすく不安定な解になりやすい． なお，フェロモン τ の蒸発を行う際に，フェロモン τi,jが一定の閾値 ϵ 以下になった場合，そのフェロモン τi,jの値を τi,j= 0 にもどす．

4

実データを用いた評価実験

ACO に基づくパターンマイニングアルゴリズムに よって，経営科学系研究部会連合協議会主催，平成 26 年度データ解析コンペティションで提供された実際の マーケティングデータの解析を行う．解析の対象とな るデータは，全日食チェーンの北海道江別市にある二 つの店舗における 2013 年 7 月 1 日から 2014 年 6 月 30 日までの一年分のレシートの情報である．データの解 析にあたって，それぞれの店舗を区別するため，店舗 A と店舗 B で表現する．また，蒸発率 ρ は 0.01 に設定 する．2013 年 12 月 31 日分までのレシートのデータを 入力したときの出力結果と 2014 年 6 月 30 日分までの レシートのデータを入力したときの出力結果について

可視化を行い，時系列による変化や店舗間での比較を しながら考察する．

4.1

出力結果の可視化

ACO に基づくパターンマイニングアルゴリズムの出 力として得られるフェロモン τ が残留する仮想グラフ G を，Cytoscape[10] を利用して可視化する．可視化に 際して，残留フェロモンτに対する閾値 ϕ を定め，閾 値 ϕ に満たないエッジ ei,j削除する．次に，仮想グラ フ G に対して，Cytoscape のプラグインである cluster maker 2 の community clustering[11] を実行する．こ の community clustering は Girvan-Newman アルゴリ ズムによるクラスタリングが実装されたものである．ク ラスタリングによって得られた結果から，各クラスタ をそれぞれ円形に並べる．それぞれの円の位置は，ク ラスタ間のエッジが極力みえるように，試行錯誤のも と配置する．また，各クラスタには，区別のため，ア ルファベットを順に振り当てて表記する．

4.2

店舗 A の解析

店舗 A の店の規模は，坪数 74 坪，日商 28 万円で ある．データが提供された期間におけるレシート数は 116756 レシート，出現する商品名数は 7082 商品，一 日あたりの平均レシート数は 318 レシート，一日あた りの最大レシート数は 425 レシート，最小レシート数 は 132 レシートである． 2013 年 12 月 31 日分までのレシートデータを入力し たときの可視化の結果が図 2 であり，2014 年 6 月 30 日 分までのレシートデータを入力したときの可視化の結 果が図 3 である．なお，エッジを削除するための閾値は， 解析結果を考察しやすくすることを考慮して，ϕ = 25 （図 2），ϕ = 28 (図 3)  とした． 図 2 におけるクラスタ A をみるとヨーグルトや牛乳， たまご，納豆，バナナ，豚肉が並んでいる．豚肉を除い て考えると朝食のための食品であると考えられる．同 様に，図 3 におけるクラスタ A をみるとハム，たまご， 牛乳，納豆，バナナ，ヤクルト，ハムが並んでいる．こ れも，朝食のための食品と考えられる．このように，二 つの図において朝食という定番ともいえるパターンが 可視化できた． 一方で，図 2 におけるクラスタ B をみると，やきそ ば弁当，鶏照焼き丼，かぼちゃコロッケ，肉じゃがコ ロッケ，カツサンド，から揚げ，さつまいも天，メンチ カツサンド，飲料，ポテトチップス，買物袋，鶏肉が並 んでいる．昼ごはんやおやつのような軽食用に購入す るパターンのクラスタと考えられる．しかし，図 3 をみ ると，先に述べた昼ごはんや軽食用の購入パターンが 存在しない．代わりに，クラスタ M ではポテトチップ スが独立したクラスタとして存在し，クラスタ L では お茶が独立したクラスタとして存在する．また，クラ スタ N をみるとから揚げ，カツサンド，サイダーと買 物袋も独立している（クリアアサヒが混入している）． やきそば弁当や鶏照焼き丼といった商品は図中に存在 しない． このことから 2013 年 12 月 31 日分までのレシート データを入力したときには昼食やおやつといった少し 広い視点で購入していたが，2014 年 6 月 30 日分までの レシートデータを入力したときにはお茶やポテトチッ プスといった明確な目的商品の購入が増えたと想定で きる． 図 2: 店舗 A における 2013 年 12 月 31 日分までのレ シートデータを入力したときの可視化結果 図 3: 店舗 A における 2014 年 6 月 30 日分までのレシー トデータを入力したときの可視化結果

4.3

店舗 B の解析

店舗 B の店の規模は，坪数 146 坪，日商 44 万円で ある．データが提供された期間におけるレシート数は 139261 レシート，出現する商品名数は 8694 商品，一

日あたりの平均レシート数は 383 レシート，一日あた りの最大レシート数は 548 レシート，最小レシート数 は 143 レシートである． 2013 年 12 月 31 日分までのレシートデータを入力し たときの可視化の結果が図 4 であり，2014 年 6 月 30 日 分までのレシートデータを入力したときの可視化の結 果が図 5 である．なお，エッジを削除するための閾値は， 解析結果を考察しやすくすることを考慮して，ϕ = 50 （図 4），ϕ = 50 (図 5)  とした． 図 4 と図 5 を見比べると，図 5 の方が小さいクラス タが増えている．増えた小さいクラスタを見ると，ク ラスタ K の黒ラベルと淡麗生，クラスタ L のさわやか チューハイグレーとさわやかチューハイレモン，クラ スタ M のー 196 ストロングゼロ W とー 196 ストロン グゼロダ，クラスタ N のクリアアサヒとセブンスター とお酒が目立つ． 2013 年 12 月 31 日分までのレシートデータを入力し たときにはお酒を購入する人がすくなかったのに対し て，2014 年 6 月 30 日分までのレシートデータを入力 したときには，お酒だけの購入する人が多いことが分 かる． 図 4: 店舗 B における 2013 年 12 月 31 日分までのレ シートデータを入力したときの可視化結果

4.4

店舗間の比較

店舗 A と店舗 B に共通して，また時系列変化に影響 されず，スープヌードルが独立のクラスタで存在して いる．スープヌードルは店舗間や時期による影響を受 けず，他商品と同時に購入されることが少ないながら も購入されやすい定番商品といえる．また，店舗 A と 店舗 B で共通して，2013 年 12 月 31 日分までのレシー トデータを入力したときには店舗 A ではさつまい天が， 店舗 B では舞茸天が抽出されてたが，2014 年 6 月 30 図 5: 店舗 B における 2014 年 6 月 30 日分までのレシー トデータを入力したときの可視化結果 日分までのレシートデータを入力したときには抽出さ れなかった．さつまいもや舞茸といった季節性の高い 商品が抽出され，また時間経過に伴い消えていること がが確認できた．これは，ACO アルゴリズムを用いた ことで容易に抽出できるようになったと考える． 一方，店舗 A と店舗 B に共通して，2013 年 12 月 31 日分までのレシートデータを入力した場合と 2014 年 6 月 30 日分までのレシートデータを入力した場合とで， 抽出されたクラスタの数に差が生じている．2013 年 12 月 31 日分までのレシートデータを入力したときの可視 化結果はクラスタの数が少なく，2014 年 6 月 30 日分 までのレシートデータを入力したときの可視化結果は クラスタの数が多い．そこから，2013 年 12 月 31 日分 までのレシートデータを入力したときでは，消費者は 朝食のため，昼食のためといった抽象度の高い目的意 識のもと購買行動を行っている消費者が多いとも考え られる．一方，2014 年 6 月 30 日分までのレシートデー タを入力したときでは，消費者はこの商品が欲しいと いった具体性のある目的意識のもとに購買活動を行っ ている消費者が多いと考えられる． 図 2 と図 3 をみると，それぞれクラスタ A は朝食に 関係する商品が多い．さらに図 3 では，クラスタ C も 朝食に関係が強そうな商品が並んでいる．確かに，図 4 と図 5 のクラスタ A は朝食に関係が強そうな商品が みられる．しかし，朝食に関係が強い商品がクラスタ 内の多数を占めるクラスタとまではいえない．そこで， 店舗 A においては朝食に関係する食品という目的意識 だけでも商品を購入していたが，店舗 B においては朝 食に関係する食品だけでなく，他の商品も同時に購入 する消費者が多いといえる．店舗 B と比べ店舗 A の方 が店舗の規模が小さいために，消費者の購買目的が小 さいものになっている可能性がある．

5

おわりに

本研究では，ACO に基づくパターンマイニング手法 を提案した．提案した ACO に基づくパターンマイニ ング手法を用いて，実際のマーケティングデータの解 析を行った．なお，解析結果は Cytoscape を用いて可 視化した． 可視化することで，消費者の同時に購買する商品の パターンが直感的にわかるようになった．時系列によっ て消費者行動に変化が見られることが確認できた．12 月までのデータを入力したときに抽出されたサツマイ モ天や舞茸天が 6 月までのデータを入力すると抽出さ れなくなる現象より，季節変化にも対応できるアルゴ リズムであるといえる．また，店舗間で共通する定番 を明らかにするとともに，店舗によって消費者の目的 意識に違いがあることが想定できた． 今後の課題として，提案手法の階層化を考える．現 状の提案手法でより多数の商品を可視化することを考 えると，情報の粒度が細かくなりすぎてしまう．そこ で，提案手法によって得られるパターンをもとに，あ らたなパターンの抽出を試みるといった階層構造の導 入を考える．階層構造の導入によって，抽象度の高い 情報の取得が得られることで，消費者の行動パターン を効率的に可視化する．

参考文献

[1] 経済産業省:経済産業ジャーナル 2013 年 12・1 月 号,pp.4-13,2013.

[2] Ahith Abraham.et al, 栗原聡ら訳:群知能とデータ マイニング, 東京電機大学出版局,2012.

[3] Agrawal Rakesh and Ramakrishnan Srikant: Fast algorithms for mining association rules, Proc. 20th int. conf. very large data bases, VLDB. Vol. 1215, 1994.

[4] Agrawal Rakesh and Ramakrishnan Srikant:Mining sequential patterns, Data Engineering, 1995. Proceedings of the Eleventh International Conference on. IEEE, 1995. [5] Srikant Ramakrishnan and Rakesh Agrawal:

Mining sequential patterns: Generalizations and performance improvements, Springer Berlin Hei-delberg, 1996.

[6] Zaki Mohammed J:SPADE: An efficient algo-rithm for mining frequent sequences, Machine learning 42.1-2 ,pp.31-60,2001.

[7] Dorigo Marco, Luca Maria Gambardella:Ant colony system: a cooperative learning approach to the traveling salesman problem, Evolutionary Computation, IEEE Transactions on 1.1 pp.53-66, 1997.

[8] Martens David, et al : Classification with ant colony optimization, IEEE Transactions on Evo-lutionary Computation 11.5, pp.651-665,2007. [9] Tamaki Hiroshi, et al :Pheromone

Ap-proach to the Adaptive Discovery of Sensor-Network Topology, Proceedings of the 2008 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology-Volume 02. IEEE Computer Society, 2008.

[10] http://www.cytoscape.org/ (accessed2014-9-14) [11] The Resource for

Biocomput-ing, Visualization and Informat-ics(RBVI). RBVI Cytoscape Plugins. http://www.rbvi.ucsf.edu/cytoscape/clusterMaker2/ (accessed 2014-9-10)

[12] Girvan, Michelle, and Mark EJ New-man:Community structure in social and bi-ological networks, Proceedings of the National Academy of Sciences 99.12, pp.7821-7826,2002.