アソシエーション分析において、アイテム数が増えるにつれて、アソシエーションルールの総数は増えることは

アソシエーション分析において、アイテム数が増えるにつれて、アソシエーションルールの総数は増えることはわかりますが、指数関数的に増加していく理由はなんですか？

No.2 ベストアンサー 回答者： kamiyasiro 回答日時： 2020/06/17 16:30

企業で統計を推進する立場の者です。

ｎ個の商品があったときに出てくるルール数はｎ個のアイテムから２個取る「組み合わせの数」なので、総ルール数はｎの階乗の式で表されますが、それが指数関数的になる理由は、＃１さんの説明のとおりです。
厳密には等比数列ではないので何か（公比）のｎ乗という指数関数ではなくそれ以上の増え方になります。「組み合わせ爆発」という現象です。

では、何万点（それ以上）もの商品があるAmazonなどでは、どういうアルゴリズムを使っているんだ？となりますが、これはリテールデータ分析（購買行動の分析）の中の推薦システム（お薦め商品とかを提示するシステム：とんでもない計算量を瞬時にこなしている）におけるデータと探索のトレードオフ問題であり、離散最適化問題（不要な線は切る）という領域になります。

ご質問の趣旨から逸脱しましたが、次にぶつかる壁だと思いましたので、ついつい書いてしまいました。すみません。

No.1 回答者： yhr2 回答日時： 2020/06/17 15:27

正確かどうかはわかりませんが、定性的な説明です。

今すでに n 個のアイテムがあったとしましょう。
そこに新しいアイテムを１個追加します。
そうすれば、既存の各々のアイテムが持っていた「アソシエーション」I 個に対して、新しく追加したアイテムからそれにつながる「アソシエーション」は n 倍つまり nI 個になります。

つまり、アイテムに対するアソシエーション数 I(n) の増え方は、そのときのアソシエーション数にアイテム数 n をかけたものになります。
式で書けば、
　dI/dn = nI　　　　①

これは数列の漸化式でも書くことができると思います。
　I(n) = nI(n - 1)　( I(1) = 1, ｎ≧2 ）　　　②
n がどんどん大きくなるので「等比」数列ではありません。

①から I を求めれば
　∫(1/I)dI = ∫ndn
→　log|I| = (1/2)n^2 + C1　（C1：積分定数）

よって、I > 0 なので
　I(n) = e^[(1/2)n^2 + C1] = C･e^[(1/2)n^2]　（C = e^C1）
ということで指数関数になりますね。


「微積分」が分からなくとも、②の数列の漸化式で、仮に「等比」数列として（公比を最低の 2 に固定して増加させない）
　I(n) = 2I(n - 1)
としても
　I(n) = 2^n･I(1)
で「2^n のネズミ算式に増えていく」ことがわかりますよね。
②では公比が「2 から順次大きくなっていく」のですから、増え方はそれよりも大きいことになります。