図面 (/)

技術 属性列挙システム、属性列挙方法および属性列挙プログラム

出願人 日本電気株式会社
発明者 楠村幸貴
出願日 2015年2月13日 (4年5ヶ月経過) 出願番号 2016-525668
公開日 2017年4月20日 (2年2ヶ月経過) 公開番号 WO2015-186278
状態 特許登録済
技術分野 検索装置
主要キーワード 技術効果 空間サイズ トポロジカルソート ノードセット 等価変換 列挙できる 全組合せ 分割元
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2017年4月20日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (14)

課題・解決手段

列挙プラン生成部81は、学習データの属性と、その属性の組合最大数とから、属性の組合せを表す論理式表現組み合わせ方表現した論理式構造の集合を生成し、生成された各論理式構造に含まれる論理式表現を2分割した部分論理式構造を生成して分割元の論理式構造に対応付けた列挙プランを生成する。属性生成部82は、生成された部分論理式構造に応じて各属性を組み合わせた新たな属性を生成する。また、列挙プラン生成部81は、各論理式構造から生成される2つの部分論理式構造に含まれる属性の数が均等になるように、論理式構造を2分割する。

概要

背景

データマイニングは、大量の情報の中から、これまで未知であった有用な知見を見つける技術である。データマイニングを効率的に実施するため、データマイニングに利用される属性(feature )を加工し、新たな属性を生成する処理が行われる。

新たな属性を生成する方法の一つとして、各属性を2値属性で表し、その2値属性をAND/OR演算子で繋いだ論理式を新たな属性として生成する方法が知られている。

例えば、各曜日を表す場合、7種類の2値属性(IS_日曜日、IS_月曜日、IS_火曜日、IS_水曜日、IS_木曜日、IS_金曜日、IS_土曜日)を用いて曜日を表すことができる。また、1日を午前または午後で表す場合、2種類の2値属性(IS_午前、IS_午後)を用いて1日を表すことができる。

これらの2値属性に基づいて、例えば、「週末の午後」という新たな属性を生成できる。具体的には、これらの2値属性をAND/OR演算子で繋いだ論理式「(IS_土曜日AND IS_午後)OR(IS_日曜日 AND IS_午後)」は、週末の午後という属性を表す。

実問題を解く上では、このように属性を適切に組合せた新しい属性を作ることが必要になることが多い。しかし、属性の適切な組合せ方を発見するのはそう簡単ではない。例えば、元データが100個の属性を持ち、このうち5つの属性をAND/ORで組み合わせることを考える場合、1005×24のオーダ(すなわち、1600億)の組合せによる論理式が存在するため、2値属性を単純に組み合わせた場合、大量のメモリや多大な計算時間を消費してしまうことになる。

非特許文献1や非特許文献2には、属性を列挙する方法が記載されている。非特許文献1および非特許文献2に記載された方法では、まず各属性をAND演算子で繋いだ属性(加法標準形:DNF(Disjunctive normal form ))を列挙し、列挙したこれらの属性をOR演算子で繋いで新たな属性を生成する。

また、非特許文献3には、頻繁に用いられるDNFのパターンを抽出する方法が記載されている。なお、非特許文献4には、属性を評価する方法の一例が記載されている。

概要

列挙プラン生成部81は、学習データの属性と、その属性の組合せ最大数とから、属性の組合せを表す論理式表現組み合わせ方表現した論理式構造の集合を生成し、生成された各論理式構造に含まれる論理式表現を2分割した部分論理式構造を生成して分割元の論理式構造に対応付けた列挙プランを生成する。属性生成部82は、生成された部分論理式構造に応じて各属性を組み合わせた新たな属性を生成する。また、列挙プラン生成部81は、各論理式構造から生成される2つの部分論理式構造に含まれる属性の数が均等になるように、論理式構造を2分割する。

目的

本発明は、属性の網羅性を担保しつつ、メモリの消費を抑えて高速に新たな属性を列挙することができる属性列挙システム、属性列挙方法および属性列挙プログラムを提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

学習データの属性と当該属性の組合最大数とから、属性の組合せを表す論理式表現組み合わせ方表現した論理式構造の集合を生成し、生成された各論理式構造に含まれる論理式表現を2分割した部分論理式構造を生成して分割元の論理式構造に対応付けた列挙プランを生成する列挙プラン生成部と、生成された前記部分論理式構造に応じて各属性を組み合わせた新たな属性を生成する属性生成部とを備え、前記列挙プラン生成部は、各論理式構造から生成される2つの部分論理式構造に含まれる属性の数が均等になるように、論理式構造を2分割することを特徴とする属性列挙システム

請求項2

列挙プラン生成部は、生成された論理式構造の一部を表現する部分論理式構造との関係をグラフ構造で表現した列挙プランを生成し、属性生成部によって生成される新たな属性を記憶するために必要な空間サイズを小さくしつつ、論理式構造の一部をより多く表現可能な部分論理式構造を前記列挙プランの中から選択する請求項1記載の属性列挙システム。

請求項3

属性生成部は、列挙プラン生成部によって選択された部分論理式構造に応じて生成される新たな属性を記憶装置に記憶させ、前記記憶装置に記憶された属性をもとに、他の論理式構造に応じた新たな属性を生成する請求項2記載の属性列挙システム。

請求項4

属性生成部により生成される属性の評価を行う属性評価部を備え、属性生成部は、各部分論理式構造に応じて新たな属性を生成するごとに、生成した属性を前記属性評価部に送信する請求項1から請求項3のうちのいずれか1項に記載の属性列挙システム。

請求項5

列挙プラン生成部は、属性の組合せを表す論理式表現に加法標準形または連言標準形を用いる請求項1から請求項4のうちのいずれか1項に記載の属性列挙システム。

請求項6

学習データの属性と当該属性の組合せ最大数とから、属性の組合せを表す論理式表現の組み合わせ方を表現した論理式構造の集合を生成し、生成された論理式構造の一部を表現する部分論理式構造との関係をグラフ構造で表現した列挙プランを生成する列挙プラン生成部と、前記部分論理式構造に応じて各属性を組み合わせた新たな属性を生成する属性生成部とを備え、前記列挙プラン生成部は、前記属性生成部によって生成される新たな属性を記憶するために必要な空間サイズを小さくしつつ、前記論理式構造の一部をより多く表現可能な部分論理式構造を前記列挙プランの中から選択することを特徴とする属性列挙システム。

請求項7

属性生成部は、列挙プラン生成部により選択された部分論理式構造に応じて生成される新たな属性を記憶装置に記憶させ、前記記憶装置に記憶された属性をもとに、他の論理式構造に応じた新たな属性を生成する請求項6記載の属性列挙システム。

請求項8

学習データの属性と当該属性の組合せ最大数とから、属性の組合せを表す論理式表現の組み合わせ方を表現した論理式構造の集合を生成し、生成された各論理式構造に含まれる論理式表現を2分割した部分論理式構造を生成して分割元の論理式構造に対応付けた列挙プランを生成し、生成された前記部分論理式構造に応じて各属性を組み合わせた新たな属性を生成し、列挙プランを生成する際、各論理式構造から生成される2つの部分論理式構造に含まれる属性の数が均等になるように、論理式構造を2分割することを特徴とする属性列挙方法

請求項9

生成された論理式構造の一部を表現する部分論理式構造との関係をグラフ構造で表現した列挙プランを生成し、生成される新たな属性を記憶するために必要な空間サイズを小さくしつつ、論理式構造の一部をより多く表現可能な部分論理式構造を前記列挙プランの中から選択する請求項8記載の属性列挙方法。

請求項10

学習データの属性と当該属性の組合せ最大数とから、属性の組合せを表す論理式表現の組み合わせ方を表現した論理式構造の集合を生成し、生成された論理式構造の一部を表現する部分論理式構造との関係をグラフ構造で表現した列挙プランを生成し、部分論理式構造に応じて生成される新たな属性を記憶するために必要な空間サイズを小さくしつつ、前記論理式構造の一部をより多く表現可能な部分論理式構造を前記列挙プランの中から選択し、選択された部分論理式構造に応じて各属性を組み合わせた新たな属性を生成することを特徴とする属性列挙方法。

請求項11

選択された部分論理式構造に応じて生成される新たな属性を記憶装置に記憶させ、前記記憶装置に記憶された属性をもとに、他の論理式構造に応じた新たな属性を生成する請求項10記載の属性列挙方法。

請求項12

コンピュータに、学習データの属性と当該属性の組合せ最大数とから、属性の組合せを表す論理式表現の組み合わせ方を表現した論理式構造の集合を生成し、生成された各論理式構造に含まれる論理式表現を2分割した部分論理式構造を生成して分割元の論理式構造に対応付けた列挙プランを生成する列挙プラン生成処理、および、生成された前記部分論理式構造に応じて各属性を組み合わせた新たな属性を生成する属性生成処理を実行させ、前記列挙プラン生成処理で、各論理式構造から生成される2つの部分論理式構造に含まれる属性の数が均等になるように、論理式構造を2分割させるための属性列挙プログラム

請求項13

コンピュータに、列挙プラン生成処理で、生成された論理式構造の一部を表現する部分論理式構造との関係をグラフ構造で表現した列挙プランを生成させ、属性生成処理で生成される新たな属性を記憶するために必要な空間サイズを小さくしつつ、論理式構造の一部をより多く表現可能な部分論理式構造を前記列挙プランの中から選択させる請求項12記載の属性列挙プログラム。

請求項14

コンピュータに、学習データの属性と当該属性の組合せ最大数とから、属性の組合せを表す論理式表現の組み合わせ方を表現した論理式構造の集合を生成し、生成された論理式構造の一部を表現する部分論理式構造との関係をグラフ構造で表現した列挙プランを生成する列挙プラン生成処理、および、前記部分論理式構造に応じて各属性を組み合わせた新たな属性を生成する属性生成処理とを実行させ、前記列挙プラン生成処理で、前記属性生成処理で生成される新たな属性を記憶するために必要な空間サイズを小さくしつつ、前記論理式構造の一部をより多く表現可能な部分論理式構造を前記列挙プランの中から選択させるための属性列挙プログラム。

請求項15

コンピュータに、属性生成処理で、列挙プラン生成処理で選択された部分論理式構造に応じて生成される新たな属性を記憶装置に記憶させ、前記記憶装置に記憶された属性をもとに、他の論理式構造に応じた新たな属性を生成させる請求項14記載の属性列挙プログラム。

技術分野

0001

本発明は、学習データの属性を組み合わせた新たな属性を列挙する属性列挙システム、属性列挙方法および属性列挙プログラムに関する。

背景技術

0002

データマイニングは、大量の情報の中から、これまで未知であった有用な知見を見つける技術である。データマイニングを効率的に実施するため、データマイニングに利用される属性(feature )を加工し、新たな属性を生成する処理が行われる。

0003

新たな属性を生成する方法の一つとして、各属性を2値属性で表し、その2値属性をAND/OR演算子で繋いだ論理式を新たな属性として生成する方法が知られている。

0004

例えば、各曜日を表す場合、7種類の2値属性(IS_日曜日、IS_月曜日、IS_火曜日、IS_水曜日、IS_木曜日、IS_金曜日、IS_土曜日)を用いて曜日を表すことができる。また、1日を午前または午後で表す場合、2種類の2値属性(IS_午前、IS_午後)を用いて1日を表すことができる。

0005

これらの2値属性に基づいて、例えば、「週末の午後」という新たな属性を生成できる。具体的には、これらの2値属性をAND/OR演算子で繋いだ論理式「(IS_土曜日AND IS_午後)OR(IS_日曜日 AND IS_午後)」は、週末の午後という属性を表す。

0006

実問題を解く上では、このように属性を適切に組合せた新しい属性を作ることが必要になることが多い。しかし、属性の適切な組合せ方を発見するのはそう簡単ではない。例えば、元データが100個の属性を持ち、このうち5つの属性をAND/ORで組み合わせることを考える場合、1005×24のオーダ(すなわち、1600億)の組合せによる論理式が存在するため、2値属性を単純に組み合わせた場合、大量のメモリや多大な計算時間を消費してしまうことになる。

0007

非特許文献1や非特許文献2には、属性を列挙する方法が記載されている。非特許文献1および非特許文献2に記載された方法では、まず各属性をAND演算子で繋いだ属性(加法標準形:DNF(Disjunctive normal form ))を列挙し、列挙したこれらの属性をOR演算子で繋いで新たな属性を生成する。

0008

また、非特許文献3には、頻繁に用いられるDNFのパターンを抽出する方法が記載されている。なお、非特許文献4には、属性を評価する方法の一例が記載されている。

先行技術

0009

Lizhuang Zhao, Mohammed J. Zaki, Naren Ramakrishnan, "BLOSOM: A Framework for Mining Arbitrary Boolean Expressions", KDD'06 Proceedings of the 12thACMSIGKDD international conference on Knowledge discovery and data mining, p.827-832, 2006
Vimieiro Renato, Moscato Pablo, “Mining disjunctive minimal generators with TitanicOR”, Expert Systems with Applications Vol.39, Issue 9, p.8228-8238, 2012
Geng Li, Mohammed J. Zaki, ”Sampling Minimal Frequent Boolean (DNF) Patterns”, KDD '12 Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, p.87-95, 2012
S. Perkins, J. Theiler, ”Online Feature Selection using Grafting”, In ICML, 2003

発明が解決しようとする課題

0010

しかし、非特許文献1や非特許文献2に記載された方法では、DNFを列挙する際、最初にAND演算子で連結した属性のみを列挙したのち、これらを一つずつOR演算子で接続していく、という列挙方式が用いられている。しかし、これでは大量のメモリ空間が必要になってしまうという問題がある。例えば、非特許文献1に記載された方法を用いて、100個のオリジナル属性の中から5つの属性をAND/OR演算子で繋いだ属性を列挙するとする。この場合、4つの属性をAND/OR演算子で繋いだ属性は、1004通りの組合せになるが、このすべての属性をメモリに保持しなければならず、大量のメモリ空間が必要になってしまう。

0011

一方、大量のメモリ空間が必要になることを抑制するため、新たに作成される属性をメモリにキャッシュせず、その都度計算することも考えられる。しかし、この方法では、全ての組合せを、一から再生成する必要があるため、多大な計算時間を消費してしまい、高速に属性を列挙することができない問題がある。

0012

また、大量のメモリや多大な計算時間を消費することを抑制するため、非特許文献3に記載された方法を用いて、ランダムに属性をサンプリングすることも考えられる。しかし、非特許文献3に記載された方法で抽出される組合せには網羅性が無いため、より良い属性を生成することは困難である。

0013

そこで、本発明は、属性の網羅性を担保しつつ、メモリの消費を抑えて高速に新たな属性を列挙することができる属性列挙システム、属性列挙方法および属性列挙プログラムを提供することを目的とする。

課題を解決するための手段

0014

本発明による属性列挙システムは、学習データの属性とその属性の組合せ最大数とから、属性の組合せを表す論理式表現組み合わせ方表現した論理式構造の集合を生成し、生成された各論理式構造に含まれる論理式表現を2分割した部分論理式構造を生成して分割元の論理式構造に対応付けた列挙プランを生成する列挙プラン生成部と、生成された部分論理式構造に応じて各属性を組み合わせた新たな属性を生成する属性生成部とを備え、列挙プラン生成部が、各論理式構造から生成される2つの部分論理式構造に含まれる属性の数が均等になるように、論理式構造を2分割することを特徴とする。

0015

本発明による他の属性列挙システムは、学習データの属性とその属性の組合せ最大数とから、属性の組合せを表す論理式表現の組み合わせ方を表現した論理式構造の集合を生成し、生成された論理式構造の一部を表現する部分論理式構造との関係をグラフ構造で表現した列挙プランを生成する列挙プラン生成部と、部分論理式構造に応じて各属性を組み合わせた新たな属性を生成する属性生成部とを備え、列挙プラン生成部は、属性生成部によって生成される新たな属性を記憶するために必要な空間サイズを小さくしつつ、論理式構造の一部をより多く表現可能な部分論理式構造を列挙プランの中から選択することを特徴とする。

0016

本発明による属性列挙方法は、学習データの属性とその属性の組合せ最大数とから、属性の組合せを表す論理式表現の組み合わせ方を表現した論理式構造の集合を生成し、生成された各論理式構造に含まれる論理式表現を2分割した部分論理式構造を生成して分割元の論理式構造に対応付けた列挙プランを生成し、生成された部分論理式構造に応じて各属性を組み合わせた新たな属性を生成し、列挙プランを生成する際、各論理式構造から生成される2つの部分論理式構造に含まれる属性の数が均等になるように、論理式構造を2分割することを特徴とする。

0017

本発明による他の属性列挙方法は、学習データの属性とその属性の組合せ最大数とから、属性の組合せを表す論理式表現の組み合わせ方を表現した論理式構造の集合を生成し、生成された論理式構造の一部を表現する部分論理式構造との関係をグラフ構造で表現した列挙プランを生成し、部分論理式構造に応じて生成される新たな属性を記憶するために必要な空間サイズを小さくしつつ、論理式構造の一部をより多く表現可能な部分論理式構造を列挙プランの中から選択し、選択された部分論理式構造に応じて各属性を組み合わせた新たな属性を生成することを特徴とする。

0018

本発明による属性列挙プログラムは、コンピュータに、学習データの属性とその属性の組合せ最大数とから、属性の組合せを表す論理式表現の組み合わせ方を表現した論理式構造の集合を生成し、生成された各論理式構造に含まれる論理式表現を2分割した部分論理式構造を生成して分割元の論理式構造に対応付けた列挙プランを生成する列挙プラン生成処理、および、生成された部分論理式構造に応じて各属性を組み合わせた新たな属性を生成する属性生成処理を実行させ、列挙プラン生成処理で、各論理式構造から生成される2つの部分論理式構造に含まれる属性の数が均等になるように、論理式構造を2分割させることを特徴とする。

0019

本発明による他の属性列挙プログラムは、コンピュータに、学習データの属性とその属性の組合せ最大数とから、属性の組合せを表す論理式表現の組み合わせ方を表現した論理式構造の集合を生成し、生成された論理式構造の一部を表現する部分論理式構造との関係をグラフ構造で表現した列挙プランを生成する列挙プラン生成処理、および、部分論理式構造に応じて各属性を組み合わせた新たな属性を生成する属性生成処理とを実行させ、列挙プラン生成処理で、属性生成処理で生成される新たな属性を記憶するために必要な空間サイズを小さくしつつ、論理式構造の一部をより多く表現可能な部分論理式構造を列挙プランの中から選択させることを特徴とする。

発明の効果

0020

本発明によれば、属性の網羅性を担保しつつ、メモリの消費を抑えて高速に新たな属性を列挙することができる。すなわち、上記の「発明が解決しようとする課題」に記載された技術課題を、上記の「課題を解決するための手段」に示される技術手段を用いることで、本「発明の効果」に記載される技術効果を得ることができる。

図面の簡単な説明

0021

本発明による属性列挙システムの一実施形態を示すブロック図である。
学習データが示す属性の例を示す説明図である。
列挙プラン生成部11が行う処理の例を示すフローチャートである。
グラフ構造の例を示す説明図である。
トポロジカルソートの動作例を示す説明図である。
トポロジカルソートの動作例を示す説明図である。
表形式で表現された列挙プランの例を示す説明図である。
計算コストおよびメモリコストの例を示す説明図である。
列挙プランの例を示す説明図である。
中間データ記憶部13が記憶するデータの例を示す説明図である。
DNF探索部12による処理の具体例を示す説明図である。
本発明による属性列挙システムの概要を示すブロック図である。
本発明による属性列挙システムの他の概要を示すブロック図である。

0022

以下、本発明の実施形態を図面を参照して説明する。図1は、本発明による属性列挙システムの一実施形態を示すブロック図である。以下の説明では、2値属性の組合せを表す論理式をDNFで表現するものとする。DNFは、Z=∨∧iziで表現される論理式であり、論理積のみからなる項を論理和で繋いだ式で表現される。任意の論理式は、DNFに等価変換可能である。

0023

なお、本実施形態では、DNFの列挙問題について説明するが、論理和のみからなる項を論理積で繋いだ式で表現されるCNF(Conjunctive normal form )の列挙問題についても同様に適用可能である。

0024

また、以下の説明では、論理式に含まれている属性の数を、論理式の長さと定義する。図2は、学習データが示す属性の例を示す説明図である。図2に例示する表(行列)は、学習データであるサンプルデータs1〜s5に対して、属性f1〜f5を有するか否かを1/0で表現したものである。

0025

例えば、長さ2の論理式f1∨f3をそれぞれの学習データについて計算すると、f1∨f3=[1,1,1,1,0]と算出される。また、例えば、長さ2の論理式f1∧f4をそれぞれの学習データについて計算すると、f2∧f4=[0,0,1,0,0]と算出される。さらに、例えば、長さ3の論理式(f2∧f4)∨f5をそれぞれの学習データについて計算すると、(f2∧f4)∨f5=[0,0,1,1,1]と算出される。

0026

図1に例示する本実施形態の属性列挙システムは、列挙プラン生成部11と、DNF探索部12と、中間データ記憶部13と、逐次的属性評価部14と、出力データ記憶部15とを備えている。

0027

本実施形態の属性列挙システムには、指定された属性を学習データが有するか否かを示す2値行列Xと、組み合わせる属性の最大数MaxLenが入力される。例えば、2値行列Xとして、図2に例示する行列が入力される。また、MaxLenは、例えば、ユーザ等により指定される。

0028

列挙プラン生成部11は、2値行列XおよびMaxLenが入力されると、学習データの属性とMaxLenとから、長さがMaxLen以内の属性の組合せを表す論理式を生成する。さらに、本実施形態では、列挙プラン生成部11は、生成した論理式の組み合わせ方を表現した論理式構造の集合を生成する。本実施形態では、論理式をDNFで表現しているため、この論理式構造のことをDNFラベルと記す。

0029

DNFラベルは、AND項に含まれる属性数とOR演算子を示すカンマで論理式を表現する。例えば、[3]と表現されるDNFラベルは、“A and B and C”を表現する。また、例えば、[1,1]と表現されるDNFラベルは、“A or B”を表現する。また、例えば、[1,3]と表現されるDNFラベルは、“A or (B and C and D)”を表現する。ここで、A、B、CおよびDは、属性を示す。

0030

次に、列挙プラン生成部11は、生成した論理式構造に含まれる論理式表現を2つの部分論理式構造に分割する。本実施形態では、列挙プラン生成部11は、生成された論理式構造の一部を表現する部分論理式構造との関係をグラフ構造で表現する。グラフ構造における各ノードは、論理式構造または部分論理式構造である。このように表現されたグラフ構造を、以下、列挙プランと記す。このようなグラフ構造を生成することにより、分割元の論理式構造と、2分割された部分論理式構造とが対応付けられることになる。グラフ構造は、例えば、DAG(有向非循環グラフ:directed acyclic graph)で表現される。

0031

以下、列挙プラン生成部11がグラフ構造を生成する処理を具体的に説明する。図3は、列挙プラン生成部11が行う処理の例を示すフローチャートである。まず、列挙プラン生成部11が、長さMaxLenまでのDNFラベルの全組合せを生成する(図3におけるステップS11)。例えば、MaxLen=4の場合、生成されるDNFラベルは、[4],[3,1],[3],[2,2],[2,1,1],[2,1],[2],[1,1,1,1],[1,1,1],[1,1],[1]である。なお、ここで生成されるDNFラベルの集合は、属性の組合せを表す論理式表現の組み合わせ方を表現した論理式構造の集合と言える。

0032

次に、列挙プラン生成部11は、構造分割を行う(図3におけるステップS12)。具体的には、列挙プラン生成部11は、生成したDNFラベルを分割して親ノードを特定し、ノード間を結ぶエッジを生成する。

0033

列挙プラン生成部11は、例えば、以下の手順に基づいて親ノードを特定する。対象とするDNFラベルがAND項のみの場合、列挙プラン生成部11は、AND項の数をNとしたとき、長さがceiling(N/2)の部分DNFラベルと、長さがN−ceiling(N/2)の部分DNFラベルに分割する。ここで、ceiling()関数は、小数点以下を切り上げる関数である。

0034

一方、対象とするDNFラベルがOR項(すなわち、カンマ)を含む場合、列挙プラン生成部11は、カンマ区切りの数列を、2つの部分DNFラベルに分割する。このとき、列挙プラン生成部11は、2つの部分DNFラベルに含まれる属性の数の差が最小になるようにDNFラベルを分割する。すなわち、列挙プラン生成部11は、各DNFラベルから生成される2つの部分DNFラベルに含まれる属性の数が均等になるように、DNFラベルを2分割する。

0035

以下、DNFラベルが[1,1,2,3,4]と表現される場合の例を用いて、DNFラベルをセットS1とセットS2に分割するアルゴリズムを説明する。なお、S1およびS2は、初期状態では空の状態に初期化される。

0036

まず、列挙プラン生成部11は、DNFラベルを降順ソートする。ソートされた結果をsorted_listに格納すると、sorted_list=[4,3,2,1,1]になる。列挙プラン生成部11は、S1とS2に含まれる数字の総和を算出し、小さいほうのセットに、sorted_listの先頭の数字を設定する。そして、設定された数字およびその後のカンマをsorted_listから削除する。

0037

上記例の場合、初期状態では、S1もS2も数字の総和は0で等しいため、列挙プラン生成部11は、まず先頭の数字「4」を、S1に設定してsorted_listから削除する。よって、sorted_list=[3,2,1,1]、S1=[4]、S2=[]になる。

0038

このとき、S1の数字の総和は4であり、S2の数字の総和は0である。そこで、列挙プラン生成部11は、先頭の数字「3」を、S2に設定してsorted_listから削除する。よって、sorted_list=[2,1,1]、S1=[4]、S2=[3]になる。すると、S1の数字の総和は4であり、S2の数字の総和は3である。そこで、列挙プラン生成部11は、先頭の数字「2」を、S2に設定してsorted_listから削除する。よって、sorted_list=[1,1]、S1=[4]、S2=[3,2]になる。

0039

以下、同様に、S1の数字の総和が4であり、S2の数字の総和は5であるため、列挙プラン生成部11は、先頭の数字「2」を、S1に設定してsorted_listから削除する。よって、sorted_list=[1]、S1=[4,1]、S2=[3,2]になる。最後に、S1の数字の総和が5であり、S2の数字の総和も5であるため、列挙プラン生成部11は、先頭の数字「1」を、S1に設定してsorted_listから削除する。sorted_list=[]、S1=[4,1,1]、S2=[3,2]になる。

0040

その結果、DNFラベルは、2つの部分DNFラベル[4,1,1]と[3,2]に分割される。そこで、列挙プラン生成部11は、この2つの部分DNFラベルを親ノードとし、分割元のDNFラベルを子ノードとして、親ノードから子ノードへのエッジを生成する。

0041

図4はグラフ構造の例を示す説明図である。図4に例示するグラフは、MaxLen=4の場合におけるDAGの例を示す。

0042

次に、列挙プラン生成部11は、各ノード(DNFラベル)に順序付けを行う(図3におけるステップS13)。本実施形態では、列挙プラン生成部11は、トポロジカルソートにより、各ノードに順序付けを行う。なお、DAGは、トポロジカルソート可能なことが知られており、トポロジカルソートにより親子関係(矢印の前後関係)を保った順序付けが可能である。

0043

以下、図4に例示するDAGに対して、トポロジカルソートにより各ノードに順序付けする動作を説明する。図5および図6は、トポロジカルソートの動作例を示す説明図である。まず、列挙プラン生成部11は、DNFラベルの集合Sを降順にソートする。その結果、DNFラベル[4]が先頭の要素になる。そこで、列挙プラン生成部11は、DNFラベル[4]のノードを訪問済みのノードとしてチェックする(図5(a))。

0044

次に、列挙プラン生成部11は、DNFラベル[4]のノードの出力辺を辿り、その先のDNFラベル[2]のノードを訪問済みのノードとしてチェックする(図5(b))。同様に、列挙プラン生成部11は、DNFラベル[2]のノードの出力辺を辿り、その先のDNFラベル[1]のノードを訪問済みのノードとしてチェックする。DNFラベル[1]のノードは、親ノードが存在しないため、列挙プラン生成部11は、DNFラベル[1]のノードを1番に設定する(図5(c))。

0045

このとき、DNFラベル[2]のノードは、親ノードにすべて順番が設定されたため、列挙プラン生成部11は、DNFラベル[2]のノードを2番に設定する。同様に、DNFラベル[4]のノードは、親ノードにすべて順番が設定されたため、列挙プラン生成部11は、DNFラベル[4]のノードを3番に設定する(図5(d))。

0046

次に、列挙プラン生成部11は、DNFラベルの集合Sの先頭から2つめの要素であるDNFラベル[3,1]を選択し、DNFラベル[3,1]のノードを訪問済みのノードとしてチェックする(図6(e))。列挙プラン生成部11は、DNFラベル[3,1]のノードの出力辺を辿り、その先のDNFラベル[3]のノードを訪問済みのノードとしてチェックする。

0047

DNFラベル[3]のノードは、親ノードにすべて順番が設定されたため、列挙プラン生成部11は、DNFラベル[3]のノードを4番に設定する。同様に、DNFラベル[3,1]のノードは、親ノードにすべて順番が設定されたため、列挙プラン生成部11は、DNFラベル[3,1]のノードを5番に設定する(図6(f))。以下、列挙プラン生成部11が同様の動作を繰り返すことにより、全てのノードに順番が設定される(図6(g))。

0048

なお、グラフ構造で表現される列挙プランは、表形式でも表現することが可能である。図7は、表形式で表現された列挙プランの例を示す説明図である。図7に示す例では、列挙プランは、DNFラベルと、そのDNFラベルの親になる2つのDNFラベルとを対応付けている。また、列挙プランは、キャッシュするか否かを示すフラグ(cacheFlag )を含んでいてもよい。

0049

次に、列挙プラン生成部11は、キャッシュ対象を特定する(図3におけるステップS14)。具体的には、列挙プラン生成部11は、中間データ記憶部13に記憶させる対象の属性を特定する。このとき、列挙プラン生成部11は、DNFラベルで特定される論理式構造(論理式)に基づいて生成される新たな属性を中間データ記憶部13に記憶させるために必要な空間サイズを小さくしつつ、論理式構造の一部をより多く表現可能な部分論理式構造を列挙プランから選択する。なお、論理式構造の一部をより多く表現可能とは、部分論理式構造の再利用性が高いことを意味する。なお、新たな属性は、後述するDNF探索部12によって生成される。

0050

本実施形態では、列挙プラン生成部11は、計算コストとメモリコストに基づいて、キャッシュ対象を特定する。ここでは、計算コストを、列挙プラン上の参照回数とする。具体的には、計算コストは、親ノードとして参照される回数を示す。また、メモリコストとは、属性を記憶するため必要なメモリ空間の大きさであり、単純には、DNFラベルに含まれる数の総和で表される。

0051

図8は、図4に例示する列挙プランに基づいて計算コストおよびメモリコストを算出した例を示す説明図である。図8に示す例では、計算コストは、列挙プラン上の参照回数、メモリコストは、DNFラベルに含まれる数の総和を示す。なお、図8(a)に例示するように、キャッシュ対象が特定されていない場合、cacheFlag列はブランクの状態である。

0052

列挙プラン生成部11は、親ノードとして参照される回数が1回以上(すなわち、計算コストが1以上)のノードを降順で並べ替え、上位K個のノードをキャッシュ対象として特定する。なお、選択するノードの個数は、生成される属性のメモリサイズMが指定されるキャッシュサイズ以内に収まる個数である。

0053

元属性数をpとし、ベクトル長をnとするとき、ノードセットSのキャッシュサイズは、以下に示す式1で算出される。

0054

0055

式1において、sum(dnf.label)は、DNFラベルに含まれる数の総和を示す。また、式1において、1変数あたり4バイト必要であると想定し、4が乗じられている。例えば、ベクトル長n=10、元属性数p=10とすると、DNFラベル[1]とDNFラベル[2]のキャッシュは、以下に示す式2のように算出される。

0056

Cashesize([1],[2])=4*10*10+4*10*10^2=4400byte (式2)

0057

上記の式2に示すように、DNFラベル[1]で示されるDNFは、p個のオーダである。すなわち、キャッシュサイズは、p個×長さ10×4バイトである。一方、DNFラベル[2]で示されるDNFは、p2個のオーダである。すなわち、キャッシュサイズは、p2個×長さ10×4バイトである。なお、DNFラベル[1,1]で示されるDNFも、p2個のオーダであるため、キャッシュサイズは、DNFラベル[2]で示されるDNFと同様である。

0058

本実施形態では、DNFラベル[1],[2],[1,1]がキャッシュ対象として特定されたものとする。この場合、列挙プラン生成部11は、図8(b)に例示するように、キャッシュ対象になったDNFラベルに対しては、cacheFlag列に“TRUE”を設定し、キャッシュ対象でないDNFラベルに対しては、cacheFlag列に“FALSE”を設定する。

0059

図9は、列挙プランの例を示す説明図である。図9に例示する表とDAGがそれぞれ対応し、表のcacheFlag列に“TRUE”が設定されたDNFラベル、および、DAGの黒塗りのノードがキャッシュ対象として特定されたことを示す。

0060

なお、上述するように、本実施形態では、列挙プラン生成部11が、各論理式構造から生成される2つの部分論理式構造に含まれる属性の数の差が最小になるように、論理式構造を2分割する。言い換えると、列挙プラン生成部11が、ノードの親子関係を作る際に、各論理式構造(DNF構造)を均等に分割する。そのため、メモリコストを下げることが可能になる。

0061

例えば、長さ4のDNFが存在する場合、列挙プラン生成部11は、長さ3のDNFと長さ1のDNFに分割するのではなく、長さ2の2つのDNFに分割する。長さ3のDNFと長さ1のDNFに分割すると、長さ3のDNFをメモリに保持するサイズは、3乗のオーダになってしまう。一方、長さ2のDNFをメモリに保持するサイズは、2乗のオーダで済むことになる。

0062

DNF探索部12は、列挙プラン生成部11により特定されたDNFラベルの順序で、そのDNFラベルに応じて各属性を組み合わせた新たな属性を生成する。また、属性を生成する対象のDNFラベルが、列挙プラン生成部11により特定されたキャッシュ対象である場合、DNF探索部12は、生成した属性を中間データ記憶部13に登録する。なお、DNF探索部12は、1番のノード(すなわち、オリジナルのノード)を最初に中間データ記憶部13に登録する。

0063

具体的には、DNF探索部12は、親のDNFラベルについて生成された属性が中間データ記憶部13にキャッシュされている場合には、その属性を利用して、新たな属性を生成する。本実施形態では、列挙プラン生成部11がキャッシュ対象として、再利用性が高い論理式構造(DNFラベル)を選択する。そのため、計算量を削減することが可能になる。

0064

DNF探索部12は、各DNFラベルに対応する新たな属性を生成するたびに、生成した属性を逐次的属性評価部14に通知する。

0065

中間データ記憶部13は、DNF探索部12により生成される新たな属性を記憶する。具体的には、中間データ記憶部13は、論理式構造(DNFラベル)ごとに、DNFのリストベクトルとを対応付けて記憶する。中間データ記憶部13は、例えば、磁気ディスク等により実現される。

0066

図10は、中間データ記憶部13が記憶するデータの例を示す説明図である。図10に例示するDNF列内の各数字は、属性の種類(属性のID番号)を示し、構造ラベルは論理式構造を示す。なお、DNF列に示す情報は、属性ID番号の順列を保持するための情報であるため、任意の符号化を行うことが可能である。また、DNF探索部12は、同じベクトルを別の記号置換するなど、任意の圧縮を行ったベクトルを中間データ記憶部13に記憶してもよい。

0067

逐次的属性評価部14は、DNF探索部12により生成される属性について評価を行う。逐次的属性評価部14は、例えば、非特許文献4に記載された方法を用いて、属性を評価してもよい。ただし、属性を評価する方法は、非特許文献4に記載された方法に限定されず、逐次的属性評価部14は、任意の方法を用いて属性を評価すればよい。

0068

本実施形態の逐次的属性評価部14は、DNF探索部12が生成するたびに通知する新たな属性を逐次受け取り、受け取った属性の評価を行う。このように、逐次評価を行うことで、新たに生成される属性を保持するためのコストを削減できる。

0069

そして、逐次的属性評価部14は、評価結果を出力データ記憶部15に記憶させる。出力データ記憶部15は、評価結果を記憶する記憶装置である。逐次的属性評価部14は、例えば、HSIC(Hilbert-Schmidt Independence Criterion)や、ピアソン相関を用いて算出される任意のスコアをもとに、上位(例えば、100個)の属性を選択し、選択した属性を出力データ記憶部15に記憶させてもよい。

0070

なお、本実施形態では、評価結果を出力データ記憶部15に記憶させる場合を例示しているが、逐次的属性評価部14は、通信回線を介して他の装置(図示せず)に評価結果を送信してもよい。

0071

列挙プラン生成部11と、DNF探索部12と、逐次的属性評価部14とは、プログラム(属性列挙プログラム)に従って動作するコンピュータのCPUによって実現される。例えば、プログラムは、属性列挙システム内の記憶部(図示せず)に記憶され、CPUは、そのプログラムを読み込み、プログラムに従って、列挙プラン生成部11、DNF探索部12および逐次的属性評価部14として動作してもよい。

0072

また、列挙プラン生成部11と、DNF探索部12と、逐次的属性評価部14とは、それぞれが専用のハードウェアで実現されていてもよい。具体的には、本実施形態の属性列挙システムは、2つ以上の物理的に分離した装置が有線または無線で接続されることにより実現されていてもよく、1つの装置で実現されていてもよい。

0073

以上のように、本実施形態では、列挙プラン生成部11が、学習データの属性とMaxLenとから、属性の組合せを表す論理式表現の組み合わせ方を表現したDNFラベルの集合を生成する。また、列挙プラン生成部11が、生成された各DNFラベルに含まれる論理式表現を2分割した部分DNFラベルを生成して分割元のDNFラベルに対応付けた列挙プランを生成する。そして、DNF探索部12が、生成された部分DNFラベルに応じて各属性を組み合わせた新たな属性を生成する。このとき、列挙プラン生成部11は、各DNFラベルから生成される2つの部分DNFラベルに含まれる属性の数が均等になるように、DNFラベルを2分割する。

0074

このようにして分割されたDNFラベルを用いることで、属性の網羅性を担保できるとともに、分割されたDNFラベルに応じて作成される属性のサイズを小さくしながら、高速に新たな属性を列挙することができる。

0075

また、一方で、本実施形態では、列挙プラン生成部11が、生成されたDNFラベルの一部を表現する部分DNFラベルとの関係をグラフ構造で表現した列挙プランを生成する。このとき、列挙プラン生成部11は、DNF探索部12によって生成される新たな属性を記憶するために必要な空間サイズを小さくしつつ、DNFラベルの一部をより多く表現可能な(すなわち、再利用性が高い)部分DNFラベルを列挙プランの中から選択する。

0076

すなわち、DNFラベルごとに生成時の部品となる関係(親子関係)をグラフ構造で特定し、キャッシュするためのメモリコストと、再利用するための計算コストの観点でノードの部分集合を選択する。そのため、計算コストを低減させて属性を高速に列挙しつつ、属性を記憶するためのメモリの消費を抑えながら、新たな属性を網羅的に列挙できる

0077

言い換えると、本実施形態では、列挙プラン生成部11が、最初にMaxLen以下のDNFの組合せ方法自動決定し、メモリ量と計算量の観点でバランスを取った列挙プランを生成する。そのため、属性の網羅性を担保しつつ、メモリの消費を抑えて高速に新たな属性を列挙することができる。

0078

例えば、図9に例示する列挙プランが特定された場合、DNFラベル[1],[2],[1,1]に対応する新たな属性、すなわち、2乗オーダの属性をキャッシュすればよい。特に、DNFラベル[4]の属性を生成する際、本実施形態では、DNFラベル[3],[1]に対応する属性ではなく、DNFラベル[2]に対応する属性を利用できるため、メモリの消費を抑えて高速に新たな属性を列挙することができる。

0079

さらに、本実施形態では、再利用性の高いDNFをキャッシュするため、キャッシュの効率を高めることができる。例えば、図9に例示する列挙プランの場合、DNFラベル[1,1,1,1],[1,1,1],[2,1,1]の属性を評価する際、新たにDNFラベル[1,1]に対応する属性を生成する必要がない。

0080

以下、具体的な実施例により本発明を説明するが、本発明の範囲は以下に説明する内容に限定されない。図11は、DNF探索部12が属性を作成し、キャッシュ対象の属性を中間データ記憶部13に記憶させる処理の具体例を示す説明図である。

0081

図11(a)は、DNFラベルごとに属性を生成する処理の例を示す。図11(a)示す例では、DNF探索部12が図9に例示する表の上の行から順に属性を生成し、属性を生成するたびに、生成した属性を逐次的属性評価部14に出力する。また、生成した属性がキャッシュ対象の場合、DNF探索部12は、生成した属性を中間データ記憶部13に記憶させる。

0082

図11(b)は、属性の組合せを出力する処理の例を示す。図11(b)に示す例では、DNFラベルに対応する属性が中間データ記憶部13に記憶されている(キャッシュされている)場合、DNF探索部12は、その属性を出力する。一方、DNFラベルに対応する属性が中間データ記憶部13に記憶されていない(キャッシュされていない)場合、属性の組合せを生成する。この場合、DNF探索部12は、親のDNFも生成する。

0083

さらに、図11(b)に例示する処理において、ラベルがAND項のみの場合、DNF探索部12は、ANDの組合せを生成し、ラベルがAND項のみでない場合、DNF探索部12は、ORの組合せを生成する。

0084

次に、本発明の概要を説明する。図12は、本発明による属性列挙システムの概要を示すブロック図である。本発明による属性列挙システムは、学習データ(例えば、2値行列X)の属性と、その属性の組合せ最大数(例えば、MaxLen)とから、属性の組合せを表す論理式表現(例えば、DNF、CNF)の組み合わせ方を表現した論理式構造(例えば、DNFラベル)の集合を生成し、生成された各論理式構造に含まれる論理式表現を2分割した部分論理式構造(例えば、部分DNFラベル)を生成して分割元の論理式構造に対応付けた列挙プラン(例えば、図9に例示する表形式またはグラフ構造による列挙プラン)を生成する列挙プラン生成部81(例えば、列挙プラン生成部11)と、生成された部分論理式構造に応じて各属性を組み合わせた新たな属性を生成する属性生成部82(例えば、DNF探索部12)とを備えている。

0085

列挙プラン生成部81は、各論理式構造から生成される2つの部分論理式構造に含まれる属性の数が均等になるように(例えば、差が最小になるように)、論理式構造を2分割する。

0086

そのような構成により、属性の網羅性を担保しつつ、メモリの消費を抑えて高速に新たな属性を列挙することができる。

0087

また、列挙プラン生成部81は、生成された論理式構造の一部を表現する部分論理式構造との関係をグラフ構造(例えば、DAG)で表現した列挙プランを生成し、属性生成部82によって生成される新たな属性を記憶するために必要な空間サイズ(例えば、メモリコスト)を小さくしつつ、論理式構造の一部をより多く表現可能な(例えば、再利用性が高い)部分論理式構造を列挙プランの中から選択してもよい。

0088

また、属性生成部82は、列挙プラン生成部81によって選択された部分論理式構造に応じて生成される新たな属性を記憶装置(例えば、中間データ記憶部13)に記憶させ、記憶装置に記憶された属性をもとに、他の論理式構造に応じた新たな属性を生成してもよい。

0089

このようにして記憶装置に記憶される新たな属性は、適切に2分割された論理式構造に基づいて生成されるものであり、空間サイズをより小さくすることが可能なため、メモリの消費を抑えることができる。また、このようにして選択された論理式構造は、より再利用性が高いものであるため、高速に新たな属性を列挙することができる。

0090

また、属性列挙システムは、属性生成部82により生成される属性の評価を行う属性評価部(例えば、逐次的属性評価部14)を備えていてもよい。このとき、属性生成部82は、各部分論理式構造に応じて新たな属性を生成するごとに、生成した属性を属性評価部に送信してもよい。

0091

このようにすることで、評価対象となる新たな属性を保持するメモリ空間をより小さくすることが可能なため、メモリ効率を高くすることが可能になる。

0092

また、列挙プラン生成部81は、属性の組合せを表す論理式表現に加法標準形(DNF)または連言標準形(CNF)を用いてもよい。加法標準形または連言標準形は、任意の論理式を等価変換可能なため、網羅性を担保できる。

0093

図13は、本発明による属性列挙システムの他の概要を示すブロック図である。本発明による属性列挙システムは、学習データ(例えば、2値行列X)の属性と、その属性の組合せ最大数(例えば、MaxLen)とから、属性の組合せを表す論理式表現(例えば、DNF、CNF)の組み合わせ方を表現した論理式構造(例えば、DNFラベル)の集合を生成し、生成された論理式構造の一部を表現する部分論理式構造(例えば、部分DNFラベル)との関係をグラフ構造(例えば、DAG)で表現した列挙プランを生成する列挙プラン生成部91(例えば、列挙プラン生成部11)と、部分論理式構造に応じて各属性を組み合わせた新たな属性を生成する属性生成部92(例えば、DNF探索部12)とを備えている。

0094

列挙プラン生成部91は、属性生成部92によって生成される新たな属性を記憶するために必要な空間サイズ(例えば、メモリコスト)を小さくしつつ、論理式構造の一部をより多く表現可能な(例えば、再利用性が高い)部分論理式構造を列挙プランの中から選択する。

0095

そのような構成によっても、属性の網羅性を担保しつつ、メモリの消費を抑えて高速に新たな属性を列挙することができる。

0096

また、属性生成部92は、列挙プラン生成部91により選択された部分論理式構造に応じて生成される新たな属性を記憶装置(例えば、中間データ記憶部13)に記憶させ、記憶装置に記憶された属性をもとに、他の論理式構造に応じた新たな属性を生成してもよい。

0097

以上、実施形態及び実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。

実施例

0098

この出願は、2014年6月3日に出願された日本特許出願2014−114923を基礎とする優先権を主張し、その開示の全てをここに取り込む。

0099

11 列挙プラン生成部
12 DNF探索部
13 中間データ記憶部
14 逐次的属性評価部
15 出力データ記憶部

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • 株式会社大和総研ビジネス・イノベーションの「 名寄せシステムおよびプログラム」が 公開されました。( 2019/05/16)

    【課題】効率的な並列分散処理を実現することができ、サーバのスケールアウトによる性能改善を図ることが可能な名寄せシステムを提供する。【解決手段】名寄せマスタの構成データを用いて同一の名称(例えば姓名)を... 詳細

  • シグニファイホールディングビーヴィの「 汚染推定システム」が 公開されました。( 2019/05/16)

    【課題・解決手段】自動車の排気ガスに起因する汚染レベルを推定するための汚染推定システム(100)が提供される。システムは、自動車音のオーディオサンプルを含む音響センサからの使用データを取得するよう構成... 詳細

  • キヤノン株式会社の「 画像データ管理装置」が 公開されました。( 2019/05/09)

    【課題】 従来複数の画像から同じ場所に存在した人や物を判断することでしか判断し得なかった、撮影の場にあった人や物の情報を判断し、画像に紐づけて記憶することで、効率的な画像の検索を可能にすること。【解... 詳細

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ