JPH06274193A

JPH06274193A - データベース検索システム

Info

Publication number: JPH06274193A
Application number: JP5084154A
Authority: JP
Inventors: Katsunobu Shibata; 克信柴田
Original assignee: Nippon Steel Corp
Current assignee: Nippon Steel Corp
Priority date: 1993-03-17
Filing date: 1993-03-17
Publication date: 1994-09-30
Anticipated expiration: 2019-07-21
Also published as: JP3545007B2

Abstract

(57)【要約】【目的】波形または数値列のデータについて特徴量抽
出、量子化を行うデータベース検索システムを提供す
る。【構成】検索対象となる波形・数値列データを複数の
ブロックたるフレームに分割し、通し番号（フレーム番
号）を付与する。このフレームを検索対象データの検索
単位とし、学習においては検索単位ごとに特徴量抽出、
量子化、コード列化の処理を施し、データを保存する。
特徴量抽出は窓付きのフーリエ変換、ウェーブレット変
換、一般の直交変換等により行われる。検索において
は、検索キーとなる波形・数値列データに対して、特徴
抽出、量子化、コード列化、重み付けの処理が行われ
る。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、データベースから必要
な情報を取り出すためのデータベース検索システムに関
し、特に波形、数値列等のデータについてのデータベー
ス検索システムに関する。

【０００２】

【従来の技術】現状のデータベース検索における検索空
間圧縮の手法としては、キーワードなどのインデックス
情報を付加する方式によるものが一般的である。また、
対象物件数が比較的小数のケースでは、全物件検索方式
が実用化されている。たとえば文書データにおいては効
率的な全物件検索手法として、ボイヤーモア法が考案さ
れている。

【０００３】

【発明が解決しようとする課題】このインデックス検索
方式は、以下のような欠点を有する。（１）物件１つ１つにインデックスを付加しなくてはな
らない。（２）任意のインデックスを付加して行くと、その個数
は膨大になるため、たとえばキーワードインデックスの
場合にはシソーラスによる管理などを必要とし、その維
持に多大なコストがかかる。（３）付加されるインデックスが必ずしも適切なものと
は限らない。すなわち現状のデータベース検索方式で
は、特に物件数が膨大になった時に必要なコストに比し
てパフォーマンスが伸びない傾向が現れる。

【０００４】一方、全物件検索方式では、上記のような
問題は発生しない。しかし、直接検索方式では、物件数
が膨大になったとき、検索時間は対話的な時間の域を大
幅に超過し、実用にならないのが現状である。また、全
物件検索方式におけるあいまい一致条件では完全一致よ
りさらに検索時間が必要となる。

【０００５】出願人は先に、全物件検索でありながら、
検索時間を飛躍的に短縮することができ、またあいまい
一致検索ができるデータベース検索方式を特願平３−１
２２７６６号として提案した。

【０００６】ところで、上述のボイヤーモア法による全
物件検索では、文書以外のデータ、たとえば物理的な時
系列データを扱うことができないという問題があった。
また、前記の特願平３−１２２７６６号に係る検索シス
テムにおいても、波形、数値列等のデータの場合には、
これらのデータ列の有意な情報単位が文書データと異な
り、特徴量を抽出し量子化することが困難であるため、
これらのデータを対象とすることができないという問題
があった。

【０００７】すなわち、波形、数値列データは、文書デ
ータ等と異なり、サンプリングされた数個の値だけで特
徴をもつことがない。したがって、何らかの方法によっ
て情報の抽出度を上げて検索データへの依存度を弱める
必要がある。現状において、波形、数値列データの検索
は主にDynamic Programingマッチング、隠れマルコフモ
デルなどの手法を用いた逐次マッチングにより実現され
ている。しかしながら、これらの手法は多くの計算コス
トを必要とするため、特に大規模システムへの適用にお
いては検索時間の点で問題を生じる。また、文書データ
におけるキーワードに相当する２次情報を事前に作成す
ることで検索時間を短縮する手法も考えられるが、有意
な情報単位の一般的定義が困難であるため、実現された
例は少ない。

【０００８】本発明は、上記のような問題に鑑み、特定
の意味を有する情報単位が文書データと比較して大きい
波形、数値列データについて、全物件検索でありながら
検索時間を飛躍的に短縮することができ、またあいまい
一致検索ができるデータベース検索方式を提供すること
を目的とする。

【０００９】

【課題を解決するための手段】本発明の波形、数値列デ
ータを対象とするデータベース検索システムは、波形・
数値列データを検索を行う所定の検索単位に分割する分
割手段と、分割手段によって分割された検索単位ごとに
特徴量抽出を行う特徴量抽出手段と、特徴量抽出手段に
よって特徴量抽出を行われたデータについて量子化を行
う量子化手段と、検索時に、検索キーとなる波形・数値
列データに対して、重み付けの処理を行う重み付け手段
とを具備する。

【００１０】

【作用】本発明によれば、波形、数値列データ情報の抽
象度を上げて検索データへの依存性を弱めることがで
き、波形、数値列データについて全物件検索でありなが
ら検索時間を飛躍的に短縮することができ、またあいま
い一致検索ができる。

【００１１】

【実施例】次に図面により本発明の実施例を説明する。
本発明の検索システムにおいては、検索対象となる波形
・数値列データを検索を行う単位である検索単位に分
け、この検索単位ごとに昇順の符合を付与する。学習に
おいては１つの検索単位に対して特徴抽出、量子化、コ
ード列化の処理を施し、データを保存する。

【００１２】検索においては、検索キーとなる波形・数
値列データに対して、特徴抽出、量子化、コード列化、
重み付けの処理が行われる。

【００１３】本発明による検索システムにおいて、対象
とされる波形、数値列データの特徴抽出は、データが時
系列であると考えた場合、時間的に局所化した関数との
内積を取ることにより特徴量を抽出することが基本的な
考え方である。内積値は、その時間近傍での特徴を反映
していると考えることができる。特徴量の抽出は、以下
の方法が例として挙げられる。１．窓付きのフーリエ変換、特徴軸は周波数これは窓関数を用いて境界付近の歪みを抑えつつ、一定
の分解能で短時間の周波数成分を抽出するものである。２．ウェーブレット変換、特徴軸は基本関数のスケールこれは時間と周波数の成分を同時に扱い、周波数によっ
て時間分解能が変化するものである。３．一般の直交関数系、特徴軸は基本多項式の展開係数これは時間分解能一定で、波形のトレンドに重点を置く
ものであり、たとえばルジャンドル多項式があげられ
る。上記の特徴抽出は十分に高速であることが、望ましい。

【００１４】次にこれらの特徴抽出方法について説明す
る。図１に示すように、波形、数値列データを複数のブ
ロックたるフレームに分割し、通し番号（フレーム番
号）を付与する。このフレームを検索対象データの単位
とする。

【００１５】次に波形、数値列データを時間軸方向、す
なわち波形の振幅方向と垂直な軸方向に窓を被せ、この
窓を特徴量抽出対象領域としてこの区間で特徴抽出を行
う。

【００１６】この窓を走査し、各区間で計算された特徴
ベクトル、すなわち特徴抽出の方法にしたがって周波
数、スケール、展開係数を成分とする特徴ベクトルの時
系列を生成する。

【００１７】例を上げて説明する。サンプリングされた
波形あるいは数値列データを時間ｔの関数であるとし、
Ｆ(t) (t=0,1,,,,) で表す。時間０の回りに局在した関
数をＧ(t,p) とする。ただし、ｐは特徴を定義するパラ
メータである。このとき時刻Ｔの近傍の特徴値は内積

【００１８】

【数１】

【００１９】で定義される。ただし、２×ａはＴを中心
とする窓の区間の大きさを表す。すなわち窓は区間[T-
a, T+a]で定義される。

【００２０】例えば、Ｇ(t, p)は窓付きのフーリエ変換
の場合、Ｇ(t, p) = 0.5× exp(-i ×p ×t)｛1+ cos( π×t/
a)｝｜t ｜≦ a (i は虚数単位) i²= -1 Ｇ(t, p) = 0 ｜t ｜≧ a ウェーブレット変換の場合、Ｇ(t, p) = exp(-t ＾2/p ＾2+i ×5 ×t/p)/ √p
｜t ｜≦ a (i は虚数単位) i²= -1 Ｇ(t, p) = 0 ｜t ｜≧ a などを用いることができる。

【００２１】また、関数Ｇ()が複素関数である場合には
I(T,p)の絶対値を特徴量とし、T-pの二次元平面上に特
徴量が計算される。

【００２２】図２（ａ）（ｂ）には、窓付きのフーリエ
変換およびウェーブレット変換の基本関数の例をそれぞ
れ示す。また、図３（ａ）（ｂ）には、窓付きのフーリ
エ変換およびウェーブレット変換の時間分解能の比較を
示す。

【００２３】次に図１に示すように、得られた特徴ベク
トルの量子化を行う。量子化はまず、軸方向T 、p の量
子化が行われる。

【００２４】まず、各軸方向で区間を設定する。例え
ば、T 軸方向で[a×k,a ×(k+1)](k = 0,1,,,,) 、p 軸
方向で[b×l,b ×(l+1)](l = 0,1,,,,) とする。この区
間内で量子化値 D[i,j] を所定の演算により決定する。
例えば 1. 区間ごとにある規則に従って代表点を選び、その点
での特徴量をそのままその区間の特徴量とする。 2. 区間内での平均値を計算する。などの方法が考えられる。これらにより特徴平面はベク
トル系列( あるいは行列) に変換される。

【００２５】次に、特徴量の量子化として、それぞれの
ベクトル成分を最大値などで正規化した後に量子化す
る。例えば４ビット、２ビットなどで表現される最大数
で正規化し、このビットで量子化する。

【００２６】上記の処理でデータの正規化は一応なされ
たが、さらにこのベクトル近傍( ベクトル同士の近傍あ
るいは、成分での近傍）から数値列を再定義し近傍特徴
量とすることも可能である。検索単位である波形のｋ番
目のベクトルのｌ番目の要素をV[k,l]とする時、例え
ば、この近傍での特徴量 I_R[k,l] は、関数h() を定義
して、 I_R[k,l] = h(V[k,l],V[k,l+1],V[k+1,l],V[k+1,l+1] で求められる。

【００２７】一方、検索時には、近傍特徴量に特徴軸方
向に重み付けを行うことも可能である。これは、検索時
に任意に設定する、あるいは類似であると定義するもの
を繰り返し提示し、学習することによって定義すること
も可能である。

【００２８】例えば、特徴量 I_R[*,l](* は任意) での
重みをA[ｌ] とし、波形１の特徴量を I_R1[k,l] 、波形
２の特徴量を I_R2[k,l] とする時、I_R1[k₁,l] = I
_R2[k₂,l] となるような k_1, k₂が存在するならば、A
[ ｌ] +=dAとし、それ以外のｌについては、 A[ ｌ] -=
dAとする。ただし、A[l]の初期値は１とし、dAは１に比
べ非常に小さい数である。

【００２９】上記のような波形、数値列データの特徴量
抽出、量子化は、たとえば次のようなデータ検索システ
ムにおけるデータの処理に適用できる。

【００３０】図４は、本発明が適用される自己相関記憶
型パターン検索システムのデータフロー図である。この
検索システムでは、予め全対象物件から事象（情報）の
位相情報を全て捨象した近傍特徴量データを作成し、そ
のデータ群に対して全物件検索を行なう。検索のアルゴ
リズムは、学習ステップと検索ステップとからなる。学
習ステップでは、物件毎に近傍特徴量行列が位相情報と
して作成される。検索ステップでは、検索キーと近傍特
徴量行列とのマッチング演算が行なわれ、物件ごとにマ
ッチング度（類似度）を示す評価結果を得る。以下、各
ステップについて説明する。

【００３１】（１）、学習ステップ図４に於いて、検索対象１０は、例えば日本語、英語、
ドイツ語、フランス語、ヘブライ語、ロシア語などの文
書データ、或いは本発明の特徴たる量子化された波形数
値データや、化学構造式、遺伝子情報などである。この
ような検索対象に対して、まず正規化手段Ｓ１により正
規化の処理を行なう。一般に検索対象は、情報の最小単
位（文書であればアルファベットなどの文字、数値チャ
ートであれば、ある時刻における実数値など）の列で表
現されている。それをなんらかの方法でｎ階調の整数列
に変換する。これをデータの正規化と呼ぶ。本発明にお
いては前述のように正規化が行われる。

【００３２】正規化されたデータ２０は、次に学習手段
Ｓ２により近傍特徴量行列３０の形式に畳込まれる。こ
こで近傍特徴量をとる演算式は種々考えられる。この演
算式は検索の鋭さ（過検出の少なさ）にも影響を与え
る。

【００３３】今、ｉ番目の物件のｊ番目のデータをＣ
_i,jとし、Ｃ_i,jに関する量子化量ｘとＣ_i,jの前方ｋ
近傍に関する量子化量ｙを次のようにして求める。ここ
では、検索される対象物件がｎ個あるとし、そのうちの
ｉ番目の物件の量子化について説明する。ｉ番目の物件
において、図５に示すように正規化された数値列135,6
4,37,71,101,...が並んでいるとすると、Ｃ_i,jに関す
る量子化量ｘは、ｘ＝f(Ｃ_i,j）Ｃ_i,jの前方ｋ近傍に関する量子化量ｙはｙ＝g(Ｃ_i,j, Ｃ_i,j+1,Ｃ_i,j+2,....,Ｃ_i,j+k) で求められる。

【００３４】ここで、f(Ｃ_i,j）はＣ_i,jに関するｎ段
階量子化関数である。すなわち、ｉ番目の物件のｊ番目
のデータＣ_i,jについて所定の演算を行って得られる値
であり、１〜ｎのいずれかの整数で表される。したがっ
て、得られたｘの値によって図６に示す行列（座標）に
おいてｘ軸方向の位置が１〜ｎの範囲で定まる。

【００３５】また、g(Ｃ_i,j, Ｃ_i,j+1,Ｃ_i,j+2,....,
Ｃ_i,j+k) は、Ｃ_i,jの前方ｋ近傍に関するｍ段階量子
化関数である。すなわち、ｉ番目の物件のｊ番目のデー
タＣ_i,jとそのデータの近傍の所定の数のデータについ
て所定の演算を行って得られる値であり、１〜ｍのいず
れかの整数で表される。たとえば図５に示すようにｊ番
目のデータＣ_i,jが１３５であり、ｋが３の場合には、
Ｃ_i,j+1,Ｃ_i,j+2,Ｃ_i,j+3としてデータ１３５に続くデ
ータ６４、３７、７１を抽出し、これらのデータとデー
タ１３５との相関について所定の演算を行う。ｊ番目の
データＣ_i,jが次の６４の場合には、Ｃ_i,j+1,Ｃ_i,j+2,
Ｃ_i,j+3としてデータ６４に続くデータ３７、７１、１
０１を抽出し、これらのデータとデータ６４との相関に
ついて所定の演算を行う。

【００３６】このようにして得られたｙの値によって、
図６に示す行列（座標）におけるｙ軸方向の位置が１〜
ｍの範囲で定まる。したがって、上記のようにｘ、ｙを
求めることによって図６に示す行列（座標）における位
置が定まる。

【００３７】本システムでは、各物件情報は、上記のよ
うにして求めたｘ、ｙに対して物件の通番ｉと重みｗ
（x,y,i)の組として記憶される。重みｗ（x,y,i)は、デ
ータｘ、ｙ、ｉから所定の演算によって求められるが、
通常は重みｗ（x,y,i)の値は１に固定される。

【００３８】上記のようにして求められたデータＣ_i,j
ごとにｘ、ｙの値に基づき図６に棒によって示されるよ
うに、データを記憶する。すなわち、データＣ_i,jの
ｘ、ｙの値によって定められる座標の位置に、その物件
の通番ｉとその重みｗ（x,y,i)を組みとしたデータを記
憶する。同図ではこのようなデータが記憶されるごとに
棒の長さが延びるように表されている。通常は重みｗ
（x,y,i)は１とされるから、物件の通番ｉのデータのみ
がｘ、ｙの値によって定められる座標の位置に記憶され
てゆく。

【００３９】この様にして作成された近傍特徴量行列に
物件の識別番号を付加して構造ファイル４０として保存
する。

【００４０】（２）、検索ステップまず検索キー５０を入力する。この検索キー５０に対し
て学習ステップと同一の正規化方法に基づく正規化手段
Ｓ３によりキー情報を整数列に正規化する。

【００４１】次に、検索手段Ｓ４において、学習ステッ
プと同一の自己相関計算式f() 、g() を用いて各物件に
対応する正規化された数値列の先頭からｘ、ｙの組の系
列を作成する。次に、このｘ、ｙの組の系列に基づい
て、物件ｋに対する検索キーの含有度数ω_kとして、Ｖ
（ｘ_j,ｙ_j,ｋ）をｊ＝１〜ｍについて合計することによ
り算出する。

【００４２】ただし、Ｖ（ｘ_j,ｙ_j,ｋ）は、物件情報リ
ストが物件ｉについての重みを持つ場合、はその重みに
等しく、持たない場合には０と定める。

【００４３】したがって、検索すべき数値列のｘ、ｙの
組に対応する図６のｘ、ｙの位置にデータがある場合
（棒がある場合）には、別に設けられた記憶手段のその
データに示される物件の通番ｉの格納箇所にその重みの
値を記憶させる。

【００４４】次に、評価結果出力手段Ｓ５において、物
件毎に得られた構造評価値score （合致度）を完全一致
の場合の評価値で割って、検索キーの含有確率を求め、
評価結果のリスト７０を得る。更にソート手段Ｓ６にお
いて、このリスト７０を含有確率の降順にソートしソー
ト済みリスト８０を得る。

【００４５】このソート済みリスト８０が検索結果であ
り、その上位物件を参照することにより、検索キーが物
件中に含まれている確率が高い物件名を知ることができ
る。含有確率は、完全一致及び不完全一致の全てについ
て求まるから、あいまい一致検索を行なうことができ
る。

【００４６】また、検索キーの全情報についての全物件
探索であるから、検索もれが発生する確率は、本質的に
零であると言う特徴がある。

【００４７】また、１つの物件に対する検索キーの評価
時間は、キーのデータ数のみに依存し、物件の大きさに
は依存しない。従って、非常に高速に検索を行なうこと
ができる。

【００４８】また検索結果のリストどうしの論理演算を
行うことにより、検索条件に対するＡＮＤ、ＯＲなどの
検索演算処理も高速に実行できる。式（１）の自己相関
式は上述の例の他に種々考えることができる。例えば、 f: x→x g: (x,y)→x-y （または｜x-y ｜）とすれば、隣接データ及び一つ置きのデータの差分（ま
たは差分の絶対値）を相関情報として近傍特徴量行列を
作ることができる。また幾つかのデータ列の個々のデー
タ整数値に対し四則演算を施すことにより近傍特徴量を
取り出してもよい。

【００４９】近傍特徴量は、各物件の全データを対象と
し取り出さなくてもよい。例えば、物件データ中の特定
の一つまたは一つ以上の整数値、特定の範囲の整数値、
或いはデータ列を構成する各バイト中の特定の１つまた
は一つ以上のビットを除外して近傍特徴量を捨象しても
よい。

【００５０】上述の例では、近傍特徴量によって生成さ
れる行列は、２５６次のビット行列であり、これは８K
バイトに相当する。従って、１物件のデータが１K バイ
ト程度であるデータベースでは、効率のよいシステムで
あるとは言えない。そこで上記のようなデータ圧縮手段
Ｓ７を設けてデータ圧縮を行なって構造ファイル４０の
容量を減らすのがよい。

【００５１】上述の実施例において，正規化手段Ｓ１、
学習手段Ｓ２、正規化手段Ｓ３、検索手段Ｓ４、評価結
果出力手段Ｓ５、ソート手段Ｓ６、データ圧縮手段Ｓ７
は、コンピュータプログラムによって構成することがで
きるが、論理回路素子を用いて専用のハードウエアを構
成してもよい。

【００５２】前述のような波形、数値列データの特徴量
抽出、量子化を上記の検索システムに適用すれば、波
形、数値列データの検索を有効に行うことができる。

【００５３】

【発明の効果】本発明は波形、数値列データの特徴量抽
出、量子化を行うようにしているからこれらのデータを
対象とする検索を有効に行うことができる。

【図面の簡単な説明】

【図１】本発明による特徴量抽出、量子化の例を示す図
である。

【図２】本発明に用いられる基本関数の例を示す図であ
る。

【図３】本発明に用いられる変換の解像度の例を示す図
である。

【図４】本発明によるデータベース検索システムのデー
タフロー図である。

【図５】近傍情報の量子化を示す図である。

【図６】記憶される情報構造を示す図である。

【符号の説明】

３０近傍特徴量行列４０構造ファイル５０検索キー６０正規化キー７０評価結果リスト８０ソート済みリストＳ１正規化手段Ｓ２学習手段Ｓ３正規化手段Ｓ４検索手段Ｓ５評価結果出力手段Ｓ６ソート手段Ｓ７データ圧縮手段

Claims

【特許請求の範囲】

【請求項１】波形、数値列データを対象とするデータ
ベース検索システムにおいて、波形・数値列データを検索を行う所定の検索単位に分割
する分割手段と、前記分割手段によって分割された前記検索単位ごとに特
徴量抽出を行う特徴量抽出手段と、前記特徴量抽出手段によって特徴量抽出を行われたデー
タについて量子化を行う量子化手段と、検索時に、検索キーとなる波形・数値列データに対し
て、重み付けの処理を行う重み付け手段とを具備するこ
とを特徴とするデータベース検索システム。
【請求項２】前記特徴量抽出手段は、データの時系列
を第一の軸とし、各特徴成分を第二の軸とする二次元平
面上に特徴量の分布として、特徴量の抽出を行うことを
特徴とする請求項１に記載のデータベース検索システ
ム。
【請求項３】検索対象の物件毎にその近傍特徴量を記
憶した記憶手段と、検索キーの近傍特徴量と検索対象の上記近傍特徴量との
合致度を物件毎に求め、物件番号を合致度の降順に出力
する検索手段とを具備するデータベース検索に用いられ
ることを特徴とする請求項１のデータベース検索システ
ム。
【請求項４】検索対象のｉ番目の物件のｊ番目のデー
タ列Ｃ_i,jに関する量子化量ｘとその近傍のｋ個のデー
タ列Ｃ_i,j+1,Ｃ_i,j+2,....,Ｃ_i,j+kに関する量子化量
ｙとをｘ＝f(Ｃ_i,j）ｙ＝g(Ｃ_i,j, Ｃ_i,j+1,Ｃ_i,j+2,....,Ｃ_i,j+k) によって求め、得られたｘ、ｙの値に基づいて定められ
る記憶手段の位置にその物件の通番ｉを記憶するデータ
ベース検索に用いられることを特徴とする請求項３のデ
ータベース検索システム。