2015(平 成27)年 度 修 士 論 文
階層 構造 を利 用 した対制約一括 生成型
イ ン タ ラ ク テ ィ ブ ク ラ ス タ リン グ シ ス テ ム
に関す る研 究
提 出 日:2016(平 成28)年2月24日
首都 大 学東京 大学 院 システ ムデザ イ ン研 究科 システ ムデ ザイ ン専攻 情 報通信 システ ム学域
高間研 究室
学 習 番 号:14890507氏 名:北 村 侑 也 指 導 教 員:高 間 康 史 教 授
要 旨
本 論 文 で は,イ ン タ ラ クテ ィブ ク ラ ス タ リン グの た め の 対 制 約 生成 手 法 お よび 可 視 化 技 術 を用 い た イ ン タ フ ェー ス を 提 案 す る.近 年,ビ ッ グデ ー タ と呼 ばれ る単 語 が 注 目 され る ほ ど社 会 に流 通 す るデ ー タ量 が 拡 大 し,そ れ に伴 い個 人 が 獲 得 で き る情 報 量 も増 大 して き た.そ の た め 現 代 で は デ ー タ を獲 得 す る だ け で は な く,大 量 のデ ー タの 中 か ら必 要 な 情 報 を 見 っ け 出す こ とが 重 要 とな る.そ こで,計 算機 を利 用 して デ ー タ を分 析 す るデ ー タマ イ ニ ン グ な どの 技 術 が研 究 され てお り,本 論 文 で は 代 表 的 デ ー タ マ イ ニ ン グ手 法 の 一 つ で あ る ク ラ ス タ リン グ に 着 目 した.ク ラ ス タ リン グは デ ー タ を ク ラ ス タ と呼 ばれ る集 合 に振 り 分 け る こ とに よ り,大 規模 デ ー タ集合 に 内在 す る構 造 や 規 則 性 な どを発 見 す る技 術 で あ る.
しか し,ク ラス タ リン グは 教 師 デ ー タを 用 い な い 教 師 な し学 習 で あ り,ま た デ ー タ の 分 類 の 仕 方 は 必 ず しも 一 意 に は決 ま らな い た め,分 析 者 の知 識 や 目的 に合 致 した ク ラ ス タ構 造 が 得 られ る とは 限 らな い.こ れ を解 決 す るた め,人 間 と計 算 機 が 協調 して ク ラ ス タ リン グ を行 う制 約 付 き ク ラス タ リン グが 注 目 され て い る.
制 約 付 き ク ラ ス タ リン グ は ク ラス タ形 成 に関 す るユ ー ザ の 意 図 を制 約 とい う形 で 計 算 機 に 与 え,こ れ を満 た す よ うな ク ラス タ構 造 を求 め るデ ー タマ イ ニ ン グ手 法 で あ り,半 教 師 あ り学 習 に分 類 され る.制 約 表 現 の代 表 的 な もの に,2つ の オ ブ ジ ェ ク ト間 に制 約 を付 与す る 対制 約 が あ る.対 制 約 で は,ユ ー ザ が 同 じク ラ ス タ に振 り分 け た い オ ブ ジ ェ ク ト対 に は must・1inkと 呼 ばれ る制 約 を,別 ク ラス タに振 り分 け た い オ ブ ジ ェ ク ト対 に はcannot‑link
と1呼ば れ る制 約 を そ れ ぞ れ 付 与 す る.計 算 機 は 与 え られ た制 約 を満 た す よ うに 全 デ ー タ を クラ ス タ リン グす る.
大 量 の デ ー タ に 対 して制 約 付 き ク ラ ス タ リン グ を用 い る 際 に は,制 約 の指 定 に 要 す るユ ー ザ の負 担 を 軽 減 す る こ とが課 題 とな る .こ れ に対 して,デ ー タ(オ ブ ジェク ト)単 位 では な く ク ラ ス タ単 位 で 操 作 を 行 い,そ の 結 果 を用 い て対 制 約 を 一 括 生 成 す る手 法 が提 案 され て い る.こ の手 法 で は ク ラ ス タ単 位 での 操 作 結 果 に 基 づ き,同 一 ク ラ ス タ 内 に 含 まれ た オ ブ ジ ェ ク ト対 に 一 括 で 対 制 約 を 生 成 す る こ とでユ ー ザ の負 担 を減 ら しつ つ 大 局 的 な制 約 付 与 が 可 能 で あ る こ とが 報 告 され て い る.し か し,従 来 手 法 で は,過 去 の 操 作 履 歴 を用 い る こ とで ユ ー ザ の操 作 意 図 を推 定 す る た め,複 数 回 の ク ラス タ リン グが 必 要 とな り,作 業 が 長 期 化 す る可 能性 が あ る.
そ こで 本 論 文 で は ク ラ ス タを 木(階 層)構 造 上 で の ノー ドとみ な し,ユ ー ザ に よ る ク ラ ス タ の 統 合 ・分 解 操 作 を木 構 造 上 での ノー ドの階 層 変 化 と捉 え る こ とで,ユ ー ザ の 操 作 意 図 を推 定 し対 制 約 を 一 括 生成 す る手 法 を提 案 す る.エ ー ジ ェ ン トシ ミュ レー シ ョン に よ り, 操 作 履 歴 を用 い た 制 約 一括 生 成 手 法 との 比較 実験 を 行 い 提 案 手 法 の 有 効 性 を 示 す.提 案 手 法 で は ユ ー ザ に よ る ク ラ ス タ操 作 を木 構 造 上 で の 階 層 変 化 と と らえ るた め,木 構 造 に適 し た情 報 可 視化 手 法 で あ るTree・mapを 採 用 した イ ン タ フ ェー ス も提 案 し,ユ ー ザ 実 験 に よ り
有 効 性 を検 証 す る.
本 論 文 は5章 か ら構 成 され る.1章 で は本 論 文 の研 究背 景 お よび 目的 を述 べ る.2章 で は 関 連 研 究 と して 制 約 付 き ク ラ ス タ リン グに 関す る既 存 手 法 お よび ク ラ ス タ単位 で の操 作 に よ る 制 約 一 括 生 成 手 法 に つ い て,ま た ク ラス タ リン グ結 果 の 可 視 化 手 法 に 関 す る既 存 研 究 お よび プ ロ トタ イ プ シ ス テ ム の 開 発 に用 い た 統合 環 境TETDM(TotalEnvironmentfor
TextDataMining)に つ い て 述 べ る.3章 で は提 案 手 法 に お け る統 合 ・分 解 操 作 の 木 構 造 上 で の と ら え方,制 約 の 生 成 ア ル ゴ リズ ム,制 約 付 き クラ ス タ リン グ の流 れ につ い て 述 べ る.
ま た,TETDM上 に実 装 した シス テ ム の構 成 や ク ラ ス タ リン グ結 果 の 表 示 方 法 に つ い て も 述 べ る.TETDMは 統 一 した ス ク リー ン構 成 や 操 作 を提 供 す る た め,異 な るテ キ ス トマ イ ニ ン グ ツー ル の 比 較 実 験 に適 して い る こ とが 指 摘 され て い る が,マ イ ニ ン グ処 理 の 組 み 合 わ せ を 動 的 に 変 更 す る こ とが 不 可 能 で あ っ た.そ こ で本 論 文 で は 処 理 の 組 み 合 わ せ を 動 的 に変 更 す る コ ン トロール パ ネ ル の 概 念 を取 り入れ た,TETDMの 新 しい デ ザ イ ンパ タ ー ン も提 案 して い る.4章 で はエ ー ジ ェ ン トシ ミュ レー シ ョン に よ る制 約 一 括 生成 手 法 の 評 価 実 験,お よび 実装 した シ ス テ ム を用 い た ユ ー ザ実 験 の 結 果 に つ い て 述 べ る.実 験 で はNTCIR プ ロジ ェ ク トで 提 供 され て い る毎 日新 聞 の 記 事 デー タ を用 い,5つ の ジ ャ ンル に 対応 した ク ラ ス タを 得 る こ と を 目標 と した 場 合 の ク ラ ス タ リン グ成 功 回 数 な どに 基 づ き評 価 を 行 っ た.
結 果 よ り提 案 す る対 制 約 生 成 手 法 お よび イ ン タフ ェ ー ス の有 効 性 を考 察 す る.5章 で は 実 験 結 果 か ら得 られ た 提 案 手 法 の 有 効 性 を ま とめ る と と もに,今 後 の 展 望 につ い て述 べ る.
Abstract
Thisthesisproposesamethodfbrgeneratingpair‑wiseconstraintsandvisualization interface丘)rinteractiveclustering.Proposedmethodautomaticallygeneratesasetof pair‑wiseconstraintsbyconsideringrelationshipbetweendata.User'sgrouping operationismodeledastheoperationonhierarchicalstructureofclusteringresults, whichmakesitpossibletofocusonimportantdatatowhichconstraintsshouldbeadded.
Thisthesisshowstheef￡ectivenessofproposedmethodbycomparingexistinggrouping history・basedapproachusingagentsimulation.Thisthesisalsoproposes
Treemap‑basedinterface,whichisexpectedtobesuitablefbrvisualizingtreestructure.
Itse脆ctivenessisevaluatedbyuserexperiment.(98words)
目次
1.は じ め に 2.関 連 研 究
2.1デ ー タ マ イ ニ ン グ
2.1.1デ ー タ マ イ ニ ン グ と は 2.1.2ク ラ ス タ リ ン グ
2.2制 約 付 き ク ラ ス タ リン グ 2.3ク ラ ス タ リ ン グ結 果 の 可 視 化
‑占QUQUQU4▲7.
2.4イ ン タ ラ ク テ ィ ブ ク ラ ス タ リ ン グ
2.5TETDM(TotalEnvironmentforTextDataMining)
3,提 案 手 法
3.1階 層 ベ ー ス の 制 約 付 与
3.2デ ザ イ ン パ タ ー ン3.3提 案 シ ス テ ム 4.比 較 実 験
4.1実 験 概 要
4.2シ ミ ュ レ ー シ ョ ン 実 験 4.3ユ ー ザ 実 験
5.お わ り に
謝辞 参考文献 発表文献
0 3 8 3 3 7 1 9 9 2 7 3 4 5 0 1 1 1 2 2 2 3 3 3 4 4 5 5 5 6
1.は じ め に
本 論 文 で は,イ ン タ ラ ク テ ィ ブ ク ラ ス タ リ ン グ の た め の 対 制 約 生 成 手 法 お よ び 可 視 化 技 術 を 用 い た イ ン タ フ ェ ー ス を 提 案 す る.近 年,個 人 が 獲 得 で き る デ ー タ 量 が 増 大 し て お り,
個 人 が す べ て を 把 握 す る こ と は 難 し く な っ て き て い る.そ の た め,大 量 の デ ー タ の 中 か ら 個 人 に と っ て 有 益 な 情 報 を 抽 出 す る こ と が 重 要 と な り,計 算 機 を 用 い て デ ー タ の 分 析 を 行
うデ ー タ マ イ ニ ン グ な ど の 技 術 が 行 わ れ て い る.デ ー タ マ イ ニ ン グ 手 法 の 一 つ に ク ラ ス タ リ ン グ が あ る.ク ラ ス タ リ ン グ は デ ー タ を ク ラ ス タ と 呼 ば れ る 集 合 に 振 り 分 け る こ と に よ り,大 規 模 デ ー タ 集 合 の 特 徴 や 構 造 な ど を 発 見 す る 技 術 で あ る.デ ー タ マ イ ニ ン グ で は 正 解 と な る 入 出 力 の 組 合 せ を 教 師 デ ー タ と して シ ス テ ム に 与 え る 教 師 あ り学 習 と,教 師 デ ー タ を 与 え な い 教 師 な し学 習 が あ り,ク ラ ス タ リ ン グ は 教 師 な し 学 習 に 分 類 さ れ る,教 師 あ り学 習 は ユ ー ザ の 目 的 に あ っ た 結 果 を 出 力 で き る 一 方,結 果 が 一 意 に 決 定 す る た め,デ ー タ 内 の 隠 さ れ た 可 能 性 を 見 つ け づ ら い.こ れ に 対 し,教 師 な し学 習 で は 教 師 デ ー タ と は 違 うデ ー タ 間 の 関 係 性 を 発 見 で き る こ と が 利 点 と して あ げ られ る.一 方 で デ ー タ の 分 類 結 果 が 一 意 に 決 ま ら な い こ と か ら,分 析 者 の 知 識 や 目 的 と 合 致 し た ク ラ ス タ 構 造 が 得 られ る と は 限 ら な い と い っ た 欠 点 も 持 つ.こ れ を 解 決 す る た め,人 間 と 計 算 機 が 協 調 し て ク ラ ス タ
リ ン グ を 行 う 制 約 付 き ク ラ ス タ リ ン グ[1]が 注 目 され て い る.
制 約 付 き ク ラ ス タ リ ン グ は ク ラ ス タ 形 成 に 関 す る ユ ー ザ の 意 図 を 制 約 と い う形 で 計 算 機 に 与 え 、 そ れ を 満 た す よ う な ク ラ ス タ 構 造 を 求 め る デ ー タ マ イ ニ ン グ 手 法 で あ り,半 教 師 あ り学 習 に 分 類 され る.制 約 の 表 現 方 法 に は 複 数 の デ ー タ を グ ル ー プ と して 制 約 を 付 与 す る 制 約 ネ ッ ト ワ ー ク,二 つ の デ ー タ 間 に 制 約 を 与 え る 対 制 約,各 デ ー タ に 対 し て ラ ベ ル を 用 い る 制 約 な ど が あ る.本 論 文 で 対 象 とす る 対 制 約 は,同 一 ク ラ ス タ に 振 り 分 け た い オ ブ ジ ェ ク ト対 に はmust・1inkと 呼 ば れ る 制 約 を,別 ク ラ ス タ に 振 り分 け た い オ ブ ジ ェ ク ト対 に はcannot・linkと 呼 ば れ る 制 約 を そ れ ぞ れ 付 与 す る.制 約 付 き ク ラ ス タ リ ン グ の 応 用 例 と して,榊 ら は 論 文 デ ー タ に 対 し て 引 用 と類 似 度 か ら な る も の と カ テ ゴ リ分 類 か ら な る も の の2種 類 の 制 約 ネ ッ トワー ク を 作 成 す る 手 法[6】を 提 案 して い る.青 島 ら はTwitterの よ う な マ イ ク ロ ブ ロ グ に 対 して 対 制 約 を 適 応 す る 手 法 【7】 を 提 案 して い る.ま た 岡 田 ら は 画 像 デ ー タ に 対 し て 少 数 の ラ ベ ル を 付 与 し ,学 習 を 行 う こ と で 高 精 度 の 制 約 付 き ク ラ ス タ リ ン グ を 行 う手 法 を 提 案 し て い る[8].
大 規 模 デ ー タ に 対 し て 対 制 約 を 付 与 す る 際 に は,オ ブ ジ ェ ク ト対 の 指 定 に 要 す る ユ ー ザ 負 担 の 軽 減 が 課 題 と な る.こ れ に 対 し て,オ ブ ジ ェ ク ト単 位 で は な く デ ー タ の 集 合 で あ る ク ラ ス タ 単 位 で 操 作 を 行 い,そ の 結 果 か ら ユ ー ザ の 意 図 を 推 定 し,一 括 で 制 約 生 成 を 行 う 手 法 が 提 案 され て い る[2】.こ の 手 法 で は 一 つ の ク ラ ス タ を 二 つ に 分 け る 分 割 操 作,二 っ の
ク ラ ス タ を 一 つ に ま と め る 統 合 操 作 の2つ か らな る グ ル ー ピ ン グ 操 作 を 用 い て ク ラ ス タ リ
ン グ 結 果 を ユ ー ザ が 修 正 す る.修 正 作 業 の 終 了 後,同 一 ク ラ ス タ に 含 ま れ る オ ブ ジ ェ ク ト
対 の い く つ か に 対 し て 一 括 でmust・1inkを 生 成 し,再 ク ラ ス タ リ ン グ を 実 行 す る.加 え て
複 数 回 の ク ラ ス タ リン グ を繰 り返 し,蓄 積 され た グル ー ピン グ履 歴 か らよ り詳 細 にユ ー ザ の 意 図 を推 定 す る.こ の 手 法 に よ りユ ー ザ 負 担 を軽 減 しつ つ 大 局 的 な 制 約 付 与 が 行 え る こ とが 報 告 され て い る[3].し か し,詳 細 なユ ー ザ の 意 図 を推 定 す る まで に複 数 回 の ク ラ ス タ リン グ を 行 うこ とか ら作 業 に 長 時 間 を要 す る可 能 性 が あ る.ま た,従 来 手 法 で は ユ ー ザ の 操 作 終 了 後 の ク ラ ス タ状 態 の み を評 価 に 用 い るた め,各 ク ラ ス タ 内 の デ ー タ対 に 対 して 差 異 は 考 慮 せ ず,同 一 の ス コ ア を 与 え て い る.そ の た め ク ラ ス タ内 のデ ー タ間 の 関係 性 を考 慮 で き て お らず,有 効 な 対 制 約 が付 与 で きな い 可 能性 が あ った.こ の こ とか ら,ク ラ ス タ リン グ結 果 に ユ ー ザ の 意 図 を反 映 させ る上 で有 効 な制 約 を 生 成 す る た め に は操 作 履 歴 だ け で は 不 十 分 で あ り,デ ー タ間 の 関 係性 に つ い て も考 慮 す る必 要 が あ る と考 え る.
本 論 文 で は デ ー タ 間 の 関 係 性 を考 慮 す るた め に,ク ラ ス タ リン グ に よ り得 られ る 階 層 構 造 に着 目す る.階 層 構 造 の 中 で,深 い 階 層 に お い て 同 一 ク ラス タ に分 類 され て い る デ ー タ ほ どデ ー タ問 の 関 係 性 は 強 い と判 断 し,対 制約 生 成 時 に 考 慮 す る.階 層 構 造 を用 い る こ と で,ク ラ ス タ リン グ結果 の 表 示 か ら再度 制 約 付 き ク ラス タ リン グを 行 うまで の1ス テ ップ 中 に操 作 履 歴 に も とつ く従 来 手法 よ りも多 くの情 報 を獲 得 で き るた め,ク ラ ス タ リン グ回 数 の 削 減 も期 待 で き る.
提 案 手 法 の有 効 性 を確 か め るた め に統 合 環 境TETDM(TotalEnvironmentforTextData
Mining)[4】 上 に プ ロ トタイ プ シス テ ム を構 築 す る.TETDMは 複 数 枚 の パ ネ ル を画 面 上 に 表 示 し,各 パ ネ ル に処 理 ・可 視 化 の モ ジ ュ ール を 設 定す る こ とで マ イ ニ ン グ結 果 を パ ネ ル に 表 示 す る,統 一 した ス ク リー ン構 成 や 操 作 を提 供 で き るた め,異 な る マ イ ニ ン グ ツー ル の 比 較 実 験 に適 して い る,し か しマ イ ニ ン グ処 理 を動 的 に 変 更す る こ とが 不 可 能 で あ っ た.
そ こで 本 論 文 で は処 理 を 動 的 に 変 更 す る コン トロー ル パ ネ ル の概 念 を 取 り入 れ た,TETDM の 新 しい デ ザ イ ンパ ター ン につ い て も提 案 す る.作 成 した プ ロ トタイ プ シ ス テ ム を用 い て エ ー ジ ェ ン トシ ミュ レー シ ョン に よ り提 案 手 法 の有 効 性 を確 認 す る.ま た提 案 手 法 で は ク ラス タ に 対 す る操 作 を 木構 造 上 で の 階層 変化 と捉 え る た め 、 木構 造 に適 した 情 報 可 視 化 手 法 で あ るTree‑map[5】 を採 用 した イ ン タ フ ェー ス も提 案 し,ユ ー ザ に よ る比 較 実 験 か らそ の 有 効 性 を検 証 す る.
2.関 連 研 究
2.1デ ー タ マ イ ニ ン グ
2.1.1デ ー タ マ イ ニ ン グ の 種 類 と 応 用
近 年,情 報 通 信 技 術 の 進 展 と と も に 社 会 で 流 通 す る デ ー タ 量 は 増 え,個 人 が 容 易 に 大 量 の 情 報 を 取 得 で き る よ う に な っ た.し か し,取 得 した す べ て の 情 報 を 確 認 す る こ と は 難 し
く,計 算 機 に 用 い て 大 量 の 情 報 の 中 か ら 必 要 な 情 報 を 抽 出 す る 必 要 性 が 出 て き た.デ ー タ マ イ ニ ン グ と は,大 量 の 情 報 の 中 か らユ ー ザ に 有 益 な 情 報 を 取 捨 選 択 し,提 供 す る こ と を 目的 と し た 技 術 ・シ ス テ ム で あ る.専 門 家 の 知 識 を 抽 出,利 用 す る こ と を 目 的 と し た エ キ ス パ ー トシ ス テ ム と は 違 い,デ ー タ マ イ ニ ン グ で は デ ー タ 群 に 内 在 す る,明 ら か と な っ て い な い 関 係 性 や 構 造 を 発 見 し,利 用 す る こ と を 目 的 と して い る[9】.デ ー タ マ イ ニ ン グ の 適 用 範 囲 は 広 く,テ キ ス トデ ー タ に 関 して は ウ ェ ブ 上 の 論 文 デ ー タ か らTwitterな どの マ イ ク ロ ブ ロ グ[6】[71,数 値 デ ー タ に 関 し て は 商 店 の 売 り上 げ や 気 象 画 像[19】[20】 な ど様 々 な デ ー タ に 適 用 され て い る.
デ ー タ マ イ ニ ン グ に は 多 く の 手 法 が 提 案 され て い る が,そ れ ら は 予 測 モ デ ル の 構 築,特 徴 パ タ ー ン の 発 見,ク ラ ス タ リ ン グ に 大 別 で き る[10].予 測 モ デ ル の 構 築 は 過 去 の デ ー タ を
基 に して 未 知 の デ ー タ を 識 別 す る 手 法 で あ り,さ ら に 回 帰 分 析 と カ テ ゴ ラ イ ゼ ー シ ョ ン に 分 け る こ と が で き る.回 帰 分 析 は 対 象 デ ー タ が 将 来 ど の よ う に 推 移 して い く か を 予 測 す る 手 法 で あ り,商 品 の 売 上 予 測 や 気 象 画 像 な ど に 用 い られ て い る[191[20】.カ テ ゴ ラ イ ゼ ー シ ョ ン は カ テ ゴ リが 既 知 の 訓 練 デ ー タ を 基 に,新 規 デ ー タ が 属 す る カ テ ゴ リ を 予 測 す る 手 法 で あ り,薬 品 の 効 能 予 測 や 図 書 の 自 動 分 類 な ど に 用 い られ て い る[11].予 測 モ デ ル の 構 築 は, 既 知 の デ ー タ か ら 予 測 モ デ ル を 決 定 す る た め 教 師 あ り 学 習 と 呼 ば れ,既 知 デ ー タ の こ と を 教 師 デ ー タ と 呼 ぶ.こ の 教 師 デ ー タ に 基 づ き 分 類 規 則 な ど を 学 習 す る.教 師 あ り学 習 は 分 類 す べ き カ テ ゴ リが あ ら か じ め 確 定 し て い る 事 象 に 用 い ら れ や す く,図 書 を 書 名 に 基 づ き 十 進 分 類 法 に 分 類 す る 作 業 な ど に 適 用 され て い る[12】.
特 徴 パ タ ー ン の 発 見 は,収 集 し た デ ー タ か ら 特 徴 的 な 事 象 や 関 連 性 を 発 見 して ユ ー ザ に
提 供 す る こ と を 目的 と した 手 法 で あ り,代 表 的 な 手 法 に 相 関 ル ー ル が あ る[13】.相 関 ル ー ル
は 大 量 の デ ー タ の 中 で 共 起 す る デ ー タ に 注 目 す る 手 法 で あ り,商 品 の 購 買 パ タ ー ン に つ い
て,同 じ場 所 で 買 わ れ や す い 商 品 の 発 見 な ど に 用 い られ る[20].ま た,時 系 列 に 着 目 した 手
法 も あ り,ク レ ジ ッ トカ ー ドの 不 正 調 査 な ど に 用 い ら れ て い る[10】.ク ラ ス タ リ ン グ に つ い
て は 次 節 に て 詳 説 す る.
2.1.2ク ラ ス タ リ ン グ
ク ラ ス タ リン グ とは,類 似 した 特 徴 を持 つ デ ー タ同 士 を ク ラ ス タ と呼 ば れ る集 合 に ま と め るデ ー タ マ イ ニ ン グ手 法 の 一 つ で あ り,顧 客 や 文 書 の 分 類 な どに 用 い られ て い る[101.前 項 で 述 べ た 教 師 あ り学 習 に 対 し,ク ラス タ リン グの よ うにデ ー タ の 特 徴 量 の み か ら分 類 結 果 を 出 力 す る手 法 を 教 師 な し学 習 と呼 ぶ.教 師 な し学 習 は 教 師 デ ー タを 用 い な い た め,正 解 が 確 定 して い る場 合 は教 師 あ り学 習 に比 べ て 精 度 が 下 が る場 合 もあ るが,正 解 が 自明 で な い場 合 で は類 似 度 も し くは 距 離 か ら結 果 を出 力 で き るた め,ユ ー ザ に 対 して新 しい 観 点
を提 供 で き る可能 性 を持 つ.
ク ラ ス タ リ ン グ に も様 々 な 種 類 が あ り,ク リスプ で あ るか,フ ァジ ィで あ るか,階 層 的 で あ るか 非 階 層 的 で あ る か とい っ た観 点 で 大別 で き る 【14].クリス プ ク ラ ス タ リン グで は デ ー タ が 所 属 す る ク ラ ス タ が 一 つ で あ るの に対 し,フ ァ ジ ィ ク ラ ス タ リン グ で は デ ー タ が 複 数 の ク ラス タに 所 属 す る の を許 可す る.前 者 は デー タ とク ラ ス タ の 関係 が1対1で あ る の で ユ ー ザ に とっ て 理 解 しや す い構 造 とな る.対 して後 者 は1つ の デ ー タ が複 数 の ク ラ ス タ に ま た が っ て 存 在 して い るた め,表 現 の 自由度 が 高 くユ ー ザ の 細 か な 意 図 も表 現 す る こ とが で き る[14].
階 層 的 ク ラ ス タ リン グ とは,す べ て のデ ー タ が含 まれ て い る ク ラ ス タ をル ー ト,す べ て の デ ー タ が そ れ ぞ れ 要 素 数1の ク ラ ス タで あ る状 態 を リー フ とす る階 層 構 造 を 求 め る手 法 で あ る.対 して 非 階 層 的 ク ラ ス タ リン グ は デー タ を幾 つ か の類 似 グル ー プ に 分 割 す る の み で あ り,ク ラ ス タ問 に上 下 関 係 な どは存 在 しな い.階 層 的 ク ラス タ リン グに は 主 に 分割 型 と凝 集 型 の2種 類 が あ る.分 割 型 で は非 階 層 的 クラ ス タ リン グ手 法 に よ りデ ー タ を幾 つ か の ク ラ ス タ に 分割 した後,ク ラ ス タ 内 に て さ らにデ ー タ を複 数 の ク ラ ス タに 分 割 す る こ と を繰 り返 して 階 層 的 な構 造 を得 る.こ れ に 対 して,凝 集 型 で は 各 デ ー タ が そ れ ぞ れ 独 立 し た ク ラ ス タで あ る と した 状 態 か ら,ク ラ ス タ間 の類 似 度 が 高 い も し くは 距 離 の 短 い ク ラ ス タ 同 士 を併 合 す る こ とを繰 り返 す.
凝 集 型 ク ラス タ リン グで は,類 似 度 も しくは 距離 の 計算 手 法 と して様 々 な 手 法 が 提 案 さ れ て い る.代 表 的 な もの に 類 似 度,距 離 の 両方 を用 い る こ とが で き る最 短 距 離 法,最 長 距 離 法,群 間 平 均 法 な どが あ る[14】.こ れ に対 して,距 離 の み を用 い る手 法 と して 重 心 法, Ward法 が あ る.以 下 で は 距 離 を用 い た場 合 の計 算 手 法 を述 べ る.最 短 距 離 法,最 長 距 離 法, 群 間 平 均 法 で は まず 式(2.1)を 用 い てデ ー タ間 の 距離 を求 め る.
れ
d(x・ ・Xj)一 Σ(x・k‑Xjk)2 k=1
(2.1)
こ こ でXi=(κil,..,,κin)は 各 デ ー タ,nは デ ー タ の 次 元 を そ れ ぞ れ 表 す.こ の 中 で,最 短 距
離 法 で は2つ の ク ラ ス タ か ら一 つ ず つ 選 び 出 した デ ー タ 問 の 距 離 を 調 べ,最 小 と な る デ ー
タ 対 の 距 離 を ク ラ ス タ 間 の 距 離 と し て 採 用 す る.対 して,最 長 距 離 法 で は 最 も 距 離 が 長 い デ ー タ 対 の 距 離 を 採 用 す る.群 間 平 均 法 で は2つ の ク ラ ス タ に つ い て,別 の ク ラ ス タ に 属 す る デ ー タ 対 間 の 距 離 を 全 て 求 め,そ の 平 均 を ク ラ ス タ 間 の 距 離 と して 採 用 す る.重 心 法 で は 各 ク ラ ス タ の 重 心 同 士 の 距 離 を,式(2.2)を 用 い て 計 算 す る.こ こ でCは 各 ク ラ ス タ, M(Ci,k)はCの 重 心 ベ ク トル のk番 目 の 値 を 表 す.こ の よ う に して 決 定 し た ク ラ ス タ 間 距 離 の う ち,最 も 距 離 の 短 い ク ラ ス タ 対 を 併 合 す る.
れ
d(C・ の=Σ(M(C・ た)‑M(ら ・ た))2
k=1
(2.2)
Ward法 で は 式(2.3)で 定 義 され る 式 を 用 い て,ク ラ ス タ 同 士 を 併 合 した 場 合 の ク ラ ス タ 内 の デ ー タ の ば ら つ き の 増 加 を 求 め る.こ こ でM(の は ク ラ ス タCの 重 心 を 表 す.
E(の 一 Σ11x・‑M(C)ll2
Xi∈c
(2.3)
2っ の ク ラ ス タCiとCjを 併 合 した 場 合 の ば らつ き の 増 加 は 次 の 式(2.4)で 定 義 す る.
△E(C、,Cj)=E(C、UCj)‑E(Ci)‑E(Cj) (2.4)
Ward法 で は こ の △E(Ci,(の が 最 小 と な る ク ラ ス タ 同 士 を 統 合 す る.
非 階 層 的 ク ラ ス タ リ ン グ に は 代 表 的 な 手 法 と し てk・means[15】,k‑medoids[16】, CLARA[181な ど が あ る.k‑meansで は 次 の 手 順 に 従 っ て デ ー タ を 分 類 す る.ク ラ ス タ 数k は ユ ー ザ が 指 定 す る.
1.要 素 数0の ク ラ ス タ をk個 用 意 し,各 ク ラ ス タ に 初 期 中 心 を 与 え る.こ こ で,ス テ ッ プ 数 をt=1と す る.
2.各 デ ー タ と ク ラ ス タ 中 心 間 の 距 離 を 計 算 し,距 離 が 最 短 と な る ク ラ ス タ に デ ー タ を 分 類 す る.
3.全 デ ー タ の 分 類 終 了 後,分 類 結 果 が 前 ス テ ッ プ(t・‑1)と 同 じ で あ れ ば ク ラ ス タ リ ン グ を 終 了 し,結 果 を 出 力 す る.
4.同 じ で な け れ ば,ク ラ ス タ 中 心 を ク ラ ス タ に 所 属 す る 全 デ ー タ の 平 均(重 心)と し て 再 計 算 し,t=t+1と して 手 順2に 戻 る.
手 順1に お け る 初期 中 心 の 決 め方 には 複 数 あ り,中 心 の 各 次 元 の 値 を ラ ン ダ ム に 決 定す る手 法,デ ー タ の 中 か ら ラ ン ダ ム に 左 個 の デ ー タを選 択 し,そ の デ ー タ を 初期 中 心 とす る
手 法,各 デ ー タ が 所 属 す る ク ラ ス タ を ラ ン ダ ム で 決 め た 後,各 ク ラ ス タ の 重 心 を 計 算 して 中 心 と して 用 い る 手 法 な ど が あ る.k‑meansは 局 所 最 適 解 に 陥 る こ と が あ る の で,こ の 初 期 中 心 に よ り結 果 が 異 な る 場 合 が あ る.
k‑medoidsは,基 本 的 な 手 順 に つ い て はk‑meansと 同 じだ が 手 順4が 異 な る.k・means で は ク ラ ス タ の 中 心 を 全 デ ー タ の 平 均 か ら求 め て い た の に 対 して,k・medoidsで は あ る デ ー
タ と ク ラ ス タ 内 の 他 の デ ー タ と の 差 の 総 和 を 用 い る.総 和 が 最 小 と な る デ ー タ を ク ラ ス タ の 代 表 値 と し,手 順4の 新 しい ク ラ ス タ 中 心 と して 用 い る.こ れ に よ り外 れ 値 の 影 響 を 緩 和 す る こ とが で き る.
CIARAは 大 規 模 デ ー タ セ ッ ト向 け のk・medoidsで あ り,最 初 に サ ン プ ル と し て40+2k 個 の デ ー タ を 取 り 出 す.抽 出 し た デ ー タ か ら 左 個 の デ ー タ を 選 び,初 期 中 心 と し て k‑medoidsを 行 う.k‑medoidsに よ る ク ラ ス タ 中 心 の 計 算 後,サ ン プ ル 以 外 の デ ー タ も含 め てk・medoidsを 実 行 し,最 終 的 な 結 果 を 得 る.サ ン プ ル の 抽 出 を 複 数 回 行 い,最 良 の 結 果 を 最 終 結 果 と し て 出 力 す る.こ の 他 に もk・meansの ク ラ ス タ 数 を 自 動 的 に 決 定 す る 手 法[17]
や,デ ー タ 問 の 密 度 に 着 目 した 手 法[16]な ど が あ る.
2.2制 約 付 き ク ラ ス タ リ ン グ
ク ラ ス タ リ ン グ は デ ー タ 集 合 を そ の 特 徴 量 に 応 じて ク ラ ス タ に 分 類 す る が,デ ー タ に は 複 数 の 特 徴 が あ り,着 目す る 特 徴 に よ りデ ー タ の 分 類 結 果 は 変 化 す る.ク ラ ス タ リ ン グ は そ の 結 果 の う ち の 一 つ を 結 果 と して 出 力 す る た め,ユ ー ザ が 期 待 す る 結 果 と ク ラ ス タ リ ン グ 結 果 が 一 致 し な い 場 合 も 存 在 す る.例 え ば,文 章 の ク ラ ス タ リ ン グ を 行 う際 に 単 語 の 登 場 頻 度 を 特 徴 量 と す る 場 合,登 場 頻 度 と 単 語 の 逆 文 書 頻 度 の 積 で あ るtf'i(lfを 特 徴 量 とす る 場 合,tf‑idfに 加 え て 文 書 長 を 考 慮 す るBM25を 特 徴 量 とす る 場 合 が あ り,そ れ ぞ れ で 結 果 は 異 な る.
そ の た め,本 来 は 教 師 な し学 習 で あ る ク ラ ス タ リ ン グ に お い て ユ ー ザ の 意 図 を 反 映 さ せ る 手 法 と し て,半 教 師 あ り学 習 で あ る 制 約 付 き ク ラ ス タ リ ン グ が 注 目 さ れ て い る[1].半 教 師 あ り学 習 と は,教 師 あ り学 習 の よ うに す べ て の デ ー タ に 対 し て 教 師 デ ー タ を 付 与 す る の で は な く,興 味 を 持 っ て い る 部 分 に お け る デ ー タ の 分 割 に 対 し,何 ら か の 制 約 を 付 与 す る 手 法 で あ る.半 教 師 あ り学 習 で は,ユ ー ザ が 興 味 を 持 つ デ ー タ に つ い て ユ ー ザ の 意 図 に 沿
っ た 分 類 が 可 能 で あ り,ユ ー ザ が 期 待 す る 結 果 が 出 力 さ れ や す く な る.
制 約 の 形 式 に は 様 々 な も の が 提 案 され て お り,大 別 して デ ー タ に 対 し て 制 約 を 付 与 す る 手 法 と ク ラ ス タ に 対 し て 制 約 を 付 与 す る 手 法 が あ る.デ ー タ に 対 して 制 約 を 付 与 す る 手 法 と し て は1つ の デ ー タ に 対 して ラ ベ ル の 付 与 を 行 い,ラ ベ ル を 制 約 と し て 扱 う手 法[8】,2 つ の デ ー タ に 対 し て 制 約 の 付 与 を 行 う対 制 約 【21],2つ 以 上 の デ ー タ を1つ の ネ ッ トワ ー ク
と し て ネ ッ トワ ー ク 単 位 で 制 約 の 付 与 を 行 う制 約 ネ ッ トワ ー ク[61な ど が あ る.
ラ ベ ル を 制 約 とす る 場 合,同 一 ク ラ ス タ に 属 す る と 想 定 し て い る デ ー タ に 対 し て 同 じ ラ ベ ル を 付 与 す る .シ ステ ム は 同 じラベ ル σ)付与 され た デ ー タを 同 一 ク ラス タ に分 類 す る こ
と に よ っ て ユ ー ザ の 意 図 を 表 現 す る.
対 制 約 は 更 に,2種 類 の 制 約must‑linkとcannot・linkに 分 け られ る.ユ ー ザ が 必 ず 同 じ ク ラ ス タ に 分 類 した い と 意 図 して い る デ ー タ 対 に はmust‑1inkを 割 り 当 て,必 ず 別 の ク ラ ス タ に 分 類 し た い と 意 図 し て い る デ ー タ 対 に はcannot・1inkを 割 り 当 て る.
制 約 ネ ッ トワ ー ク を 用 い る 場 合,ユ ー ザ は 同 一 ク ラ ス タ に 分 類 した い2つ 以 上 の デ ー タ を1つ の ネ ッ トワ ー ク と み な し,ネ ッ トワ ー ク に 対 し て 制 約 を 付 与 す る.シ ス テ ム は 同 一 の 制 約 ネ ッ ト ワ ー ク 内 の デ ー タ が 同 一 ク ラ ス タ に,別 の 制 約 ネ ッ ト ワ ー ク 内 の デ ー タ が 別 ク ラ ス タ に そ れ ぞ れ 分 類 され る よ う な ク ラ ス タ を 形 成 す る.
ク ラ ス タ に 対 す る 制 約 と して,広 義 に は ク ラ ス タ リ ン グ を 行 う際 に ユ ー ザ が 指 定 す る ク ラ ス タ 数 も 制 約 と み な され る 場 合 が あ る[22].ま た,ク ラ ス タ 内 に 含 ま れ る 要 素 数 の 上 限 あ る い は 下 限 に 対 して 制 約 が 与 え られ る 場 合 も あ る[22】.
制 約 を 用 い た 応 用 事 例 と して,岡 田 ら は 大 規 模 な 画 像 デ ー タ 群 に 対 し て,少 数 の ラ ベ ル
の 付 与 か ら距 離 学 習 を 行 い,最 小 限 の 制 約 か ら高 精 度 の 制 約 付 き ク ラ ス タ リ ン グ を 行 う手
法 を 提 案 して い る[8】.ま た,榊 ら は 論 文 間 の 類 似 度 と 引 用 関 係 か ら 作 成 し た ネ ッ トワ ー ク,
論 文 の カ テ ゴ リ分 類 か ら作 成 し た ネ ッ トワ ー ク の2種 類 の ネ ッ トワー ク を 統 合 し て 制 約 ネ ッ トワ ー ク を 作 成 し,制 約 付 き ク ラ ス タ リ ン グ を 行 う こ と で,論 文 カ テ ゴ リ と論 文 間 の 関 係 の 両 方 を 協 調 させ た ク ラ ス タ リ ン グ 結 果 を 得 る 手 法 を 提 案 して い る[6].寺 見 ら は 重 心 法 とWard法 を 用 い た 階 層 的 ク ラ ス タ リ ン グ に 対 制 約 を 適 用 し た 手 法 を 提 案 して お り,特 に cannot‑1inkの 有 効 性 に つ い て 示 して い る 【23].
ク ラ ス タ リ ン グ に お け る 制 約 の 利 用 方 法 と し て,k‑meansに 対 制 約 を 適 用 し た COP‑KMEANS[24]が 知 られ て い る.COP‑KMEANSは 次 の 手 順 に 従 っ て デ ー タ の 分 類 を 行 う.
1.要 素 数0の ク ラ ス タ をk個 用 意 し,各 ク ラ ス タ に 対 し て 初 期 中 心 を 与 え る.ス テ ッ プ 数 をt=1と す る.
2.各 デ ー タxを 以 下 の 両 条 件 を 満 た す ク ラ ス タ0の 内,ク ラ ス タ 中 心 と の 距 離 が 最 短 で あ る も の に 分 類 す る.条 件 を 満 た す ク ラ ス タ が 存 在 し な い 場 合,ク ラ ス タ リ ン グ 失 敗 と し て 空 の ク ラ ス タ 集 合 を 出 力 す る.
(ア)既 に 分 類 が 終 了 し て い る デ ー タ の 内,xと の 間 にmust‑linkが 付 与 され て い る デ ー タ が0内 に 存 在 す る.
(イ)既 に 分 類 が 終 了 し て い る デ ー タ の 内,xと の 間 にcannot‑linkが 付 与 さ れ て い る デ ー タ が0内 に 存 在 しな い.
3.全 デ ー タ の 分 類 終 了 後,分 類 結 果 が 前 ス テ ッ プ(t‑1)と 同 じ で あ れ ば 終 了 し,結 果 を 出 力 す る.
4.同 じで な け れ ば,ク ラ ス タ 中 心 を ク ラ ス タ に 所 属 す る 全 デ ー タ の 平 均(重 心)と し て 再 計 算 し,t=t+1と し て 手 順2に 戻 る.
k‑meansと の 相 違 点 は 主 に 手 順2に あ る.k・meansで は ク ラ ス タ 中 心 と の 距 離 を 計 算 し, 最 近 の ク ラ ス タ に デ ー タ を 分 類 す る の に 対 し,COP・KMEANSで は 距 離 を 計 算 す る 前 に 制 約 を 確 認 す る.デ ー タ にmust‑1ink,cannot‑1inkの ど ち ら か,も し く は 両 方 が 割 り 当 て ら れ て い れ ば,そ れ を 満 た す よ うに デ ー タ を 分 類 す る.
ま た,制 約 を 考 慮 す る 他 の ア プ ロー チ と して,デ ー タ を 分 類 す る 際 に 制 約 を 確 認 す る の で は な く,前 処 理 と して デ ー タ が 存 在 す る 空 間 内 の 距 離 を 学 習 す る 手 法 が 提 案 され て い る
【251.こ の 手 法 で は 同 一 ク ラ ス タ に 分 類 した い デ ー タ 間 の 距 離 を 短 く,も し く は 別 ク ラ ス タ に 分 類 し た い デ ー タ 問 の 距 離 を 長 く す る な ど して,制 約 を 表 現 す る.変 換 後 の 距 離 空 間 に お け る デ ー タ 問 の 距 離 を 用 い て,制 約 を 考 慮 し な い 通 常 の ク ラ ス タ リ ン グ 手 法 を 適 用 す る.
こ の ア プ ロ ー チ は,既 存 の ク ラ ス タ リ ン グ ア ル ゴ リズ ム を 変 更 す る こ と な く利 用 可 能 と い う利 点 が あ る.
対 制 約 を 用 い た 制 約 付 き ク ラ ス タ リ ン グ に 関 す る研 究 で は,デ ー タ セ ッ トを 用 い て 学 習
を 行 う 際,同 一 ク ラ ス タ に 存 在 す る デ ー タ 間 にmust・linkを,別 ク ラ ス タ に 存 在 す る デ ー
タ 問 にcannot‑linkを そ れ ぞ れ 割 り 当 て る の が 一 般 的 で あ る.し か しユ ー ザ が イ ン タ ラ ク テ ィ ブ に 制 約 を 付 与 す る 際 に は,図2.1に 示 す よ うな 矛 盾 が 発 生 して しま う場 合 も存 在 す る.
こ の 図 で は デ ー タ 対AとB,BとCの 間 に はmust‑linkが,デ ー タ 対AとCの 間 に は cannot・linkが そ れ ぞ れ 付 与 され て い る,こ れ らの 制 約 を も れ な く満 た す ク ラ ス タ リ ン グ 結 果 は 存 在 しな い.こ の よ うな 例 は 珍 し く な く,例 え ば 新 聞 記 事 で 内 容 の 近 い 記 事AとB,B
とCの 間 にmust‑linkを 付 与 し,掲 載 面 の 違 うAとCの 間 に はcannot‑1inkを ユ ー ザ が 付 与 して し ま う場 合 な ど が 想 定 さ れ る.特 に 記 事 が 多 数 存 在 す る 場 合 や,制 約 付 与 作 業 が 長 期 間 に 渡 り継 続 して 行 わ れ る 場 合,こ の よ う な 矛 盾 が 発 生 しや す く な る こ と が 想 定 さ れ る, こ の よ う な 矛 盾 を 回 避 す る た め に,青 島 ら は マ イ ク ロ ブ ロ グ を 対 象 と した 制 約 付 き ク ラ ス タ リ ン グ シ ス テ ム[7]に お い て,ユ ー ザ が 矛 盾 を 含 ん だ 制 約 を 付 与 す る 操 作 を 行 お う と し た 場 合,シ ス テ ム 側 で そ の よ うな 操 作 を 禁 止 す る こ と で 矛 盾 を 回 避 して い る.ま た 性 質 上, 矛 盾 した 制 約 を 付 与 す る 操 作 が 本 質 的 に 行 え な い 手 法 も提 案 され て い る[26】,三 宅 ら は 一 っ 一 つ の デ ー タ で は な く
,デ ー タ の 集 合 で あ る ク ラ ス タ 単 位 の 操 作 を ユ ー ザ が 行 う こ と で, 矛 盾 の な い 制 約 を 生 成 す る 手 法 を 提 案 して お り[26],4節 で 詳 細 を 述 べ る.
＼
must‑Hnk
cannot‑1ink
図2.1制 約 に よ り矛 盾 が 発 生 した 状 態
2.3ク ラ ス タ リ ン グ 結 果 の 可 視 化
大 規 模 デ ー タ に 対 し て ク ラ ス タ リ ン グ を 適 用 す る こ と に よ り,デ ー タ の 分 類 結 果 を ユ ー ザ に 提 示 す る 場 合,ユ ー ザ の 意 図 に 沿 っ た ク ラ ス タ リン グ 結 果 を 作 成 す る だ け で な く,結 果 を ユ ー ザ に わ か りや す く提 示 す る こ と が 重 要 で あ る.結 果 を わ か りや す く 可 視 化 す る こ
と に よ りユ ー ザ は 結 果 を 解 析 しや す く な り,新 し い 知 識 の 発 見 作 業 時 間 の 短 縮 な ど が 可 能 と な る.
ク ラ ス タ リ ン グ 結 果 の 可 視 化 は 大 き く,非 階 層 的 ク ラ ス タ リ ン グ の 結 果 の 可 視 化 と 階 層 的 ク ラ ス タ リ ン グ の 結 果 の 可 視 化 の2手 法 に 分 け る こ と が で き る.ク ラ ス タ リ ン グ 結 果 を 可 視 化 す る 際 に は,可 視 化 に よ る ユ ー ザ の 理 解 度 の 向 上 が 重 要 と な る.以 下 で は 関 連 研 究 に っ い て ど の 点 を 考 慮 し,理 解 度 の 向 上 を 図 っ て い る か を 説 明 す る.理 解 度 を 向 上 さ せ る ア プ ロ ー チ は,階 層 的 ク ラ ス タ リ ン グ を 非 階 層 的 ク ラ ス タ リ ン グ で 異 な る.
非 階 層 的 ク ラ ス タ リン グ で は 理 解 度 の 向 上 の た め に,類 似 デ ー タ が 形 成 す る グ ル ー プ が 確 認 しや す い よ う に,各 デ ー タ に 対 応 し た ノ ー ドを 配 置 す る こ と が 課 題 と な っ て い る.解 決 策 の1つ と し てMarksら は,表 示 の 密 度 を 考 慮 し たDesignGalleries[27】 を 提 案 し て い
る,DesignGalleriesで は 主 成 分 分 析 を 利 用 し,2次 元 平 面 上 で 最 も分 散 し て デ ー タ を 配 置 で き る 主 軸 を 決 定 し,表 示 を 行 う,DesignGalleriesを 用 い る こ と で,デ ー タ が 一 箇 所 に 固 ま る こ と に よ る 誤 読 を 回 避 で き,ユ ー ザ の 理 解 度 が 向 上 す る,ま た,配 置 に 関 し て,特 に デ ー タ を 重 ね て 表 示 し て し ま う こ と に よ る 誤 読 を 回 避 す る 手 法 と し て,デ ー タ 間 の 距 離 を 考 慮 した 手 法 も 提 案 され て い る.土 井 ら は 力 学 モ デ ル を 用 い る こ と に よ り,デ ー タ 間 の 距 離 を 一 定 以 上 に 保 つ 手 法 を 提 案 して い る[28】.
階 層 的 ク ラ ス タ リ ン グ で は 理 解 度 の 向 上 の た め に,階 層 構 造 や ク ラ ス タ の 近 接 関 係,サ イ ズ の 違 い な ど を 理 解 しや す い よ うに 各 ク ラ ス タ に 対 応 した ノ ー ドを 配 置 す る こ と が 課 題
と な る.ク ラ ス タ 問 の 関 係 を 直 感 的 に 理 解 す る こ と に 重 き を お い た 手 法 と してnode‑link diagram[34]が あ る.node‑linkdiagramで は 図2.2に 示 す よ うに ク ラ ス タ 間 の 上 下(親 子 〉
関 係 を エ ッ ジ と し て 描 画 す る,図22の 各 ク ラ ス タ 内 の 数 字 は ル ー トの 階 層 を0と し た 時 の 各 ク ラ ス タ の 階 層 を 表 し,大 き い ほ ど 階 層 が 深 い こ と を 意 味 す る.全 デ ー タ 集 合 に 対 応 す る ル ー トを 起 点 と し て,同 階 層 に 位 置 す る ク ラ ス タ は ル ー トか ら の 同 一 の 距 離 に 配 置 され る こ と が 一 般 的 で あ り,ユ ー ザ は ノ ー ドが 階 層 の どの 部 分 に 位 置 し て い る か を 把 握 しや す い.
ま た,ク ラ ス タ サ イ ズ を 考 慮 し た 手 法 と し て,表 示 領 域 全 体 を 矩 形 に 分 割 す る Tree・map[5]が 提 案 さ れ て い る.図2.3は,図22と 同 じ階 層 構 造 をTree・mapに よ り描 画 した 例 で あ る.Tree‑mapで は 表 示 領 域 に お い て ク ラ ス タ を 矩 形 で 表 す.子 ク ラ ス タ は 親 ク ラ ス タ の 矩 形 を,ク ラ ス タ 内 に 存 在 す るデ ー タ数 な ど を も と に 分 割 す る こ と で 描 画 され る.
こ の 分 割 を 再 帰 的 に 行 う こ と で,階 層 構 造 全 体 を 描 画 す る.図 に お い て,階 層0で あ る ル
ー トの ク ラ ス タ は す べ て の ク ラ ス タ を 含 ん だ 全 体 を 表 す 矩 形 ,階 層1の 位 置 に あ る 黄 緑 の
ク ラ ス タ は 階 層2の ク ラ ス タ を ま と め た 矩 形 に そ れ ぞ れ 対 応 す る.
領 域 の 分 割 方 法 に は い く つ か あ り,図2.3で は 代 表 的 な 手 法 の1つ で あ る ス ラ イ ス&ダ イ ス を 利 用 し て い る.ス ラ イ ス と は,長 方 形 の 短 辺 の 長 さ は 変 え ず,長 辺 の 長 さ を 分 け る こ と で 小 さ な 長 方 形 に 分 割 す る 操 作 で あ る.常 に 長 辺 を 分 割 す る た め に,1階 層 下 を 描 画 す る 際 に は 分 割 方 法 を90度 変 更 す る.こ の 操 作 を ダ イ ス と 呼 ぶ.こ の 操 作 を 繰 り返 し行 い,表 示 領 域 全 体 を 用 い た デ ー タ 集 合 の 可 視 化 を ユ ー ザ に 提 示 す る.Tree・mapは,各 ク ラ ス タ が ど れ く ら い の 容 量 を 持 っ て い る か,も し く は ク ラ ス タ の 近 接 関 係 を 把 握 す る の に 適 して い る が,上 下 関 係 に あ る ク ラ ス タ や,別 の 親 を 持 つ 同 一 階 層 の ク ラ ス タ を 確 認 す る 場 合 は node‑1inkdiagramの ほ う が 適 して い る と い え る.
◎
図2.2node・linkdiagramの 例
図2.3Tree・mapの 例
Tree‑mapを 用 い た 例 と し て,世 界 中 の ニ ュ ー ス をTree‑mapを 用 い て 表 示 す るnewsmap が あ る.newsmapで は 上 部 の タ ブ で 国 を 選 択 す る こ と に よ っ て,そ の 国 で 起 き て い る ニ ュ ー ス の 一 覧 を 階 層 構 造 と して 表 示 す る .ク ラ ス タ 上 の 一 文 は 見 出 し で あ り,各 ク ラ ス タ の 色 は ニ ュ ー ス の ジ ャ ン ル,色 の 濃 さ は 更 新 時 間 を そ れ ぞ れ あ ら わ して い る.Tree‑mapで は
こ の よ う に 文 宇 や 色 を 追 加 す る こ と で よ り詳 細 な 情 報 を 表 す こ と が で き る.
ス ラ イ ス&ダ イ ス 以 外 の 領 域 分 割 方 法 を 採 用 した 手 法 と し て,Squari丘edTreemap[321
やQuantumTreemap[33]な どが 提 案 さ れ て い る.Squari丘edTreemapは 各 ク ラ ス タ を で き る だ け 正 方 形 に 近 い 長 方 形 で 表 す こ と に よ り,ク ラ ス タ の 見 や す さ を 向 上 させ る 手 法 で あ る.QuantumTreemapは 一 度Squar面edTreemapに よ る 分 割 を 行 っ た 後,各 ク ラ ス タ に 対 し て 同 一 形 状 の 正 方 形 を 所 属 デ ー タ 数 だ け 割 り 当 て,正 方 形 が 入 り き る よ う,ク ラ ス タ に 対 応 す る 長 方 形 の 描 画 領 域 の 大 き さ を 調 整 す る.こ れ に よ り,ク ラ ス タ の 大 き さ の 微 調 整 が 可 能 と な る.
ま た,伊 藤 ら は ク ラ ス タ リ ン グ 結 果 の 概 要 把 握 をTree・mapと 同 様 の ア プ ロ ー チ で 支 援 す る 可 視 化 手 法 と し て,デ ー タ 宝 石 箱 を 提 案 して い る[29】.デ ー タ 宝 石 箱 で は リー フ を 色 付 き の 正 方 形 の ア イ コ ン で,上 位 ノ ー ドに 当 た る ク ラ ス タ を 白 枠 の 長 方 形 で そ れ ぞ れ 表 示 す る.
これ に よ り,ユ ー ザ は ク ラ ス タ リ ン グ 結 果 の 概 観 を 把 握 す る こ とが で き る.Tree‑mapと の
相 違 点 と して,描 画 の 際 に は リ ー フ に 対 応 す る ア イ コ ン を 画 面 上 に 配 置 し,親 ク ラ ス タ は
ア イ コ ン を 白 線 で 囲 む こ と に よ っ て 描 画 す る.こ の 操 作 を 繰 り返 す こ と で 階 層 構 造 全 体 を
描 画 す る,つ ま りTree・mapが 階 層 構 造 の 上 位 か ら下 位 に 向 か っ て 描 画 して い く の に 対 し て,
デ ー タ 宝 石 箱 で は 下 位 か ら上 位 に 向 か っ て 描 画 す る.描 画 順 序 は 異 な る が,ど ち ら も概 要
把 握 に 重 き を 置 い て い る 点 で は 同 様 の ア プ ロ ー チ と み な せ る.ま た,デ ー タ 宝 石 箱 の 拡 張
手 法 と し て,ク ラ ス タ に 対 応 し た 長 方 形 の 辺 を 同 一 直 線 上 に 揃 え る こ と で 複 数 の ク ラ ス タ
を 整 列 し て 配 置 し,見 や す さ を 向 上 させ た 平 安 京 ビ ュ ー[30】や,ア イ コ ン に 変 数 の 数 だ け 色
を 割 り 当 て,色 の 濃 さ に よ り ク ラ ス タ 内 の デ ー タ が と る 変 数 の 値 を 表 現 す る こ と で,ユ ー
ザ に 詳 細 情 報 を 提 供 す る 十 二 単 ビ ュ ー[31】な ど が 提 案 さ れ て い る.
2.4イ ン タ ラ ク テ ィ ブ ク ラ ス タ リ ン グ
本 来 ク ラ ス タ リ ン グ は 教 師 な し学 習 で あ り,結 果 が ユ ー ザ の 意 図 と合 致 す る と は 限 ら な い.そ の た め ユ ー ザ の 知 識 や 意 図 を 反 映 さ せ る 手 法 と し て イ ン タ ラ ク テ ィ ブ ク ラ ス タ リ ン グ が 研 究 され て い る[35][361[37】.イ ン タ ラ ク テ ィ ブ ク ラ ス タ リ ン グ は ユ ー ザ の 意 図 を ユ ー ザ フ ィ ー ドバ ッ ク と して,計 算 機 に 与 え る こ と に よ り ク ラ ス タ リ ン グ 結 果 を 調 整 す る.ユ ー ザ フ ィ ー ドバ ッ ク か ら学 習 す る こ と に よ りユ ー ザ と 計 算 機 が 協 調 し ,よ りユ ー ザ の 意 図
に 沿 っ た 結 果 の 出 力 を 可 能 とす る.
ユ ー ザ フ ィ ー ドバ ッ ク は 以 下 の3種 類 に 大 別 で き る.
● ク ラ ス タ リ ン グ 結 果 の 全 体 構 造 の 確 認 に お け る ユ ー ザ の 意 図[38]
● 詳 細 デ ー タ の 確 認 に お け る ユ ー ザ の 意 図[35][39】[40】
● デ ー..一.bタ 分 類 に お け る ユ ー ザ の 意 図[39】【40】
全 体 構 造 の 確 認 に お け る 意 図 と し て は,表 示 す る ク ラ ス タ 数 や ク ラ ス タ の 大 き さ な ど が 想 定 され,シ ス テ ム は フ ィ ー ドバ ッ ク を も と に 調 整 を 行 う.詳 細 デ ー タ の 確 認 に お け る 意 図 と し て は,結 果 を 見 た 際 に ユ ー ザ が 興 味 を 持 っ た デ ー タ な ど が 想 定 さ れ,シ ス テ ム は フ ィ ー ドバ ッ ク を も と に デ ー タ に 関 す る 詳 細 表 示 や 受 け 取 っ た デ ー タ を 中 心 と した 分 析 を 行 う.分 類 に お け る 意 図 と し て は,デ ー タ の 同 一 も し く は 別 ク ラ ス タ へ の 分 類 が 想 定 さ れ る.
前 節 に お け る 制 約 付 き ク ラ ス タ リン グ の 制 約 は 分 類 に 関 す る ユ ー ザ の 意 図 に 当 た り,シ ス テ ム は ユ ー ザ の 意 図 で あ る 制 約 を 満 た す よ うな ク ラ ス タ リ ン グ 結 果 を 出 力 す る.
全 体 構 造 の 確 認 に お け る 意 図 を フ ィ ー ドバ ッ ク と し て 用 い た 例 と し て,井 上 ら は 画 面 上 に 表 示 す る デ ー タ 数 や 表 示 粒 度 を フ ィ ー ドバ ッ ク に よ り調 整 可 能 な シ ス テ ム を 提 案 し て い る[38].シ ス テ ム は フ ィ ー ドバ ッ ク を も とに した 可 視 化 を 行 い,デ ー タ の 外 観 や 詳 細 を 表 示 す る.
詳 細 デ ー タ の 確 認 に お け る 意 図 を ユ ー ザ フ ィ ー ドバ ッ ク と し た 例 と して,打 田 ら は ア ン ケ ー ト自 由 記 述 文 章 解 析 支 援 シ ス テ ム[35】を 提 案 し て い る.こ の 手 法 で は 多 次 元 尺 度 構 成 法 を 用 い て 文 書 問 の 関 係 性 を マ ッ プ と して 可 視 化 す る.ユ ー ザ は マ ッ プ 上 に 任 意 の ク ラ ス タ を 形 成 し,ユ ー ザ が ク ラ ス タ リ ン グ を 行 う こ と で フ ィ ー ドバ ッ ク を 与 え る.シ ス テ ム は フ
ィー ドバ ッ ク を 元 に,ユ ー ザ が 形 成 した ク ラ ス タ 内 のHKGraph(HierarchicalKeyword
Graph)を 作 成 し ユ ー ザ に 提 示 す る.HKGraphと は 文 章 情 報 に 付 与 さ れ た 属 性 情 報 と 自 由 記 述 文 書 中 の 語 句 か ら共 起 度 を 計 算 し,抽 出 され た 語 句 に 対 す る 階 層 的 キ ー ワ ー ドグ ラ フ で あ る[36】.
ま た,詳 細 デ ー タ の 確 認 に お け る 意 図 と 分 類 に お け る 意 図 の 両 方 を 扱 っ た 例 と し て,伊
藤 ら は ラ ベ ル 形 式 の 制 約 を 用 い て,マ イ ク ロ ブ ロ グ な ど か ら抽 出 した 単 語 の 制 約 付 き ク ラ
ス タ リン グ 結 果 を 表 形 式 で 表 示 す る 手 法 を 提 案 して い る[39].表 の 列 は ク ラ ス タ,行 は 単 語
の 出 現 頻 度 の 違 い を そ れ ぞ れ 表 して い る.ユ ー ザ は 表 に 対 し て 単 語 を 選 択,も し く は 単 語 の 横 に あ る チ ェ ッ ク ボ ッ ク ス を チ ェ ッ ク す る こ と に よ り フ ィ ー ドバ ッ ク を 与 え る.シ ス テ ム は 選 択 さ れ た 単 語 に っ い て は 他 ク ラ ス タ に あ る 類 似 した 単 語 を ハ イ ラ イ トで 表 示 し,チ ェ ッ ク の 入 れ られ た 単 語 に つ い て はk‑meansを 用 い た ク ラ ス タ リ ン グ 時,そ の ク ラ ス タ に 当 該 単 語 を 固 定 す る こ と で ユ ー ザ の 意 図 を 反 映 させ る.
同 様 に 詳 細 デ ー タ の 確 認 に お け る 意 図 と 分 類 に お け る 意 図 の 両 方 を 扱 っ た 例 と し て,高 間 ら は 協 調 的 マ ル チ ビ ュ ー に も とつ く イ ン タ ラ ク テ ィ ブ 文 書 ク ラ ス タ リ ン グ シ ス テ ム を 提 案 して い る[40].シ ス テ ム は4枚 の 可 視 化 パ ネ ル か ら構 成 され,そ れ ぞ れ が ク ラ ス タ レベ ル, 文 書 レベ ル,単 語 集 合 レ ベ ル,単 語 レベ ル の 可 視 化 を 行 う.ユ ー ザ は 詳 細 デ ー タ 確 認 の 意 図 と し て,各 パ ネ ル で 文 書 や 単 語 を 選 択 す る こ と に よ り フ ィ ー ドバ ッ ク を 与 え る.シ ス テ ム は フ ィ ー ドバ ッ ク を も と に,対 応 す る パ ネ ル の 表 示 を 変 更 す る こ と で ユ ー ザ の 意 図 を 反 映 さ せ る.ま た,ユ ー ザ は 分 類 に 関 す る 意 図 と し て,形 成 す る ク ラ ス タ 数 や 各 単 語 へ の 重 み を フ ィ ー ドバ ッ ク と して 与 え る.シ ス テ ム は フ ィ ー ドバ ッ ク を も と に,指 定 され た ク ラ ス タ数 のk‑meansを 行 い,距 離 計 算 時 に 重 み を 適 用 す る こ と で ユ ー ザ の 意 図 を 反 映 さ せ る.
制 約 付 き ク ラ ス タ リ ン グ を 利 用 し た イ ン タ ラ ク テ ィ ブ ク ラ ス タ リ ン グ の 場 合,制 約 が ユ ー ザ フ ィ ー ドバ ッ ク に 相 当 す る .従 っ て,制 約 付 与 に お け る ユ ー ザ の 作 業 負 荷 を 考 慮 す る 必 要 が あ る.ま た,対 制 約 を ユ ー ザ が 付 与 す る 場 合 に は 制 約 問 に 矛 盾 が 発 生 し て し ま う場 合 が あ り,こ れ を 回 避 す る 必 要 も あ る.こ れ らの 課 題 に 対 して,ユ ー ザ が 図2.4で 示 す よ う
な ク ラ ス タ 単 位 で の 操 作 を 行 っ た 結 果 か ら制 約 を 一 括 生 成 す る 手 法 が 提 案 され て い る[37].
噌 レ
∈)㊤
図2.4ク ラ ス タ 単 位 で の 操 作
こ の 手 法 で は ク ラ ス タ リン グ 結 果 を シ ス テ ム が 表 示 した の ち,ユ ー ザ は 図2.4に 示 す1 つ の ク ラ ス タ を2つ の ク ラ ス タ に 分 け る 分 割 操 作,2つ の ク ラ ス タ を1つ の ク ラ ス タ に ま と め る 統 合 操 作 を 行 う.2つ の 操 作 を ま と め て グ ル ー ピ ン グ操 作 と 呼 び,グ ル ー ピ ン グ 操 作 を 通 して ユ ー ザ は 類 似 す る と 判 断 し た デ ー タ を 同 一 ク ラ ス タ に 集 め る.す べ て の 操 作 が 終 了 した 段 階 で,同 一 ク ラ ス タ 内 の い く つ か の デ ー タ 間 に 一 括 でmust‑linkを 生 成 す る.作 業 の 流 れ 図 を 図2.5に 示 し,各 作 業 の 内 容 を 以 下 に 述 べ る.ま た,こ こ で 示 す1ス テ ッ プ は ク
ラ ス タ リ ン グ 結 果 の 表 示 か ら 制 約 付 ク ラ ス タ リ ン グ の 実 施 ま で を 指 す.
⑦ 制約付き
クラスタリング
一括 生 成制 約
目標 達 成?
グ ルー ピング
グル ー ピング結 果 の 表示
クラス タ リング?
Yes
Yes
赤:計 算 機 側 の タスク 緑:ユ ー ザ 側 の タス ク
図2.5制 約 一 括 生 成 手 法 の フ ロー チ ャ ー ト
① 制 約 な し ク ラ ス タ リ ン グ:1回 目の ク ラ ス タ リン グ で は ユ ー ザ の 操 作 に よ る 制 約 が 与 え られ な い た め,通 常 の ク ラ ス タ リ ン グ を 行 う.
② ク ラ ス タ リ ン グ 結 果 の 表 示:ク ラ ス タ リ ン グ の 結 果 を イ ン タ フ ェ ー ス に 表 示 す る.
③ 結 果 評 価:表 示 さ れ た 結 果 が ユ ー ザ の 意 図 を 満 た す も の か ユ ー ザ が 判 断 す る.満 た し て い れ ば 終 了 と し,満 た し て い な け れ ば グ ル ー ピ ン グ に 移 行 す る.
④ グ ル ー ピ ン グ:ユ ー ザ の 意 図 を 満 た して い な い ク ラ ス タ に 対 し て,グ ル ー ピ ン グ 操 作 を 行 う.ユ ー ザ が 別 の ク ラ ス タ に 入 れ た い と意 図 し て い る デ ー タ 集 合 が 同 一 ク ラ
ス タ 内 に 存 在 して い れ ば 分 割 操 作 を 行 い,デ ー タ を 別 の ク ラ ス タ に 分 け る.ま た ユ ー ザ が 同 じ ク ラ ス タ に 入 れ た い と 意 図 し て い る デ ー タ 集 合 が 別 ク ラ ス タ 内 に 存 在 し
て い れ ば,ク ラ ス タ 対 に 対 して 統 合 操 作 を 行 い,デ ー タ を 同 一 ク ラ ス タ に ま と め る.
⑤ グ ル ー ピ ン グ 結 果 の 表 示:グ ル ー ピ ン グ 操 作 を 行 っ て い な い ク ラ ス タ も含 め て,ク ラ ス タ 群 全 体 を 表 示 す る.
⑥ 再 ク ラ ス タ リ ン グ:グ ル ー ピ ン グ 操 作 の 結 果 が ユ ー ザ の 意 図 を 満 た し て い る も の で あ れ ば 制 約 一 括 生 成 に 移 行 す る.満 た して い な い 場 合 は グ ル ー ピ ン グ に 戻 る.
⑦ 制 約 一 括 生 成:ユ ー ザ の グ ル ー ピ ン グ 結 果 よ り,同 一 ク ラ ス タ に 統 合 され た い く つ か の デ ー タ 間 にmust・1inkを 生 成 す る.
⑧ 制 約 付 き ク ラ ス タ リ グ:生 成 し たmust‑linkを も と にCOP・KMEANSを 実 行 す る.
ス テ ッ プ ⑦ に お い て,ユ ー ザ の グ ル ー ピ ン グ 操 作 で は 完 全 な ク ラ ス タ が 形 成 さ れ る と は 限 らず,あ る 程 度 の ノ イ ズ が 含 ま れ る と想 定 さ れ る.そ の た め す べ て の デ ー タ 間 で は な く, い く つ か の デ ー タ 間 へ の 付 与 と して い る.制 約 を 付 与 す る デ ー タ 対 は,過 去 の グ ル ー ピ ン
グ 履 歴 を 考 慮 し,確 率 的 に 決 定 す る.以 下 に 手 順 を 示 す.
1.オ ブ ジ ェ ク ト集 合 を0={x1,...,Xn}と し,ス テ ッ プtで の グ ル ー ピ ン グ 情 報 を 式(2.5) のc(Xi,Xj,t)で 表 す.
幅 の一{畿1纒1嬬1 (2.5)
2.Tス テ ッ プ 内 に お け る 同 一 ク ラ ス タ へ の 統 合 回 数f(Xi,Xj,T)を 式(2.6)で 求 め る.
f(Xi,Xj,T)=Σo≦kく7c(Xi,Xj,t‑k)
(2.6)3.以 下 の2つ の 戦 略 に お け る ス コ アS(Xi,Xj)を 式(2.7)で 求 め る.
(ア)保 守 的 戦 略 …c(Xi,Xj,t)=1を 満 た す デ ー タ 対 の 中 でf(Xi,Xj,T)が 高 い デ ー タ 対 ほ
どユ ー ザ の 着 目 度 が 高 い と 判 断 し,優 先 的 に 制 約 を 付 与 す る.
(イ)c(Xi,Xj,t)=1を 満 た す デ ー タ 対 の 中 でf(Xi,Xj,T)が 低 い デ ー タ 対 ほ ど ユ ー ザ の 着
目度 が 高 い と判 断 し,優 先 的 に制 約 を付 与 す る,
s幅贈 瀦
〔購 脚 醐 戦略, (2.7>
4.c(Xi,Xj,t)=1と な る オ ブ ジ ェ ク ト対 の 集 合 をPと し,S(Xi,tj)の う ち,Pに 含 ま れ て い る オ ブ ジ ェ ク ト対 の ス コ ア の 合 計 をF(P)と し,式(2.8)で 求 め る,
F(P)一 Σs(Xk・'Xk・)
1Sk≦lpi
(2.8)
5.R=rと す る.た だ し,rは1≦r≦F(P)の 乱 数 で あ る.
6.Rを 式(2.9)に 従 っ て 更 新 す る,R≦0と な れ ば そ の 時 のXkl,Xk2間 に 皿u、st・linkを 付 与 す る.そ れ 以 外 はk←k+1と し て 再 びRを 更 新 す る.
R←R‑s(Xk1,Xk2)
(2.9)上 記 ス テ ッ プ4‑6は,ル ー レ ッ ト選 択 に よ る オ ブ ジ ェ ク ト対 選 択 に 対 応 す る.制 約 を 逐 次 指 定 す る 手 法 との 比 較 実 験 を 行 うた め に,後 述 す る 統 合 環 境TETDM(TotalEnVironment
forTextDataMining)[4】 上 に 両 手 法 を 用 い た イ ン タ ラ ク テ ィ ブ ク ラ ス タ リ ン グ シ ス テ ム を
実 装 した 例 が 報 告 さ れ て い る[3].比 較 実 験 の 結 果,制 約 一 括 生 成 手 法 で は 逐 次 指 定 手 法 と
比 べ,作 業 が 終 了 す る ま で の ク ラ ス タ リ ン グ 回 数 が 少 な い こ と,制 約 が 全 体 に ば らつ い て
お り,大 局 的 な 視 点 か ら の 制 約 の 付 与 を 行 え る こ と を 示 し て い る.
2.5TETDM(TotalEnvironmentforTextDataMining)
