January 2019
Volume 34 Number 1
[テストの実行]
C# を使用した自己組織化マップ
.jpg "James McCaffrey に心より感謝いたします。")
自己組織化マップ (Self-Organizing Map: SOM) は、比較的単純な機械学習 (ML) 手法/オブジェクトです。ただし、SOM にはバリエーションがかなり多く、他のいくつかの ML 手法 (教師なしクラスタリング、教師付き分類法など) と似た特性もあるため、少しわかりにくいようです。簡潔に言うと、SOM は探索的クラスタリング分析の一種だと私はよく考えます。その目標は、互いに似ているデータ項目を 1 つのマップ ノードに割り当てることです。
SOM とは何か、またこの記事でどんなことを説明するかを把握していただくために、図 1 のデモ プログラムと図 2 をご覧ください。このデモは、UCI 数字データセット用の 5x5 SOM を作成します。データセットには 1,797 項目があり、SOM には 25 個のノードがあります。各データ項目が正確に 1 つのマップ ノードに関連付けられるように SOM が作成されます。
.png "自己組織化マップ (SOM) のデモ")
図 1 自己組織化マップ (SOM) のデモ
.png "SOM を可視化した例")
図 2 SOM を可視化した例
SOM を構築した後、このデモは各マップ ノードに関連付けられた最も共通する数字を計算し、その情報が 図 2 に表示されます。SOM 分析の結果は通常、可視化され、何らかの主観的な分析を必要とします。たとえば、特定の 1 つの数字を表すほとんどのデータ項目が、互いに近接する SOM ノードに割り当てられていることが表示されます。さらに、数字の 0 と数字の 6 をそれぞれ表すデータ項目が SOM 内で互いに近接しています。これは、両者の間の類似性が、数字の 4 と数字の 8 の間の類似性よりも何らかの形で大きいことを示唆します。
今回は、少なくとも中級レベルのプログラミング スキルがあることを前提としますが、SOM の知識は問いません。デモ プログラムのコーディングでは C# を使用していますが、コードを Visual Basic や Python などの別の言語にリファクタリングするのはそれほど難しくないでしょう。デモ プログラムのコード全体を図 3 に示します (スペース節約のために少しだけ編集しています)。また、本稿付随のダウンロード セクションからこのコードとデータ ファイルを入手することもできます。
図 3 自己組織化マップのデモ プログラム
using System;
using System.Collections.Generic;
using System.IO;
namespace SOmap
{
class SOmapProgram
{
static void Main(string[] args)
{
Console.WriteLine("\nBegin self-organizing map demo \n");
Random rnd = new Random(0);
int Rows = 5, Cols = 5;
int RangeMax = Rows + Cols;
double LearnRateMax = 0.5;
int StepsMax = 100000;
// Initialize SOM nodes to random values
double[][][] map = new double[Rows][][]; // [r][c][vec]
for (int i = 0; i < Rows; ++i) {
map[i] = new double[Cols][];
for (int j = 0; j < Cols; ++j) {
map[i][j] = new double[64];
for (int k = 0; k < 64; ++k)
map[i][j][k] = rnd.NextDouble();
}
}
// Read data and labels into memory
Console.WriteLine("Reading UCI digits data into memory");
double[][] data = new double[1797][];
for (int i = 0; i < 1797; ++i)
data[i] = new double[64];
int[] labels = new int[1797];
FileStream ifs = new FileStream("..\\..\\digits_uci.txt",
FileMode.Open);
StreamReader sr = new StreamReader(ifs);
string line = ""; string[] tokens = null;
int row = 0;
while ((line = sr.ReadLine()) != null) {
tokens = line.Split(',');
for (int j = 0; j < 64; ++j)
data[row][j] = double.Parse(tokens[j]) / 16.0;
labels[row] = int.Parse(tokens[64]);
++row;
}
sr.Close(); ifs.Close();
// Construct the SOM
Console.WriteLine("Constructing 5x5 SO Map");
for (int s = 0; s < StepsMax; ++s) // main loop
{
if (s % (int)(StepsMax/5) == 0 && s > 0)
Console.WriteLine("step = " + s);
double pctLeft = 1.0 - ((s * 1.0) / StepsMax);
int currRange = (int)(pctLeft * RangeMax);
double currLearnRate = pctLeft * LearnRateMax;
// Pick random data index
int t = rnd.Next(0, 1797);
// Get (row,col) of closest map node -- 'bmu'
int[] bmuRC = ClosestNode(data, t, map);
// Move each map mode closer to the bmu
for (int i = 0; i < Rows; ++i) {
for (int j = 0; j < Cols; ++j) {
if (ManDist(bmuRC[0], bmuRC[1], i, j) <= currRange)
for (int k = 0; k < 64; ++k)
map[i][j][k] = map[i][j][k] +
currLearnRate * (data[t][k] - map[i][j][k]);
} // j
} // i
} // s(tep)
Console.WriteLine("Map construction complete \n");
// Show one map node
Console.WriteLine("Value of map[1][1] vector is: ");
Console.WriteLine(map[1][1][0].ToString("F4") + " " +
map[1][1][1].ToString("F4") + " . . " +
map[1][1][63].ToString("F4"));
Console.WriteLine(" [0] [1] . . [63] \n");
// Map has been created. assign data items to map
Console.WriteLine("Assigning data indices to map \n");
List<int>[][] mapping = new List<int>[Rows][];
for (int i = 0; i < Rows; ++i)
mapping[i] = new List<int>[Cols];
for (int i = 0; i < Rows; ++i)
for (int j = 0; j < Cols; ++j)
mapping[i][j] = new List<int>();
for (int t = 0; t < 1797; ++t) // each data item
{
// Find node map coords where node is closest to D(t)
int[] rc = ClosestNode(data, t, map);
int r = rc[0]; int c = rc[1];
mapping[r][c].Add(t);
}
Console.WriteLine("Data indices assigned to map[3][3]: ");
foreach (int idx in mapping[3][3])
Console.Write(idx.ToString().PadLeft(5) + " ");
Console.WriteLine("\n");
// Show one possible visualization
Console.WriteLine("Most common labels for each map node: ");
for (int i = 0; i < Rows; ++i) {
for (int j = 0; j < Cols; ++j) {
List<int> members = new List<int>(); // '0'- '9'
foreach (int idx in mapping[i][j])
members.Add(labels[idx]);
int mcv = MostCommonVal(members);
Console.Write(mcv + " ");
}
Console.WriteLine("");
}
Console.WriteLine("\nEnd self-organizing map demo");
Console.ReadLine();
} // Main
static int ManDist(int x1, int y1, int x2, int y2)
{
return Math.Abs(x1 - x2) + Math.Abs(y1 - y2);
}
static double EucDist(double[] v1, double[] v2)
{
double sum = 0;
for (int i = 0; i < v1.Length; ++i)
sum += (v1[i] - v2[i]) * (v1[i] - v2[i]);
return Math.Sqrt(sum);
}
static int[] ClosestNode(double[][] data, int t,
double[][][] map)
{
// Coords in map of node closest to data[t]
double smallDist = double.MaxValue;
int[] result = new int[] { 0, 0 }; // (row, col)
for (int i = 0; i < map.Length; ++i) {
for (int j = 0; j < map[0].Length; ++j) {
double dist = EucDist(data[t], map[i][j]);
if (dist < smallDist) {
smallDist = dist; result[0] = i; result[1] = j;
}
}
}
return result;
}
static int MostCommonVal(List<int> list)
{
if (list.Count == 0) return -1;
int largestCount = 0; int mostCommon = 0;
int[] counts = new int[10];
foreach (int val in list) {
++counts[val];
if (counts[val] > largestCount) {
largestCount = counts[val]; mostCommon = val;
}
}
return mostCommon;
}
} // Program
} // ns
SOM について理解する
SOM を作成するための第一歩は、対象となるデータを確実に理解することです。UCI 数字データセットには 1,797 個の項目があります。データは次のようになっています。
0, 12, 0, 8, . . 16, 70, 9, 11, 5, . . 13, 4...
1 項目ごとに 65 個の値があります。最初の 64 個の値は、未加工の 8x8 手書き数字を表すグレースケール ピクセル値 (0 から 16 の範囲) です。最後の 1 つの値は、ピクセル値に対応する数字ラベル (0 から 9) です。したがって、上記のデータセットにある 2 つの項目はそれぞれ 7 および 4 を表します。ラベル付きデータ、またはラベルのないデータに関して SOM を作成できますが、基本的な SOM では、ラベルのないデータは厳密に数値でなければなりません。
このデモ プログラムは 5x5 SOM を作成します。SOM のディメンションはかなりの程度、自由裁量に任され、多くの場合は試行錯誤した上で決まります。SOM の各セルをノードといいます。各ノードは 1 つのベクター値を保持し、それらはすべて同じ長さで、ラベルを除くデータ項目を含んでいます。したがって、デモの SOM 内の各ノードには 64 個の値からなる 1 つのベクターがあります。たとえば図 1 を見ると、SOM が作成された後、[1][1] 地点のマップ ノードは (0.000, 0.0237, . .0.0086) です。
SOM を作成すると、各ノード ベクターがいくつかのデータ項目を表すようになり、幾何学的に互いに近接するマップ ノードは、互いに類似するデータ項目を表します。デモ SOM の作成に使われたアルゴリズムを擬似コードで大まかに表すと、次のようになります。
create map with random node vectors
loop while s < StepsMax times
compute what a "close" node is, based on s
compute a learn rate, based on s
pick a random data item
determine map node closest to data item ("BMU")
for-each node close to the BMU
adjust node towards data item
end-loop
実際、SOM の作成は、アルゴリズムを厳格に規定するというよりも、メタヒューリスティック的です。擬似コードの各ステートメントを複数の方法で実装することができます。
デモ プログラム
このデモ プログラムを作成するために、私は Visual Studio を起動して、SOmap という新しい C# コンソール アプリケーション プロジェクトを作成しました。今回は Visual Studio 2017 を使用しましたが、このデモは .NET との大きな依存関係がないので、どのバージョンの Visual Studio でも機能するでしょう。テンプレート コードが読み込まれた後、Program.cs ファイルの名前を SOmapProgram.cs に変更します。これにより、Program クラスの名前が Visual Studio によって自動的に変更されます。エディター ウィンドウで、不要な using ステートメントをすべて削除し、System 名前空間への参照だけを残しました。次に、Collections.Generic および IO 名前空間への参照を追加しました。これは、デモで List<int> コレクションを使用してテキスト ファイルからデータを読み取るためです。
デモ プログラムの Main メソッドの開始部分は次のとおりです。
Random rnd = new Random(0);
int Rows = 5, Cols = 5;
int RangeMax = Rows + Cols;
double LearnRateMax = 0.5;
int StepsMax = 100000;
SOM アルゴリズムの主要な部分は、2 つのマップ ノードが互いに近接しているとはどんな意味かを決定します。このデモはマンハッタン距離を使用しています。たとえば [1][1] および [3][4] におけるマップ ノード間のマンハッタン距離は 2 + 3 = 5 です。5x5 マップの場合、任意の 2 ノード間の距離は最大で 5 + 5 = 10 になります。
主要な処理ループの中では、互いに「近い」ノードを定義する現在の最大距離が次のように計算されます。
double pctLeft = 1.0 - ((s * 1.0) / StepsMax);
int currRange = (int)(pctLeft * RangeMax);
double currLearnRate = pctLeft * LearnRateMax;
pctLeft 変数は、残っているステップ数の割合を計算します。たとえば、StepsMax が 100 に設定され、現在のループ カウント変数が s = 33 である場合、残りのステップ数の割合は 0.67 です。この割合を使用して、ステップ s の近隣ノードの最大距離が計算されます。同様に、近隣ノードが更新されると、残存ステップ数の割合を使用して学習率を徐々に減らしていきます。
それぞれのトレーニング反復ステップで、ランダムに選ばれたデータ項目に (ユークリッド距離で) 最も近いマップ内の 1 つのノードを、「ベスト マッチング ユニット (BMU)」といいます。現在の BMU に近い各ノード マップを更新するコードは、次のとおりです。
for (int i = 0; i < Rows; ++i) {
for (int j = 0; j < Cols; ++j) {
if (ManDist(bmuRC[0], bmuRC[1], i, j) <= currRange)
for (int k = 0; k < 64; ++k)
map[i][j][k] = map[i][j][k] +
currLearnRate * (data[t][k] - map[i][j][k]);
言葉で表現すると、各マップ ノードにおいて、近接を定義する現在の最大範囲よりもマンハッタン距離が小さい場合、マップ ノード ベクターの現在値と現在のデータ項目の間の差異に基づきベクターがわずかに調整されます。
SOM を使用する
n X m 個のノードからなるグリッドとして SOM を作成したとします。ここで各ノードは、分析対象のデータ (ラベルを除く) と同じ長さの数値ベクターだとします。これでどうでしょう。SOM の使用方法は問題に応じて異なります。ラベルのないデータの場合、1 つの標準的な技法は、n X m グリッドである U-Matrix を作成することです。この場合、各ノードの値は、対応する SOM ノード ベクターといくつかの近隣ノード ベクターの間の平均距離です。U-Matrix の表示では、通常、それぞれの値が 1 つのグレースケール ピクセル値として解釈されます。
ラベルのないデータから作成された SOM を表示するもう 1 つの方法は、各ノード ベクターを 1 つの色にマッピングすることです。たとえば SOM ノード ベクターのサイズが 6 である場合、RGB カラー モデルを使ってそれぞれの SOM セルに色を付けることができます。その際、最初の 2 つのベクター値の平均に R を割り当て、次の 2 つのベクター値に G、最後の 2 つの値に B を割り当てます。このデモの SOM ノード ベクターのサイズは 64 ですから、各ベクターを 1 つの色に割り当てる明白な方法はありません。
ラベル付きのデータの場合、それぞれの SOM ノードを 1 つのラベルにマッピングできます。デモ プログラムは、各 SOM ノードに関連付けられた分析対象データからすべてのラベルを判別し、ノードごとに最も頻度の高いラベルを計算して、任意の色付け方法でノードに色を割り当てます。
まとめ
デモ プログラムで使用した基本的な自己組織化マップ構造には、数多くのバリエーションがあります。n X m の長方形グリッドを使用する代わりに、SOM 内の各セルが六角形であるレイアウトを使用することもできます。SOM の端が互いに繋がっているドーナツ状のジオメトリを使用することもできます。2 つのディメンションではなく 3 つのディメンションを使用できます。さらに、ノードの近接を定義する方法も多数あります。他も同様に続きます。
SOM は ML の分野で広く知られていますが、少なくとも私の周囲ではそれほど頻繁には使用されていません。その理由がいくつか考えられますが、その中でも特に、SOM のバリエーションが多すぎて特定の 1 つの設計を選ぶのに苦労するのが主な原因だと思われます。さらに、私の経験に基づいて言うと、SOM を使ってデータセットから洞察を得るには (ML ライブラリにある既製の SOM をそのまま使用するのではなく) カスタム SOM が必要です。とはいえ、問題のシナリオによっては SOM から役立つ洞察を導き出すことが可能です。
Dr.James McCaffreyは、ワシントン州レドモンドの Microsoft Research に勤務しています。これまでに、Internet Explorer、Bing など、いくつかの主要なマイクロソフト製品にも携わってきました。Dr.McCaffrey の連絡先は jammc@microsoft.com (英語のみ) です。
この記事のレビューに協力してくれたマイクロソフト技術スタッフのChris Lee、Ricky Loynd、Ken Tran に心より感謝いたします。