sqlite3-ruby でプレースホルダの最初の引数が無視される問題について

環境によっては sqlite3-ruby でプレースホルダを使うと最初の引数が無視されるという問題が発生することがある．

require 'rubygems'
require 'sqlite3'

db = SQLite3::Database.new("test.db")
db.execute("CREATE TABLE t (a INTEGER PRIMARY KEY, b INTEGER, c INTEGER)")
db.execute("INSERT INTO t (b, c) VALUES (?, ?)", 42, 666)

これを実行すると t には (a, b, c) = (1, 42, 666) という組が挿入されるはずだが，特定の環境では (a, b, c) = (1, NULL, 666) という組が挿入されてしまう．

プレースホルダの引数を配列にして渡すと，この問題は解決できるらしい．

require 'rubygems'
require 'sqlite3'

db = SQLite3::Database.new("test.db")
db.execute("CREATE TABLE t (a INTEGER PRIMARY KEY, b INTEGER, c INTEGER)")
db.execute("INSERT INTO t (b, c) VALUES (?, ?)", [42, 666])      # プレースホルダの引数を配列にした

これは正しく動く．

K-means, EM Algorithm

PRMLを見ながら，K-meansによるクラスタリングと，EM Algorithmによるクラスタリングを実装してみた．
EM Algorithmの方は，あまり考えずに普通にループで書いてるのでかなり遅い．
うまく書けば行列演算で効率的にできるんだろうけど，まだ numpy, scipy の経験値が足りない…．

#!/usr/bin/env python
# k-means

import numpy as np
import numpy.random as random
import matplotlib.pyplot as plt

def adjust_scale(dataset):
    # adjust dataset with mean=0, stddev=1
    mean = np.mean(dataset, axis=0)
    std = np.std(dataset, axis=0)
    return (dataset - mean) / std

def plot_dataset(dataset, k, cluster):
    options = ["b.", "r.", "g.", "c.", "m.", "y.", "k."]
    fig = plt.figure()
    ax = fig.add_subplot(111)
    for i in xrange(k):
        subset = dataset[cluster==i]
        ax.plot(subset[:,0], subset[:,1], options[i])

def init_center(dataset, n, k):
    # choose random k points as initial values of centers
    index = np.arange(n, dtype=int)
    random.shuffle(index)
    return dataset[index[:k]]

def e_step(dataset, n, k, cluster, center):
    # assign points to clusters which have nearest centers
    for i in xrange(n):
        distance = np.sum((center - dataset[i]) ** 2, axis=1)
        cluster[i] = np.argmin(distance)
    
def m_step(dataset, n, k, cluster, center):
    # move centers to gravity centers
    for i in xrange(k):
        center[i] = np.mean(dataset[cluster==i], axis=0)

def k_means(dataset, k):
    # divide dataset into k clusters
    n = dataset.shape[0]                # the number of points
    cluster = np.empty(n, dtype=int)    # cluster assignments
    center = init_center(dataset, n, k) # centers of the clusters
    max_iter = 100                      # maximum iteration times
    for i in xrange(max_iter):
        old_cluster = cluster.copy()
        e_step(dataset, n, k, cluster, center)
        if np.all(cluster == old_cluster): break
        m_step(dataset, n, k, cluster, center)
    return cluster

k = 2
random.seed()
dataset = adjust_scale(np.loadtxt("faithful.txt"))
cluster = k_means(dataset, k)
plot_dataset(dataset, k, cluster)
plt.show()

#!/usr/bin/env python
# EM algorithm

import numpy as np
import numpy.linalg as la
import numpy.random as random
import matplotlib.pyplot as plt

def mvndst(x, mean, cov):
    # multivariate normal distribute function
    d = x.size
    a = (2.0*np.pi)**(-0.5*d) * (la.det(cov)**-0.5)
    b = -0.5 * np.dot(np.dot(x - mean, la.inv(cov)), x - mean)
    return a * np.exp(b)

def adjust_scale(dataset):
    # adjust dataset with mean=0, stddev=1
    mean = np.mean(dataset, axis=0)
    std = np.std(dataset, axis=0)
    return (dataset - mean) / std

def plot_dataset(dataset, k, res):
    fig = plt.figure()
    ax = fig.add_subplot(111)
    n = dataset.shape[0]
    colors = np.zeros((n, 3))
    colors[:,0] = res[:,0]
    colors[:,2] = res[:,1]
    for i in xrange(n):
        colors[i,:] /= np.sqrt(np.sum(colors[i,:] ** 2))
    x = dataset[:,0]
    y = dataset[:,1]
    ax.scatter(x, y, c=colors)

def init_mean(dataset, n, k):
    # choose random k points as initial values of mean
    index = np.arange(n, dtype=int)
    random.shuffle(index)
    return dataset[index[:k]]

def e_step(dataset, n, k, mean, cov, mix, res):
    for i in xrange(n):
        denom = 0.0
        for j in xrange(k):
            denom += mix[j] * mvndst(dataset[i], mean[j], cov[j])
        for j in xrange(k):
            res[i, j] = mix[j] * mvndst(dataset[i], mean[j], cov[j]) / denom

def m_step(dataset, n, k, mean, cov, mix, res):
    for i in xrange(k):
        weight = np.sum(res[:,i])
        mean[i] = 0.0
        for j in xrange(n):
            mean[i] += res[j, i] * dataset[j]
        mean[i] /= weight
        cov[i] = np.zeros((k, k))
        for j in xrange(n):
            diff = dataset[j] - mean[i]
            cov[i] += res[j, i] * np.outer(diff, diff)
        cov[i] /= weight
        mix[i] = weight / n

def calc_likehood(dataset, n, k, mean, cov, mix):
    likehood = 0.0
    for i in xrange(n):
        s = 0.0
        for j in xrange(k):
            s += mix[j] * mvndst(dataset[i], mean[j], cov[j])
        likehood += np.log(s)
    return likehood

def em_algorithm(dataset, k):
    # divide dataset into k clusters
    n, d = dataset.shape
    mean = init_mean(dataset, n, k)
    cov = np.array([np.eye(d)] * k)
    mix = np.repeat(1.0/k, k)
    res = np.empty((n, k))
    max_iter = 20
    threshold = 0.001
    likehood = calc_likehood(dataset, n, k, mean, cov, mix)
    for i in xrange(max_iter):
        e_step(dataset, n, k, mean, cov, mix, res)
        m_step(dataset, n, k, mean, cov, mix, res)
        old_likehood = likehood
        likehood = calc_likehood(dataset, n, k, mean, cov, mix)
        if likehood - old_likehood < threshold: break
    return res

k = 2
random.seed()
dataset = adjust_scale(np.loadtxt("faithful.txt"))
res = em_algorithm(dataset, k)
plot_dataset(dataset, k, res)
plt.show()

Jaccard 距離

Jaccard 係数

Ubuntu Server に LaTeX 環境を入れた

Ubuntu 10.04 Server Edition に LaTeX の環境を構築した時のメモ。

基本的に JapaneseLocalizedDerivative/LaTeXForJapanese - Ubuntu Japanese Wiki の通りにやっていけばいいんだけど、Ubuntu Server だと、latex-env-ja が見つからない。どうも latex-env-ja は Ubuntu の Japanese Team が提供する追加パッケージに入ってるらしく、Ubuntu の Server Edition だとそのパッケージレポジトリを自分で追加しないといけない。そこで、Ubuntuの日本語環境 | Ubuntu Japanese Team を見ながらパッケージレポジトリを追加する。

$ wget -q https://www.ubuntulinux.jp/ubuntu-ja-archive-keyring.gpg -O- | sudo apt-key add -
$ wget -q https://www.ubuntulinux.jp/ubuntu-jp-ppa-keyring.gpg -O- | sudo apt-key add -
$ sudo wget https://www.ubuntulinux.jp/sources.list.d/lucid.list -O /etc/apt/sources.list.d/ubuntu-ja.list
$ sudo apt-get update
$ sudo apt-get upgrade

次に latex-env-ja パッケージを入れる。dvipsk-ja の依存関係を解決できないと言われるけど、特に何も考えずにYを答えて次に進む。

$ sudo aptitude install latex-env-ja

結構、このコマンドの実行に時間がかかるので、その時間を使って調べてたら、dvipsk-ja の依存関係を直したものを公開している人を発見した (dvipsk-ja : Mitsuya Shibata) のでありがたく使わせてもらうことにした。

$ sudo aptitude install python-software-properties
$ sudo add-apt-repository ppa:cosmos-door/dvipsk-ja
$ sudo aptitude update

これで、dvipsk-ja がインストールできるようになる。次に latex-extra-ja をインストール。一緒に dvipsk-ja も入る。

$ sudo aptitude install latex-extra-ja

次。これが何なのかよく分かってないけどとりあえず実行。

$ sudo jisftconfig add

CMAP 関係のインストール。

$ sudo aptitude install cmap-adobe-cns1 cmap-adobe-gb1 cmap-adobe-japan2 gs-cjk-resource

次に、気の向くままに 〜備忘録@wiki〜 - LaTeX を見ながら dvipdfmx の設定をする。

まず、/etc/texmf/dvipdfmx/dvipdfmx.cfg の最後に

f jis-cjk.map

と加える。次に、/etc/texmf/texmf.cnf の CMAPFONTS の行を次のように編集する。

CMAPFONTS = .;$TEXMF/fonts/cmap//;/usr/share/fonts/cmap//

最後に pdfglyphlist.txt と glyphlist.txt を w32tex から持ってくる。

$ cd /tmp
$ wget http://w32tex.org/current/dvipdfm-w32.tar.bz2
$ tar xvf dvipdfm-w32.tar.bz2
$ cd share/texmf/fonts/map/agl
$ sudo cp -v pdfglyphlist.txt glyphlist.txt /etc/texmf/dvipdfmx

SlimDXでテクスチャを表示するサンプル

SlimDXでテクスチャを表示するサンプルを書いてみた。sample.png がアルファ値を持ってる場合はちゃんとアルファブレンドして表示する。

using System;
using System.Drawing;
using System.Runtime.InteropServices;
using SlimDX;
using SlimDX.Direct3D9;
using SlimDX.Windows;

namespace SlimDXTextureSample {
    [StructLayout(LayoutKind.Sequential)]
    struct Vertex {
        public const VertexFormat Format = VertexFormat.Position | VertexFormat.Texture1;

        public Vector3 Position;
        public Vector2 TextureCoordinate;
    }

    static class Program {
        // 画面の幅と高さ
        static int _width = 800, _height = 600;
        // Direct3D9 Device
        static Device _device;
        // テクスチャ
        static Texture _texture;
        // テクスチャ描画用の頂点バッファ
        static VertexBuffer _vertices;

        /// <summary>
        /// Direct3D9 Deviceの初期化を行う
        /// </summary>
        /// <param name="form"></param>
        static void InitializeDirect3D9(RenderForm form) {
            var pp = new PresentParameters();
            pp.BackBufferFormat = Format.X8R8G8B8;
            pp.BackBufferCount = 1;
            pp.BackBufferWidth = form.ClientSize.Width;
            pp.BackBufferHeight = form.ClientSize.Height;
            pp.Multisample = MultisampleType.None;
            pp.SwapEffect = SwapEffect.Discard;
            pp.EnableAutoDepthStencil = true;
            pp.AutoDepthStencilFormat = Format.D16;
            pp.PresentationInterval = PresentInterval.Default;
            pp.Windowed = true;
            pp.DeviceWindowHandle = form.Handle;

            _device = new Device(new Direct3D(), 0, DeviceType.Hardware, form.Handle, CreateFlags.HardwareVertexProcessing, pp);
        }

        /// <summary>
        /// テクスチャを読み込んで頂点バッファを作る
        /// </summary>
        static void LoadTexture() {
            // テクスチャを sample.png から読み込む
            ImageInformation info;
            _texture = Texture.FromFile(_device, "sample.png", 0, 0, 1, Usage.None,
                Format.A8R8G8B8, Pool.Managed, Filter.None, Filter.None, 0, out info);

            var description = _texture.GetSurfaceLevel(0).Description;
            // テクスチャの幅と高さ (2のべき乗になるように調整される)
            float textureWidth = description.Width;
            float textureHeight = description.Height;
            // 画像の幅と高さ
            float imageWidth = info.Width;
            float imageHeight = info.Height;

            // 頂点のサイズ (バイト)
            int vertexSize = Marshal.SizeOf(typeof(Vertex));
            // 頂点バッファを作成
            _vertices = new VertexBuffer(_device, 4 * vertexSize, Usage.WriteOnly, Vertex.Format, Pool.Managed);
            // 頂点バッファをロック
            var dataStream = _vertices.Lock(0, 4 * vertexSize, LockFlags.None);

            // テクスチャ座標の指定
            // 0.5ピクセル分だけずらしてやらないと、画像がぼけてしまう
            float x1 = 0.5f / textureWidth, y1 = 0.5f / textureHeight;
            float x2 = (imageWidth + 0.5f) / textureWidth, y2 = (imageHeight + 0.5f) / textureHeight;
            // 頂点バッファにデータを書き込む
            dataStream.WriteRange(new[] {
                new Vertex { Position = new Vector3(0, 0, 0.5f), TextureCoordinate = new Vector2(x1, y1) },
                new Vertex { Position = new Vector3(imageWidth, 0, 0.5f), TextureCoordinate = new Vector2(x2, y1) },
                new Vertex { Position = new Vector3(0, imageHeight, 0.5f), TextureCoordinate = new Vector2(x1, y2) },
                new Vertex { Position = new Vector3(imageWidth, imageHeight, 0.5f), TextureCoordinate = new Vector2(x2, y2) },
            });

            // 頂点バッファをアンロック
            _vertices.Unlock();
        }

        /// <summary>
        /// 描画する
        /// </summary>
        static void Render() {
            // 画面をクリアする
            _device.Clear(ClearFlags.Target | ClearFlags.ZBuffer, Color.Gray, 1.0f, 0);

            _device.BeginScene();

            // ビュー行列の設定
            // 画面の左上を原点とし、右方向にx軸、下方向にy軸が来るようにしている
            var view = Matrix.Identity;
            view.M22 = -1;
            view.M41 = -_width / 2.0f;
            view.M42 = _height / 2.0f;
            _device.SetTransform(TransformState.View, view);

            // 射影行列の設定
            // 正射影行列を指定して遠近感を消している
            var projection = Matrix.OrthoLH(_width, _height, -0.01f, 1.01f);
            _device.SetTransform(TransformState.Projection, projection);

            // テクスチャを描画
            RenderTexture();

            _device.EndScene();

            // 表画面に描画内容を転送
            _device.Present();
        }

        /// <summary>
        /// テクスチャを描画する
        /// </summary>
        static void RenderTexture() {
            // 左上の座標
            float x = 10, y = 10;
            // (x, y, 0)だけ平行移動
            _device.SetTransform(TransformState.World, Matrix.Translation(x, y, 0));

            // 描画する頂点バッファを指定する
            _device.SetStreamSource(0, _vertices, 0, Marshal.SizeOf(typeof(Vertex)));
            // 頂点バッファのフォーマットを指定する
            _device.VertexFormat = Vertex.Format;

            // テクスチャを指定
            _device.SetTexture(0, _texture);
            // カラー成分の設定
            _device.SetTextureStageState(0, TextureStage.ColorOperation, TextureOperation.SelectArg1);
            _device.SetTextureStageState(0, TextureStage.ColorArg1, TextureArgument.Texture);
            // アルファ成分の設定
            _device.SetTextureStageState(0, TextureStage.AlphaOperation, TextureOperation.SelectArg1);
            _device.SetTextureStageState(0, TextureStage.AlphaArg1, TextureArgument.Texture);
            // ブレンディングモードの設定
            _device.SetRenderState(RenderState.AlphaBlendEnable, true);
            _device.SetRenderState(RenderState.SourceBlend, Blend.SourceAlpha);
            _device.SetRenderState(RenderState.DestinationBlend, Blend.InverseSourceAlpha);

            // 描画する
            _device.DrawPrimitives(PrimitiveType.TriangleStrip, 0, 2);
        }

        /// <summary>
        /// アプリケーションのメイン エントリ ポイントです。
        /// </summary>
        [STAThread]
        static void Main() {
            var form = new RenderForm("SlimDX Texture Sample");
            form.ClientSize = new Size(_width, _height);
            InitializeDirect3D9(form);
            LoadTexture();
            MessagePump.Run(form, Render);
        }
    }
}

SimRank: A Measure of Structural-Context Similarity

"SimRank: A Measure of Structural-Context Similarity" という論文を読んだので内容をメモ。

• オブジェクトとオブジェクトの関係から類似度を測りたい
  • 関係というのは、例えば、論文の引用関係とか、Webページのリンク、被リンクの関係など
• 「2つのオブジェクトが関係しているオブジェクトが似ていれば、その2つのオブジェクトは似ている」と仮定
  • A, A', B, C という4つの論文があり、AはBを引用し、A'はCを引用しているとする。ここでAとA'が似ているとすると、BとCも似ているはず。
• SimRankというドメインに依らない尺度を導入して、類似度を測ってみる

モデル

2つのオブジェクト a, b に対して、類似度 s(a, b) を次のように定義する。

つまり、a, b の類似度は、a と b に入ってくる辺の始点のオブジェクトの類似度の平均を C 倍したものである。C は 0 から 1 の間の実数であり、類似性の減少率を表す。この定義が再帰的な定義であることに注意。s(a, b) は常に存在し、一意であることが示せる。

計算方法

ナイーブな方法

上の類似度の定義をすべての頂点の対に対して収束するまで反復的に計算する。

まず、次のように初期化する。

後は次の漸化式を使って更新していく。

この漸化式で k → ∞ とするとSimRankの類似度の式に一致する。実際には k = 5 ぐらいまで計算すれば十分であることが実験的に示されている。

枝狩り

グラフ上で遠いオブジェクトの類似度を 0 としてしまうことで計算量を減らせる。