(57)【要約】  本発明は、識別、ソート、及び効率的なストレージのために、電子メール、画像、サウンドファイル等の電子データストリームを分類してクラスタリングするための方法、装置、及びシステムを提供する。本発明のシステムは、コンピュータ方法を通じて文書を所定のクラスに属するものとしてラベリングすることを開示する。このコンピュータ方法は、１つ又は複数の学習マシンを使用して電子データストリームを識別するステップと、マシンからの出力を比較して、データに関連付けるラベルを決定するステップとを含む。この方法は、ハッシング方式と組み合わせて学習マシンをさらに利用し、文書をクラスタリングして分類する。一実施の形態では、ハッシュ装置及びハッシュ方法はクラスタを分類する。さらに別の実施の形態では、文書のクラスタは、幾何ハッシュを使用して、探索及びストレージのオーバーヘッドなしに、文書をデータコーパスに含める。【選択図】 図１ａ
2008529105.tif 000002
【特許請求の範囲】
【請求項１】
電子データストリームを所定のクラスに属するものとしてラベリングするためのコンピュータ方法であって、
１つ又は複数の学習マシンによって電子データストリームを識別するステップと、
前記学習マシンからの出力を比較するステップであって、それによって、前記電子データストリームに関連付けるラベルを決定する、比較するステップと
を含む、コンピュータ方法。
【請求項２】
前記電子データストリームはあいまいなクラスを含む、請求項１に記載のコンピュータ方法。
【請求項３】
ニューラルネットワーク処理が、結果として、前記電子データストリームを識別して分類することになる、請求項１に記載のコンピュータ方法。
【請求項４】
サポートベクトルマシン処理が、結果として、前記電子データストリームを識別して分類することになる、請求項１に記載のコンピュータ方法。
【請求項５】
ナイーブベイズ処理が、結果として、前記電子データストリームを識別して分類することになる、請求項１に記載のコンピュータ方法。
【請求項６】
孤立値のクラスが管理機能によって識別される、請求項１に記載のコンピュータ方法。
【請求項７】
Ｋ−ＮＮが、前記あいまいなクラスを処理して、類似の電子データストリームのクラスタ内に配置する、請求項２に記載のコンピュータ方法。
【請求項８】
前記電子データストリームは文書の一部である、請求項１に記載のコンピュータ方法。
【請求項９】
前記文書は電子メールである、請求項８に記載のコンピュータ方法。
【請求項１０】
前記電子データストリームは画像の一部である、請求項１に記載のコンピュータ方法。
【請求項１１】
前記電子データストリームはサウンドファイルの一部である、請求項１に記載のコンピュータ方法。
【請求項１２】
ハッシュ技術処理が、結果として、前記電子データストリームを識別して分類することになる、請求項１に記載のコンピュータ方法。
【請求項１３】
識別された属性を有する文書を検出するためのコンピュータ方法であって、
（ａ）２進符号化メッセージを数値に変換すること、
（ｂ）数学関数に対して提供される前記数値に基づいてハッシングベクトルを計算すること、及び
（ｃ）ハッシングベクトルと記憶されているベクトルとの差を比較すること
を含む、コンピュータ方法。
【請求項１４】
前記差を示すヘッダを前記メッセージに付加することをさらに含む、コンピュータ方法。
【請求項１５】
前記数値は少なくとも２バイトから成る、請求項１３に記載のコンピュータ方法。
【請求項１６】
通信媒体により受信された、識別された属性を有する文書を検出するためのコンピュータ方法であって、
（ａ）識別された属性ダイジェストを有する文書のアーカイブを生成するステップと、
（ｂ）電子メールダイジェストのダイジェストを計算するための第１の手段を設けるステップと、
（ｃ）前記電子メールダイジェストと、前記文書のアーカイブに記憶されている、識別された属性ダイジェストを有する１つ又は複数の文書との差の尺度を計算するステップと
を含む、コンピュータ方法。
【請求項１７】
第１のデータオブジェクトの第２のデータオブジェクトとの類似性を判断するためのコンピュータ方法であって、
（ａ）各データオブジェクトを構文解析するステップであって、それによって、数値を有するシンボル列にする、構文解析するステップと、
（ｂ）数学関数に基づいて一組の第１のダイジェストを計算するステップと、
（ｃ）類似の数組の第１のダイジェストを検索用のアーカイブにグループ化するステップと、
（ｄ）前記数学関数に基づいて、数値を有する第２の一組のデータオブジェクトのシンボル列から新しいダイジェストを計算するステップと、
（ｅ）前記新しいダイジェストと前記第１の組のダイジェストのメンバーとの最小の差を求めるために、前記新しいダイジェストを、類似の一組又は二組以上の第１のダイジェストと比較するステップであって、それによって、前記オブジェクトのデータの類似性を判断する、比較するステップと
を含む、コンピュータ方法。
【請求項１８】
識別された属性を有する文書を検出するための装置であって、
（ａ）２進符号化メッセージを一組の数値に変換する手段と、
（ｂ）数学関数に対して提供される前記数値に基づいたハッシングベクトルを計算する手段と、
（ｃ）前記ハッシュベクトルの値と記憶されているベクトル又は該記憶されているベクトルを表すダイジェストとの差を比較する手段と、
（ｄ）前記比較に基づいてスパムメッセージにヘッダを付加する手段と
を備える、装置。
【請求項１９】
通信媒体により受信された、識別された属性を有する文書を検出するための装置であって、
（ａ）識別された属性のダイジェストを有する文書のアーカイブを生成するための手段と、
（ｂ）電子メールダイジェストのダイジェストを計算するための第１の手段を設けるための手段と、
（ｃ）前記電子メールダイジェストと、識別された属性ダイジェストを有する前記文書のアーカイブに記憶されている、識別された属性ダイジェストを有する１つ又は複数の文書との差の尺度を計算するための手段と
を備える、装置。
【請求項２０】
第１のデータオブジェクトの第２のデータオブジェクトとの類似性を判断するための装置であって、
（ａ）各データオブジェクトを構文解析して数値を有するシンボル列にするための手段と、
（ｂ）数学関数に基づいて前記数値から一組の第１のダイジェストを計算するための手段と、
（ｃ）類似の数組の第１のダイジェストを検索用のアーカイブにグループ化するための手段と、
（ｄ）前記数学関数に基づいて、数値を有する第２のデータオブジェクトのシンボル列から新しいダイジェストを計算するための手段と、
（ｅ）前記新しいダイジェストと前記第１の組のダイジェストのメンバーとの最小の差を求めるために、前記新しいダイジェストを、類似の一組又は二組以上の第１のダイジェストと比較して、前記オブジェクトのデータの類似性を判断するための手段と
を備える、装置。
【請求項２１】
複数の文書を比較するためのコンピュータ方法であって、
（ａ）符号化された要素を有する第１の文書をランダムアクセスメモリ内に受信するステップと、
（ｂ）前記符号化された要素を２つの境界の間の数値に変換するステップと、
（ｃ）前記ランダムアクセスメモリからデータレジスタにシリアルに、前記文書からの少なくとも２つの隣接するデータ要素をロードするステップと、
（ｄ）少なくとも２つの関連する隣接データ要素に対応するベクトル及び均一フィルタを計算するステップと、
（ｅ）記憶するための手段から１つの前記データレジスタにシリアルに、前記文書からの次の隣接するデータ要素をロードするステップと、
（ｆ）少なくとも２つの関連する隣接データ要素に対応するベクトル及び均一フィルタを計算するステップと、
（ｇ）前記第１の文書からの要素が、対応するベクトルを有するまで前記ステップ（ｅ）から（ｆ）を繰り返すステップと、
（ｈ）各関連するベクトル要素を合計するステップであって、それによって、関連するハッシングベクトル要素を形成する、合計するステップと、
（ｉ）前記ハッシングベクトルをハッシングベクトルのアーカイブと比較するステップであって、それによって、類似性を判断する、比較するステップと
を含む、コンピュータ方法。
【請求項２２】
均一フィルタセットであって、第１の電子信号及び乱数関数発生器から該均一フィルタへの入力が、前記第１の電子信号の入力との関連性を有する出力を生成するように、確率変数及びランダムマトリクスの関数を備える、均一フィルタセット。
【請求項２３】
前記セットの各フィルタは、このような関数の初期化に使用される関係する種が異なる、請求項２２に記載の均一フィルタセット。
【請求項２４】
前記セットの各フィルタは、同じしきい値を利用して、同じクラス内の信号間の統計的同一性の尺度を求める、請求項２２に記載の均一フィルタセット。
【請求項２５】
均一フィルタを利用して、識別された属性を有する文書が、規定された統計クラス内の電子メールであるか否かをテストすることにより、前記文書の存在を検出するステップを含む、コンピュータ方法。
【請求項２６】
（ａ）前記均一フィルタを利用するステップであって、それによって、電子メール１つ又は複数のクラスを表す特徴ベクトルを形成する、均一フィルタを利用するステップと、
（ｂ）前記特徴ベクトルを特徴ベクトルサンプルと比較するステップであって、それによって、該サンプルが前記受信された電子メールと類似しているか否かを判断する、比較するステップと
をさらに含む、請求項２５に記載のコンピュータ方法。
【請求項２７】
電子メールのスパム性の尺度でスパムとして検出された電子メールをタグ付けするステップをさらに含む、請求項２５に記載のコンピュータ方法。
【請求項２８】
前記電子メールのスパム性の尺度を利用するステップであって、それによって、前記電子メールを隔離する、利用するステップをさらに含む、請求項２５に記載のコンピュータ方法。
【請求項２９】
事前にプログラミングされたルールに基づいて前記電子メールを隔離するステップをさらに含む、請求項２８に記載のコンピュータ方法。
【請求項３０】
（ａ）一組の文書から複数のハッシングベクトルを受信して、前記サンプルハッシングベクトルをランダムアクセスメモリに記憶するステップと、
（ｂ）データレジスタに、受信された文書からの少なくとも２つの隣接するデータ要素をロードするステップと、
（ｄ）ハッシュ手段を利用して電子メールハッシングベクトルを計算するステップと、
（ｅ）前記電子メールハッシングベクトルを前記複数のサンプリングされたハッシングベクトルと比較するステップと
を含む、コンピュータ方法。
【請求項３１】
（ａ）数値のランダムマトリクスを生成するステップと、
（ｂ）前記数値を一組のフィルタに入力するステップと、
（ｃ）前記フィルタの１つ又は複数に１つ又は複数のデータを入力するステップと、
（ｄ）前記乱数及び前記データの関数を計算するステップと、
（ｅ）結果を合計するステップと
を含む、コンピュータ方法。
【請求項３２】
前記マトリクスは、別個のマトリクスを含み、各マトリクスは、２５６×２５６の要素及び範囲０から２５５のエントリーを有する、請求項３１に記載のコンピュータ方法。
【請求項３３】
前記マトリクスは、別個のマトリクスを含み、各マトリクスは、２５６×２５６の要素及び範囲０から２５５のエントリーを有する、請求項３２に記載のコンピュータ方法。
【請求項３４】
前記マトリクスは、別個のマトリクスを含み、各マトリクスは、２５６×２５６の要素及び範囲０から２５５のエントリーを有し、それらのエントリーはタイムスタンプから生成される、請求項３３に記載のコンピュータ方法。
【請求項３５】
前記マトリクスは、擬似乱数発生器から形成される、請求項３４に記載のコンピュータ方法。
【請求項３６】
前記擬似乱数発生器は、範囲０から２５５の数値のエントリー列を生成する、請求項３５に記載のコンピュータ方法。
【請求項３７】
前記擬似乱数発生器は、左に３３０００箇所及び右に３３０００箇所を超える、１０進数で範囲０から２５５の数値のエントリー列を生成する、請求項３６に記載のコンピュータ方法。
【請求項３８】
前記擬似乱数発生器は、入力として前記タイムスタンプを利用して前記乱数列を作成し、範囲０から２５５の数値のエントリー列を生成する、請求項３７に記載のコンピュータ方法。
【請求項３９】
前記擬似乱数発生器は、入力として前記タイムスタンプを利用して値の一様分布を有する前記乱数列を作成し、範囲０から２５５の数値のエントリー列を生成する、請求項３８に記載のコンピュータ方法。
【請求項４０】
値の一様分布を有する前記乱数列は、前記均一フィルタを形成するのに利用される、請求項３１に記載のコンピュータ方法。
【請求項４１】
通信媒体により受信された、識別された属性を有する文書を検出するためのコンピュータ方法であって、区別する点を半径τのボールの中心として選択することによって、特徴ベクトルの空間を分割するステップを含む、コンピュータ方法。
【請求項４２】
時間が最も古い特徴ベクトルは、クラスタの中心としての適格性を失い、最も新しい特徴ベクトルによって取り替えられる、請求項４１に記載のコンピュータ方法。
【請求項４３】
識別された属性を有する文書を検出するためのコンピュータ方法であって、
（ａ）ハッシュを生成するための手段に数値を入力するステップと、
（ｂ）前記ハッシュを生成するための手段に乱数を入力するステップと、
（ｃ）前記ハッシュを生成するための手段を利用するステップであって、それによって、提供された前記入力及び数学関数に基づいてハッシングベクトルを計算する、利用するステップと
を含み、前記ハッシングベクトルの要素は、１つ又は複数のしきい値に対してテストされる、コンピュータ方法。
【請求項４４】
第１の特徴ベクトルの要素をテストするステップであって、（ａ）該第１の特徴ベクトルの要素が第１の事前に選択された数値よりも大きいか又は第２の事前に選択された数値よりも小さい場合には、関連するハッシュベクトルの第１の要素の状態を１に等しく設定し、（ｂ）そうでない場合には、関連するハッシュベクトルの第１の要素の状態を０に等しく設定し、（ｃ）すべての特徴ベクトルの要素がテストされるまで、該特徴ベクトル及び該関連するハッシュベクトルの要素のそれぞれについてステップ「ａ」から「ｂ」を繰り返す、テストするステップをさらに含む、請求項４３に記載のコンピュータ方法。
【請求項４５】
（ａ）前記第１の特徴ベクトルの要素が量子化要素よりも大きいか否かをテストするステップと、
（ｂ）且つそうでない場合には、関連するビットマスクを１に設定するステップと、
（ｃ）又は前記要素が前記量子化要素以下である場合に、前記関連するビットマスクを０に設定するステップと
をさらに含む、請求項４３に記載のコンピュータ方法。
【請求項４６】
電子信号のパターンを検出するためのプロセスであって、
（ａ）前記パターン信号を、間隔を有する期間に分割すること、
（ｂ）前記信号の１つ又は複数の分割された期間を１つ又は複数の、ハッシュを生成するための手段に入力すること、
（ｃ）間隔を有する期間を有するランダム信号を前記１つ又は複数のフィルタに入力すること、
（ｃ）前記フィルタを利用して各パターン信号を変換することにより期間別に各ランダム信号の関数によって、特徴信号を計算すること、
（ｄ）各特徴信号時間期間ｎを、前記パターンの第１の選択された１つ又は複数の統計値と比較することにより、ハッシュパターンを作成すること、
（ｅ）各特徴信号期間を、前記パターンの第２の選択された１つ又は複数の統計値と比較することにより、マスクパターンを作成すること、及び
（ｆ）前記ハッシュパターンと前記マスクパターンとを組み合わせるとともに、その結果を、検出される前記パターンに基づいて１つ又は複数のパターンと比較すること
を含み、一致が存在する場合に、前記パターンが検出される、プロセス。
【請求項４７】
前記電子信号はアナログである、請求項４５に記載のプロセス。
【請求項４８】
前記電子信号はデジタルである、請求項４５に記載のプロセス。
【請求項４９】
前記電子信号はテキストメッセージである、請求項４５に記載のプロセス。
【請求項５０】
前記電子信号は音声メッセージである、請求項４５に記載のプロセス。
【請求項５１】
前記電子信号は画像である、請求項４５に記載のプロセス。
【請求項５２】
前記電子信号は、ビデオメッセージ、オーディオメッセージ、及び制御メッセージのうちの１つ又は複数のを含む合成信号である、請求項４５に記載のプロセス。
【請求項５３】
前記ランダム信号はデジタルである、請求項４５に記載のプロセス。
【請求項５４】
前記ランダム信号はアナログである、請求項４５に記載のプロセス。
【請求項５５】
前記特徴信号はデジタルである、請求項４５に記載のプロセス。
【請求項５６】
前記特徴信号はアナログである、請求項４５に記載のプロセス。
【請求項５７】
変換する前記フィルタは非線形変換である、請求項４５に記載のプロセス。
【請求項５８】
変換する前記フィルタは線形変換である、請求項４５に記載のプロセス。
【請求項５９】
前記ハッシュパターンはアナログである、請求項４５に記載のプロセス。
【請求項６０】
前記ハッシュパターンはデジタルである、請求項４５に記載のプロセス。
【請求項６１】
前記ビットマスクパターンはデジタルである、請求項４５に記載のプロセス。
【請求項６２】
前記ビットマスクパターンはアナログである、請求項４５に記載のプロセス。
【請求項６３】
一致したことを示すヘッダを前記電子信号に追加することをさらに含む、請求項４５に記載のプロセス。
【請求項６４】
前記電子信号は、２バイトから成る数値に変換された２進符号化メッセージである、請求項４５に記載のプロセス。
【請求項６５】
電子信号のパターンを検出するためのシステムであって、
（ａ）前記パターン信号を、間隔を有する期間に分割するための手段と、
（ｂ）前記信号の１つ又は複数の分割された期間を１つ又は複数のフィルタに入力するための手段と、
（ｃ）間隔を有する１つ又は複数の期間を有するランダム信号を前記１つ又は複数のフィルタに入力するための手段と、
（ｃ）前記フィルタを利用して各パターン信号を変換することにより、期間別に、各ランダム信号の関数として、特徴信号を計算するための手段と、
（ｄ）各特徴信号期間を、前記パターンの第１の選択された１つ又は複数の統計値と比較することにより、ハッシュパターンを作成するための手段と、
（ｅ）各特徴信号期間を、前記パターンの第２の選択された１つ又は複数の統計値と比較することにより、ビットマスクパターンを作成するための手段と、
（ｆ）前記ハッシュパターンと前記ビットマスクパターンとを組み合わせるとともに、その結果を、検出される前記パターンに基づいて１つ又は複数のパターンと比較するための手段と
を備え、一致が存在する場合に、前記パターンが検出される、システム。
【請求項６６】
前記信号はアナログである、請求項６４に記載のシステム。
【請求項６７】
前記信号はデジタルである、請求項６４に記載のシステム。
【請求項６８】
電子メールのクラスタの送信を検出するためのコンピュータ方法であって、
（ａ）１つ又は複数の電子メールメッセージを受信するステップと、
（ｂ）前記複数の電子メールメッセージの１つ又は複数の部分に基づいてハッシュ値を生成するステップと、
（ｃ）前記複数の電子メールメッセージの１つ又は複数の部分に基づいて、関連するビットマスク値を生成するステップと、
（ｄ）前記生成されるハッシュ値及び前記関連するビットマスク値が、前記クラスタの１つ又は複数の前の電子メールメッセージに関係する、対応するハッシュ値及び関連するビットマスク値と一致するか否かを判断するステップと
を含む、コンピュータ方法。
【請求項６９】
前記生成されるハッシュ値及び前記関連するビットマスク値が、前記クラスの前の電子メールメッセージに関係する、対応するハッシュ値及び関連するビットマスク値と一致するか否かの判断の結果に基づいて、前記複数の電子メールメッセージのセイリエンススコア（salience score：特徴スコア）を生成することをさらに含む、請求項６７に記載のコンピュータ方法。
【請求項７０】
前記複数の電子メールメッセージのうちの１つが、不要である可能性のある電子メールである場合に、救済動作を取るステップをさらに含む、請求項６８に記載のコンピュータ方法。
【請求項７１】
不要である可能性のある電子メールの送信を検出するためのシステムであって、
複数の電子メールを観察するための手段と、
前記複数の電子メールの１つ又は複数の部分のハッシングベクトルを作成するための手段と、
ハッシュ値を生成する手段と、
ビットマスクを生成する手段と、
前記生成されるハッシュ値及び関連するビットマスク値が、前の電子メールに関係するハッシュ値及び関連するビットマスク値と一致するか否かを判断するための手段と、
前記複数の電子メールが不要である可能性のある電子メールであると判断するための手段と
を備える、システム。
【請求項７２】
不確かな領域内で動作することによってテキスト分類の精度を改善するためのコンピュータ方法であって、Ｋ−ＮＮプロセッサを利用するステップであって、それによって、前記テキストとの最大の類似度を有する文書を決定する、Ｋ−ＮＮプロセッサを利用するステップを含む、コンピュータ方法。
【請求項７３】
ハッシュ生成手段を利用するステップであって、それによって、前記テキストとの最大の類似度を有するクラスタを決定する、前記ハッシュ生成手段を利用するステップをさらに含む、請求項７２に記載の不確かな領域内で動作することによってテキスト分類の精度を改善するためのコンピュータ方法。
【請求項７４】
スタック可能ハッシュ（stackable hash）プロセスを利用するステップであって、それによって、前記テキストとの最大の類似度を有するクラスタを決定する、スタック可能ハッシュプロセスを利用するステップをさらに含む、請求項７２に記載の不確かな領域内で動作することによってテキスト分類の精度を改善するためのコンピュータ方法。
【請求項７５】
電子メールメッセージを記憶するためのコンピュータ方法であって、スタック可能ハッシュプロセスを利用するステップであって、それによってクラスタを決定する、スタック可能ハッシュプロセスを利用するステップを含み、該クラスタは前記電子メールのデルタストレージを決定する、電子メールメッセージを記憶するためのコンピュータ方法。
【請求項７６】
均一フィルタプロセスを利用するステップであって、それによってクラスタを決定する、均一フィルタプロセスを利用するステップをさらに含み、該クラスタは前記電子メールのデルタストレージを可能にする、請求項７５に記載の電子メールメッセージを記憶するためのコンピュータ方法。
【請求項７７】
電子メールメッセージを取り出すための方法であって、スタック可能ハッシュプロセスを利用するステップであって、それによってクラスタを決定する、スタック可能ハッシュプロセスを利用するステップを含み、該クラスタはメモリのロケーションを決定する、方法。
【請求項７８】
電子メールメッセージを記憶するための方法であって、ハッシュ生成手段を利用するステップであって、それによってクラスタを決定する、ハッシュ生成手段を利用するステップを含み、該クラスタはメモリのロケーションを決定する、方法。
【請求項７９】
クラスタとして記憶される文書の蓄積を作成するための方法であって、ハッシングベクトルを作成するプロセスを利用するステップであって、それによって、クラスタに文書を追加するか否かを判断する、ハッシングベクトルを作成するプロセスを利用するステップを含む、方法。
【請求項８０】
一組のクラスタとして記憶される文書の蓄積を作成するためのコンピュータ方法であって、スタック可能ハッシュを利用するステップであって、それによって、前記一組のクラスタに文書を追加するか否かを判断する、スタック可能ハッシュを利用するステップを含む、コンピュータ方法。
【請求項８１】
エージング関数によって調整される、請求項７８に記載のクラスタとして記憶される文書の蓄積を作成するためのコンピュータ方法。
【請求項８２】
エージング関数によって調整される、請求項７９に記載のクラスタとして記憶される文書の蓄積を作成するためのコンピュータ方法。
【請求項８３】
文書クラスタを識別するマスクをさらに含む、請求項７８に記載のクラスタとして記憶される文書の蓄積を作成するためのコンピュータ方法。
【請求項８４】
文書クラスタを識別するマスクをさらに含む、請求項７９に記載のクラスタとして記憶される文書の蓄積を作成するためのコンピュータ方法。
【請求項８５】
ラベルの例示に従い、これらのラベルが事前に規定されているのか、又はユーザ規定であるのかに基づいて、電子メールを自動ラベリングすることをさらに含む、請求項７９に記載のコンピュータ方法。
【請求項８６】
テキスト入力が関係しているのか又は関係していないのかを、この判断に関するスコアを割り当てることによって判断することをさらに含む、請求項７９に記載のコンピュータ方法。
【請求項８７】
電子メールクラスタリングを形成すること、及び長いハッシュ及び小さなハッシュをグラフィカル形式で表示することをさらに含む、請求項７９に記載のコンピュータ方法。
【請求項８８】
小さなハッシュのしきい値を利用して、電子メールクラスタリングを形成することをさらに含む、請求項７９に記載のコンピュータ方法。
【請求項８９】
小さなハッシュの長さを利用して、電子メールクラスタリングを形成することをさらに含む、請求項７９に記載のコンピュータ方法。
【請求項９０】
小さなハッシュの平均を利用して、電子メールクラスタリングを形成することをさらに含む、請求項７９に記載のコンピュータ方法。
【請求項９１】
ＳＶＭプロセス、ＮＢプロセス、及びＮＮプロセスを組み合わせるコンピュータ方法であって、それによって、テキスト分類のマシン学習の実用性を最適化する、コンピュータ方法。
【請求項９２】
Ｋ−ＮＮプロセスを組み合わせるステップであって、それによって、テキスト分類のマシン学習の実用性を最適化する、Ｋ−ＮＮプロセスを組み合わせるステップをさらに含む、請求項９１に記載のコンピュータ方法。
【請求項９３】
ナイーブベイズプロセスとＫ−ＮＮプロセスとを組み合わせるコンピュータ方法であって、それによって、テキスト分類のマシン学習の実用性を最適化する、コンピュータ方法。
【請求項９４】
クラスタリングに基づいて、保有率を電子メールのクラスタに属するものとみなすステップをさらに含む、請求項７９に記載のコンピュータ方法。
【請求項９５】
テキスト分類器を初期化又はトレーニングするユーザ規定のラベルの例示を使用するステップであって、それによって、使用するステップをさらに含む、請求項９１に記載のコンピュータ方法。
【請求項９６】
クラスタリングの計算時間を最小にし、且つ、分類の精度を最大にするハッシュ方法を作成するステップをさらに含む、請求項７９に記載のコンピュータ方法。
【請求項９７】
デルタストレージ方法を使用するコンピュータ方法であって、
（ｉ）クラスタを作成するステップと、
（ｉｉ）クラスタをソートするステップと、
（ｉｉｉ）クラスタに対してラベリングするステップと、
（ｉｖ）各クラスタの最も短い電子メールを代表として識別するステップと、
（ｖ）クラスタの他のすべてのメンバーについてバイナリ差分関数（binary differential function）を計算するステップと、
（ｖｉ）前記クラスタ内の圧縮された電子メールをタグ付けするステップと
を含む、コンピュータ方法。
【請求項９８】
前記デルタストレージ方法を使用するステップであって、それによって、ファイルを圧縮する、デルタストレージ方法を使用するステップをさらに含む、請求項９７に記載のコンピュータ方法。
【請求項９９】
悪質なコード、フィッシング、ウィルス、又はワームのうちの１つを含む電子メールを識別する目的でクラスタリング方法を使用するステップをさらに含む、請求項７９に記載のコンピュータ方法。
【請求項１００】
デルタストレージのために電子メールを識別する目的でクラスタリング方法を使用するステップをさらに含む、請求項７９に記載のコンピュータ方法。
【請求項１０１】
クラスタメンバーを識別する目的で時間フレームにマスクを使用するステップをさらに含む、請求項７９に記載のコンピュータ方法。
【請求項１０２】
エージング関数を使用するステップであって、それによって、クラスタメンバーを識別する、エージング関数を使用するステップをさらに含む、請求項７９に記載のコンピュータ方法。
【請求項１０３】
クラスタを使用するステップであって、それによって、ハッシュデータの中央レポジトリをポピュレートする、クラスタを使用するステップをさらに含む、請求項７９に記載のコンピュータ方法。
【請求項１０４】
組織間で情報を匿名で共有するためのハッシュ表をポピュレートするステップをさらに含む、請求項７９に記載のコンピュータ方法。
【請求項１０５】
冗長な情報を削除することによって電子メールコーパスを圧縮するステップをさらに含む、請求項９７に記載のコンピュータ方法。
【請求項１０６】
小さな衝突を有するハッシュ関数を選択するステップをさらに含む、請求項７９に記載のコンピュータ方法。
【請求項１０７】
クラス別にインデキシング技法をソートするステップであって、それによって、クエリーをルーティングする、ソートするステップをさらに含む、請求項７９に記載のコンピュータ方法。
【請求項１０８】
クラスを使用するステップであって、それによって、クラスタの一部としてクエリーをルーティングする、クラスを使用するステップをさらに含む、請求項７９に記載のコンピュータ方法。
【請求項１０９】
情報を取り出す目的で、データコーパスに含まれる１つ又は複数のオブジェクトに分類を適用するステップ、をさらに含む、請求項９７に記載のコンピュータ方法。
【請求項１１０】
スタック可能ハッシュ方法において等価クラス（ｍｏｄ  Ｐ）を求める目的で素数Ｐを選択するステップをさらに含む、請求項７９に記載のコンピュータ方法。
【請求項１１１】
クラスタを作成するためのハッシュ方法において輝度及びエージング関数を使用するステップをさらに含む、請求項７９に記載のコンピュータ方法。
【請求項１１２】
電子データストリームを所定のクラスに属するものとしてラベリングするためのコンピュータ方法であって、
１つ又は複数の学習マシンによって電子データストリームを識別するステップと、
前記学習マシンからの出力を比較するステップであって、それによって、前記電子データストリームに関連付けるラベルを決定する、比較するステップと、
電子メールの内容及びラベルから編集された集約データを処理して分析することによって、電子メールユーザのラベルをあらかじめ規定するステップと
を含む、コンピュータ方法。
【請求項１１３】
電子データストリームを所定のクラスに属するものとしてラベリングするためのコンピュータ方法であって、
１つ又は複数の学習マシンによって電子データストリームを識別するステップと、
前記学習マシンからの出力を比較するステップであって、それによって、前記電子データストリームに関連付けるラベルを決定する、比較するステップと、
均一フィルタを使用するのか、又はスタック可能ハッシュを使用するのかを決定するステップであって、それによって、前記電子データストリームのクラスタを決定する、前記決定するステップと
を含む、コンピュータ方法。
【請求項１１４】
電子データストリームを所定のクラスに属するものとしてラベリングするためのコンピュータ方法であって、
１つ又は複数の学習マシンによって電子データストリームを識別するステップと、
前記学習マシンからの出力を比較するステップであって、それによって、前記電子データストリームに関連付けるラベルを決定する、比較するステップと、
均一フィルタを使用するのか、又はスタック可能ハッシュを使用するのかを決定するステップであって、それによって、識別された属性の電子メールを有する文書のクラスタを決定する、決定するステップと
を含む、コンピュータ方法。
【請求項１１５】
電子データストリームを所定のクラスに属するものとしてラベリングするためのコンピュータ方法であって、
１つ又は複数の学習マシンによって電子データストリームを識別するステップと、
前記学習マシンからの出力を比較するステップであって、それによって、前記電子データストリームに関連付けるラベルを決定する、比較するステップと、
Ｋ−ＮＮ方法を使用して１つ又は複数のクラスに空間を分割した後に、許容可能な精度のレベルを求めるステップと
を含む、コンピュータ方法。
【請求項１１６】
前処理時間、実行時間、精度のレベル、又は安定性のレベルのうちのうちの１つに基づいて、Ｋ−ＮＮを使用するのか、又はニューラルネットワークを使用するのかを選択するステップをさらに含む、請求項１１２に記載のコンピュータ方法。
【請求項１１７】
均一フィルタ方法を使用するのか、又はスタック可能ハッシュ方法を使用するのかを決定するステップであって、それによって、電子メールを不確かな領域にクラスタリングする、決定するステップをさらに含む、請求項１１２に記載のコンピュータ方法。
【請求項１１８】
スタック可能ハッシュを使用するステップであって、それによって、電子文書を比較する、スタック可能ハッシュを使用するステップをさらに含む、請求項１１２に記載のコンピュータ方法。
【請求項１１９】
学習マシンによる分析のためのベクトル空間にテキスト入力をマッピングするために、クラスタリング用にテキストを前処理するステップをさらに含む、請求項１１２に記載のコンピュータ方法。
【請求項１２０】
混合分布を使用するステップであって、それによって、前処理時間、実行時間、精度、及び安定性の重要度及び同時最適化を評価してＳＶＭ、ＮＮ、及びＮＢのうちの１つから分類方法を選択する、前記混合分布を使用するステップをさらに含む、請求項１１２に記載のコンピュータ方法。
【発明の詳細な説明】
【技術分野】
【０００１】
［発明の背景］
［発明の分野］
本出願は、電子データ構造体のパターンを識別することに別の方法で適用されるような符号化データの生成又は変換の分野に関する。
【背景技術】
【０００２】
［従来技術の説明］
文書のクラスタリング技法及び分類技法は、概観を提供するか、又は一定の基準に基づいて一組の文書を識別することができる。これによって、その一組の文書の内容内の一定のパターンが増強（amplifies）又は検出される。これらの技法により、用途によっては、不要な電子メールがフィルタリングされるものもあれば、探索ストラテジー及び記憶ストラテジーが効果的になるものもある。識別ストラテジーは、たとえば、クラスタ内の文書が互いに類似し且つ他のクラスタの文書とはそれほど類似しないように、類似度測定に基づいて文書をクラスタに分割することができる。クラスタリング及び分類のプロセスをラベリングと呼ぶ。要求の厳しい用途では、ラベリングは、安定していて、高速で、効率的で、且つ、正確であるという条件で、特に、ストレージ及び検索の用途では、企業の効率を大きく改善することができる。
【０００３】
情報技術のユーザは、数え切れないほどの不要な電子メール、不要なテキストメッセージ、並びに、非常に有害な新しいウィルス及びワームに毎日効率的に対処しなければならない。この大部分が不必要に大容量のネットワークトラフィックは、労働者の生産性を低下させ、重要なネットワークアプリケーションを低速にする。今日のデジタルエコノミーにおける最も重大な問題のうちの１つは、スパムの容量の増加に対処しなければならない。したがって、電子メールの受信者だけでなくサービスプロバイダも、ワールドワイドウェブ上でのその拡散を削減する有効な解決法を必要としている。しかしながら、スパム検出がより高性能になるにつれて、スパムの発信者は、検出を回避する新しい方法を発明する。たとえば、或る従来技術の方法論は、電子メールと比較される識別された属性を有する文書シグネチャを保持するための集中データベースを提供する。しかしながら、スパムの発信者は、今や、メッセージ自体は理解可能となるようにするが、現在使用されているさまざまなアンチスパムフィルタリング技法に基づく検出を逃れるように、電子メールの内容をわずかに又はランダムに変更する。
【０００４】
現在、少なくとも３０個のオープンリレーが世界を支配しており、異なるレート及び異なるレベルの構造的変化でメッセージを送信（burst）している。一定のタイプの電子メールは、スパムによって例示されるように、変化又は進化するので、スパムフィルタリング検出アルゴリズムは、有効となるように絶えず順応しなければならない。スパム電子メールの場合、たとえば、スパムコーパスのまさにその性質は、体制変化を受ける。したがって、クラスタリングの最適性は、データコーパスの性質及びデータコーパスが受ける変化に大きく依存する。
【０００５】
識別された属性を有する文書の有効な検出方式又は電子メール分類方式の目的は、類似のメッセージを見つけることである。電子メールの多くのクラスタはスパム、ｅ−ｖｉｔｅ、メーリングリストによって表される；電子メールは企業内を何度も転送される；ウェブサイトからのターゲットメーリング（targeted mailing）。企業がその後これらのクラスタで何を行うかは、その企業の裁量に委ねられている。したがって、クラスタの空間におけるメトリックの明確な概念を規定することが不可欠である。分かりやすく言えば、文書に関連する２つの電子データストリームが与えられると、システムは、２つのメッセージがどれくらい類似しているか又はどれくらい近いかを、意味のある或る方法で表す「距離」と呼ばれる数値を生成可能でなければならない。
【０００６】
分類器は、電子メールの異なるカテゴリーの検出器として有効に動作するために、距離関数のパラメータ及びしきい値を慎重に確立しなければならない。たとえば、しきい値があまりにも高い場合、分類器は、あまりにも多くの誤検知を生み出すことになる。同じことは、しきい値が不当に低く選ばれた場合にも起こる可能性がある。
【０００７】
一般に、メトリックの選択は、分類器又はフィルタの選択による影響を受ける。フィルタについては、２つのメッセージＸ及びＸ'が与えられると、システムは、電子データストリーム又はシグネチャアレイ（ｆ１，ｆ２，…，ｆｎ）及び（ｆ'１，ｆ'２，…，ｆ'ｎ）を生成することができる。ここで、ｎはフィルタの個数である。
【０００８】
これらの２つのアレイを比較するには、メトリックの仕様及びその組における各フィルタのしきい値が必要とされる。したがって、たとえば、以下の条件のすべてが同時に当てはまる場合、且つその場合に限り、２つのメッセージは同じスパムクラスに属する。
【０００９】
【数１】
2008529105.tif 000003
【００１０】
ここで、τｎは、フィルタのそれぞれについて適切に選ばれた数値のしきい値であり、ｄは、２つのフィルタ値間の距離の関数を表す。
【００１１】
Ｎｉｌｓｉｍｓａシグネチャ（「ＮＳ」）方法は、電子メールのメッセージ本体に同じハッシュ値を有する３グラムの生起（3-gram occurrences）をカウントし、或るスパム検出スキーマの一例として機能する（http://ixazon.dynip.com/~cmeclax/nilsimsa.htmlを参照）。ＮＳは、テキストの変化が統計的に無関係であるとみなされるので、テキストの変化を無視する。メッセージが与えられると、ＮＳは、６４個の１６進数のシーケンスを生成する。たとえば、ＮＳが４ビットのみから成る場合、２つの符号１００１と０００１との間の距離は、これらの２つのシグネチャが第１ビットしか異ならないので、１となる。ＮＳの重要な側面は、入力テキストを変更しても、符号のエントリーのすべてが変更されるわけではないということである。本発明の方法では、入力テキストに対する小さな変更が符号のエントリーのすべてを変更させる。
【００１２】
スパムを検出する一方法は、ＭＤ５と呼ばれるハッシュ値を作成する。ＭＤ５は、スパムを識別するための手段としては、比較的効果がないことが分かる。その理由は、メッセージがわずかに変更されると、ハッシュ値が大幅に変化するからである。これらの方法は、完全に同一のメッセージを識別するのには有効に機能するが、スパム検出回避の本質は、スパムの送信者が、大幅に異なるＭＤ５の結果を生成する相違を組み込み続けることを意味する（「純粋な」メッセージの２つの文字の簡単な並べ替えによって、ＭＤ５のチェックは、スパム検出に完全に役立たなくなる）。
【００１３】
数個のフィルタを使用することによって、電子メールメッセージがより綿密な検査の対象にされ、それによって誤検知が削減される。その６４個の値のそれぞれが単一のフィルタと考えられる場合、ＮＳは一組のフィルタとみなすことができる。次に、メトリックを、各個々の数値について異なるビットの個数として規定することができる。このような方法の欠点は、このように規定された距離が４を超えることができないことである。その理由は、数値が１６進数だからである。各フィルタは単独では、完全に原始的なものである。アルゴリズムの変更を通じて達成されるような基数（radix）を増加させることによるか、又は隣接するフィルタを結合してより大きな全体フィルタにし、したがって、フィルタ数を減少させることにより、この方法をより強固にすることができる。
【発明の開示】
【発明が解決しようとする課題】
【００１４】
数個のフィルタを配置することに加えて、しきい値の選択が依然として要件であるという点で問題は存続する。あいにく、１つのフィルタであっても、電子メールが互いに類似するものとしてどのようにタグ付けされるかのヒューリスティックな目視検査プロセスによって、及び、何が、識別された属性を有する文書の許容可能な検出をもたらすかについての試行錯誤による以外に、そのしきい値を選択する体系的な手法は存在しない。数個のフィルタ値を考慮しなければならない場合、フィルタリングは、すべてのしきい値に依存し、したがって、このような試行錯誤プロセスによって最適なしきい値を見つけることは、非常な難事業を呈する。（１）しきい値をソフトウェアにハードコードすること、（２）手動で且つ定期的に最適化チェックを実行すること、及び／又は（３）最適化を自動的に実行すること、の３つの解決法が可能である。
【００１５】
第１の解決法で成功するには、現在のスパムの傾向に基づいて最適化問題を解かなければならない。しかしながら、それが、たとえ今日の一定のタイプの電子メールをフィルタリングすることに仮に成功したとしても、明日、十分であるという保証は存在しない。第２の解決法は、骨の折れることが分かり得る。しかしながら、本発明者らは、一定のタイプの電子メール認識の最適化問題の解決法を求めた。この解決法は、学習マシン、並びに、特別なクラスの均一フィルタ及びスタック可能ハッシュの組み合わせを利用することによって従来技術の欠点を緩和する。この組み合わせは、電子データストリームの類似度又は同一性を比較して、それらの電子データストリームをクラスタ又は分類に入れるしきい値の体系的な調査、決定、及び最適化を可能にするものである。電子文書の分類及びクラスタリングに関して、本発明は、結果の安定性及び精度を最大にする一方で、コンピュータプロセスの前処理時間及び実行時間を最小にしようとさらに努力する。
【課題を解決するための手段】
【００１６】
［発明の概要］
本発明は、電子データストリームを識別して分類するためのコンピュータ方法、装置、及びシステムに関し、したがって、電子メールの情報コンテンツ、画像、及びサウンドファイル（一括してデータコーパスと呼ぶ）を所定のクラスに属するものとして含む。識別するステップ及び分類するステップは、ニューラルネットワークプロセッサ（「ＮＮ」）、サポートベクトルマシン（「ＳＶＭ」）、ナイーブベイズプロセッサ（「ＮＢ」）等のうちの１つ又は複数の学習マシンによって行われる。電子データストリームがあいまいであると判断された場合、Ｋ−ＮＮプロセッサは、類似の電子メールストリームのクラス又はクラスタ内に入れることを可能にしようと試みる。
【００１７】
また、本発明は、ＳＶＭ、ＮＮ、ＮＢ、Ｋ−ＮＮ、及び他のマシン学習方法を均一フィルタ技術やスタック可能ハッシュ技術等のハッシュ技術と組み合わせて、マシン学習方法及び関連する技術のみを使用して得ることができるものよりも正確なクラスタリングによるテキスト分類を可能にするための方法も提供する。
【００１８】
また、本発明は、基礎となるデータオブジェクトの意味のある（たとえば、意味論的な）内容に基づいてデータコーパスの分類法をもたらすための方法も提供する。一実施の形態では、本発明は、電子メールに関係するハッシュを作成することによりクラスタリングする目的で電子メールのパターンを検出し、また、ハッシュを使用して、スパム、ポルノ、又は緊急情報（critical intelligence）等のカテゴリーに受信したタイプの電子メールのセイリエンスをスコアするために電子メールのＮ個の文字のダイジェストを生成するためのコンピュータ方法、装置、及びシステムを利用する。この方法は、既知のメッセージタイプから計算されたダイジェストの、インターネットにより受信された電子メールとの類似を判断する。一実施の形態では、受信された電子メールは、構文解析されて、数値を有するコンテンツシンボル列にされる。この方法は、類似の数組のダイジェストをグループ化するアルゴリズムを使用して、サンプリングされた既知の電子メールを表すダイジェストを計算する。その後、それらは検索のためにアーカイブされる。その後、この方法は、アルゴリズムに基づき、構文解析して、数値を有するコンテンツシンボル列を作成することにより、受信された電子メールから新しいダイジェストを計算する。新しいダイジェストは、１つ又は複数の類似の数組のサンプリングされたダイジェストと比較されて、その新しいダイジェストと、サンプリングされたダイジェストのメンバーとの間の最小の差が求められ、それによって、それらの２つのダイジェスト間のデータ類似が判断される。
【００１９】
本発明の一実施の形態は、一組のハッシュフィルタを備える。この実施の形態において、この一組における各フィルタは、乱数のマトリクスの関数及び確率変数の関数から形成されて、通常はサンプリングされた電子メール及び同じランダム関数によって生成される乱数のマトリクスのうちの１つを特徴付ける第１の組の可変電子信号入力が、通常は精密な調査の下で電子メールを特徴付ける第２の組の電子信号入力との統計的同一性を有する出力シグネチャのデータベースを生成するようにされる。この一組における各均一フィルタは、このような関数の初期化に使用される、統計的に関係する種が異なる。２つの電子メール出力の組は、このように作成された２つの電子メールの関係の程度を測定するのに使用されるしきい値と比較される。
【００２０】
また、本発明の一実施の形態は、オプションの「スタック可能ハッシュ」も備える。このスタック可能ハッシュは、クラスタの領域を抜粋するためのマスクの実施を可能にする。加えて、この方法は、四角形の十分に解像度の高い格子に低衝突ハッシュも利用する。
【００２１】
本発明は、以下の詳細な説明を添付の図面と共に読んだ時に、以下の詳細な説明から最も良く理解される。図面のさまざまな特徴は、余すところなく明記されていない。そればかりでなく、それらのさまざまな特徴は、明確にするために任意に拡張又は削減されている場合がある。添付の図面には以下の図が含まれる。
【発明を実施するための最良の形態】
【００２２】
［発明の詳細な説明］
解説する図において、回路及び関連するブロック並びに矢印は、本発明によるプロセスの機能を表している。これらの機能は、電気回路及び関連する配線又はデータバスとして実施してもよい。関連する配線又はデータバスは電気信号を運ぶ。代替的に、１つ又は複数の関連する矢印は、特に、本発明の本方法又は本装置がデジタルプロセスである場合に、ソフトウェアルーチン間の通信（たとえば、データフロー）を表す場合もある。
【００２３】
図１ａは、１つ又は複数の新規な文書分類方式に基づいて電子メールを分類し、分離し、そして記憶するための本発明の方法の概観を提供している。電子メールが金融、法律、及び税金に関係するものであるのか、又はワールドワイドウェブにより電子メールを送信できる任意の主題に関係するものであるのか等の識別ラベルを適用する目的で、電子メールが受信される（１０１）。電子メールは、１つ又は複数の学習マシンによって提供されるような、識別のためのプロセスを受ける（１０３）。識別情報又はラベルは、利用される各学習マシンプロセスについて生成されて記憶される（１０５）。各学習マシンを利用した後、学習マシンからの出力が比較され（１０７）、多数決や他の既知の統計方法等の分析方法によって、電子メールに関連付けるラベルを決定し（１０９）、その結果、電子メールをラベル付けする（１０９）。その後、分析中の電子メールは、たとえば、別のラベルが同じ電子メールに適合するか否かを確かめるために、プロセス１０１を再び受ける場合がある。この理由は、いくつかの電子メールでは２つ以上のクラスが、一例として、金融情報を税の問題の法解釈に関係付ける電子メールを適用する場合があるからである。
【００２４】
図１ｂでは、コンピュータによって受信された電子メールが、任意選択的に視覚的に検査され（１３０）分類される（１３６）か、又は本発明に従って、その内容を１つ又は複数の学習マシンへの入力として利用する目的で前処理される（１２０）。学習マシンの技術及び科学的知識は時間と共に発展するので、発明者は、本明細書において、本発明を特定の学習マシンプロセスに限定しない。しかしながら、限定ではなく例示として開示された学習マシンは、ＮＮ、ＳＶＭ、ＮＢ等のパターン認識の技術分野において既知のプロセスのクラス内のプロセスである。この方法は、上記学習マシンのうちの１つを選択して（１２２）、入力された電子メールを電子メールの所定のクラスに分類することを試みる。ステップ１２４において、学習マシンのうちの１つを利用して、本発明のプロセスは、所定のクラスに属するものとして電子メールを識別して分類する（１２６）か、又は電子メールの分類が曖昧であり、したがって、不確かな領域に分類されていると判断する等の一定の結果を生成する。これらの領域を図１ｃに図示する。図１ｃでは、電子メールは、クラスＡ１３８又はクラス〜Ａ１４４として指定された非Ａのいずれかにクラスタリングされている。図１ｃに示すように、電子メールが不確かな領域１４４にある場合、Ｋ−ＮＮ１２７が分類を処理する。電子メールが、プロセス１２７により判断ステップ１３３においてラベリング可能であると判定される場合、電子メールは、Ａ又は〜Ａによって表記されたいずれかのクラスとしてさらに判断されて（１２８）、記憶される（１３６）。電子メールがラベリング可能でない場合、ユーザには、電子メールのラベリングの判定オプション１３４が提供され、ユーザが電子メールにラベリングしないことを決定する（１３４）場合、ラベル「不確か」がステップ１３５において提供される。要約すれば、マシン学習には、分析を行うためにテキスト入力をベクトル空間にマッピングすることが必要とされる；各マシン（実際には、各ラベルＡ）には、Ａとしての資格を有するもの（what qualifies as A）及び〜Ａとしての資格を有するもののトレーニングセットが必要とされる。通常、電子メールの分類には、１０００個の事例で十分である。学習マシンは、適切にトレーニングされると、分類を開始する。
【００２５】
本発明の一実施形態は、類似の特性を有する電子メールをクラスタに入れる。均一フィルタハッシュ（uniform filter hash）又はスタック可能ハッシュは、テキストのクラスタリングを行うことができる。ＳＶＭ予測時間は、サポートベクトルの個数又は不確かなゾーンの点の個数に比例するので、予測時間は、不確かなゾーンの類似のデータ点をクラスタにグループ化することによって削減することができる。これらの類似のデータ点は、クラスタの中心によって表すことができる。
【００２６】
クラスタリング方法の使用は、ＳＶＭのアプリケーション及びＫ−ＮＮのアプリケーションに従う。ＳＶＭのアプリケーションは、グローバルマシン学習方法Ｋ−ＮＮであり、ＫＮＮのアプリケーションは、ローカルマシン学習方法である。クラスタリングは、クラスタの直径及びクラスタ間の距離の概念、又は分離を行うこのテーマにおける変形の概念を取り扱う。しかしながら、本発明は、（ｉ）トレーニング／前処理時間を最小にすること、（ｉｉ）分類の計算時間を最小にすること、及び（ｉｉｉ）クラスタ弁別精度を最大にすること、に関係するような新規なクラスタを形成する方法を検討する。図１ｄは、電子メールが、いくつかの方法、すなわち、Ｋ−ＮＮマシン学習方法、均一フィルタハッシュ方法、及びスタック可能ハッシュ方法のうちの１つを使用して電子メールを分類するのではなく電子メールをクラスタリングする方法を受ける本発明の一実施形態を示している。図１ｅは、クラスタの各位置が類似性メトリックに基づいているクラスタ分布の２次元空間を図示している。類似性メトリックは、たとえば、類似の主題のような特性の関数とすることができる（Vijayshankar Raman著「Locality preserving dictionaries: theory & application to clustering in databases」（In Proceedings of the eighteenth ACM symposium on Principles of database systems, pages 337-345. ACM Press, 1999）を参照されたい）。
【００２７】
一例として、以下の電子メールの写しは、同じクラスタに属するものとして考えることができる。
【００２８】
利用可能な学習マシンプロセスが、分類若しくはラベリングに関して使い果たされているか、又は代替的に、ユーザが電子メールを単にクラスタリングすること（１５６）を決定した場合、本発明のプロセスは、次に、図１ｄで説明したクラスタリング方法のうちの１つを使用する。ステップ１５０において、Ｋ−ＮＮ方法が使用される。代替的に、電子メールをクラスタリングする方法１５２は、以下でより十分に説明する均一フィルタ技術に基づく。方法１５４において、スタック可能ハッシュが、観察中の文書を、類似の電子メールのクラスタに入れる目的で電子メールを受信するクラスタプロセスの基礎を形成する。
【００２９】
均一クラスタ技術によって、どのクラスタが着信電子メールメッセージの母クラスタであるかの高速な判断が可能になる。スタック可能ハッシュ技術は、着信電子メールメッセージからの地理的ハッシュ（geographic hash）の作成を伴う。１つのアプリケーションでは、スタック可能ハッシュ技術によって、着信電子メールメッセージが最近の履歴のクラスタに属するか否かの高速な判断が可能になる。
【００３０】
均一フィルタはまず、ＡＳＣＩＩ文字から成る長いハッシュを計算する。均一フィルタの特徴的な特性は、入力における小さな変化が、第２のハッシュの長いハッシュ出力の各プレースホルダを、第１のハッシュの長いハッシュ出力の対応するプレースホルダと異ならせる可能性があるというものである。小さなハッシュ方法の有益な特性は、所与のクラスタ内のすべての電子メールが、原則として、同じ小さなハッシュ出力を有するものであるということである。
【００３１】
図１ｆでは、「Call me, OK!」という内容を有する電子メールが、シングリング（shingling）後にスタック可能ハッシュを生成する。この電子メールは、最初に英数字でないものを取り除くことにより前処理を行っており、次に、「遷移シングル（transition shingle）」を形成している。この遷移シングルには、次に、独自の「スタック可能ハッシュ」が適用される。この独自のスタック可能ハッシュは、各遷移シングルを四角形によって表されるクラスタの内部の単一の点にマッピングする。
【００３２】
図１ｇに示すように、スタック（すなわち、最近受信した入力電子メール／文書に対応するシートの集合）において頻繁に発生する点と一致する、着信電子メールメッセージのシートの点が多いほど、その電子メールメッセージはクラスタの一部である可能性が高くなるということが、スタック可能ハッシュの特性である。図１ｇでは、現在のシートの点は、スタックにおいて頻繁に発生する点に一致し、「ｏ」シンボルによって表記されている。
【００３３】
実際には、電子メールメッセージは、通常、図１ｆに示したような６つの遷移シングルよりもさらに多くの遷移シングルから成る。さらに、実際には、スタック可能ハッシュ方法は、図１ｆ又は図１ｇに示したものと比較して、はるかに高い解像度の四角形の格子を使用する。要するに、スタック可能ハッシュのパラメータ化と組み合わされた格子の選択は、衝突が実際には起こりそうにないような構成の重要な特性を提供する。
【００３４】
また実際には、英語に特有である、頻繁に発生するハッシュに対応する格子の点は取り除かれる。たとえば、上記のような３遷移シングルを使用すると、あらゆるスタックに頻繁に発生するものの、Ｔ−Ｈ−Ｅ、Ａ−Ｎ−Ｄ、Ｗ−Ｉ−Ｔ、Ｉ−Ｔ−Ｈ、Ｆ−Ｏ−Ｒに対応するハッシュ点は、着信電子メールメッセージが実際にスタックと意味のある類似性を有するか否かについての情報をほとんど与えない。
【００３５】
図２ａは、本発明の装置及び方法の概観をさらに示している。ブロック２０１ａにおいて、学習マシン技術及び関連する方法論が、本明細書で図１ａ及び図１ｂに関して説明したような１つ又は複数の学習マシン内に入力された電子メールを受信する。学習マシン技術２０１ａは、一般に明確な分類（well classified）２０１及び不確か２１１の２つの領域又はカテゴリーに分かれる分類の形で出力を生成する。学習マシン２０１ａからの出力に応じて、システムは、Ｋ−ＭＭ技術２０９の方法を使用して不確か２１１の電子メールを処理する等のためにどのさらなる処理ステップが必要とされるかについての決定を行う。さらなる処理ステップは、その後の検索のために分類を記憶すること（２０６）、分類をさらに改善する手段として分類を利用すること、又はスパムをブロックする等、管理目的で結果を使用するようにシステムのユーザに警報を出すことに及ぶ。
【００３６】
図２ａでは、均一ハッシュフィルタ技術２０２ａが、ブロック２０１ａに関して説明したような種類の電子データパターンをクラスタリングするのに利用される。データは、均一ハッシュフィルタ技術２０２ａの適切なレジスタ内に読み込まれ、特徴ベクトル２０２ｂの形でハッシュと呼ばれる結果を生成する。特徴ベクトル２０２ｂは、以下で詳細に説明する。ハッシュに関するさらなる処理ステップは、その後の検索のために電子メールをクラスタ内に記憶すること（２０７）又はクラスタ内に入れることに及ぶ。ハッシュの他の用途は、識別された属性を有する文書をブロックする等、管理目的で結果を使用するようにシステムのユーザに警報を出すことである。
【００３７】
図２ａでは、スタック可能ハッシュ技術２０３ａが、ブロック２０１ａ及び２０２ａに関して説明したのと同じ種類の電子データパターンをクラスタリングするのに利用される。データは、スタック可能ハッシュ技術２０３ａの適切なレジスタに読み込まれ、文書をクラスタリングするのに使用される幾何ベクトル又はハッシングベクトルを生成するスタック可能ハッシュと呼ばれる結果を生成する。これについては、以下で詳細に説明することにする。ハッシュに関するさらなる処理ステップは、その後の検索のためにクラスタを記憶すること（２０７）、クラスタリングをさらに改善する手段を利用すること、又は識別された属性を有する文書をブロックする等、管理目的で結果を使用するようにシステムのユーザに警報を出すことに及ぶ。
【００３８】
本発明の方法は、ハッシング技術２０２ａ及びスタック可能ハッシュ技術２０３ａに関連して学習マシン技術２０１ａを利用する。好都合であると判明した学習マシン２０１ａは、パターン認識の技術分野で既知であり、本発明に関係するように、ローカルマシン学習に関してＳＶＭ最近傍プロセス、ＮＢ最近傍プロセス、並びにＮＮ最近傍プロセス及びＫ−ＮＮ最近傍プロセスとしてカテゴリー化される。しかしながら、図のように、学習マシン２０１ａは、すべてのタイプの電子データストリームを、所与のアプリケーションにとって十分に分類しない場合があり、したがって、これらの方法は、特定のアプリケーションによって必要とされる分類のレベルが達成されるまで、他の方法と組み合わされる。学習マシン技術の圏内では、教師有り学習が、トレーニングデータから関数を作成するためのマシン学習技法である。このトレーニングデータは、数対の入力オブジェクト（通常はベクトル）及び所望の出力から成る。関数の出力は、連続値（回帰と呼ばれる）とすることもできるし、入力オブジェクトのラベル（分類と呼ばれる）を予測することもできる。教師有り学習器のタスクは、比較的少数のトレーニング例（すなわち、数対の入力及びターゲット出力）を観察した後にあらゆる有効な入力オブジェクトの関数の値を予測することである。これを達成するために、学習器は、観察されたデータ又は提示されたデータから観察されていない状況又は未知の状況まで、「論理的に妥当な」方法で一般化しなければならない。
【００３９】
本発明は、ブースティングを使用する。このブースティングは、ロジスティック回帰の最大エントロピー方法に関係する。ブースティングは、現在の学習結果の関数を徐々に増大させることによって段階的に行われる。あらゆる段階で、弱学習器（すなわち、偶然と同程度に乏しい精度又は偶然よりもわずかに良い精度を有することができる学習器）が、データでトレーニングされる。弱学習器の出力は、次に、（弱学習器がどれくらい正確であるかに比例する）或る強度で、学習結果の関数に追加される。次に、データが再加重される。現在の学習結果の関数が間違える例は、重要度において「ブースト」され、その結果、その後の弱学習器は、エラーを訂正しようと試みることになる。上記は、多くの異なるブースティング方法のうちの１つを説明したものであり、最終的には、強度及び重みの正確な数学的形式、たとえば、関数空間で勾配降下を行うブースティング、及び正しい学習に基づくブースティング、に依存する。
【００４０】
２つ以上の分類器が利用される場合、ラベリングを実施するのに使用される次のステップは、（１）異なるデータセット又は同じデータセットを使用して複数の分類器をトレーニングすること、（２）より大きなトレーニングセットからランダムにサンプリングし、分類器として多数決を使用すること、（３）各分類器が異なるゾーン（明確な分類領域及び不確かな領域）で特殊化される一組の異なる分類器を使用すること、である。
【００４１】
学習マシン２０１ａは、一定の入力タイプの電子データパターンを分類するその能力に応じて使用される。場合によっては、３つ以上の分類器が、１つの入力を分析する際に同時に使用され得ることが考えられる。このような場合には、単純な多数決が、電子メールのクラスを決定することになる。それ以外の場合には、統計分析又は回帰分析に基づくより複雑な分析を使用され得る。さらに、一例として、Ａと表記される或る分類器が、ブロック２１０及び２１１によって規定されるような特定の領域で分類器Ｂよりも優れている場合、システムは、使用される学習マシンによって生成される定量的な結果の関数を使用せず、Ａからの分類別の予測のみを使用するように構成してもよい。代替的に、システムは、すべての学習マシンを使用することもでき、すべての学習マシンが分類出力において異なる場合には、多数決による決定方法を使用して、電子メールにラベリングすることができる。ＳＶＭが安定したグローバル分類器であり、領域が分離面から遠く離れている場合、明確な分類２１０等の明確な分類領域において他のほとんどすべての学習マシン方法よりも高い精度で機能する傾向があることは既知である。不確かな領域２１１では、ＳＶＭは、Ｋ−ＮＮを使用するローカル方法よりも良好でない場合がある。これは、特に、データセットが、分離面に近い複雑なローカル構造を有する場合に当てはまる。このような場合、ＳＶＭは、非常に高次元のカーネルを使用して、複雑なローカル構造を取り扱わなければならない一方、Ｋ−ＮＮ及びニューラルネットワークを使用するローカル方法は、このローカルな複雑さを解決するのにより良いものとなり得る。異なる分類器の組み合わせは、それ自体でエキスパートシステムである。このエキスパートシステムは、特定の体制又は領域の分類においてそれぞれより良い一組のエキスパートとして動作する。各領域では、特定の分類を行うように特定のエキスパートを選択してもよい。
【００４２】
上記解説から、２つ以上の分類器が存在し、それらの分類器のそれぞれが或る領域において他のあらゆる分類器よりも高い精度を有する場合、それらの分類器の組み合わせによって精度が改善される。一方、精度のブースト量は、電子メールの一定のデータセットにおいて必要とされるほど高くない場合がある。一例として、これは、不確かな領域２１１のＳＶＭの難しい点が、他の学習マシン分類器にとっても難しいとの理由による場合がある。Ｋ−ＮＮ及びニューラルネットワークは、不確かな領域２１１のＳＶＭよりも約５％〜１０％良い精度を有することができ、したがって、精度のブーストは３％〜７％からであることが見出された。学習マシン分類器のパラメータを慎重に選択することによって、わずかに高い精度のブーストを達成できることが予想される。
【００４３】
パターン認識の技術分野の熟練者（当業者）は、サポートベクトルマシンを理解している。サポートベクトルマシンは、電子データストリームの処理に関係するタスク等の幅広いタスクにおいて優れた分類精度をもたらす（Scholkopt他著「Advances in Kernel Methods-Support Vector Learning」（MIT Press, Cambridge, Mass., 1999）及びVapnik著「The Nature of Statistical Learning Theory Statistical Learning Theory」（Springer, N.Y. 1995）を参照されたい）。
【００４４】
本発明の一実施形態では、多変量出力を予測するためのＳＶＭアルゴリズムは、ラベリングされたトレーニング例（ｘ１，ｙ１）、…、（ｘｎ，ｙｎ）を使用してマッピングｈ：Ｘ→Ｙを近似することにより教師有り学習を実行する。本発明のＳＶＭは、決定木、決定シーケンス、決定集合等の複合オブジェクトｙを予測する。複合出力を有する問題の例は、自然言語の構文解析、タンパク質相同性検出における配列アラインメント、及び品詞タグのマルコフモデルである。
【００４５】
ＳＶＭは、異なる種類の複合予測アルゴリズムを実施するためのアプリケーションプログラムインターフェースとして実施することができる。マルチクラス分類は、ｋ個の相互排他的なクラスのうちの１つを予測することを学習する。一方、ＳＶＭが、各クラスＣを分離して、Ｃであるものの例及び〜Ｃであるものの例でトレーニングを行うのに使用される場合、発明者は、ＳＶＭが相互排他条件を未然に回避することを発見した。
【００４６】
代替的な一実施形態では、ナイーブベイズ分類器が、ベイズルール、ベイズルールを近似したもの、又はベイズルールを変更した他の任意のものに基づいてパターンを分類する。ベイズルールの下では、属性（ハッシュ等）は、ラベル（スパム、スパム無し、納税申告、納税申告なし）を決定する際に分類器によって条件付きで独立であると仮定される。この条件付き独立性は、完全条件付き独立性であると仮定することができる。代替的に、完全条件付き独立性の仮定は、分類器の精度又はさらに他の設計基準を最適化するように緩和することもできる。したがって、分類器には、完全条件付き独立性を仮定するナイーブベイズ分類器が含まれるが、これに限定されるものではない。各属性値についての各ラベル値の「条件付き確率」は、所与のラベル値を有する記録からのみ選択されたランダム記録がその属性値を取る条件付き確率である。ラベル値の「事前確率」は、元のデータ（トレーニングセット）のラベル値を有する記録の割合である。「事後確率」は、選択された属性値（複数可）の組み合わせが与えられたラベル値の予測分布である。
【００４７】
図２ｂ及び図２ｃは、本明細書で説明されるような電子メールやその構成体等の電子データパターンの２つ以上のクラスを示すデータの分類、カテゴリー化、及び重み付けを行うアルゴリズムをモデル化するように構成される学習マシン２０１ａを示している。分類器は、ネットワークのアクティブなコンポーネント２０１ｃへの入力に適したベクトル等の形に電子メールを変換するように前処理される第１の入力２０１ｈを表すデータをカテゴリー化して重み付けする。
【００４８】
学習マシン科学及び学習マシン工学の技術分野の熟練者（当業者）は、トレーニングされたネットワークに対する多くの方法を知っているが、本明細書で示すものは、バックプロパゲーションと呼ばれる。図２ａを参照すると、ネットワークは、ステップ１において電子データストリームのベクトルを取り入れ、それをシステムを通じて供給し、ステップ２において出力の数値を求める。次に、ネットワークは、より正確な出力を得るためにステップ３において重みを変更する。ネットワークは、ネットワークの出力とネットワークに与えられた出力との間の誤差が規定の許容レベル未満となるまで、入力を複数回ネットワークに通し続ける。トレーニングが完了した後、ニューラルネットワークには、当該ニューラルネットワークが前にさらされたことがない電子メール表現が提供される。ニューラルネットワークは、次に、トレーニング中に作成した重みに基づいて分類を予測する。
【００４９】
本発明のネットワークの一実施形態を、ネットワークの１つの要素を詳細に表す図２ｃに示す。このネットワークの１つの要素は、モデリングアルゴリズムを使用して、電子メールや、本明細書で説明したようなハッシュ等の電子メールの構成体等の電子データパターンの２つ以上のクラスを示すデータの分類、カテゴリー化、及び重み付けを行う。図２ｃに示すように、バックプロパゲーションは３つのステップから成る。電子メール２０１ｈの文字値のベクトル２０１ｇは、プロセッサ２０１ｂによって組み立てられ、学習マシン２０１ａの入力レイヤ２０１ｊに提供される。入力２０１ｊは、出力２０１ｅに到達するまでネットワーク２０１ｃを通じて伝播される。これによって、実際の出力パターン又は予測された出力パターンが生成される。実際のネットワーク出力は、所望の出力から引かれて、エラー信号が生成される。エラーは、隠れた各処理ユニット（each hidden processing unit）の貢献を計算して、所望の出力を生成する重み付けされた調整を導出することによりネットワークを通じて戻される。単一の付加的レイヤを追加することによって、通常ならば線形のニューラルネットワークを非線形ニューラルネットワークに変換することができる。非線形ニューラルネットワークは、多変量ロジスティック回帰を行うことができる。
【００５０】
分類器の一例は、第１の入力２０１ｊ（１）及び１つ又は複数の追加入力２０１ｊ（ｎ）を表すデータをカテゴリー化するとともに重み付けする。トレーニングフェーズ及び実行フェーズのそれぞれの期間中に、それぞれの入力２０１ｊ（１）及び１つ又は複数の追加入力２０１ｊ（ｎ）には、事前に割り当てられた重み２０１ｋ（１）及び１つ又は複数の追加入力２０１ｋ（ｎ）がそれぞれ乗算される。合計接点２０１ｆにおいて、データは、それぞれの入力２０１ｊ（１）及び１つ又は複数の追加入力２０１ｊ（ｎ）並びに重み２０１ｍからの入力の差を形成する。この差は重み付き差と呼ばれる。複数のこのような重み付き差は、出力２０１ｅが２０１ｍにおいてバックプロパゲーションされる時に、重み付き差がノード２０１ｆにおいて最小値を生成するようなシグモイド伝達関数を有するプロセッサ２０１ｄにおいて加算される。基本的には、プロセッサ２０１ｃは、電子メールや、ハッシュ等の電子メールの構成体等の２つの異なる電子データパターンのレベルを表す１つ又は複数の入力の重み付き和を計算するように動作する。より詳細には、既知の特徴を有するトレーニング電子メール２０１ｈｅｔ（ｔ）は、重み付けノード２０１ｋ（１）及び１つ又は複数の追加ノード２０１ｋ（ｎ）に供給され、出力ｅｏ（ｔ）２０１ｅは、２０１ｍにフィードバックされて、ノード２０１ｆがプロセッサの出力ｅｏ（ｔ）２０１ｅを強制的にゼロにするような調整を行う（２０１ｐ）。そのように、プロセッサ２０１ｄ（通常はシグモイド関数）は、重み２０１ｍを適切に設定し、さらにノード２０１ｆを適切に設定することによってゼロ出力（zero out）する。未知の電子メール２０１ｈｅｕ（ｔ）が２０１ｊ（１）及び１つ又は複数の追加入力２０１ｊ（ｎ）に供給された場合、出力ｅｏ（ｔ）２０１ｅは、Σすべてのｎ（Ｗ２０１ｊ（ｎ）＊ｅｕ（ｔ）＋Ｗ２０１ｍ）＊ｅｏ（ｔ）＋Ｋｂ＞０となる。ここで、Ｗ２０１ｊ（ｎ）は、入力重み付けノード２０１ｊ（１）〜２０１ｊ（ｎ）に対応し、Ｗ２０１ｍは、電子メールやその構成体等の２つの異なる電子データパターンの重み付けノード２０１ｍに対応する。定数Ｋは、しきい値として使用することができる。
【００５１】
クラスタは、ほとんど同一のオブジェクトから成る。図２ａに示すように、本発明のＫ−ＮＮプロセスの方法は、クラスタがどこに配置されるかを決定する。この方法は、非母数の教師有りパターン分類に教師有り分類ルールを使用する。分析の目的で次元ｍのベクトルに削減されている電子メールの多様性を有するクラスタ内の既知のパターンの知識、及び、いくつかのクラス内へのそれらの正しい分類が与えられると、Ｋ−ＮＮルールは、アプリオリ（未分類パターン）を、学習ネットワークによって失敗した分類に従う不確かな又はあいまいな点のクラスタに存在し得るような、或る関連空間におけるそのｋ最近傍の中で最も厳しく表されるクラスに割り当てる。特に、トレーニングサンプル数が、ｋと比較して十分大きい場合、分類エラーは、通常、対象空間の異なるクラスのオーバーラップを特徴付けるベイズリスクよりも（１＋１／ｋ）倍大きくなる。Ｋ−ＮＮ方法はパターン分類技法として、パターン認識の技術分野の熟練者（当業者）に既知である（Buttrey (1998): Buttrey, S.E.著「Nearest-Neighbor Classification with Categorical Variables」（Computational Statistics and Data Analysis, Vol. 28, No. 2, (1998), pp. 157-169）を参照されたい）。Ｋ−ＮＮ処理の背景にあるアイデアは、電子メール等の電子データパターンに関する類似の観察結果が類似のクラスタに属するということである。
【００５２】
Ｋ−ＮＮの方法は、文書分類及び文書クラスタリングの両方に使用することができる。前者の用途では、分類タスクは、ラベリングされた又は識別されたトレーニング文書が必要である所定のクラスを必要とする。後者の場合、すなわち、クラスタリングは所定のクラスを必要としない。その目的は、文書をクラスタリングする際に使用されるような、類似度に基づくオブジェクトのグループ化を求めることである。
【００５３】
他の既知の類似の尺度には、特に、コサイン距離又はユークリッド距離、ジャッカード係数又は抑制係数（containment coefficient）が含まれる。分類されたテキストには、そのｋ最近傍の中で最も一般的なクラスが割り当てられ、ｋ＝１の場合に、観察中のテキストには、類似の尺度によって規定されたようにそれに最も近いアプリオリなサンプルのクラスが割り当てられるようになる。
【００５４】
本発明のＫ−ＮＮクラスタ分類方法は、次のステップ、すなわち、（ａ）任意の２つの文書間の「類似度を測定するメトリックを規定するステップと、（ｂ）実験に基づいて定数ｋを確立するステップと、（ｃ）観察対象のサンプルを観察するステップと、（ｅ）事前に分類された点のトレーニングセットステップと、（ｆ）トレーニングセットに最も近いデータｘに対するｋ最近傍（Ｋ−ＮＮ）を突き止めるステップと、（ｇ）他のどのクラスよりもクラスｙに最近傍のより多くのものが存在する場合に、データｘをクラスｙとして分類するステップとを含む。
【００５５】
ハッシュ技術
スタック可能ハッシュ
本明細書で使用されるクラスタリング方法は、この実施形態における「境界」点又は「不確かな」点のメンバーシップを明確にするためのものである。通常のクラスタリング方法は、クラスタ分離、クラスタ半径、及び関係する量を最小にする目的で設計されるが、説明するようなハッシュ方法の使用は、さらにインデキシング解決法（indexing solution）を可能にする。図２ａは、スタック可能ハッシュ技術２０３ａを示している。このスタック可能ハッシュ技術２０３ａは、文書を或るクラスタに入れるものであり、その文書がメンバーである特定のクラスタを識別するものではない。分類器２０３ａは、２５６個の８ビットバイトから成る各記録を、電子データストリームの離散的な部分として読み込む。この電子データストリームは、通常、個々のオーバーラップする８ビットバイトのシングル（shingle）に区画される。オーバーラップするシングルは、次に、分類器２０３ａに提供される。分類器２０３ａは、特定の電子データストリームがスパム等の対象オブジェクト又は対象パターンを含むか否かを確かめるように構成又はプログラミングされている（ただし、分類器は、他のオブジェクト又はパターンを検出するのに使用できることが十分理解されよう）。各電子データストリームについて、システムは、電子データストリームがスパム等のパターンに対応するか否かを判断する。分類出力を提供するために、何が識別された属性を有する文書であるのか、又は何が識別された属性を有する文書でないのかを規定する「空間」に対して、各電子データストリームを評価しなければならない。
【００５６】
図２ｄに示すように、本発明の一実施形態は、任意選択的な「スタック可能ハッシュ」Ｓ（ｋ）も含む。このＳ（ｋ）によって、スタック可能ハッシュクラスタの作成が可能になる。図２ｄでは、ｎ個の文字を有する通常の電子メール送信で見ることができるようなデータｘｉ、ｘｉ＋１、…ｘｉ＋ｎとしてさまざまに示される８ビットバイトのＡＳＣＩＩ文字の形式の電子データストリームＸが、１つ又は複数の離散的な入力データレジスタ２０３ｃ内に入力として受信される。
【００５７】
隣接するデータ要素を使用してデータ要素Ｘ∈｛ｘ｝を１つの位置又は１バイトだけシフト又は移動する技法は、シングリングと呼ばれ、従来技術で見られる技法である。これらのシングルは、基本的に、テキスト文字列のローカル分析の最も基本的な要素を形成する。あらゆる電子メール文書は、本明細書ではシングルと呼ばれる、トークンの一組の部分列から成り、一例として、文字「a and b」は２シングルを形成し、「a, b, and c」は３シングルを形成する等のようになる。図２ｄに示すように、電子文書の電子データストリームＸ２０３ｂを有する文書の情報内容を表すデータ要素２０３（１）、２０３（２）、及び２０３（３）を有するデータが、入力レジスタ２０３ｃ内にシリアルに受信される。この電子文書の電子データストリームＸ２０３ｂは、たとえば、
（ａｂｃ，ｃｄｅ，ｄｅｆ，ａｅｆ，ｄｅｒ，ａｂｆ）
｛（ａｂｃ，ｃｄｅ，ｄｅｆ），（ｃｄｅ，ｄｅｆ，ａｅｆ），（ａｅｆ，ｄｅｒ，ａｂｆ），）｝
の３シングリングとして一組のオーバーラップするデータを関連付けることができる。
本発明の一実施形態では、計算機２０３ｄによって提供される数学関数は、３つの隣接する８ビット文字を受け取るように構成されている。これらのデータから、必要とされる数値結果が計算される。データｘｉ、ｘｉ＋１、及びｘｉ＋２は、数学関数Ｓｋを提供するように構成される計算機２０３ｄに入力を提供する。数学関数Ｓｋは、数値結果Ｓ（ｋ）を生成する。数値結果Ｓ（ｋ）は、代替的に、ハッシュ値又は幾何学的ハッシングベクトルと呼ばれる。すべてのハッシング方法の基本概念は、それらのハッシング方法がハッシュ値をシングルに関連付けるということであることに留意すべきである。本明細書で説明するようなスタック可能ハッシュの場合には、それらのハッシング方法は、ハッシュ値を遷移シングルに関連付け、他の方法の場合には、それらのハッシング方法は、ハッシュ値をスーパーシングル（super-shingle）又は他の関係する構成等の他の分解した単位に関連付ける。
【００５８】
ハッシュ出力は、入力ｘｉ、ｘｉ＋１、及びｘｉ＋２から形成される。ここで、ｉ＝１である。数値結果が計算されると、新たなトリオの隣接するデータ要素ｘｉ＋１、ｘｉ＋２、及びｘｉ＋３がデータレジスタ２０３ｃにロードされる。これらの新たなデータ要素ｘｉ＋１、ｘｉ＋２、及びｘｉ＋３は、次に、算術論理ユニット２０３ｄ並びに数学関数２０３ｆ、２０３ｇ、及び２０３ｈへの入力として利用されて、数学プロセッサ２０３ｊへの入力としてシングリングが生成される。数学プロセッサ２０３ｊは、入力２０３ｅとして、通常は素数である任意選択の追加パラメータを有し、幾何ベクトル結果Ｓｋを形成する。特定の数学関数が、公式又はアルゴリズムによって決定され、入力、及び場合によっては１つ又は複数の任意選択のパラメータ２０３ｅに対して操作を行うように選択される。この任意選択のパラメータ２０３ｅは、数値結果を計算するようために選択された確率変数Ｒ、又は主要なハッシュ表のサイズを削減する素数等である。データソース｛ｘ｝∈Ｘからオペランドｘｉ及びｘｉ＋１、ｘｉ＋２、…ｘｉ＋ｎを形成する他の方法の使用が有利であることが分かるので、シングリングは本発明の要件ではない。特に、シングル（又はシングリング）技法と共に本明細書で説明したような数学関数Ｓｋの選択方法は、説明するように新規である。
【００５９】
一般に、本発明のＳｋを生成する計算機２０３ｄは、可変長の文字列を生成する。しかしながら、一実施形態では、出力Ｓ（ｋ）は、０〜２５５の範囲又は代替的に１〜２５６の数値である。計算Ｓ（ｋ）の対は、ｘ−ｙ平面の一対のデカルト座標になる。この平面における各ｘ、ｙエントリーは、単位値として表され、基本的に、点の２次元ヒストグラムを作成する。ヒストグラムの振幅は、特定の３−ａｒｙ（3-ary）シングルの発生頻度として特徴付けられる。
【００６０】
開示されるスタック可能ハッシュ方法は、（ａ）一組の文書から複数のハッシングベクトルを受信するとともに、当該サンプルハッシングベクトルをランダムアクセスメモリに記憶するステップと、（ｂ）データレジスタに、受信された文書からの少なくとも２つの隣接するデータ要素をロードするステップと、（ｄ）ハッシュ手段を利用して電子メールハッシングベクトルを計算するステップと、（ｅ）電子メールハッシングベクトルを複数のサンプリングされたハッシングベクトルと比較するステップとを含む。
【００６１】
スタック可能ハッシュを作成することは、クラスタの兄弟のようなメンバーを見つけるのにハッシュ空間を探索する必要がないという観点から重要である。図１ｅに示すように、本発明の一実施形態は、説明したようにシングリングされた多数の電子メール文書を形成し、その結果は合成ヒストグラムを形成する。合成ヒストグラムを形成する電子メール文書の個数は、１つから任意の個数に変化し得る。しかしながら、エージングプロセス（aging process）が、ヒストグラムの増大の安定化を達成できることが判明した。ここで、最も古い文書は蓄積から取り除かれる。一方、全体のラベリングの目的に貢献できない文書、たとえば、文書が全体として１文字しか含まないので何ら情報を与えない文書を捨てる等の、他の基準を使用することもできる。
【００６２】
文書の集合の視覚化は、一般に、クラスタリング又は文書の集合に焦点を当てた独自の空間変換技法に基づいている（１９９８年８月１１日に出願された「Visualization of Information using graphical representations of context vector based relationships and attributes」と題する米国特許第５，７９４，１７８号を参照されたい。この米国特許は、アイテム間の概念関係を表すコンテキストベクトルを生成し、さらに、視覚表現及びグラフィカル表現を使用してテキスト情報の理解及び使用を容易にする）。
【００６３】
図１ｄ及び図２ａに示すようなスタック可能ハッシュの特徴は、その目的として、リアルタイムで「バーストされる」クラスタを捕捉することを有する。さらに、図１ｅによって示されるようなヒストグラムは、文書のクラスの識別がヒストグラムに含まれる統計値に基づいて行われる有益な関数を提供する。資力調査（means test）や変動調査（variance test）等の技法の多くが適用可能である。しかしながら、発明者は、振幅の１つ又は複数のしきい値が、少なくとも、リアルタイムで「バーストされた」電子メールの多数の異種クラスを特定するのに役立つことを見出した。
【００６４】
図１ｅは、部分分布１７０、１７５等の部分分布をより大きなｘ−ｙ平面に形成する計算されたシングルの重要なクラスタを示す１つ又は複数の矢印１７２を示している。本発明の方法は、四角形の十分に高解像度の格子上の低衝突のハッシュを利用する。限定ではなく説明として、図１ｅのｘ−ｙ平面が９９７×９９７の方形格子によって規定されているものと考える。たとえば、入力Ｓ−Ｅ−Ｔ−Ｈを選ぶ。２シングルはＳＥ、ＥＴ、及びＴＨである。しかし、２つの遷移シングルＳＥ→ＥＴ及びＥＴ→ＴＨしか存在しない。その結果、出力マトリクスは２つのハッシュエントリーしか含まない。文字として、これらの２シングルは、それぞれ６５５３６ビットのストレージに値する。これは実用的でない場合がある。一般に、Ｓ−Ｅの整数表現を選び、その整数表現をその等価クラス（モジュロＰ）と同一視することがより効率的である。ここで、Ｐは適度に大きな素数である。本発明の目的のために、Ｐ＝９９７を選ぶ。これは、最小の衝突確率を関連付けて実験的に見出されたものである。その結果、本発明が一実施形態で利用するマトリクスは、サイズが９９７×９９７である。
【００６５】
一続きのシングル１２３４５６→２３４５６７を有する場合、それらのシングルを、素数、たとえば９９７によってより小さなサイズにハッシュすることができ、次に、上記シングルの一続きのハッシュは、素数によって除算された数値である８２５→２７２になり、それによって、余りは、より小さな２Ｄ表に適合される。２８又は１０３等の非素数（すなわち、合成数）以外の素数を使用することによって、ハッシュ値のクラスタリングの確率を低減することができる。すなわち、ハッシュ値は、表にランダムに一様に分散する傾向にある。
【００６６】
簡単な例として、１６進数０ｘ？？００％０ｘ０１００（すなわち２＾８）＝０を考える。この場合、最初の文字の変更はハッシュ値を変更しないので、？？の値は、結果に影響を与えない。さらに、衝突の確率は非常に高い。
【００６７】
本発明のスタック可能ハッシュの特徴は、当該スタック可能ハッシュを他のハッシング関数と区別する次の特性を有する。すなわち、（ａ）ハッシング符号は、大きなマトリクスによって表され、この大きなマトリクスは、点在する非ゼロのエントリーを有する、（ｂ）ハッシュの各エントリー（すなわち、マトリクスのエントリー）は、テキストメッセージの或る場所の或る符号化されたローカル情報を表す、（ｃ）２つのテキストメッセージが無関係である場合に、オーバーラップされた非ゼロのエントリーの個数は確率が小さいが、２つのテキストメッセージが或る類似性を共有する場合に、オーバーラップされた非ゼロのエントリーの個数は確率が高い、（ｄ）複数の文書又はメッセージのハッシュをスタックすることによって、共有されたテキストセグメント又は類似のテキストセグメントに対応するハッシュエントリーが強調される。
【００６８】
ヒストグラムのピークの構築は、「輝度」関数を関連付ける効果がある。この輝度関数は、シングリングにオーバーラップ量が発生するにつれて値が増加する。また、輝度関数は、時間が経過するにつれて値が減少する。このように、「エージング（aging）」関数が取り入れられる。
【００６９】
以下の実施形態では、本発明のスタック可能ハッシュの特徴は、素数によって除算することによりマトリクスのサイズの削減をさらに示す既知のソースコードで実施される。
function [deg1, deg2] = similarity(s1, s2)
% FUNCTION [deg1, deg2] = SIMILARITY(s1, s2)
% 目的：２つの文字列の類似度を比較する
%
% 入力：
%     ｓ１−文字列１
%     ｓ２−文字列２
% 出力：
%     ｄｅｇ１−類似度の上限値
%     ｄｅｇ２−類似度の下限値
% グループとしてのバイト数
bytes = 3;
P = 997; % ハッシング用の大きな素数
M = zeros(P, P); % 空の２次元遷移グラフを作成する
len1 = length(s1);
len2 = length(s2);
% 長い文字列を最初のものと交換する
if(len2 > len1)
temp = s1;
s1 = s2;
s2 = temp;
temp = len1;
len1 = len2;
len2 = temp;
end
% グラフを作成する
for i=1:len1-3
d = double(s1(i:i+3))+1;
x = rem(d(1)*256+d(2), P)+1;
y = rem(d(3)*256+d(4), P)+1;
M(x,y) = M(x,y)+1;
end
% 文字列を比較する
common = 0;
for i=1:len2-3
d = double(s2(i:i+3))+1;
x = rem(d(1)*256+d(2), P)+1;
y = rem(d(3)*256+d(4), P)+1;
if(M(x,y)>0)
common = common+1;
end
end
deg1 = common/max([1, len1-3, len2-3]);
deg2 = common/max(1, min(len1-3, len2-3));
return
【００７０】
クラスタとして記憶されている文書の蓄積を作成するためのコンピュータ方法は、文書クラスタを識別する目的で、クラスタをしきい値のｎ次元マトリクスと比較するマスクの作成をさらに含む。図１ｅに示すような２次元では、図１ｈに示すようなマトリクスは、マスク及び関係する文書の２次元クラスタの交わりを作成するのに適した２値の２次元ビットパターンである。クラスタリングされた着信電子メール１９２は、クレンジングマスク（cleansing mask）１９４との論理的な交わりを求めることができ、クレンジングされた電子メールクラスタ１９６が生成される。より高い次元のクラスタ空間では、クラスタ空間と同じように番号付けするいくつかのマスクが、関連する空間との交わりをペアワイズで形成することができる。
【００７１】
スタック可能ハッシュを利用する本発明は、（ａ）２進符号化メッセージを数値に変換すること、（ｂ）数学関数に提供される数値に基づいたベクトルを計算すること、及び（ｃ）ハッシングベクトルの値と記憶されているベクトルとの差を比較することを含む識別された属性を有する文書を検出するためのコンピュータ方法を含む。
【００７２】
また、スタック可能ハッシュを利用する本発明は、（ａ）２進符号化メッセージを一組の数値に変換する手段と、（ｂ）数学関数に提供される数値に基づいたハッシングベクトルを計算する手段と、（ｃ）ハッシュベクトルの値と記憶されているベクトル又は記憶されているベクトルを表すダイジェストとの差を比較する手段と、（ｄ）比較に基づいてスパムメッセージにヘッダを付加する手段とを備えるメッセージを検出するための装置も含む。
【００７３】
均一フィルタ方法
類似の分類に電子メールをクラスタリングする目的で、本発明の一実施形態は、（ｉ）小さなハッシュしきい値、（ｉｉ）小さなハッシュ長、（ｉｉｉ）小さなハッシュ平均、（ｉｖ）チェックする電子メール数、及び（ｖ）データベース／サブコーパスの選択、（ｖｉ）長いハッシュのしきい値の選択の方法を実行する。これらのプロセスを以下でさらに説明する。
【００７４】
本発明で利用される均一フィルタ技術は、類似のメッセージダイジェストを有する２つのメッセージが同じ特徴ベクトル値を生成できることが計算的に可能であるような連続関数を提供する。しかしながら、事前に指定された所与の目標のメッセージダイジェストを有するあらゆる任意のメッセージを生成することは計算的に可能でない。均一フィルタでは、以下で明らかになるように、少数の初期化されたサンプリング関数しかマトリクスルックアップ及び加算演算の要件を満たすのに必要とされないので、競合する方式と比較して、必要とされる計算オーバーヘッドは比較的小さい。加えて、それらは効率的に符号化することができ、スパムの識別及び管理以外の多数の用途に有用である。
【００７５】
本発明のハッシュ技術は、ファジーハッシュ、局所性保存ハッシュ、及び局所センシティブハッシュ（locality-sensitive hash）の分野における革新を表している。したがって、本発明のハッシュ技術は、静的データベース又は動的データベースのオブジェクト間の正確な距離及びおよその距離を求める。ハッシュ技術ハッシュ空間の探索は、元のデータベースを探索するよりもはるかに高速である。本発明の一態様は、メッセージがＳＭＴＰ等の任意のタイプのプロトコルで電子メールメッセージを受信するように構成されるサーバコンピュータによって受信されると、特徴ベクトルを生成する。本発明は、一例として、スパムを検出するための方法及び装置を利用するが、均一フィルタのパラメータを変更することによって、他の適用も可能である。限定ではなく一例として、本発明は、（１）農業・数学政策（agriculture-mathematics-politics）及び農業・数学技術等のテキストクラスタリング、（２）数億個の写真のアーカイブの選択されたテンプレート画像に類似のデジタル写真を見つけるための画像クラスタリング、及び（３）同様の方法でデジタルサウンド／音楽ファイルを識別するためのサウンドクラスタリングを可能にする。
【００７６】
本発明は、電子メールに対して操作を行って特徴ベクトルを構築する均一フィルタにより生成される連続関数によって計算されたメッセージハッシュ又はハッシングベクトルを作成する。特徴ベクトルは、メッセージがわずかに変化しても大きく変化しない。一実施形態では、電子メール特徴ベクトルは、その後の電子メール特徴ベクトルを比較するためにテンプレートとしてメモリに記憶される。実験及び分析を通じて、本発明者らは、識別された属性を有する文書が或る誤差のマージン内で類似の特徴ベクトル又は同等の特徴ベクトルを共有することを見出した。
【００７７】
本明細書の発明は、コンピュータ方法及びシステムを備える。このシステムは、特徴ベクトルを生成する均一フィルタを利用して、カテゴリーに対する電子メールのダイジェストを作成する。その後、ダイジェストを生成するフィルタと同一の特徴を有するフィルタが、ダイジェストと比較することによって電子メールを分類するために、電子メールの特徴ベクトルを作成する。一実施形態では、本発明の方法は、二組の特徴ベクトルを分離する距離しきい値を比較することによりそれらの二組の特徴ベクトルを比較し、それによって、それらのしきい値により規定された数値範囲内に入る（スパムにより表すことができるような）肯定的な着信メッセージ識別情報（positive incoming message identification）を生成する。このしきい値が高いほど、メッセージが類似しているとみなされる蓋然性は高くなる。しきい値が２５５に等しい場合、すべてのメッセージは類似しているとみなされる。他方、しきい値が０に等しいと、同一の電子メールしか選択されない。１３のしきい値が、電子メールを弁別するのに最適な値であることが見出されている。
【００７８】
一実施形態では、コンピュータシステムは、リアルタイム環境でスパムをフィルタリングする実行時の性能を可能にする目的でセンドメールプロトコル及びフィルタプロトコル（sendmail and filter protocol）を利用する。
【００７９】
概観として、図３ａは、増加するフィルタ数についてプロットされたしきい値の関数としての電子メールの総数を表している。プロットは、フィルタ数が増加するにつれて、関数が普遍関数に近づくことを実証している。図３ｂは、或る範囲のしきい値を利用するスパムクラスの相対度数をプロットしている。相対度数分布のモードは、約１３のしきい値で生じる普遍関数における強い共鳴を示す。詳細には、本発明者らは、図３ｂから分かるように最適なしきい値が２５５よりもはるかに小さいことに気付いた。マルチフィルタセットで実現される１つの重要な特徴は、特性が普遍であるという特徴である。できるだけ多くのフィルタを使用することが最も信頼性のあるフィルタリングを生み出すように見えるかも知れないが、本発明者らは、電子メールが通常約２００文字の長さである場合に、１００個のフィルタが、電子メールのスパムクラスを認識するのに十分な程度のフィルタリングを提供することを見出した。電子メールの他のクラス及び他の長さの電子メールは、したがって、特定の用途に必要な程度のフィルタリングを提供するのに、１００個よりも多くのフィルタ又は少ないフィルタを必要とする場合がある。
【００８０】
一般に、本発明のプロセスは、データ要素の形で電子メールの内容を受信する。電子メールの内容は電子メールの本体を含む。電子メールの送信において、データ要素は制御文字又は情報文字を表す。好ましい実施形態では、メッセージから取り除かれるＨＴＭＬタグ等の制御文字は、本明細書全体を通じて特に言及がない限りそのメッセージに関して、情報文字のみを意味する。
【００８１】
一組のフィルタは、それらのフィルタのすべてが、計算上の意味で、構造的に等価である場合に均一であると規定される。均一フィルタの自明な例は、出力状態が、固定パラメータによって処理される所与の入力状態について決定される一組の同一のフィルタである。均一フィルタの別の例は、出力状態が推移確率のマトリクスの関数である一組のフィルタである。本明細書でさらに説明する本発明では、ランダムに選択された数値のマトリクスが、フィルタを生成する同じ乱数関数によって生成される。ここで、フィルタは、乱数関数の初期化に使用される種によって互いに異なる。等価であることの結果として、すべてのフィルタは、スタンドアロンフィルタとして使用される場合に同じ最適なしきい値を使用する。このことによって、最適化問題が単純化される。基本的な要素として均一フィルタ手法を利用する結果、しきい値のさまざまな関数が扱いやすくなる。これは、非均一フィルタ技術の下では、５０個のフィルタ程度の少ない個数であっても極めて難しい。複数のフィルタのそれぞれを別々に使用すること及び複数のフィルタを全体として使用することとの間で相違がある。最初のケースでは、フィルタのそれぞれがしきい値を有し、これは、均一フィルタセットの場合に、各フィルタについて同じである。
【００８２】
図３ｃを参照して、本発明の方法は、以下でさらに説明するように、均一フィルタの適したランダム性を確立する際に利用される乱数のマトリクス３１２を作成する。データソース｛ｘ｝∈Ｘｓからの文字ｘｉ及びｘｉ＋１、ｘｉ＋２、…ｘｉ＋ｎを有するＸｓによって表される一組の電子メッセージ３１５が、ハッシュダイジェスト３３２データベースを作成する目的でサンプリングされる。受信された電子メールは、記憶されているダイジェストと比較されて（３７０）、一致するものがあるか否かが判断される。より詳細には、メッセージＸｓは、均一フィルタ３２０への入力となる。均一フィルタ３２０は特徴ベクトル３２５を形成する。特徴ベクトル３２５の要素は短いハッシュ値である。特徴ベクトル３２５の要素の全体は、別名としてメッセージのハッシュダイジェストと呼ばれる。シグネチャは、通常リアルタイムで達成される、しきい値３４０を利用した電子メールとの後の比較のために、ハッシュダイジェスト３３２データベースに記憶される。電子メールメッセージの入力ストリーム（おそらく、それらのメッセージの一部は、決定されるクラスに存在する）は、入力段３５５において受信される。この入力ストリームは、データパケット、ランダムアクセスメモリ、又は（電子メールに収容可能な）連続レコードに組み込むことができるような、データソース｛ｘ｝∈Ｘｍからの文字ｘｉ及びｘｉ＋１、ｘｉ＋２、…ｘｉ＋ｎを有するＸｍと表記することができる。それらの文字は通常、処理のために、データレジスタに記憶又はバッファリングされる。データ要素｛ｘ｝は、ＡＳＣＩＩ等の符号化送信の形式とすることができる。符号化送信は、均一フィルタ３２０と同一の特徴を有する均一フィルタ３６０への入力となる。特徴ベクトル３６５は、しきい値３４０を利用したハッシュダイジェスト３３２との最終比較及び結果３８０のために作成される。
【００８３】
図３に示すようなコンピュータ方法は、ランダムマトリクス３１２も含む。その要素は、３２０等の一組のフィルタから生成される。それらは、受信メッセージ｛ｘ｝∈Ｘｓの近傍の対を個々に合計する。マトリクス３１２は、通常、１００個の個別のマトリクスを含む。各マトリクスは、１０進法で範囲０から２５５のエントリーを有する２５６×２５６の要素を有する。一実施形態では、エントリーは、擬似乱数発生器と共に動作するタイムスタンプの積である。擬似乱数発生器は、１０進法で範囲０から２５５の数値の一連のエントリーを生成する。この一連のエントリーは、通常、左に３３０００箇所及び右に３３０００箇所を超える。
【００８４】
ハッシュの比較を最適化する方法は、ＡＳＣＩＩ値に見られるような同じ又は類似の分布を有する乱数ベクトルＶｍ、Ｖｓを利用する。この理由から、乱数ベクトルを計算するのに使用される数学的方式は、均一フィルタ方法として知られている。その後、均一フィルタ３０６は、調査中の電子メールの特徴ベクトルの作成に関連して乱数関数マトリクス３５２に転送されている場合があるランダムマトリクス３１２からの値を利用する。
【００８５】
均一フィルタコンピュータ方法は、（ａ）一組の文書から複数のハッシングベクトルを受信するとともに、当該サンプルハッシングベクトルをランダムアクセスメモリに記憶するステップと、（ｂ）データレジスタに、受信された文書からの少なくとも２つの隣接するデータ要素をロードするステップと、（ｄ）ハッシュ手段を利用して電子メールハッシングベクトルを計算するステップと、（ｅ）電子メールハッシングベクトルを複数のサンプリングされたハッシングベクトルと比較するステップとを含む。
【００８６】
図３ｄを参照して、ダイジェストの作成及びその後の比較の両方のための均一フィルタシステム３００の電子メッセージＸは、データパケット、ランダムアクセスメモリ、又は（電子メールに収容可能な）連続レコードに組み込むことができるような、データソース｛ｘ｝∈Ｘからの文字ｘｉ及びｘｉ＋１、ｘｉ＋２、…ｘｉ＋ｎのストリームを考えることにより説明される。それらの文字は通常、処理のためにデータレジスタ３１０ＤＲに記憶又はバッファリングされる。データ要素｛ｘ｝は、ＡＳＣＩＩ等の符号化送信の形式とすることができる。符号化送信は通常、処理のために変換又は数値化解除（denumerate）される。あらゆる任意の個数のデータ要素を処理のために選ばれたデータレジスタ３１０に記憶することができるが、発明者は、少なくとも２つの隣接するデータ要素ｘｉ及びｘｉ＋１が、一実施形態のデータ構造体として機能することを決定している。
【００８７】
データｘｉ及びｘｉ＋１は、均一フィルタＭｋを表す数学関数を提供するように構成されるフィルタ関数３２０Ｍへの入力として利用される。均一フィルタＭｋは、ｊ＝１である場合に最初の入力ｘｉ及びｘｉ＋１の対について、一連のベクトル３３０Ｖｉｊの要素ｅｉｊ、ｅｉ＋１，ｊ、…ｅｉ＋９９ｊを計算する。ベクトルＶｉ，１が計算されると、新たな一対の隣接するデータ要素ｘｉ＋１、ｘｉ＋２がデータレジスタ３１０ＤＲにロードされる。この新たなデータ要素ｘｉ＋１及びｘｉ＋２は、その後、第２の均一フィルタＭｋ関数への入力として利用される。第２の均一フィルタＭｋ関数は、ベクトルＶｉ，，２の要素ｅｉ，２、ｅｉ＋１，２、…ｅｉ＋９９，２を計算する。特定の均一フィルタ関数は、入力に対して操作を行うように選択された公式又はアルゴリズムと、Ｖｉｊの要素ｅｉ，ｊを計算するために選択された確率変数Ｒとの両方によって決定される。隣接するデータ要素を使用してデータ要素Ｘ∈｛ｘ｝を１つの位置又は１バイトだけシフト又は移動する技法は、シングリングと呼ばれ、従来技術で見られる技法である。データソース｛ｘ｝∈Ｘからオペランドｘｉ及びｘｉ＋１、ｘｉ＋２、…ｘｉ＋ｎを形成する他の方法の使用が有利であることが分かるので、シングリングは本発明の要件ではない。特に、シングル技法と共に本明細書で説明するような均一フィルタ関数Ｍｋの選択方法は、説明するように新規である。
【００８８】
本発明の一実施形態では、フィルタＭｋは、２つの隣接する８ビット文字を受け取るように形成される。これらの２つのデータから、必要とされるベクトルＶｉｊの要素ｅｉｊを計算することができる。
【００８９】
一般に、本発明のフィルタ３２０Ｍｋは、可変長の文字列を生成する。しかしながら、一実施形態では、フィルタ３２０Ｍｋのそれぞれは、０〜２５５の範囲の数値を出力する。統計的に関連のあるフィルタＭｋの個数は、通常、文字列の長さを表し、一実施形態では、少なくとも１から最大１００の範囲にある。ただし、用途が指示するように、他の長さを使用することもできる。
【００９０】
各均一フィルタ３３０を作成する際に、フィルタＭｋ（ｘ）＝［Ｍ１，Ｍ２，…，Ｍ１００］は、種子発生器（seminal generator）として機能する「母乱数列（mother random sequence）」Ｒｋをパラメータとして利用する事前に割り当てられた数学関数を表す。母乱数列は、例示として、長さが２１６個の文字として選択することができる。乱数発生器の統計的特性は、最終的な特徴ベクトル３４０のハッシュ関数パターンに見られる。フィルタは、特徴ベクトル（ＡＳＣＩＩ値の発生回数）と同じ分布を有する。その後、フィルタ関数の統計的特性は、いくつかの用途ではガウス分布関数に似ているが、ハッシュ値を生成するのに役立つ。
【００９１】
より詳細には、フィルタ３２０Ｍｋ（ｘ，Ｒ）のフィルタ関数は、図３ｄに示すような一組の均一分布関数を備えるように選択される。任意の長さの乱数発生器は、計算用の開始点を決定する乱数Ｒｋを選択する。たとえば、列Ｒｋを、無理数の最初の２１６個の文字に限定することができる。フィルタＭｋ＋１を形成するために、開始点は、１つの要素分、１バイト分、又は１文字分だけ右にシフトされて、次に高いカウント場所が得られる。このプロセスでは均一分布が形成される。これは、乱数Ｒｋのソースであるランダムマトリクスの要素を提供する。一実施形態では、マトリクスデータは数式の因数として利用される。この数式は、｛ｘ｝のデータ要素及びフィルタＭｋの乱数Ｒｋを利用して、Ｖｉｊ３３０のベクトル要素３３５ｅｉｊを形成する。このような数学関数は、設計の選択肢であり、排他的「論理和」のクラスの論理関数、又は線形方程式、非線形方程式、及びフーリエ変換及びべき級数で求められるような級数の系で見られるような分析関数を含むことができる。
【００９２】
次のステップにおいて、すべてのベクトルＶｉｊの要素３３５ｅｉｊが、ｆｉ＝Σｅｉｊとして合計されて、Ｆ（ｆ）と呼ばれる特徴ベクトル３４０の１つのハッシュ要素３５０が生成される。１００個のフィルタＭｋが１００個のベクトルＶｉｊを計算する場合、特徴ベクトル３４０Ｆ（ｆ）は、１００個のハッシュ要素３５０から成る。
【００９３】
ｆ１、ｆ２…ｆｎとして示される特徴ベクトル要素３５０は、シグネチャｆ'１、ｆ'２…ｆ'ｎとして記憶されている対応する特徴ベクトル要素と比較される。２つの特徴ベクトルｄ（ｆｉ，ｆｉ'）の要素間の差「ｄ」は、先に示したように距離である。この距離が、事前に選択されたしきい値τよりも小さい場合、特徴ベクトル３４０Ｆ（ｆ）は、スパムクラスを表すものと判断される。先に示したように、本発明者らは、約１３のしきい値が、少なくとも１つのタイプのスパムを分類するのに役立つことを見出している。当業者には、他のしきい値が電子メールのソース又は電子メールの主題によって関係付けられるような他のタイプの電子メールの他の分類を生み出すことが認識される。
【００９４】
図４ａに関して、本発明の方法論は、選択されたテスト電子メールをフィルタリングして（４０１）、参照のためにデータベースに記憶されている（４０４）、識別された属性の特徴ベクトルを有する文書を作成する（４０２）。その後、通常は整数に変換されたＡＳＣＩＩ文字である２００個の８ビット文字の連続ストリームが、選択されたテスト電子メールをフィルタリングする際に使用されたフィルタクラスを利用して、ペアワイズでフィルタリングされる（４０５）。フィルタからの出力は合計されて、特徴ベクトル４０６が作成される。この方法は、この特徴ベクトルを、記憶されている特徴ベクトル４０４と比較する（４０８）。比較ステップ４０８は、２つの特徴ベクトル（４０６、４０４）の要素間の差「ｄ」を計算する。ステップ４１０は、この差をしきい値４１４τと比較し、差が事前に選択されたしきい値τよりも小さい場合には、特徴ベクトル４０６に関連する電子メールは廃棄される（４１２）。ステップ４１０において、差が事前に選択されたしきい値τよりも大きい場合には、この方法は、特徴ベクトル４０６に関連する電子メールを受信者に渡す（４１６）。
【００９５】
均一フィルタ方法は、サンプル電子メールの特徴ベクトル４０２（たとえば、Ｖ１、Ｖ２、…、Ｖｊ、Ｖ１００）をオフラインで計算する。複数の乱数ベクトルを有することの背景にあるアイデアは、複数のエントリーを有する出力ベクトルを生成することである。本発明の方法によって生成されるハッシュは、メッセージのＡＳＣＩＩ値と同じ又は類似の分布を有する乱数ベクトルＶｊを生成する。ベクトルが長いほど、短いベクトルよりも信頼性の高い比較結果を生成する可能性が高くなる。いずれにしても、２つの異なるオブジェクトの比較を意味のあるものとするために、それらのハッシュは同じ長さでなければならない。
【００９６】
好ましい実施形態では、ステップ４０１の着信電子メールサンプル及び後のステップ４０５の後者の受信電子メールは、構文解析されて、長さ２００のメッセージＰにされる。均一フィルタが２つの８ビットバイト数値の積を計算する場合に、ステップ４０６及び４０２でそれぞれ生成されるような関連するベクトルは、２つのＡＳＣＩＩ文字の可能な最大の数値の積に適合するように少なくとも２１６の長さとされるべきである（２５５×２５５は、２１６によって制限される）。実際には、構文解析されたメッセージは英数字文字しか含まないので、構文解析されたメッセージの文字は、全範囲［０，２５５］の値を取らない。
【００９７】
さらに、目的は、０から２５５にわたる１００個のフィルタ値から成るダイジェストを生成することであるので、ステップ４０６及び４０２でそれぞれ生成されるような乱数ベクトルは、整数エントリーを含むべきである。ｊ＝１、２、…、１００の場合の「サンプリング関数」の集合が規定される。ここで、構文解析されたメッセージの２００文字のそれぞれは、サンプリング関数のうちの１つにおける引数の少なくとも１つであるべきである。次の例は、各文字Ｐが、正確に１つのサンプリング関数：｛Ｎ１（Ｐ１，Ｐ２），Ｎ２（Ｐ３，Ｐ４），…，Ｎ１００（Ｐ１９９，Ｐ２００）｝に使用される場合を示している。
【００９８】
各引数は、Ｐの各文字が各サンプリング関数：｛Ｎ１（Ｐ１，Ｐ２，…，Ｐ２００），…，Ｎ１００（Ｐ１，Ｐ２，…，Ｐ２００）｝で使用される可能性を示している。
【００９９】
これは、サンプリング関数がどの引数を取ることができるかを示唆するが、形式は任意とすることができる。特徴ベクトルの効率は、サンプリング関数の実際の値を計算するのに必要とされる計算量に依存する。このために、マトリクスルックアップ手順によって評価されるサンプリング関数を選ぶべきである。実際の評価が多くの費用を要しない限り、サンプリング関数のオフライン初期化にかなりの計算が必要とされることは容認できる。いずれにしても、これらのサンプリング関数は、その後、フィルタアレイを形成するのに使用される。
【０１００】
ランダムマトリクスによって、いわゆる「マトリクスルックアップ」ステップによって前述した最近傍関数の計算が可能になる。メモリのストレージのサイズは、ｘ｛ｉ｝＋２５６＊ｘ｛ｉ＋１｝に近づくか又は等しくなるはずである。
【０１０１】
第１の特徴ベクトルＶａ１を生成した電子メールデータストリームＸａ、及び特徴ベクトルＶｂｎを生成する電子メールＸｎは、長期間にわたってまったく異なる可能性がある。その結果、ペアワイズで、第１のベクトルが第２のベクトルのτ＜１の範囲内にあり、且つ、第２のベクトルが第３のベクトルのτ＜１の範囲内にある場合であっても、これは、常に、クラスを区別するための最適な解を提供するとは限らない。換言すれば、クラスのメンバーシップが推移的に規定されることは妥当でない。それとは論理的に正反対の場合には、クラスのメンバーシップが、第１のベクトル等の単一のベクトルからの半径によって規定されることは妥当ではない。上記の場合には、第１のベクトルＶａ１：２，２，…，２によって規定されたクラスのうちの１つのメンバーのみが存在する。これは、第３のベクトル及び第４のベクトルも第１のベクトルと同じにクラスに属する可能性が非常に高いので満足できるものではない。したがって、一方法及び一システムは、区別された点を半径τのボールの中心として選択することにより、特徴ベクトルの空間を分割する。しかし、ベクトルのこの方法のストレージは静的ではないが、リアルタイムで追加されているベクトルのストアである。リアルタイムフローを取り扱うために、この方法は、好ましい実施形態では、１００００個以上のベクトルを有する「現在のレジスタ」を規定する。時間が最も古いものは、最も新しいものが来ると一クラスのボールの中心としての適格性を失い、正確に１００００時間単位の間留まる（この動的なデータベース内への１００００個の新しいベクトルの流入によって境界が定められる）。区別された中心が一組のクラスのボールの中心を共有する方法は、時間と共に動的に変化する。選択は空間基準に基づき、その技法は統計学の当業者に既知である。
【０１０２】
小さなハッシュ方法と呼ばれる一代替的な実施形態である図４ｂは、２００個の８ビット文字（通常は整数に変換されたＡＳＣＩＩ文字）の連続ストリームをペアワイズでフィルタリングするステップ４０３が、均一フィルタを利用して、１２８個、すなわち２７個の特徴ベクトルを生成する、本発明の方法論を示している。ステップ４０７において、フィルタからの出力は合計されて、特徴ベクトルが作成される。この特徴ベクトルは、τ１及びτ２と呼ばれるステップ４２０の関係する２つのしきい値と比較される（４２２）。
【０１０３】
元の（長い）ハッシュからのいくつかの準不変なもの（quasi-invariant）を計算した後、その結果の文字列は、電子メールのクラスタを識別するのに有用である。
【０１０４】
特徴ベクトルは、あらゆる任意の長さとすることができる。しかしながら、一実施形態は、１２８個、すなわち２７個の要素を有する特徴ベクトルを利用して、識別された属性の電子メールを有する文書を弁別する。１２８個の要素の特徴ベクトルにおいて、各要素は、８ビットバイトによって表される。
【０１０５】
τ１及びτ２の確立は実験に基づいている。この実験では、識別された属性を有する文書が均一フィルタによって処理されて、通常は整数に変換されているＡＳＣＩＩ文字である２００個の８ビット文字の連続ストリームをペアワイズで均一フィルタリングすることによって形成されるような特徴ベクトルの要素ｅ'の値が求められる。この方法は、均一フィルタ出力を合計して、変化しないとみなされる、平均（ｍ）及び分散（ｖ）を有する分布関数を有する特徴ベクトルを作成する。平均ｍからの距離（統計値ｓ'）が、非スパムからスパムを弁別した実験に基づいて選択される。
【０１０６】
ステップ４２２において、特徴ベクトルの要素ｅ'の値が、τ１及びτ２に対してテストされる。これらは、統計値（ｍ＋／−ｓ'）とみなすことができる。第１の特徴ベクトルの要素ｅ'（１）から開始して（４０７）、ｅ'（１）＞（ｍ＋ｓ'）又はｅ'（１）＜（ｍ−ｓ'）が真である場合、ハッシュベクトルの第１の要素の状態ｈ（１）＝１が設定され（４２４）、そうでない場合、ステップ４２７で作成されたハッシュベクトルの第１の要素ｈ（１）のステップ４２４の状態はゼロに等しく設定される。ステップ４２４は、特徴ベクトル４０７の要素及び対応するハッシュベクトルのステップ４２７の要素のそれぞれについて繰り返され、要素「ｈ」が生成される。したがって、各ｅ'［ｉ］について、ｅ'［ｉ］＞ｍ＋ｓ'  ＯＲ  ｅ'［ｉ］＜ｍ−ｓ'である場合にはｈ１［ｉ］＝１であり、そうでない場合にはｈ１［ｉ］＝０である小さなハッシュが生成される。
【０１０７】
実験に基づいて、パラメータｇは量子化要素を確立する（４１９）。この量子化要素は、ｅ'（ｉ）が当該量子化要素よりも大きいのか又は小さいのかに関して使用される。その後のステップにおいて、ビットマスクがステップ４２３に基づいて生成される（４２８）。ステップ４２３では、ｅ'［ｉ］＞ｇ１である場合にｇ１｛ｉ｝＝１であり、ｅ'（ｉ）≦ｇ１である場合にｇ１（ｉ）＝０である。したがって、１２８バイトの特徴ベクトルが与えられると、（ｉ）１６（すなわち、１２８／８）バイトの小さなハッシュベクトルが生成され、且つ、（ｉｉ）１６バイトのビットマスクが全３２バイトについて生成される。小さなハッシュテスト及びビットマスクテストは、共に、２つのフィルタ値が類似しているか否かをチェックするのに必要である。
【０１０８】
１６バイトの小さなハッシュが一旦作成され、１６バイトのビットマスクが一旦作成されると、これらの２バイトの値は、スパムハッシュベクトル４１４ｈ２及びビットマスク４１３ｇ２との電子メールの類似を判断するのに使用される。検査中の電子メールはそれぞれ、ビットマスクｇ１及び小さなハッシュｈ１を有し、これは、スパムの既知のサンプルからの見本のビットマスクｇ２及びハッシュベクトルｈ２と共に計算で利用される。計算４２６は続けて、ａ＝ｇ１  ＡＮＤ  ｇ２及びｂ＝ｈ１  ＯＲ  ｈ２を判断する。２つのハッシュは、ステップ４１０がａ  ＡＮＤ  ｂ＝ｂを与える場合に類似している。これは、（ａ  ＡＮＤ  ｂ）ＸＯＲ  ｂ＝０と等価である。
【０１０９】
計算された（４２７）ハッシュベクトル値と、ステップ４２８で求められた、記憶されているハッシュベクトル値とが一致する場合、スパムは有効に廃棄される（４１２）。ステップ４２７の計算されたハッシュと、ステップ４２８の記憶されているハッシュとが一致しない場合、電子メールメッセージは、受信者に有効に渡される（４１６）。
【０１１０】
図５は、不要である可能性のある電子メールの送信を検出するための従来のインターネット５０１システムを示している。このシステムは、クライアントメールサーバ５０９を利用する複数の電子メールを観察するための手段と、図４ａ及び図４ｂに示すように、複数の電子メールの１つ又は複数の部分の特徴ベクトルを作成して、ハッシュ値及び関連するビットマスクを生成し、生成されるハッシュ値及び関連するビットマスク値が前の電子メールに関係するハッシュ値及び関連するビットマスク値と一致するか否かを判断するための手段とを備える。理解されるように、周辺サーバ５０３は、電子メールを分類し、図１ａ、図１ｂ、図２ａ、及び図３ｃについて説明したように電子メールのクラスタを作成するように構成することができる。
【０１１１】
図５では、インターネット５０１の接続５２６ａ及び５２６ｂによって、ユーザ５１０は、クライアントメールサーバ５０９に関連するプロセッサ５０４及び５０７を通じて電子メールを送受信することが可能になる。クライアントメールサーバ５０９は、周辺サーバ５０３と共に動作する。周辺サーバ５０３は、ソフトウェアプログラム５４５、及び上述したような分類及びクラスタを記憶するデータベース５１１にアクセスするプログラムの制御下で動作する。ソフトウェアプログラム５４５は、図１ａ、図１ｂ、図２ａ、及び図３ｃに示すプロセスと、本明細書で説明したハッシュ技術に従って電子データストリームを解析するためのプロセス５０２（ａ）、５０２（ｂ）、及び５０２（ｃ）とを実行するためのプロセス５１５を含む。サーバ５０３及び関連するソフトウェアは、電子メールプロセッサ５０７を通じて追加されたスパムセイリエンシ（spam saliency）を有する電子メールを送信するように構成することもできるし、出て行くスパムを所定のルールに基づいてブロックするように構成することもできる。メールサーバ５０９との接続が素早く確立されない場合に、タイムアウト５１３も使用することができる。電子メールの入力用の電子メール５０４プロセッサを利用すると、プロセス５１５は、本発明の技術に基づいて、クラスタリング及び分類を計算する。
【０１１２】
本明細書で説明したシステムによって作成されるような分類データ及びクラスタリングデータ、又は（ａ）外部ソース５１８からさらに受信されたか、（ｂ）若しくは、インターネット接続５２６ｂ及び５２４等のインターネット接続を通じてダウンロードされるような分類データ及びクラスタリングデータを含むデータベース５１１は、中央サーバ５４０及び関連するデータベース５２２から受信できるように、
【０１１３】
本明細書の発明は、学習マシンプロセス並びにハッシュ技術プロセス５０２ｂ及び５０２ｃを含み、データベース５１１に記憶されているハッシングベクトル又はハッシングベクトルから導出されたものを利用して文書をクラスタリングし、電子メールを比較するために、図２ａ、図２ｄ、図３ｃ、図４ａ、及び図４ｂについて説明したような新規なプロトコルの下で動作して、本発明の特徴ベクトル及び幾何ベクトル（一括して「ハッシングベクトル」）を作成する。以下に示すものを除いて、電子メールの送信者又は受信者は通常、均一ハッシュフィルタ５０２ａの直接制御もスタック可能ハッシュ５０２ｃの直接制御も有しない。均一ハッシュフィルタ５０２ａ又はスタック可能ハッシュ５０２ｃは通常、ゲートウェイセンドメールサーバ５０３内にインストールされる。
【０１１４】
センドメールが一旦電子メール５０４をサーバ５０３から受信すると、その電子メールは、ソフトウェア５４５のプログラムコールによって、学習マシン５０２ａ及び代替的にハッシュ技術プロセス５０２ｂ及び５０２ｃに渡る。一実施形態では、ハッシュ技術プロセス５０２ｂ及び５０２ｃは、受信コンピュータ５１２に直接インストールされる場合もあるし、インターネット接続５０１又はローカルエリアネットワーク接続５２８を通じてダウンロードされる場合もある。代替的に、受信コンピュータは、電子メールが、ユーザ５１０による処分を保留している一時停止に保持されていることに応じて、ローカルエリアネットワーク接続５２８を通じて直接情報を受信することもできる。
【０１１５】
サーバ５０３及び関連するソフトウェア５４５は、受信される電子メールのリレーであって、メッセージを変更して２値ヘッダ５０５を任意選択的に組み込むためのリレーとして機能する。より詳細には、学習マシン５０２ａ、均一フィルタ５０２ｂ及び５０２ｃは、個々に又は代替的に電子メール５０４の内容を分析して、電子メール５０４のデータストリームにヘッダ５０５を追加する。このヘッダ５０５は、その電子メールが相対的にどれくらい危険であると考えられるかを示すスパム性（spamicity）５０６の尺度を含む。プログラミング手段は、任意のスケールの数値としてスパム性５０６を生成する。しかしながら、アドミニストレータは、プロセッサ５１５によって具現化されたプロセスの起動中にその大きさ又はパラメータを調節することができる。
【０１１６】
受信コンピュータ５１２のユーザ５１０及びサーバ５０３のアドミニストレータ（図示せず）は、それぞれ、スパム性５０６の尺度に基づいてどの動作を取るかを決定することができる。一例として或るシナリオは、デフォルトで、ハッシュ技術プロセス５０２ａ及び５０２ｂが、受信コンピュータ５１２の特定のユーザについてオフにされることである。ユーザ５１０がその後の電子メール５０４をフィルタリングしたい場合、ユーザは、ハッシュ技術プロセス５０２ａ及び５０２ｂをオンにする要求を送信する。ハッシュ技術プロセス５０２ａ及び５０２ｂは、すでにオンにされている場合があるが、ユーザは、スパム性のしきい値５１４の設定を所望する。このしきい値よりも大きい場合、電子メール５０４は基本的に、ハッシュ技術プロセス５０２ａ及び５０２ｂの攻撃であると判断されてユーザ５１０に配信されない。ユーザ５１０がスパム性５０６のしきい値５１４を指定しない場合、サーバのアドミニストレータによって事前に確立されたデフォルト値をプロセス５０２ａ及び５０２ｂは利用することができる。電子メール５０４のスパム性５０６がしきい値５１４よりも大きい場合、ユーザ５１０は、事前にプログラミングされたルールに基づき、１つ又は複数のフォルダに電子メール５０４を送信するルールを起動して電子メールを隔離し、その電子メールをスパムフォルダ５１６に記憶することができる。
【０１１７】
中央サーバ５２０は、ワールドワイドウェブと通信する周辺サーバ５０３等のクライアントサーバの統一アドレス（uniform address）を提供する。その主要な目的は、世界のすべてのサーバのキャッシュを比較し、次に、インターネットを通じて結果を配信することである。キャッシュは、ハードウェアの速度及びインターネット５０１のトラフィックに応じて１分以下に近い間隔で絶えずローリングしている。目的は、中央サーバ５２０に対する悪意のある攻撃を軽減するために、すべてのサーバのスパムリストを記憶して同期させ、クライアントサーバ５０９の一部とすることができるような、各企業に動的に割り当てられる確信度評定を作成することである。
【０１１８】
プログラム５４０は、原則として比較的大きい可能性があるクラスタ、分類、幾何ベクトル、及び特徴ベクトルを記憶する。基本的な例示では、特徴ベクトルはファイルに記憶される。この場合値が起動中に読み出され、その後、別のメモリに記憶される。この基本的な例示は、プロセッサ５１５に具現化されたプロセスを、例えばバークレイＤＢ等のデータベースと共に統合することでよりロバストにすることができる。バークレイＤＢは、センドメールエイリアスファイルをエイリアスデータベースと比較する。
【０１１９】
図５について、ハッシュ技術プロセス５０２ｂは、特徴ベクトルを作成して、図４ａ又は図４ｂのいずれかに開示したプロセスに従い特徴ベクトルを利用するための方法を含む。したがって、図５は、電子メールのクラスの送信を検出するためのコンピュータ方法も開示する。このコンピュータ方法は、（ａ）１つ又は複数の電子メールメッセージを受信するステップと、（ｂ）学習マシンを利用して電子メールを分類するステップと、（ｃ）Ｋ−ＮＮマシンを利用してあいまいな文書をさらにクラスタリングするステップと、（ｄ）複数の電子メールメッセージの１つ又は複数の部分に基づいてハッシュ値を生成するステップと、（ｅ）複数の電子メールメッセージのうちの１つ又は複数の部分に基づいて、関連するビットマスク値を生成するステップと、（ｆ）生成されるハッシュ値及び関連するビットマスク値が、クラスタの１つ又は複数の前の電子メールメッセージに関係する、対応するハッシュ値及び関連するビットマスク値と一致するか否かを判断するステップとを含む。
【０１２０】
この開示した方法は、生成されるハッシュ値及び関連するビットマスク値が、クラスタの前の電子メールメッセージに関係する、対応するハッシュ値及び関連するビットマスク値と一致するか否かの判断の結果に基づいて、複数の電子メールメッセージのセイリエンススコアを生成することをさらに含む。
【０１２１】
より一般的には、上記によれば、図５に開示したようなシステムは、（ａ）２進符号化メッセージを一組の数値に変換する手段と、（ｂ）数学関数に提供される数値に基づいてハッシングベクトルを計算する手段と、（ｃ）ハッシュベクトルの値と記憶されているベクトル又は記憶されているベクトルを表すダイジェストとの差を比較する手段と、（ｄ）比較に基づいてスパムメッセージにヘッダを追加する手段と、を提供する。
【０１２２】
図６は、小さなハッシュ方法論を示し、電子メール６０４のメッセージの文字を、サーバ５０３のメモリに代表され得るようなコンピュータに記録されるとともに記憶されているｍ０、ｍ１、…ｍ（ｎ−１）と考える。
【０１２３】
ステップ６０４は、まず、すべての非英数字文字のメッセージを取り除く。ここで、限定ではなく例示として、「文字」は、８ビットバイトとして規定することができる。一実施形態では、入力された電子メールメッセージは、通常はＡＳＣＩＩ文字である２００個の８ビット文字の連続ストリームを含み、２００文字の出力ストリームを生成する構文解析機能６０６への入力として機能する。この２００文字の出力ストリームは、均一フィルタ６０８の入力として機能する。その後、次の５つのステップ６０７、６０８、６１１が実行されて、メッセージの特徴ベクトルが計算される（６１１）。
【０１２４】
構文解析機能６０６、６０７は、処理のために着信データストリームを準備する。ここで、αは、α（０）がメッセージに最初に現れた英数字文字として選ばれること：α（ｊ）＝ｊｍｉｎによって作成される。ここで、ｊｍｉｎ＝ｍｉｎ｛ｋ｜ｋ＞α（ｊ−１）｝であり、ｍｋは英数字である。
【０１２５】
この段階では、小文字及び大文字を同じように取り扱うために、すべての大文字は、その小文字のＡＳＣＩＩ対応文字にマッピングされる。便宜上、メッセージに最後に現れる英数字文字のインデックスがαｍａｘであるものと仮定する。この場合、２つのケース、すなわち、Ａ｛α１，α２，…，αｍａｘ｝＜２００及びＢ｛α１，α２，…，αｍａｘ｝＞２００が存在する。
【０１２６】
第１のケースでは、メッセージは、その後、（文字による）その長さが２００となるように「パッディング」又は延長される。パッディングは次のように行われる。すなわち、パッディングされたメッセージのビットによる長さが２００となるように、「０」ビットが追加される。全部で、少なくとも１つの文字及び多くとも２００個の文字が追加される。
【０１２７】
限定ではなく例示として、その最も基本的な形式では、構文解析オペレーション６０６は、すべての非英数字文字を除去し、次に、結果の文字列６０８を、長さが二百の２００個の文字にトランケートする。ステップ６０７の文字列が、長さが２００文字よりも小さくなる場合、この方法は、必要に応じて０を連結して長さが２００文字に達するようにする。
【０１２８】
ステップ６１１において、特徴ベクトルが、ステップ６０７で生成される構文解析されたメッセージ文字列に対してフィルタステップ６０８を適用することにより作成される。各着信（６０４）電子メールメッセージについて、フィルタは、ダイジェスト６１１へのエントリーを計算する（６０８）。ステップ６１６は、１６バイトの小さなハッシュベクトルを、値が０から２５５に及ぶ２進数で符号化された符号なし文字として計算する。ただし、他のアプリケーションはこの範囲を増減することができる。ステップ６１８において、１６バイトのビットマスクも特徴ベクトルから計算され、小さなハッシュベクトルは論理計算で結合される。これらの２バイトの値は、スパムの既知のサンプルからスパムの見本のビットマスク及びハッシュベクトルとの電子メールの類似を判断するのに使用される。図４ｂについて先に詳述したように、計算は次に、ａ＝ｇ１  ＡＮＤ  ｇ２及びｂ＝ｈ１  ＯＲ  ｈ２を判断することに進む。ステップ６１７がａ  ＡＮＤ  ｂ＝ｂを与える場合に、２つのハッシュは類似している。ａ  ＡＮＤ  ｂ＝ｂは、（ａ  ＡＮＤ  ｂ）ＸＯＲ  ｂ＝０と等価である。ステップ６１９において、ステップ６１７の計算結果により、電子メールの分類が可能になる。
【０１２９】
均一フィルタリングは、電子メール５０４の小さな変化が、ダイジェストデータベース５１１のエントリーのすべてを或る増分量だけ変化させる、ダイジェストデータベース５１１のエントリーの区分的に連続な振る舞いを示す。性能データは、本明細書の本発明の方法が、（標準的なメモリ量を有する）Ｐｅｎｔｉｕｍ  ＩＩＩパーソナルコンピュータにおいて２５〜５０マイクロ秒で単一の電子メール５０４のメッセージのハッシュダイジェスト計算を実行できることを示している。レート制限は、着信電子メールの前処理を行うことである。それにもかかわらず、この方法はスケーラブルであり、既知の暗号ハッシュアルゴリズムであるＭＤ５を比較して、テストされたプラットフォームでより良い速度を示し、また、より良いスケーラビリティを示す。
【０１３０】
最後に、類似のハッシュを決定するために、作成されたハッシュダイジェスト６１６のアーカイブを効率的に探索するトピックが、サンプルハッシュから導出された小さなハッシュの構築によって対処されている。これによって、類似のハッシュダイジェスト６１６のグループを素早く決定することが可能になる。最適な探索方法は、性質上、二分又はｋ−ａｒｙである。このような最適な探索方法は、データベース探索アプリケーションのアーキテクチャ及びプログラミングの当業者に既知である。
【０１３１】
図示するように、データ要素を処理してハッシュ符号を生成する前に、システムは、一組の均一フィルタを生成する。これらの均一フィルタは、ランダムマトリクスの形を有する（一例として、１２８個のランダムマトリクスが作成される場合がある）。これらのフィルタは、フィルタ関数を構築する適切なアルゴリズムを有するプログラムとして実施することもできるし、ハードウェアに具現化することもできる。図７では、装置は、前述したような構文解析されたメッセージを有する電子メールを受信するための均一フィルタシステムを備える。構文解析されたメッセージからのデータストリーム７０１は、少なくとも１つではあるが、２５５個よりも多くない２進符号を含む。２バイトレジスタ７０２は、クロック７０３及び分周器７０５の制御下で、データストリーム７０１を受信する。レジスタ７０２は、均一フィルタ７０８への入力として機能する。均一フィルタ７０８は、乱数発生器７０４と共同して乱数７０６のマトリクスにより生成される入力Ｒｋも受信する。均一フィルタ７０８は、出力の文字列７０９を生成する１２８個の対応する乱数によって提供される入力に対して処理を行う。各一組の入力値７０１Ｘｉ、Ｘｉ＋１及び１２８個の対応する乱数について、１２８個の要素を有するベクトルが作成されて、アキュムレータ７１０で合計され、１２８個の要素ｉ１、ｉ２、…ｉ１２８を有する特徴ベクトルレジスタ７１２のｉ番目の成分が形成される。１２８個の特徴ベクトルの要素が形成されると、その特徴ベクトルの値は、要素ごとに比較器７１４ａ及び７１４ｂの２つの統計値と比較される。第１の特徴ベクトルレジスタ７１２の要素ｒ'（１）から開始して、比較器７１４ａのｒ'（１）＞（ｍ＋ｓ'）が真である場合又は比較器７１４ｂのｒ'（１）＜（ｍ−ｓ'）が真である場合には、「ＯＲ」関数がハッシュレジスタ７１８の要素ｈ（１）＝１に設定し、そうでない場合、ハッシュレジスタ７１８のｈ（１）の状態を０に等しく設定するという条件で、論理ゲート７１６を通じて出力状態７１５を設定する。要素ごとに特徴ベクトルレジスタ７１２を比較するプロセスは、特徴ベクトルレジスタ７１２の要素のそれぞれについて繰り返され、ハッシュベクトルの要素「ｈ」が生成される。したがって、各ｒ'［ｉ］について、ｒ'［ｉ］＞ｍ＋ｓ'  ＯＲ  ｒ'［ｉ］＜ｍ−ｓ'である場合にｈ［ｉ］＝１であり、そうでない場合にはｈ［ｉ］＝０である小さなハッシュが生成される。
【０１３２】
実験に基づいて、パラメータｇ１は、ｒ'（１）が量子化要素よりも大きいか又は小さいかに関して使用されるビットマスク形成器７２８への入力として量子化要素を確立する（７１９）。次のステップにおいて、ｒ'［ｉ］＞ｇ１の場合にｇ１［ｉ］＝１であり、ｅ'（ｉ）≦ｇ１の場合にｇ１（ｉ）＝０であるビットマスク形成プロセッサにおけるテストに基づいて、ビットマスクが生成される。したがって、１２８バイトの特徴ベクトルが与えられると、１６バイトのビットマスクが形成される（１２８）。小さなハッシュのテスト及びビットマスクのテストは共に、２つのフィルタ値が類似しているか否かをチェックするのに必要である。
【０１３３】
１６バイトの小さなハッシュが一旦作成され、１６バイトのビットマスクが一旦作成されると、これらの２バイトの値は、ハッシュベクトル７２６のｈ２及びビットマスク７２２のｇ２との電子メールの類似を判断するのに使用される。検査中の電子メールはそれぞれ、ビットマスクｇ１及び小さなハッシュｈ１を有し、これは、スパム等の既知のクラスタのサンプルからの見本のビットマスクｇ２及びハッシュベクトルｈ２と共に計算で利用される。計算は、ロジック７２４によって実行されて、ａ＝ｇ１  ＡＮＤ  ｇ２及びｂ＝ｈ１  ＯＲ  ｈ２が判断される。これらの２つのハッシュは、ロジック７２４の計算がａ  ＡＮＤ  ｂ＝ｂを与える場合に類似している。ａ  ＡＮＤ  ｂ＝ｂは、（ａ  ＡＮＤ  ｂ）ＸＯＲ  ｂ＝０と等価である。
【０１３４】
図８は、一見本のパターンとのパターンの類似を検出するための装置及びシステムを示している。電子技術の当業者には理解されるように、この装置及びシステムは、アナログプロセス、デジタルプロセス、又はアナログデバイスとデジタルデバイス及びデジタルプログラミング手段の組み合わせとを組み込んだハイブリッドプロセスとして実施することができる。図８の装置及びシステムは、電子信号パターンを検出するためのプロセスを実行し、（ａ）時間間隔Ｔ又はバイト長Ｂｘ（ここでは一括して期間（複数可）と呼ぶ）を有するパターン信号Ｉ（ｍ）を、プロセッサ８０２においてｎｔ個の期間又はｎｘ個の要素（ｎｔ個の要素及びｎｘ個の要素を一括してｎと呼ぶ）に分割すること、（ｂ）信号の１つ又は複数の期間を１つ又は複数のフィルタ８０６に入力すること、（ｃ）時間間隔Ｔ又はバイト長Ｂｙを有する、ｍｔ個の期間又はｍｙ個の要素（ｍｔ個の要素及びｍｙ個の要素を一括してｍと呼ぶ）を有する乱数発生器８０８からのランダム信号を１つ又は複数のフィルタ８０６に入力すること、（ｃ）フィルタ８０６を利用して、各ランダム信号ｍの関数により各パターン信号の期間を変換することによって、特徴信号又は特徴ベクトル（ここでは一括して信号と呼ぶ）８１０を計算すること、（ｄ）各特徴信号期間ｎを、パターンの第１の選択された１つ又は複数の統計値Ｓ１と比較することによってハッシュパターン８１４を作成すること、（ｅ）各特徴信号期間ｎを、パターンの第２の選択された１つ又は複数の統計値Ｓ２と比較することにより、ビットマスクパターン８１６を作成すること、（ｆ）ハッシュパターン及びビットパターンを組み合わせるとともに、その結果を、検出されるパターンに基づいて１つ又は複数のパターンと比較すること、及び一致が存在する場合に、上記パターンが検出されることを含む。
【０１３５】
本発明の一般的なアプリケーションにおいて、図８は、第１の時間間隔で、数値を有する一組の符号がプログラム制御下でシリアルにシフトされて、図３ｄのデータレジスタ３１０ＤＲの関数を提供する長さＬのレジスタ８０２へ一組の符号をシフトするクロック８０１が生成される。明らかなように、シフトレジスタ８０２の長さＬは、あらゆる任意の長さとして選択されており、したがって、着信メッセージデータＩ（ｍ）の２バイトを運ぶことに限定されるものではない。前述したように、シフトレジスタ８０２の長さは、特徴ベクトル８１２の計算に利用される項目の個数によって決まる設計上の選択肢である。
【０１３６】
シフトレジスタ８０２の離散符号化値は、数学的プロセスの変数として利用される、この数学的プロセスは、第１の時間間隔中に特徴ベクトル８１２の少なくとも１つの要素を計算する。
【０１３７】
第２の時間間隔において、シフトレジスタ８０２内に前にシフトされた一組の数値は、ｎ個の均一フィルタ８０６によって表される計算手段８０６への入力８０４として機能する。ランダム発生器は一連の乱数を生成するのに役立つ。一連の乱数は、フィルタ８０６Ｆ（ｖＡ）、Ｆ（ｖＢ）、Ｆ（ｖＣ）…Ｆ（ｖＮ）による計算のパラメータとして使用される。均一フィルタ８０６は、期間Ｔ２の間に各ベクトル値を計算する。第３の時間間隔Ｔ３では、加算器８１０が、期間Ｔ３の間に、値Ｖｍｍを列方向に合計して、特徴ベクトルの要素８１２１、８１２２、…８１２ｎを有するΣＶｎ１、ΣＶｎ２、ΣＶｎｍの特徴ベクトル８１２を形成する。このように実行されるプロセスは、通常は２００バイトのすべての入力データがシフトレジスタ８０２に存在するので、並列処理された特徴ベクトルを生成する。
【０１３８】
図８に示す実施形態では、ブロックＦ（ｖＡ）、Ｆ（ｖＢ）、Ｆ（ｖＣ）…Ｆ（ｖＮ）によって表される計算手段８０６は、或る電子信号を別のものと弁別するのに必要とされる任意の計算手段を使用することができ、したがって、一例として、一組の内積Ｖ１１、Ｖ１２、…Ｖｎ１と、対応する一組の内積Ｖ２１、Ｖ２、…Ｖｎ２からＶ１１ｍ、Ｖ２ｍ…Ｖｎｍとを形成する行列乗算を表す。この内積の計算に続いて、内積の各列の組は合計されて、特徴ベクトルΣＶｎ１〜ΣＶｎｍが形成される。
【０１３９】
図示した装置及び関連する手段のいずれも、表データベースのルックアップ又は短いハッシュとの関連で、ハッシングベクトルに関して先に説明した実施形態で使用することができる。新しく形成されたベクトルの比較がスパムとの類似を示している場合、関連する電子メールは前述したようなそのスパム性の尺度でタグ付けされる。同様の利益は、ハッシングベクトルに関して先に説明した実施形態を使用するとともに、悪質なコード、フィッシング、ウィルス、又はワームのうちの１つを含む電子メールを識別する目的でクラスタリングすることにより達成される。その後、周辺サーバに存在する事前にプログラミングされたルールに基づいて、スパム、悪質なコード、フィッシング、ウィルス、又はワーム等の有害である可能性のある電子メールを隔離又は廃棄することができる。表データベースのルックアップ又は短いハッシュとの関連でハッシュフィルタに関して先に説明した実施形態のさらに別の特徴として、このような方法は、最大の類似度を有する文書を１つのクラスタに入れることによって、不確かな領域に入れられたテキスト分類の精度を改善する。
【０１４０】
適用
一実施形態において先に示したように、均一フィルタ技術及びスタック可能ハッシュ技術は、着信電子メールメッセージを、近時のメモリのクラスタ構造に関係付ける。均一フィルタは、小さな損失性ハッシュ（lossy hash）がクラスタにおいて不変であるか又はほぼ不変であるという特性を享受するが、均一フィルタのオペレーションには、ハッシュ値のストレージ及び探索が必要とされる。均一フィルタ及びスタッキングハッシュはそれぞれ、ハッシュベクトルを有する。しかしながら、これらのベクトルは、異なる空間に存在する（すなわち、均一フィルタハッシュは多次元である）。他方、スタック可能ハッシュ方法のオペレーションは、ストレージも探索オーバーヘッドも伴わない。電子メールの配列の通常の表示は、以下の見本のハッシュ値を有する。
【０１４１】
【表１】
2008529105.tif 000004
【０１４２】
１．最も興味のあるメタデータフィールドはクラスタ構造に関係する。これらのすべてはさまざまなしきい値パラメータを伴う。これらの数値のそれぞれは、均一フィルタ（表示された均一フィルタ）又はスタック可能ハッシュ（表示されたスタック可能ハッシュ）に関係し、対象となる電子メールに適用される。
【０１４３】
図９ａに示すように、電子メール９０２はクラスタ９０１に属し、他の電子メール９０４はクラスタ９０１に属さない。均一フィルタは、以下の表に類似の出力を生成する。ここで、クラスタ識別情報（「ＩＤ」）の「０」エントリーは、クラスタに存在しないと判断された電子メールメッセージに対応する。確信度％は、τｕｎｉｆｏｒｍ  ｆｉｌｔｅｒ（τ均一フィルタ）の妥当性に関係している。
【０１４４】
【表２】
2008529105.tif 000005
【０１４５】
電子メールＩＤの全体集合からランダムに電子メールメッセージをチェックすること、及び／又は、クラスタごとに電子メールメッセージをチェックすることのいずれかにより、均一フィルタの有効性をチェックするための２つの異なる方法が存在する。
【０１４６】
スタック可能ハッシュは、電子メールメッセージが或るクラスタ９０１に属するか否かを判断する。図９ｂの大きな円の内部の電子メール９０６メッセージのすべてが、クラスタ９０８のメンバーである。一方、大きなクラスタ９０８の外部の電子メール９１０メッセージのすべては、クラスタ９０８のメンバーではない。
【０１４７】
スタック可能ハッシュの出力は均一フィルタの出力よりも単純である。ここで、百分率（％）としての確信度は、微小なクラスタ数Ｎｓｔａｃｋａｂｌｅ  ｈａｓｈ（Ｎスタック可能ハッシュ）に関係している。
【０１４８】
【表３】
2008529105.tif 000006
【０１４９】
同様に、均一フィルタの有効性をチェックするための２つの異なる方法が存在する。すなわち、電子メールＩＤの全体集合からランダムに電子メールメッセージをチェックすること、及びクラスタメンバーシップに基づいて電子メールメッセージをチェックすることが存在する。
【０１５０】
クラスタデルタストレージ（「ＣＤＳ」）
すべての電子メールの特徴は、それらの電子メールが類似しているが必ずしも同一ではない情報を運ぶということである。たとえば、銀行取引明細書は、受信者名及び預金口座の詳細が異なる。スパム電子メールは、通常、スパムフィルタを迂回することを目的とする一定量のランダムなミススペルを運ぶ。このような電子メールの送信元が何であろうとも、それらの電子メールを記憶することはかなりの費用を要する。数十万人のユーザに送信された１０キロバイトの電子メールは、ギガバイトのディスク容量のコストを要する。このようなすべての電子メールを記憶することがディスク容量の浪費となることは、かなり明らかである。すべての大量のメーリング電子メールは、テンプレートが元になっているので、このような電子メールを記憶することは、同じテンプレートをほとんど変更せずに何度も繰り返して記憶することを意味する。
【０１５１】
ＣＤＳは、企業レベルでのあらゆるタイプの大量のメーリング電子メールの効率的なストレージのための有効な手段である。上記方法は、スケーラビリティ、速度、圧縮、及び送信元独立性（source-independence）を改善するのに役立つ。
【０１５２】
ＣＤＳの背後にある重要なアイデアは、コンピュータシステムがテンプレートを１度しか記憶する必要がなく、変更は別々に記憶されるべきであるということである。本発明の方法は、テンプレートと、クラスタの代表／電子メールメッセージとの差を記憶する。限定ではなく一例として、それぞれが、名前を含むメッセージのストレージとして１０４バイトを必要とする１０００００通の電子メール案内状（「ｅＶｉｔｅ」）を考える。それぞれの長さが１０４バイトである１０５通の電子メールを記憶するには、１０９バイト、すなわち１ＧＢのメモリストレージが必要とされる。１０２を有するｅＶｉｔｅテンプレート及び受信者の名前に対するストレージを制限し、それぞれを別々に記憶することによって、必要とされるストレージは、多くとも、名前用に１０７バイト及びメッセージ用に１０３バイトである。このようにテンプレートと共に変更を記憶するのに要するストレージは、１０．０１ＭＢだけである。これは、元の電子メールを記憶するのに必要とされる容量である１ＧＢよりもかなり小さい。元の電子メールを圧縮することが決定されている場合、節減されるディスク容量は、未圧縮の変更よりもさらに大きくなる。要約すると、システムがテンプレート及び変更を別々に記憶する場合、システムは、従来の圧縮とは対照的に抽出速度の損失なくディスク容量を節減する。ｂｚｉｐ２のような従来のツールの通常の圧縮比は約０．５であるので、テンプレートになされた変更が非常に大きいため、従来の方法を使用して圧縮された文書全体が、未圧縮の文書よりも結果として小さくなることは可能である。
【０１５３】
類似の電子メールのクラスタを見つけるために、本発明の方法はハッシュを利用する。ハッシュは、この特定の目的に最も適した高速且つスケーラブルなアルゴリズムである。すべての電子メールが、ハッシュを使用してベクトル空間に一旦マッピングされると、類似の電子メールのクラスタを見つけることができる。クラスタが一旦見つかると、システムはテンプレートを再構築する（たとえば、テンプレートとして、クラスタから最小の文書を選択する）。テンプレートが一旦見つかると、バイナリ差分アルゴリズム（binary differential algorithm）（クラスタの最も短いメンバーを使用するテンプレート）が使用されて、テンプレートと、そのテンプレートが生成した電子メールとの差が記憶される。ＣＤＳがどのようにしてディスク容量を節減できるかを示すために、本発明者らは、ＣＤＳを、ランダム汚損テキスト（randomly polluted text）と呼ばれる、起こり得る最悪のケースに適用した。１００通の電子メールをメールボックスから抜粋した。これらの電子メールのそれぞれを使用して、１０通のよりランダムに汚損された電子メールを生成した。汚損の程度は、「雑音レベル」と呼ばれる。たとえば、雑音レベル１０は、１００通からの１０通ごとの電子メールがランダムな文字に置き換えられていることに対応する。電子メールの平均サイズは５．５キロバイトであった。本明細書の目的は、本発明のデルタストレージを、ｂｚｉｐ２等の従来の圧縮方法と比較することである。文書圧縮の程度は、元の電子メールのサイズに対する（ｂｚｉｐ２又はＣＤＳのいずれかを使用して）圧縮された電子メールのサイズの比である「圧縮率」と呼ばれる。
【０１５４】
全体として、デルタストレージ方法は、（ｉ）クラスタを作成するステップと、（ｉｉ）クラスタをソートするステップと、（ｉｉｉ）クラスタに対してラベリングするステップと、（ｉｖ）各クラスタの最も短い電子メールを代表とするステップと、（ｖ）クラスタの他のすべてのメンバーについてバイナリ差分関数を取得するステップと、（ｖｉ）圧縮された電子メールがクラスタにかかわり続けるようにするためにこれらの圧縮された電子メールをタグ付けするステップとを含む。
【０１５５】
この比は、次に、クラスタ特有の圧縮率を生成するためにクラスタにわたって平均化される。圧縮率は、図１０から分かるようにクラスタごとに変化する。図１０は、雑音レベルの関数としてＣＤＳアルゴリズム及びｂｚｉｐ２アルゴリズムの圧縮率を示している。エラーバーは、さまざまなクラスタの圧縮率の２乗平均平方根（「ｒｍｓ」）偏差を示す。ＣＤＳは、低い雑音比では、ほとんどが大規模な圧縮利得を提供する。雑音レベルが１０であっても、圧縮利得は約５である。
【０１５６】
ラベリング
本発明の一実施形態は、ラベルが事前に規定されていようがユーザにより規定されていようが、これらのラベルの例示に従って電子メールを自動ラベリングするための方法である。ラベルは複数対１とすることができる。たとえば、その主題として、広告会社に支払い可能な請求明細書を有する電子メールメッセージは、「広告」及び「金融」の両方が関係するものとして表すことができる。「Ｇｍａｉｌ」として知られているＧｏｏｇｌｅのメールサービスは、ユーザ向けにこの機能を導入した。Ｇｍａｉｌが機能する方法は、ユーザが、積極的にラベルを作成して割り当てなければならないことである。ユーザは、次に、ラベル名を編集し、多くのラベルを所与の電子メールに任意に割り当て、所与の電子メールにすでに割り当てられている任意の個数のラベルを除去することができる。ハッシュ技術は、対象となる各ラベルについて個々のＳＶＭを割り当てることにより、本発明の方法を複数対１のアプリケーションに適用できるという点で異なっている。
【０１５７】
電子メールのラベリングを、よりユーザフレンドリーで且つより少ない時間で行うための方式は、（ａ）ユーザがラベルを作成するタイプ、及び（ｂ）ユーザがラベルを作成しないタイプの２つのタイプに分かれる。第１のタイプでは、ユーザがラベルの割り当てを開始するものと想定される。ラベルの作成には、Ｇｍａｉｌにおける少なくとも１つの割り当てが必要とされる。ハッシュ技術は、本発明のマシン学習方法及びクラスタリング方法の最適な組み合わせを具現化する点で独特である。マシン学習は、各ラベルのしきい値の個数の例示が実行された後に十分なトレーニングを獲得する。したがって、本発明の機能は、十分な例示が実行された後の自動ラベリングである。
【０１５８】
第２のタイプでは、例として、
Ｓ＿１＝｛ホーム，車，ショッピング，家族，イベント，パーソナル｝
Ｓ＿２＝｛授業料，ダイニング，電気通信，性能，パーティ，クラス，財政援助｝
のさまざまな所定のラベル方式が存在する。この場合の機能について、２つの可能性が存在する。第１に、ユーザは、提供されたラベルを使用して例示することができる。或いは、別法ではラベリングは、デフォルトのトレーニングパラメータを使用して自動的に開始する。これらのデフォルトのトレーニングパラメータは、本発明の長いハッシュ又は短いハッシュを利用する分類によって決まる。これは、ホームユーザの電子メールの大きなコーパスを調べることによって行うことができる。また、本発明の方法は、組織間の匿名の情報共有のためのハッシュ表をポピュレートする能力もユーザに提供する。
【０１５９】
実質的に同じ機能を実質的に同じ方法で実行して同じ結果を達成する要素のすべての組み合わせが、本発明の範囲内にあることが明確に意図されている。説明する或る実施の形態から別の実施の形態への要素の置換も、十分に意図されており、且つ、予想されている。
【図面の簡単な説明】
【０１６０】
【図１ａ】本発明の一態様の概観のフローチャートである。
【図１ｂ】本発明において分類するのに使用されるプロセスのフローチャートである。
【図１ｃ】３つの領域に分割されたクラスタ空間を示す図である。
【図１ｄ】本発明のクラスタ方法のブロック図である。
【図１ｅ】蓄積された文書クラスタの２次元アレイを示す図である。
【図１ｆ】本発明の電子メール、シングリング、及び形成されたクラスタを示す図である。
【図１ｇ】スタックにおいて発生頻度の高い点を有する電子メールクラスタを示す図である。
【図２ａ】本発明のブロック図である。
【図２ｂ】本発明の学習マシンの特徴の図である。
【図２ｃ】本発明の学習マシンの図である。
【図２ｄ】本発明のスタック可能ハッシュ手段の図である。
【図３ａ】いくつかのフィルタ値にプロットされたしきい値の関数としてのスパムクラスを示す図である。
【図３ｂ】スパムクラスの関数としての最適なしきい値を示す図である。
【図３ｃ】ハッシュを形成するプロセスのブロック図である。
【図３ｄ】本発明で使用される均一フィルタのブロック図である。
【図４ａ】本発明の方法論のブロック図である。
【図４ｂ】本発明の一代替的な方法論のブロック図である。
【図５】本発明のブロック図である。
【図６】本発明の方法論のブロック図である。
【図７】本発明の装置のブロック図である。
【図８】本発明のフィルタの概略図である。
【図９ａ】一組の蓄積された文書クラスタを示す図である。
【図９ｂ】一組の蓄積された文書クラスタを示す図である。
【図１０】圧縮比の図である。
【図１ａ】
2008529105.tif 000007
【図１ｂ】
2008529105.tif 000008
【図１ｃ】
2008529105.tif 000009
【図１ｄ】
2008529105.tif 000010
【図１ｅ】
2008529105.tif 000011
【図１ｆ】
2008529105.tif 000012
【図１ｇ】
2008529105.tif 000013
【図１ｈ】
2008529105.tif 000014
【図２ａ】
2008529105.tif 000015
【図２ｂ】
2008529105.tif 000016
【図２ｃ】
2008529105.tif 000017
【図２ｄ】
2008529105.tif 000018
【図３ａ】
2008529105.tif 000019
【図３ｂ】
2008529105.tif 000020
【図３ｃ】
2008529105.tif 000021
【図３ｄ】
2008529105.tif 000022
【図４ａ】
2008529105.tif 000023
【図４ｂ】
2008529105.tif 000024
【図５】
2008529105.tif 000025
【図６】
2008529105.tif 000026
【図７】
2008529105.tif 000027
【図８】
2008529105.tif 000028
【図９ａ】
2008529105.tif 000029
【図９ｂ】
2008529105.tif 000030
【図１０】
2008529105.tif 000031
【誤訳訂正書】
【提出日】平成19年7月20日(2007.7.20)
【誤訳訂正１】
【訂正対象書類名】明細書
【訂正対象項目名】００２７
【訂正方法】変更
【訂正の内容】
【００２７】
一例として、以下の電子メールの写しは、同じクラスタに属するものとして考えることができる。
Looking For Mortg.age? You are already APPR.OVED by us! 
Louking foR Mo.rtgage! You are already AproOVED by us. 
LOOk-ing For M.o.rtg.age? U r alredy eppRO:ved by us... 
LOOk-ing For Mo.rgage? Yo ar alreedy AppROC.ved by us; 
Loking FOR M.o.rtg.age? yoo r alreaDY eppRO:ved by Us. 
Loiking for Moortg.age? yo r alrady ap-proved by uS// 
Leoking fr mortGAGE! You! ARE alrady ahpRO:ved by USS. 
Loooking fr mo..rt;gage; yoU Re alRReady AppRO:ved by UUS! 
【誤訳訂正２】
【訂正対象書類名】明細書
【訂正対象項目名】０１１２
【訂正方法】変更
【訂正の内容】
【０１１２】
データベース５１１は、本明細書で説明したシステムによって作成されるような分類データ及びクラスタリングデータ、又は（ａ）外部ソース５１８からさらに受信されたか、（ｂ）若しくは、インターネット接続５２６ｂ及び５２４等のインターネット接続を通じてダウンロードされて中央サーバ５４０及び関連するデータベース５２２から受信できるような分類データ及びクラスタリングデータを含む。
【国際調査報告】
2008529105.tif 000032