COS類似度 - 小宮日記
文章の類似度を計算する場合などにCOS類似度というのが 使われるらしい。 二次元で考えた場合、ベクトルAとベクトルBの類似度は、 COS類似度＝AとBの内積/(norm(A)*norm(B))normは my $norm_1 = 0.0; map { $norm_1 += $_ ** 2 } values %{$vector_1}; $norm_1 = sqrt($norm_1);のように、ベクトルの要素をそれぞれ二乗して積算して、SQRTをとったもの。 二次元の場合は、norm([x,y])=sqrt(x^2+y^2)=距離ですね （このへんはボナメソのペナルティでもおなじみ。L1norm、L2norm） 内積をノルムで割ってるのは、正規化がかかるためのようです。 ベクトルによって長かったり、短かったりするでしょうから。 ベクトルとベクトルの間の角度が、類似度を表現するわけです。 内積は
bayonやCLUTOが爆速な理由 - download_takeshi’s diary
クラスタリングツールbayonを使っていて、常々「どうしてこんなに高速に処理できんのかなぁ」と疑問に感じていました。repeated bisectionという手法自体がk-means法などと比べると効率がいいのですが、それにしても、それだけでは説明がつかないほど爆速なわけです。 うまく例えられませんが、自前でk-meansのスクリプトを書いて比べてみると、自転車と新幹線くらいちがうという印象です。はじめてCLUTOを触った時、数万件程規模のクラスタリング処理が本当に「あっ」という間に終わってしまい、びっくりした記憶があります。 きっと実装面でなにか特殊なことがあるんだろうなと思い、mixiエンジニアブログでbayonの記事を改めて読み漁っていたら、以下の部分が目に止まりました。 このクラスタの評価は、クラスタの各要素とクラスタの中心とのcosine類似度の和としています。この和が大きいほど
人材獲得作戦の問題を反復深化深さ優先探索で - 簡潔なQ
人生を書き換える者すらいた。: 人材獲得作戦・４ 試験問題ほか 反復深化深さ優先探索は、深さ優先探索の深さのリミットを少しずつ増やしながら行う探索で、幅優先探索に近い性質をもつ探索。 ゲーム木のように浅くて広い探索木の場合にメモリ効率が良く好まれる。 再帰で書けるので幅優先よりシンプル。 #include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; string maze; vector<int> depths; size_t w; bool search(int x, int depth) { if(depth<=depths[x])return false; depths[x]=depth; if(maze[x]=='*')return false; i
人材獲得作戦の問題をWarshall-Floydで - 簡潔なQ
人生を書き換える者すらいた。: 人材獲得作戦・４ 試験問題ほかを今度はWarshall-Floydで解いてみた。 Dijkstraが特定の2点間の最短経路を求めるのに対して、Warshall-Floydは全ての2点間の最短経路を一括で求める。 またWarshall-Floydの良い点として、負辺の処理および負閉路の検出も可能ということが挙げられる。 負辺に対応した単一始点最短経路探索のBellman-Fordというのもあるようだけれど、Warshall-FloydのオーダーがO(|V|^3)なのに対してBellman-FordはO(|V||E|)らしいので、ある程度疎でない限りWarshall-Floydでいいんじゃないかな。 効率は悪いが、まあWarshall-Floydの練習ってことでどんまい。綺麗だし。 #include <iostream> #include <string> #i
もっと高速に－線分交差判定－
線分交差判定といっても、すべての与えられた線分に対して、同様な計算を 行って判定していたのでは、無駄が多いように見えます。場合によっては もっと単純な軽い判定で行えるはずです。そこで、 『場合分けによるラフチェック』を もっと簡単に－線分交差判定－のプロシージャ に追加して、次のように変更します。 '構造体 Private Type POINT x As Double y As Double End Type '座標 p1,p2 を結ぶ線分と座標 p3,p4 を結ぶ線分が交差しているかを調べる 'ただし、線分が重なっている場合(3点,4点が一直線上にある)、「交差している」、と判定します。 Private Function intersectionEX(p1 As POINT, p2 As POINT, _ p3 As POINT, p4 As POINT) As Boolean 'x座標
もっと簡単に－線分交差判定－
ここでは、線分交差判定の定石ともいえる方法を紹介しています。 線分と直線の見落としがちな大切な定義です。
Bayesian Setsによる関連文書検索システムStupa - mixi engineer blog
都会よりも田舎が好きなfujisawaです。Bayesian Setsというアルゴリズムを使って、関連する文書を高速・高精度に検索できるシステムを作成しましたので、そのご紹介をさせていただきます。 Bayesian Setsとは Bayesian Setsはいくつかアイテムを入力すると、それを補完するようなアイテムを返してくれるアルゴリズムです。原著論文の先頭に"Inspired by Google Sets"と書かれているように、Google Setsを参考にして作成されています。実際にどのような出力が得られるか、Google Setsに以下の表のクエリを検索して試してみますと、 クエリ 出力 apple, banana chocolate, strawberry, vanilla, cherry, ... apple, macintosh software, windows, mac,
トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター
トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター：最強最速アルゴリズマー養成講座（1/4 ページ） プログラミングにおける重要な概念である「探索」を最速でマスターするために、今回は少し応用となる探索手法などを紹介しながら、その実践力を育成します。問題をグラフとして表現し、効率よく探索する方法をぜひ日常に生かしてみましょう。 まだまだ活用可能な探索 前回の「知れば天国、知らねば地獄――『探索』虎の巻」で、「探索」という概念の基礎について紹介しました。すでに探索についてよく理解している方には物足りなかったかと思いますが、「問題をグラフとしてうまく表現し、そのグラフを効率よく探索する」というアルゴリズマー的な思考法がまだ身についていなかった方には、得るものもあったのではないでしょうか。 前回は、「幅優先探索」と「深さ優先探索」という、比較的単純なものを紹介しましたが
チームラボ / teamLab
森ビル デジタルアート ミュージアム：エプソン チームラボボーダレス Feb 09, 2024 - 麻布台ヒルズ、東京 NOW OPEN
第7回 転置索引の構築 | gihyo.jp
はじめに これまで、転置索引の構造や具体的なデータ構造を見てきました。今回は、検索したいテキスト文書から、どのようにこの構造を構築するかを説明していきます。 ディスクベースの構築方法 第3回では、表を作成しそれを転置させることで転置索引を構築しました。実際にコンピュータに処理をさせる場合も、メモリ上の2次元配列で同様に構築することが可能となります。しかし、通常の転置索引は非常に疎な表となるため、この方法ではメモリを使いすぎてしまいます。また、リンクリストなどのメモリ上でのデータ構造を用いることにより、上記の方法と比較して少ないメモリ量で構築することもできます。 これらの方法はいずれも、対象とする文書集合を変換した転置索引が実メモリに収まる場合にのみ可能となる方法となります。しかし多くの場合、転置索引は実メモリよりも大きくなります。そのような場合はディスクを用いた構築方法が必要となり、効率的
【SEOリサーチ】本文のテキストが鍵を握る！ Yahoo!検索アルゴリズム2009年12月更新分の調査レポート
『MarkeZine』が主催するマーケティング・イベント『MarkeZine Day』の 最新情報をはじめ、様々なイベント情報をまとめてご紹介します。 MarkeZine Day
Mipmap - Wikipedia
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Mipmap" – news · newspapers · books · scholar · JSTOR (June 2009) (Learn how and when to remove this message) In computer graphics, a mipmap (mip being an acronym of the Latin phrase multum in parvo, mea
B-tree and UB-tree - Scholarpedia
The B-tree is a dynamic high performance data structure to organize and manage large datasets which are stored on pseudorandom access devices like disks, (Bayer and McCreight 1972). The UB-tree is a multidimensional generalization of the B-tree. Invented in 1969, B-trees are still the prevailing data structure for indexes in relational databases and many file systems (Comer 1979), (Weikum and Voss
その13 OBBとOBBの衝突
ホーム＜ゲームつくろー！＜衝突判定編＜ OBBとOBBの衝突 3D衝突編 その13 OBBとOBBの衝突 衝突の本丸の1つ「OBBとOBB」の衝突です。大きさの違うお互いに3次元的に回転した直方体が衝突しているかどうかを調べるというのはやはり簡単ではありませんが、これができると多種多様な方面で役に立ちます。OBB同士の衝突として主流なのは「分離軸判定」と呼ばれる方法でして、ここでもそれについて見ていきます。ちょっと深呼吸してご覧下さい(^-^; ① 「分離軸」判定とは？ OBBの衝突には「分離軸」という物が登場します。これがいったい何なのか？まずは下の図をご覧下さい。 上のOBBは明らかに衝突していません。この時、両方のOBBを分ける直線が「絶対に」存在します。この直線は、ちょっと小難しい言葉で言うと分離超平面（Separating hyperplane）と呼ばれています。直線なのに平面と
scale out の技術 (in UNIX magazine, April 2009)
scale outの技術 首藤 一幸 Last-updated: January 5, 2010 注: このページの文章は以下の記事の元原稿です。 首藤一幸, "スケールアウトの技術", クラウドの技術, pp.88-101, (株)アスキー・メディアワークス, ISBN978-4-04-868064-6, 2009年 11月 6日 アスキー・メディアワークス社の 書籍紹介ページ Amazon.co.jp の ページ 首藤一幸, "スケールアウトの技術", UNIX magazine 2009年 4月号, pp.78-91, (株)アスキー・メディアワークス, 2009年 3月 18日 データベースに求められる性能を試算したところ、 十台、百台…数万台のサーバが必要になった。 クラウドを構築する側はこういう問題に直面し、解決しようとしてきた。 台数に比例した性能を引き出すこと、つまりsca
key-valueストアの基礎知識
首藤 一幸 Last-updated: January 5, 2010 注: このページの文章は Software Design 誌 2010年 2月号に掲載された以下の記事の元原稿です。 Software Design 誌編集部の了承の元に、本ウェブページに掲載しております。 首藤一幸: "key-valueストアの基礎知識", Software Design 2010年 2月号, p.14-21, (株)技術評論社, 2010年 1月 18日 クラウド、特にPaaS向けのソフトウェア開発が現実のものとなり、 そこではリレーショナルデータベースとは違ったデータベースが 勢いを増しています。 その代表であるkey-valueストアを解説します。 もくじ key-valueストアとは なぜkey-valueストアか key-valueストアの使いどころ key-valueストアとNoSQLの
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
NWB Community Wiki : Fruchterman-Rheingold browse
グラフ描画入門 - Wolfram Mathematica
ネットワーク構造の可視化
Summed-Area Tables And Their Application to Dynamic Glossy Environment Reflections