sql - SQLで同様のセットを選択する方法

Question

私は次のテーブルを持っています：

Order
----
ID (pk)

OrderItem
----
OrderID (fk -> Order.ID)
ItemID (fk -> Item.ID)
Quantity

Item
----
ID (pk)

Orders特定の85％以上類似しているものをすべて選択できるクエリを作成するにはどうすればよいOrderですか？

Jaccard Index統計を使用して、2つの類似度を計算することを検討しましたOrders。（各セットの積を各セットのOrderItems和集合で割ったものをとることによってOrderItems）

ただし、2つの可能な組み合わせごとに計算されたジャッカード係数を保存せずにこれを行う方法を考えることはできませんOrders。 別の方法はありますか？

Quantityまた、一致したそれぞれの違いOrderItemを考慮に入れる方法はありますか？

追加情報：

---

合計Orders：〜79k
合計OrderItems：〜1.76m
平均 OrderItemsあたりOrder：21.5
合計Items：〜13k

ノート

---

85％の類似性の数値は、顧客が実際に何を必要としているかを推測するためのものであり、将来変更される可能性があります。任意の類似性に対して機能するソリューションが望ましいでしょう。

Answer 1

指定します

特定の注文に85％以上類似しているすべての注文を選択できるクエリを作成するにはどうすればよいですか？

これは、「互いに少なくとも85％類似している注文のすべてのペア」と比較して重要な単純化です。

いくつかのTDQD（テスト駆動クエリ設計）といくつかの分析を使用して支援します。

予選

リモートで類似させるには、2つの注文に少なくとも1つの共通のアイテムが必要です。このクエリを使用して、指定した注文と共通するアイテムが少なくとも1つある注文を特定できます。

SELECT DISTINCT I1.OrderID AS ID
  FROM OrderItem AS I1
  JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID AND I2.OrderID = <specified order ID>
 WHERE I1.OrderID != <specified order ID>

これにより、他の注文のリストがかなり整理されますが、指定された注文に最も人気のあるアイテムの1つが含まれている場合は、他の多くの注文にも含まれている可能性があります。

DISTINCTの代わりに、次を使用できます。

SELECT I1.OrderID AS ID, COUNT(*) AS Num_Common
  FROM OrderItem AS I1
  JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID AND I2.OrderID = <specified order ID>
 WHERE I1.OrderID != <specified order ID>
 GROUP BY I1.OrderID

これにより、指定された順序と共通する順序のアイテムの数がわかります。また、各注文のアイテム数も必要です。

SELECT OrderID AS ID, COUNT(*) AS Num_Total
  FROM OrderItem
 GROUP BY OrderID;

同一の注文

100％の類似性の場合、2つの注文には、それぞれがアイテムを持っているのと同じ数の共通のアイテムがあります。ただし、これではおそらく多くの注文のペアは見つかりません。指定された注文とまったく同じアイテムの注文を簡単に見つけることができます。

SELECT L1.ID
  FROM (SELECT OrderID AS ID, COUNT(*) AS Num_Total
          FROM OrderItem
         GROUP BY OrderID
       ) AS L1
  JOIN (SELECT I1.OrderID AS ID, COUNT(*) AS Num_Common
          FROM OrderItem AS I1
          JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID AND I2.OrderID = <specified order ID>
         WHERE I1.OrderID != <specified order ID>
         GROUP BY I1.OrderID
       ) AS L2 ON L1.ID = L2.ID AND L1.Num_Total = L2.Num_Common;

編集：これは十分に厳格ではないことが判明しました。注文が同一であるためには、指定された注文のアイテムの数も共通の数と同じである必要があります。

SELECT L1.ID, L1.Num_Total, L2.ID, L2.Num_Common, L3.ID, L3.Num_Total
  FROM (SELECT OrderID AS ID, COUNT(*) AS Num_Total
          FROM OrderItem
         GROUP BY OrderID
       ) AS L1
  JOIN (SELECT I1.OrderID AS ID, COUNT(*) AS Num_Common
          FROM OrderItem AS I1
          JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID AND I2.OrderID = <specified order ID>
         WHERE I1.OrderID != <specified order ID>
         GROUP BY I1.OrderID
       ) AS L2 ON L1.ID = L2.ID AND L1.Num_Total = L2.Num_Common
  JOIN (SELECT OrderID AS ID, COUNT(*) AS Num_Total
          FROM OrderItem
         WHERE OrderID = <specified order ID>
         GROUP BY OrderID
       ) AS L3 ON L2.Num_Common = L3.Num_Total;

同様の順序—式の分析

ウィキペディアで定義されているJaccardの類似性 を、|A|を使用して2つのオーダーAとBに適用します。順序Aのアイテム数のカウントであるため、Jaccard類似度J（A、B）=|A∩B| ÷|A∪B| 、ここで|A∩B| は2つの注文に共通するアイテムの数であり、|A∪B| 注文されたさまざまなアイテムの総数です。

85％のJaccard類似性基準を満たすには、いずれかの注文のアイテム数がしきい値より少ない場合、注文は同一である必要があります。たとえば、注文AとBの両方に5つのアイテムがあるが、2つの間に1つのアイテムが異なる場合、共通の4つのアイテム（|A∩B|）と合計6つのアイテム（|A∪B|）が得られます。したがって、Jaccard類似度J（A、B）はわずか66⅔％です。

2つの注文のそれぞれにN個のアイテムがあり、1個のアイテムが異なる場合の85％の類似性の場合、（N-1）÷（N + 1） ≥0.85、つまりN> 12（正確には121/3）。分数F=J（A、B）の場合、1つの項目が異なるとは（N-1）÷（N + 1）≥Fを意味し、 N≥（1 + F）÷（1-F）を与えるNに対して解くことができます。類似性の要件が高くなるにつれて、Nの値がますます大きくなる場合、次数は同一でなければなりません。

さらに一般化して、NアイテムとMアイテムで異なるサイズの注文があると仮定しましょう（一般性を失うことなく、N <M）。|A∩B|の最大値 はNになり、|A∪B|の最小値になります。はMです（小さい順序のすべてのアイテムが大きい順序で表示されることを意味します）。M = N + ∆であり、大きい順序では存在しない∂アイテムが小さい順序で存在することを定義しましょう。したがって、小さい順序ではなく、大きい順序で存在する∆+∂アイテムがあります。

定義上、|A∩B| = N-∂、および|A∪B| =（N-∂）+∂+（N + ∆-（N-∂））、ここで、追加された3つの用語は、（1）2つの注文に共通するアイテムの数、（2）小さい方の注文、および（3）大きい方の注文のみのアイテムの数。これにより、次のように簡略化されます。|A∪B| = N + ∆+∂。

---

キー方程式

類似度Fの場合、J（A、B）≥Fである次数のペアに関心があるため、次のようになります。

（N-∂）÷（N + ∆ +∂）≥F

F≤（N-∂）÷（N + ∆ +∂）

---

スプレッドシートを使用して、これらの間の関係をグラフ化できます。小さい順序（x軸）の特定の数のアイテムについて、特定の類似性について、Fの類似性を与える∂の最大値をグラフ化できます。式は次のとおりです。

∂=（N（1-F）-F∆）÷（1 + F）

これは、定数FのNと∆の線形方程式です。Fの値が異なると非線形になります。明らかに、∂は非負の整数である必要があります。

F = 0.85の場合、同じサイズ（∆ = 0）の注文の場合、1≤N<13の場合、∂= 0; 13≤N<25の場合、∂≤1; 25≤N<37の場合、∂≤2、37≤N<50の場合、∂≤3。

1（∆ = 1）だけ異なる注文の場合、1≤N<18の場合、∂= 0; 18≤N<31の場合、∂≤1; 31≤N<43の場合、∂≤2; など。∆ = 6の場合、注文が∂= 1と85％類似する前に、N=47が必要です。つまり、小口注文には47個のアイテムがあり、そのうち46個は大口注文の53個のアイテムと共通しています。

同様の順序—分析の適用

ここまでは順調ですね。その理論を、指定された注文に類似した注文を選択するためにどのように適用できますか？

まず、指定された注文が同様の注文と同じサイズか、それよりも大きいか、または小さい可能性があることを確認します。これは物事を少し複雑にします。

上記の式のパラメーターは次のとおりです。

• N –小さい順序のアイテムの数
• ∆ —上位のアイテム数とNの差
• F —修正済み
• ∂—小さい順序のアイテムの数が大きい順序で一致していません

上部で開発されたクエリのマイナーバリエーションを使用して利用可能な値：

• NC —共通のアイテムの数
• NA —指定された順序のアイテムの数
• NB —比較された順序でのアイテムの数

対応するクエリ：

SELECT OrderID AS ID, COUNT(*) AS NA
  FROM OrderItem
 WHERE OrderID = <specified order ID>
 GROUP BY OrderID;

SELECT OrderID AS ID, COUNT(*) AS NB
  FROM OrderItem
 WHERE OrderID != <specified order ID>
 GROUP BY OrderID;

SELECT I1.OrderID AS ID, COUNT(*) AS NC
  FROM OrderItem AS I1
  JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID AND I2.OrderID = <specified order ID>
 WHERE I1.OrderID != <specified order ID>
 GROUP BY I1.OrderID

便宜上、値NおよびN + ∆（したがって∆）を使用できるようにしたいので、UNIONを使用して、次のように適切に配置できます。

• NS = N —小さい順序のアイテムの数
• NL = N + ∆ —より大きな順序のアイテムの数

UNIONクエリの2番目のバージョンでは、次のようになります。

• NC = N-∂—共通のアイテムの数

どちらのクエリも2つの注文ID番号を保持しているため、後で残りの注文情報を追跡できます。

SELECT v1.ID AS OrderID_1, v1.NA AS NS, v2.ID AS OrderID_2, v2.NB AS NL
  FROM (SELECT OrderID AS ID, COUNT(*) AS NA
          FROM OrderItem
         WHERE OrderID = <specified order ID>
         GROUP BY OrderID
       ) AS v1
  JOIN (SELECT OrderID AS ID, COUNT(*) AS NB
          FROM OrderItem
         WHERE OrderID != <specified order ID>
         GROUP BY OrderID
       ) AS v2
    ON v1.NA <= v2.NB
UNION
SELECT v2.ID AS OrderID_1, v2.NB AS NS, v1.ID AS OrderID_2, v1.NA AS NL
  FROM (SELECT OrderID AS ID, COUNT(*) AS NA
          FROM OrderItem
         WHERE OrderID = <specified order ID>
         GROUP BY OrderID
       ) AS v1
  JOIN (SELECT OrderID AS ID, COUNT(*) AS NB
          FROM OrderItem
         WHERE OrderID != <specified order ID>
         GROUP BY OrderID
       ) AS v2
    ON v1.NA > v2.NB

これにより、列OrderID_1、NS、OrderID_2、NLを持つテーブル式が得られます。ここで、NSは小さい順序のアイテムの数であり、NLは大きい順序のアイテムの数です。v1テーブル式とv2テーブル式によって生成される注文番号に重複がないため、OrderID値が同じである「再帰的」エントリについて心配する必要はありません。これにNCを追加することは、UNIONクエリでも最も簡単に処理できます。

SELECT v1.ID AS OrderID_1, v1.NA AS NS, v2.ID AS OrderID_2, v2.NB AS NL, v3.NC AS NC
  FROM (SELECT OrderID AS ID, COUNT(*) AS NA
          FROM OrderItem
         WHERE OrderID = <specified order ID>
         GROUP BY OrderID
       ) AS v1
  JOIN (SELECT OrderID AS ID, COUNT(*) AS NB
          FROM OrderItem
         WHERE OrderID != <specified order ID>
         GROUP BY OrderID
       ) AS v2
    ON v1.NA <= v2.NB
  JOIN (SELECT I1.OrderID AS ID, COUNT(*) AS NC
          FROM OrderItem AS I1
          JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID AND I2.OrderID = <specified order ID>
         WHERE I1.OrderID != <specified order ID>
         GROUP BY I1.OrderID
       ) AS v3
    ON v3.ID = v2.ID
UNION
SELECT v2.ID AS OrderID_1, v2.NB AS NS, v1.ID AS OrderID_2, v1.NA AS NL, v3.NC AS NC
  FROM (SELECT OrderID AS ID, COUNT(*) AS NA
          FROM OrderItem
         WHERE OrderID = <specified order ID>
         GROUP BY OrderID
       ) AS v1
  JOIN (SELECT OrderID AS ID, COUNT(*) AS NB
          FROM OrderItem
         WHERE OrderID != <specified order ID>
         GROUP BY OrderID
       ) AS v2
    ON v1.NA > v2.NB
  JOIN (SELECT I1.OrderID AS ID, COUNT(*) AS NC
          FROM OrderItem AS I1
          JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID AND I2.OrderID = <specified order ID>
         WHERE I1.OrderID != <specified order ID>
         GROUP BY I1.OrderID
       ) AS v3
    ON v3.ID = v1.ID

これにより、OrderID_1、NS、OrderID_2、NL、NCの列を持つテーブル式が得られます。ここで、NSは小さい順序のアイテムの数、NLは大きい順序のアイテムの数、NCは次のアイテムの数です。一般。

NS、NL、NCを考えると、次の条件を満たす注文を探しています。

（N-∂）÷（N + ∆ +∂）≥F。

• N –小さい順序のアイテムの数
• ∆ —上位のアイテム数とNの差
• F —修正済み

• ∂—小さい順序のアイテムの数が大きい順序で一致していません

• NS = N —小さい順序のアイテムの数

• NL = N + ∆ —より大きな順序のアイテムの数
• NC = N-∂—共通のアイテムの数

したがって、条件は次のようにする必要があります。

NC / (NL + (NS - NC)) ≥ F

LHSの項は、整数式ではなく、浮動小数点数として評価する必要があります。これを上記のUNIONクエリに適用すると、次のようになります。

SELECT OrderID_1, NS, OrderID_2, NL, NC,
        CAST(NC AS NUMERIC) / CAST(NL + NS - NC AS NUMERIC) AS Similarity
  FROM (SELECT v1.ID AS OrderID_1, v1.NA AS NS, v2.ID AS OrderID_2, v2.NB AS NL, v3.NC AS NC
          FROM (SELECT OrderID AS ID, COUNT(*) AS NA
                  FROM OrderItem
                 WHERE OrderID = <specified order ID>
                 GROUP BY OrderID
               ) AS v1
          JOIN (SELECT OrderID AS ID, COUNT(*) AS NB
                  FROM OrderItem
                 WHERE OrderID != <specified order ID>
                 GROUP BY OrderID
               ) AS v2
            ON v1.NA <= v2.NB
          JOIN (SELECT I1.OrderID AS ID, COUNT(*) AS NC
                  FROM OrderItem AS I1
                  JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID AND I2.OrderID = <specified order ID>
                 WHERE I1.OrderID != <specified order ID>
                 GROUP BY I1.OrderID
               ) AS v3
            ON v3.ID = v2.ID
        UNION
        SELECT v2.ID AS OrderID_1, v2.NB AS NS, v1.ID AS OrderID_2, v1.NA AS NL, v3.NC AS NC
          FROM (SELECT OrderID AS ID, COUNT(*) AS NA
                  FROM OrderItem
                 WHERE OrderID = <specified order ID>
                 GROUP BY OrderID
               ) AS v1
          JOIN (SELECT OrderID AS ID, COUNT(*) AS NB
                  FROM OrderItem
                 WHERE OrderID != <specified order ID>
                 GROUP BY OrderID
               ) AS v2
            ON v1.NA > v2.NB
          JOIN (SELECT I1.OrderID AS ID, COUNT(*) AS NC
                  FROM OrderItem AS I1
                  JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID AND I2.OrderID = <specified order ID>
                 WHERE I1.OrderID != <specified order ID>
                 GROUP BY I1.OrderID
               ) AS v3
            ON v3.ID = v1.ID
       ) AS u
 WHERE CAST(NC AS NUMERIC) / CAST(NL + NS - NC AS NUMERIC) >= 0.85 -- F

このクエリはOrderItemテーブルのみを使用していることに気付くかもしれません。OrderテーブルとItemテーブルは必要ありません。

---

警告：部分的にテストされたSQL（警告レクター）。上記のSQLは、ごくわずかなデータセットに対してもっともらしい答えを生成しているようです。類似性の要件（0.25、次に0.55）を調整し、妥当な値と適切な選択性を取得しました。しかし、私のテストデータは最大の順序で8項目しかなく、確かに記述されたデータの全範囲をカバーしていませんでした。私が最も頻繁に使用するDBMSはCTEをサポートしていないため、以下のSQLはテストされていません。ただし、大きな間違いをしない限り、バージョン1のCTEコード（指定された注文IDが何度も繰り返される）はクリーンであるはずだとある程度確信しています。バージョン2でも大丈夫だと思いますが...テストされていません。

おそらくOLAP関数を使用して、クエリを表現するよりコンパクトな方法があるかもしれません。

これをテストする場合は、注文アイテムの代表的なセットをいくつか含むテーブルを作成し、返された類似度が適切であることを確認します。示されているようにクエリを多かれ少なかれ処理し、徐々に複雑なクエリを構築します。式の1つに欠陥があることが示された場合は、欠陥が修正されるまで、そのクエリで適切な調整を行います。

明らかに、パフォーマンスが問題になります。最も内側のクエリはそれほど複雑ではありませんが、それほど些細なことではありません。ただし、測定により、それが劇的な問題なのか、単なる迷惑なのかがわかります。クエリプランを調べると役立つ場合があります。OrderItem.OrderIDにインデックスがある可能性が非常に高いようです。そのようなインデックスがない場合、クエリはうまく機能しない可能性があります。外部キー列であるため、これが問題になる可能性はほとんどありません。

'WITH句'（共通テーブル式）を使用すると、いくつかの利点が得られる場合があります。それらは、UNIONサブクエリの2つの半分に暗黙的に含まれる繰り返しを明示的にします。

---

一般的なテーブル式の使用

共通のテーブル式を使用すると、式が同じである場合にオプティマイザーに明確になり、パフォーマンスの向上に役立つ場合があります。彼らはまた、人間があなたの質問を読むのを助けます。上記のクエリは、CTEの使用を要求します。

バージョン1：指定された注文番号を繰り返す

WITH SO AS (SELECT OrderID AS ID, COUNT(*) AS NA       -- Specified Order (SO)
              FROM OrderItem
             WHERE OrderID = <specified order ID>
             GROUP BY OrderID
           ),
     OO AS (SELECT OrderID AS ID, COUNT(*) AS NB       -- Other orders (OO)
              FROM OrderItem
             WHERE OrderID != <specified order ID>
             GROUP BY OrderID
           ),
     CI AS (SELECT I1.OrderID AS ID, COUNT(*) AS NC    -- Common Items (CI)
              FROM OrderItem AS I1
              JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID AND I2.OrderID = <specified order ID>
             WHERE I1.OrderID != <specified order ID>
             GROUP BY I1.OrderID
           )
SELECT OrderID_1, NS, OrderID_2, NL, NC,
        CAST(NC AS NUMERIC) / CAST(NL + NS - NC AS NUMERIC) AS Similarity
  FROM (SELECT v1.ID AS OrderID_1, v1.NA AS NS, v2.ID AS OrderID_2, v2.NB AS NL, v3.NC AS NC
          FROM SO AS v1
          JOIN OO AS v2 ON v1.NA <= v2.NB
          JOIN CI AS v3 ON v3.ID  = v2.ID
        UNION
        SELECT v2.ID AS OrderID_1, v2.NB AS NS, v1.ID AS OrderID_2, v1.NA AS NL, v3.NC AS NC
          FROM SO AS v1
          JOIN OO AS v2 ON v1.NA  > v2.NB
          JOIN CI AS v3 ON v3.ID  = v1.ID
       ) AS u
 WHERE CAST(NC AS NUMERIC) / CAST(NL + NS - NC AS NUMERIC) >= 0.85 -- F

バージョン2：指定された注文番号の繰り返しを避ける

WITH SO AS (SELECT OrderID AS ID, COUNT(*) AS NA       -- Specified Order (SO)
              FROM OrderItem
             WHERE OrderID = <specified order ID>
             GROUP BY OrderID
           ),
     OO AS (SELECT OI.OrderID AS ID, COUNT(*) AS NB    -- Other orders (OO)
              FROM OrderItem AS OI
              JOIN SO ON OI.OrderID != SO.ID
             GROUP BY OI.OrderID
           ),
     CI AS (SELECT I1.OrderID AS ID, COUNT(*) AS NC    -- Common Items (CI)
              FROM OrderItem AS I1
              JOIN SO AS S1 ON I1.OrderID != S1.ID
              JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID
              JOIN SO AS S2 ON I2.OrderID  = S2.ID
             GROUP BY I1.OrderID
           )
SELECT OrderID_1, NS, OrderID_2, NL, NC,
        CAST(NC AS NUMERIC) / CAST(NL + NS - NC AS NUMERIC) AS Similarity
  FROM (SELECT v1.ID AS OrderID_1, v1.NA AS NS, v2.ID AS OrderID_2, v2.NB AS NL, v3.NC AS NC
          FROM SO AS v1
          JOIN OO AS v2 ON v1.NA <= v2.NB
          JOIN CI AS v3 ON v3.ID  = v2.ID
        UNION
        SELECT v2.ID AS OrderID_1, v2.NB AS NS, v1.ID AS OrderID_2, v1.NA AS NL, v3.NC AS NC
          FROM SO AS v1
          JOIN OO AS v2 ON v1.NA  > v2.NB
          JOIN CI AS v3 ON v3.ID  = v1.ID
       ) AS u
 WHERE CAST(NC AS NUMERIC) / CAST(NL + NS - NC AS NUMERIC) >= 0.85 -- F

これらはどちらも簡単に読むことはできません。どちらも、CTEが完全に書き出された大きなSELECTよりも簡単です。

---

最小限のテストデータ

これは、適切なテストには不十分です。それは少しの自信を与えます（そしてそれは「同一の順序」クエリの問題を明らかにしました。

CREATE TABLE Order (ID SERIAL NOT NULL PRIMARY KEY);
CREATE TABLE Item  (ID SERIAL NOT NULL PRIMARY KEY);
CREATE TABLE OrderItem
(
    OrderID INTEGER NOT NULL REFERENCES Order,
    ItemID INTEGER NOT NULL REFERENCES Item,
    Quantity DECIMAL(8,2) NOT NULL
);

INSERT INTO Order VALUES(1);
INSERT INTO Order VALUES(2);
INSERT INTO Order VALUES(3);
INSERT INTO Order VALUES(4);
INSERT INTO Order VALUES(5);
INSERT INTO Order VALUES(6);
INSERT INTO Order VALUES(7);

INSERT INTO Item VALUES(111);
INSERT INTO Item VALUES(222);
INSERT INTO Item VALUES(333);
INSERT INTO Item VALUES(444);
INSERT INTO Item VALUES(555);
INSERT INTO Item VALUES(666);
INSERT INTO Item VALUES(777);
INSERT INTO Item VALUES(888);
INSERT INTO Item VALUES(999);

INSERT INTO OrderItem VALUES(1, 111, 1);
INSERT INTO OrderItem VALUES(1, 222, 1);
INSERT INTO OrderItem VALUES(1, 333, 1);
INSERT INTO OrderItem VALUES(1, 555, 1);

INSERT INTO OrderItem VALUES(2, 111, 1);
INSERT INTO OrderItem VALUES(2, 222, 1);
INSERT INTO OrderItem VALUES(2, 333, 1);
INSERT INTO OrderItem VALUES(2, 555, 1);

INSERT INTO OrderItem VALUES(3, 111, 1);
INSERT INTO OrderItem VALUES(3, 222, 1);
INSERT INTO OrderItem VALUES(3, 333, 1);
INSERT INTO OrderItem VALUES(3, 444, 1);
INSERT INTO OrderItem VALUES(3, 555, 1);
INSERT INTO OrderItem VALUES(3, 666, 1);

INSERT INTO OrderItem VALUES(4, 111, 1);
INSERT INTO OrderItem VALUES(4, 222, 1);
INSERT INTO OrderItem VALUES(4, 333, 1);
INSERT INTO OrderItem VALUES(4, 444, 1);
INSERT INTO OrderItem VALUES(4, 555, 1);
INSERT INTO OrderItem VALUES(4, 777, 1);

INSERT INTO OrderItem VALUES(5, 111, 1);
INSERT INTO OrderItem VALUES(5, 222, 1);
INSERT INTO OrderItem VALUES(5, 333, 1);
INSERT INTO OrderItem VALUES(5, 444, 1);
INSERT INTO OrderItem VALUES(5, 555, 1);
INSERT INTO OrderItem VALUES(5, 777, 1);
INSERT INTO OrderItem VALUES(5, 999, 1);

INSERT INTO OrderItem VALUES(6, 111, 1);
INSERT INTO OrderItem VALUES(6, 222, 1);
INSERT INTO OrderItem VALUES(6, 333, 1);
INSERT INTO OrderItem VALUES(6, 444, 1);
INSERT INTO OrderItem VALUES(6, 555, 1);
INSERT INTO OrderItem VALUES(6, 777, 1);
INSERT INTO OrderItem VALUES(6, 888, 1);
INSERT INTO OrderItem VALUES(6, 999, 1);

INSERT INTO OrderItem VALUES(7, 111, 1);
INSERT INTO OrderItem VALUES(7, 222, 1);
INSERT INTO OrderItem VALUES(7, 333, 1);
INSERT INTO OrderItem VALUES(7, 444, 1);
INSERT INTO OrderItem VALUES(7, 555, 1);
INSERT INTO OrderItem VALUES(7, 777, 1);
INSERT INTO OrderItem VALUES(7, 888, 1);
INSERT INTO OrderItem VALUES(7, 999, 1);
INSERT INTO OrderItem VALUES(7, 666, 1);

Answer 2

これに対する簡単な答えは本当にありません。確かにJaccardインデックスを保存することはできますが（実際には、基準を満たすものを保存し、残りを破棄します）、実際の問題はそれを計算することです（新しい注文のたびに既存の注文をすべてスキャンする必要があります）新しいインデックスを計算するためにシステムに入力されました）。

維持している注文の量によっては、かなり高額になる可能性があります。たぶん、あなたはそれを昨年の注文か何かと比較するだけです。

その場でそれをしているなら、それはもっと面白くなりますが、それでも高価です。

同じ商品アイテムを持つすべての注文のリストを簡単に取得できます。アイテムごとに1つのリスト。実際、これは必ずしも大量のデータではありません（1つの人気のあるアイテムの注文が多い場合は、長いリストになる可能性があります）。個々のクエリも特に異常ではありません（これもデータによって異なります）。膨大な量のデータがある場合、クエリは簡単にマッピング/縮小でき、シャーディングされたデータストアでも機能します。ビットマップインデックス（DBがこれをサポートしている場合）は、このようなリストを非常に迅速に取得するのに特に適しています。

次に、すべてのリストで注文番号が発生する回数を数えるだけで、しきい値を満たしていないものを削除できます。これは単純なマージ操作です。

ただし、実際には情報を保存できないため、情報が必要になるたびにこの計算を行う必要があります。

つまり、実際には、情報が必要なもの、必要な頻度、アイテムの<->注文の配布、待機できる時間などに要約されます。

補遺：

もう少し考えてみると、これは単純なクエリですが、実行に時間がかかる場合があります。最近のハードウェアではそれほど多くない可能性がありますが、実際にはそれほど多くのデータはありません。注文を表示している単一の画面の場合、気付かないでしょう。すべての注文にわたってレポートを実行している場合は、間違いなくそれに気付くでしょう-そして別のアプローチが必要になります。

20の広告申込情報がある注文を考えてみましょう。

そして、85％の一致が必要です。これは、17個以上の共通アイテムがある注文を意味します。

興味のある注文を表示するクエリは次のとおりです。

SELECT orderId, count(*) FROM OrderItem
WHERE itemId in ('list', 'of', 'items', 'in', 'order', 123, 456, 789)
GROUP BY orderId
HAVING count(*) >= 17

したがって、これにより、注文と同じアイテムを持つすべてのラインアイテムのコレクションが得られます。次に、それらをorderIdで合計すると、しきい値（この場合は17）以上のオーダーが候補オーダーになります。

さて、あなたはあなたがあなたのカタログにいくつのアイテムを持っているかを言いません。1000個のアイテムが完全に分散されている場合、このクエリは1600行のデータを処理します。これは大したことではありません。適切なインデックスがあれば、これは非常に迅速に進むはずです。ただし、「非常に人気のある」アイテムがある場合は、より多くのデータ行を処理することになります。

しかし、繰り返しになりますが、それほど多くのデータはありません。このクエリのほとんどは、適切なデータベースのインデックス内で実行でき、実際のテーブルにヒットすることもありません。したがって、前述したように、このクエリがインタラクティブシステムに与える影響に気付かない可能性があります。

だから、それを試してみて、それがあなたのためにどうなるかを見てください。

Answer 3

このアプローチでは、拡張ジャッカード係数または谷本類似性を使用した数量が考慮されます。量の大きさの一般的なItemIDのベクトルを使用して、すべての注文の類似性を計算します。テーブルスキャンにはコストがかかりますが、考えられるすべての類似点をN^2で計算する必要はありません。

SELECT
    OrderID,
    SUM(v1.Quantity * v2.Quantity) /
    (SUM(v1.Quantity * v1.Quantity) +
     SUM(v2.Quantity * v2.Quantity) -
     SUM(v1.Quantity * v2.Quantity) ) AS coef
FROM
    OrderItem v1 FULL OUTER JOIN OrderItem v2
    ON v1.ItemID = v2.ItemID
    AND v2.OrderID = ?
GROUP BY OrderID
HAVING coef > 0.85;

拡張ジャッカード係数の式：

Answer 4

これは、拡張コメントほどの答えではありません。意味がないと思われる場合は削除します。

「類似した」アイテムをその場で見つけようとしている場合、問題は、確認する注文がたくさん（〜79k）あることです。したがって、これを実行しようとしている場合は、高価なセットの比較を行う前に、検討している注文の数を減らす方法が必要です。

@Willが指摘する1つの方法は、注文のアイテム数を考慮することです。したがって、ターゲット注文に20個のアイテムがある場合は、17〜23個のOrderItem（または「85％の類似性」の正確な計算に応じてそのようなもの）の注文のみを考慮する必要があります。これらの数値は、Orderが作成または変更されるたびにトリガーを介して計算され、Orderテーブルの列に格納されると想定しています。

ただし、セットのサイズを保存できる場合は、他の数値も保存できます。たとえば、各Orderに奇数のOrderItem主キー値の数を格納できます。次に、検討している注文は、その数の奇数の注文番号に適切に近い必要があります（「適切に近い」と記入するために、ある時点で計算を行う場合があります）。

また、値を「奇数」の数値で分割することをサイズ1のストライプに分割することを考えると、モジュラス演算子を使用して、さまざまなサイズのストライプで簡単に分割できます。例えば。ItemID％4<2はサイズ2のストライプになります。次に、注文ごとに、それらのストライプ内のOrderItem主キーの数を記録できます。候補の注文は、値を分割する各方法で、ターゲットの注文に適切に近い必要があります。

したがって、最終的には、Ordersテーブルに格納され、インデックスが付けられている一連のメトリック全体を調べて、Ordersテーブルの候補のサイズを制限しようとする大きなサブクエリになります。

Answer 5

Order @OrderIdとの類似性によって注文を一覧表示し、速度を上げるためにこのようなものを試してみます。結合されたINTSは共通部分であると想定され、類似度の値はJaccardインデックスを計算するための私の試みです。

ここでは数量フィールドをまったく使用していませんが、数量を含む類似性を定量化する方法を見つければ、クエリをあまり遅くすることなく実行できると思います。以下では、類似性として2つの順序で同一のアイテムを数えています。数量で参加することも、数量を含む一致が2倍になるメジャーを使用することもできます。それが合理的かどうかはわかりません。

SELECT 
    OI.OrderId,
    1.0*COUNT(INTS.ItemId) / 
    (COUNT(*)
    + (SELECT COUNT(*) FROM OrderItem WHERE OrderID = @OrderId) 
    - COUNT(INTS.ItemId)) AS Similarity
FROM    
    OrderItem OI        
JOIN
    OrderItem INTS ON INTS.ItemID = OI.ItemID AND INTS.OrderId=@OrderId
GROUP BY 
    OI.OrderId
HAVING  
    1.0*COUNT(INTS.ItemId) / 
    (COUNT(*)
    + (SELECT COUNT(*) FROM OrderItem WHERE OrderID = @OrderId) 
    - COUNT(INTS.ItemId)) > 0.85
ORDER BY
    Similarity DESC

また、OrderId/ItemIdの組み合わせがOrderItemで一意であることを前提としています。これは当てはまらない可能性があり、ビューを使用して回避できる可能性があることを認識しています。

より良い方法があると確信していますが、違いを定量化する1つの方法は、ノミネーターCOUNT（INTS.ItemId）を次のようなものに置き換えることです（すべての数量が正であると仮定）。異なる。

    1/(ABS(LOG(OI.quantity)-LOG(INTS.quantity))+1)  

追加：JRideoutによって提案された谷本類似性を使用したこのより読みやすいソリューション

DECLARE 
    @ItemCount INT,
    @OrderId int 
SELECT     
    @OrderId  = 1
SELECT     
    @ItemCount = COUNT(*)
FROM 
    OrderItem
WHERE 
    OrderID = @OrderId 


SELECT 
    OI.OrderId,
    SUM(1.0* OI.Quantity*INTS.Quantity/(OI.Quantity*OI.Quantity+INTS.Quantity*INTS.Quantity-OI.Quantity*INTS.Quantity )) /
    (COUNT(*) + @ItemCount - COUNT(INTS.ItemId)) AS Similarity
FROM    
    OrderItem OI        
LEFT JOIN
    OrderItem INTS ON INTS.ItemID = OI.ItemID AND INTS.OrderId=@OrderId
GROUP BY 
    OI.OrderId
HAVING      
    SUM(1.0* OI.Quantity*INTS.Quantity/(OI.Quantity*OI.Quantity+INTS.Quantity*INTS.Quantity-OI.Quantity*INTS.Quantity )) /
    (COUNT(*) + @ItemCount - COUNT(INTS.ItemId)) > 0.85
ORDER BY
    Similarity DESC

Answer 6

うーん、おかしい、私は現在似たようなことに取り組んでいます。サンプル注文（つまり、それらのアイテム）を他のすべての注文（それらのアイテム）と結合し、注文ごとの一致数をグループ化して、85％以上一致するすべての注文をリストしてみませんか？

-- let @SampleorderID be the ID of a sample

declare @totalOrders int, @ThresholdOrderCount int
select @totalOrders = count(*) from OrderItems where orderID=@SampleOrderID

set @ThresholdOrderCount = 85*@totalOrders/100 -- 85% of the item amount of the sample

-- Now match the contents of the sample order with the contents of all other orders
-- count the #matches and show only those orders with at least 85% identical items
Select AllOrder.OrderID, count(*)
from   OrderItems sample 
       join OrderItems AllOrder 
         on sample.ItemID = AllOrder.ItemID
where sample.OrderID = @SampleOrderID 
  and sample.OrderID<>AllOrder.OrderID
group by AllOrder.OrderID 
having count(*)>@ThresholdOrderCount

これは機能するはずです。ただし、サンプルよりも多くのアイテムを含む注文も返します。それで問題がなければ、上記のクエリも非常に高速です。

Answer 7

私が取るアプローチは、最初に、選択した注文の注文アイテムに85％類似しているすべての注文アイテムを見つけ、次に各注文のこれらの注文アイテムの数を数え、アイテムの数が85％類似しているかどうかを確認することです。次のクエリを使用して、選択した注文：

DECLARE @OrderId int = 2
SET @OrderId = 6

/*
Retrieve orderitems that match 85% with required @orderId
*/
;WITH SelectedOrderItemCount
AS
(
    SELECT COUNT(*) * 0.85 AS LowerBoundary, COUNT(*) * 1.15 AS UpperBoundary
    FROM OrderItem
    WHERE OrderId = @OrderId
)
SELECT OtherOrders.OrderId, COUNT(*) as NumberOfOrderItems
FROM OrderItem SpecificOrder
INNER JOIN OrderItem OtherOrders
    ON OtherOrders.ItemId = SpecificOrder.ItemId
WHERE SpecificOrder.OrderId = @OrderId AND
      OtherOrders.OrderId <> @OrderId AND
    OtherOrders.Quantity BETWEEN SpecificOrder.Quantity * 0.85 AND SpecificOrder.Quantity * 1.15
GROUP BY OtherOrders.OrderId
HAVING COUNT(*) BETWEEN (SELECT LowerBoundary FROM SelectedOrderItemCount) 
                    AND (SELECT UpperBoundary FROM SelectedOrderItemCount)

ここに完全なSQLFiddleデモ

Answer 8

これはデータマイニングの問題の一種です。したがって、SQLを使用する代わりに、85％のサポートでAprioriアルゴリズムを使用できます。このアルゴリズムの実装は、多くのツールで自由に利用できます。