(57)【要約】  消費者トランザクションルールの冗長性フィルタリングを、様々な手法を介して達成することができる。サポートバンドを使用して、冗長性分析の間にルールをクラスタ化することができる。ビットベクトルを使用して、冗長なルールを識別することができる。任意化（anyfication）などの他の特徴を使用して、利点を得ることができる。種々のベンチマークを使用して、改良された性能を実証することができる。
2015508918.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータによって少なくとも部分的に実施される方法であって、
複数の候補消費者トランザクションルールエントリを受信するステップであり、前記候補消費者トランザクションルールエントリは、アプリケーションストア消費者トランザクションに関連付けられた同様の消費者特性値の発生についてのそれぞれのサポート率を示すルールを含む、ステップと、
前記候補消費者トランザクションルールエントリの少なくとも１つを冗長として識別するステップであり、該識別するステップは、前記候補消費者トランザクションルールエントリのうちの２つのサポート率が十分に近接することを判定するステップと、前記候補消費者トランザクションルールエントリのうちの前記２つの間の包含関係を識別するステップとを含む、ステップと、
前記候補消費者トランザクションルールエントリをフィルタするステップであり、該フィルタするステップは、前記少なくとも１つの前記の冗長な候補消費者トランザクションルールエントリを除去するステップを含む、ステップと、
を含む方法。
【請求項２】
前記候補消費者トランザクションルールエントリをフィルタするステップは、フィルタされたルールエントリを生成し、当該方法は、
前記フィルタされたルールエントリをユーザインタフェース内に表示するステップ
をさらに含む請求項１に記載の方法。
【請求項３】
前記フィルタされたルールエントリをサポート率でランク付けするステップ、
をさらに含み、
前記表示するステップは、サポート率でランク付けされたとおりに上位λ個のルールエントリを表示する、
請求項２に記載の方法。
【請求項４】
前記サポート率が十分に近接することを判定するステップが、包含関係を識別するステップの後に実行される、
請求項１に記載の方法。
【請求項５】
前記候補消費者トランザクションルールエントリのうちの２つのサポート率が十分に近接することを判定するステップは、サポート閾値εに従って、前記候補消費者トランザクションルールエントリをサポートバンドにクラスタ化するステップを含む、
請求項１に記載の方法。
【請求項６】
領域特化型のヒューリスティックに基づいて、前記候補消費者トランザクションルールエントリを精緻化するステップ
をさらに含む請求項１に記載の方法。
【請求項７】
第１の候補消費者トランザクションルールエントリに存在せず、しかし他の候補消費者トランザクションルールエントリに存在する１又は複数の消費者特性値について、任意という値を示すステップ
をさらに含む請求項１に記載の方法。
【請求項８】
１又は複数のプロセッサと、
メモリと、
１又は複数のコンピュータ読取可能記憶媒体に記憶された複数の候補消費者トランザクションルールエントリであり、該候補消費者トランザクションルールエントリは、アプリケーションストア消費者トランザクションに参加する消費者についての消費者特性値とサポート率とを含む、候補消費者トランザクションルールエントリと、
前記候補消費者トランザクションルールエントリのペアを受け入れ、前記候補消費者トランザクションルールエントリの前記ペアの中の個々の消費者特性値に基づいて、それぞれの前記候補消費者トランザクションルールエントリを表すビットベクトルのペアを生成するように動作可能なビットベクトルツールであり、該ビットベクトルツールは、欠損値を、任意という値を有するものとして扱う、ビットベクトルツールと、
前記ビットベクトルツールと相互作用し、ルールのペアに対するビットベクトルの前記ペアの評価に基づいて冗長なルールエントリをフィルタするように動作可能な消費者トランザクションルール冗長性フィルタと、
サポート率でランク付けされた、フィルタされたルールエントリのリストを表示するユーザインタフェースと、
を含むシステム。
【請求項９】
ビットベクトルの前記ペアの評価が、
前記ビットベクトルに対して論理積演算を実行して結果を作るステップと、
前記結果とビットベクトルの前記ペアの中のビットベクトルとを比較するステップと、
を含む、請求項８に記載のシステム。
【請求項１０】
前記消費者トランザクションルール冗長性フィルタはさらに、候補消費者トランザクションルールエントリを、それぞれのサポート率に基づいてクラスタ化するように動作可能である、
請求項８に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、種々のアプリケーションストアトランザクションに参加している消費者の特性を示すことができる消費者トランザクションルールに関し、冗長な消費者トランザクションルールをフィルタして過分な情報を除去することに関する。
【背景技術】
【０００２】
モバイルコンピューティングの利用の広がりに伴い、消費者は、新しいアプリケーションを試行し購入するなどの、増加の一途をたどるトランザクションに関与している。しかしながら、多数の売り出されているものと結び付けられた非常に多くの消費者が、モバイルコンピューティングの世界において売買を困難なタスクにしている可能性がある。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
消費者がアプリケーションを見つけることを支援するように、検索技術を含む種々のツールが実現されている。しかしながら、アプリケーション開発者が消費者を見つけることの支援に対しては、あまり注意が払われていない。例えば、開発者は、アプリケーション購入数に関して情報を与えられる場合がある。単純な数が、マーケティング努力が成功しているかどうかのいくらかの指標を与えることができる一方、改良の余地が残っている。
【課題を解決するための手段】
【０００４】
本概要は、以下の発明を実施するための形態においてさらに説明される概念のうち選ばれたものを簡易化された形で紹介するために提供される。本概要は、請求される対象事項の主要な特徴又は本質的特徴を特定するものではなく、請求される対象事項の範囲を限定するために使用されるものでもない。
【０００５】
消費者トランザクションルールは、種々のアプリケーションストアトランザクションに参加している消費者の特性を示すことができる。冗長な消費者トランザクションルールをフィルタして、過分な情報を除去することができる。消費者特性に関する有意義な情報を、限られた量の空間に提示することができる。
【０００６】
冗長性識別には、サポート率が十分に近接しているかを判定することなどの、種々の手法を採用することができる。例えば、閾値εを使用して、ルールを、冗長性フィルタリングのためのサポートバンドにクラスタ化することができる。
【０００７】
他の手法には、本明細書に説明されるビットベクトル手法を用いるなどの、種々の方法で包含関係を識別することが含まれる。
【０００８】
ルールエントリの任意化（anyfication）などの種々の他の特徴を使用して、利点を得ることができる。
【０００９】
冗長性フィルタリングは、より少ないルールが同等以上の情報を伝達することをもたらし、この情報は、消費者トランザクションルールを表すユーザインタフェース及び他のシナリオにおいて特に有用となり得る。
【００１０】
本明細書に説明されるとおり、種々の他の特徴及び利点を、所望される技術に組み込むことができる。
【図面の簡単な説明】
【００１１】
【図１】冗長な消費者トランザクションルールのフィルタリングを実施する例示的なシステムのブロック図である。
【図２】冗長な消費者トランザクションルールをフィルタする例示的な方法のフローチャートである。
【図３】基本的な冗長な消費者トランザクションルールフィルタリングを示すブロック図である。
【図４】消費者トランザクションルールエントリの例示的な集合のブロック図である。
【図５】冗長性を除去するようにフィルタされた消費者トランザクションルールを含む開発マイナーツールのための例示的なユーザインタフェースの画面ショットである。
【図６】サポートバンドツールを用いて冗長な消費者トランザクションルールのフィルタリングを実施する例示的なシステムのブロック図である。
【図７】サポートバンドを介して冗長な消費者トランザクションルールのフィルタリングを実施する例示的な方法のフローチャートである。
【図８】ビットベクトルツールを用いて冗長な消費者トランザクションルールのフィルタリングを実施する例示的なシステムのブロック図である。
【図９】ビットベクトルを介して冗長な消費者トランザクションルールのフィルタリングを実施する例示的な方法のフローチャートである。
【図１０】例示的な消費者トランザクションルールを示す表である。
【図１１】任意化を適用された、例示的な消費者トランザクションルールを示す表である。
【図１２】ビットベクトルを介した冗長性フィルタリングを示す表である。
【図１３】ビットベクトルを介した冗長性フィルタリングを示す別の表である。
【図１４】冗長性フィルタリングの性能メトリクスを示すブロック図である。
【図１５】冗長性フィルタリングを達成するために最近傍手法を適用することを示すブロック図である。
【図１６】冗長性フィルタリングを達成するための例示的なアーキテクチャのブロック図である。
【図１７】データ集合性能を示すグラフである。
【図１８】データ集合性能を示すグラフである。
【図１９】データ集合性能を示すグラフである。
【図２０】データ集合性能を示すグラフである。
【図２１】いくつかの説明された実施形態を実施することができる例示的なコンピューティングシステムの図である。
【図２２】アプリケーションストアにおける消費者トランザクションに関与するために使用することができる例示的なモバイル装置である。
【図２３】本明細書に説明される技術に関連して使用することができる例示的なクラウドサポート環境である。
【発明を実施するための形態】
【００１２】
例１‐代表的な概説
本明細書に説明される技術は、種々の冗長性フィルタリングシナリオに対して使用することができる。上記技術の採用は、冗長なルールをフィルタすることに対して有効な手法を提供することができる。
【００１３】
上記技術は、アプリケーションストアトランザクションに関わる消費者の特性をモニターしたい者にとって役立つものとなり得る。受益者には、現在の消費者と将来見込まれる消費者との特性を判定したいアプリケーション開発者を含む。消費者もまた、特定のアプリケーションにおそらく関心があると正しく認識される可能性がより高くなるため、上記技術から間接的に恩恵を受ける可能性がある。
【００１４】
例２‐冗長なトランザクションルールのフィルタリングを実施する例示的なシステム
図１は、本明細書に説明される冗長な消費者トランザクションのフィルタリングを実施する例示的なシステム１００のブロック図である。
【００１５】
背景として、この図は、種々のアプリケーションと関わる消費者トランザクションに関与する消費者１１０によってアクセスされるアプリケーションストア１２０を示す。消費者トランザクションの種々の態様が、消費者トランザクションデータ１３０として記憶されることができる。消費者トランザクションルール生成部１４０が、任意の数の手法を使用して、消費者トランザクションデータ１３０に基づいて候補消費者トランザクションルールエントリ１５０を生成することができる。例えば、相関ルール（ＡＲ）生成手法を使用することができる。
【００１６】
本明細書に説明される技術に従い、消費者トランザクションルール冗長性フィルタ１６０が、本明細書に説明される手法のいずれかを適用して、候補消費者トランザクションルールエントリ１５０をフィルタして、フィルタされたトランザクションルールエントリ１７０を生成することができる。
【００１７】
実際には、システム１００などの本明細書に示されるシステムは、追加の機能性、より複雑な入力などを有して、より複雑なものとすることができる。
【００１８】
システム１００と本明細書に説明されるその他のシステムのいずれかとは、以下に説明されるコンピューティングシステムなど（例えば、処理ユニット、メモリなど）の本明細書に説明されるハードウェアコンポーネントのいずれかと関連して実装されることができる。本明細書における例のいずれにおいても、入力、出力及びツールを、１又は複数のコンピュータ読取可能記憶媒体又はコンピュータ読取可能記憶装置に記憶することができる。本明細書に説明される技術は、オペレーティングシステム又はハードウェアの仕様について包括的とすることができ、任意の様々な環境に適用されて説明される特徴の利点を得ることができる。
【００１９】
例３‐冗長なトランザクションルールのフィルタリングを実施する例示的な方法
図２は、冗長な消費者トランザクションルールをフィルタする例示的な方法２００のフローチャートであり、例えば、図１に示されるシステムにおいて実施することができる。
【００２０】
２１０において、候補トランザクションルールエントリが受信される。本明細書に説明されるとおり、候補消費者トランザクションルールエントリには、アプリケーションストア消費者トランザクションに関連付けられた同様の消費者特性値の発生についての、それぞれのサポート率を示すルールを含むことができる。
【００２１】
２２０において、冗長なルールエントリが識別される。本明細書に説明されるとおり、ルールエントリを冗長なものと識別することには、２つの候補消費者トランザクションルールエントリについてのサポート率が十分に近接すると判定することを含むことができる。識別することにはさらに、２つの候補消費者トランザクションルールエントリ間の包含関係を（例えば、本明細書に説明されるように直接的に又は間接的に）識別することを含むことができる。
【００２２】
２３０において、候補トランザクションルールエントリがフィルタされる（例えば、冗長なルールエントリが除去される）。
【００２３】
方法２００と本明細書に説明されるその他の方法のいずれかとは、１又は複数のコンピュータ読取可能媒体（例えば、記憶装置又は他の有形媒体）に記憶され、あるいは１又は複数のコンピュータ読取可能記憶装置に記憶された（例えば、コンピューティングシステムに本方法を実行させる）コンピュータ実行可能命令によって実行されることができる。
【００２４】
例４‐例示的な冗長な消費者トランザクションルールのフィルタリング
図３は、基本的な冗長な消費者トランザクションルールフィルタリングを示すブロック図である。
【００２５】
実際には、トランザクション３１０が、冗長性フィルタリングシステムに直接アクセス可能である必要はなく、あるいはその一部である必要はない。しかしながら、トランザクション３１０は、背景として、ここに示されている。
【００２６】
アプリケーションストア消費者トランザクション３２０Ａ〜Ｆに関連付けられた同様の消費者特性値の発生についてのそれぞれのサポート率を示すルールエントリ３６０Ａ、３６０Ｂ、３６０Ｃによって、候補ルール３５０を表すことができる。
【００２７】
例えば、この例において、４つのトランザクション３２０Ｃ〜Ｆは、これらのトランザクションに関与している消費者がこうした特性を有するという理由で、同様の（例えば、同じ）消費者特性値、すなわち、国＝“ＵＳＡ”、州＝“ＷＡ”及び年齢＝“２２〜４０”を有する。結果として、ルール生成部は（例えば、相関ルール生成手法を用いて）、トランザクション３２０Ｃ〜Ｆによってサポートされる種々のルール３６０Ａ〜Ｃを生成することができる。この例において、３つのルール３６０Ａ〜Ｃが生成される。これらルールについてのサポート値は、同じルールに基づいているため、同じものである。実際には、ルール３５０は、観察されたトランザクションに厳密に基づく必要はないが、実際のトランザクション３１０を確実に表すようにサンプリングなどの統計的手法を用いて構築されることができる。
【００２８】
ルール３６０Ａ〜Ｃの評価は、これらルールが包含関係を有することを明らかにする。ルール３６０Ｂ及び３６０Ｃは伝達する情報がより少ないため、ルール３６０Ａに関して冗長である（例えば、ルール３６０Ｂ及び３６０Ｃは、同じサポートを有し、３６０Ａの属性値アサーションの部分集合しか示していない）。
【００２９】
本明細書に説明される冗長性フィルタリングは、２つのルール３６０Ｂ〜Ｃを除去することができ、ルール３６０Ａのみを有するフィルタされたルール３７０をもたらすことができる。実際には、追加のルールが存在することができる（例えば、トランザクション３２０Ａ、３２０Ｂなどによってサポートされる）。
【００３０】
例５‐例示的な冗長な消費者トランザクションルール
本明細書における例のいずれにおいても、冗長な消費者トランザクションルールは、別のルールに関して過分な情報を提示するルールとすることができる。実際には、冗長なルールは、別のルールより少ない情報を提示するものであり、ゆえに、結果として生じる残りのルールにおける重大な情報損失なしにフィルタされることができる。冗長なルールは、包含関係がルール間に存在することと、これらルールのサポート率が十分に近接するかどうかとを判定することによって、識別されることができる。
【００３１】
例えば、６つの消費者アプリケーションストアトランザクションという母集団の、図３の例において、４人の異なる消費者についての４つのトランザクションが、“国＝ＵＳＡ”、“州＝ＷＡ”及び“年齢＝２２〜４０”という属性値を有することができる。こうした場合、消費者トランザクションルールは、“国＝ＵＳＡ”、“州＝ＷＡ”及び“年齢＝２２〜４０”を、０．６７というサポートと共に示すことができる。別のルールが、“国＝ＵＳＡ”及び“州＝ＷＡ”を、０．６７というサポートと共に示すことができる。さらに別のルールが、“国＝ＵＳＡ”を、０．６７というサポートと共に示すことができる。第１のルールが、最も具体的である。第２の２つのルールは、第１のルールより具体的でなく（例えば、より少ない属性値ペアを有することによってより少ない情報を提供する）、トランザクションに関する追加の情報を第１のルールを超えて提供するものではないため、冗長と見なすことができる。この例において、第１ルールと第２のルールとは同一のサポートを有する。しかしながら、本明細書におけるいくつかの他の例において、サポートは、同一ではなしに、十分に近接し得る。
【００３２】
実際には、冗長なルールをフィルタすることで、より少ないルールを、重大な情報損失なしに提示することが可能となり、このことは、ユーザによる検討のためにルールを提示するときに役立ち得る。
【００３３】
例６‐例示的な消費者トランザクションルールサポート
これらの例のいずれにおいても、ルールは、該ルールを満たす特性を有する消費者によるトランザクションの数を示すサポート率（又は、単に「サポート」）を有することができる。サポート率は、絶対値（例えば、１４３件のトランザクション）、比率（例えば、ルールに一致するトランザクション１４３件／合計トランザクション１３９４件）、パーセンテージ（例えば、１０．３％）などの種々の形式で与えられることができる。例えば、あるパターンＰについて、サポート(Ｐ)＝Ｆｒｅｑ(Ｐ)／Ｔｏｔａｌである。
【００３４】
例７‐例示的な包含関係
本明細書における例のいずれにおいても、冗長性を判定することには、２つのルールが包含関係を有するかどうかを判定することを含むことができる（例えば、一方のルールを満たす消費者トランザクションが、他方によって最終的に包含される）。別のルールの完全なトランザクションを論理的に包含する（又は、単に「包含する」）ルール（例えば、このルールは、別のルールが特定の値を指定しているところに「任意（any）」を指定する）は、本明細書に説明されるサポートに依存して、冗長なものとして消去されることができる。
【００３５】
第１の、より一般的なルールは、第２の、より具体的なルールを包含するといわれる（例えば、第１のルールは、第２のルールが特定の値を指定するところに、「任意」を指定する）。より一般的なルールは、サポートに依存して、冗長なものとして除去されることができる。
【００３６】
トランザクション母集団についての集合‐部分集合関係を有するルールは、「包含」関係を有すると考えられる（例えば、別のルールについてのトランザクションが、別の、より具体的なルール内に必然的に包含される）。論理的な集合‐部分集合関係は、２つのルールを満たすトランザクションが同一である場合でさえ、存在することができる。本明細書に説明されるとおり、ビットベクトルを使用して包含関係が存在するかどうかを判定することができる。
【００３７】
例８‐例示的な十分に近接したサポート率
本明細書における例のいずれにおいても、サポート率が同一であるときに、十分に近接したサポート率を示すことができる。しかしながら、非同一のサポート率もまた十分に近接することができる。
【００３８】
本明細書に説明される例には、サポート閾値εの使用、拡張されたサポートバンド、サポート率によるクラスタリングなどを含む。
【００３９】
例９‐例示的な消費者トランザクション
本明細書における例のいずれにおいても、消費者トランザクションは、特定のアプリケーション（例えば、ダウンロード可能なプログラム）に関わる消費者トランザクションの形式をとることができる。例えば、こうしたトランザクションには、アプリケーションを試行すること、アプリケーションをダウンロードすること、アプリケーションを購入すること、アプリケーションをアンインストールすること、アプリケーションをアップグレードすることなどを含むことができる。必要に応じて、トランザクションには、アプリケーションの特定の特徴を使用することなどの、アプリケーションとの相互作用を含むことができる。
【００４０】
実際には、アプリケーション消費者は、アプリケーションストアを介して、アプリケーションストアから取得されたアプリケーションと相互作用することによって、こうしたトランザクションに関与することができる。アプリケーションストアは、消費者がアプリケーションを発見し、試行し、ダウンロードすることができる豊かな環境を提供することができる。
【００４１】
例１０‐例示的な消費者トランザクションタイプ
消費者トランザクションは、特定のタイプに関連付けられて、どのような種類のトランザクションが関わっているかを示すことができる。例えば、例示的なトランザクションタイプには、「購入」、「試行」、「ダウンロード」、「閲覧」、「アンインストール」などを含む。
【００４２】
本明細書に説明されるルールフィルタリング技術は、特定のタイプのトランザクション、種々のタイプのトランザクションの組み合わせなどに適用することができる。
【００４３】
例１１‐例示的な消費者特性
本明細書におけるいずれの例においても、消費者トランザクションは、消費者の特性（例えば、属性）と関連付けられることができる。
【００４４】
消費者は、アプリケーションストアに登録をすることができ、この登録処理には、消費者からの種々の消費者特性（例えば、人口学的情報）とユーザの装置に関する種々の情報とを収集することを含む。プライバシーに対する懸念は、ユーザの同一性を十分に保護することによって、対処されることができる（例えば、トランザクションを分析するときに消費者を具体的に又は個人的に識別する情報を記憶しない）。
【００４５】
例１２‐例示的な消費者トランザクションルール
本明細書における例のいずれにおいても、トランザクションルールは、（例えば、アプリケーションストアを介して）消費者トランザクションに関与している消費者に関連付けられているとして観察されている属性値アサーションの特定の集合を示す属性値ペアの集合の形式をとることができる。例えば、消費者トランザクションに関与している消費者の特性を使用して、消費者トランザクションルールを形成することができる。ルールを満たすトランザクションが、ルールをサポートすると考えられる。通常、関心のあるルールは、より大きなサポートを含むルールである（例えば、多数の消費者が、このルールに合致する特性を有する）。しかしながら、時に、より少ないサポートからなるルールが関心を持たれる場合がある。
【００４６】
実際には、ルールを使用して、消費者トランザクションの人口学的パターン（例えば、消費者トランザクションデータの範囲内の頻度で生じる消費者特性の集合）を指定することができる。
【００４７】
本明細書に説明されるとおり、ルールは、該ルールによって表される人口動態を示す属性値ペア（例えば、属性値アサーション又は“ＡＶＡ”）の集合を有するルールエントリとして記憶されることができる（例えば、ルールエントリは、“属性１＝値１”“属性２＝値２”などの属性値ペアを有することができる）。実際には、これらペアは、ＸＭＬ、構造化データ、データベース内のフィールドなどとして記憶されることができる。
【００４８】
図４は、消費者トランザクションルールエントリの例示的な集合４５０のブロック図である。実際には、数百、数千又はそれ以上のルールを、トランザクションの分析から生成することができる。本明細書に説明されるフィルタリングは、消費者に関してもっと知りたい開発者に対して、ルールをより分かりやすいものにすることができる。
【００４９】
例１３‐例示的な内部表現
実際には、値、属性、ルールなどは、種々の方法で内部的に表されることができる。例えば、特定の値（例えば、国「ＵＳＡ」）は、リテラル値又は文字列に代わって、コード（例えば、数字など）によって表されることができる。しかしながら、ユーザによる検討のためにレンダリングされるとき、人間が理解可能な値で示されることができる。
【００５０】
例１４‐例示的な領域特化型のヒューリスティック
本明細書における例のいずれにおいても、消費者トランザクションルールエントリは、領域特化型のヒューリスティック（domain-specific  heuristics）に基づいて精緻化される（refined）ことができる。例えば、消費者特性のケースにおいて、ある値が別の値を暗示することが既知である場合、その値は精緻化の間に供給されることができる。
【００５１】
こうした領域特化型のヒューリスティックの一例は、州が国なしで供給されていることを検出することである。この州がある国の地形の一部であることが既知である場合、この州がルール内に存在すると検出したことに応じて、その国を、ルールに追加することができる。例えば、ワシントン（“ＷＡ”）という州がルール内に存在し、しかしながら国が欠損している場合、アメリカ合衆国（“ＵＳＡ”）という国をルールに追加することができる（例えば、国＝“ＵＳＡ”）。
【００５２】
例１５‐フィルタされたルールを提示する例示的なユーザインタフェース
本明細書における例のいずれにおいても、候補トランザクションルールエントリをフィルタすることで、フィルタされたルールエントリを生成することができる。フィルタされたルールエントリは、その後、ユーザインタフェースに表示されることができる。
【００５３】
図５は、冗長性を除去するようにフィルタされた消費者トランザクションルールを含む開発マイナーツール（development  miner  tool）の例示的なユーザインタフェース５１０の画面ショットである。ユーザインタフェースは、本明細書に説明されるフィルタリング技術を適用することによって、消費者トランザクションルールを表示する間のユーザエクスペリエンスの最適化を向上させることができる。
【００５４】
この例において、ツール５１０は、ダウンロードデータペイン５２０を含む（例えば、アプリケーションのダウンロード数）。
【００５５】
ユーザインタフェースはさらに、誰がダウンロードしているかのペイン５４０（例えば、サポート率によってランク付けされた、上位λでフィルタされた消費者トランザクションルールを示す）と、カテゴリトレンドペイン５５０（例えば、サポート率によってランク付けされた、上記アプリケーションと同じカテゴリ内の他のアプリケーションについての上位ｎでフィルタされた消費者トランザクションルールを示す）とを含むことができる。
【００５６】
ペイン５４０は、上位ｎでフィルタされたアプリケーションストアの消費者トランザクションルールを表示することができる。アプリケーションストアの消費者トランザクションルールは、アプリケーションストア消費者トランザクションルールに関連付けられたアプリケーションストアの消費者トランザクションに関連する消費者特性値を示すことができる。フィルタされたアプリケーションストア消費者トランザクションルールは、本明細書に説明されるとおり、サポート閾値εと包含関係とに従ってフィルタされることができる。フィルタされたアプリケーションストア消費者トランザクションルールは、サポート率によってソートされることができる（例えば、最高から最低へと降順に）。
【００５７】
実際には、任意の数の他の構成が可能である。本明細書に説明される冗長性フィルタリング技術は様々なシナリオに使用されることができ、そのシナリオにおいて、画面の実際の占有部分（estate）は、アプリケーションストア消費者に関するより有意義な情報を表示するように限定される。
【００５８】
例１６‐サポートバンドを介してフィルタする例示的なシステム
図６は、サポート近接性ツール６６５を用いて冗長な消費者トランザクションルールのフィルタリングを実施する例示的なシステム６００のブロック図である。
【００５９】
この例において、候補消費者トランザクションルールエントリ６５０とフィルタされたトランザクションルールエントリ６７０とは、本明細書において他所で説明されたようなルールエントリの形式をとることができる。
【００６０】
冗長性フィルタ６６０は、サポート近接性ツール６６５を含み、サポート近接性ツール６６５は、本明細書における手法のいずれかを使用して、２つのルールのサポート率が冗長であると見なされるほど十分に近接しているかどうか（例えば、上記２つのルールが包含関係をも有するかどうか）を判定することができる。例えば、閾値εを使用して、単純な同一のサポートを超えて、サポートバンドを拡張することができる。種々の他の手法が本明細書に説明される。
【００６１】
候補消費者トランザクションルールエントリ６５０が、多数のトランザクションから導出されることができ、統計的手法に依存する可能性があるため、ルールエントリのサポート率がノイズを包含することになる可能性が存在する。したがって、２つのルールが同一のサポートを有しない場合に冗長性フィルタリングを許可することが、過分なルールエントリを除去することに対してかなり有利になり得る。
【００６２】
例１７‐サポートバンドを介してフィルタする例示的な方法
図７は、サポートバンドを介して冗長な消費者トランザクションルールのフィルタリングを実施する例示的な方法７００のフローチャートである。
【００６３】
７１０において、候補トランザクションルールエントリを、本明細書に説明されるように受信することができる。
【００６４】
冗長なルールエントリを識別することが、７２０と７３０とから成る。７２０において、サポート閾値εに基づいて、ルールが、そのサポート率に基づいてバンドにクラスタ化される。種々のクラスタリング手法（例えば、最近傍など）が使用されることができる。クラスタリングは、あるルールエントリを、異なる（例えば、非同一の）サポート率を有する他のルールエントリと一緒にクラスタ化することができる。
【００６５】
次いで７３０において、冗長なルールが、サポートバンド内で識別される。例えば、サポートバンド内のルールは、冗長性目的で、十分に近接していると見なすことができる。本明細書に説明されるように、ルールは、クラスタに割り当てることができ、同じクラスタ内のこれらルールは、冗長性目的で、十分に近接していると見なすことができる。
【００６６】
本明細書に説明されるとおり、あるバンド内のルールエントリは、包含関係についてチェックされることができる。こうした包含関係を有するバンド内のこれらルールエントリ（例えば、別のルールを包含する、あるルールエントリ）は、冗長であると識別されることができる。
【００６７】
本明細書に説明されるとおり、ルールは、包含関係に従ってグループ化されることができ、サポート率は、そのグループ内で（例えば、サポート閾値εに基づいて）チェックされて、サポート率が十分に近接しているかどうかを知ることができる。こうした場合、サポート率が十分に近接していると判定することは、包含関係を識別することの後に行われる。こうした構成は、通常、より良好な冗長性除去をもたらす。
【００６８】
７４０において、候補ルールエントリが、本明細書に説明されるとおり（例えば、冗長なルールエントリを除去することによって）フィルタされる。
【００６９】
例１８‐ビットベクトルを介してフィルタする例示的なシステム
図８は、ビットベクトルツール８６５を用いた冗長な消費者トランザクションルールのフィルタリングを実施する例示的なシステム８００のブロック図である。
【００７０】
この例において、候補消費者トランザクションルールエントリ８５０とフィルタされたトランザクションルールエントリ８７０とは、本明細書の他所で説明されたようなルールエントリの形式をとることができる。
【００７１】
冗長性フィルタ８６０は、ビットベクトルツール８６５を含み、ビットベクトルツール８６５と相互作用することができ、ビットベクトルツール８６５は、本明細書におけるビットベクトル手法の任意のものを使用して２つのルールエントリが包含関係を有するかどうかを判定することができる。例えば、ルールエントリのペアについて、それぞれのビットベクトルを割り当て、評価して、包含関係が存在するかどうかを示す結果を生成することができる。本明細書に説明されるとおり、ツール８６５は、欠損値を、任意（any）という値を有するものとして扱うことができる。
【００７２】
図８には示されていないが、本明細書におけるシステムのいずれもが、（例えば、サポート率によってランク付けされた）フィルタされたルールエントリのリストを表示するユーザインタフェースを含むことができる。
【００７３】
例１９‐ビットベクトルを介してフィルタする例示的な方法
図９は、ビットベクトルを介した冗長な消費者トランザクションルールのフィルタリングを実施する例示的な方法９００のフローチャートである。
【００７４】
９１０において、候補トランザクションルールエントリが、本明細書に説明されるとおり受信される。
【００７５】
ビットベクトルを介して冗長なルールエントリを識別することは、９２０及び９３０から成ることができる。９２０において、ビットベクトルが、ルールペアについて生成される。ビットベクトルペアは、候補消費者トランザクションルールエントリのペアの中の個々の消費者特性値の比較に基づいて、候補消費者トランザクションルールエントリのそれぞれのペアについて、生成されることができる。
【００７６】
９３０において、ビットベクトルが評価されて、ルールエントリが包含関係を示すかどうかが判定される。あるルールエントリがこうした関係を示す（例えば、別のルールエントリを包含する）場合、このルールエントリをさらに解析して、２つのルール間のサポート率が十分に近接しているかどうかを判定することができる。もしそうである場合、このルールエントリを冗長であると識別することができる。
【００７７】
本明細書に説明されるとおり、包含関係を（例えば、ビットベクトルを用いて）識別することの前に、ルールエントリを、そのサポート率にしたがってクラスタ化することが可能である。こうした場合、サポート率が十分に近接していると判定することは、包含関係を識別することの前に行われる。
【００７８】
９４０において、候補ルールエントリが、本明細書に説明されるとおり（例えば、冗長なルールエントリを除去することによって）フィルタされる。
【００７９】
例２０‐例示的なビットベクトル割り当て
本明細書における例のいずれにおいても、当該ルール（Ｒｉ）と別のルール（Ｒｊ）とについて以下のとおり２つのルールエントリを比較するとき、ビットベクトルは、消費者特性につき１つのビットを割り当てられることができる。
【表１】
2015508918.tif 000003
【００８０】
ビットベクトルＲｉとＲｊとが消費者特性について異なる非任意値を有する場合、ルールエントリは独立しているため、包含をチェックする必要はない。ビットベクトル処理は、こうした独立したルールについて、スキップすることができる。
【００８１】
ＲｉとＲｊとがすべての消費者特性について同一の値を有する場合、それらは同一であり、そのようなものとして扱われることができる（例えば、一方が他方の中に包含されるように、一方は除去されることができる）。
【００８２】
例２１‐例示的なビットベクトル評価
本明細書における例のいずれにおいても、２つのルールエントリのビットベクトル（例えば、ビットベクトルのペア）は、ベクトルのペアに対して論理積を実行することによって評価され、結果的なビットベクトルを作ることができる。結果的なビットベクトルは、それから、各ルールのビットベクトルと（例えば、ペアの中のビットベクトルと）比較されることができる。結果的なビットベクトルが、ルールのうちいずれかのビットベクトルと一致する場合、一致するビットベクトルを有するルールは、包含関係を有し（例えば、他方のルールを包含する）、サポート率がルール間で十分に近接している場合に冗長であるとして除去されることができる。
【００８３】
例２２‐例示的な開発者
本明細書における例のいずれにおいても、開発者は、アプリケーションを開発し、かつ／あるいはアプリケーションストア消費者によるアクセスのためにアプリケーションストアにアプリケーションをアップロードする、任意の関係者又はエンティティとすることができる。本明細書に説明されるとおり、こうした開発者は、本説明による技術から大きく恩恵を受けることができる。
【００８４】
例２３‐例示的な組み合わせ
本明細書における例のいずれにおいても、サポート近接手法の任意のものを、本明細書に説明されるビットベクトル手法の任意のものと関連させて使用することができる。
【００８５】
例２４‐例示的な消費者トランザクションルール
図１０は、例示的な消費者トランザクションルールを示す表１０００である。この例において、トランザクションの１００％（サポート率１）が男性（Ｍａｌｅ）消費者に関わったことをルールが示していることが明らかである。
【００８６】
別のルールは、トランザクションの６３％が２２〜４０歳のバケットの消費者に関わったことを示している。こうしたルールは、別のルールが、トランザクションの６３％が２２〜４０歳のバケットに関わり、かつ男性であることを示している場合に、冗長である。他の冗長なルールが示されている。
【００８７】
例２５‐消費者トランザクションルールの例示的な任意化（anyfication）
図１１は、任意化を適用された例示的な消費者トランザクションルールを示す表１１００である。本明細書における例のいずれにおいても、ルールエントリの分析は、欠損値が値「任意（any）」を有するとみなされるとき、有利に進めることができる。こうした手法は、「任意化」と呼ばれ、本明細書に説明される例のいずれにおいても適用されることができる。実際には、値「任意」は、特別なコード又はポインタを含め、様々な方法で表されることができる。
【００８８】
任意化は、第１の候補消費者トランザクションルールエントリ内に存在せず、しかしながら他の候補消費者トランザクションルールエントリに存在する１又は複数の消費者特性値について、任意（Ａｎｙ）という値を示すことができる。
【００８９】
値のうち１つは、代わって、“ＵＳＡ”に補正される。なぜならば、領域特化型の知識は、州“ＷＡ”は必然的に国の値が“ＵＳＡ”であることを意味すると保証するからである。
【００９０】
例２６‐例示的なビットベクトル評価
図１２は、ビットベクトルを介した冗長性フィルタリングを示す表１２００である。この例において、Ｒ１とＲ２とが評価されて、包含関係が存在するかどうかが決定される。ビットベクトル（Ｒ１用の１１０１とＲ２用の１００１）が、本明細書に説明されるビットベクトル割り当て手法に従って構築される。
【００９１】
論理積が実行されるとき（例えば、図面において＾で示される）、結果的なビットベクトル（１００１）はＲ２に一致し、ゆえにＲ２は、Ｒ１によって包含される。したがって、Ｒ２は、２つのルールのサポート率が十分に近接する場合、冗長である。
【００９２】
図１３は、ビットベクトルを介した冗長性フィルタリングを示す別の表１３００である。この例において、ビットベクトル（Ｒ１用の１１０１とＲ２用の００１０）が、本明細書に説明されるビットベクトル割り当て手法に従って構築される。
【００９３】
論理積が実行されるとき、結果的なビットベクトル（００００）はＲ１とＲ２とのいずれにも一致せず、ゆえにいずれのルールも包含関係を有しない。したがって、ルールは維持され、独立していると見なされる。
【００９４】
例２７‐例示的な性能メトリクス
図１４は、冗長性フィルタリングの性能メトリクスを示すブロック図である。
【００９５】
この例において、上位Ｎウィンドウに、Ｍ個のルールが存在する。こうした構成は、上位Ｎ個のルールが検討のためにユーザに伝達されるシナリオを分析するのに有用な方法である。Ｎは様々な値のうち任意のものとすることができるが、１つの実装がＮ＝５を使用する。
【００９６】
カバレッジ増加パーセンテージは、１００＊((Ｌ／Ｎ)−１)で算出することができ、ここで、Ｌは、その数（Ｎ個）の上位Ｎ個のルールが最終候補リストに載せられ得る前に、冗長なルールを回避するために、（例えば、サポートに基づいて順序付けされた）上位からスキャンされる必要があったルールの数（例えば、通常はＮを超える）を決定する。換言すると、カバレッジ増加は、冗長なルールを除去していないＮ個のルールのウィンドウに限られたときに当初見込まれたルールを超える、冗長なルールを除去することによって増加されるルールへの追加的なカバレッジ深さの量を測定する。
【００９７】
こうしたカバレッジ増加メトリックは、サポート率によってランク付けされた、フィルタされたルールエントリの上位Ｎウィンドウについて、もとのルール集合（例えば、候補消費者トランザクションルールエントリ）におけるＮ番目のルールエントリの（例えば、サポート値の降順における）ランク付けＬを決定することと、(Ｌ／Ｎ)−１を算出することを含むカバレッジ増加メトリックを算出することとによって、算出することができる。カバレッジ増加メトリックのパーセンテージは、１００＊((Ｌ／Ｎ)−１)で算出することができる。
【００９８】
冗長性消去パーセンテージメトリックは、Ｎ又は上位Ｎのシナリオを考慮せずに進めることができる。発見された（例えば、候補の、冗長か否かの）ルールの集合全体が、スキャンされることができる（例えば、最小サポート値によって適格とされることができる）。それから、ルールのうちどれほどのパーセンテージが、発見されたルールの全範囲の中で冗長であるのかを見出すことができる。
【００９９】
こうした冗長性消去メトリックは、冗長であると識別された候補消費者トランザクションルールエントリを、候補消費者トランザクションルールエントリの総数で除算することによって、算出することができる。冗長性消去メトリックのパーセンテージは、１００を乗算することによって算出することができる。
【０１００】
候補ルールの中の上位Ｎ個のルールの中から、本明細書に説明される手法によって冗長であるとして何個の（例えば、Ｒ）ルールが削減されている（knocked  off）のかを、見出すことができる。削減パーセンテージは、１００＊(Ｒ／Ｎ)で算出することができる。
【０１０１】
こうした削減メトリックは、候補消費者トランザクションルールエントリの上位Ｎウィンドウについて、フィルタされた候補トランザクションルールエントリの数Ｒを、冗長であると判定することによって算出することができる。削減メトリックを算出することには、Ｎで除算されたＲを算出することを含む。削減メトリックのパーセンテージは、１００を乗算することによって決定することができる。
【０１０２】
上記メトリックは、本明細書に説明されるように限られたウインドウ内にルールを表示するときのルール冗長性除去手法の有効性などの、本明細書に説明される手法の利点を実証することに特に役立ち得る。
【０１０３】
例２８‐例示的な最近傍手法
図１５は、冗長性フィルタリングを達成するために最近傍手法を適用することを示すブロック図である。任意の数のクラスタリング手法を本明細書において適用して、サポート率によってルールエントリのクラスタリングを達成することができるが、最近傍手法が一例として示される。
【０１０４】
１５００Ａにおいて、分析が第１のルール１５１０Ａにおいて始まり、別のルール１５２０Ａが第１のルール１５１０Ａの閾値εの範囲内のサポート率を有することを判定する。分析は、次いで、ルール１５２０Ａに進む。
【０１０５】
分析は１５００Ｂに続き、ここで、ルール１５３０Ｂが分析１５２０Ｂのもとでルールの閾値εの範囲内のサポート率を有することを判定する。それに応じて、次いで、分析はルール１５３０Ｂに進む。
【０１０６】
１５００Ｃにおいて、ルール１５１０Ｃが１５３０Ｃの閾値の範囲内にないことが発見される。それに応じて、１５１０Ｃは、１５２０Ｃ及び１５３０Ｃと同じクラスタの範囲内にないものとしてマーク付けされる（例えば、１５１０Ｃは、１５３０Ｃの最近傍ではない）。
【０１０７】
分析は、グループ内の他のルールについて同様に続けることができる。
【０１０８】
例２９‐例示的な全体アーキテクチャ
図１６は、冗長性フィルタリングを達成するための例示的なアーキテクチャのブロック図である。この例において、ルールは、ＸＭＬで表されるが、他の表現が本明細書に説明されるとおり可能である。
【０１０９】
最小サポート閾値μを使用して、ＳＱＬ相関ルールアルゴリズム（SQL  Association  Rule  Algorithm）を用いてルールを生成することができる。こうしたルールは、冗長性についてまだフィルタされていないため、「最適化されていない」（例えば、候補ルール）と呼ばれる場合がある。
【０１１０】
ルールは、ＸＭＬルールで記憶され、ＸＭＬパーサによってパースされ、これがソートされたルールリストを生成する。
【０１１１】
本明細書に説明されるような領域特化型の精緻化が、適用されることができ、ルールは、拡張された表現（例えば、任意化など）にされることができる。
【０１１２】
包含に基づいたルールリストを、生成することができる。例えば、ルールは、包含関係を有する他のルールのリスト内に置かれることができる。本明細書に説明されるとおり、こうしたリストは、包含関係に基づいて順序付けられることができる。こうした順序付けは、最も一般的なものから最も一般的でないものへ、又はその逆とすることができる（例えば、包含するものから包含されるものへ、又はその逆）。
【０１１３】
ルールリストについて、εで拡張されたサポートクラスタリングが、包含されたルールリストについて実行されることができる。
【０１１４】
次いで、冗長性は、包含関係とサポート率とにしたがって消去されることができる。次いで、重要性判定（例えば、より高いランク付け、より多くの特性など）が行われ、最適化されたルール（例えば、冗長性についてフィルタされ、サポートによってランク付けされ、上位Ｎウィンドウ内に置かれるルール）をもたらすことができる。
【０１１５】
例３０‐例示的なさらなる情報
アプリケーションストアは、消費者が新しい好まれるアプリケーションを容易に発見し、試行し、購入するためのプラットフォームを提示することができる。開発者マイナー（Developer  Miner；ＤＭ）コンポーネントが、アプリケーションストアを通じてアプリケーション（「アプリ」）を配布している開発者に、（データに基づいた）ビジネスの方向性を提供することができる。開発者マイナーの機能性の１つが、アプリ（‘Ｌ３’採用ページ）についての記録された（ダウンロードされた）トランザクションからビジネスパターン（別称、ビジネスルール）を取り出し、アプリの（サブ）カテゴリ（新しいビジネス機会、すなわち、ＮＢＯページ）についての集約された（ダウンロードされた）トレンドに対して同じものを比較することである。このことは、開発者が、自身のアプリの実世界消費に基づいて、自身のビジネス戦略を再調整することに役立つ。
【０１１６】
ＳＱＬサーバ分析サービス相関ルール（ＡＲ）手法を使用して、消費者トランザクションからビジネスルールを抽出することができる。不幸なことに、ＡＲは、非常に冗長なルールを生成する。あるルールが、例えば、｛国＝“ＵＳＡ”、州＝“ワシントン”、年齢＝[０〜１３]、性別＝“男性”｝という属性値アサーション（ＡＶＡ）の列として表されると仮定することで、（ダウンロードされた）消費者のトランザクションから、ＤＭによって発見されたビジネスルールの１つを表すことになる。上記の例において、｛国＝“ＵＳＡ”、州＝“ワシントン”、年齢＝[０〜１３]｝、｛国＝“ＵＳＡ”、州＝“ワシントン”｝、｛国＝“ＵＳＡ”｝などの、（ほぼ）同じ頻度を有する冗長なルールの存在が、大いに起こり得る。このことは、限られた実際の占有部分（ディスプレイ）を冗長なルールであふれさせ、ひどいユーザエクスペリエンスをもたらすことになる。
【０１１７】
したがって、（１）消去のため、非冗長なビジネスルールを自動的に識別すること、（２）ユーザエクスペリエンスを最大化するために最も重要なルールを上部に示すようにルールを順序付けすること、及び（３）こうしたアルゴリズムの性能を評価するためにメトリクスを用意することが望ましい。
【０１１８】
本明細書に説明されるとおり、問題点に対処するための手法が、アプリケーションストア開発者分析において実施されることができる。これら手法は、一意のルール表現スキームによって促された包含関係を通じて冗長なルールを正しく識別する。この空間におけるアルゴリズムのベンチマーキングに役立つ新しいメトリクスが定義される（％冗長性、％カバレッジ増加、％削減）。実世界のアプリケーションストアデータを使用すると、平均で、４０％以上の％削減、３０％の冗長性、５８％以上のカバレッジ増加を得ることができる。このことは、（ルールの「サポート」に関する）上位５個のスキーマについて、平均で２つのルールがより有意義なルールによって置換されることになることを意味する。追加的に、アルゴリズムは、上位５個のルールを超えてスキャンして（すなわち、５８％のカバレッジ増加は上位８個のルールのスキャンを示す）、単に上位５個から選択することと対照して、非冗長なルールを探す。
【０１１９】
例３１‐例示的なさらなる情報
本明細書に説明される手法は、所与の属性集合を含む生成されたビジネスパターン（ルール）の冗長性を縮小する。ルールは、ＡＶＡ（属性値アサーション）の列で表すことができる。
【０１２０】
属性が、ルール内に存在しない場合、「任意」値を保有する属性と等価であるという事実を、活用することができる。換言すると、ルールは、上記属性の値についてあいまいである（agnostic）。このことは、冗長性を識別するという問題を、ＡＶＡ列の所与の集合（より一般的なルール）の部分集合（より具体的なルール）を検出するという問題へと縮小する。ビットベクトルは、生成されたルールと関連付けられることができ、生成されたルールは、ルール間のこの包含関係を検出するように操作されることができる。切り取り判断が、ルールの最小サポートと、ビットベクトル操作に基づいた他のルールとの包含関係と、領域特化型の冗長性識別との結合結果に基づいて行われる。
【０１２１】
特定の手法が、迅速となる可能性があり、実世界データ上の上位５個のルールから平均で４０％以上を置換することができる。さらに、ルールが上位５ウィンドウに表示されることになったモデルの８０％超が、冗長性消去の有効性を証明して改良されたユーザエクスペリエンスをもたらした。
【０１２２】
例３２‐例示的な表現
消費者トランザクションに基づいて生成された消費者トランザクションルールは、開発者のためにアプリケーションをモニターしているアプリケーションストアでの表示用に最適化される（例えば、冗長性についてフィルタされる）ことができる。ルールを最適化するための同様のアプローチが、決定木（ＤＴ）手法を用いて生成されたルールに適用されることができる。
【０１２３】
ルールは、ＸＭＬ形式でシステム内に記憶されることができるが、このことは必要ではない。
【０１２４】
マイニングシステム内の属性集合全体を、Ωで表すものとする。相関ルール手法によって発見されたルールは、属性値アサーションの列、すなわち、Ｒｉ：｛(Ａｋ＝ｖｋ,ｊ),ｋ∈[１，Ｎｉ]，ｊ∈[１，Ｖｋ]、Ａｋ∈Ω｝であり、ここで、
ｖｋ,ｊは、ｋ番目の属性値Ａｋのｊ番目の値であり、
Ｖｋは、Ａｋのとり得る値の数であり、
ｖｋ,ｊ∈ｖａｌ(Ａｋ)すなわちＡｋの値集合であり、
Ｎｉは、ｉ番目のルールすなわちＲｉに含まれる属性の数である。
【０１２５】
適格とされるルールの集合γは、最小閾値（μ）より大きなサポートを有するルールである。
【０１２６】
例えば、あるアプリケーションストアについて、
Ω＝｛国（＝Ａ１），州（＝Ａ２），年齢バケット（＝Ａ３），性別（＝Ａ４）｝
‘ｖａｌ(Ａ１)’は、｛ＵＳＡ、英国、インド、・・・｝などの値を仮定することができ、同様にして、他の値はその独自の値集合を有し、
典型的なルールＲは、｛国＝‘ＵＳＡ’，州＝‘ワシントン’，年齢バケット＝‘１５〜３０’，性別＝‘男性’｝という形式とすることができる。
【０１２７】
例３３‐例示的な任意化ルール表現
消費者トランザクションから生成されたルールの拡張された表現を、使用することができる。必ずしも、ルール‘Ｒ’がΩのすべての属性値を含む属性値アサーションを有する必要はない。Ｒの中にはいくらかの欠損している属性値（ＭＡｉ）が存在する可能性がある。
【０１２８】
こうした欠損している属性値アサーション（ＡＶＡ）は、｛ＭＡｉ｝の仮定し得る値についてルールがあいまいであることを示す｛(ＭＡｉ＝‘任意’)｝で補完されることができる。したがって、ルールＲ｛国＝‘ＵＳＡ’、性別＝‘男性’｝の拡張された表現は、｛国＝‘ＵＳＡ’、州＝‘任意’、バケット＝‘任意’、性別＝‘男性’｝に等しい。欠損している属性｛州、年齢バケット｝が、拡張された表現モードにおいてどのように‘任意’値で埋められているのかに留意されたい。
【０１２９】
拡張された表現において、システム内のルールは、Ωのうち欠損している属性（例えば、他のルールのいずれかに出現する属性などの、他のルールの属性）を含むことができる。
【０１３０】
例３４‐例示的な冗長なルール及び独立したルール
本明細書に説明される技術は、２つのルールが独立しているか、あるいは一方が他方を前提として冗長であるかを発見することができる。下記の定義を使用して、冗長なルール及び独立したルールの識別を支援することができる。
【０１３１】
拡張された表現を有する２つのルールＲｉ及びＲｊは、次の場合、２つのルールのうち一方を冗長にする集合‐部分集合関係を保有する。
【０１３２】
これらのサポートが等しく（又は本明細書に説明さるように近接している）、かつ、
これらの拡張された表現において、
［ＡＶＡｋがＲｉ及びＲｊについて正確に一致する］か、あるいは
［ＡｋはＲｉについて‘任意’でなければならず、ＡｋはＲｊについて‘任意’であってはならない］か、のいずれか
の場合に、ルールのうち一方、例えば（Ｒｉ）が、他方（Ｒｊ）よりも一般的である。
【０１３３】
２つのルールＲｉ及びＲｊは、冗長でない場合、独立している。
【０１３４】
例３５‐冗長なルール及び独立したルールの例示的な判定
上記に基づいて、冗長なルール及び独立したルールを判定する手法は、以下のとおりとすることができる。
【０１３５】
ルール（Ｒｉ及びＲｊ）の（相対的な）ビットベクトルは、以下のとおり、互いのコンテキスト内で同じ（例えば、又は十分に近接した）サポートを有するものを定義されることができる。
【０１３６】
［各ｋ＝１から|Ω|について］
１．同じサポートを有するＲｉ及びＲｊ内のｋ番目の属性Ａｋを含む属性値アサーションについて、
Ａ．Ｖａｌ(Ｒｉ：Ａｋ)、すなわち、Ｒｉ内の属性Ａｋの値が、Ｖａｌ(Ｒｊ：Ａｋ)に等しい場合、Ｒｉ及びＲｊの各々について、結果として得られるビットベクトル内のｋ番目のビット位置に、Ｒｉ及びＲｊの各々について‘１’を立てる（put）。これは、双方のルール内のＡｋのあらゆる非‘任意’値についてのみ保有する
Ｂ．Ｒｉ及びＲｊのいずれかの中で、Ａｋが‘任意’に等しい値を有し、他方が非‘任意’をとる場合、その対応するルールのビットベクトル表現内に‘０’を立てるとともに、他方のルール内に‘１’を立てる
Ｃ．双方のＲｉ及びＲｊ内のＡｋの値が‘任意’に等しい場合、双方のルールのビットベクトル表現のｋ番目の位置に‘０’を立てる
２．例えば、Ｒｉ＝｛国＝‘ＵＳＡ’、年齢バケット＝‘１５〜３０’｝、かつ、Ｒｊ＝｛年齢バケット＝‘１５〜３０’｝である場合、これらの相対的なビットベクトルに到達するために以下のステップをたどる
Ａ．［拡張された表現によって］
Ｒｉ＝｛国＝‘ＵＳＡ’、州＝‘任意’、年齢バケット＝‘１５〜３０’、性別＝‘任意’｝、かつ
Ｒｊ＝｛国＝‘任意’、州＝‘任意’、年齢バケット＝‘１５〜３０’、性別＝‘任意’｝
Ｂ．［ビットベクトル表現］
ＲｉのＲｊに対するビットベクトル＝ＢｉｔＶｅｃｔｏｒＲｊ(Ｒｉ)＝１０１０
ＲｊのＲｉに対するビットベクトル＝ＢｉｔＶｅｃｔｏｒＲｉ(Ｒｊ)＝００１０
３．［冗長性及び独立性テスト］Ｒｉ及びＲｊに関わる冗長性についてテストするために以下を行う
Ａ．Ｆ＝ＢｉｔＶｅｃｔｏｒＲｊ(Ｒｉ)∧ＢｉｔＶｅｃｔｏｒＲｉ(Ｒｊ)［ビット単位ＡＮＤ演算］を計算する
［ＦがＲｊに等しい場合］Ｒｊは、Ｒｉの上位集合（すなわち、より一般的）である。そうである場合、Ｒｊは冗長であると宣言し、Ｒｉだけを表示に含む
［ＦがＲｉに等しい場合］Ｒｉは冗長であり、表示から同じものを除去する
［ＦがＲｉ及びＲｊのいずれにも等しくない場合］ＲｉとＲｊとは独立しており、表示に双方を維持する。
【０１３７】
例３６‐独立性及び冗長性についての上記手法が動作することの例示的な証明
２つルール｛ＲＡ、ＲＢ｝を仮定し、その各々がＡＶＡの列である。ｉ番目のＡＶＡとｊ番目のＡＶＡとに焦点を当てる。こうしたＡＶＡは、{ＲＡ：Ａｉ＝Ａｖｉ，ＲＢ：Ａｉ＝Ｂｖｉ}、｛ＲＡ：Ａｊ＝Ａｖｊ，ＲＢ：Ａｊ＝Ｂｖｊ｝という形式となる。これは、任意化又は拡張されたルール表現のストラテジに起因して、あらゆる属性が各ルール内に存在することを確かにする。一般性をなんら失うことなしに（‘ｉ’及び‘ｊ’の選択に付された制限は存在しないため）、{Ａｉ，Ａｊ}以外の残りの属性が同じものであると仮定することができる。部分的に開発されたビットベクトルは、同じものであり、例えば‘Ｙ’である。これは、一回に１つのＡＶＡを追加することによって積み上げられたルールを常に構築することができるからである。下記のケースについて考える。
【０１３８】
ケース‐Ｉ：{Ａｖｉ＝Ｂｖｉ}  ＲＡ及びＲＢの各々について生成されるビットベクトルが“Ｙ１”となり、したがって同じものとして残る。これがすべての属性にわたって起こり続ける場合、生成されるビットベクトルは、双方のルールについて厳密に同じものとなる。これらのＡＮＤ演算は、ルールのいずれのビットベクトルも等しくすることになり、アルゴリズムが、ルールのうち一方（重複）を消去することになる。これは、“任意＝任意”のケースを消去することにも対処する。
【０１３９】
ケース‐ＩＩ：{Ａｖｉ≠Ｂｖｉ}  ここで、ＲＡ及びＲＢの各々について生成されるビットベクトルは、Ａｉの値に依存することになる。
【０１４０】
これらのうち一方（例えば、Ａｖｉ）が‘任意’であり、他方（Ｂｖｉ）がそうではない場合、ＲＡのビットベクトルは“Ｙ０”となり、ＲＢのビットベクトルは、“Ｙ１”となる。ここで、２つのビットベクトルのＡＮＤ演算は、“Ｙ０”となり、ＲＢより一般的であるＲＡのものと等しくなる。このアルゴリズムは、こうしたケースにおいて正しく動作する。
【０１４１】
双方の値が‘任意’とは異なり、等しくない場合、この手法は、双方の値を独立しているものとして正しく識別することになる（上記の、冗長なルール及び独立したルールの例示的な判定を参照）。
【０１４２】
ケース‐ＩＩＩ：{Ａｖｉ≠Ｂｖｉ，Ａｖｊ≠Ｂｖｊ，ｉ＜ｊ}  これは、中間にあるすべての他の属性（Ａｋ：ｉ≦ｋ≦ｊ）がそれらの値において合致し、さもなければケース‐Ｉ又はケース‐ＩＩのいずれかに帰着することが、安全に仮定されることができるケースである。｛Ａｖｉ＝‘任意’≠Ｂｖｉ，Ｂｖｊ＝‘任意’≠Ａｖｊ｝というケースは、明らかに、正しい判断がこれらルールを独立しているものとして宣言するべきである相反する状況を、提示している。
【０１４３】
ＲＡのビットベクトルは、“Ｙ０Ａ１”として展開されることになり、ＲＢのビットベクトルは、“Ｙ１Ａ０”になることになる。この部分列に対して再びＡＮＤ演算を行うことは、ＲＡ又はＲＢの双方とは異なるビットベクトル“Ｙ０Ａ０”をもたらすことになる。このアルゴリズムは、ＲＡ及びＲＢを独立しているものとして正しく識別することになる。
【０１４４】
証明終わり。
【０１４５】
例３７‐冗長なルール及び独立したルールについてのサポートの定義の例示的なε拡張（ε-Extension）
独立性又は冗長性について考えられることになる、同じサポートを有する２つのルールの制限は、緩和されることができる。本明細書における例のいずれにおいても、その概念は、サポートのε拡張を含むように拡張されることができる。２つのルール（例えば、Ｒｉ及びＲｊ）は、それらのサポートが最大でεだけ変化する場合、すなわち、|Ｓｕｐ(Ｒｉ)−Ｓｕｐ(Ｒｊ)|＜εの場合、独立性テスト又は冗長性テストについて考慮されることに適格となる。これを、同じε拡張されたサポートを有するＲｉ及びＲｊと呼ぶことができる。
【０１４６】
ε拡張を考慮する手法修正：以下のとおり‘ε拡張’を含むように手法（例えば、例３５を参照）を修正する。
【０１４７】
γをε拡張されたサポートバンドに分割する（例えば、例３８及び／又は例４１を参照）。
【０１４８】
手法（例えば、例３５を参照）のステップを繰り返す。注記：ルールがそれらのサポートに対してどこで比較されていても、各ルールについて、‘サポート’を‘クラスタＩＤ’で置換する。上記のとおり分割した後、各ルールの唯一のメトリックは、サポートに代わって‘クラスタＩＤ’である。例えば、同じクラスタＩＤ（以前は‘サポート’が使用された）に属するルールだけが、それらの冗長性を判定するために取得されることになる。
【０１４９】
例３８‐ルール集合の、ε拡張されたサポートバンドへの、例示的な分割
ルール集合γは、ε近傍クラスタリング手法などの、様々なクラスタリング手法のいずれかを用いて、ε拡張されたサポートバンドに分割されることができる。最近傍クラスタリングが、使用されることができる。
【０１５０】
例３９‐性能についての例示的なメトリクス
下記のメトリクスは、上記手法の性能を定量化する。以下のすべてのメトリクスにおいて、γを、各ルールがμ以上のサポートを有し、かつルールがそのサポートの降順に配置されているところの、適格とされたＡＲルールの集合であると仮定することができる。さらに、最終的に開発者はシステム内の上位λ個のルールだけを目にすることになると仮定することができる。
【０１５１】
％冗長性消去（％ＲＥ）：これは、合計（|γ|）のうち、アルゴリズムによって冗長であるとマーク付けされたルールの(％)を捉える。
【０１５２】
(％)カバレッジ増加（％ＣＧ）：冗長性消去後に上位λウィンドウに入れられる最後のルールが、元のルール集合‘γ’において‘δ’とランク付けされる場合、％ＣＧ＝(δ／λ−１)である。
【０１５３】
(％)削減（％ＫＯ）：このメトリックは、表示される最大の‘Ｎ’個のルールのうち、アルゴリズムによって冗長であるとして削減された上位（λ）のルールの(％)を示す。
【０１５４】
上記メトリクスは、こうしたアルゴリズムの成功を判定することに対して非常に有用である。図１４が、さらなる詳細を示す。
【０１５５】
例４０‐ルール順序付けの例示的な手法
一フレームワークが、ルールの自動化された順序付けを開始して、非冗長なルールの上位λウィンドウへの露出を最大化することができる。
入力：
ＡＲで生成されたルールの集合：γ。このルールの集合は、その構成要素であるルールのサポートの降順にソートされる。すべてのルールがμより大きいサポートを有することが保証されている。‘μ’（例えば、０．０１）が、ルールの最小サポートとして既知である
開発者に視認可能な上位λ個のルールを包含する上位λウィンドウとしての‘λ’（<<|γ|）
出力：
改定された、非冗長なルールの集合（γｎｒ）。このリストから上位λ個を取得して、上位λウィンドウを埋める
前提
ルールは、詳細な実装例が要求するとおりに関連するデータ構造を有する。以下のステップにおいて、ルールは、そのフィールドの１つとして‘状態’を有し、状態は、｛Ｉｎ，Ｏｕｔ｝の範囲内の値を有する。これは、ルールが独立している（‘Ｉｎ’）か、あるいは冗長である（‘Ｏｕｔ’）かを示す
動作：
１．開始
２．γｎｒを定義し、γｎｒ←Φ（空集合）で初期化する
３．各ルールｒ∈γについて
ａ．あらゆる欠損している属性について‘任意’値を挿入することによって、‘ｒ’をその拡張された表現（例えば、例３３を参照）に変換する。ここで、Ａ∈Ω、かつ
【数１】
2015508918.tif 000004
である
ｂ．ｒ.ｓｔａｔｕｓ←‘Ｉｎ’
４．各(ｒｉ∈γ，ｉ∈[１，|γ|)について
ａ．(ｒｉ.ｓｔａｔｕｓ＝＝‘Ｏｕｔ’)が真である場合、残りをスキップし、次の繰り返し［ｉループ］を開始する；
ｂ．各(ｒｊ∈γ，ｊ＝ｉ＋１＆ｊ＜|γ|)について
ｉ．(ｒｊ.ｓｔａｔｕｓ＝＝‘Ｏｕｔ’)が真である場合、残りをスキップし、次の繰り返し［ｊループ］を開始する；
ｉｉ．(ｒｉ，ｒｊ)が次のいずれかであるかをチェックする：
独立である（例えば、例３５）
そうである場合、γｎｒ←γｎｒＵ｛ｒｉ，ｒｊ｝．
ｒｉ.ｓｔａｔｕｓ←‘Ｉｎ’；
ｒｊ.ｓｔａｔｕｓ←‘Ｉｎ’；
冗長である（例えば、例３５）
(ｒｉが冗長である)が真である場合、｛ｒｉ.ｓｔａｔｕｓ←‘Ｏｕｔ’；ｒｊ.ｓｔａｔｕｓ←‘Ｉｎ’；γｎｒ←γｎｒＵ｛ｒｊ｝｝
そうでない場合、｛ｒｊ.ｓｔａｔｕｓ←‘Ｏｕｔ’；ｒｉ.ｓｔａｔｕｓ←‘Ｉｎ’；γｎｒ←γｎｒＵ｛ｒｉ｝｝
ｃ．(ｊループ)の終了
５．(ｉループ)の終了
６．‘γｎｒ’は、ルールのサポートの降順で順序付けされた独立したルールを包含する。別法として、γは、‘状態’が‘Ｉｎ’又は‘Ｏｕｔ’としてマーク付けされて埋められており、かつ‘γｎｒ’と同様に有用であるルールを含む
７．終了。
【０１５６】
例４１‐ε拡張されたサポートバンドを作成するための例示的なクラスタリング手法
一クラスタリング手法（例えば、最近傍）を、この問題に対して使用することができる。
入力：
ＡＲで生成されたルールの集合：γ。このルールの集合は、その構成要素であるルールのサポートの降順にソートされる
‘ε’すなわちサポートバンドであり、その範囲内で、ルールは同じ‘拡張されたサポート’値を有するとみなされる（例えば、非常に近接する）
出力：
あらゆるルールが一意のクラスタＩＤを割り当てられている、ルールの集合γ
発見された一意のクラスタの数Ｃ
前提
ルールは、関連するデータ構造を、その詳細な実装例に従って有し、具体的に、ルールは下記のフィールドを有する
アイテム集合（ＡＲ専門用語）の出現の頻度を示す‘サポート’
ルールが冗長である（‘Ｏｕｔ’）のか、あるいは重要である（‘Ｉｎ’）のかを示す‘状態’
ルールがどのクラスタに属するのかを示す‘クラスタＩＤ’
動作：
１．｛
２．２つのinteger型配列、すなわちsortedindex[|γ|]，clusterIDs[|γ|]を定義する
３．ｒ∈γである各ルールのサポートを格納するdouble型配列、value[|γ|]を定義する
４．降順の値となっているvalue[]配列のインデクスで、sortedindex[]を初期化する
５．clusterIDs[]エントリを‘-1’で初期化する
６．lastgrp←0；clusterIDs[sortedIndex[0]]←lastgrp；indmaxlastgr←0；alreadyentered=false;
７．for(cnt=1；cnt<|γ|；cnt++)
８．｛
９．val1=value[sortedIndex[indmaxlastgrp]]-value[sortedIndex[cnt]]；
１０．(val1≦ε)が真である場合
ａ．clusterlDs[sortedindex[cnt]]=clusterlDs[sortedindex[cnt-1]]；  /*  同じクラスタに属する  */
１１．他の場合
ａ．｛
i．clusterlDs[sortedindex[cnt]]=clusterlDs[sortedindex[cnt-1]]+1；
ii．alreadyentered=false；
iii．/*  可能な場合、古いメンバを新しいクラスタに再調整する  */
iv．for(j=indmaxlastgrp+1；j<cnt；j++)
v．｛
vi．val2=value[sortedIndex[j]]-value[sortedIndex[cnt]]；
vii．(val2＜ε)が真である場合
viii．｛
(!alreadyentered)が真である場合、｛indmaxlastgrp=j；alreadyentered=true；｝
clusterlDs[sortedindex[j]]=clusterlDs[sortedindex[cnt]]；
ix．｝
x．｝  /*  内側のforループの終了  */
xi．(!alreadyentered)が真である場合、indmaxlastgrp=cnt；
ｂ．｝
１２．｝  /*  forループの終了  */
１３．  /*  一意のクラスタが何個作成されたかを再計算  */
１４．C=clusterlDs[sortedindex[|γ|]]+1；
１５．｝  /*  クラスタリングの終了  */  。
【０１５７】
例４２‐ε拡張されたサポートバンドを含むための手法の例示的な修正
ε拡張されたサポート（例えば、例４１のもの）を考慮するために、以下の動作に従うことができる。
【０１５８】
ルール[γ]をεバンドにクラスタ化し、各ルールにクラスタＩＤを割り当てる（例えば、例４１のもの）。原理上、ここで、任意のクラスタリングアルゴリズムを使用することができる。
【０１５９】
手法（例えば、例３５）を修正して、関連するルールについて、未加工のサポートに代わってクラスタＩＤだけを比較する（例えば、‘同じサポートを有する’という節を、‘同じクラスタＩＤを有する’で置換する）。
【０１６０】
上記の修正を用いて、最終的な手法動作は、下記のとおりとなる（ε拡張なしの手法からのずれが、以下で強調される）。
入力：
ＡＲ（相関ルール手法）で生成されたルールの集合：γ。ルールの集合は、その構成要素であるルールのサポートの降順にソートされる
開発者に視認可能な上位λ個のルールを包含する上位λウィンドウとしての‘λ’（<<|γ|）
‘ε’すなわちサポートバンドであり、その範囲内で、ルールは同じ‘拡張されたサポート’値を有するとみなされる（例えば、非常に近接する）
出力：
改定された、非冗長なルールの集合（γｎｒ）。このリストから上位λ個を取得して、上位λウィンドウを埋める
動作：
１．開始
２．γｎｒを定義し、γｎｒ←Φ（空集合）で初期化する
３．クラスタリング手法（例えば、例４１）に基づいて、εを所与としてγをクラスタ化する
４．各ルールｒ∈γについて
ａ．あらゆる欠損している属性について‘任意’値を挿入することによって、‘ｒ’をその拡張された表現（例えば、例３３）に変換する。ここで、Ａ∈Ω、かつ
【数２】
2015508918.tif 000005
である
ｂ．ｒ.ｓｔａｔｕｓ←‘Ｉｎ’
５．各(ｒｉ∈γ，ｉ∈[１，|γ|)について
ａ．(ｒｉ.ｓｔａｔｕｓ＝＝‘Ｏｕｔ’)が真である場合、残りをスキップし、次の繰り返し［ｉループ］を開始する；
ｂ．各(ｒｊ∈γ，ｊ＝ｉ＋１＆ｊ＜|γ|)について
ｉ．(ｒｊ.ｓｔａｔｕｓ＝＝‘Ｏｕｔ’)が真である場合、残りをスキップし、次の繰り返し［ｊループ］を開始する；
ｉｉ．(ｒｉ，ｒｊ)が次のいずれかであるかをチェックする：
独立である（例えば、例３４及び例３５）
そうである場合、γｎｒ←γｎｒＵ｛ｒｉ，ｒｊ｝．
ｒｉ.ｓｔａｔｕｓ←‘Ｉｎ’；
ｒｊ.ｓｔａｔｕｓ←‘Ｉｎ’；
冗長である（例えば、例３４及び例３５）
(ｒｉが冗長である)が真である場合、｛ｒｉ.ｓｔａｔｕｓ←‘Ｏｕｔ’；ｒｊ.ｓｔａｔｕｓ←‘Ｉｎ’；γｎｒ←γｎｒＵ｛ｒｊ｝｝
そうでない場合、｛ｒｊ.ｓｔａｔｕｓ←‘Ｏｕｔ’；ｒｉ.ｓｔａｔｕｓ←‘Ｉｎ’；γｎｒ←γｎｒＵ｛ｒｉ｝｝
ｃ．(ｊループ)の終了
６．(ｉループ)の終了
７．‘γｎｒ’は、ルールのサポートの降順で順序付けされた独立したルールを包含する。別法として、γは、‘状態’が‘Ｉｎ’又は‘Ｏｕｔ’としてマーク付けされて埋められており、かつ‘γｎｒ’と同様に有用であるルールを含む
８．終了。
【０１６１】
例４３‐ε拡張された手法に対する、例示的な領域特化型の変更
領域特化型の知識を通じて、さらにルールを精緻化することができる。アプリケーションストアにおいて、例えば、あるルール内に‘国’なしで‘州’属性だけが存在しているかどうかをチェックすることができる。この場合、州情報を所与として、記憶された参照テーブルから国情報を読み出す。ルールが冗長性消去を受けるまでになされ得ることが可能な多くのこうした精緻化が存在し得る。
【０１６２】
例４４‐上記手法の例示的な改良
上記のε拡張されたアルゴリズムにおいて、クラスタリングは、ルール間の集合‐部分集合にかかわらず、適用されることができる。あるルールの集合、すなわち、γ＝｛Ｒ１，Ｒ２，Ｒ３，Ｒ４｝を考える。ただし、｛Ｒ１，Ｒ２｝は依存性があり、その残りは依存性がないものとする。このルールは、そのサポートに関して等距離であり、そのサポート間の距離は、(ε−δ)であり、ただしδ<<εとする。γに対して最近傍クラスタリングを実行するとき、上記手法によって生成されるクラスタの集合は、［｛Ｒ１｝，｛Ｒ２｝，｛Ｒ３，Ｒ４｝］となる。前提として｛Ｒ３，Ｒ４｝が独立であるため、縮小されたルールの集合（γｎｒ）はγと同じものになる。
【０１６３】
しかしながら、｛Ｒ１，Ｒ２｝が確実にε距離の範囲内にあるため、最初に｛Ｒ１，Ｒ２｝が縮小され得た。ゆえに、提案されるアルゴリズムの精度は、こうしたまれなケースについて明らかに苦しむ。
【０１６４】
まれなケースについてさえも精度を改良するために、下記を行うことができる。
Ａ．ルール集合γに対して、集合‐部分集合識別アルゴリズムを実行する。これは、ルール集合のリストγ＝｛γ１，…，γｋ｝を生成することになる
γｉ（ｉ番目のルールリスト、ｉ＝１…ｋ）は、包含関係を通じて関連するルールを包含する
γｉの範囲内のルールは、そのサポートを用いて、より一般的なものから非常に具体的なものへと降順に順序付けられる
Ｂ．各γｉ（ｉ番目のルールリスト、ｉ＝１…ｋ）について、ε及びγｉを所与として、ε拡張されたサポートバンドを実施する手法を適用する。γｉ内のルールは集合‐部分集合関係を保有することが既知であるため、速度の効率を目的として、集合‐部分集合判定ステップはスキップされることができる。ここで、冗長なルールは、前述のように“ｏｕｔ”とマーク付けされる
Ｃ．ここで、γのうち“ｉｎ”とマーク付けされた状態を有するすべてのルールを含むことによって、非冗長なルール集合γｎｒを生成する
Ｄ．停止。
【０１６５】
上記に挙げられたような例外的なケースについて、上記の改定されたアルゴリズムに従って、ステップａは、γをγ＝(｛Ｒ１｝，｛Ｒ２｝，｛Ｒ３，Ｒ４｝)に分割し、このリストの各々についてステップｂを適用することになる。｛Ｒ３，Ｒ４｝がε近傍にあると仮定すると、このリストは縮小されることになる。ここで、識別された、非冗長なルールの集合は、より精緻なものとなる。
【０１６６】
例４５‐例示的なεの選択
上記のε拡張されたアルゴリズムにおいて、クラスタリングは、パラメータ‘ε’の選択による影響を受けることになる。
【０１６７】
ＡＲアルゴリズムについて明らかであるように、（集合‐部分集合を通じて関連する）パターンのサポートは、これがパターンの閾値長さを超えて急激に落ち込むまで、互いに近接して存在する。このことは、冗長なルールが非常に近接してクラスタ化され、分離がその後急激に増加することを意味する。しがたって、小さな値の‘ε’が、クラスタリングの目的を満足させることになる。
【０１６８】
εは、全体のルール集合γのトランザクションの総数（Ｎ）の関数、すなわちε(Ｎ)とすることができる。したがって、例えば、以下のとおり、‘ε’とＮとの間で観察された関係を捉えた表を作成することができる。
【表２】
2015508918.tif 000006
【０１６９】
ε＝０．０１、すなわち１％が、一様に選択されることができ、あるいはεは、上記の表から選択されることができる。あるいは、パラメータは、ユーザによって設定可能とすることができる。
【０１７０】
例４６−例示的な性能
種々のデータ（発見されたルール）集合に対する種々の実験を実行して、言及されたメトリクスの性能を測定した（本明細書に説明された性能のメトリクスを参照）。データ集合は、例えば‘アプリ’、‘カテゴリ’、‘サブカテゴリ’などの、構成要素である検索可能な要素の各々についての、種々のＡＲモデルを有する。アプリケーションストアからのデータを含む実世界データの２つの集合と、冗長性消去の手法の性能をベンチマークする２つの合成データ集合とが、使用された。
【０１７１】
以下の表は、＜μ＝０．０３，ε＝０．０１，Ｎ＝５＞について、前述のメトリクスの性能データを捉えている。種々のデータ集合にわたって、その構成要素であるモデルを通じて、それは、モデルの８７．８％を改良している。実世界データにのみ焦点を当てる場合、検討されたモデルのうち９５％が冗長性消去をもたらしており、これは明らかに、この手法の有効性を示すものである。
【０１７２】
以下の例において、μ＜０．０３，ε＝０．０２，Ｎ＝５である。イプシロンフィルタリングが最初に行われ、次に、適用された包含関係が適用された。別法として、包含されたルールのリストが最初に作成され、εサポートクラスタリングがその後に続き、さらに高度な冗長性除去メトリクスをもたらすことができる。
【表３】
2015508918.tif 000007
【０１７３】
上記データ集合の各々の詳細な性能データが、最小サポート（μ）、イプシロン（ε）を変化させることによってプロットされている。
【０１７４】
モデルが、モデル自体が含むルールの数に基づいて、６つの範囲［範囲１（Range1）：１〜１０、範囲２（Range2）：１１〜２０、範囲３（Range3）：２１〜３０、範囲４（Range4）：３１〜４０、範囲５（Range5）：４１〜５０、範囲６（Range6）：＞５０］にカテゴリ分けされている。
【０１７５】
詳細な性能グラフが、各データ集合について、％ＫＯ、％ＲＥ，％ＣＧ及び一体型（All  In  One）として整理される。データ集合‐Ａ（合成）の詳細なグラフ、データ集合‐Ｃ（実世界）の性能グラフが図面において利用可能である。図１７、図１８、図１９及び図２０は、データ集合性能を示すグラフである。
【０１７６】
例４７‐例示的なコンピューティングシステム
図２１は、適切なコンピューティングシステム２１００の一般化された例を示し、コンピューティングシステム２１００において、説明された発明のいくつかを実施することができる。本発明は、多様な汎用目的又は特別目的のコンピューティングシステムにおいて実施できるものであり、コンピューティングシステム２１００は、利用又は機能性について何らかの限定を示唆するものではない。
【０１７７】
図２１を参照すると、コンピューティングシステム２１００は、１又は複数の処理ユニット２１１０、２１１５と、メモリ２１２０、２１２５とを含む。図２１において、この基本的な構成２１３０は、破線内に含まれる。処理ユニット２１１０、２１１５は、コンピュータ実行可能命令を実行する。処理ユニットは、汎用目的の中央処理装置（ＣＰＵ）、特定用途向け集積回路（ＡＳＩＣ）内のプロセッサ、又は任意の他の種類のプロセッサとすることができる。多重処理システムにおいて、多重処理ユニットがコンピュータ実行可能命令を実行して処理能力を増加させる。例えば、図２１は、中央処理装置２１１０と、グラフィックス処理ユニット又はコプロセシングユニット２１１５とを示している。有形のメモリ２１２０、２１２５は、処理ユニット（群）によってアクセス可能な揮発性メモリ（例えば、レジスタ、キャッシュ、ＲＡＭ）、不揮発性メモリ（例えば、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリなど）、又はこの２つの何らかの組み合わせとすることができる。メモリ２１２０、２１２５は、処理ユニット（群）による実行に適したコンピュータ実行可能命令の形式で、消費者トランザクション冗長性フィルタリングについての１又は複数の発明を実施するソフトウェア２１８０を記憶する。
【０１７８】
コンピューティングシステムは、さらなる特徴を有することができる。例えば、コンピューティングシステム２１００は、記憶装置２１４０、１又は複数の入力装置２１５０、１又は複数の出力装置２１６０、及び１又は複数の通信接続２１７０を含む。バス、コントローラ又はネットワークなどの相互接続機構（図示せず）が、コンピューティングシステム２１００のコンポーネントを相互接続する。通常、オペレーティングシステムソフトウェア（図示せず）が、コンピューティングシステム２１００内で動作する他のソフトウェアにオペレーティング環境を提供し、コンピューティングシステム２１００のコンポーネントのアクティビティを連携させる。
【０１７９】
有形の記憶装置２１４０は、取り外し可能又は取り外し不能とすることができ、磁気ディスク、磁気テープ若しくはカセット、ＣＤ−ＲＯＭ、ＤＶＤ、又は、非一時的な方法で情報を記憶することに使用されることができ、かつコンピューティングシステム２１００内でアクセスされることができる任意の他の媒体を含む。記憶装置２１４０は、消費者トランザクションルール冗長性フィルタリングのための１又は複数の発明を実施するソフトウェア２１８０の命令を記憶する。
【０１８０】
入力装置（群）２１５０は、キーボード、マウス、ペン若しくはトラックボールなどのタッチ入力装置、音声入力装置、スキャニング装置、又は、コンピューティングシステム２１００に入力を提供する別の装置とすることができる。ビデオ符号化について、入力装置（群）２１５０は、カメラ、ビデオカード、ＴＶチューナーカード、若しくはアナログ若しくはデジタルの形式でビデオ入力を受け入れる類似の装置、又は、コンピューティングシステム２１００にビデオサンプルを読み込むＣＤ−ＲＯＭ若しくはＣＤ−ＲＷとすることができる。出力装置（群）２１６０は、ディスプレイ、プリンタ、スピーカ、ＣＤライタ、又は、コンピューティングシステム２１００から出力を提供する別の装置とすることができる。
【０１８１】
通信接続（群）２１７０は、通信媒体を介して、別のコンピューティングエンティティへの通信を可能にする。通信媒体は、コンピュータ実行可能命令、オーディオ若しくはビデオの入力若しくは出力、又は変調されたデータ信号における他のデータなどの、情報を伝達する。変調されたデータ信号は、情報を信号内に符号化するように、その特性の１又は複数を設定又は変更させた信号である。限定ではなく例として、通信媒体は、電気的、光学的、ＲＦ又は他の搬送波を使用することができる。
【０１８２】
本発明は、コンピュータ読取可能媒体の一般的背景において説明されることができる。コンピュータ読取可能媒体は、コンピューティング環境内でアクセスされることができる任意の利用可能な有形の媒体である。限定ではなく例として、コンピューティングシステム２１００において、コンピュータ読取可能媒体には、メモリ２１２０、２１２５、記憶装置２１４０、及び上記のいずれかの組み合わせを含む。
【０１８３】
本発明は、コンピュータ内で対象の実際又は仮想のプロセッサ上で実行される、プログラムモジュールに含まれる命令などの、コンピュータ実行可能命令の一般的背景において説明されることができる。概して、プログラムモジュールは、特定のタスクを実行し、あるいは特定の抽象データ型を実施するルーチン、プログラム、ライブラリ、オブジェクト、クラス、コンポーネント、データ構造などを含む。プログラムの機能性は、種々の実施形態において所望されるとおりに、プログラムモジュール間で組み合わせられ、あるいは分割されることができる。プログラムモジュールのコンピュータ実行可能命令は、ローカルの又は分散型のコンピューティングシステム内で実行されることができる。
【０１８４】
用語「システム」及び「装置」は、本明細書において、互換的に使用される。文脈が明示的にその他の方法で示していない限り、どちらの用語も、コンピューティングシステム又はコンピューティング装置の種類に対して何らかの限定をするものではない。一般に、コンピューティングシステム又はコンピューティング装置は、ローカル又は分散型とすることができ、専用目的ハードウェア及び／又は汎用目的ハードウェアと本明細書に説明される機能性を実施するソフトウェアとの任意の組み合わせを含むことができる。
【０１８５】
表現のため、本詳細な説明は、「判定する」及び「使用する」などの用語を使用してコンピューティングシステム内のコンピュータ動作を説明している。これらの用語は、コンピュータによって実行される動作のハイレベルの抽象化であり、人間によって行われる動作と混同されるべきではない。これらの用語に対応する実際のコンピュータ動作は、実装に依存して変化する。
【０１８６】
例４８‐例示的なモバイル装置
図２２は、例示的なモバイル装置２２００を表すシステム図であり、モバイル装置２２００は、概して２２０２で示される、様々な随意的なハードウェア及びソフトウェアコンポーネントを含む。モバイル装置内の任意のコンポーネント２２０２が、任意の他のコンポーネントと通信することができるが、図示の簡易化のため、すべての接続が示されているわけではない。モバイル装置は、様々なコンピューティング装置（例えば、セルフォン、スマートフォン、ハンドヘルドコンピュータ、パーソナルデジタルアシスタント（ＰＤＡ）など）のいずれかとすることができ、セルラー、衛星又は他のネットワークなどの１又は複数のモバイル通信ネットワーク２２０４を用いて無線の双方向通信を可能にすることができる。
【０１８７】
図示されたモバイル装置２２００は、信号符号化、データ処理、入力／出力処理、電源制御及び／又は他の機能などのタスクを実行するためのコントローラ又はプロセッサ２２１０（例えば、シングルプロセッサ、マイクロプロセッサ、ＡＳＩＣ、又は他の制御及び処理論理回路）を含むことができる。オペレーティングシステム２２１２は、コンポーネント２２０２の割り振り及び使用を制御し、１又は複数のアプリケーションプログラム２２１４をサポートすることができる。アプリケーションプログラムには、一般的なモバイルコンピューティングアプリケーション（例えば、電子メールアプリケーション、カレンダ、連絡先管理部、ウェブブラウザ、メッセージングアプリケーション）、又は任意の他のコンピューティングアプリケーションを含むことができる。さらに、アプリケーションストアにアクセスするための機能性２２１３が、アプリケーション２２１４を取得し、アップデートすることに対して使用されることができる。
【０１８８】
図示されたモバイル装置２２００は、メモリ２２２０を含むことができる。メモリ２２２０は、取り外し不能メモリ２２２２及び／又は取り外し可能メモリ２２２４を含むことができる。取り外し不能メモリ２２２２には、ＲＡＭ、ＲＯＭ、フラッシュメモリ、ハードディスク、又は他の周知のメモリ記憶装置技術を含むことができる。取り外し可能メモリ２２２４には、フラッシュメモリ、若しくはＧＳＭ(登録商標)通信システムにおいて周知である加入者識別モジュール（ＳＩＭ）カード、又は「スマートカード」などの他の周知のメモリ記憶装置技術を含むことができる。メモリ２２２０は、オペレーティングシステム２２１２及びアプリケーション２２１４を実行するためのデータ及び／又はコードを記憶することに使用されることができる。例となるデータには、１又は複数の有線又は無線のネットワークを介して、１若しくは複数のネットワークサーバ又は他の装置と送受信されるウェブページ、テキスト、画像、サウンドファイル、ビデオデータ、又は他のデータ集合を含むことができる。メモリ２２２０を使用して、国際移動体加入者識別番号（International  Mobile  Subscriber  Identity；ＩＭＳＩ）などの加入者識別子、及び国際移動体機器識別番号（International  Mobile  Equipment  Identifier；ＩＭＥＩ）などの機器識別子を記憶することができる。こうした識別子がネットワークサーバに送信されて、ユーザ及び機器を識別することができる。
【０１８９】
モバイル装置２２００は、タッチ画面２２３２、マイクロフォン２２３４、カメラ２２３６、物理的キーボード２２３８及び／又はトラックボール２２４０などの１又は複数の入力装置２２３０と、スピーカ２２５２及びディスプレイ２２５４などの１又は複数の出力装置２２５０とをサポートすることができる。他の有り得る出力装置（図示せず）には、圧電性の又は他の触覚に基づく出力装置を含むことができる。いくつかの装置は、２以上の入力／出力機能を果たすことができる。例えば、タッチ画面２２３２とディスプレイ２２５４とを組み合わせて単一の入力／出力装置とすることができる。
【０１９０】
当分野において十分に理解されているとおり、無線モデム２２６０は、アンテナ（図示せず）に結合されることができ、プロセッサ２２１０と外部装置との間の双方向通信をサポートすることができる。モデム２２６０は、一般的に示されており、モバイル通信ネットワーク２２０４及び／又は他の無線ベースのモデム（例えば、ブルートゥース又はワイファイ）と通信するためのセルラ方式モデムを含むことができる。無線モデム２２６０は、通常、単一のセルラーネットワーク内、複数セルラーネットワーク間、又はモバイル装置と公衆交換電話網（ＰＳＴＮ）との間でのデータ通信及び音声通信のためのＧＳＭ(登録商標)ネットワークなどの、１又は複数のセルラーネットワークとの通信に対して構成される。
【０１９１】
モバイル装置は、さらに、少なくとも１つの入力／出力ポート２２８０、電源供給２２８２、グローバルポジショニングシステム（ＧＰＳ）受信部などの衛星ナビゲーションシステム受信部２２８４、加速度計２２８６、並びに／又は、ＵＳＢポート、ＩＥＥＥ１３９４（ファイヤワイヤ）ポート及び／若しくはＲＳ−２３２ポートとすることができる物理的コネクタ２２９０を含むことができる。図示されたコンポーネント２２０２は、必要ではなく、あるいはすべてを含むものではなく、任意のコンポーネントが削除されることができ、他のコンポーネントが追加されることができる。
【０１９２】
例４９‐例示的なクラウドサポートされた環境
例となる環境２３００において、クラウド２３１０は、様々な画面能力を有する接続された装置２３３０、２３４０、２３５０に、サービスを提供する。接続された装置２３３０は、コンピュータ画面２３３５（例えば、中間サイズの画面）を有する装置を表す。例えば、接続された装置２３３０は、デスクトップコンピュータ、ラップトップ、ノートブック、ネットブックなどのパーソナルコンピュータとすることができる。接続された装置２３４０は、モバイル装置画面２３４５（例えば、小さいサイズの画面）を有する装置を表す。例えば、接続された装置２３４０は、モバイルフォン、スマートフォン、パーソナルデジタルアシスタント、タブレット型コンピュータなどとすることができる。接続された装置２３５０は、大きい画面２３５５を有する装置を表す。例えば、接続された装置２３５０は、テレビ画面（例えば、多機能テレビ）、又はテレビに接続された別の装置（例えば、セットトップボックス又はゲーム用コンソール）などとすることができる。接続された装置２３３０、２３４０、２３５０のうち１又は複数は、タッチ画面能力を含むことができる。タッチ画面は、種々の方法で入力を受け入れることができる。例えば、物体（例えば、指先又はスタイラス）が、表面にわたって走っている電流を歪め、あるいは遮断するとき、容量性のタッチ画面が、タッチ入力を検出する。別の例として、タッチ画面は、光学的センサを使用して、光学的センサからのビームが遮断されたときにタッチ入力を検出することができる。画面の表面との物理的接触は、いくつかのタッチ画面により検出される入力について、必ずしも必要ない。画面能力のない装置もまた、例となる環境２３００において使用されることができる。例えば、クラウド２３１０は、ディスプレイなしの１又は複数のコンピュータ（例えば、サーバコンピュータ）にサービスを提供することができる。
【０１９３】
サービスは、サービスプロバイダ２３２０を通じて、あるいは他のオンラインサービスのプロバイダ（表示せず）を通じて、クラウド２３１０によって提供されることができる。例えば、クラウドサービスは、特定の接続された装置（例えば、接続された装置２３３０、２３４０、２３５０）の画面サイズ、ディスプレイ能力及び／又はタッチ画面能力についてカスタマイズされることができる。
【０１９４】
例となる環境２３００において、クラウド２３１０は、少なくとも部分的にサービスプロバイダ２３２０を使用して、種々の接続された装置２３３０、２３４０、２３５０に、本明細書に説明される技術及びソリューションを提供する。例えば、サービスプロバイダ２３２０は、種々のクラウドベースのサービスに、集中型のソリューションを提供することができる。サービスプロバイダ２３２０は、ユーザ及び／又は装置の（例えば、接続された装置２３３０、２３４０、２３５０及び／又はそのそれぞれのユーザについての）サービス加入を管理することができる。
【０１９５】
例５０‐例示的な実装
開示された方法のいくつかの動作が、簡便な表現のため、特定の連続した順序で説明されているが、この説明による方法は、特定の順序付けが以下に明記される具体的な言葉によって必要とされない限り、再配置を包含することを理解されたい。例えば、連続して説明された動作は、いくつかの場合に、再配置され、あるいは同時に実行されてよい。その上、簡便さのため、添付された図は、開示された方法が他の方法と関連して使用されることができるための種々の方法を示していない場合がある。
【０１９６】
開示された方法のいくつかは、１又は複数のコンピュータ読取可能記憶媒体（例えば、１又は複数の光媒体ディスクなどの非一時的なコンピュータ読取可能媒体、揮発性メモリコンポーネント（例えば、ＤＲＡＭ又はＳＲＡＭ）、又は不揮発性メモリコンポーネント（ハードドライブなど））上に記憶され、コンピュータ（例えば、スマートフォン又はコンピューティングハードウェアを含む他のモバイル装置を含む、任意の市販のコンピュータ）上で実行されるコンピュータ実行可能命令として実施されることができる。開示された手法を実施するコンピュータ実行可能命令の任意のものと、開示された実施形態の実施の間に作成され、使用される任意のデータとは、１又は複数のコンピュータ読取可能媒体（例えば、非一時的なコンピュータ読取可能媒体）に記憶されることができる。コンピュータ実行可能命令は、例えば、専用のソフトウェアアプリケーション、又は、ウェブブラウザ若しくは他のソフトウェアアプリケーション（リモートコンピューティングアプリケーションなど）を介してアクセスされ、あるいはダウンロードされるソフトウェアアプリケーションの、一部とすることができる。こうしたソフトウェアは、例えば、単一のローカルコンピュータ（例えば、任意の適切な市販のコンピュータ）上で、あるいは１又は複数のネットワークコンピュータを用いてネットワーク環境内で（例えば、インターネット、ワイドエリアネットワーク、ローカルエリアネットワーク、クライアントサーバネットワーク（クラウドコンピューティングネットワークなど）又は他のこうしたネットワークを介して）実行されることができる。
【０１９７】
明りょうさのため、特定の選択された態様のソフトウェアベースの実装だけが説明されている。当分野において周知である他の詳細は、省略されている。例えば、開示された技術は、いかなる具体的なコンピュータ言語又はプログラムにも限定されないことを理解されたい。例えば、開示された技術は、Ｃ＋＋、Ｊａｖａ(登録商標)、Ｐｅｒｌ、ＪａｖａＳｃｒｉｐｔ(登録商標)、ＡｄｏｂｅＦｌａｓｈ又は任意の他の適切なプログラミング言語で書かれたソフトウェアによって実装されることができる。同様にして、開示された技術は、いかなる特定のコンピュータにも、あるいはいかなる特定の種類のハードウェアにも限定されない。適切なコンピュータ及びハードウェアの特定の詳細は周知であり、本開示において詳細に明記される必要はない。
【０１９８】
さらに、ソフトウェアベースの実施形態（例えば、開示された方法のうち任意のものをコンピュータに実行させるコンピュータ実行可能命令を含む）のいずれもが、適切な通信手段を通じて、アップロードされ、ダウンロードされ、あるいは遠隔からアクセスされることができる。こうした適切な通信手段には、例えば、インターネット、ワールドワイドウェブ、イントラネット、ソフトウェアアプリケーション、ケーブル（光ファイバケーブルを含む）、磁気通信、電磁気通信（ＲＦ、マイクロ波及び赤外線通信を含む）、電子的通信、又は他のこうした通信手段を含む。
【０１９９】
開示された方法、装置及びシステムは、いかなる方法においても限定するものと見なされるべきではない。代わって、本開示は、単独で、並びに互いの種々の組み合わせ及び副次的な組み合わせにおいて、種々の開示された実施形態についてのすべての新規かつ非自明の特徴及び態様に向けられている。開示された方法、装置及びシステムは、そのいかなる特定の態様若しくは特徴又は組み合わせにも限定されず、開示された実施形態は、何らかの１又は複数の特定の利点が存在すること、又は問題が解決されることを、必要とするものではない。
【０２００】
非一時的なコンピュータ読取可能媒体
本明細書におけるコンピュータ読取可能媒体のいずれも、非一時的なもの（例えば、メモリ、磁気記憶装置、光学記憶装置など）とすることができる。
【０２０１】
コンピュータ読取可能媒体への記憶
本明細書に説明される記憶動作のいずれも、１又は複数のコンピュータ読取可能媒体（例えば、コンピュータ読取可能記憶媒体又は他の有形媒体）に記憶することによって実施されることができる。
【０２０２】
記憶されると説明されたもののいずれも、１又は複数のコンピュータ読取可能媒体（例えば、コンピュータ読取可能記憶媒体又は他の有形媒体）に記憶されることができる。
【０２０３】
コンピュータ読取可能媒体における方法
本明細書に説明される方法のいずれも、１又は複数のコンピュータ読取可能媒体（例えば、コンピュータ読取可能記憶媒体又は他の有形媒体）内の（例えば、上記コンピュータ読取可能媒体上に符号化された）コンピュータ実行可能命令によって実施されることができる。こうした命令が、コンピュータに本方法を実行させることができる。本明細書に説明される技術は、様々なプログラミング言語で実装されることができる。
【０２０４】
コンピュータ読取可能記憶装置における方法
本明細書に説明される方法のいずれも、１又は複数のコンピュータ読取可能記憶装置（例えば、メモリ、磁気記憶装置、光学記憶装置など）に記憶されたコンピュータ実行可能命令によって実施されることができる。こうした命令が、コンピュータに本方法を実行させることができる。
【０２０５】
代替策
任意の例による技術を、その他の例のうち任意の１又は複数において説明された技術と組み合わせることができる。開示された技術の原理を適用することができる、多くの有り得る実施形態を考慮して、解説された実施形態は開示された技術の例であり、開示された技術の範囲に対する限定と解されるべきではないことを、認識されたい。むしろ、開示された技術の範囲は、別記の請求項によって対象にされるものを含む。したがって、発明者らは、請求項の範囲及び主旨の内に入るすべてのものを自身らの発明として請求する。
【図１】
2015508918.tif 000008
【図２】
2015508918.tif 000009
【図３】
2015508918.tif 000010
【図４】
2015508918.tif 000011
【図５】
2015508918.tif 000012
【図６】
2015508918.tif 000013
【図７】
2015508918.tif 000014
【図８】
2015508918.tif 000015
【図９】
2015508918.tif 000016
【図１０】
2015508918.tif 000017
【図１１】
2015508918.tif 000018
【図１２】
2015508918.tif 000019
【図１３】
2015508918.tif 000020
【図１４】
2015508918.tif 000021
【図１５】
2015508918.tif 000022
【図１６】
2015508918.tif 000023
【図１７】
2015508918.tif 000024
【図１８】
2015508918.tif 000025
【図１９】
2015508918.tif 000026
【図２０】
2015508918.tif 000027
【図２１】
2015508918.tif 000028
【図２２】
2015508918.tif 000029
【図２３】
2015508918.tif 000030
【国際調査報告】
2015508918.tif 000031
2015508918.tif 000032