(57)【特許請求の範囲】
【請求項１】
データ群からなる母集団の異なり数を計数するための異なり数計数方法であって、
行列生成手段が、前記母集団のサイズと、前記母集団から標本を抽出する抽出率とに基づき、前記母集団の度数毎の異なり数を示した度数異なり数ベクトルと、前記母集団から前記抽出率で抽出された標本の度数毎の異なり数を示した度数異なり数ベクトルとの関係を規定する行列を生成するステップと、
異なり数算出手段が、前記行列生成手段で生成された前記行列と、前記母集団から前記抽出率で抽出された標本とに基づいて、前記母集団の異なり数の推定値を算出するステップと、を有する異なり数計数方法。
【請求項２】
前記行列は、前記母集団の度数異なり数ベクトルとの積が前記標本の度数異なり数ベクトルとなるように要素として確率を配置した二項確率行列を行方向および列方向に圧縮した圧縮行列の逆行列であり、
前記異なり数算出手段は、前記母集団から抽出された前記標本の度数異なり数ベクトルを圧縮した圧縮度数異なり数ベクトルと前記逆行列との積により、前記母集団の推定された圧縮度数異なり数ベクトルを算出し、該母集団の推定された圧縮度数異なり数ベクトルの要素の総和を、前記母集団の異なり数の推定値とする、
請求項１に記載の異なり数計数方法。
【請求項３】
前記二項確率行列における行方向に所定行目までを切れ目とし、列方向に所定列目までを切れ目とするグループによって要素をグループ化し、グループ毎に要素をまとめた行列である圧縮行列において、前記グループの行数は行番号が大きくなると共に増加し、前記グループの列数は列番号が大きくなると共に増加する、
請求項２に記載の異なり数計数方法。
【請求項４】
前記圧縮行列は、前記二項確率行列における行方向に２のべき乗番目の要素までを切れ目とし、列方向に２のべき乗番目の要素までを切れ目とするグループによって要素をグループ化し、グループ毎に要素をまとめた行列である、
請求項３に記載の異なり数計数方法。
【請求項５】
前記圧縮行列を求める演算は、前記二項確率行列の行方向に要素の加重平均を求めると共に列方向に要素の合計値を求める演算である、請求項２から４のいずれか一項に記載の異なり数計数装置。
【請求項６】
前記行列生成手段は、式（１）により前記抽出率ｒから求まる二項確率行列Ｐの各要素を用いて、式（２）により対数圧縮二項確率行列ＬＰを求め、前記圧縮行列として用いる、請求項２から５のいずれか一項に記載の異なり数計数方法。
【数１】
0005925043.tif 000015
【請求項７】
データ群からなる母集団の異なり数を計数する異なり数計数装置であって、
前記母集団のサイズと、前記母集団から標本を抽出する抽出率とに基づき、前記母集団の度数毎の異なり数を示した度数異なり数ベクトルと、前記母集団から前記抽出率で抽出された標本の度数毎の異なり数を示した度数異なり数ベクトルとの関係を規定する行列を生成する行列生成手段と、
前記行列生成手段で生成された前記行列と、前記母集団から前記抽出率で抽出された標本とに基づいて、前記母集団の異なり数の推定値を算出する異なり数算出手段と、を有する異なり数計数装置。
【請求項８】
データ群からなる母集団の異なり数を計数させるための異なり数計数プログラムであって、
コンピュータを、
前記母集団のサイズと、前記母集団から標本を抽出する抽出率とに基づき、前記母集団の度数毎の異なり数を示した度数異なり数ベクトルと、前記母集団から前記抽出率で抽出された標本の度数毎の異なり数を示した度数異なり数ベクトルとの関係を規定する行列を生成する行列生成手段と、
前記行列生成手段で生成された前記行列と、前記母集団から前記抽出率で抽出された標本とに基づいて、前記母集団の異なり数の推定値を算出する異なり数算出手段、として機能させるための異なり数計数プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、膨大な数の要素を有するデータ群の異なり数を推定する技術に関する。
【背景技術】
【０００２】
情報処理においては膨大な個数の要素を有するデータ群を効率良く、短時間で処理することが求められる。多くの場合、情報処理に供されるデータ群には同じ種類の要素が複数含まれている。そして、データ群に同じ種類の要素が含まれていることを利用してデータ群の処理を効率化する技術がある。つまり、データ群に含まれている要素の種類の個数すなわち異なり数が情報処理に用いられることがある。データ、あるいは有限なデータセットのデータ項目に対し、そのとる相異なる値の種類の数をデータあるいはデータ項目の異なり数と言っている。
【０００３】
例えば、膨大なデータが蓄積されたデータベースにおけるデータのソーティングでは、データベースに含まれる要素の異なり数を抽出し、その異なり数を用いることにより、ソーティング処理を高速化できることが知られている。また、データベースにデータを蓄積する際に、全てのデータを個々の領域に格納するのではなく、要素の種類と度数とを記録することで全体のデータ量を圧縮することができる。その場合にも要素の種類の個数を予め計数しておくことが求められる。なお、有限なデータセットのデータ項目のとる値に対し、その出現頻度をその値の度数といっている。
【０００４】
また、サイトへの膨大なアクセスの履歴を蓄積したアクセスログから、あるサイトにアクセスしたユーザ数を抽出できれば、アクセス解析に利用することができる。その場合、アクセスログに含まれているアクセス元アドレスの異なり数がユーザ数を示すことになる。大規模なインターネットサイトにおいては、様々な外部からの攻撃や、許容範囲を超えたアクセス負荷からサーバーを守るため、常に外部からのアクセス状況の監視を行わなければならない。大量のアクセスログの中から、ユニークなアクセスホスト数を計測するのもその一環である。これはすなわち、アクセスログデータからＩＰアドレスなどのホスト識別情報の異なり数を数え上げることである。大きいサイトにおいては、一日のアクセス数が１０億件を超えており、常時全件の統計量を掌握するには、多大な計算機資源が必要となる。
【０００５】
また、翻訳ソフトウェアや辞書データベースの作成においては、膨大なコーパスから単語数を抽出し、データベースの構築に利用する。その場合、膨大なコーパスの異なり数が単語数を示すことになる。
【０００６】
また、住所管理においては、蓄積された住民の情報から住民の名字数を抽出し、住民データの管理に利用することができる。その場合、住民情報における名字の異なり数が名字数を示すことになる。
【０００７】
上述のように、データあるいはデータ項目の異なり数を計数することはデータ処理において非常に有用である。しかしながら、データ群が膨大であれば異なり数の計数にも膨大な処理量や記憶容量が必要となる。そのため、膨大なデータ群の異なり数を効率良く計数する技術が求められている。
【０００８】
そのような要求に対して、特許文献１には、様々なデータ群の異なり数を高い精度で推定する技術が開示されている。特許文献１の技術は、小さい異なり数の計数に適した計数法と、大きい異なり数の計数に適した計数法とを併用することにより、高い精度で異なり数を推定しようとするものである。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００８−５９２９３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
特許文献１の技術は、単一の異なり数計数方法では、様々なデータ群の異なり数を高い精度で計数できないことを前提とし、同じデータ群の異なり数を２つの計数法で推定している。しかし、そのために冗長な処理を行うことになり、処理効率が良くなかった。
【００１１】
本発明の目的は、データ群の異なり数を効率良く推定する技術を提供することである。
【課題を解決するための手段】
【００１２】
本発明の一態様による異なり数計数方法は、データ群からなる母集団の異なり数を計数するための異なり数計数方法であって、行列生成手段が、前記母集団のサイズと、前記母集団から標本を抽出する抽出率とに基づき、前記母集団の度数毎の異なり数を示した度数異なり数ベクトルと、前記母集団から前記抽出率で抽出された標本の度数毎の異なり数を示した度数異なり数ベクトルとの関係を規定する行列を生成するステップと、異なり数算出手段が、前記行列生成手段で生成された前記行列と、前記母集団から前記抽出率で抽出された標本とに基づいて、前記母集団の異なり数の推定値を算出するステップと、を有している。
【発明の効果】
【００１３】
本発明によれば、予め算出した行列と母集団から抽出した標本とを使って母集団の異なり数を推定することができるので、全ての要素を分析することなく効率的に異なり数を推定することができる。
【図面の簡単な説明】
【００１４】
【図１】本実施形態による異なり数計数装置のブロック図である。
【図２】本実施形態の異なり数計数装置の動作を示すフローチャートである。
【図３】本実施形態の異なり数計数装置１０を組み込んだデータ分析装置２０の一例を示すブロック図である。
【図４】アクセスログの一例を模式的に示した図である。
【図５】アクセス解析結果データの一例を模式的に示した図である。
【図６】母集団から標本を抽出する様子を示す図である。
【図７】ｆ−度数異なり数Ｕｆについて説明するための図である。
【図８】二項確率行列による近似の原理をトイモデルで示した図である。
【図９】二項確率行列を圧縮する様子を示す図である。
【図１０】二項確率行列における要素の分布の様子を示す図である。
【図１１】度数異なり数ベクトルを圧縮する様子を示す図である。
【図１２】対数圧縮二項確率行列による近似の原理を示した図である。
【図１３】推定実験１において抽出率を変えて推定精度を比較した結果を示す図である。
【図１４】推定実験１において変数と抽出率を変えて推定精度を比較した結果を示す図である。
【図１５】図１４の結果における対真値をグラフ化した図である。
【図１６】推定実験２における推定実験結果を示す図である。
【発明を実施するための形態】
【００１５】
本発明の基本的な実施形態について図面を参照して説明する。
【００１６】
図１は、本実施形態による異なり数計数装置のブロック図である。本実施形態の異なり数計数装置１０は、膨大なデータ群からなる母集団の異なり数を計数する装置である。
【００１７】
母集団は、例えば、データベースに蓄積された膨大なデータ、あるいはそのデータが複数の項目で構成されている場合には各項目の値を元とする集合である。データベースに蓄積されたデータ数が母集団のサイズである。母集団には同じ値を持ったデータが含まれている可能性があるため、母集団の異なり数は母集団のサイズと等しいかあるいはそれよりも小さい値である。
【００１８】
本実施形態の異なり数計数装置１０は異なり数の計数に近似を用いる。近似の方法は母集団から所定の抽出率で抽出した標本群から母集団の異なり数を推定するものである。抽出率は予め与えられるものとする。
【００１９】
ここで、母集団や母集団から抽出された標本群のようなデータ群について、度数異なり数ベクトルというものを定義する。度数異なり数ベクトルは、度数毎の異なり数を示したベクトルである。度数は、同じ値のデータが幾つあるかを示すものである。よって、度数異なり数ベクトルは、同じ値のものが何個あるデータが何種類あるかを示していると言える。
【００２０】
ここでは母集団の度数異なり数ベクトルは未知であるが、標本の度数異なり数ベクトルは既知である。
【００２１】
図１を参照すると、異なり数計数装置１０は行列生成部１１および異なり数算出部１２を有している。
【００２２】
行列生成部１１は、母集団のサイズと、母集団から標本を抽出する抽出率とに基づき、母集団の度数毎の異なり数を示した度数異なり数ベクトルと、母集団からその抽出率で抽出された標本の度数毎の異なり数を示した度数異なり数ベクトルとの関係を二項確率によって規定する行列を生成する。この行列については後述において段階的に詳しく説明する。
【００２３】
異なり数算出部１２は、行列生成部１１で生成された行列と、母集団から抽出率で抽出された標本とに基づいて、母集団の異なり数の推定値を算出する。
【００２４】
本実施形態によれば、予め算出した行列と母集団から抽出した標本とを使って母集団の異なり数を推定することができるので、全ての要素を分析することなく効率的に異なり数を推定することができる。
【００２５】
以下、各部における、より具体的な動作について説明する。
【００２６】
上述の行列を、二項確率行列を対数的に圧縮したという意味で対数圧縮二項確率行列と呼ぶことにする。二項確率行列は、母集団の度数異なり数ベクトルとの積が標本の度数異なり数ベクトルとなるように、要素として確率を配置した行列のことをいう。対数圧縮二項確率行列は、その二項確率行列を行方向および列方向に圧縮した圧縮行列である。
【００２７】
そして、異なり数算出部１２は、母集団から抽出された標本の度数異なり数ベクトルを圧縮して、それを対数圧縮度数異なり数ベクトルを求め、その標本の対数圧縮度数異なり数ベクトルと、対数圧縮二項確率行列の逆行列との積により、母集団の推定された対数圧縮度数異なり数ベクトルを算出する。更に、異なり数算出部１２は、その母集団の推定された対数圧縮度数異なり数ベクトルの要素の総和を、母集団の異なり数の推定値とする。対数圧縮度数異なり数ベクトルは、度数異なり数ベクトルを対数圧縮二項確率行列に合うように圧縮したベクトルである。
【００２８】
このように、母集団の度数異なり数ベクトルと標本群の度数異なり数ベクトルとの関係を示す二項確率行列を行方向および列方向に圧縮した対数圧縮二項確率行列を用いて母集団の異なり数を算出するので、少ない処理量で効率良く異なり数を算出することができる。
【００２９】
その際、行列生成部１１は、対数圧縮二項確率行列の１つの要素にまとめる二項確率行列における行数は、行番号が大きくなると共に増加し、同じく対数圧縮二項確率行列の１つの要素にまとめる二項確率行列における列数は、列番号が大きくなると共に増加するように圧縮を行う。行番号や列番号が大きくなるにつれて変化が緩やかになる二項確率行列を、行番号や列番号が大きくなるにつれて大きな単位で１つの要素にまとめるので、精度の劣化を抑えつつ処理量を大きく低減することが可能である。
【００３０】
より好ましくは、行列生成部１１は、対数圧縮二項確率行列の１つの要素にまとめる二項確率行列における行数は、行番号が大きくなると共に指数関数的に増加し、対数圧縮二項確率行列の１つの要素にまとめる二項確率行列における列数は、列番号が大きくなると共に指数関数的に増加するように圧縮を行うとよい。例えば、２のべき乗個目を切れ目として要素を区切って圧縮を行うとよい。行番号や列番号が大きくなるにつれて対数的に変化が緩やかになる二項確率行列を、行番号や列番号が大きくなるにつれて指数関数的に大きな単位で１つの要素にまとめるので、精度の劣化を抑えつつ処理量を大きく低減することが可能である。
【００３１】
本実施形態の異なり数計数装置の基本的な動作の流れをフローチャートを用いて説明する。
【００３２】
図２は、本実施形態の異なり数計数装置の動作を示すフローチャートである。図２を参照すると、異なり数計数装置１０は、まず、行列生成部１１によって、上述のような二項確率による行列を生成する（ステップ１０１）。続いて、異なり数計数装置１０は、その行列と標本とに基づいて、母集団の異なり数を算出する。
【００３３】
次に、本実施形態の異なり数計数装置による具体的な演算処理について説明する。
【００３４】
サイズがＮの母集団の度数異なり数ベクトルＵを式（１）で表し、Ｍ個の標本からなる集団の度数異なり数ベクトルＶを式（２）で表わす。
【００３５】
【数１】
0005925043.tif 000002
【００３６】
【数２】
0005925043.tif 000003
【００３７】
母集団から所定の抽出率ｒで元を抽出したときに、母集団の中に同じものがｎ個ある元が標本としてｋ個抽出される確率を要素とするＮ次行列Ｐが二項確率行列である。この二項確率行列は、母集団の度数毎に、標本の度数毎の発生確率を表した行列である。二項確率行列は式（３）で表すことができる。ｉ＜ｊならばＰｉｊ＝０である。
【００３８】
【数３】
0005925043.tif 000004
【００３９】
これらＵ、Ｖ、Ｐは式（４）の関係にあり、Vが与えられると、式（５）によりＵを推定することができる。
【００４０】
【数４】
0005925043.tif 000005
【００４１】
【数５】
0005925043.tif 000006
【００４２】
このままでは母集団のサイズＮが膨大なときには、二項確率行列Ｐの巨大なものとなり、逆行列Ｐ−１を求めることが難しい。そこで二項確率行列Ｐを対数化によって圧縮した対数圧縮二項確率行列ＬＰを導入する。対数圧縮二項確率行列ＬＰは、二項確率行列Ｐに対し、列方向に（２のべき乗）列を区切りとして確率値を合算し、行方向に（２のべき乗÷抽出率）行を区切りとして確率値を平均した行列である。二項確率行列を対数圧縮二項確率行列に圧縮する演算は、行方向に加重平均を求めると共に列方向にの合計値を求める演算としてもよい。各要素の重みは適宜設定すればよい。あるいは、全ての要素に均一の重みを与えても良い。
【００４３】
この二項確率行列におけるグループ化して１つにまとめる要素は、行方向および列方向に２のべき乗番目までを切れ目とするグループでまとめられ、グループは行方向および列方向に進むにつれて要素の個数が増大する。
【００４４】
対数圧縮二項確率行列ＬＰは式（６）で表わすことができる。
【００４５】
【数６】
0005925043.tif 000007
【００４６】
また、度数異なり数ベクトルＶも、対数圧縮二項確率行列ＬＰと同様に対数化による圧縮を行う。圧縮化された度数異なり数ベクトル（対数圧縮度数異なり数ベクトル）ＬＶは式（７）で表わすことができる。標本の度数異なり数ベクトルを（２のべき乗）個目を区切りとして、値を合算したものを標本の対数圧縮度数異なり数ベクトルという。抽出率ｒの標本をもつ母集団の度数異なり数ベクトルを（２のべき乗÷抽出率）個目を区切りとして、値を合算したものを母集団の対数圧縮度数異なり数ベクトルという。
【００４７】
【数７】
0005925043.tif 000008
【００４８】
そして、Ｕの推定値は、ＬＰの逆行列ＬＰ−１を用いて、式（８）により求めることができる。
【００４９】
【数８】
0005925043.tif 000009
【００５０】
以上のような演算処理により、行列生成部１１が式（６）に示される対数圧縮二項確率行列ＬＰの逆行列ＬＰ−１を生成し、異なり数算出部１２が式（８）により、母集団の度数異なり数ベクトルＵの推定値を算出する。
【００５１】
なお、ここでは、演算およびその考え方の理解を容易にするために、二項確率行列Ｐを求め、それを圧縮することにより対数圧縮二項確率行列ＬＰを生成するような説明をしている。しかし実際には、行列生成部１１は、一旦、二項確率行列Ｐを求めるということをせず、直接、対数圧縮二項確率行列ＬＰを生成する。
【００５２】
図３は、本実施形態の異なり数計数装置１０を組み込んだデータ分析装置２０の一例を示すブロック図である。図３を参照すると、データ分析装置２０は、図１と同じ行列生成部１１および異なり数算出部１２に加えて、記憶部２１、サイズ算出部２２、標本抽出部２３、およびデータ分析部２４を有している。
【００５３】
記憶部２１は、母集団のデータ群を蓄積している。一例として、あるサーバへのアクセスデータを蓄積したアクセスログのデータ群を母集団とする。図４は、アクセスログの一例を模式的に示した図である。このアクセスログは、あるサーバへのアクセスデータを時系列に蓄積したものである。アクセスログには、個々のアクセスについて、アクセス番号（Ｎｏ．）、発ＩＰアドレス、およびユーザＩＤを含む各種項目が蓄積されている。アクセス番号は、サーバへのアクセスが発生した順に各アクセスに付与されるシリアル番号である。発ＩＰアドレスは、アクセス元のＩＰアドレスであり、アクセス元のユーザの識別に用いられる。利用時間は、そのアクセスによるサイト閲覧等の利用が継続した時間である。
【００５４】
サイズ算出部２２は、記憶部２１に蓄積されている母集団のデータ群のサイズすなわち元の個数を算出し、行列生成部１１および標本抽出部２３に通知する。例えば、サイズ算出部２２は、ログカウンタを有し、記憶部２１に１件のアクセスの情報が格納されるたびに、ログカウンタをカウントアップすることにより、データ群のサイズを計数することにしてもよい。あるいは、サイズ算出部２２は、母集団のデータ群のサイズの情報が必要になったときに、記憶部２１におけるアクセスログの有効領域の大きさからアクセスログのサイズを算出することにしてもよい。
【００５５】
標本抽出部２３は、サイズ算出部２２から通知された母集団のサイズと、与えられた抽出率とに基づて、母集団から抽出すべき標本の個数を算出し、その個数の標本を記憶部２１の母集団のデータ群から抽出する。例えば、母集団のサイズに抽出率を乗算すれば、母集団から抽出すべき標本の個数が得られる。抽出された標本は、異なり数算出部１２に通知される。
【００５６】
行列生成部１１は、与えられた抽出率と、サイズ算出部２２から通知されたサイズとに基づいて、対数圧縮二項確率行列ＬＰの逆行列ＬＰ−１を生成し、異なり数算出部１２に通知する。具体的には、通知されたサイズによって二項確率行列Ｐの行数および列数が定まる。例えば、通知されたサイズ以上であり、対数圧縮における圧縮の単位が完成する最小限の行数および列数を用いることにしてもよい。式（３）によって、抽出率から二項確率行列Ｐの各要素が定まる。更に、式（６）によって、二項確率行列Ｐの各要素から対数圧縮二項確率行列ＬＰが定まる。
【００５７】
異なり数算出部１２は、行列生成部１１から通知された逆行列ＬＰ−１と、標本抽出部２３で抽出された標本群とに基づいて、母集団の異なり数Ｕの推定値を算出する。標本群を分析することにより、その度数異なり数ベクトルＶを算出することができる。式（７）によって、その度数異なり数ベクトルＶを対数圧縮し、対数圧縮度数異なり数ベクトルＬＶを得ることができる。そして、式（８）によって、この対数圧縮二項確率行列ＬＰと、対数圧縮二項確率行列ＬＶの逆行列ＬＰ−１とから、母集団の異なり数Ｕの推定値を算出することができる。算出された母集団の異なり数Ｕの推定値はデータ分析部２４に通知される。例えば、異なり数算出部１２は、算出した母集団の異なり数Ｕの推定値を記憶部２１に記録し、データ分析部２４は、記憶部２１からその異なり数Ｕの推定値を読み出す。
【００５８】
データ分析部２４は、異なり数算出部１２で算出された異なり数の推定値を利用して、記憶部２１に蓄積されてるデータ群の分析を行う。例えば、データ群のソーティングにおいて異なり数を利用することでソーティング処理を高速化することができる。例えば、データ分析部２４は、例えば、図４に示したアクセスログから、アクセス解析結果データを生成してもよい。図５は、アクセス解析結果データの一例を模式的に示した図である。アクセス解析結果データには、各ユーザについてのユーザＩＤ、アクセス回数、および平均利用時間等の項目のデータが含まれている。ユーザの異なり数がユーザ数を示し、そのユーザ数分の記憶領域を確保することが必要となる。データ分析部２４は、例えば、ユーザ数分の記憶領域を予め確保し、各ユーザについての各項目のデータを算出し、記録することにしてもよい。
【００５９】
続いて、上述した実施形態における更に具体的な実施例について説明する。
【実施例】
【００６０】
本実施例の異なり数計数装置の基本的な構成は図１に示したものと同じであり、基本的な動作は図２に示したものと同じである。以下、本実施例における各詳細処理について説明する。
【００６１】
図６は、母集団から標本を抽出する様子を示す図である。ここでは標本の抽出率を５０％としている。図中で大きな文字で書かれた要素が標本として抽出される要素である。
【００６２】
度数が大きいければ、母集団における異なり数と標本における異なり数はほとんど変わらない。図６（ａ）では、母集団の異なり数と標本の異なり数がともに４であり、変わっていない。一方、度数が小さいと、標本における異なり数は母集団における異なり数から減少する。図６（ｂ）では、母集団の異なり数が４であり、標本の異なり数が２である。
【００６３】
度数ｎの要素からｋ個の要素が抽出される確率は、式（９）の二項確率で示すことができる。
【００６４】
【数９】
0005925043.tif 000010
【００６５】
ここで、要素の度数がｆである異なり数をｆ−度数異なり数Ｕｆと呼ぶことにする。
【００６６】
図７は、ｆ−度数異なり数Ｕｆについて説明するための図である。図７を参照すると、Ａの度数だけが１０なので、１０−度数異なり数Ｕ１０＝１である。また、ＢとＣの度数が３なので、３−度数異なり数Ｕ３＝２である。ＤとＥとＦの度数が２なので、２−度数異なり数Ｕ２＝３である。ＧとＨとＩとＪとＫの度数が１なので、５−度数異なり数Ｕ１＝５である。また、全体の異なり数は全てのｆ−度数異なり数の合計なので１１である。
【００６７】
式（１）や式（２）などで上述した度数異なり数ベクトルは、ｆ−度数異なり数を度数毎の要素とするベクトルである。
【００６８】
標本のｋ−度数異なり数の期待値Ｖｋ＾は、母集団のｎ−度数異なり数Ｕｎと、式（９）の二項確率とを用いて、式（１０）のように示すことができる。
【００６９】
【数１０】
0005925043.tif 000011
【００７０】
サイズがＮの母集団の度数異なり数ベクトルＵ＝（Ｕ１，・・・，ＵＮ）と、標本の度数異なり数ベクトルＶ＝（Ｖ１，・・・，ＶＮ）は、上述のように、それぞれ式（１）と式（２）に示される。
【００７１】
ここで、式（３）として上述した、二項確率を要素とするＮ次行列である二項確率行列Ｐを利用すると、式（４）が成り立つ。よって、式（５）によって、標本の異なり数Ｕの推定値Ｕ＾は、式（５）によって得られる。
【００７２】
【数１１】
0005925043.tif 000012

【００７３】
【数１２】
0005925043.tif 000013

【００７４】
【数１３】
0005925043.tif 000014
【００７５】
図８は、二項確率行列による近似の原理をトイモデルで示した図である。
【００７６】
上述のように、本発明の実施形態および実施例では、二項確率行列を用いて、標本の度数異なり数ベクトルから、母集団の度数異なり数ベクトルを近似的に算出するものである。この二項確率行列はは圧縮を行っていないものである。
【００７７】
図８参照すると、サイズ２２２の母集団から抽出率５０％で標本を抽出している。
【００７８】
母集団の度数異なり数ベクトルを見ると、１−度数異なり数＝１２１であり、２−度数異なり数＝２７であり、３−度数異なり数＝１０であり、４−度数異なり数＝３であり、５−度数異なり数＝１である。母集団全体の異なり数は１６２である。ただし、実際には母集団の各異なり数は未知である。
【００７９】
実際に抽出された標本の度数異なり数ベクトルを見ると、１−度数異なり数＝８７であり、２−度数異なり数＝１０であり、３−度数異なり数＝３であり、４−度数異なり数＝０であり、５−度数異なり数＝０である。母集団全体の異なり数は１００である。この標本の各異なり数は既知である。
【００８０】
この標本の度数異なり数ベクトルと、二項確率行列（圧縮していないもの）の逆行列との積として算出される、母集団の度数異なり数ベクトルの推定値は、１−度数異なり数＝１５２であり、２−度数異なり数＝４であり、３−度数異なり数＝２４であり、４−度数異なり数＝０であり、５−度数異なり数＝０である。母集団全体の異なり数の推定値は１８０となり、ある程度の誤差内で異なり数の推定ができていることが分かる。
【００８１】
図９は、二項確率行列を圧縮する様子を示す図である。
【００８２】
図９の右側には、圧縮されていない二項確率行列の一部が示され、左側には、その二項確率行列を圧縮した対数圧縮二項確率行列が示されている。
【００８３】
右側の二項確率行列は、母集団の度数異なり数ベクトルとの積が標本の度数異なり数ベクトルとなるように要素として二項確率を配置した行列である。この二項確率行列を行方向および列方向に圧縮したものが、左側の対数圧縮二項確率行列である。
【００８４】
二項確率行列の複数の要素が対数圧縮二項確率行例では１つの要素にまとめられている。二項確率行列の複数の要素が対数圧縮二項確率行列の１つの要素にまとめられる様子が図９では破線矢印で示されている。
【００８５】
対数圧縮二項確率行列の１つの要素にまとめる二項確率行列における行数は、行番号が大きくなると共に指数関数的に増加し、対数圧縮二項確率行列の１つの要素にまとめる二項確率行列における列数は、列番号が大きくなると共に指数関数的に増加するように圧縮を行っている。まとめる要素の個数が増えれば処理量削減の効果が増大する。
【００８６】
図１０は、二項確率行列における要素の分布の様子を示す図である。図１０において、二項確率で示される要素の値の変化が山型の曲線によって示されている。これを見ると、二項確率行列では、行番号や列番号が大きくなるにつれて対数的に変化が緩やかになっていることが分かる。このように行番号や列番号が大きくなるにつれて対数的に変化が緩やかになる二項確率行列を、本実施例では、行番号や列番号が大きくなるにつれて指数関数的に大きな単位で１つの要素にまとめるので、精度の劣化を抑えつつ処理量を大きく低減することが可能となっている。
【００８７】
図１１は、度数異なり数ベクトルを圧縮する様子を示す図である。
【００８８】
図１１を参照すると、母集団の度数異なり数ベクトルにおける度数３〜４の２つの要素が、母集団の対数圧縮度数異なり数ベクトルにおける１つの要素に圧縮されている。ここでの圧縮は、３−度数異なり数と４−度数異なり数を合計して１つの要素にする演算である。
【００８９】
同じように、標本の度数異なり数ベクトルにおける度数５〜８の４つの要素が、母集団の対数圧縮度数異なり数ベクトルにおける１つの要素に圧縮されている。圧縮は、５３−度数異なり数〜８−度数異なり数を合計して１つの要素にする演算である。
【００９０】
図１２は、対数圧縮二項確率行列による近似の原理を示した図である。
【００９１】
本実施例では、圧縮二項確率行列を用いて、標本の度数異なり数ベクトルから、母集団の度数異なり数ベクトルを近似的に算出するものである。この例では、抽出率が１／２５６である。また、図８とは異なり、この例では行列および度数異なり数ベクトルの圧縮を行ってる。
【００９２】
図１２を参照すると、サイズ＝７５２４６８２の母集団から抽出率１／２５６で標本を抽出している。
【００９３】
母集団の対数圧縮度数異なり数ベクトルを見ると、２５６−度数異なり数＝１７０８であり、５１２−度数異なり数＝４５４であり、１０２４−度数異なり数＝６４であり、２０４８−度数異なり数＝２１である。母集団全体の異なり数は２２４８である。ただし、実際には母集団の各異なり数は未知である。
【００９４】
実際に抽出された標本の対数圧縮度数異なり数ベクトルを見ると、１−度数異なり数＝４８０であり、２−度数異なり数＝２１３であり、４−度数異なり数＝１３４であり、８−度数異なり数＝３４である。母集団全体の異なり数は１００である。この標本の各異なり数は既知である。
【００９５】
この標本の度数異なり数ベクトルと、二項確率行列（圧縮していないもの）の逆行列との積として算出される、母集団の度数異なり数ベクトルの推定値は、１−度数異なり数＝１５２であり、２−度数異なり数＝４であり、３−度数異なり数＝２４であり、４−度数異なり数＝０である。母集団全体の異なり数の推定値は１７９０となり、ある程度の誤差内で異なり数の推定ができていることが分かる。
【００９６】
以下、データを用いて異なり数計数において異なり数の推定精度がどの程度かを実験結果によって示す。
（推定実験１）
【００９７】
商品購入の取引で記録される購買取引データにおける異なり数の推定精度の実験結果について説明する。
【００９８】
母集団として、１０種類のデータ項目をもつ１０００万件の購買履歴データを用いた。すなわち、この購買取引データには、取引日、取引店、取引額など様々な変数があるが、ここではその中から１０個の変数（データ項目）を選んだ。また、抽出率として、１／４、１／１６、１／６４、１／２５６、１／１０２４について計算を行った。
【００９９】
図１３は、推定実験１において抽出率を変えて推定精度を比較した結果を示す図である。変数は、ある一つの変数ｖ５を固定的に用いている。対真値は、真の値に対する推定値を示している。
【０１００】
図１３を見て分かるように、抽出率が下がると推定精度の低下するが、１／６４程度の抽出率であれば推定精度６５％が得られている。
【０１０１】
図１４は、推定実験１において変数と抽出率を変えて推定精度を比較した結果を示す図である。図１５は、図１４の結果における対真値をグラフ化した図である。図１５において、推定誤差が３５％に収まってるプロットが破線で囲まれている。これを見て分かるように、実験に用いた１０個の変数のうち８個の変数において、抽出率１／６５以上では、推定誤差が３５％以内に収まっていることが分かる。
（推定実験２）
【０１０２】
全国の世帯数を母集団とし、抽出率１／１６の世帯の苗字データから、全国世帯の苗字数を推定した実験結果について説明する。
【０１０３】
全国の世帯数は、国勢調査により、約５０００万世帯であることが分かっている。抽出率１／１６の標本として、３１２３９７９世帯の苗字データを用いた。ただし、無作為抽出は行っていない。
【０１０４】
図１６は、推定実験２における推定実験結果を示す図である。異なり数が７０５０６の標本から算出した母集団の異なり数は１３１２６５である。
【０１０５】
苗字の個数には、十数万から３０万と諸説がある。この幅の広さには新字と旧字の扱いによる差異が大きく影響している。したがって、旧字を用いた苗字と新字を用いた苗字を合算すると、その幅の中の小さい方の値になることが考えられる。
【０１０６】
本推定実験では、旧字を用いた苗字を新字を用いた苗字に寄せるように合算している。したがって、１３１２６５という推定値は、十数万という苗字数とよく合っていると言える。
【０１０７】
以上、上述した本発明の実施形態および実施例は、本発明の説明のための例示であり、本発明の範囲をそれらの実施形態あるいは実施例のみに限定する趣旨ではない。当業者は、本発明の要旨を逸脱することなしに、他の様々な態様で本発明を実施することができる。
【０１０８】
また、上述した実施形態および実施例の装置は、装置を構成する各部の処理手順を規定したソフトウェアプログラムをコンピュータに実行させることにより実現することができるものである。その場合、各部の間におけるデータの通知はメモリやレジスタ等のデータ格納領域を介して行われることにしてもよい。送り側の処理において、通知しようとするデータをデータ格納領域に格納し、受け側の処理において、そのデータ格納領域からデータを読み出せばよい。
【符号の説明】
【０１０９】
１０…異なり数計数装置、１１…行列生成部、１２…異なり数算出部、２０…データ分析装置、２１…記憶部、２２…サイズ算出部、２３…標本抽出部、２４…データ分析部
【図１】
0005925043.tif 000016
【図２】
0005925043.tif 000017
【図３】
0005925043.tif 000018
【図４】
0005925043.tif 000019
【図５】
0005925043.tif 000020
【図６】
0005925043.tif 000021
【図７】
0005925043.tif 000022
【図８】
0005925043.tif 000023
【図９】
0005925043.tif 000024
【図１０】
0005925043.tif 000025
【図１１】
0005925043.tif 000026
【図１２】
0005925043.tif 000027
【図１３】
0005925043.tif 000028
【図１４】
0005925043.tif 000029
【図１５】
0005925043.tif 000030
【図１６】
0005925043.tif 000031