約 1,512,080 件
https://w.atwiki.jp/wiki15_kiki/pages/156.html
https://w.atwiki.jp/dooooornob/pages/36.html
分散の別表記 突然ですが、次のような公式（？）が成り立ちます。 見ると嫌な気持ちになる式ですが順を追えばそうむずかしいことはないです。 はそれまでの通り平均値です。ですので右辺はとも書けますね。 それでもの中身がエライことになってることですが、要するに平均というのは 「ある確率変数の総和を、個数で割ってください」 ということなので、をについて全部足して、その個数で割ってやればいいのです。これを式で書けば 何のことはない、分散の定義式ですね。よって式(1)が成立することが分かります。 二つの確率変数の「類似度」を表す量 前項までは「ある生徒」に対して「一つの点数」が決まっていました。 ここで、中間テストなんかだと色んな教科のテストを受けますよね。 例えばある生徒の「数学の出来具合」と「英語の出来具合」には相関があるんだろうか、ということを調べたい場合。 つまりある教科が得意な生徒は他の教科も同様に得意なんだろうかということを調べたい場合、次のような共分散という量を使い評価します。 これも前の節の説明を踏まえて考えてみます。 いわば「出来具合」みたいなものは平均からの差で分かるわけです。 つまり、確率変数－例えば数学の点数－の「出来具合」はで表せるということです。同様に確率変数についてはですね。 この数字が相関しているかどうかの「相関度」はこれらを掛け算してやればわかりそうです。例で考えましょうか。 例えばが平均より+1点、が平均より+2点だったとすれば、相関度は+2ですね。この人は数学も英語もやや良いようです。 次にが平均より+10点、が平均より+20点だったとすれば相関度は+200。スゴイ相関です。 逆に、が平均より-20、が平均より-10だったとすれば相関度は+200。両方とも悪いっていう残念な相関性です。 対して、が平均より+10だったのに、が-10点だった、つまり「似ていない」というような場合の相関度は-100ですね。 このような逆向きの相関のことは負の相関といいます。 バラつきと違って、「傾向が似ている」「傾向がない」「逆の傾向がある」という意味で正と負の方向があるのに注意してください。 さ～てこんな感じで5番目の人の相関度、6番めの人の相関度を足していけば全体的な傾向が得られそうですね。つまり という式で２つの確率変数の「類似度」が表せそうです。これが共分散ですね。 分散と共分散の式の類似性 式(1)と式(2)、実はよく似ています。式(1)の2乗を展開してこんな感じにするともっとわかりやすいでしょうか。 つまり、分散はその確率変数自身との共分散ということになるでしょうか。 分散共分散行列 さあさあ、今までは2つの確率変数とについて考えてきましたが次はもっと拡張して個の確率変数についての情報を統括したようなものを考えてみます。 それが次の分散共分散行列Cです。 ただし、です。こいつは各成分が確率変数同士の共分散の形になっていますね。ただし、対角成分は同じ確率変数の共分散、つまり分散になっていることに注意しましょう。 だから、「分散」共分散行列といいます。
https://w.atwiki.jp/dooooornob/pages/20.html
アルゴリズムとは？ あるデータを集めてきて統計学者さんなんかに見せるとそこから色々な情報を提供してくれます。 ではこれが「学者」みたいな人ではなく、手続き―つまり、このようにすれば持ってきたデータから所望のデータを得られるという手順―のことをアルゴリズムと言います。 以下では種々の用語を定義していきます。 1)入力(input)・・・アルゴリズムに与えるデータのこと。学者の例で言えば集めたデータ。 2)出力(output)・・・アルゴリズムから得られるデータ。 3)入力の大きさ(input size)/問題の大きさ(problem size)・・・与える入力データの数のこと。 アルゴリズムの優劣 入力をいれて出力を取り出すこの「アルゴリズム」というのは非常に広範な概念です。 たとえば、「１～１００までの数を入力して、その合計を出力する」といったようなアルゴリズムを考えることができます。 さて、これを解くための最も堂々たる単純な方法はすべて足しあげることですね。 1+2+3+…=？ 少なくとも手計算で流行りたくないですね。これを簡単に計算する方法として有名（？）な次の方法があります。 1)一番小さい数と一番大きい数を足し合わせる。この和をXとする。(この場合 X=1+100=101) 2)この数は「k番目に小さい数とk番目に大きい数を足し合わせた数」として一般化できる。(例えばk=3ならば 3+98=101でXと同じ数になる) 3)よって、入力の数nの半分 n/2 個の組み合わせの和がすべて1)で求めた数Xになるので、が求める答えになる。(n=100なので、101×100/2=5050が答え) さて、初めの地道に足し合わせる方法と、上の方法、どちらが「優秀」なアルゴリズムかというのは言うまでもないと思います。 このように、ある結果を求めるためにどの程度計算が必要なのか、という指標を計算量と言います。 オーダーという概念 前節のことをまとめれば「計算量が少ないほど、そのアルゴリズムは優秀」ということになります。 しかし、たとえば「4個の数を地道に足しあげる」のか「5000個の数を『優秀』な方法で足しあげる」のか、どちらが早いかといわれるといくら「優秀」なアルゴリズムでも負けてしまいそうです。 直感的にも明らかですが、アルゴリズムの計算量というのは入力の数nが増えれば増える程増加する場合がほとんどです。 （nが増えても計算量が変わらないことはありますが、少なくとも計算が簡単になることはないでしょう。） ですからただ単に計算量が多いか少ないかではなくて、「nが増えることによってどの程度計算量が大きくなるのか」ということで考える方が、よりいい指標になりそうです。 そこで次の定義があります。 [定義]関数および任意の実数$a$に対して が成立しているとき と表記する。またfはgで押さえられているといったり、fはgのオーダーであると言ったり。 さらに、ここで使われた記号のをランダウの記号と言います。 要するに「単純に計算量だけで比較しちゃダメ」だということだから、入力に対する「関数」と比較してしまえ、ということです。 複雑度 さて、今までは計算量だけで物事を考えてきましたが、計算機でアルゴリズムを動かす時にはもう一つ『容量』の概念が重要です。 入力nが増えるにしたがって爆発的にメモリを食ってしまうような計算はいくら早くても稼働させることができないからです。 ここで以上の２つのアルゴリズムに関する指標、計算量のオーダーの事を時間複雑度(time complexity)、記憶容量のオーダーのことを空間複雑度(space complexity)と言います。 またこれらを合わせて複雑度(complexity)といいます。
https://w.atwiki.jp/wiki15_kiki/pages/68.html
https://w.atwiki.jp/wiki15_kiki/pages/353.html
https://w.atwiki.jp/dooooornob/pages/28.html
3次元凸包 という点が3次元空間に点在しているとします。 またの座標はという風に指定します。 ここで、「の凸包を求めよう」というのが今回の主題です。 点の数が多い－つまりの数が多い－ことを想定して、分割統治法による解法を試みます。 1)をx座標の大きいとx座標の小さいに分割します。 2)それぞれとについて、再帰的に凸法を作ります。 3)それらを統合します。 さて、1)2)のプロセスはいいでしょう。問題は3)のプロセス－つまり、分割した凸包をどうくっつけて凸包にするか－です。 3次元凸包の統合 用語の定義をしましょう。図を見てもらうと棒人間が立っています。この人が色々な頂点から向こう側の3次元凸包を観察してみることができる三角形を灰色に塗りました。 言い換えれば、反対側の凸包からみて「オモテ側」の三角形ですね。 このオモテとウラの境目（図で赤い点線にしたところです。）をシルエットサイクルと呼ぶことにします。 これら2つの三次元凸包を統合したくば、「片方の凸包のシルエットサイクルに属す頂点」と「もう片方の凸包のシルエットサイクルに属す辺」で三角形をつくります。 こいつを接着剤代わりにして２つの凸包を繋ぐのです。この三角形を橋渡し三角形と言います。 ということで3次元凸包は結局橋渡し三角形を見つける問題に帰着されるわけです。
https://w.atwiki.jp/wiki15_kiki/pages/50.html
https://w.atwiki.jp/wiki15_kiki/pages/302.html
https://w.atwiki.jp/wiki15_kiki/pages/196.html
https://w.atwiki.jp/wiki15_kiki/pages/157.html