朝日新聞デジタル：プロ野球日程を瞬時に計算 数学者がソフトを開発 - スポーツ
プロ野球の移動距離を短くする計算例 【藤島真人】１カ月以上かかるプロ野球の日程づくりが、あっという間にできるソフトウエアを数学者が開発した。日程を工夫するだけで、球団の移動距離を２割以上減らすこともできるという。シーズン開幕を控え、彼らの計算式と現実とのギャップはいかに。 開発したのは、国立情報学研究所の河原林健一教授と星野リチャード・前外来研究員。２人は効率の良い鉄道網や電気回路の設計などにも応用できる「グラフ理論」と呼ばれる分野の研究者だ。 ソフト開発は、３年前の３月、カナダからリチャードさんが来日し、たまたま千葉ロッテの本拠地の近くに住んだことがきっかけ。鉄道網のような「グラフ」を球団の移動に置き換え、最適な日程をはじき出せないかを考えた。 続きを読むこの記事の続きをお読みいただくには、会員登録が必要です。登録申し込みログインする（会員の方） 無料会員登録はこちら朝日新聞デジタ
定期的に繰り返し実行する簡単ではないお仕事 - やねうらおブログ(移転しました)
いやー、この問題は本当に難しい。難しすぎて、どうやって解決すればいいかいまだによくわからない。わからないので、ここに書いてみる。 最初、とあるお客さんのために「ひよこの餌やりプログラム(仮)」を作っていたんだ。開始ボタンを押すとひよこの餌が出てくる。たったそれだけのプログラム。 今回は、これを「定期的に実行する機能が欲しい」と言われた。 この要望を実現するのがすこぶる難しかったんだ。 「やねうらおってそんなプログラムすら書けないの？老害なの？」 とか言わないで欲しい。この問題、本当に難しいんだよ！ ■ １度目のひよこの全滅 まず、この要望に沿って、私の会社のプログラマが当初、次のようなダイアログをつけたわけだ。 繰り返し実行のところにチェックを入れた場合、ここで指定された時間後にも繰り返し実行する。単位は分で指定する。1日ならば60×24 = 1440を指定する。そうすると、ひよこの餌やり
データマイニングで使われるトップ10アルゴリズム - データサイエンティスト上がりのDX参謀・起業家
2006年のデータマイニング学会、IEEE ICDMで選ばれた「データマイニングで使われるトップ10アルゴリズム」に沿って機械学習の手法を紹介します（この論文は@doryokujin君のポストで知りました、ありがとうございます！）。 必ずしも論文の内容には沿っておらず個人的な私見も入っていますので、詳細は原論文をご確認下さい。また、データマイニングの全体観をサーベイしたスライド資料がありますので、こちらも併せてご覧下さい。 データマイニングの基礎 View more presentations from Issei Kurahashi 1. C4.5 C4.5はCLSやID3といったアルゴリズムを改良してできたもので、決定木を使って分類器を作ります。決定木といえばCARTが良く使われますが、CARTとの違いは以下のとおりです。 CARTは2分岐しかできないがC4.5は3分岐以上もできる C
Flashでグニグニ曲がるUIを作る方法 - しっぽのブログ
前にtwitterアイコンやpixivの画像をプヨプヨすることのできるpuyopixというコンテンツを作りました。 Puyopix -プヨプヨにするよ- このページの右上にあるブログパーツもこれです。 解説をやると言っておいて、ずっと書いていなかったので書きます。 あんまりコードだらけにしても面白くないし、方法の概念的なものを図を交えながら説明していきます。 画像をプヨプヨする方法の概要と、それをUIに応用する方法です。 プヨプヨの実装 骨組みを作る 格子状バネという、わりと普通の実装をしています。 格子状に並んだ各点をばねのように接続します。 バネはお互いの点の距離が一定になるように、２つの点に逆方向の力をかけます。 フックの法則というのがあって、「F = -kx」とかいう式もありますが、プログラムとしての感覚は「本来あるべき距離の方向へ、ズレた分の○%だけ加速度をつける」って感じになり
yebo blog: クヌース教授は間違っていた
2010/06/15 クヌース教授は間違っていた Slashdotによれば、この数十年間、クヌース教授をはじめとするコンピュータ科学者が最適としてきたアルゴリズムを10倍高速にする方法をPoul-Henning Kamp (PHK) というハッカーが見付けたという。その論文タイトルは「You're Doing It Wrong (あなた達のやっている事は間違っている)」で、ACM Queueに掲載されている。別にクヌース教授の考えが間違っているわけではなく、アルゴリズム的には正しいが、実用レベルでは、OSには仮想メモリがあり、VMと干渉しないようにすれば簡単に高性能なシステムが作れる。従来の考え方はモダンな計算機を考慮に入れていないので、現実的には不適合を起こしている。具体的にはヒープにBツリーの要素を取り込んだBヒープというデータ構造を使うことで、バイナリヒープの10倍のパフォーマンスを
iVoca の履歴から単語の難易度を計算 - 木曜不足
まずは iVoca のデータを使って自分で IRT で計算してみるところからかな。 というわけで、ユーザの学習履歴から単語の難易度を求めるコードを書いてみた。 ソーシャルっぽい！ 残念ながら IRT(項目反応理論) について書かれた文献を持っていないのだが、id:niam さんの SocialDict についてのプレゼン資料 のおかげで、「２値のラッシュモデル＋逐次勾配降下」なら単純なロジスティック回帰であることがわかるので、簡単に実装できた。 しかも IRT の特徴ベクトルが疎であることを用いると、非常にシンプルなコードで済む。 # data には [ユーザID, 単語ID, 知ってる(1)/知らない(0)] を格納。 # users/words は各IDをキー、重み(ユーザの語彙力/単語の難しさ)を値とするHash 100.times do |k| eta = 1.0 / (k + 1
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意していま
PHPを使うなら理解しておきたいアルゴリズム - 抽出・ソート・結合・集計 - いろいろ解析日記
PHPでのアルゴリズムの書き方の覚書です。 目次 説明に使用するデータ構造 抽出 ソート PHPでの配列のソート ソートの例(五十音順) ソートの例(数値順) 結合 集計 関連記事 説明に使用するデータ構造 アルゴリズムの説明のために、以下のような配列の配列を使います。 $countries = array(); $countries= array( name => "日本", currency => "JPY", population => 127156000 ); $countries= array( name => "フランス", currency => "EUR", population => 65073482 ); $countries= array( name => "スペイン", currency => "EUR", population => 44904000 ); $co
どのようにして一番右の1のビット位置を求めているのか？ - ザリガニが見ていた...。
一番右端の立っているビット位置を求める「ものすごい」コード - 当面C#と.NETな記録 「ものすごい」コードなのだけど、凄過ぎて自分には全くチンプンカンプン...。それでも、どの辺が凄いのか、ちゃんと理解したい。シンプルなコードから順を追って確かめてみた。 public static int GetNumberOfTrailingZeros( long x ) { if ( x == 0 ) return 64; ulong y = ( ulong ) ( x & -x ); int i = ( int ) ( ( y * 0x03F566ED27179461UL ) >> 58 ); return table[ i ]; } static int[] table; table = new int[ 64 ]; ulong hash = 0x03F566ED27179461UL; for
適切なクラスタ数を推定するX-means法 - kaisehのブログ
K-means法によるクラスタリングでは、あらかじめクラスタ数Kを固定する必要があります。HatenarMapsでもK-means法を使っているのですが、クラスタ数は（特に根拠もなく）200個に決め打ちになっていました。 これに対して、X-means法というK-means法の拡張が提案されていることを知りました。X-means法を使うと、データに応じて最適なクラスタ数を推定できます。 K-means and X-means implementations http://www-2.cs.cmu.edu/~dpelleg/download/xmeans.pdf X-means法の考え方は、K=2で再帰的にK-means法を実行していくというもので、クラスタの分割前と分割後でBIC（ベイズ情報量規準）を比較し、値が改善しなくなるまで分割を続けます。 調べたところ、Javaのデータマイニングツー
ジャンル別ゲームの作り方とアルゴリズムまとめ - ネットサービス研究室
ゲームの作り方とアルゴリズムをジャンル別にまとめてみました。ゲーム制作や、プログラミングの勉強用にご活用ください。言語別ゲームプログラミング制作講座一覧もあわせてお読みください。 リンク切れがおきていたものは、URLを表示しておくので、Internet Archiveなどでキャッシュを表示させてみてください。 RPG ゲームの乱数解析 乱数を利用した敵出現アルゴリズムの解説 各種ゲームプログラム解析 FF、ドラクエ、ロマサガのプログラムの解析。乱数の計算など ダメージ計算あれこれ（http://ysfactory.nobody.jp/ys/prg/calculation_public.html） ダメージの計算式 エンカウントについて考えてみる エンカウント（マップでの敵との遭遇）の処理方法いろいろ RPGの作り方 - ゲームヘル2000 RPGのアルゴリズム ドルアーガの塔 乱数の工夫の
論文 頻出パターン発見アルゴリズム入門 － アイテム集合からグラフまで －
2024.07.12： 【お知らせ】次世代のための2024年夏AIセミナー 第1～3回参加申込者の皆さんへ →詳細 2024.07.09： 【お知らせ】次世代のための2024年夏AIセミナー 第1, 2回講座参加申込延長等 →詳細 2024.07.04： 【締切延長】第1回スマートマニュファクチャリングとシステム健全性管理研究会（SIG-SMSHM），2024/07/30 ハイブリッド，2024/07/12 申込締切 →詳細 2024.07.01： 【記事更新】私のブックマーク「空間統計と無線通信」 →詳細 2024.07.01： 【会誌発行】人工知能学会誌 Vol.39 No.4 (2024/7) →詳細
テキストからの評判分析と 機械学習
テキストからの評判分析と 機械学習 鍜治伸裕 東京大学 生産技術研究所 講演の前に • 想定している聴衆 – 評判分析について専門的なことを知らない – 機械学習（ML）の素養を持っている • 講演の内容 – 評判分析という分野の解説 – 評判分析における ML の適用事例の紹介 • お断り – 自然言語処理(NLP)の話に特化 – ML を使っている論文を私の好みで選んで紹介 評判分析を概観する 評判分析はこんな技術 • 例： Yahoo!ブログ検索における「VAIO」の検索結果 肯定的評判と否定的評判の 書き込み数を集計して表示 肯定的な書き込みと否定的 な書き込みを分類して提示 背景: CGMの出現 • CGM – Consumer Generated Media のこと – 例えば Amazon に投稿されたレビューやブログなど – 一般人が作成，発信するコンテンツである点がポイン
フォント同士を交配させて新しいフォントを作る「genoTyp」が面白い - てっく煮ブログ
「この発想はなかった！」と驚いた。genoTyp はフォント同士を交配させて新しいフォントを生み出す実験サイトだ。早速、試しにやってみた。1. 第一世代の親を決めるgenoTyp を開いて左上の [Breed] タブをクリックすると「交配ページ」が表示される。[add original font] ボタンをクリックして、祖先となるフォントを２つ追加してみた。交配させるために２つのフォントをドラッグしてくっつけた。くっついた状態になれば交配の準備は完了だ。2. 交配させてみる中央の [cross] ボタンを押すと第一世代が誕生する。４人の子供が誕生した。父親似だったり、母親似だったり、子供によって雰囲気が異なっている。3. 第一世代でも交配別の [original font] を追加させて、第一世代の中から気に入ったものと交配させてみた。３人の子供が第二世代に誕生した。4. さらに交配！今度
レコメンデーションとエディットグラフ
レコメンデーションとエディットグラフ：コーディングに役立つ！ アルゴリズムの基本（10）（1/4 ページ） プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか（編集部） 実際のアプリケーションで使われるアルゴリズム これまで見てきたアルゴリズムは、実際のアプリケーション開発の際にそのまま使われることはあまりなく、プログラム言語やライブラリなどですでに機能が用意されているものが大半でした。 今回は最終回ということで、実際のアプリケーション開発でそのまま使えるものを紹介したいと思います。 レコメンデーション ECサイトで、「あなたにお勧めの商品」を表示していることがあります。いろいろなデータベースや行動履歴のデータから、その人ごとにお勧めの商品をはじき出して推薦する機能をレコメンデー
「確率モデルによるwebデータ解析法」8章メモ - <s>gnarl,</s>技術メモ”’<marquee><textarea>￥
昔書いたやつを発掘してきた。また読み返す必要があるなー。 8章は商用アプリケーションの話、レコメンダシステムと顧客行動解析。 ここで扱うレコメンダシステムは、ユーザの行動履歴に基づきユーザに対してアイテムを推薦するようなもの。 興味深い問題として、欠損をすべて0と考えた場合、ユーザiがチェックしなかった項目jに関する行列V中の欠損地の扱いがある。これら欠損データは、必ずしも完全にランダムに欠損しているわけではなく、ユーザが好まない項目に対して「どちらかといえば選ばない」という負のバイアスが 影響していると思われる(Breese,J.S.,Heckerman,D. and Kadie,C. 1988 Empirical analysis of predictive algorithms for collaborative filtering.)。リコメンダシステムに関する多くの研究において、
Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
アルゴリズムイントロダクション輪講 動的計画法の発表資料 - てっく煮ブログ
2009年3月2日に、はてな京都オフィスで開催された アルゴリズムイントロダクション輪講 の第12回で「動的計画法」について発表しました。資料をここにおいておきます。View more presentations from nitoyon.分かりやすくしようと気合を入れてまとめたら165ページの大作になっちゃいました。無駄に長くてすいません。アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)作者: T.コルメン, R.リベスト, C.シュタイン, C.ライザーソン, Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, Charles E. Leiserson, 浅野哲夫, 岩野和生, 梅尾博司, 山下雅史, 和田幸一出版社/メーカー: 近代科学社発売日: 2007/03メディア: 単行本
Introduction to Information Retrieval #18 の復習資料 - naoyaのはてなダイアリー
Introduction to Information Retrieval 輪読会 18章の復習資料を以下にアップロードしました。 http://bloghackers.net/~naoya/iir/ppt/iir_18.ppt 18章のテーマは "Matrix decompositions and latent semantic indexing" で、行列の特異値分解と Latent semantic indexing (LSI, 潜在的意味インデキシング) でした。ベクトル空間モデルの核である単語文書行列を特異値分解を用いて低階数近似し、計算量を下げながらも*1適合度を向上させるという LSI についての解説の章です。LSI に関しては http://d.hatena.ne.jp/naoya/20090212/latent_semantic_indexing にて先日少し言及しました
JavaでTrieデータ構造を実装する
WEB+DB PRESS vol.42の特集「アルゴリズム＆データ構造」でもとりあげられていたTrie(とらい; p34-37)について調べてみたので、忘れないようにメモです。 Trie(s)というのは単語を辞書のなかから見つけ出すときに人がふつうに行っている探し方のアルゴリズムです。例えば、poolならまず、pのところに行って、次にoのところに行って、、、つまり、p -> o -> o -> lと探していきます。続いてprizeを見つけるとしたら、p -> r -> i -> z -> eですが、先頭の文字が同じpなので、pの付近からはずれたところから始めたりはしません。この二つの単語の場合pをprefixと見なすのがTrieです。poolとpoleだったらprefixはpoにのびていきます。prefixがのびていけばいくほど候補は減っていきます。ちょうどIDEのメソッド補完機能のように
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
