プログラミング

データマイニングとはデータマイニングとは、リポジトリに蓄積された大量のデータを、パターン認識技術や統計・数学的手法を駆使して精査し、意味のある新しい相関関係、パターン、トレンドを発見するプロセスです。具体的には、観測データセットを分析して予期しない関係性を明らかにし、データ所有者にとって理解しやすく有益な形でレコードを要約することを指します。ここでは、データマイニングの代表的な用途について詳しく見ていきましょう。データマイニングの主な用途1. データウェアハウスとデータ前処理データウェアハウスは、情報交換とデータマイニングにおいて不可欠な基盤です。しかし、地理空間データの分野では、真の意味での

周期性分析とは、時間に関連する系列データの中から繰り返し現れるパターン（周期パターン）を発見するデータマイニング手法のことです。私たちの身の回りには周期的な現象が数多く存在します。例えば、四季の移り変わり、潮の満ち引き、惑星の軌道、一日ごとの電力消費量、日々の交通パターン、毎週放送されるテレビ番組などは、いずれも一定の周期パターンを持つ典型的な例です。 周期性分析の対象となるデータ 周期性分析は主に時系列データを対象として実行されます。時系列データとは、1時間ごと、1日ごと、1週間ごとなど、一定の等しい時間間隔で測定された値やイベントの連なりを指します。 さらに、オンライン取引のように、値や

データマイニングやグラフマイニングの分野において、頻出部分構造（frequent substructure）の発見は重要なタスクの一つです。本記事では、頻出部分構造発見の基本的な流れと、代表的な2つのマイニング手法である「アプライオリ型アプローチ」と「パターングロース型アプローチ」について詳しく解説します。頻出部分構造発見の基本的な2つのステップ頻出部分構造の発見は、通常以下の2つのステップで構成されます。第1ステップでは、頻出部分構造の候補を生成します。続く第2ステップでは、生成された各候補の頻度を検証します。第2ステップには部分グラフ同型性判定（subgraph isomorphism t

ソーシャルネットワークの定義ソーシャルネットワークとは、グラフ（グラフ構造）によって表現される異種かつ多関係的なデータ集合です。このグラフは一般的に非常に大規模であり、ノード（頂点）はオブジェクト（対象）に、エッジ（辺）はオブジェクト同士の関係やつながりを記述する接続に対応します。ノードとエッジの両方が属性を持つ点が特徴で、オブジェクトにはクラスラベルが割り当てられることもあります。また、リンクは一方向（有向）である場合もあり、必ずしも二値である必要はありません。ソーシャルネットワークの3つの特徴ソーシャルネットワークには、以下のような重要な特性が観察されています。1. 稠密化のべき乗則（De

リンクマイニングは、データオブジェクト間のつながり（リンク）を分析・活用するデータマイニング手法であり、複数の重要なタスクで構成されています。本記事では、リンクマイニングにおける6つの主要タスクについて、具体例を交えながらわかりやすく解説します。 リンクマイニングの6つの主要タスク 1. リンクベースのオブジェクト分類 従来の分類手法では、オブジェクトはその属性のみに基づいて分類されます。一方、リンクベースの分類では、オブジェクト自身の属性だけでなく、そのオブジェクトが持つリンクや、リンク先オブジェクトの属性も考慮してカテゴリを予測します。 代表的な例としてWebページの分類が挙げられます

リンクマイニングにおける主な課題リンクマイニングは、グラフ構造を持つデータから有用な知見を抽出する強力な手法ですが、実践にはいくつかの重要な課題が伴います。以下に、代表的な6つの課題を詳しく解説します。1. 論理的依存関係と統計的依存関係グラフのリンク構造には、2種類の依存関係が存在します。1つはオブジェクト間の論理的な関係を表す依存関係、もう1つはオブジェクトの属性間の相関といった統計的な関係を表す確率的依存関係です。これらの依存関係を一貫して扱うことは、複数のテーブルにまたがるデータを対象とするマルチリレーショナルデータマイニングにとっても大きな課題となります。オブジェクト間の多様な論理的

マルチリレーショナルデータマイニング（MRDM）の基本概念マルチリレーショナルデータマイニング（MRDM：Multi-Relational Data Mining）とは、リレーショナルデータベース内の複数のテーブル（リレーション）にまたがるパターンを探索する手法です。各テーブル（リレーション）は、属性の集合によって記述されたエンティティ（実体）またはリレーションシップを表し、リレーション間のリンクは相互の関係性を示しています。従来手法の課題：「命題化」とその限界従来のデータマイニング手法は、データが単一のテーブルに格納されていることを前提としています。この前提のもとで複数のリレーショナルデータ

マルチリレーショナルクラスタリングとはマルチリレーショナルクラスタリング（多関係クラスタリング）とは、複数のリレーション（関係）に含まれる情報を活用し、データオブジェクト同士の類似性に基づいてクラスタの集合へと分割する処理のことです。本記事では、この手法を実現するアルゴリズムの一つである CrossClus（ユーザガイダンスを用いたクロスリレーショナルクラスタリング）を紹介します。CrossClusは、クラスタリングにおいてユーザからのガイダンスをどのように活用するか、また物理的な結合（ジョイン）を避けるためにタプルID伝播をどのように利用するかを探求したアルゴリズムです。主要な課題：膨大な属

オブジェクト識別子とクラス階層による一般化オブジェクト識別子は、以下の手順で一般化することができます。まず、オブジェクト識別子を、そのオブジェクトが属する最下位のサブクラスの識別子へと一般化します。次に、このサブクラスの識別子を、クラス／サブクラス階層を上位へたどることで、より高レベルのクラスまたはサブクラスの識別子へと一般化できます。同様に、クラスやサブクラス自身も、関連するクラス／サブクラス階層を上位へたどることによって、対応するスーパークラス（複数存在する場合もあります）へと一般化可能です。オブジェクト指向データベースにおける継承の仕組みオブジェクト指向データベースはクラス／サブクラス階

空間データベースの特徴空間データベースには、地図、前処理済みのリモートセンシングデータや医療画像の記録、VLSIチップ設計データといった、膨大な空間関連データが格納されています。空間データベースには、一般的なリレーショナルデータベースとは異なる、以下のような特徴があります。位相（トポロジー）情報や距離情報を保持している高度な多次元空間インデックス構造によってデータが整理されている専用の空間データアクセス手法を通じてデータへアクセスする空間推論・幾何計算・空間知識表現の技術が求められるケースが多い空間データマイニングの定義空間データマイニングとは、空間データベースに明示的には格納されていない知識

空間データウェアハウスの構築・利用における主な課題 空間データウェアハウス（Spatial Data Warehouse）の構築と利用には、いくつかの難しい課題が存在します。本記事では、代表的な2つの課題と、それに関連する技術的な概念についてわかりやすく解説します。 課題1：異種ソースからの空間情報の統合 最初の課題は、異種（ヘテロジニアス）なソースやシステムに分散する空間情報を統一することです。空間データは通常、さまざまな業界の企業や政府機関によって、それぞれ異なるデータ形式で保存されています。 これらのデータ形式は、構造固有のもの（ラスタ形式とベクタ形式の空間データ、オブジェクト指向モデ

WaveClusterとはWaveClusterはマルチ解像度クラスタリングアルゴリズムの一つで、まずデータ空間に多次元グリッド構造を適用することでレコードを要約します。その後、ウェーブレット変換を利用して元の特徴空間を変換し、変換後の空間における高密度領域を検出することでクラスタを見つけます。この手法では、各グリッドセルがそのセルにマッピングされた点群のデータを要約します。要約データは通常メインメモリに収まるため、マルチ解像度ウェーブレット変換やその後のクラスタ分析を効率的に実行できます。ウェーブレット変換の仕組みウェーブレット変換は、信号を複数の周波数サブバンドに分解する信号処理手法です。

EMアルゴリズムの概要EMアルゴリズム（Expectation-Maximization algorithm、期待値最大化法）は、パラメータ推定を行うための代表的な反復改良アルゴリズムです。k-means法のパラダイムを拡張したものと考えることができます。k-means法では、クラスタ平均に基づいて各オブジェクトを最も類似度の高いクラスタに割り当てますが、EMアルゴリズムでは所属確率を表す重みに従って各オブジェクトをクラスタに割り当てます。つまり、EMアルゴリズムではクラスタ間に厳密な境界は存在せず、新しい平均値は重み付けされた測定値に基づいて算出されるのが特徴です。EMアルゴリズムの仕組みE

概念クラスタリングとは概念クラスタリング（Conceptual Clustering）は、機械学習におけるクラスタリング手法の一つで、ラベル付けされていないオブジェクトの集合に対して分類構造を構築するアプローチです。従来のクラスタリングが単に似た性質を持つオブジェクトのグループを識別するにとどまるのに対し、概念クラスタリングはさらに一歩進み、各グループの特徴的な定義を自動的に発見します。このとき、各グループは一つの概念（クラス）として定義されます。2段階のプロセス：クラスタリングと特徴付け概念クラスタリングは、まずクラスタリングを実行し、その後に特徴付け（characterization）を行

制約ベースクラスタリング（Constraint-based Clustering）とは、ユーザーが指定した好みや制約条件を満たすクラスタを発見する手法です。制約の性質に応じて、さまざまなアプローチを採用することができます。制約ベースクラスタリングで扱われる制約は、大きく以下の5つのカテゴリに分類されます。1. 個々のオブジェクトに対する制約クラスタリング対象となるオブジェクトそのものに制約を定義できます。例えば、不動産アプリケーションにおいて、100万ドル以上の価値がある高級邸宅のみを空間的にクラスタリングしたいケースが考えられます。この種の制約は、クラスタリング対象のオブジェクト集合を限定す

半教師ありクラスタリングの概要半教師ありクラスタリング（Semi-supervised Clustering）とは、ドメイン知識（事前知識）を活用しながらラベルなしデータを分割する手法です。事前知識は、一般的にインスタンス間のペアワイズ制約として、あるいは少数のラベル付きインスタンスの集合という形で表現されます。教師情報によるクラスタリング品質の向上通常の教師なしクラスタリングでも、わずかな教師情報（弱い監督構造）を加えるだけで、その精度を大幅に改善できます。代表例としては、「2つのオブジェクトが同じクラスタに属する／異なるクラスタに属する」という形でラベル付けされたペアワイズ制約が挙げられま

データセットS内のオブジェクトoが、パラメータpとdで定義される距離ベース（DB）外れ値、すなわちDB(p, d)外れ値であるとは、「S内の少なくとも割合pのオブジェクトが、oから距離dよりも遠い位置に存在する」場合を指します。言い換えれば、統計的検定に頼るのではなく、「近傍となるオブジェクトが十分に存在しないオブジェクト」を外れ値とみなす考え方です。近傍の有無は、対象オブジェクトからの距離に基づいて判定されます。統計的手法との関係とメリット統計的手法と比較すると、距離ベースの外れ値検出は、標準分布を前提とした不一致性検定（discordancy testing）の背後にある考え方を汎用化・統

BIRCH（バーチ）とはBIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies）は、大量の数値データレコードを効率よくクラスタリングするために設計されたアルゴリズムです。階層型クラスタリングと、反復分割法をはじめとする他のクラスタリング手法を統合したアプローチを採用しています。BIRCHの中核となるのが、「クラスタリング特徴量（Clustering Feature：CF）」と「CFツリー」という2つの概念です。これらの構造によって、大規模データベース上でも高速かつ高いスケーラビリティを実現でき、継続的に流入してくるオ

ホフディングツリー（Hoeffding Tree）アルゴリズムは、ストリーミングデータの分類に特化した決定木学習手法です。当初はWebクリックストリームの追跡に活用され、ユーザーがどのWebホストやサイトへアクセスする可能性が高いかを予測するモデルの構築に用いられていました。従来のバッチ学習とほぼ同等の決定木を生成しながら、準線形時間（サブリニア時間）で動作できる点が最大の特徴です。ホフディング境界による分割属性の選択このアルゴリズムの中核にあるのは、「少量のサンプルでも最適な分割属性を選択できることが多い」というアイデアです。この考え方は、ホフディング境界（Hoeffding bound、加

CluStreamは、ユーザーが指定したオンラインのクラスタリングクエリに基づいて、進化し続けるデータストリーム（evolving data stream）のクラスタリングを行うアルゴリズムです。最大の特徴は、クラスタリング処理を「オンライン」と「オフライン」の2つのコンポーネントに分割している点にあります。 オンラインとオフラインの2段階構成 オンラインコンポーネントは、「マイクロクラスタ（micro-cluster）」と呼ばれる要約統計量を計算・保存しながら、データストリームを増分的（インクリメンタル）に処理し、マイクロクラスタの維持・更新をリアルタイムに行います。 一方、オフラインコン