データベースS

データベースＳ
第13回マルチメディアデータベース
システム創成情報工学科尾下真樹
試験とレポート
スケジュール
• 7/27（金）レポート提出締め切り
• 7/30（月） 2限目試験
• レポートの大まかな点数とコメントを個別に
公開する予定
– レポート提出と同じシステム上で個別に提示
• 成績は、レポート締め切り終了後、なるべく
早目に公開予定
レポート
• 提出締め切り
– 7/27（金） 18:00
• 講義のページから提出
– ファイル形式を守ること
– 提出後は、自分でダウ
ンロードして表示できる
ことを確認すること
• 読めないファイルを提出
しても評価しない
– 締め切りまで修正可能
試験
• 教科書・ノートなどの持込は不可
• 出題範囲
– 講義で取り扱った内容全て
– 重要な概念を理解しているかどうか、アルゴリズ
ムや考え方を理解しているかどうかを問う問題
を出す
– 演習問題・過去問や講義資料を眺めておくだけ
では不十分だと思われるので注意
• 講義資料は、あくまで講義の補助資料なので、講義
の説明をきちんと聞いて理解していなければ、後から
資料だけ見ても理解できない
成績判定と再試験
• 成績判定
– 演習レポート（40点）＋試験（40点）
＋毎回の演習問題・課題（20点）
• 再試験は基本的に行わない（シラバス通り）
– もし、再試験を行う場合は、
• 全員受験可能とする
• 本試験と同じ難易度の問題を出す
• 試験点は、再試験の点数に80%をかけたものとする
– 再試験・レポート再提出等を場合は、夏休み～
再試期間中に連絡する
• いちいち個別に質問に来ないこと
今回の内容
• オブジェクト指向データベース
• マルチメディアデータベース
– 特徴量を使った検索
– （地理情報データベース）
– （テキストデータベース）
オブジェクト指向データベース
オブジェクト指向データベース
• マルチメディアデータや複雑なデータの扱い
に適している
• リレーションではなく、オブジェクトとしてデー
タを定義
class 従業員
{
番号, 部門, 氏名, 住所, 給与
従業員（番号, 部門, 氏名, 住所, 給与）
}
番号部門
氏名
住所給与
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
従業員
従業員
従業員
・・・・・・
・・・・・・
・・・・・・
オブジェクト指向データベースの利点
• 配列や集合を属性に持たせることができる
• データ＋メソッドを組み合わせることができる
• カプセル化
• 継承
• ポリモーフィズム
可変長の属性の利用
• 属性には、オブジェクト指向プログラミング言
語と同様、配列や集合なども使える
番号部門
氏名
住所給与
・・・
・・・
・・・
・・・
上司部下
1
2
1
5
2
3
2
6
・・・
class 従業員
{
Set< 従業員 > 部下;
}
複数の値（参照）を持つ属性を定義可能
リレーショナルモデルで
は、１対多、多対多の
関係を表すために別の
リレーションを定義して
いた
従業員
部下
・・・・・・
従業員
従業員
・・・・・・
・・・・・・
メソッドの利用とカプセル化
• メソッドをデータに組み合わせることができる
• メソッド経由でアクセスすることで、不正な
データ変更が防げる
従業員
番号部門
氏名
住所給与
・・・
・・・
・・・
・・・
・・・
従業員の属性値
給与計算処理
給与計算処理
住所変更処理
リレーションとは別に
様々な処理を作成し
て管理する
住所変更処理
オブジェクトと処理をセットにできる
定義したメソッドは簡単に呼び出せる
継承の利用
• 継承により共通の属性を持つオブジェクトを
階層的に定義できる
従業員（番号, 部門, 氏名, 住所, 給与）
番号部門
氏名
住所給与
・・・
・・・
・・・
・・・
従業員
属性値
・・・
役員（番号, 従業員番号, 役職）
継承
番号
従業員番号
役職
役員
派遣社員
・・・
・・・
・・・
従業員
属性値
従業員
属性値
属性値
属性値
派遣社員（番号, 従業員番号, 派遣元）
番号
従業員番号
派遣元
・・・
・・・
・・・
全て従業員として共通に扱える
ポリモーフィズム
• 同一のインターフェースで、クラスごとに振る
舞いを変えることができる
– 例：「給与計算」というインターフェースを定義
各クラスごとに、異なる計算方法を定義できる
全オブジェクトの「給与計算」を呼べば、自動的
にオブジェクトに合った方法で計算される
従業員
役員
派遣社員
給与計算処理
給与計算処理
給与計算処理
役員や派遣社員のメソッドをオーバーライドすれば、同じ給与計
算処理を呼び出しても、オブジェクトに応じた処理が実行される
オブジェクト指向データベースの利用
• OQLを使った検索
– SQLのオブジェクト指向データベース版
• ユーザプログラムからの利用
– オブジェクト指向プログラミング言語から、通常
のオブジェクトとしてアクセスできる
• C++, Java, SmallTalk バインディング
– 永続オブジェクト
• 一度作成されたオブジェクトは、プログラムが終了し
てもデータベースに存在し続ける
– OQLよりも高度な処理が行える
問題点
• データを表形式で扱うことができない
– データを一覧表示したりするのが面倒
• 処理効率の問題
– オブジェクト単位でデータを操作しなければいけ
ないので、メモリ管理や並列処理などがかなり
複雑になる
– あまり高いパフォーマンスが得られない
• プログラミング言語からの使い方などを含め
て学習する必要がある
オブジェクト指向データベースの現状
• 現在はごく一部のマルチメディアデータベー
スなどで利用されている
– マルチメディアデータは、多くの処理を必要とす
るので、データと処理を一緒に管理できると都合
が良い
– 一般的にはあまり利用されていない
• 最近は、従来のリレーショナルデータベース
にオブジェクト指向拡張を取り入れる動きが
盛んになっている
マルチメディアデータベース
マルチメディアデータベース
• マルチメディアデータ
– 画像、音楽、動画
– 地理情報
– 文書、ウェブページ
• 通常のデータベースとの違い
– データ管理については同様の方法が使える
• ただしそれぞれのデータのサイズは非常に大きくなる
場合がある
– 必要とされる検索機能が大きく異なる
マルチメディアの検索
• メタデータに基づく検索
– 例：1956年にマグリットによって
描かれた絵画を検索
– あらかじめ、メタデータがデータ
ベースに登録されていれば、
SQLなどを使って検索可能
• 内容に基づく検索
マグリット(1956) ピレネーの城
– 例：空の描かれている絵画を検索
– データの内容に基づいて検索を行う必要がある
ので、単純な SQL などでは検索できない
マルチメディアデータ
データ
メタデータ
データに関する説明のためのデータ
画家
絵画名
マグリット
ピレネーの城
制作年所蔵美術館
1956
• データ量が大きい
• データ量は小さい
• SQLによる検索は困難
• SQLによる検索が可能
それぞれ異なる情報を持つので、両方の
情報でも検索できることが望まれる
特徴量を使った検索
特徴量を使った内容検索
• そのままのデータでは、検索が困難
– データ量が非常に大きい
– 多種の情報が混在しており、単純比較できない
• データの特徴をうまく表すような特徴量を計
算し、その特徴量を使って検索を行う
– 最大でも数十次元程度のデータに次元を減少
– データ同士の類似度などを何らかの意味のある
尺度で評価できるようになる
特徴量の例
• 画像の特徴量の例：ヒストグラム
– 画像全体のRGBの割合を計算
• ３次元の特徴量の例（通常はもっと高次元を使用する）
B
R
G
各画像は３次元空間上の
点として表現できる
検索インターフェース
• 検索方法
– ユーザが特徴量を直接指定
• 欲しいデータをうまく記述するのは難しい
– あるサンプルデータを入力して、そのデータの特
徴量に近いデータを検索
特徴量を直接指定
B
R
サンプル画像を入力
G
特徴量空間での距離の定義
• ユークリッド距離
– 空間内の距離で評価
– 必ずしも正しい距離とは限らない
• 楕円体距離（マハラノビス距離）
– 次元によって分散の度合いが
異なるのを標準化した距離
A
B
• 各次元で最も差の大きい値
– ひとつでも値が離れていれば
遠いと判定
B
A
特徴量空間での検索の種類
• 範囲検索
– 範囲を指定して、範囲内の全
データを出力
– データの密集度に応じて、求
まるデータ数がばらつく
• k-近傍検索
– 入力した特徴量に近いデータ
のうち、最も近 k 個のデータ
を出力
– k の数は動的に増やせる
空間インデックス
• 特徴量空間での検索
– 全データとの距離計算を行っていると大量に
時間がかかる
– インデックスを使うことにより効率化できる
• 空間インデックス
– R-Tree
– S-Tree
– SR-Tree
R-Tree
• B-Tree の２次元以上のバージョン
– B-Tree は、１次元の値を順番に並べて管理する
– R-Tree も平衡木
– R-Tree ではノード同士のオーバーラップがある
1次元でのB-Tree
2次元でのR-Tree
高度な空間インデックス
• R-Tree の問題
– 範囲検索には向いているが、
k近傍検索には向いていない
• S-Tree
– ノードを球にしたもの
– 距離で検索しやすい
• RS-Tree
– 球と四角を組み合わせたもの
– 両方の利点を持つ
特徴量の選択
• 目的に適した特徴量を選ぶ必要がある
• 用途を限定したアプリケーション
– 用途に応じた特徴量を決めてやることで、比較
的低次元の特徴量でうまく判別することができる
– 例：顔写真、指紋認識、手書き文字認識など
特徴量の選択
• 一般的な画像の特徴量
– ヒストグラム
– エッジ情報
• 縦線・横線・曲線などの
割合を計算
– 画像をブロックに分けて、
それぞれの特徴量を計算
• より細かい指定・判定ができる
• 一般的な画像をうまく検索できる
ようなシステムはまだ難しい
応用例
• 顔認識、指紋認識など
– 特定用途の画像データベースは既に実用化
• 一般的な画像データベース
– 多くの研究用システムが開発されている
– 検索が難しいため、実用的なシステムは少ない
• 音楽データベース
– ハミングから音楽の検索など実用化されている
• 動画データベース
– スポーツのシーン検索などの用途向けに開発
地理情報データベース
地理情報データベース
• 地理情報データベース
– マルチメディアデータベースの一種
– 地図・道路・建物など、地理情報を扱う
– 例：地図、カーナビ、工事用図面など
ゼンリン日本地図
地理情報データベースの種類
• 地図データ（２次元）
• 地図データ＋高さ情報（２.５次元）
– 地図、カーナビなどに広く使われている
• 空間データ（３次元）
– 現在は建物など一部のデータに使われている
• 時空間データ（４次元）
– 時間軸も加えることで、時間変化も表せる
– まだほとんど実用的には使われていない
地理情報データの表現
• 各データは空間上の図形として表される
– 点（位置情報など）
– 折れ線（道路、川、境界線など）
– 多角形・立体（区域や敷地や建物など）
• 全ての図形は、頂点データとそのつながりで表される
点
折れ線
多角形
地理情報データの検索
• 図形データに対する検索処理が必要となる
– 範囲検索
• 指定範囲に図形が含まれるか求める
• 完全に含まれるか or 一部が含まれる
– 距離検索
• ユークリッド距離
• 経路探索
地理情報データの検索
• 図形データに対する検索処理が必要となる
– 図形同士の重なりに関する検索
• 例：九州工業大学内にある全建物を求めよ
敷地を表す図形と建物を表す図形同士の交差判定
図形同士の演算を含む計算
• インデックス
– 図形を四角形のような
単純な図形に置き換え
て簡易的に判定
– R-Tree のような空間
インデックスが利用できる
• 正確な判定処理
– インデックスでは、大まかな判定しかできないた
め、最終的には、図形同士の幾何情報を用いて
判定を行う必要がある
地理情報データベースの開発
• 地理情報を扱えるデータベースを利用
– PostgreSQL なども、データ型として図形データを
サポートしている
– ごく基本的な検索手法のみが提供されているの
で、必ずしも性能が得られるとは限らない
• データ格納にのみデータベースを利用し、
検索処理などは自力で開発
• 地理情報格納に適したデータベースを含め
て開発
テキストデータベース
テキストデータベース
• テキストデータベースの例
– Google などのWeb検索
– 企業内部の文書データベース
• テキストデータの検索
– 文章の一部に含まれている
単語を検索することが必要
とされる
・・・
・・・・・・
・・・・
・・・文字列検索・・・
・・・
・・・・・・
・・・・・・・・・・
・・・
テキストデータのインデックス
• あらかじめキーワードを（自動）抽出し、各
キーワードごとのインデックスを作成
– 効率の良いインデックスが作れる
– 日本語のように、明確に単語が区切られない言
語についてはキーワードを取り出すのが難しい
– 用意されているキーワードでしか検索できない
「文字列検索」
「文字」
「文字列」
「検索」
「列検索」
テキストデータのインデックス
• 任意のキーワードに対応したインデックス
• Ｎグラム
– 文章中に登場するＮ個の文字の組み合わせご
とにインデックスを作成しておく
• 例（Ｎ＝２）
「文字列検索」
文字列検索
「文字」「字列」「列検」「検索」
テキストデータのインデックス
• Ｎグラムを使った検索
– 検索文字が指定された場合は、Ｎグラムに分け
それぞれを検索し、結果を組み合わせて判定
– どのような文字列が来ても検索可能
• Ｎグラムの大きさ
– Ｎが大きいとキーの種類は大量になるが、キー
に対応するデータは減るため処理は効率的
– Ｎ＝２or３ぐらいが良く使われる
まとめ
• オブジェクト指向データベース
• マルチメディアデータベース
– 特徴量を使った検索
– 地理情報データベース
– テキストデータベース

Download Report