データベース内に近似文字列照合を実装するための方法およびシステム
文字列候補とデータベース内に格納された複数の文字列レコードとの文字列照合を行うためのコンピュータベースの方法について説明する。本方法は、ａ）データベース内の参照文字列集合を識別するステップであって、前記参照文字列は異種文字列集合の最適化探索を使用して識別されるステップと、ｂ）前記参照文字列集合における参照文字列のうちの１つに関するｎグラム表現を生成するステップと、ｃ）前記文字列候補のｎグラム表現を生成するステップと、ｄ）これらのｎグラム表現間の類似性を決定するステップと、ｅ）前記識別された参照文字列集合における残りの参照文字列についてステップｂ）およびステップｄ）を反復するステップと、ｆ）前記文字列候補および前記識別される集合における参照文字列のｎグラム表現間の決定された前記類似性に基づいてデータベース内の文字列候補に指数を付けるステップと、を含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概して加盟店予測システムに関し、特に、銀行カードネットワーク内に含まれるデータベースレコードへの加入に関連してデータベース内に近似文字列照合を実装するための方法およびシステムに関する。
【背景技術】
【０００２】
歴史的にみると、消費者取引の支払いに「チャージ」カードを使用することはせいぜい地域的なものであって、クレジット発行銀行と多様な地域加盟店との間の関係性に基づくものであった。支払いカード産業は、発行銀行が協会（例えば、MasterCard）を形成し、そして第三者取引処理会社（例えば、「Merchant Acquirers」）を取り込むことにより、加盟店とカード発行者との銀行関係に関わらず、カード所有者がいずれの加盟店の施設においてもそのチャージカードを広範に使用できるように発展してきた。
【０００３】
例えば、本出願の図１は、カード支払い取引を有効化するための例示的な複数関係者による支払いカード産業システムを示している。図示されているように、加盟店と発行者とは、必ずしも１対１の関係を有している必要はない。さらに、今日のカード支払い産業においては、カード発行者が特定の加盟店、または加盟店グループと特別な、またはカスタマイズされた関係性を有する様々なシナリオが存在する。
【０００４】
２５００万件を超える加盟店が、支払いカードの形式を受け入れている。協会の１つは、何千件もの加盟店の名称および加盟店ロケーションの住所情報を本明細書ではデータウェアハウスと称するものに格納されている。加盟店ロケーションのレベルでは、このデータウェアハウスに何百万件ものエントリが存在する。ロケーションエントリのうちの多くは、取引データにおける名称および／または住所の情報の変動に起因して重複していることが知られている。例えば、同じ街路であっても住所が様々に表記される可能性があり、その全てが有効である（例えば、400 South Fourth Street、400 S.Fourth St.、400 South 4th Street、他）。名称もまた、時として幾つかの方式で表示される可能性があり、その全てが有効である。現在のデータベース技術では、類似するフィールド値を有する名称および住所等のエントリを識別する能力が極めて限定的である。従って、重複に近い加盟店の名称および加盟店ロケーションがデータウェアハウスに多く入力されている。
【０００５】
協会のある典型的な処理の一日において、データウェアハウス内に既に格納されている約５００万件のロケーションエントリに対して照合チェックを行う必要があるロケーション候補（例えば、新しい加盟店ロケーション）は約１５，０００件存在する。照合のためのチェックは、少なくとも２つの目的を果たす。その１つとして、類似の名称および／または住所を有するロケーションは、幾つかの実体ではなく１つの実体として識別され得る。さらに、名称または住所があまりに相違していれば、協会は、１つの実体が転居している、または１つの実体が営業を停止していて別の実体に取って代わられていると決定することができる。
【０００６】
この名称およびロケーションの照合問題は、第三者がデータウェアハウスを保持する協会に取引ファイルを、ひいてはデータウェアハウスの強化および／または認証に使用される加盟店の名称および住所（ロケーション）のリストを提供する幾つかの他のコンテキストにおいても生じる。別の第三者の例では、国内の大規模小売業者に関する全てのロケーションのリストが受信される場合もあれば、チェーン店の名称および住所のリストが受信される場合もある。データウェアハウスの保持を担っているチームは、受信されるリストを小売業者またはチェーンの既知のロケーションと照合するタスクを任される。
【０００７】
既存のロケーションと新しいロケーションとの照合をチェックする１つの方法は、文字列照合アルゴリズムを介するものである。従って、文字列照合に利用される可能性のあるソリューションは何れも、データベース（データウェアハウス）システムの枠組み内でスケーラブルであるはずである。近似文字列照合に対しては、第三者ソリューションが存在する。しかしながら、これらのソリューションには、典型的には、ソリューションが法外な費用がかかり、特有のドメインまたはツールであり、もしくはソリューションがデータベース（データウェアハウス）システムの外部に存在することを含むような１つまたはそれ以上の欠点を有している。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
従って、データベースシステム内でスケーラブルに加盟店レコードを照合するためにデータウェアハウスチームが名称および住所の近似照合を実行できるようにする技術を開発するという、これまでに未だ果たされていない目的が存在している。所望される結果は、例えば取引履歴データを利用して将来の金融カード取引を予測しかつデータから関連づけられるべきことが存在するかどうかを決定する他のダウンストリームアプリケーションをサポートすることのできる小型で正確なデータウェアハウスであろう。
【課題を解決するための手段】
【０００９】
ある態様においては、文字列候補とデータベース内に格納された複数の文字列レコードとの文字列照合を行うためのコンピュータベースの方法が提供される。本方法は、ａ）データベース内の参照文字列集合を識別するステップであって、前記参照文字列は異種文字列集合の最適化検索を使用して識別されるステップと、ｂ）前記参照文字列集合における参照文字列のうちの１つに関するｎグラム表現を生成するステップと、ｃ）前記文字列候補のｎグラム表現を生成するステップと、ｄ）これらのｎグラム表現間の類似性を決定するステップと、ｅ）前記識別された参照文字列集合における残りの参照文字列についてステップｂ）およびステップｄ）を反復するステップと、ｆ）前記文字列候補および前記識別された集合における参照文字列のｎグラム表現間の決定された前記類似性に基づいてデータベース内の文字列候補に指数を付けるステップと、を含む。
【００１０】
別の態様では、最適化探索を使用してデータベース内の異種参照文字列集合を識別し、文字列候補のｎグラム表現を生成し、前記集合内の異種参照文字列の各々についてｎグラム表現を生成し、前記文字列候補のｎグラム表現と前記異種参照文字列集合の各ｎグラム表現との間の類似性を決定し、かつ前記両ｎグラム表現において前記決定された類似性に基づいてデータベース内の文字列候補に指数をつけるようにプログラムされたコンピュータが提供される。
【００１１】
さらに別の態様では、文字列候補をデータベース内の参照文字列集合と近似照合させるための、コンピュータベースの方法が提供される。本方法は、文字列候補のｎグラム表現と参照文字列集合における各参照文字列のｎグラム表現とを個々に比較することと、前記文字列候補に関連づけられる２進指数値を生成することとを含み、前記２進指数値は文字列候補と参照文字列の各々との間の類似性を示す。
【図面の簡単な説明】
【００１２】
【図１】日常的なカード支払い取引を有効化するための例示的な複数関係者による支払いカード産業システムを示す略図である。
【図２】本発明の一実施形態によるシステムのサーバアーキテクチャの例示的な一実施形態を示す単純化したブロック図である。
【図３】本発明の一実施形態によるシステムのサーバアーキテクチャの例示的な一実施形態を示す拡大ブロック図である。
【図４】加盟店集合体予測システムのためのハイレベルコンポーネントを示すフローチャートである。
【図５】前記加盟店集合体予測システムに関連づけられるスコアリングエンジンのオペレーションを示すフローチャートである。
【図６】加盟店ロケーションを分類するアルゴリズムに入力されるデータを示すフローチャート２５０である。
【図７】加盟店ロケーションを分類するアルゴリズムを記述するフローチャートである。
【図８】加盟店の集合体および集合を分類システムにおける文書として示す線図である。
【図９】データベース内の参照文字列または主要コンポーネントの集合の決定を示すフローチャートである。
【図１０】文字列候補の類似性メトリックを決定するための参照文字列の集合の使用を示すフローチャートである。
【発明を実施するための形態】
【００１３】
本明細書に記述する実施形態は、データベース内で近似列（例えば、文字列）照合を検索し、一方ではデータベース全体で類似性メトリックを計算する必要のない効率的な方法に関する。例えばコンテンツが若干変わる受信されたロケーションデータの近似文字列照合では、ロケーションの一致を決定することができる。この効率性は、照合されているフィールドの文字列のスペースを網羅する参照文字列の集合に対する各文字列の相対位置（一致の度合い）を捕捉する２進指数を生成することによって達成される。金融取引カードシステムの運用に関連づけられる加盟店の名称およびロケーションのコンテキストで説明しているが、近似文字列照合技術は文字列照合ではなく加盟店の名称および住所情報の情報検索等のより一般的なタスクに適用可能である点に留意することが重要である。一例は、文書照合のための技術をコンピュータシステム内で利用することである。
【００１４】
本明細書に記述しているシステムおよびプロセスの技術的効果は、下記、即ち（ａ）データベースシステム内で加盟店レコードをスケーラブルに照合するために、名称および住所の近似照合を実行する技術、（ｂ）複数の参照文字列の各々に対する文字列候補の類似性メトリックの決定を行なうこと、（ｃ）照合されているフィールドに関してデータベース内の文字列のスペースを網羅する参照文字列集合に対する各文字列候補の相対位置を捕捉する２進指数を生成すること、および（ｄ）文字列候補と複数の文字列レコードを含むデータベースとの間の近似文字列照合を、レコードのデータベース全体の類似性メトリックを計算する必要なしに検索すること、のうちの少なくとも１つを含む。
【００１５】
ある実施形態では、あるコンピュータプログラムが提供され、前記プログラムはコンピュータ読取り可能媒体上に具現され、かつ管理のためのクライアントユーザインタフェース・フロントエンドおよび一般ユーザの入力およびレポートのためのウェブインタフェースを有する構造化問合せ言語（ＳＱＬ）を使用する。ある例示的な実施形態では、このシステムはウェブ対応であって、企業体のイントラネット上で実行される。さらに別の実施形態では、このシステムは、認証されたアクセスを有する個人によって企業体のファイアウォールの外側でインターネットを介して十分にアクセスされる。さらなる例示的な実施形態では、このシステムはWindows（登録商標）環境（Windowsは、ワシントン州レドモンド所在のMicrosoft社の登録商標である）において実行されている。このアプリケーションはフレキシブルであり、かつ主要な機能性を危うくすることなく様々な異なる環境で実行されるように設計される。
【００１６】
これらのシステムおよびプロセスは、本明細書に記述される特有の実施形態に限定されない。さらに、各システムおよび各プロセスのコンポーネントは、本明細書に記述されている他のコンポーネントおよびプロセスとは独立して別個に実施され得る。また各コンポーネントおよびプロセスは、他のアッセンブリパッケージおよびプロセスと組み合わせて使用され得る。
【００１７】
背景として、図１は、取引履歴が少なくとも部分的に加盟店集合体予測システムによって利用される日常的なカード支払い取引を有効化するための例示的な複数関係者による支払いカード産業システムを示すダイアグラム２０である。本明細書において使用しているように、加盟店集合体とは、加盟店ロケーションのハイレベルなグルーピングを指す。より具体的には、１件の小売業者に関する様々な個々の加盟店ロケーションが集められて（例えば、データベース内で互いにリンクされて）１つの加盟店集合体が形成される。従って、１つの加盟店ロケーションは、１つの加盟店集合体の１つのコンポーネントである。典型的には、加盟店集合体はストアチェーンを指す場合に使用され、ロケーションは、本明細書において詳述するように、取引データのデータベースに格納されている幾つかのフィールド値に基づいて集合化される。
【００１８】
本発明は、ＭａｓｔｅｒＣａｒｄ（登録商標）インターチェンジを使用するクレジットカードの支払いシステム等の支払いカードシステムに関する。ＭａｓｔｅｒＣａｒｄ（登録商標）インターチェンジは、ＭａｓｔｅｒＣａｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ社によって普及されている、ＭａｓｔｅｒＣａｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｉｎｃｏｒｐｏｒａｔｅｄ（登録商標）の会員である金融機関間で金融取引データを交換するための独自仕様の通信標準である。（ＭａｓｔｅｒＣａｒｄは、ニューヨーク州パーチェス所在のＭａｓｔｅｒＣａｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ社の登録商標である。）
【００１９】
ある典型的な支払いカードシステムでは、「発行者」と呼ばれる金融機関が消費者にクレジットカード等の支払いカードを発行し、消費者はこの支払いカードを使用して加盟店からの購入に対する支払いを申し出る。支払いカードによる支払いを受け入れるためには、加盟店は通常、金融支払いシステムの一部である金融機関と契約を結ばなければならない。この金融機関は一般に、「加盟店銀行」または「アクワイアリングバンク」または「アクワイアラバンク」と呼ばれる。消費者２２が支払いカード（金融取引カードとしても知られる）による購入の支払いを申し出ると、加盟店２４は購入高に関して加盟店銀行２６から認証を要求する。この要求は電話によって実行される場合もあるが、通常は販売時点端末の使用を介して実行される。販売時点端末は、支払いカード上の磁気ストライプから消費者の口座情報を読み取って加盟店銀行の取引処理コンピュータと電子的に通信する。或いは、加盟店銀行は第三者が取引処理を代行することを認可する場合もある。この場合、販売時点端末はこの第三者と通信するように構成される。このような第三者は通常、「加盟店プロセッサ」または「アクワイアリングプロセッサ」と呼ばれる。
【００２０】
インターチェンジ２８を使用して、加盟店銀行または加盟店プロセッサのコンピュータはカード発行者銀行３０のコンピュータと通信し、その消費者の口座が堅実な状態にあるかどうか、およびその購入がその消費者の利用可能な信用限度額の範囲内であるかどうかを決定する。これらの決定に基づいて、認証要求は謝絶または受容される。要求が受容されれば、加盟店に認証コードが発行される。
【００２１】
認証要求が受け入れられると、消費者の口座３２の利用可能信用限度額が下げられる。通常、ＭａｓｔｅｒＣａｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｉｎｃｏｒｐｏｒａｔｅｄ（登録商標）等の銀行カード協会は、商品が出荷されるまで、またはサービスが届けられるまで加盟店に取引をチャージまたは「獲得」させないという規則を普及させていることに起因して、課金は消費者口座へ即時的には計上されない。加盟店が商品を出荷する、またはサービスを届けると、加盟店は、例えば販売時点端末上への適切なデータ入力処置によってその取引を獲得する。取引が獲得される前に消費者が取引をキャンセルすれば、「無効」が発生する。取引が獲得された後に消費者が商品を返品すれば、「クレジット」が発生する。
【００２２】
取引が獲得された後、この取引は、加盟店と、加盟店銀行と、発行者との間で決済される。決済とは、その取引に関連づけられる加盟店の口座と、加盟店銀行と発行者との間の金融データまたは資金の転送を指す。通常、取引は獲得されて「バッチ」に累積され、バッチはグループとして決済される。このような取引に関連づけられるデータは、本明細書において詳述するように、将来の購入活動を予測する分野において利用される。
【００２３】
金融取引カードまたは支払いカードは、クレジットカード、デビットカードおよびプリペイドカードを指す可能性がある。これらのカードは全て、取引を実行するための支払い方法として使用され得る。本明細書に記述しているように、「金融取引カード」または「支払いカード」という言い回しはクレジットカード、デビットカードおよびプリペイドカード等のカードを含むが、支払い勘定情報を保持している場合がある移動電話、パーソナルデジタルアシスタント（ＰＤＡ）およびキーフォブ等の他の任意のデバイスも含む。
【００２４】
図２は、本発明の一実施形態による例示的なシステム１００を示す単純化されたブロック図である。ある実施形態において、システム１００は、例えばカスタマイズされた発行者−加盟店の関係性を実装すると同時に取引に関連づけられる履歴データの処理を実行するために使用される支払いカードシステムである。別の実施形態において、システム１００は、支払い取引に適用されるべき処理コードを入力するために口座保持者によって利用されることが可能な支払いカードシステムである。
【００２５】
より具体的には、この例示的な実施形態において、システム１００はサーバシステム１１２と、サーバシステム１１２へ接続されるクライアントシステム１１４とも称される複数のクライアントサブシステムとを含む。ある実施形態では、クライアントシステム１１４はウェブブラウザを含むコンピュータであり、よってサーバシステム１１２はインターネットを使用してクライアントシステム１１４へアクセス可能である。クライアントシステム１１４は、ローカルエリアネットワーク（ＬＡＮ）または広域ネットワーク（ＷＡＮ）等のネットワーク、ダイアルイン接続、ケーブルモデムおよび専用高速ＩＳＤＮ回線を含む多くのインタフェースを介してインターネットへ相互接続される。クライアントシステム１１４は、ウェブベース電話、パーソナルデジタルアシスタント（ＰＤＡ）または他のウェブベースの接続可能機器を含むインターネットへ相互接続することができる任意のデバイスであり得る。データベースサーバ１１６は、後に詳述するように、様々な事柄に関する情報を含むデータベース１２０へ接続される。ある実施形態では、サーバシステム１１２上に集中データベース１２０が格納され、クライアントシステム１１４の１つにおける潜在的ユーザはクライアントシステム１１４のうちの１つを介してサーバシステム１１２へログオンすることにより、集中データベース１２０へアクセスすることができる。ある代替実施形態では、データベース１２０はサーバシステム１１２から遠隔に格納され、かつ非集中式であってもよい。
【００２６】
後に論じるように、データベース１２０は、銀行カードネットワーク上で実行される販売行動の一部として生成される、加盟店、口座名義人または顧客および購入に関するデータを含む取引データを格納する。データベース１２０はさらに、報酬プログラムおよび特典に関する、異なる報酬プログラムおよび特典に関連づけられる処理コードおよび業務規定を含むデータも含む。
【００２７】
図３は、本発明の一実施形態によるシステム１２２のサーバアーキテクチャを示す例示的な実施形態の拡大ブロック図である。（図２に示す）システム１００のコンピュータに等しいシステム１２２におけるコンポーネントは、図３では、図２で使用している同じ参照数字を使用して識別されている。システム１２２は、サーバシステム１１２と、クライアントシステム１１４とを含む。サーバシステム１１２はさらに、データベースサーバ１１６と、アプリケーションサーバ１２４と、ウェブサーバ１２６と、ファックスサーバ１２８と、ディレクトリサーバ１３０と、メールサーバ１３２とを含む。データベースサーバ１１６およびディレクトリサーバ１３０へは、ディスク記憶ユニット１３４が結合される。サーバ１１６、１２４、１２６、１２８、１３０および１３２は、ローカルエリアネットワーク（ＬＡＮ）１３６内で結合されている。さらに、ＬＡＮ１３６へは、システム監督者のワークステーション１３８、ユーザのワークステーション１４０および監督者のワークステーション１４２も結合される。或いは、ワークステーション１３８、１４０および１４２はインターネットリンクを使用してＬＡＮ１３６へ結合され、またはイントラネットを介して接続される。
【００２８】
各ワークステーション１３８、１４０および１４２は、ウェブブラウザを有するパーソナルコンピュータである。これらのワークステーションにおいて実行される機能は、典型的には個々のワークステーション１３８、１４０および１４２において実行されるものとして示されるが、このような機能は、ＬＡＮ１３６へ結合される多くのパーソナルコンピュータのうちの１つにおいて実行され得る。ワークステーション１３８、１４０および１４２は、単にＬＡＮ１３６へのアクセスを有する個人により実行され得る異なるタイプの機能の理解を促進する目的で、別々の機能に関連づけられるものとして示されているに過ぎない。
【００２９】
サーバシステム１１２は、ＩＳＰインターネット接続１４８を使用して従業員を含む様々な個人１４４へ、かつ例えば口座名義人、顧客、監査人、他である第三者１４６へ通信可能式に結合されるように構成される。この例示的な実施形態における通信はインターネットを使用して実行されるように示されているが、他の実施形態では、他の任意の広域ネットワーク（ＷＡＮ）型通信を利用することができる。即ち、これらのシステムおよびプロセスは、インターネットを使用する実施に限定されない。さらに、かつＷＡＮ１５０ではなく、ローカルエリアネットワーク１３６がＷＡＮ１５０の代わりに使用される可能性もある。
【００３０】
この例示的な実施形態では、ワークステーション１５４を有する任意の認証された個人がシステム１２２にアクセスすることができる。クライアントシステムのうちの少なくとも１つは、リモートロケーションに位置づけられるマネージャワークステーション１５６を含む。ワークステーション１５４および１５６は、ウェブブラウザを有するパーソナルコンピュータである。また、ワークステーション１５４および１５６は、サーバシステム１１２と通信するように構成される。さらに、ファックスサーバ１２８は、電話回線を使用してクライアントシステム１５６を含む遠隔に位置づけられたクライアントシステムと通信する。ファックスサーバ１２８は、他のクライアントシステム１３８、１４０および１４２とも通信するように構成される。
【００３１】
図４は、各コンポーネントが金融取引カードネットワークのオペレーションに関する予測を提供する集団的または集合的な加盟店予測システムの一実施形態のハイレベル機能コンポーネントを示すフローチャート２００である。従って、さらに述べるように、これらの予測は１つの予測へと集合される。この予測の集合化は、アンサンブル予測と称されることがある。本明細書に記述しているこれらの実施形態に関する一例は、受信された加盟店ロケーションデータに関する集合予測を含む。図４に関連して紹介しているが、本明細書では、全ての予測アルゴリズムについてより詳細に説明する。
【００３２】
第１のコンポーネントは類似ロケーション予測アルゴリズム２０２（ｋ類似ロケーション予測アルゴリズムと称される場合がある）であり、これは、所定の加盟店ロケーションに最も類似する「ｋ」件の加盟店ロケーションを検索するように構成される。予測アルゴリズム２０２はさらに、検索された「ｋ」件の最も類似するロケーションの中から類似する加盟店ロケーションの１グループをモードグループとして分類するように動作可能である。
【００３３】
文書予測アルゴリズムとしての集合ロケーション２０４は、あらゆるフィールドと、既知の値のスペースにおけるロケーションの各集合体（ハイレベルのデータ分類）に関するフィールド値との関連性を計算するために利用され、結果は文書として格納される。これらの文書からの最も関連のある値は、予測を生成するために利用される。
【００３４】
予測が特定の第三者ブランドに関連づけられる場合には、ロケーション照合システムを含む第三者データ予測アルゴリズム２０６が利用される。アルゴリズム２０６への少なくとも１つの入力は第三者から受信される取引レコードを含み、これが予測の生成に利用される。ある実施形態では、この予測は、第三者データソースとのロケーション照合が実行された後に生成される。フローチャート２００には、その一実施形態が主としてベンフォードの法則に基づき、かつさらには同一のグルーピングに属する加盟店について観察される、Ｂｅｎｆｏｒｄにより識別される分布から比較的一貫した方法で拡散する傾向に基づく数値サイン予測アルゴリズム２０８が含まれる。アルゴリズム２０８から結果的に生じる予測は、各加盟店ロケーションに比較して最も類似する数値分布を有するロケーショングループになる。
【００３５】
ある実施形態において、オラクル（Ｏｒａｃｌｅ）に実装されるトップレベル統計モデルおよびスコアリングエンジン２１０は、アルゴリズム２０２、２０４、２０６および２０８からの予測を利用して、データベース内に新しく受信および／または格納されるデータ間のグループメンバーシップを決定する。このデータの一例は、加盟店ロケーションデータである。少なくとも１つの実施形態では、かつ本明細書でさらに述べるように、データベース内の加盟店ロケーションデータはロケーションおよび距離に関して、例えば所定のロケーションから所定の距離内にある幾つかの加盟店ロケーションに関して記述される。少なくとも１つの態様において、ロケーションおよび距離は必ずしも地理的なものではなく、むしろデータベースに格納されている加盟店データを利用して計算されるような類似性に基づいている。特定の実施形態では、ロケーションおよび距離は、データベース内のフィールド値およびフィールドのトークン化された値に関するクロス属性加重式ターム出現頻度／文書出現頻度逆数（ＴＦ／ＩＤＦ）の計算によって測定されるような類似性に基づいている。
【００３６】
図５は、スコアリングエンジン２１０のオペレーションを示すフローチャート２２０である。具体的には、スコアリングエンジン２１０は、２２２において、アルゴリズム２０２、２０４、２０６および２０８からの加盟店ロケーション予測をオラクルデータマイニング（ＯＤＭ）アプリケーション２２４における予測に関するメタデータと共に使用し、個々の予測を取り囲む状況を記述し、次いで２２６において、集合化された個々の予測から最終予測を生成する。この最終予測は、加盟店ロケーションに関するものであってもよい。またこのアプリケーションは、複数のアルゴリズム２０２、２０４、２０６および２０８に関する集合予測に関連づけられる信頼スコアの生成も行う。
【００３７】
次に、４つのアルゴリズム２０２、２０４、２０６および２０８の各々についてさらに詳しく説明する。
【００３８】
ｋ件の類似ロケーション（アルゴリズム２０２）
【００３９】
図６は、類似性に基づいて、例えばロケーションの類似性に基づいて加盟店ロケーションを分類するアルゴリズム２０２へ入力されるデータを示すフローチャート２５０である。チェーンまたはコレクション（例えば、グループ）メンバーシップを導出するコンテキストにおいて有意義であることが知られるロケーションレベルフィールドの集合またはロケーション座標２５２は、金融取引カードを引き受ける機関のデータベース２５４から識別される。さらに、日常的な新規／変更ロケーションデータベース２５６並びにその関連の新規／変更ロケーション座標２５８からのデータは、後述する加盟店ロケーション分類アルゴリズムへ供給される。
【００４０】
図７は、加盟店ロケーションをグループメンバーシップに分類するために利用されるアルゴリズムのうちの１つ（図４に示すアルゴリズム２０２）を記述するフローチャート２８０である。アルゴリズム２０２は、少なくとも図６のフローチャート２５０に関して記述されているデータを利用する。具体的には、２８２において、データベース内の加盟店ロケーションデータが、所定のロケーションから所定の距離内にある幾つか（ｋ件）のロケーションについて検索される。さらに、２８４において、所定の距離内にあるロケーションが類似性について検索され、任意の新規／変更ロケーションが決定される。２８６では、特定の特徴スペース（取引データをアルゴリズム２０２へ入力する起点エリア）内の前記（ｋ件の）ロケーション間で発生する加盟店ロケーションを分類することによって、モード値が決定される。（ｋ件の）ロケーション記録の分類によって結果的に得られる最も出現頻度の高い値は最高の重みを有し、かつモード値と称され、後述するように決定される。このモード値は、２８８においてアルゴリズム２０２から予測として返される。
【００４１】
後に詳しく述べるように、フィールド（ロケーション座標２５２および２５８）はトークン化され、特徴スペースを網羅するトークン化された全てのフィールド値に関して文書出現頻度の逆数が計算される。ある実施形態では、各ロケーションについて、各フィールド値およびトークン化された各フィールド値の重みメトリックの疎行列がターム出現頻度／文書出現頻度逆数として計算される。予測値は、１つまたはそれ以上のフィールドタイプおよびフィールド値に基づいて所定のロケーションフィールドを他のあらゆるロケーションフィールドに結合することによって計算される。
【００４２】
疎行列はロケーション、ターム値のフィールドタイプおよび重みおよびタームトークンを含み、下記の段落に記述するように生成される。
【００４３】
行列は、全てのフィールド値およびトークン化されたフィールド値の文書出現頻度逆数を含んで生成され、かつある実施形態では９個のディメンションを網羅する。ある特定の実施形態では、これらの９個のディメンションは、加盟店カテゴリコード、インターバンクカード協会（ＩＣＡ）コード、事業領域、加盟店名、加盟店電話番号、アクワイアリング加盟店ＩＤ、ティア加盟店ＩＤ、加盟店の正式名称および連邦税ＩＤを含む。これらのディメンションは、全ての加盟店ロケーションレコードに包含される。文書出現頻度の逆数は、レコード数を特定の値を含むレコードの数で除算した商の（ある特定の実施形態では２を底とする）対数である。一例を表１に示す。ある実施形態において、この商は、９個のディメンションの各々について別々に計算される。レコードの数は、加盟店ロケーションの数として計算される。特定のタームを含むレコードの数は、各フィールドタイプ内に各タームを含む加盟店ロケーションの数を計数することによって計算される。
【００４４】
【表１】
【００４５】
各ロケーション毎に、表２に示すような、クロス属性正規化ターム出現頻度−文書出現頻度二重逆数重みが９個のディメンションを網羅する値およびトークン化された値について計算される。この場合も、９個のディメンションは加盟店カテゴリコード、ＩＣＡコード、事業領域、加盟店名、加盟店電話番号、アクワイアリング加盟店ＩＤ、ティア加盟店ＩＤ、加盟店の正式名称および連邦税ＩＤを含む。
【００４６】
【表２】
【００４７】
所定のロケーションに関するグループメンバーシップ予測および信頼度は、予測すべきロケーションをフィールドタイプおよびフィールド値上の他の全てのロケーションへ結合し、次いで共通するフィールドタイプおよびフィールド値に関してターム出現頻度−文書出現頻度二重／逆数重みの積を合計することによって計算される。ロケーション結果は次に結果スコアの降順にソートされ、最も高いスコアを有する例えば１３件のロケーション間で発生するモードグループが予測として与えられる。この予測の信頼スコアは、上位１３件のロケーションのうちで同一のグループ（予測された値）を含んでいたロケーションの数、予測されたグループに属するｋ件のロケーションの個々の重みおよびこれらの重み間の分散によって表される。
【００４８】
文書予測としての集合ロケーション（アルゴリズム２０４）
【００４９】
図８は、文書内の集合へ分類系として集合化されたロケーションを示すダイアグラム３００である。集合ロケーションの文書を生成するアルゴリズム２０４（図４に示す）は、インターネット検索エンジンによって一般に使用される文書関連性アルゴリズムに類似するものである。具体的には、加盟店ロケーションの各集合体またはコレクションに対する所定の加盟店ロケーションの関連性は、下記のようにして計算される。
【００５０】
文書３０２を生成するためには、例えば住所である関連特徴が複数のロケーション３０４に関するデータベースのデータから抽出されて集合に、例えば集合３０６にグルーピングされる。説明を目的として、ダイアグラム３００は、４つのロケーション集合３０６、３０８、３１０および３１２を含んでいる。集合３１２は集合Ｍとラベリングされているが、これは、特定の実施において、集合の数は図示されている４つより多い、または少ない場合があることを示す。同様に、１集合内のロケーションの数も１から「Ｎ」まで変わる可能性がある。
【００５１】
各々が抽出された関連する特徴を含む生成された文書３０２、３２０、３２２および３２４は、辞書３３０に集められる。辞書３３０を利用して疎行列３４０が形成され、これにより、抽出された特徴を使用して、各集合加盟店グループ毎にターム出現頻度および文書出現頻度逆数の少なくとも一方に基づいて、各フィールド値およびトークン化されたフィールド値の関連性が計算される。
【００５２】
疎行列３４０内では、ロケーションレベルの重みの行列が、フィールドタイプおよびフィールド値に基づいて加盟店グループの重みの行列に結合される。ある実施形態では、これらの重みの和が関連性エンジン３５０によって利用され、各ロケーションの各加盟店グループに対する関連性が決定される。関連性が最も高い加盟店グループは、先に述べた予測値として返される。より具体的には、グループ、フィールドタイプおよびタームルールおよびタームトークンの重みから成る疎行列は、次の段落で説明するようにして生成される。
【００５３】
まず、全ての加盟店ロケーションレコードに亘り、本明細書において別段で列挙した９個のディメンション、具体的には加盟店カテゴリコード、ＩＣＡコード、事業領域、加盟店名、加盟店電話番号、アクワイアリング加盟店ＩＤ、ティア加盟店ＩＤ、加盟店の正式名称および連邦税ＩＤを網羅する全てのフィールド値およびトークン化されたフィールド値の文書頻度の逆数を含む行列が生成される。
【００５４】
文書予測アルゴリズムとしての集合ロケーションに関して、かつ表３に示すように、文書頻度の逆数は、比率、即ち特定の値を含むレコードの数で除算されたレコードの数の対数（ある特定の実施形態では２を底とする）である。ある実施形態では、文書頻度の逆数は９個のディメンションの各々について別々に計算される。レコードの数は、加盟店ロケーションの数として計算される。特定のタームを含むレコードの数は、各フィールドタイプ内の各タームを含む加盟店ロケーションの数を計数することによって計算される。
【００５５】
【表３】
【００５６】
各グループ毎に、かつ各グループに属する全てのロケーション毎に、表４に示すように、加盟店カテゴリコード、ＩＣＡコード、事業領域、加盟店名、加盟店電話番号、アクワイアリング加盟店ＩＤ、ティア加盟店ＩＤ、加盟店の正式名称および連邦税ＩＤである９個のディメンションを網羅する値およびトークン化された値について、クロス属性正規化ターム出現頻度−文書頻度の二重逆数が計算される。
【００５７】
【表４】
【００５８】
所定のロケーションに関する１つのグループメンバーシップ予測は、先に説明した（ｋ件の）類似ロケーション行列からの行をフィールドタイプおよびフィールド値上のグループ行列に結合し、次いで共通のフィールドタイプおよびフィールド値のターム出現頻度−文書頻度の二重逆数の重みの積を合計することによって計算される。予測されるグループおよび信頼スコアは、最も高い類似性スコア（一致するフィールド値およびトークン化された値の重みの積の和によって与えられる）を有するグループである。結果的に生じるスコアは、この予測の信頼性である。
【００５９】
第三者データ予測とロケーション照合（アルゴリズム２０６）
【００６０】
アンサンブル予測の第３のコンポーネントは、加盟店ロケーションによって金融取引のデータベースに照合されたことのある第三者提供データを使用するアルゴリズム２０６（図４に示す）である。ある実施形態では、これらの第三者レコードに、例えば売り手に関するチェーンＩＤが割り当てられる。これらのチェーンＩＤは、金融取引カードブランド（例えば、カード発行者）に関連づけられる加盟店ロケーションのグループにリンクされる。従って、予測は単に、第三者レコードがリンクされているチェーンに対応する加盟店データのグルーピングになる。このリンク付けは、次の段落で説明するようにロケーション照合に続いて発生する。
【００６１】
ロケーションが（売り手によって）チェーンへ割り当てられている場合、加盟店ロケーションのデータセットは第三者データプロバイダから抽出される。第三者加盟店ロケーションのスペース内の各チェーンは、対応する適切なグループへ割り当てられる。近似加盟店ロケーション照合エンジンは、第三者加盟店ロケーションレコードの集合をカード発行者により保持される加盟店ロケーションレコードの集合へ結合するために使用される。次に、所定のロケーションに関する予測グループが、カード発行者の加盟店ロケーションレコードに一致した第三者ロケーションレコードに対応するチェーンに相当するグループとして計算される。信頼スコアは、近似加盟店ロケーション照合エンジンによって割り当てられる照合信頼スコアである。
【００６２】
数値サイン予測（アルゴリズム２０８）
【００６３】
ある実施形態において、加盟店数値サインアルゴリズム２０８（図４に示す）は、第１の位置における一日当たりの取引額および取引量の数表示分布に関する観察を使用する。具体的に言えば、この分布は、様々な加盟店データが集合される際には幾分か一意になる傾向がある。さらに、この分布は、自然データにおいてベンフォードの法則が提案する分布に合致している傾向がある。実世界の例では、ファーストフードレストランのチェーンは、取引額の最初の数字として特定の数字を繰返し現出させる傾向を示すことがある。このような傾向は少なくとも部分的に、例えば、ファーストフードレストランチェーンのフランチャイズ加盟店がある特定のロケーションまたは住所に存在することを確認するために利用され得る。
【００６４】
このようなアルゴリズムを利用する予測の一例は、各加盟店集合（加盟店データのグルーピング）からの加盟店ロケーションのランダムな１０パーセントサンプルである。加盟店集合毎に、第１の位置の取引額および取引量において発生する数字１−９の分布が計算されかつ集約され、この分布と、ベンフォードの法則により識別される分布との間の角距離が計算される。
【００６５】
次には、所定の加盟店ロケーションについて、第１の位置の取引額および取引量において発生する数字１−９の分布が計算され、この分布と、ベンフォードの法則により識別される分布との間の角距離が計算される。加盟店ロケーションの角距離に最も近い角距離を有する加盟店集合は、その所定のロケーションの加盟店集合予測として与えられる。
【００６６】
より具体的には、かつ各グループ毎に、取引計数、取引額および平均取引額の間における、グループ内の全てのロケーションを網羅する各数字（即ち、１、２、３、４、５、６、７、８、９）の出現頻度の分布が計算され、全体に対する比率として表される。前記分布は次に、表に格納される。表５は、これを表したものである。
【００６７】
【表５】
【００６８】
各グループに関する分布が計算されると、各グループに関する数値サインが、このグループの分布ベクトルとベンフォードの法則が提案する分布ベクトルとのドット積を計算することによって決定される。このドット積（発散角度）は、各グループの分布ベクトルの平方和によって除算される。ベンフォードの法則において識別される分布が計算され、表に格納される。表６は、これを表したものである。
【００６９】
【表６】
【００７０】
各ロケーション毎に、所定のロケーションに関して１か月の期間内に観察された取引計数、取引額および平均取引額を網羅する各数字（１、２、３、４、５、６、７、８、９）の出現頻度の分布が計算され、全体に対する比率として表される。これらの分布は次に表に格納され、表７はこれを表す。
【００７１】
【表７】
【００７２】
各ロケーションに関する分布が計算されると、各ロケーションに関する数値サインが、このロケーションの分布ベクトルとベンフォードの法則が提案する分布ベクトルとのドット積を計算することによって決定される。このドット積（発散角度）は、各ロケーションの分布ベクトルの平方和によって除算され、かつベンフォードの法則において識別される分布が計算され、表に格納される。表８は、これを表したものである。
【００７３】
【表８】
【００７４】
次に、所定のロケーションに関するグループメンバーシップ予測が、この所定のロケーションの数値サインに最も近い数値サインを有するグループを見つけることによって計算され、信頼スコアがこれらの２サイン間の距離として計算される。
【００７５】
統計モデルとスコアリング
【００７６】
図５に関連して先に述べたように、４つの予測アルゴリズム（２０２、２０４、２０６および２０８）からの各予測値は、２２２において、各予測の環境を記述する豊富なメタデータ集合と共に集められ、Ｏｒａｃｌｅデータマイニング（ＯＤＭ）アプリケーション２２４へ入力される。ＯＤＭアプリケーション２２４は、ある実施形態では、ラベリングされたトレーニングデータを使用して構築される統計モデル（決定木）を利用して各予測値へ信頼スコアを割り当てる。次には、最も高い信頼スコアを有する予測値が各加盟店ロケーションの最終的な集合値予測として提供される。
【００７７】
近似文字列照合
【００７８】
先に述べたように、アンサンブル予測の１つのコンポーネントは、例えば金融取引カード提携加盟店ロケーションのデータベースへ照合されているロケーションデータを使用するアルゴリズムである。幾つかのデータは、第三者ソースによって提供されてもよい。後述の実施形態は、データベース内のデータについて近似列（例えば、文字列）照合を検索するための方法およびシステムに関する。この実施形態では、文字列照合を利用して、例えばあるロケーションを表す文字列がそのデータベースにおいて別の文字列によって表されているかどうかが決定される。このようなアルゴリズムは、取引レコードにおいて発生する変形に起因して、特にこれらのレコードは加盟店の名称およびロケーションに関連することから、様々な実施形態において適切である。
【００７９】
近似文字列照合のデータベースシステムは、正確に一致する、または共通のフィールド値等の共通の結合キーがデータ内に存在しない場合に、１つのレコード集合を別のレコード集合へ結合するように動作可能である。おそらくは、これらのレコード集合には幾分かの類似性が存在する。
【００８０】
典型的には、２つのデータセットが１つのデータベース内で結合されると、これらは１つまたは複数のフィールドで正確な値を共有する。データ内の変形に起因して２つのデータソース（レコード集合）によって正確なフィールド値が共有されない場合、個々のデータソースからのデータセットを結合する伝統的な方法は、２つの値を取って、そこでその類似性を計算してリターンするという機能を実装することである。データセットを結合する基準として、このタイプの機能の使用することは、結合されるべき各データセット内のレコードの数の積に等しい反復回数を必要とする。
【００８１】
一例として、データセットＡ内に１０，０００件のレコードが存在しかつデータセットＢ内に５００，０００件のレコードが存在すれば、類似性計算機能はデータセットＡをデータセットＢへ結合するために５０億回呼び出されることになる。さらに、このような機能が呼び出される場合、指数または機能ベース指数はデータベースオプティマイザによって使用されなくなる。このタイプのデータセットは非常に非効率的であって、自明でないデータ量を有するデータセットの結合に使用するにはあまりに処理が集約的に過ぎる。
【００８２】
文字列照合技術は、様々な実施形態において下記のコンポーネントのうちの１つまたはそれ以上を利用して実装されるものが開発されている。具体的には、主成分因子分析（ＰＣＦＡ）を使用して生成される結合基準において参照文字列集合が使用される。ＰＣＦＡは、既知の値のスペース内に存在する極めて異種である文字列集合を識別しようとするものであり、前記文字列集合は参照文字列として使用される。
【００８３】
別のコンポーネントは、リレーショナルデータベース管理システム（ＲＤＢＭＳ）におけるパフォーマンスを最大化するために純粋なＡＳＣＩＩ構造化問合せ言語（ＳＱＬ）に実装されるｎグラム頻度類似性計算である。さらに、ＲＤＢＭＳには、ｎグラム頻度類似性計算を使用して２進キーを形成するためのプロセスも実装される。２進キーは、後述するように、ＰＣＦＡにおいて識別された参照文字列の各々に対する所定のレコードの類似性を示す。
【００８４】
ある実施形態では、全てのｎグラムの文書頻度逆数（ＩＤＦ）を含むテーブルおよびクロス属性加重ターム出現頻度／文書頻度逆数（ＴＦ／ＩＤＦ）計算のＳＱＬ実装であるとして、ＲＤＢＭＳ内でデータ駆動標準化機能セットが実装される。
【００８５】
文字列照合技術の一実施形態は、同じ２進キー値を共有するレコードを結合し、次いで全ての一致するｎグラムのＴＦ／ＩＤＦの重みの積を合計することによってこれらを関連性毎にソートするパラメータ化された分析ＳＱＬクエリを含む。そのレコードが所定のしきい値より上でｉ番目の参照文字列に一致すれば、２進キーにおけるｉ番目のビットは論理１に設定される。
【００８６】
ＲＤＢＭＳ内では、結合により生じる各照合へ信頼スコアを割り当てるように、プロセスが実装され、同時に、データセットの結合において取り込まれるデータを格納するＲＤＢＭＳデータモデルも包含される。
【００８７】
データセット結合問題の１つのシンプルなものとしては、１つの名称（または住所）を、Ｏｒａｃｌｅテーブル等のデータベース内に含まれる名称（または住所）のより大きい集合に対して照合することである。このｎグラム照合の一例を表９に示す。
【００８８】
【表９】
【００８９】
データセット結合のソリューションに必要とされるエレメントは、文字列間の任意の類似性を測定するためのメトリックである。ｎグラムは単にｎ文字より成る一意の文字列であり、ｎグラム照合は、ｎグラム間の照合を決定するためのプロセスである。ｎが２に等しい事例では、表１における住所候補は下記の各２グラム、即ち「１０」、「００」、「０１」、「１４」、「４＜スペース＞」、「＜スペース＞Ｓ」、「Ｓ＜スペース＞」、「＜スペース＞Ｃ」、「Ｃｌ」、「ｌａ」、．．．、「Ｒｄ」から成る。
【００９０】
表１０は、ｎグラム照合アルゴリズムを要約したものである。これは、文字列候補（例えば、Ｃａｎｄｉｄａｔｅ＿ａｒｒａｙ）のｎグラム頻度ベクトルを決定することと、照合データベース候補（例えば、Ｃａｎｄｉｄａｔｅ＿Ｍａｔｃｈ＿Ａｒｒａｙ）における各エントリのｎグラム頻度ベクトルを決定することと、前記Ｃａｎｄｉｄａｔｅ＿ａｒｒａｙと前記Ｃａｎｄｉｄａｔｅ＿Ｍａｔｃｈ＿Ａｒｒａｙとの間の類似性の度合いを測定することと、特定のしきい値を超える照合候補を保持することを含む。例えば、「ＪｏＪｏ’ｓ Ｄｉｎｅｒ」は下表のようになる。
【００９１】
【表１０】
【００９２】
表１１、表１２および表１３は、ｎグラム照合メトリックの例である。「内積」はアレイのドット積であり、「大きさ」は平方和の平方根であり、「（角度の）余弦」は大きさの積で除算されたドット積であり、角度は大きさの積で除算されたドット積の逆余弦である。
【００９３】
【表１１】
【００９４】
【表１２】
【００９５】
【表１３】
【００９６】
参照文字列
【００９７】
上記表および記述は、文字列を量的に表現しかつこれらの間の類似性を測定する能力を示している。この時点で、各レコードの指数は、参照文字列の小集合に対するその相対位置に基づいて構築され得る。
【００９８】
参照文字列を選ぶことにより、参照文字列の各々に対する新しいレコードの相対位置を計算することができる。さらに、データベース内のあらゆるレコードは、参照文字列に対するその固有の予め計算された位置を有する。従って、新しいレコードとデータベース全体との間の完全な類似性メトリックを計算する必要なしに、同じ近接性で指数が付けられたレコードを検索することによって近似照合を見つけることができる。参照文字列を選択する１つの目的は、異種であるレコードを選ぶことであり、こうしてより良い見通しが得られる。次の段落では、参照文字列選択の１つの手法を概説する。
【００９９】
参照文字列は、指数付けされているデータベースから文字列のサンプルをとることによって識別される。サンプル内の各文字列のｎグラム表現は、頻度のベクトルを生成することによって生成される。但し、ベクトルのｉ番目の成分は、その文字列においてｎグラムが発生した回数を含む。類似性行列は、余弦類似性メトリックを使用してあらゆるサンプル文字列ペア間の類似性を測定することにより生成される。
【０１００】
類似性データのコレクションにおいて異種成分を見つけるための１つの技術が、主成分分析である。主成分分析は類似性行列に対して実行され、最初のｋ個の主成分が保持される。各成分上の最大負荷を有するサンプル文字列が保持され、参照文字列集合が形成される。
【０１０１】
２進指数および情報検索
【０１０２】
指数を生成できるように類似する文字列をグループに纏め、近似文字列照合の間に高速検索候補を提供するために、潜在的な各レコード候補および各比較レコードがｎグラム頻度類似性ＳＱＬ計算を使用して参照文字列の各々と比較される。
【０１０３】
類似性計算が予め定義されたしきい値より高いスコアを産生すれば、参照文字列に対応する２進キーの位置に値１が割り当てられる。スコアがしきい値より低ければ、対応するキー位置に０が割り当てられる。
【０１０４】
ＮＧＲＡＭ類似性計算
【０１０５】
所定の２つの文字列内に存在する全ての一意のＮ−ＧＲＡＭＳの出現頻度を含む二次元ベクトルを形成するＳＱＬクエリが開発されている。このクエリは、次に、各頻度積の合計を頻度ベクトルの各ディメンションの大きさの平方で割って、正規化された類似性メトリックに到達する。
【０１０６】
このような計算は、次の例、即ち比較文字列Ａが「ＭＡＳＴＥＲＣＡＲＤ」であり、かつ比較文字列Ｂが「ＭＡＳＴＥＲＣＨＡＲＧＥ」である例によって表される。下表、表１４は、２つの比較文字列内に存在するあらゆる一意のｎグラムの出現頻度を含む二次元ベクトルである。
【０１０７】
【表１４】
【０１０８】
文字列Ａの大きさは、ディメンションＡにおける各頻度値の平方和の平方根として計算され、具体的には、文字列Ａの大きさは３．０である。文字列Ｂの大きさは、ディメンションＢにおける各頻度値の平方和の平方根として計算され、具体的には、大きさＢは３．３１６６２４７９０３５５４である。ベクトルのドット積が計算され、この例の場合、ドット積は７．０（ＡおよびＢの双方が値１を有する表エントリの数）である。類似性はドット積／（大きさＡｘ大きさＢ）として、即ちこの例示的な例では０．７０３５２６４７０６８１４４８として計算される。
【０１０９】
２進キー値の形成
【０１１０】
類似性計算が予め定義されたしきい値より高いスコアを産生すれば、参照文字列に対応する２進キーの位置に値１が割り当てられる。スコアがしきい値より低ければ、対応するキー位置に０が割り当てられる。ある実施形態において、２進キー位置を決定するためのプロセスは、ＳＱＬおよびＰＬ／ＳＱＬの組合せを使用して実装される。このアルゴリズムの実装は、アルゴリズム内の以前の反復においてその正確な値に関する２進キー値が計算されていれば所定の文字列に２進キー値を自動的に割り当てるように、分析的構造化問合せ言語を使用することにより、必要とされる文字列比較計算の数を最小化する。この最適化は、ＳＱＬで達成される。
【０１１１】
一意の識別子および各２進キー値は、ＲＤＢＭＳ内の仕切られた索引構成表（ＩＯＴ）に格納される。一意のデータセットは各々単一のパーティション内に格納され、２つのデータセットが同じパーティションを共有することはない。ロードパフォーマンスを最大化するために、この表への各データセットのロードは、ｃｒｅａｔｅ ｔａｂｌｅ ａｓ ｓｅｌｅｃｔ（ＣＴＡＳ）およびパーティション交換を使用して達成される。各パーティション内のデータは、結合パフォーマンスを最大化するために２進キー値順に格納される。
【０１１２】
データの標準化
【０１１３】
類似性比較および２進キー値分布の精度を高めるために、ある実施形態では、データが既知の略語および同義語について標準化される。このようなデータ標準化を達成するために、様々なフィールドタイプに関して全ての既知の変形および同義語をその個々の標準表現と共に含むテーブルが生成される。次に、アルゴリズムは各データエレメントをトークン化しかつ任意の既知の変形または同義語をその標準形式にマップするように作動する。
【０１１４】
ＩＤＦテーブル
【０１１５】
近似照合結合に関与するフィールド内に存在する全てのｎグラムについて加重ＴＦ／ＩＤＦを計算する際のパフォーマンスをより高速にするために、レコード候補のスペース内に存在する全ての２文字ｎグラムの文書頻度逆数を含むテーブルが構築される。スペース内の全てのｎグラムの形成はＰＬ／ＳＱＬを介して達成されるが、ＩＤＦの計算はＡＳＣＩＩ ＳＱＬで行われる。ＩＤＦテーブルは、各データカテゴリの可能なｎグラムの各々についてＩＤＦ値を格納する。このテーブルは、結合パフォーマンスを最大化するために、データカテゴリおよびｎグラムに従って索引構成される。
【０１１６】
クロス属性加重ＴＦ／ＩＤＦ
【０１１７】
近似照合結合に関与するフィールド毎に、所定のレコード内に存在する２文字ｎグラムの各々へ重みまたは重大さを割り当てるために、各ｎグラム値についてクロス属性加重ターム出現頻度／文書頻度逆数ＴＦ／ＩＤＦ値が計算される。ｎグラムタームおよび所定の各レコードおよびフィールド内でのその個々の出現頻度は、入力としてＲＥＦ＿ＣＵＲＳＯＲをとるパイプライン表関数を使用して計算される。この計算は、伝統的な加重ＴＦ／ＩＤＦ計算とは僅かに異なり、各フィールド内の各ｎグラムについてＴＦ／ＩＤＦを計算した後に、各フィールド内の全てのｎグラムの重みを同じレコードの他のフィールド内に存在するｎグラムの全体の重みに従って上下に調整する。この技術により、各フィールド内の値の全体的な重大さに従った照合ｎグラムの相対的重みに対するレコードレベルの動的調整が生じる。
【０１１８】
先に述べたように、所定のデータセット内の各レコードの一意の識別子は、結合パフォーマンスを最大化するために、そのｎグラムタームおよび計算された重みスコアと共に仕切られた索引構成表（ＩＯＴ）に格納される。このテーブルは、一意の識別子、データカテゴリおよびｎグラムターム値に従って編成される。一意のデータセットは各々、テーブル内の別々のパーティション内に格納される。各パーティションは、ロードパフォーマンスを最大化するためにｃｒｅａｔｅ ｔａｂｌｅ ａｓ ｓｅｌｅｃｔおよびパーティション交換を使用してロードされる。
【０１１９】
結合クエリ
【０１２０】
２進キーおよびクロス属性ＴＦ／ＩＤＦ計算がＲＤＢＭＳへロードされると、分析的な結合クエリを使用して全ての照合レコード候補が検索され、かつ比較レコードに照らしたその関連性または照合品質に従ってソートされる。これは、まず一致する２進キー値を有するレコードを結合し、次に結果的に生じるレコード候補のｎグラム値を結合しかつこれらの重みの積の合計を計算することによって達成される。
【０１２１】
信頼スコアの割当て
【０１２２】
結合クエリの結果は、各入力およびレコード候補に対して超低レベル比較を実行し、次いで先に述べたＯｒａｃｌｅデータマイニングアプリケーションに使用するための統計モデルを使用して信頼スコアを割り当てるＲＤＢＭＳ内に実装された関数を介して送信される。
【０１２３】
近似文字列照合に関連づけられる上述のプロセスを、さらに図９および図１０に示す。図９および図１０は各々、参照文字列集合の決定を示し、かつ文字列候補の類似性メトリックを決定するための参照文字列集合の利用を示すフローチャート４００および４５０である。各成分上の最大ローディングを有するサンプル文字列は、参照文字列集合を形成するために保持される。これらのサンプル文字列は、相関目的で主成分を表している。類似性メトリックは、文字列候補と決定された参照文字列集合内の個々の文字列との比較における幾つかの一致するｎグラムに基づいている。
【０１２４】
具体的には、かつ図９を参照すると、データベースは潜在的照合候補データのスペース４０２を含む。このスペース４０２は、本明細書において文字列のデータベース（即ち、加盟店の名称および／またはロケーションデータ）と称することがある。本明細書で記述しているように、４０４において、照合フィールドまたはデータベースレコードのランダムなサンプルが、例えば異種文字列集合の最適化探索に基づいて生成される。４０６において、類似性行列が計算され、かつ４０８において主成分因子分析が適用され、その結果主成分４１０が生じ、その各々は対応する参照文字列を参照する。この参照文字列集合は、この集合が具体的には異種データを包含するように生成されることから、文字列候補に対する比較に有益である。
【０１２５】
次に、図１０を参照すると、４５２において、文字列候補を受信した時点で、各文字列候補と各主成分に関連づけられる参照文字列との間の類似性が計算される。本明細書で記述しているように、このような比較はｎグラム照合アルゴリズムに基づく場合もあり、よって、４５４において、文字列候補の各参照文字列およびその対応する主成分に対する類似性を示す２進キーが生成される。４５６では、高速かつ効率的な近似文字列照合のために、レコード（参照文字列）がその個々の２進キーレコードの比較に基づいて文字列候補へ結合される。このようなプロセスは、ユーザが参照文字列（加盟店の名称および／またはロケーションデータを含んでもよい）と加盟店の名称および／またはロケーションデータを表す場合もある文字列候補との間の高確率照合を迅速に検索することを可能にする。４５８において、照合されるべき各データベースレコードの２進キーを生成することにより、４６０では、参照文字列の文字列候補に対する照合ファイルを生成することができる。
【０１２６】
以上、様々な特有の実施形態に関して本発明を説明したが、当業者には、本発明をクレームの精神および範囲内にある変形によって実施し得ることが認識されるであろう。
【技術分野】
【０００１】
本発明は概して加盟店予測システムに関し、特に、銀行カードネットワーク内に含まれるデータベースレコードへの加入に関連してデータベース内に近似文字列照合を実装するための方法およびシステムに関する。
【背景技術】
【０００２】
歴史的にみると、消費者取引の支払いに「チャージ」カードを使用することはせいぜい地域的なものであって、クレジット発行銀行と多様な地域加盟店との間の関係性に基づくものであった。支払いカード産業は、発行銀行が協会（例えば、MasterCard）を形成し、そして第三者取引処理会社（例えば、「Merchant Acquirers」）を取り込むことにより、加盟店とカード発行者との銀行関係に関わらず、カード所有者がいずれの加盟店の施設においてもそのチャージカードを広範に使用できるように発展してきた。
【０００３】
例えば、本出願の図１は、カード支払い取引を有効化するための例示的な複数関係者による支払いカード産業システムを示している。図示されているように、加盟店と発行者とは、必ずしも１対１の関係を有している必要はない。さらに、今日のカード支払い産業においては、カード発行者が特定の加盟店、または加盟店グループと特別な、またはカスタマイズされた関係性を有する様々なシナリオが存在する。
【０００４】
２５００万件を超える加盟店が、支払いカードの形式を受け入れている。協会の１つは、何千件もの加盟店の名称および加盟店ロケーションの住所情報を本明細書ではデータウェアハウスと称するものに格納されている。加盟店ロケーションのレベルでは、このデータウェアハウスに何百万件ものエントリが存在する。ロケーションエントリのうちの多くは、取引データにおける名称および／または住所の情報の変動に起因して重複していることが知られている。例えば、同じ街路であっても住所が様々に表記される可能性があり、その全てが有効である（例えば、400 South Fourth Street、400 S.Fourth St.、400 South 4th Street、他）。名称もまた、時として幾つかの方式で表示される可能性があり、その全てが有効である。現在のデータベース技術では、類似するフィールド値を有する名称および住所等のエントリを識別する能力が極めて限定的である。従って、重複に近い加盟店の名称および加盟店ロケーションがデータウェアハウスに多く入力されている。
【０００５】
協会のある典型的な処理の一日において、データウェアハウス内に既に格納されている約５００万件のロケーションエントリに対して照合チェックを行う必要があるロケーション候補（例えば、新しい加盟店ロケーション）は約１５，０００件存在する。照合のためのチェックは、少なくとも２つの目的を果たす。その１つとして、類似の名称および／または住所を有するロケーションは、幾つかの実体ではなく１つの実体として識別され得る。さらに、名称または住所があまりに相違していれば、協会は、１つの実体が転居している、または１つの実体が営業を停止していて別の実体に取って代わられていると決定することができる。
【０００６】
この名称およびロケーションの照合問題は、第三者がデータウェアハウスを保持する協会に取引ファイルを、ひいてはデータウェアハウスの強化および／または認証に使用される加盟店の名称および住所（ロケーション）のリストを提供する幾つかの他のコンテキストにおいても生じる。別の第三者の例では、国内の大規模小売業者に関する全てのロケーションのリストが受信される場合もあれば、チェーン店の名称および住所のリストが受信される場合もある。データウェアハウスの保持を担っているチームは、受信されるリストを小売業者またはチェーンの既知のロケーションと照合するタスクを任される。
【０００７】
既存のロケーションと新しいロケーションとの照合をチェックする１つの方法は、文字列照合アルゴリズムを介するものである。従って、文字列照合に利用される可能性のあるソリューションは何れも、データベース（データウェアハウス）システムの枠組み内でスケーラブルであるはずである。近似文字列照合に対しては、第三者ソリューションが存在する。しかしながら、これらのソリューションには、典型的には、ソリューションが法外な費用がかかり、特有のドメインまたはツールであり、もしくはソリューションがデータベース（データウェアハウス）システムの外部に存在することを含むような１つまたはそれ以上の欠点を有している。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
従って、データベースシステム内でスケーラブルに加盟店レコードを照合するためにデータウェアハウスチームが名称および住所の近似照合を実行できるようにする技術を開発するという、これまでに未だ果たされていない目的が存在している。所望される結果は、例えば取引履歴データを利用して将来の金融カード取引を予測しかつデータから関連づけられるべきことが存在するかどうかを決定する他のダウンストリームアプリケーションをサポートすることのできる小型で正確なデータウェアハウスであろう。
【課題を解決するための手段】
【０００９】
ある態様においては、文字列候補とデータベース内に格納された複数の文字列レコードとの文字列照合を行うためのコンピュータベースの方法が提供される。本方法は、ａ）データベース内の参照文字列集合を識別するステップであって、前記参照文字列は異種文字列集合の最適化検索を使用して識別されるステップと、ｂ）前記参照文字列集合における参照文字列のうちの１つに関するｎグラム表現を生成するステップと、ｃ）前記文字列候補のｎグラム表現を生成するステップと、ｄ）これらのｎグラム表現間の類似性を決定するステップと、ｅ）前記識別された参照文字列集合における残りの参照文字列についてステップｂ）およびステップｄ）を反復するステップと、ｆ）前記文字列候補および前記識別された集合における参照文字列のｎグラム表現間の決定された前記類似性に基づいてデータベース内の文字列候補に指数を付けるステップと、を含む。
【００１０】
別の態様では、最適化探索を使用してデータベース内の異種参照文字列集合を識別し、文字列候補のｎグラム表現を生成し、前記集合内の異種参照文字列の各々についてｎグラム表現を生成し、前記文字列候補のｎグラム表現と前記異種参照文字列集合の各ｎグラム表現との間の類似性を決定し、かつ前記両ｎグラム表現において前記決定された類似性に基づいてデータベース内の文字列候補に指数をつけるようにプログラムされたコンピュータが提供される。
【００１１】
さらに別の態様では、文字列候補をデータベース内の参照文字列集合と近似照合させるための、コンピュータベースの方法が提供される。本方法は、文字列候補のｎグラム表現と参照文字列集合における各参照文字列のｎグラム表現とを個々に比較することと、前記文字列候補に関連づけられる２進指数値を生成することとを含み、前記２進指数値は文字列候補と参照文字列の各々との間の類似性を示す。
【図面の簡単な説明】
【００１２】
【図１】日常的なカード支払い取引を有効化するための例示的な複数関係者による支払いカード産業システムを示す略図である。
【図２】本発明の一実施形態によるシステムのサーバアーキテクチャの例示的な一実施形態を示す単純化したブロック図である。
【図３】本発明の一実施形態によるシステムのサーバアーキテクチャの例示的な一実施形態を示す拡大ブロック図である。
【図４】加盟店集合体予測システムのためのハイレベルコンポーネントを示すフローチャートである。
【図５】前記加盟店集合体予測システムに関連づけられるスコアリングエンジンのオペレーションを示すフローチャートである。
【図６】加盟店ロケーションを分類するアルゴリズムに入力されるデータを示すフローチャート２５０である。
【図７】加盟店ロケーションを分類するアルゴリズムを記述するフローチャートである。
【図８】加盟店の集合体および集合を分類システムにおける文書として示す線図である。
【図９】データベース内の参照文字列または主要コンポーネントの集合の決定を示すフローチャートである。
【図１０】文字列候補の類似性メトリックを決定するための参照文字列の集合の使用を示すフローチャートである。
【発明を実施するための形態】
【００１３】
本明細書に記述する実施形態は、データベース内で近似列（例えば、文字列）照合を検索し、一方ではデータベース全体で類似性メトリックを計算する必要のない効率的な方法に関する。例えばコンテンツが若干変わる受信されたロケーションデータの近似文字列照合では、ロケーションの一致を決定することができる。この効率性は、照合されているフィールドの文字列のスペースを網羅する参照文字列の集合に対する各文字列の相対位置（一致の度合い）を捕捉する２進指数を生成することによって達成される。金融取引カードシステムの運用に関連づけられる加盟店の名称およびロケーションのコンテキストで説明しているが、近似文字列照合技術は文字列照合ではなく加盟店の名称および住所情報の情報検索等のより一般的なタスクに適用可能である点に留意することが重要である。一例は、文書照合のための技術をコンピュータシステム内で利用することである。
【００１４】
本明細書に記述しているシステムおよびプロセスの技術的効果は、下記、即ち（ａ）データベースシステム内で加盟店レコードをスケーラブルに照合するために、名称および住所の近似照合を実行する技術、（ｂ）複数の参照文字列の各々に対する文字列候補の類似性メトリックの決定を行なうこと、（ｃ）照合されているフィールドに関してデータベース内の文字列のスペースを網羅する参照文字列集合に対する各文字列候補の相対位置を捕捉する２進指数を生成すること、および（ｄ）文字列候補と複数の文字列レコードを含むデータベースとの間の近似文字列照合を、レコードのデータベース全体の類似性メトリックを計算する必要なしに検索すること、のうちの少なくとも１つを含む。
【００１５】
ある実施形態では、あるコンピュータプログラムが提供され、前記プログラムはコンピュータ読取り可能媒体上に具現され、かつ管理のためのクライアントユーザインタフェース・フロントエンドおよび一般ユーザの入力およびレポートのためのウェブインタフェースを有する構造化問合せ言語（ＳＱＬ）を使用する。ある例示的な実施形態では、このシステムはウェブ対応であって、企業体のイントラネット上で実行される。さらに別の実施形態では、このシステムは、認証されたアクセスを有する個人によって企業体のファイアウォールの外側でインターネットを介して十分にアクセスされる。さらなる例示的な実施形態では、このシステムはWindows（登録商標）環境（Windowsは、ワシントン州レドモンド所在のMicrosoft社の登録商標である）において実行されている。このアプリケーションはフレキシブルであり、かつ主要な機能性を危うくすることなく様々な異なる環境で実行されるように設計される。
【００１６】
これらのシステムおよびプロセスは、本明細書に記述される特有の実施形態に限定されない。さらに、各システムおよび各プロセスのコンポーネントは、本明細書に記述されている他のコンポーネントおよびプロセスとは独立して別個に実施され得る。また各コンポーネントおよびプロセスは、他のアッセンブリパッケージおよびプロセスと組み合わせて使用され得る。
【００１７】
背景として、図１は、取引履歴が少なくとも部分的に加盟店集合体予測システムによって利用される日常的なカード支払い取引を有効化するための例示的な複数関係者による支払いカード産業システムを示すダイアグラム２０である。本明細書において使用しているように、加盟店集合体とは、加盟店ロケーションのハイレベルなグルーピングを指す。より具体的には、１件の小売業者に関する様々な個々の加盟店ロケーションが集められて（例えば、データベース内で互いにリンクされて）１つの加盟店集合体が形成される。従って、１つの加盟店ロケーションは、１つの加盟店集合体の１つのコンポーネントである。典型的には、加盟店集合体はストアチェーンを指す場合に使用され、ロケーションは、本明細書において詳述するように、取引データのデータベースに格納されている幾つかのフィールド値に基づいて集合化される。
【００１８】
本発明は、ＭａｓｔｅｒＣａｒｄ（登録商標）インターチェンジを使用するクレジットカードの支払いシステム等の支払いカードシステムに関する。ＭａｓｔｅｒＣａｒｄ（登録商標）インターチェンジは、ＭａｓｔｅｒＣａｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ社によって普及されている、ＭａｓｔｅｒＣａｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｉｎｃｏｒｐｏｒａｔｅｄ（登録商標）の会員である金融機関間で金融取引データを交換するための独自仕様の通信標準である。（ＭａｓｔｅｒＣａｒｄは、ニューヨーク州パーチェス所在のＭａｓｔｅｒＣａｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ社の登録商標である。）
【００１９】
ある典型的な支払いカードシステムでは、「発行者」と呼ばれる金融機関が消費者にクレジットカード等の支払いカードを発行し、消費者はこの支払いカードを使用して加盟店からの購入に対する支払いを申し出る。支払いカードによる支払いを受け入れるためには、加盟店は通常、金融支払いシステムの一部である金融機関と契約を結ばなければならない。この金融機関は一般に、「加盟店銀行」または「アクワイアリングバンク」または「アクワイアラバンク」と呼ばれる。消費者２２が支払いカード（金融取引カードとしても知られる）による購入の支払いを申し出ると、加盟店２４は購入高に関して加盟店銀行２６から認証を要求する。この要求は電話によって実行される場合もあるが、通常は販売時点端末の使用を介して実行される。販売時点端末は、支払いカード上の磁気ストライプから消費者の口座情報を読み取って加盟店銀行の取引処理コンピュータと電子的に通信する。或いは、加盟店銀行は第三者が取引処理を代行することを認可する場合もある。この場合、販売時点端末はこの第三者と通信するように構成される。このような第三者は通常、「加盟店プロセッサ」または「アクワイアリングプロセッサ」と呼ばれる。
【００２０】
インターチェンジ２８を使用して、加盟店銀行または加盟店プロセッサのコンピュータはカード発行者銀行３０のコンピュータと通信し、その消費者の口座が堅実な状態にあるかどうか、およびその購入がその消費者の利用可能な信用限度額の範囲内であるかどうかを決定する。これらの決定に基づいて、認証要求は謝絶または受容される。要求が受容されれば、加盟店に認証コードが発行される。
【００２１】
認証要求が受け入れられると、消費者の口座３２の利用可能信用限度額が下げられる。通常、ＭａｓｔｅｒＣａｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｉｎｃｏｒｐｏｒａｔｅｄ（登録商標）等の銀行カード協会は、商品が出荷されるまで、またはサービスが届けられるまで加盟店に取引をチャージまたは「獲得」させないという規則を普及させていることに起因して、課金は消費者口座へ即時的には計上されない。加盟店が商品を出荷する、またはサービスを届けると、加盟店は、例えば販売時点端末上への適切なデータ入力処置によってその取引を獲得する。取引が獲得される前に消費者が取引をキャンセルすれば、「無効」が発生する。取引が獲得された後に消費者が商品を返品すれば、「クレジット」が発生する。
【００２２】
取引が獲得された後、この取引は、加盟店と、加盟店銀行と、発行者との間で決済される。決済とは、その取引に関連づけられる加盟店の口座と、加盟店銀行と発行者との間の金融データまたは資金の転送を指す。通常、取引は獲得されて「バッチ」に累積され、バッチはグループとして決済される。このような取引に関連づけられるデータは、本明細書において詳述するように、将来の購入活動を予測する分野において利用される。
【００２３】
金融取引カードまたは支払いカードは、クレジットカード、デビットカードおよびプリペイドカードを指す可能性がある。これらのカードは全て、取引を実行するための支払い方法として使用され得る。本明細書に記述しているように、「金融取引カード」または「支払いカード」という言い回しはクレジットカード、デビットカードおよびプリペイドカード等のカードを含むが、支払い勘定情報を保持している場合がある移動電話、パーソナルデジタルアシスタント（ＰＤＡ）およびキーフォブ等の他の任意のデバイスも含む。
【００２４】
図２は、本発明の一実施形態による例示的なシステム１００を示す単純化されたブロック図である。ある実施形態において、システム１００は、例えばカスタマイズされた発行者−加盟店の関係性を実装すると同時に取引に関連づけられる履歴データの処理を実行するために使用される支払いカードシステムである。別の実施形態において、システム１００は、支払い取引に適用されるべき処理コードを入力するために口座保持者によって利用されることが可能な支払いカードシステムである。
【００２５】
より具体的には、この例示的な実施形態において、システム１００はサーバシステム１１２と、サーバシステム１１２へ接続されるクライアントシステム１１４とも称される複数のクライアントサブシステムとを含む。ある実施形態では、クライアントシステム１１４はウェブブラウザを含むコンピュータであり、よってサーバシステム１１２はインターネットを使用してクライアントシステム１１４へアクセス可能である。クライアントシステム１１４は、ローカルエリアネットワーク（ＬＡＮ）または広域ネットワーク（ＷＡＮ）等のネットワーク、ダイアルイン接続、ケーブルモデムおよび専用高速ＩＳＤＮ回線を含む多くのインタフェースを介してインターネットへ相互接続される。クライアントシステム１１４は、ウェブベース電話、パーソナルデジタルアシスタント（ＰＤＡ）または他のウェブベースの接続可能機器を含むインターネットへ相互接続することができる任意のデバイスであり得る。データベースサーバ１１６は、後に詳述するように、様々な事柄に関する情報を含むデータベース１２０へ接続される。ある実施形態では、サーバシステム１１２上に集中データベース１２０が格納され、クライアントシステム１１４の１つにおける潜在的ユーザはクライアントシステム１１４のうちの１つを介してサーバシステム１１２へログオンすることにより、集中データベース１２０へアクセスすることができる。ある代替実施形態では、データベース１２０はサーバシステム１１２から遠隔に格納され、かつ非集中式であってもよい。
【００２６】
後に論じるように、データベース１２０は、銀行カードネットワーク上で実行される販売行動の一部として生成される、加盟店、口座名義人または顧客および購入に関するデータを含む取引データを格納する。データベース１２０はさらに、報酬プログラムおよび特典に関する、異なる報酬プログラムおよび特典に関連づけられる処理コードおよび業務規定を含むデータも含む。
【００２７】
図３は、本発明の一実施形態によるシステム１２２のサーバアーキテクチャを示す例示的な実施形態の拡大ブロック図である。（図２に示す）システム１００のコンピュータに等しいシステム１２２におけるコンポーネントは、図３では、図２で使用している同じ参照数字を使用して識別されている。システム１２２は、サーバシステム１１２と、クライアントシステム１１４とを含む。サーバシステム１１２はさらに、データベースサーバ１１６と、アプリケーションサーバ１２４と、ウェブサーバ１２６と、ファックスサーバ１２８と、ディレクトリサーバ１３０と、メールサーバ１３２とを含む。データベースサーバ１１６およびディレクトリサーバ１３０へは、ディスク記憶ユニット１３４が結合される。サーバ１１６、１２４、１２６、１２８、１３０および１３２は、ローカルエリアネットワーク（ＬＡＮ）１３６内で結合されている。さらに、ＬＡＮ１３６へは、システム監督者のワークステーション１３８、ユーザのワークステーション１４０および監督者のワークステーション１４２も結合される。或いは、ワークステーション１３８、１４０および１４２はインターネットリンクを使用してＬＡＮ１３６へ結合され、またはイントラネットを介して接続される。
【００２８】
各ワークステーション１３８、１４０および１４２は、ウェブブラウザを有するパーソナルコンピュータである。これらのワークステーションにおいて実行される機能は、典型的には個々のワークステーション１３８、１４０および１４２において実行されるものとして示されるが、このような機能は、ＬＡＮ１３６へ結合される多くのパーソナルコンピュータのうちの１つにおいて実行され得る。ワークステーション１３８、１４０および１４２は、単にＬＡＮ１３６へのアクセスを有する個人により実行され得る異なるタイプの機能の理解を促進する目的で、別々の機能に関連づけられるものとして示されているに過ぎない。
【００２９】
サーバシステム１１２は、ＩＳＰインターネット接続１４８を使用して従業員を含む様々な個人１４４へ、かつ例えば口座名義人、顧客、監査人、他である第三者１４６へ通信可能式に結合されるように構成される。この例示的な実施形態における通信はインターネットを使用して実行されるように示されているが、他の実施形態では、他の任意の広域ネットワーク（ＷＡＮ）型通信を利用することができる。即ち、これらのシステムおよびプロセスは、インターネットを使用する実施に限定されない。さらに、かつＷＡＮ１５０ではなく、ローカルエリアネットワーク１３６がＷＡＮ１５０の代わりに使用される可能性もある。
【００３０】
この例示的な実施形態では、ワークステーション１５４を有する任意の認証された個人がシステム１２２にアクセスすることができる。クライアントシステムのうちの少なくとも１つは、リモートロケーションに位置づけられるマネージャワークステーション１５６を含む。ワークステーション１５４および１５６は、ウェブブラウザを有するパーソナルコンピュータである。また、ワークステーション１５４および１５６は、サーバシステム１１２と通信するように構成される。さらに、ファックスサーバ１２８は、電話回線を使用してクライアントシステム１５６を含む遠隔に位置づけられたクライアントシステムと通信する。ファックスサーバ１２８は、他のクライアントシステム１３８、１４０および１４２とも通信するように構成される。
【００３１】
図４は、各コンポーネントが金融取引カードネットワークのオペレーションに関する予測を提供する集団的または集合的な加盟店予測システムの一実施形態のハイレベル機能コンポーネントを示すフローチャート２００である。従って、さらに述べるように、これらの予測は１つの予測へと集合される。この予測の集合化は、アンサンブル予測と称されることがある。本明細書に記述しているこれらの実施形態に関する一例は、受信された加盟店ロケーションデータに関する集合予測を含む。図４に関連して紹介しているが、本明細書では、全ての予測アルゴリズムについてより詳細に説明する。
【００３２】
第１のコンポーネントは類似ロケーション予測アルゴリズム２０２（ｋ類似ロケーション予測アルゴリズムと称される場合がある）であり、これは、所定の加盟店ロケーションに最も類似する「ｋ」件の加盟店ロケーションを検索するように構成される。予測アルゴリズム２０２はさらに、検索された「ｋ」件の最も類似するロケーションの中から類似する加盟店ロケーションの１グループをモードグループとして分類するように動作可能である。
【００３３】
文書予測アルゴリズムとしての集合ロケーション２０４は、あらゆるフィールドと、既知の値のスペースにおけるロケーションの各集合体（ハイレベルのデータ分類）に関するフィールド値との関連性を計算するために利用され、結果は文書として格納される。これらの文書からの最も関連のある値は、予測を生成するために利用される。
【００３４】
予測が特定の第三者ブランドに関連づけられる場合には、ロケーション照合システムを含む第三者データ予測アルゴリズム２０６が利用される。アルゴリズム２０６への少なくとも１つの入力は第三者から受信される取引レコードを含み、これが予測の生成に利用される。ある実施形態では、この予測は、第三者データソースとのロケーション照合が実行された後に生成される。フローチャート２００には、その一実施形態が主としてベンフォードの法則に基づき、かつさらには同一のグルーピングに属する加盟店について観察される、Ｂｅｎｆｏｒｄにより識別される分布から比較的一貫した方法で拡散する傾向に基づく数値サイン予測アルゴリズム２０８が含まれる。アルゴリズム２０８から結果的に生じる予測は、各加盟店ロケーションに比較して最も類似する数値分布を有するロケーショングループになる。
【００３５】
ある実施形態において、オラクル（Ｏｒａｃｌｅ）に実装されるトップレベル統計モデルおよびスコアリングエンジン２１０は、アルゴリズム２０２、２０４、２０６および２０８からの予測を利用して、データベース内に新しく受信および／または格納されるデータ間のグループメンバーシップを決定する。このデータの一例は、加盟店ロケーションデータである。少なくとも１つの実施形態では、かつ本明細書でさらに述べるように、データベース内の加盟店ロケーションデータはロケーションおよび距離に関して、例えば所定のロケーションから所定の距離内にある幾つかの加盟店ロケーションに関して記述される。少なくとも１つの態様において、ロケーションおよび距離は必ずしも地理的なものではなく、むしろデータベースに格納されている加盟店データを利用して計算されるような類似性に基づいている。特定の実施形態では、ロケーションおよび距離は、データベース内のフィールド値およびフィールドのトークン化された値に関するクロス属性加重式ターム出現頻度／文書出現頻度逆数（ＴＦ／ＩＤＦ）の計算によって測定されるような類似性に基づいている。
【００３６】
図５は、スコアリングエンジン２１０のオペレーションを示すフローチャート２２０である。具体的には、スコアリングエンジン２１０は、２２２において、アルゴリズム２０２、２０４、２０６および２０８からの加盟店ロケーション予測をオラクルデータマイニング（ＯＤＭ）アプリケーション２２４における予測に関するメタデータと共に使用し、個々の予測を取り囲む状況を記述し、次いで２２６において、集合化された個々の予測から最終予測を生成する。この最終予測は、加盟店ロケーションに関するものであってもよい。またこのアプリケーションは、複数のアルゴリズム２０２、２０４、２０６および２０８に関する集合予測に関連づけられる信頼スコアの生成も行う。
【００３７】
次に、４つのアルゴリズム２０２、２０４、２０６および２０８の各々についてさらに詳しく説明する。
【００３８】
ｋ件の類似ロケーション（アルゴリズム２０２）
【００３９】
図６は、類似性に基づいて、例えばロケーションの類似性に基づいて加盟店ロケーションを分類するアルゴリズム２０２へ入力されるデータを示すフローチャート２５０である。チェーンまたはコレクション（例えば、グループ）メンバーシップを導出するコンテキストにおいて有意義であることが知られるロケーションレベルフィールドの集合またはロケーション座標２５２は、金融取引カードを引き受ける機関のデータベース２５４から識別される。さらに、日常的な新規／変更ロケーションデータベース２５６並びにその関連の新規／変更ロケーション座標２５８からのデータは、後述する加盟店ロケーション分類アルゴリズムへ供給される。
【００４０】
図７は、加盟店ロケーションをグループメンバーシップに分類するために利用されるアルゴリズムのうちの１つ（図４に示すアルゴリズム２０２）を記述するフローチャート２８０である。アルゴリズム２０２は、少なくとも図６のフローチャート２５０に関して記述されているデータを利用する。具体的には、２８２において、データベース内の加盟店ロケーションデータが、所定のロケーションから所定の距離内にある幾つか（ｋ件）のロケーションについて検索される。さらに、２８４において、所定の距離内にあるロケーションが類似性について検索され、任意の新規／変更ロケーションが決定される。２８６では、特定の特徴スペース（取引データをアルゴリズム２０２へ入力する起点エリア）内の前記（ｋ件の）ロケーション間で発生する加盟店ロケーションを分類することによって、モード値が決定される。（ｋ件の）ロケーション記録の分類によって結果的に得られる最も出現頻度の高い値は最高の重みを有し、かつモード値と称され、後述するように決定される。このモード値は、２８８においてアルゴリズム２０２から予測として返される。
【００４１】
後に詳しく述べるように、フィールド（ロケーション座標２５２および２５８）はトークン化され、特徴スペースを網羅するトークン化された全てのフィールド値に関して文書出現頻度の逆数が計算される。ある実施形態では、各ロケーションについて、各フィールド値およびトークン化された各フィールド値の重みメトリックの疎行列がターム出現頻度／文書出現頻度逆数として計算される。予測値は、１つまたはそれ以上のフィールドタイプおよびフィールド値に基づいて所定のロケーションフィールドを他のあらゆるロケーションフィールドに結合することによって計算される。
【００４２】
疎行列はロケーション、ターム値のフィールドタイプおよび重みおよびタームトークンを含み、下記の段落に記述するように生成される。
【００４３】
行列は、全てのフィールド値およびトークン化されたフィールド値の文書出現頻度逆数を含んで生成され、かつある実施形態では９個のディメンションを網羅する。ある特定の実施形態では、これらの９個のディメンションは、加盟店カテゴリコード、インターバンクカード協会（ＩＣＡ）コード、事業領域、加盟店名、加盟店電話番号、アクワイアリング加盟店ＩＤ、ティア加盟店ＩＤ、加盟店の正式名称および連邦税ＩＤを含む。これらのディメンションは、全ての加盟店ロケーションレコードに包含される。文書出現頻度の逆数は、レコード数を特定の値を含むレコードの数で除算した商の（ある特定の実施形態では２を底とする）対数である。一例を表１に示す。ある実施形態において、この商は、９個のディメンションの各々について別々に計算される。レコードの数は、加盟店ロケーションの数として計算される。特定のタームを含むレコードの数は、各フィールドタイプ内に各タームを含む加盟店ロケーションの数を計数することによって計算される。
【００４４】
【表１】
【００４５】
各ロケーション毎に、表２に示すような、クロス属性正規化ターム出現頻度−文書出現頻度二重逆数重みが９個のディメンションを網羅する値およびトークン化された値について計算される。この場合も、９個のディメンションは加盟店カテゴリコード、ＩＣＡコード、事業領域、加盟店名、加盟店電話番号、アクワイアリング加盟店ＩＤ、ティア加盟店ＩＤ、加盟店の正式名称および連邦税ＩＤを含む。
【００４６】
【表２】
【００４７】
所定のロケーションに関するグループメンバーシップ予測および信頼度は、予測すべきロケーションをフィールドタイプおよびフィールド値上の他の全てのロケーションへ結合し、次いで共通するフィールドタイプおよびフィールド値に関してターム出現頻度−文書出現頻度二重／逆数重みの積を合計することによって計算される。ロケーション結果は次に結果スコアの降順にソートされ、最も高いスコアを有する例えば１３件のロケーション間で発生するモードグループが予測として与えられる。この予測の信頼スコアは、上位１３件のロケーションのうちで同一のグループ（予測された値）を含んでいたロケーションの数、予測されたグループに属するｋ件のロケーションの個々の重みおよびこれらの重み間の分散によって表される。
【００４８】
文書予測としての集合ロケーション（アルゴリズム２０４）
【００４９】
図８は、文書内の集合へ分類系として集合化されたロケーションを示すダイアグラム３００である。集合ロケーションの文書を生成するアルゴリズム２０４（図４に示す）は、インターネット検索エンジンによって一般に使用される文書関連性アルゴリズムに類似するものである。具体的には、加盟店ロケーションの各集合体またはコレクションに対する所定の加盟店ロケーションの関連性は、下記のようにして計算される。
【００５０】
文書３０２を生成するためには、例えば住所である関連特徴が複数のロケーション３０４に関するデータベースのデータから抽出されて集合に、例えば集合３０６にグルーピングされる。説明を目的として、ダイアグラム３００は、４つのロケーション集合３０６、３０８、３１０および３１２を含んでいる。集合３１２は集合Ｍとラベリングされているが、これは、特定の実施において、集合の数は図示されている４つより多い、または少ない場合があることを示す。同様に、１集合内のロケーションの数も１から「Ｎ」まで変わる可能性がある。
【００５１】
各々が抽出された関連する特徴を含む生成された文書３０２、３２０、３２２および３２４は、辞書３３０に集められる。辞書３３０を利用して疎行列３４０が形成され、これにより、抽出された特徴を使用して、各集合加盟店グループ毎にターム出現頻度および文書出現頻度逆数の少なくとも一方に基づいて、各フィールド値およびトークン化されたフィールド値の関連性が計算される。
【００５２】
疎行列３４０内では、ロケーションレベルの重みの行列が、フィールドタイプおよびフィールド値に基づいて加盟店グループの重みの行列に結合される。ある実施形態では、これらの重みの和が関連性エンジン３５０によって利用され、各ロケーションの各加盟店グループに対する関連性が決定される。関連性が最も高い加盟店グループは、先に述べた予測値として返される。より具体的には、グループ、フィールドタイプおよびタームルールおよびタームトークンの重みから成る疎行列は、次の段落で説明するようにして生成される。
【００５３】
まず、全ての加盟店ロケーションレコードに亘り、本明細書において別段で列挙した９個のディメンション、具体的には加盟店カテゴリコード、ＩＣＡコード、事業領域、加盟店名、加盟店電話番号、アクワイアリング加盟店ＩＤ、ティア加盟店ＩＤ、加盟店の正式名称および連邦税ＩＤを網羅する全てのフィールド値およびトークン化されたフィールド値の文書頻度の逆数を含む行列が生成される。
【００５４】
文書予測アルゴリズムとしての集合ロケーションに関して、かつ表３に示すように、文書頻度の逆数は、比率、即ち特定の値を含むレコードの数で除算されたレコードの数の対数（ある特定の実施形態では２を底とする）である。ある実施形態では、文書頻度の逆数は９個のディメンションの各々について別々に計算される。レコードの数は、加盟店ロケーションの数として計算される。特定のタームを含むレコードの数は、各フィールドタイプ内の各タームを含む加盟店ロケーションの数を計数することによって計算される。
【００５５】
【表３】
【００５６】
各グループ毎に、かつ各グループに属する全てのロケーション毎に、表４に示すように、加盟店カテゴリコード、ＩＣＡコード、事業領域、加盟店名、加盟店電話番号、アクワイアリング加盟店ＩＤ、ティア加盟店ＩＤ、加盟店の正式名称および連邦税ＩＤである９個のディメンションを網羅する値およびトークン化された値について、クロス属性正規化ターム出現頻度−文書頻度の二重逆数が計算される。
【００５７】
【表４】
【００５８】
所定のロケーションに関する１つのグループメンバーシップ予測は、先に説明した（ｋ件の）類似ロケーション行列からの行をフィールドタイプおよびフィールド値上のグループ行列に結合し、次いで共通のフィールドタイプおよびフィールド値のターム出現頻度−文書頻度の二重逆数の重みの積を合計することによって計算される。予測されるグループおよび信頼スコアは、最も高い類似性スコア（一致するフィールド値およびトークン化された値の重みの積の和によって与えられる）を有するグループである。結果的に生じるスコアは、この予測の信頼性である。
【００５９】
第三者データ予測とロケーション照合（アルゴリズム２０６）
【００６０】
アンサンブル予測の第３のコンポーネントは、加盟店ロケーションによって金融取引のデータベースに照合されたことのある第三者提供データを使用するアルゴリズム２０６（図４に示す）である。ある実施形態では、これらの第三者レコードに、例えば売り手に関するチェーンＩＤが割り当てられる。これらのチェーンＩＤは、金融取引カードブランド（例えば、カード発行者）に関連づけられる加盟店ロケーションのグループにリンクされる。従って、予測は単に、第三者レコードがリンクされているチェーンに対応する加盟店データのグルーピングになる。このリンク付けは、次の段落で説明するようにロケーション照合に続いて発生する。
【００６１】
ロケーションが（売り手によって）チェーンへ割り当てられている場合、加盟店ロケーションのデータセットは第三者データプロバイダから抽出される。第三者加盟店ロケーションのスペース内の各チェーンは、対応する適切なグループへ割り当てられる。近似加盟店ロケーション照合エンジンは、第三者加盟店ロケーションレコードの集合をカード発行者により保持される加盟店ロケーションレコードの集合へ結合するために使用される。次に、所定のロケーションに関する予測グループが、カード発行者の加盟店ロケーションレコードに一致した第三者ロケーションレコードに対応するチェーンに相当するグループとして計算される。信頼スコアは、近似加盟店ロケーション照合エンジンによって割り当てられる照合信頼スコアである。
【００６２】
数値サイン予測（アルゴリズム２０８）
【００６３】
ある実施形態において、加盟店数値サインアルゴリズム２０８（図４に示す）は、第１の位置における一日当たりの取引額および取引量の数表示分布に関する観察を使用する。具体的に言えば、この分布は、様々な加盟店データが集合される際には幾分か一意になる傾向がある。さらに、この分布は、自然データにおいてベンフォードの法則が提案する分布に合致している傾向がある。実世界の例では、ファーストフードレストランのチェーンは、取引額の最初の数字として特定の数字を繰返し現出させる傾向を示すことがある。このような傾向は少なくとも部分的に、例えば、ファーストフードレストランチェーンのフランチャイズ加盟店がある特定のロケーションまたは住所に存在することを確認するために利用され得る。
【００６４】
このようなアルゴリズムを利用する予測の一例は、各加盟店集合（加盟店データのグルーピング）からの加盟店ロケーションのランダムな１０パーセントサンプルである。加盟店集合毎に、第１の位置の取引額および取引量において発生する数字１−９の分布が計算されかつ集約され、この分布と、ベンフォードの法則により識別される分布との間の角距離が計算される。
【００６５】
次には、所定の加盟店ロケーションについて、第１の位置の取引額および取引量において発生する数字１−９の分布が計算され、この分布と、ベンフォードの法則により識別される分布との間の角距離が計算される。加盟店ロケーションの角距離に最も近い角距離を有する加盟店集合は、その所定のロケーションの加盟店集合予測として与えられる。
【００６６】
より具体的には、かつ各グループ毎に、取引計数、取引額および平均取引額の間における、グループ内の全てのロケーションを網羅する各数字（即ち、１、２、３、４、５、６、７、８、９）の出現頻度の分布が計算され、全体に対する比率として表される。前記分布は次に、表に格納される。表５は、これを表したものである。
【００６７】
【表５】
【００６８】
各グループに関する分布が計算されると、各グループに関する数値サインが、このグループの分布ベクトルとベンフォードの法則が提案する分布ベクトルとのドット積を計算することによって決定される。このドット積（発散角度）は、各グループの分布ベクトルの平方和によって除算される。ベンフォードの法則において識別される分布が計算され、表に格納される。表６は、これを表したものである。
【００６９】
【表６】
【００７０】
各ロケーション毎に、所定のロケーションに関して１か月の期間内に観察された取引計数、取引額および平均取引額を網羅する各数字（１、２、３、４、５、６、７、８、９）の出現頻度の分布が計算され、全体に対する比率として表される。これらの分布は次に表に格納され、表７はこれを表す。
【００７１】
【表７】
【００７２】
各ロケーションに関する分布が計算されると、各ロケーションに関する数値サインが、このロケーションの分布ベクトルとベンフォードの法則が提案する分布ベクトルとのドット積を計算することによって決定される。このドット積（発散角度）は、各ロケーションの分布ベクトルの平方和によって除算され、かつベンフォードの法則において識別される分布が計算され、表に格納される。表８は、これを表したものである。
【００７３】
【表８】
【００７４】
次に、所定のロケーションに関するグループメンバーシップ予測が、この所定のロケーションの数値サインに最も近い数値サインを有するグループを見つけることによって計算され、信頼スコアがこれらの２サイン間の距離として計算される。
【００７５】
統計モデルとスコアリング
【００７６】
図５に関連して先に述べたように、４つの予測アルゴリズム（２０２、２０４、２０６および２０８）からの各予測値は、２２２において、各予測の環境を記述する豊富なメタデータ集合と共に集められ、Ｏｒａｃｌｅデータマイニング（ＯＤＭ）アプリケーション２２４へ入力される。ＯＤＭアプリケーション２２４は、ある実施形態では、ラベリングされたトレーニングデータを使用して構築される統計モデル（決定木）を利用して各予測値へ信頼スコアを割り当てる。次には、最も高い信頼スコアを有する予測値が各加盟店ロケーションの最終的な集合値予測として提供される。
【００７７】
近似文字列照合
【００７８】
先に述べたように、アンサンブル予測の１つのコンポーネントは、例えば金融取引カード提携加盟店ロケーションのデータベースへ照合されているロケーションデータを使用するアルゴリズムである。幾つかのデータは、第三者ソースによって提供されてもよい。後述の実施形態は、データベース内のデータについて近似列（例えば、文字列）照合を検索するための方法およびシステムに関する。この実施形態では、文字列照合を利用して、例えばあるロケーションを表す文字列がそのデータベースにおいて別の文字列によって表されているかどうかが決定される。このようなアルゴリズムは、取引レコードにおいて発生する変形に起因して、特にこれらのレコードは加盟店の名称およびロケーションに関連することから、様々な実施形態において適切である。
【００７９】
近似文字列照合のデータベースシステムは、正確に一致する、または共通のフィールド値等の共通の結合キーがデータ内に存在しない場合に、１つのレコード集合を別のレコード集合へ結合するように動作可能である。おそらくは、これらのレコード集合には幾分かの類似性が存在する。
【００８０】
典型的には、２つのデータセットが１つのデータベース内で結合されると、これらは１つまたは複数のフィールドで正確な値を共有する。データ内の変形に起因して２つのデータソース（レコード集合）によって正確なフィールド値が共有されない場合、個々のデータソースからのデータセットを結合する伝統的な方法は、２つの値を取って、そこでその類似性を計算してリターンするという機能を実装することである。データセットを結合する基準として、このタイプの機能の使用することは、結合されるべき各データセット内のレコードの数の積に等しい反復回数を必要とする。
【００８１】
一例として、データセットＡ内に１０，０００件のレコードが存在しかつデータセットＢ内に５００，０００件のレコードが存在すれば、類似性計算機能はデータセットＡをデータセットＢへ結合するために５０億回呼び出されることになる。さらに、このような機能が呼び出される場合、指数または機能ベース指数はデータベースオプティマイザによって使用されなくなる。このタイプのデータセットは非常に非効率的であって、自明でないデータ量を有するデータセットの結合に使用するにはあまりに処理が集約的に過ぎる。
【００８２】
文字列照合技術は、様々な実施形態において下記のコンポーネントのうちの１つまたはそれ以上を利用して実装されるものが開発されている。具体的には、主成分因子分析（ＰＣＦＡ）を使用して生成される結合基準において参照文字列集合が使用される。ＰＣＦＡは、既知の値のスペース内に存在する極めて異種である文字列集合を識別しようとするものであり、前記文字列集合は参照文字列として使用される。
【００８３】
別のコンポーネントは、リレーショナルデータベース管理システム（ＲＤＢＭＳ）におけるパフォーマンスを最大化するために純粋なＡＳＣＩＩ構造化問合せ言語（ＳＱＬ）に実装されるｎグラム頻度類似性計算である。さらに、ＲＤＢＭＳには、ｎグラム頻度類似性計算を使用して２進キーを形成するためのプロセスも実装される。２進キーは、後述するように、ＰＣＦＡにおいて識別された参照文字列の各々に対する所定のレコードの類似性を示す。
【００８４】
ある実施形態では、全てのｎグラムの文書頻度逆数（ＩＤＦ）を含むテーブルおよびクロス属性加重ターム出現頻度／文書頻度逆数（ＴＦ／ＩＤＦ）計算のＳＱＬ実装であるとして、ＲＤＢＭＳ内でデータ駆動標準化機能セットが実装される。
【００８５】
文字列照合技術の一実施形態は、同じ２進キー値を共有するレコードを結合し、次いで全ての一致するｎグラムのＴＦ／ＩＤＦの重みの積を合計することによってこれらを関連性毎にソートするパラメータ化された分析ＳＱＬクエリを含む。そのレコードが所定のしきい値より上でｉ番目の参照文字列に一致すれば、２進キーにおけるｉ番目のビットは論理１に設定される。
【００８６】
ＲＤＢＭＳ内では、結合により生じる各照合へ信頼スコアを割り当てるように、プロセスが実装され、同時に、データセットの結合において取り込まれるデータを格納するＲＤＢＭＳデータモデルも包含される。
【００８７】
データセット結合問題の１つのシンプルなものとしては、１つの名称（または住所）を、Ｏｒａｃｌｅテーブル等のデータベース内に含まれる名称（または住所）のより大きい集合に対して照合することである。このｎグラム照合の一例を表９に示す。
【００８８】
【表９】
【００８９】
データセット結合のソリューションに必要とされるエレメントは、文字列間の任意の類似性を測定するためのメトリックである。ｎグラムは単にｎ文字より成る一意の文字列であり、ｎグラム照合は、ｎグラム間の照合を決定するためのプロセスである。ｎが２に等しい事例では、表１における住所候補は下記の各２グラム、即ち「１０」、「００」、「０１」、「１４」、「４＜スペース＞」、「＜スペース＞Ｓ」、「Ｓ＜スペース＞」、「＜スペース＞Ｃ」、「Ｃｌ」、「ｌａ」、．．．、「Ｒｄ」から成る。
【００９０】
表１０は、ｎグラム照合アルゴリズムを要約したものである。これは、文字列候補（例えば、Ｃａｎｄｉｄａｔｅ＿ａｒｒａｙ）のｎグラム頻度ベクトルを決定することと、照合データベース候補（例えば、Ｃａｎｄｉｄａｔｅ＿Ｍａｔｃｈ＿Ａｒｒａｙ）における各エントリのｎグラム頻度ベクトルを決定することと、前記Ｃａｎｄｉｄａｔｅ＿ａｒｒａｙと前記Ｃａｎｄｉｄａｔｅ＿Ｍａｔｃｈ＿Ａｒｒａｙとの間の類似性の度合いを測定することと、特定のしきい値を超える照合候補を保持することを含む。例えば、「ＪｏＪｏ’ｓ Ｄｉｎｅｒ」は下表のようになる。
【００９１】
【表１０】
【００９２】
表１１、表１２および表１３は、ｎグラム照合メトリックの例である。「内積」はアレイのドット積であり、「大きさ」は平方和の平方根であり、「（角度の）余弦」は大きさの積で除算されたドット積であり、角度は大きさの積で除算されたドット積の逆余弦である。
【００９３】
【表１１】
【００９４】
【表１２】
【００９５】
【表１３】
【００９６】
参照文字列
【００９７】
上記表および記述は、文字列を量的に表現しかつこれらの間の類似性を測定する能力を示している。この時点で、各レコードの指数は、参照文字列の小集合に対するその相対位置に基づいて構築され得る。
【００９８】
参照文字列を選ぶことにより、参照文字列の各々に対する新しいレコードの相対位置を計算することができる。さらに、データベース内のあらゆるレコードは、参照文字列に対するその固有の予め計算された位置を有する。従って、新しいレコードとデータベース全体との間の完全な類似性メトリックを計算する必要なしに、同じ近接性で指数が付けられたレコードを検索することによって近似照合を見つけることができる。参照文字列を選択する１つの目的は、異種であるレコードを選ぶことであり、こうしてより良い見通しが得られる。次の段落では、参照文字列選択の１つの手法を概説する。
【００９９】
参照文字列は、指数付けされているデータベースから文字列のサンプルをとることによって識別される。サンプル内の各文字列のｎグラム表現は、頻度のベクトルを生成することによって生成される。但し、ベクトルのｉ番目の成分は、その文字列においてｎグラムが発生した回数を含む。類似性行列は、余弦類似性メトリックを使用してあらゆるサンプル文字列ペア間の類似性を測定することにより生成される。
【０１００】
類似性データのコレクションにおいて異種成分を見つけるための１つの技術が、主成分分析である。主成分分析は類似性行列に対して実行され、最初のｋ個の主成分が保持される。各成分上の最大負荷を有するサンプル文字列が保持され、参照文字列集合が形成される。
【０１０１】
２進指数および情報検索
【０１０２】
指数を生成できるように類似する文字列をグループに纏め、近似文字列照合の間に高速検索候補を提供するために、潜在的な各レコード候補および各比較レコードがｎグラム頻度類似性ＳＱＬ計算を使用して参照文字列の各々と比較される。
【０１０３】
類似性計算が予め定義されたしきい値より高いスコアを産生すれば、参照文字列に対応する２進キーの位置に値１が割り当てられる。スコアがしきい値より低ければ、対応するキー位置に０が割り当てられる。
【０１０４】
ＮＧＲＡＭ類似性計算
【０１０５】
所定の２つの文字列内に存在する全ての一意のＮ−ＧＲＡＭＳの出現頻度を含む二次元ベクトルを形成するＳＱＬクエリが開発されている。このクエリは、次に、各頻度積の合計を頻度ベクトルの各ディメンションの大きさの平方で割って、正規化された類似性メトリックに到達する。
【０１０６】
このような計算は、次の例、即ち比較文字列Ａが「ＭＡＳＴＥＲＣＡＲＤ」であり、かつ比較文字列Ｂが「ＭＡＳＴＥＲＣＨＡＲＧＥ」である例によって表される。下表、表１４は、２つの比較文字列内に存在するあらゆる一意のｎグラムの出現頻度を含む二次元ベクトルである。
【０１０７】
【表１４】
【０１０８】
文字列Ａの大きさは、ディメンションＡにおける各頻度値の平方和の平方根として計算され、具体的には、文字列Ａの大きさは３．０である。文字列Ｂの大きさは、ディメンションＢにおける各頻度値の平方和の平方根として計算され、具体的には、大きさＢは３．３１６６２４７９０３５５４である。ベクトルのドット積が計算され、この例の場合、ドット積は７．０（ＡおよびＢの双方が値１を有する表エントリの数）である。類似性はドット積／（大きさＡｘ大きさＢ）として、即ちこの例示的な例では０．７０３５２６４７０６８１４４８として計算される。
【０１０９】
２進キー値の形成
【０１１０】
類似性計算が予め定義されたしきい値より高いスコアを産生すれば、参照文字列に対応する２進キーの位置に値１が割り当てられる。スコアがしきい値より低ければ、対応するキー位置に０が割り当てられる。ある実施形態において、２進キー位置を決定するためのプロセスは、ＳＱＬおよびＰＬ／ＳＱＬの組合せを使用して実装される。このアルゴリズムの実装は、アルゴリズム内の以前の反復においてその正確な値に関する２進キー値が計算されていれば所定の文字列に２進キー値を自動的に割り当てるように、分析的構造化問合せ言語を使用することにより、必要とされる文字列比較計算の数を最小化する。この最適化は、ＳＱＬで達成される。
【０１１１】
一意の識別子および各２進キー値は、ＲＤＢＭＳ内の仕切られた索引構成表（ＩＯＴ）に格納される。一意のデータセットは各々単一のパーティション内に格納され、２つのデータセットが同じパーティションを共有することはない。ロードパフォーマンスを最大化するために、この表への各データセットのロードは、ｃｒｅａｔｅ ｔａｂｌｅ ａｓ ｓｅｌｅｃｔ（ＣＴＡＳ）およびパーティション交換を使用して達成される。各パーティション内のデータは、結合パフォーマンスを最大化するために２進キー値順に格納される。
【０１１２】
データの標準化
【０１１３】
類似性比較および２進キー値分布の精度を高めるために、ある実施形態では、データが既知の略語および同義語について標準化される。このようなデータ標準化を達成するために、様々なフィールドタイプに関して全ての既知の変形および同義語をその個々の標準表現と共に含むテーブルが生成される。次に、アルゴリズムは各データエレメントをトークン化しかつ任意の既知の変形または同義語をその標準形式にマップするように作動する。
【０１１４】
ＩＤＦテーブル
【０１１５】
近似照合結合に関与するフィールド内に存在する全てのｎグラムについて加重ＴＦ／ＩＤＦを計算する際のパフォーマンスをより高速にするために、レコード候補のスペース内に存在する全ての２文字ｎグラムの文書頻度逆数を含むテーブルが構築される。スペース内の全てのｎグラムの形成はＰＬ／ＳＱＬを介して達成されるが、ＩＤＦの計算はＡＳＣＩＩ ＳＱＬで行われる。ＩＤＦテーブルは、各データカテゴリの可能なｎグラムの各々についてＩＤＦ値を格納する。このテーブルは、結合パフォーマンスを最大化するために、データカテゴリおよびｎグラムに従って索引構成される。
【０１１６】
クロス属性加重ＴＦ／ＩＤＦ
【０１１７】
近似照合結合に関与するフィールド毎に、所定のレコード内に存在する２文字ｎグラムの各々へ重みまたは重大さを割り当てるために、各ｎグラム値についてクロス属性加重ターム出現頻度／文書頻度逆数ＴＦ／ＩＤＦ値が計算される。ｎグラムタームおよび所定の各レコードおよびフィールド内でのその個々の出現頻度は、入力としてＲＥＦ＿ＣＵＲＳＯＲをとるパイプライン表関数を使用して計算される。この計算は、伝統的な加重ＴＦ／ＩＤＦ計算とは僅かに異なり、各フィールド内の各ｎグラムについてＴＦ／ＩＤＦを計算した後に、各フィールド内の全てのｎグラムの重みを同じレコードの他のフィールド内に存在するｎグラムの全体の重みに従って上下に調整する。この技術により、各フィールド内の値の全体的な重大さに従った照合ｎグラムの相対的重みに対するレコードレベルの動的調整が生じる。
【０１１８】
先に述べたように、所定のデータセット内の各レコードの一意の識別子は、結合パフォーマンスを最大化するために、そのｎグラムタームおよび計算された重みスコアと共に仕切られた索引構成表（ＩＯＴ）に格納される。このテーブルは、一意の識別子、データカテゴリおよびｎグラムターム値に従って編成される。一意のデータセットは各々、テーブル内の別々のパーティション内に格納される。各パーティションは、ロードパフォーマンスを最大化するためにｃｒｅａｔｅ ｔａｂｌｅ ａｓ ｓｅｌｅｃｔおよびパーティション交換を使用してロードされる。
【０１１９】
結合クエリ
【０１２０】
２進キーおよびクロス属性ＴＦ／ＩＤＦ計算がＲＤＢＭＳへロードされると、分析的な結合クエリを使用して全ての照合レコード候補が検索され、かつ比較レコードに照らしたその関連性または照合品質に従ってソートされる。これは、まず一致する２進キー値を有するレコードを結合し、次に結果的に生じるレコード候補のｎグラム値を結合しかつこれらの重みの積の合計を計算することによって達成される。
【０１２１】
信頼スコアの割当て
【０１２２】
結合クエリの結果は、各入力およびレコード候補に対して超低レベル比較を実行し、次いで先に述べたＯｒａｃｌｅデータマイニングアプリケーションに使用するための統計モデルを使用して信頼スコアを割り当てるＲＤＢＭＳ内に実装された関数を介して送信される。
【０１２３】
近似文字列照合に関連づけられる上述のプロセスを、さらに図９および図１０に示す。図９および図１０は各々、参照文字列集合の決定を示し、かつ文字列候補の類似性メトリックを決定するための参照文字列集合の利用を示すフローチャート４００および４５０である。各成分上の最大ローディングを有するサンプル文字列は、参照文字列集合を形成するために保持される。これらのサンプル文字列は、相関目的で主成分を表している。類似性メトリックは、文字列候補と決定された参照文字列集合内の個々の文字列との比較における幾つかの一致するｎグラムに基づいている。
【０１２４】
具体的には、かつ図９を参照すると、データベースは潜在的照合候補データのスペース４０２を含む。このスペース４０２は、本明細書において文字列のデータベース（即ち、加盟店の名称および／またはロケーションデータ）と称することがある。本明細書で記述しているように、４０４において、照合フィールドまたはデータベースレコードのランダムなサンプルが、例えば異種文字列集合の最適化探索に基づいて生成される。４０６において、類似性行列が計算され、かつ４０８において主成分因子分析が適用され、その結果主成分４１０が生じ、その各々は対応する参照文字列を参照する。この参照文字列集合は、この集合が具体的には異種データを包含するように生成されることから、文字列候補に対する比較に有益である。
【０１２５】
次に、図１０を参照すると、４５２において、文字列候補を受信した時点で、各文字列候補と各主成分に関連づけられる参照文字列との間の類似性が計算される。本明細書で記述しているように、このような比較はｎグラム照合アルゴリズムに基づく場合もあり、よって、４５４において、文字列候補の各参照文字列およびその対応する主成分に対する類似性を示す２進キーが生成される。４５６では、高速かつ効率的な近似文字列照合のために、レコード（参照文字列）がその個々の２進キーレコードの比較に基づいて文字列候補へ結合される。このようなプロセスは、ユーザが参照文字列（加盟店の名称および／またはロケーションデータを含んでもよい）と加盟店の名称および／またはロケーションデータを表す場合もある文字列候補との間の高確率照合を迅速に検索することを可能にする。４５８において、照合されるべき各データベースレコードの２進キーを生成することにより、４６０では、参照文字列の文字列候補に対する照合ファイルを生成することができる。
【０１２６】
以上、様々な特有の実施形態に関して本発明を説明したが、当業者には、本発明をクレームの精神および範囲内にある変形によって実施し得ることが認識されるであろう。
【特許請求の範囲】
【請求項１】
文字列候補とデータベース内に格納された複数の文字列レコードとの文字列照合を行うためのコンピュータベースの方法であって、
ａ）前記データベース内の参照文字列集合を識別するステップであって、前記参照文字列は異種文字列集合の最適化検索を使用して識別されるステップと、
ｂ）前記参照文字列集合における前記参照文字列のうちの１つに関するｎグラム表現を生成するステップと、
ｃ）前記文字列候補のｎグラム表現を生成するステップと、
ｄ）これらのｎグラム表現間の類似性を決定するステップと、
ｅ）前記識別された参照文字列集合における残りの参照文字列についてステップｂ）およびステップｄ）を反復するステップと、
ｆ）前記文字列候補のｎグラム表現と前記識別された集合における前記参照文字列のｎグラム表現との間の前記決定された類似性に基づいて、前記データベース内の前記文字列候補に指数を付けるステップと、を含むコンピュータベースの方法。
【請求項２】
前記ｎグラム表現間の類似性を決定するステップは、
前記文字列候補における全ての一意のｎグラムの出現頻度と、前記参照文字列における全ての一意のｎグラムの出現頻度とを含む二次元ベクトルを計算するステップと、
前記二次元ベクトルに基づいて、前記文字列候補の前記参照文字列に対する類似性メトリックを計算するステップと、を含む、請求項１記載のコンピュータベースの方法。
【請求項３】
前記文字列候補の類似性メトリックを計算するステップは、構造化問合せ言語の計算を使用して前記二次元ベクトルのコンテンツを比較するステップを含む、請求項２記載のコンピュータベースの方法。
【請求項４】
類似性メトリックを計算するステップは、
前記文字列候補に関連づけられるベクトルの大きさを大きさＡとして決定するステップと、
前記参照文字列に関連づけられるベクトルの大きさを大きさＢとして決定するステップと、
前記２つのベクトル間のドット積を計算するステップと、
前記類似性メトリックを（ドット積／（大きさＡｘ大きさＢ））に従って計算するステップと、を含む、請求項２記載のコンピュータベースの方法。
【請求項５】
類似性メトリックを計算するステップは、ｎグラム頻度類似性計算をＡＳＣＩＩ構造化問合せ言語で実装するステップを含む、請求項２記載のコンピュータベースの方法。
【請求項６】
前記ｎグラム頻度類似性計算を使用して、前記文字列候補と前記識別された参照文字列の各々との間の類似性を示す２進キーを形成するステップをさらに含む、請求項５記載のコンピュータベースの方法。
【請求項７】
前記データベース内の前記文字列候補に指数を付けるステップは、
ｎグラム頻度類似性計算を実装するステップと、
前記計算を使用して、前記文字列候補に関連づけられるレコードと前記識別された参照文字列の各々に関連づけられるレコードとの間の類似性を示す２進キーを形成するステップと、
同じ２進キー値を共有するレコードを結合するステップと、
前記結合されたレコードを、全ての一致するｎグラムの頻度重みの積を合計することによって関連性毎にソートするステップと、を含む、請求項１記載のコンピュータベースの方法。
【請求項８】
前記文字列候補に指数を付けるステップは、前記参照文字列集合と比較した前記文字列候補の類似性メトリックの行列を生成するステップを含む、請求項１記載のコンピュータベースの方法。
【請求項９】
前記文字列候補に指数を付けるステップは、
前記類似性メトリックが予め定義されたしきい値を上回れば、前記参照文字列に対応する２進キーに値１を割り当てるステップと、
前記類似性メトリックが予め定義されたしきい値を下回れば、前記参照文字列に対応する２進キーに値０を割り当てるステップと、を含む、請求項１記載のコンピュータベースの方法。
【請求項１０】
前記データベース内の参照文字列集合を識別するステップは、主成分因子分析を使用して異種文字列レコード集合を識別するステップを含む、請求項１記載のコンピュータベースの方法。
【請求項１１】
コンピュータであって、
最適化探索を利用して、データベース内の異種参照文字列集合を識別し、
文字列候補のｎグラム表現を生成し、
前記集合内の前記異種参照文字列の各々のｎグラム表現を生成し、
前記文字列候補の前記ｎグラム表現と、前記異種参照文字列集合の各ｎグラム表現との間の類似性を決定し、かつ、
前記ｎグラム表現において決定された類似性に基づいて、前記データベース内の前記文字列候補に指数を付けるようにプログラムされるコンピュータ。
【請求項１２】
前記文字列候補の前記ｎグラム表現と、前記異種参照文字列集合の各ｎグラム表現との間の類似性を決定するために、前記コンピュータは、さらに、
前記参照文字列の各々について、前記文字列候補における全ての一意のｎグラムおよび前記参照文字列のうちの１つにおける全ての一意のｎグラムの出現頻度を含む二次元ベクトルを計算し、かつ、
前記二次元ベクトルに基づいて、前記文字列候補の各参照文字列に対する類似性メトリックを計算するようにプログラムされる、請求項１１記載のコンピュータ。
【請求項１３】
前記類似性メトリックを計算するために、前記コンピュータは、構造化問合せ言語計算を利用して前記二次元ベクトルのコンテンツを比較するようにプログラムされる、請求項１２記載のコンピュータ。
【請求項１４】
前記文字列候補に指数を付けるために、前記コンピュータは、
前記決定された類似性が予め定義されたしきい値を上回れば、前記参照文字列に対応する２進キーに値１を割り当て、かつ、
前記決定された類似性が予め定義されたしきい値を下回れば、前記参照文字列に対応する２進キーに値０を割り当てるようにプログラムされる、請求項１１記載のコンピュータ。
【請求項１５】
最適化探索を利用するために、前記コンピュータは、主成分因子分析を使用して前記データベース内の異種参照文字列集合を識別するようにプログラムされる、請求項１１記載のコンピュータ。
【請求項１６】
文字列候補とデータベース内の参照文字列集合との近似照合を行うためのコンピュータベースの方法であって、
前記文字列候補のｎグラム表現を前記参照文字列集合内の各参照文字列のｎグラム表現と個々に比較するステップと、
前記文字列候補に関連づけられる２進指数値を生成するステップであって、前記２進指数値は、前記文字列候補と前記参照文字列の各々との間の類似性を示すステップとを含むコンピュータベースの方法。
【請求項１７】
前記文字列候補のｎグラム表現を各参照文字列のｎグラム表現と個々に比較するステップは、構造化問合せ言語のｎグラム頻度類似性計算を使用して前記ｎグラム表現を比較するステップを含む、請求項１６記載のコンピュータベースの方法。
【請求項１８】
前記文字列候補のｎグラム表現を各参照文字列のｎグラム表現と個々に比較するステップは、
ａ）前記文字列候補の前記ｎグラム表現に関連づけられるベクトルの大きさ（Ａ）を決定するステップと、
ｂ）前記参照文字列のうちの１つの前記ｎグラム表現に関連づけられるベクトルの大きさ（Ｂ）を決定するステップと、
ｃ）前記２つのベクトル間のドット積を計算するステップと、
ｄ）前記参照文字列に対する前記文字列候補の類似性メトリックを（ドット積／（大きさＡｘ大きさＢ））に従って計算するステップと、
各参照文字列についてステップｂ）、ステップｃ）およびステップｄ）を反復するステップと、を含む、請求項１６記載のコンピュータベースの方法。
【請求項１９】
前記文字列候補は加盟店の名称および加盟店の住所のうちの一方であり、かつ前記データベース内の前記参照文字列集合は各々加盟店の名称および加盟店の住所のより大きい集合である、請求項１６記載のコンピュータベースの方法。
【請求項２０】
同じ２進指数値を共有するレコードを結合するステップと、
前記結合されたレコードを、全ての一致するｎグラム表現の頻度重みの積を合計することによって関連性毎にソートするステップと、をさらに含む、請求項１６記載のコンピュータベースの方法。
【請求項１】
文字列候補とデータベース内に格納された複数の文字列レコードとの文字列照合を行うためのコンピュータベースの方法であって、
ａ）前記データベース内の参照文字列集合を識別するステップであって、前記参照文字列は異種文字列集合の最適化検索を使用して識別されるステップと、
ｂ）前記参照文字列集合における前記参照文字列のうちの１つに関するｎグラム表現を生成するステップと、
ｃ）前記文字列候補のｎグラム表現を生成するステップと、
ｄ）これらのｎグラム表現間の類似性を決定するステップと、
ｅ）前記識別された参照文字列集合における残りの参照文字列についてステップｂ）およびステップｄ）を反復するステップと、
ｆ）前記文字列候補のｎグラム表現と前記識別された集合における前記参照文字列のｎグラム表現との間の前記決定された類似性に基づいて、前記データベース内の前記文字列候補に指数を付けるステップと、を含むコンピュータベースの方法。
【請求項２】
前記ｎグラム表現間の類似性を決定するステップは、
前記文字列候補における全ての一意のｎグラムの出現頻度と、前記参照文字列における全ての一意のｎグラムの出現頻度とを含む二次元ベクトルを計算するステップと、
前記二次元ベクトルに基づいて、前記文字列候補の前記参照文字列に対する類似性メトリックを計算するステップと、を含む、請求項１記載のコンピュータベースの方法。
【請求項３】
前記文字列候補の類似性メトリックを計算するステップは、構造化問合せ言語の計算を使用して前記二次元ベクトルのコンテンツを比較するステップを含む、請求項２記載のコンピュータベースの方法。
【請求項４】
類似性メトリックを計算するステップは、
前記文字列候補に関連づけられるベクトルの大きさを大きさＡとして決定するステップと、
前記参照文字列に関連づけられるベクトルの大きさを大きさＢとして決定するステップと、
前記２つのベクトル間のドット積を計算するステップと、
前記類似性メトリックを（ドット積／（大きさＡｘ大きさＢ））に従って計算するステップと、を含む、請求項２記載のコンピュータベースの方法。
【請求項５】
類似性メトリックを計算するステップは、ｎグラム頻度類似性計算をＡＳＣＩＩ構造化問合せ言語で実装するステップを含む、請求項２記載のコンピュータベースの方法。
【請求項６】
前記ｎグラム頻度類似性計算を使用して、前記文字列候補と前記識別された参照文字列の各々との間の類似性を示す２進キーを形成するステップをさらに含む、請求項５記載のコンピュータベースの方法。
【請求項７】
前記データベース内の前記文字列候補に指数を付けるステップは、
ｎグラム頻度類似性計算を実装するステップと、
前記計算を使用して、前記文字列候補に関連づけられるレコードと前記識別された参照文字列の各々に関連づけられるレコードとの間の類似性を示す２進キーを形成するステップと、
同じ２進キー値を共有するレコードを結合するステップと、
前記結合されたレコードを、全ての一致するｎグラムの頻度重みの積を合計することによって関連性毎にソートするステップと、を含む、請求項１記載のコンピュータベースの方法。
【請求項８】
前記文字列候補に指数を付けるステップは、前記参照文字列集合と比較した前記文字列候補の類似性メトリックの行列を生成するステップを含む、請求項１記載のコンピュータベースの方法。
【請求項９】
前記文字列候補に指数を付けるステップは、
前記類似性メトリックが予め定義されたしきい値を上回れば、前記参照文字列に対応する２進キーに値１を割り当てるステップと、
前記類似性メトリックが予め定義されたしきい値を下回れば、前記参照文字列に対応する２進キーに値０を割り当てるステップと、を含む、請求項１記載のコンピュータベースの方法。
【請求項１０】
前記データベース内の参照文字列集合を識別するステップは、主成分因子分析を使用して異種文字列レコード集合を識別するステップを含む、請求項１記載のコンピュータベースの方法。
【請求項１１】
コンピュータであって、
最適化探索を利用して、データベース内の異種参照文字列集合を識別し、
文字列候補のｎグラム表現を生成し、
前記集合内の前記異種参照文字列の各々のｎグラム表現を生成し、
前記文字列候補の前記ｎグラム表現と、前記異種参照文字列集合の各ｎグラム表現との間の類似性を決定し、かつ、
前記ｎグラム表現において決定された類似性に基づいて、前記データベース内の前記文字列候補に指数を付けるようにプログラムされるコンピュータ。
【請求項１２】
前記文字列候補の前記ｎグラム表現と、前記異種参照文字列集合の各ｎグラム表現との間の類似性を決定するために、前記コンピュータは、さらに、
前記参照文字列の各々について、前記文字列候補における全ての一意のｎグラムおよび前記参照文字列のうちの１つにおける全ての一意のｎグラムの出現頻度を含む二次元ベクトルを計算し、かつ、
前記二次元ベクトルに基づいて、前記文字列候補の各参照文字列に対する類似性メトリックを計算するようにプログラムされる、請求項１１記載のコンピュータ。
【請求項１３】
前記類似性メトリックを計算するために、前記コンピュータは、構造化問合せ言語計算を利用して前記二次元ベクトルのコンテンツを比較するようにプログラムされる、請求項１２記載のコンピュータ。
【請求項１４】
前記文字列候補に指数を付けるために、前記コンピュータは、
前記決定された類似性が予め定義されたしきい値を上回れば、前記参照文字列に対応する２進キーに値１を割り当て、かつ、
前記決定された類似性が予め定義されたしきい値を下回れば、前記参照文字列に対応する２進キーに値０を割り当てるようにプログラムされる、請求項１１記載のコンピュータ。
【請求項１５】
最適化探索を利用するために、前記コンピュータは、主成分因子分析を使用して前記データベース内の異種参照文字列集合を識別するようにプログラムされる、請求項１１記載のコンピュータ。
【請求項１６】
文字列候補とデータベース内の参照文字列集合との近似照合を行うためのコンピュータベースの方法であって、
前記文字列候補のｎグラム表現を前記参照文字列集合内の各参照文字列のｎグラム表現と個々に比較するステップと、
前記文字列候補に関連づけられる２進指数値を生成するステップであって、前記２進指数値は、前記文字列候補と前記参照文字列の各々との間の類似性を示すステップとを含むコンピュータベースの方法。
【請求項１７】
前記文字列候補のｎグラム表現を各参照文字列のｎグラム表現と個々に比較するステップは、構造化問合せ言語のｎグラム頻度類似性計算を使用して前記ｎグラム表現を比較するステップを含む、請求項１６記載のコンピュータベースの方法。
【請求項１８】
前記文字列候補のｎグラム表現を各参照文字列のｎグラム表現と個々に比較するステップは、
ａ）前記文字列候補の前記ｎグラム表現に関連づけられるベクトルの大きさ（Ａ）を決定するステップと、
ｂ）前記参照文字列のうちの１つの前記ｎグラム表現に関連づけられるベクトルの大きさ（Ｂ）を決定するステップと、
ｃ）前記２つのベクトル間のドット積を計算するステップと、
ｄ）前記参照文字列に対する前記文字列候補の類似性メトリックを（ドット積／（大きさＡｘ大きさＢ））に従って計算するステップと、
各参照文字列についてステップｂ）、ステップｃ）およびステップｄ）を反復するステップと、を含む、請求項１６記載のコンピュータベースの方法。
【請求項１９】
前記文字列候補は加盟店の名称および加盟店の住所のうちの一方であり、かつ前記データベース内の前記参照文字列集合は各々加盟店の名称および加盟店の住所のより大きい集合である、請求項１６記載のコンピュータベースの方法。
【請求項２０】
同じ２進指数値を共有するレコードを結合するステップと、
前記結合されたレコードを、全ての一致するｎグラム表現の頻度重みの積を合計することによって関連性毎にソートするステップと、をさらに含む、請求項１６記載のコンピュータベースの方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公表番号】特表２０１１−５０９４６３（Ｐ２０１１−５０９４６３Ａ）
【公表日】平成２３年３月２４日（２０１１．３．２４）
【国際特許分類】
【出願番号】特願２０１０−５４１４６８（Ｐ２０１０−５４１４６８）
【出願日】平成２０年１２月４日（２００８．１２．４）
【国際出願番号】ＰＣＴ／ＵＳ２００８／０８５５８５
【国際公開番号】ＷＯ２００９／０８５５５５
【国際公開日】平成２１年７月９日（２００９．７．９）
【出願人】（５００５５７８６４）マスターカード インターナシヨナル インコーポレーテツド (18)
【Ｆターム（参考）】
【公表日】平成２３年３月２４日（２０１１．３．２４）
【国際特許分類】
【出願日】平成２０年１２月４日（２００８．１２．４）
【国際出願番号】ＰＣＴ／ＵＳ２００８／０８５５８５
【国際公開番号】ＷＯ２００９／０８５５５５
【国際公開日】平成２１年７月９日（２００９．７．９）
【出願人】（５００５５７８６４）マスターカード インターナシヨナル インコーポレーテツド (18)
【Ｆターム（参考）】
[ Back to top ]