データ処理

特定の目的でデータを変換や処理を行うアルゴリズムや手法についてまとめているページです.

2018.8.5

72

Views
0

Watch
12

Knows

データ変換

ある与えられたデータを他のデータに変換するに当たって必要なデータ処理に関してまとめたページです.例えばハッシュ関数によって与えられたデータは固定サイズのデータに変換されます.

情報フィルタリング

おすすめの提示等溢れる膨大な情報の中から適切にユーザに必要な情報を抽出するといった情報フィルタリングに関連した情報についてまとめています.リコメンドシステム等もここで紹介します.

特定のルールに基づいたり特性を持つ数値を生成するアルゴリズムについてまとめます.

データ処理の新規投稿

メルセンヌ・ツイスタ

メルセンヌ・ツイスタ(MT, Primitive Twisted Generalized Feedback Shift Register Sequence)は非常によい性質を持ち合わせている擬似乱数生成アルゴリズムの一つで、様々なプログラミング言語の標準ライブラリに実装されている.メルセンヌ数を用いることで、この擬似乱数生成を実現しており、高次元においても均等分布する、長期的な周期、比較的高速、メモリ効率もよいといった特徴を持ちます.

xorshift+はxorshiftを元に他手法を参考に改善したもの.XSAddの検討時には低いビット列に乱数性が見られなかったが、xorshift+にすることで解決.

xorshiftは、近年発表されたビット演算のみで非常に高速に長期的な周期の乱数を得ることができる擬似乱数生成アルゴリズムです.しかし乱数を評価する統計的なテストに幾らか落ちており、xorshiftは乱数として信用できないとする声もあります.複数の発展系がありGoogleChromeでも発展系のxorshift+が使用されます.乱数は暗号学的安全性は保証されません.

Order Preserving Encryption

Order Preserving Encryption(順序保持暗号、順序保存暗号)は、入力された単語の特定の順番(大小関係)が暗号化後も保持されている暗号化技術.昔のOne Part Codeから使用されているものである.一般的にセキュリティは低くなってしまうが、通常の単語と同じようにデータベース上で範囲検索(Range)、MAX、 MINなどができるため、そういった分野で使用が想定される.

Two Part Codeは One Part Codeでは一つの暗号表があれば暗号化復号化できたのとは違い、対応する単語またはコードがランダムな順番なため暗号化用と復号化用の暗号表が必要な暗号化手法.暗号化用と復号化用が必要なのはどちらかだけでは反対の操作をするときに単語を見つけにくいだけなので、一冊あれば対応はわかる.

One Part Codeは単語と対応するコードが双方アルファベット順に対応している暗号化方式.どちらも順番になっているため、一部単語がわからなくても前後から推測が可能.

GeoHash(ジオハッシュ)は、緯度と経度の値を元に任意の場所、任意の精度でその位置を表現する短い文字列を得る.文字列が近いほど位置も近く(必ずとは限らない)、精度が高いほど文字列が長くなる性質.

Slope Oneはアイテム間協調フィルタリングの手法に似た手法の一つで、不明な評価値を他の評価値の平均差を使って単純に推定する.アルゴリズムが非常にシンプルであるが精度が高いため、様々なシステムで導入されている.

コンテンツベースフィルタリングとは

コンテンツベースフィルタリング(内容ベースフィルタリング)は、対象の商品またはアイテムの特徴量と、ユーザプロファイル(嗜好の傾向)の特徴量を算出しおすすめ商品を求めるフィルタリング技術.アイテムにはあらかじめ特徴的なキーワードを割り当てておく.ユーザの行動やアイテムの閲覧履歴等を参考にユーザの嗜好の特徴量をアイテムに記されているキーワード等から構築していく.ユーザの事前の情報がなくともある程度推薦を出せる.ユーザの嗜好の変化に合わせることや同じようなものばかりにならないようにすることがポイント.

アイテム間協調フィルタリング

アイテム間協調フィルタリング(Item-Item Collaborative Filtering)は、ユーザの購買履歴や評価の履歴を元に類似した評価を持つ商品を見つけ出し、ユーザにおすすめするフィルタリング技術.Amazonによって発表された手法で、ユーザベース協調フィルタリングより、「ユーザ数がアイテム数より多い時にもよい」「アイテムの類似度は変わりにくいため更新頻度が少ない」といった点が有利.

ユーザベース協調フィルタリング

ユーザベース協調フィルタリングはユーザの行動履歴や評価履歴を用いて各ユーザがどのように商品を扱ったかによって次におすすめする商品を決定するフィルタリング技術.あるユーザが同様の評価を行ったもの同様の評価を行っているユーザ、同様のものを買っているユーザを参考にまだ買っていないものを紹介する.この手法はユーザの情報から新しいものを推薦するメモリーベースの手法.

ハッシュ関数とは

ハッシュ関数とは与えられたデータを別の小さな値に変換する関数です.どのような変換を行うかについては自身で関数を選択する必要があります.幾らか求められる特徴があり、元の入力データが異なれば出力も異なることが期待されます.検索の高速化やデータ構造、データの一致、データの改竄検出など幅広く用いられる.

データ処理人気知識・質問

コンテンツベースフィルタリングとは

コンテンツベースフィルタリング(内容ベースフィルタリング)は、対象の商品またはアイテムの特徴量と、ユーザプロファイル(嗜好の傾向)の特徴量を算出しおすすめ商品を求めるフィルタリング技術.アイテムにはあらかじめ特徴的なキーワードを割り当てておく.ユーザの行動やアイテムの閲覧履歴等を参考にユーザの嗜好の特徴量をアイテムに記されているキーワード等から構築していく.ユーザの事前の情報がなくともある程度推薦を出せる.ユーザの嗜好の変化に合わせることや同じようなものばかりにならないようにすることがポイント.

ユーザベース協調フィルタリング

ユーザベース協調フィルタリングはユーザの行動履歴や評価履歴を用いて各ユーザがどのように商品を扱ったかによって次におすすめする商品を決定するフィルタリング技術.あるユーザが同様の評価を行ったもの同様の評価を行っているユーザ、同様のものを買っているユーザを参考にまだ買っていないものを紹介する.この手法はユーザの情報から新しいものを推薦するメモリーベースの手法.

アイテム間協調フィルタリング

アイテム間協調フィルタリング(Item-Item Collaborative Filtering)は、ユーザの購買履歴や評価の履歴を元に類似した評価を持つ商品を見つけ出し、ユーザにおすすめするフィルタリング技術.Amazonによって発表された手法で、ユーザベース協調フィルタリングより、「ユーザ数がアイテム数より多い時にもよい」「アイテムの類似度は変わりにくいため更新頻度が少ない」といった点が有利.

xorshiftは、近年発表されたビット演算のみで非常に高速に長期的な周期の乱数を得ることができる擬似乱数生成アルゴリズムです.しかし乱数を評価する統計的なテストに幾らか落ちており、xorshiftは乱数として信用できないとする声もあります.複数の発展系がありGoogleChromeでも発展系のxorshift+が使用されます.乱数は暗号学的安全性は保証されません.

xorshift+はxorshiftを元に他手法を参考に改善したもの.XSAddの検討時には低いビット列に乱数性が見られなかったが、xorshift+にすることで解決.

メルセンヌ・ツイスタ

メルセンヌ・ツイスタ(MT, Primitive Twisted Generalized Feedback Shift Register Sequence)は非常によい性質を持ち合わせている擬似乱数生成アルゴリズムの一つで、様々なプログラミング言語の標準ライブラリに実装されている.メルセンヌ数を用いることで、この擬似乱数生成を実現しており、高次元においても均等分布する、長期的な周期、比較的高速、メモリ効率もよいといった特徴を持ちます.

ハッシュ関数とは

ハッシュ関数とは与えられたデータを別の小さな値に変換する関数です.どのような変換を行うかについては自身で関数を選択する必要があります.幾らか求められる特徴があり、元の入力データが異なれば出力も異なることが期待されます.検索の高速化やデータ構造、データの一致、データの改竄検出など幅広く用いられる.

GeoHash(ジオハッシュ)は、緯度と経度の値を元に任意の場所、任意の精度でその位置を表現する短い文字列を得る.文字列が近いほど位置も近く(必ずとは限らない)、精度が高いほど文字列が長くなる性質.

Slope Oneはアイテム間協調フィルタリングの手法に似た手法の一つで、不明な評価値を他の評価値の平均差を使って単純に推定する.アルゴリズムが非常にシンプルであるが精度が高いため、様々なシステムで導入されている.

Order Preserving Encryption

Order Preserving Encryption(順序保持暗号、順序保存暗号)は、入力された単語の特定の順番(大小関係)が暗号化後も保持されている暗号化技術.昔のOne Part Codeから使用されているものである.一般的にセキュリティは低くなってしまうが、通常の単語と同じようにデータベース上で範囲検索(Range)、MAX、 MINなどができるため、そういった分野で使用が想定される.

Two Part Codeは One Part Codeでは一つの暗号表があれば暗号化復号化できたのとは違い、対応する単語またはコードがランダムな順番なため暗号化用と復号化用の暗号表が必要な暗号化手法.暗号化用と復号化用が必要なのはどちらかだけでは反対の操作をするときに単語を見つけにくいだけなので、一冊あれば対応はわかる.

One Part Codeは単語と対応するコードが双方アルファベット順に対応している暗号化方式.どちらも順番になっているため、一部単語がわからなくても前後から推測が可能.