特許ウォッチ

公開番号2024124254
公報種別公開特許公報(A)
公開日2024-09-12
出願番号2023032272
出願日2023-03-02
発明の名称探索プログラム、探索方法および情報処理装置
出願人富士通株式会社
代理人弁理士法人酒井国際特許事務所
主分類G06F 17/15 20060101AFI20240905BHJP(計算;計数)
要約【課題】データ間に相関がある条件の組み合わせ探索の高速化を支援する。
【解決手段】実施形態の探索プログラムは、各データを行、当該データに含まれる属性が所定の条件を満たすか否かを列とする行列に基づいて各データにおいて相関を有する1または複数の条件を探索する際に、算出する処理と、ソートする処理と、割り当てる処理とをコンピュータに実行させる。算出する処理は、行列の列ごとに、条件を満たすデータ数を算出する。ソートする処理は、算出した列ごとのデータ数に基づいて、行列の列の並び順をソートする。割り当てる処理は、ソートした列の並び順に基づいて、列に対応する条件の組み合わせを、相関の有無を計算する各プロセスに割り当てる。
【選択図】図1
特許請求の範囲【請求項１】
各データを行、当該データに含まれる属性が所定の条件を満たすか否かを列とする行列に基づいて前記各データにおいて相関を有する１または複数の条件を探索する際に、
前記行列の列ごとに、前記条件を満たすデータ数を算出し、
算出した前記列ごとのデータ数に基づいて、前記行列の列の並び順をソートし、
ソートした前記列の並び順に基づいて、前記列に対応する条件の組み合わせを、前記相関の有無を計算する各プロセスに割り当てる、
処理をコンピュータに実行させることを特徴とする探索プログラム。
続きを表示（約 850 文字）【請求項２】
前記割り当てる処理は、前記列の並び順に１または複数の列を選択して得られた前記条件の組み合わせを順に前記各プロセスに割り当てる、
ことを特徴とする請求項１に記載の探索プログラム。
【請求項３】
前記行列は、前記条件を満たすか否かを０または１の２値で表し、
前記算出する処理は、前記行列の列ごとに、値が１である行数をカウントして前記データ数を算出する、
ことを特徴とする請求項１に記載の探索プログラム。
【請求項４】
前記各プロセスは、前記データ数が所定値以上である組み合わせについて前記相関の有無を計算する、
ことを特徴とする請求項１に記載の探索プログラム。
【請求項５】
各データを行、当該データに含まれる属性が所定の条件を満たすか否かを列とする行列に基づいて前記各データにおいて相関を有する１または複数の条件を探索する際に、
前記行列の列ごとに、前記条件を満たすデータ数を算出し、
算出した前記列ごとのデータ数に基づいて、前記行列の列の並び順をソートし、
ソートした前記列の並び順に基づいて、前記列に対応する条件の組み合わせを、前記相関の有無を計算する各プロセスに割り当てる、
処理をコンピュータが実行することを特徴とする探索方法。
【請求項６】
各データを行、当該データに含まれる属性が所定の条件を満たすか否かを列とする行列に基づいて前記各データにおいて相関を有する１または複数の条件を探索する際に、
前記行列の列ごとに、前記条件を満たすデータ数を算出し、
算出した前記列ごとのデータ数に基づいて、前記行列の列の並び順をソートし、
ソートした前記列の並び順に基づいて、前記列に対応する条件の組み合わせを、前記相関の有無を計算する各プロセスに割り当てる、
処理を実行する制御部を含むことを特徴とする情報処理装置。

発明の詳細な説明【技術分野】
【０００１】
本発明の実施形態は、探索プログラム、探索方法および情報処理装置に関する。
続きを表示（約 1,400 文字）【背景技術】
【０００２】
従来、消費者の購買傾向などを分析するため、顧客の購買履歴などのサンプルデータ群をもとに、サンプルデータ間に相関がある条件の組み合わせを求めるデータ解析が行われている。
【０００３】
図７は、従来の相関計算を説明する説明図である。図７に示すように、従来の情報処理装置では、サンプルデータ群をもとに、サンプルデータのそれぞれが各条件を満たすか否かを示す行列Ｄ１００を作成する。この行列Ｄ１００の各行は、識別情報（サンプルｉｄ）で識別されるサンプルデータを示す。また、行列Ｄ１００の各列は、サンプルデータに含まれる属性（例えば年齢）が所定の条件（例えば２０歳未満）を満たすか否かを１／０の２値で示す。
【０００４】
従来の情報処理装置では、探索対象とする条件の組み合わせについて、行列Ｄ１００をもとに、組み合わせた条件に該当するサンプルデータを抽出する。例えば、「年齢が２０歳未満」、「体重が５０ｋｇ以上」の条件の組み合わせについては、両方の条件に対応する２列の値が１（条件を満たす）であるサンプルデータ（図示例ではｉｄ＝１，４）が抽出される。ついで、従来の情報処理装置では、抽出したサンプルデータについて、２つの属性を抜き出して属性間の相関を示す相関係数を計算する。従来の情報処理装置は、この相関係数の計算結果をもとに、相関係数が閾値を超える属性ペアが１または複数ある場合、探索対象とする条件の組み合わせ（例えば、「年齢が２０歳未満」、「体重が５０ｋｇ以上」）についてサンプルデータ間に相関があるものとする。
【０００５】
このように条件を組み合わせて相関計算を行う探索は、条件の数をｄｘ、組み合わせる条件の数をｋとすると、
ｄｘ
Ｃ
ｋ
回実施される。このため、ｄｘやｋが大きくなると探索回数は爆発的に増加する。例えば、ｄｘ＝１００００、ｋ＝３とすると、
１００００
Ｃ
３
＝１．３３×１０
１２
となる。
【０００６】
この探索は、条件の組み合わせごとに独立して行うことができるため、条件の組み合わせを各プロセスに割り当てて並列化することで、処理を高速化することができる。
【先行技術文献】
【特許文献】
【０００７】
特開２００３－４４２８０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上記の従来技術では、並列化したプロセス間の計算量に不均衡が生じ、プロセス間の計算時間にばらつきが生じるという問題がある。このため、計算量が過大なプロセスの計算時間によって全プロセスの終了時間が遅くなり、結果的に処理の高速化が実現できないことがある。
【０００９】
図８は、従来の相関計算を説明する説明図である。図８に示す行列Ｄ１００に対し、従来の情報処理装置が条件（列）の組を順に２プロセス（ｒａｎｋ０，ｒａｎｋ１）に割り当てて並列に処理する場合を考える。
【００１０】
条件（列）の組み合わせ数がｋ＝１の場合、ｒａｎｋ０のプロセスに割り当てる組み合わせは、（ｘ０）、（ｘ２）、（ｘ４）となる。また、ｒａｎｋ１のプロセスに割り当てる組み合わせは、（ｘ１）、（ｘ３）、（ｘ５）となる。
（【００１１】以降は省略されています）

関連特許