自力で生成したデータポイントに対して自力でクラスタ分割してみる

ドキュメントを読んで使ったことが無い機能に詳しくなるシリーズ。 今回は検索最適化サービス(Search Optimization Service)。 他のドキュメントと比較して英語・日本語ともに文体が異なる気がする。 日本語訳が変なのではなく、元の英文の文体が違う。 まず、\"クラスタリング\"とか\"Materialized View\"が構造の名称である一方で、 \"検索最適化\"が目的の名称となっている点に違和感を感じる。 似て非なる索引(index)とは違うのだよ、という何かなのだろうか... [arst_toc tag=\"h4\"] 検索最適化サービスの概要 検索最適化サービスは、1つまたは少数の異なる行のみを返す「ポイントルックアップクエリ」。むむ?。 要は、巨大なテーブルに対するSELECT文の結果が数行となるようなケースを高速化する。 例えば、あるテーブルのageというカラムに対する等価条件を設定したクエリを速くしたい場合、 あらかじめ高速化用のデータ構造を構築し、ageに対する等価条件を使ったクエリを高速化する。 等価条件検索、範囲条件検索、部分文字列検索に加え、 プレビュー機能として、正規表現検索、半構造化型値検索、地理空間関数検索 が用意される。 他の高速化技術との比較 高速化機能として、他にクラスタリング、Materialized Viewがあるが、それぞれ機序が異なる。 クラスタリングは、マイクロパーティションの分散と枝刈りを利用した方法であって、 ナチュラルキーよりも高いプルーニング効率が得られるケースに適用する。 Materialized Viewは、同一テーブルに対して複数のクラスタリングキーを透過的に適用する 用途で用いられる。もちろん直アクセスでは遅い場所の事実上のキャッシュとしても使う。 検索最適化サービスは、ある意味、RDBMSの索引チックな使い方ができる。 良く使うカラムと検索述語を「アクセスキー」として登録し、高速検索用の索引を構築する。 検索最適化サービスの構成に必要な権限 以下の権限が必要。 テーブルの所有権 テーブルを含むスキーマに対する ADD SEARCH OPTIMIZATION 権限 検索最適化サービスを適用したテーブルにアクセスするには普通にSELECTできれば良い。 検索最適化サービスで未サポートのもの 以下に対して検索最適化サービスを適用することはできない。 (逆に以下以外なら適用できる。) 外部テーブル マテリアライズドビュー COLLATE 句 で定義された列 列の連結 分析表現 テーブル列にキャスト（文字列にキャストされる固定小数点数を除く） Materialized Viewは外部テーブルアクセスを高速化できるが、 検索最適化は外部テーブル、Materialized Viewを対象に出来ない。 何かの事情でCOLLATE句を指定した場合、その列は使用できない。 述語を指定する際に、定数側の明示的キャストはサポートされるが、 列側をキャストすると効かなくなる。例えば以下のような違いがある。 ただし、NUMBERからVARCHARへのキャストだけは機能する。 -- 機能する SELECT hoge FROM table as t1 WHERE timestamp1 = \'2020-01-01\'::date; -- 機能する SELECT hoge FROM table as t1 WHERE cast(numeric_column as varchar) = \'2\' -- 機能しない SELECT hoge FROM table as t1 WHERE to_date(varchar_column) = \'2020-01-01\'; (分析表現って何!?) 検索最適化サービスの構成方法 ALTER TABLE と ADD SEARCH OPTIMIZATION を使用する。 テーブル全体(つまり全カラム)に対して適用できるか、カラムを指定することもできる。 カラムを指定する場合、ON句に最適化したい検索述語等を指定する。 例えば以下であればc1,c2列を使用した等価述語が最適化される。 c1列、c2列に対して等価述語(=)を使ったSQLが高速化される。 -- t1テーブルの c1,c2 の等価述語に対して検索最適化を適用 ALTER TABLE t1 ADD SEARCH OPTIMIZATION ON EQUALITY(c1,c2); -- クエリ SELECT hoge FROM t1 where c1 = 100 and c2 = 200; 検索最適化サービスが適用済みか確認する方法 DESCRIBE により該当テーブルへの検索最適化サービスの適用状況を確認できる。 定義した「検索アクセスパス」の詳細と、有効無効が表示される。 DESCRIBE SEARCH OPTIMIZATION ON t1; +---------------+----------+--------+------------------+--------+ | expression_id | method | target | target_data_type | active | +---------------+----------+--------+------------------+--------+ | 1 | EQUALITY | C1 | NUMBER(38,0) | true | +---------------+----------+--------+------------------+--------+ テーブル全体に対して検索最適化サービスを適用していた場合、 列の追加により、追加した列に対して自動的に検索最適化サービスが適用される。 逆に列の削除により、削除した列が検索最適化サービスから除外される。 列のデフォルト値を無効にすると、検索最適化サービスが「無効」になる。 一度「無効」になってしまったら、SEARCH OPTIMIZATION を一度 DROP し、 再度 ADD しなければならない。 検索最適化サービスのコスト 以下のコストがかかる。 ストレージリソース コンピューティングリソース ストレージリソース 検索アクセスパスのためのデータ構造を構築するために使われる。 通常、元テーブルの1/4ぐらいのサイズになるらしい。 ただし、テーブル内の個別の値の数が多ければ多いほどストレージを消費する。 例えば、全カラムを対象としている場合、全カラムの値が全て異なるという状況は最悪で、 元テーブルと同じだけのストレージを消費してしまう。 コンピューティングリソース 検索最適化を維持するためにコンピューティングリソースが使われる。 テーブル内で大量のデータが変更される場合、リソースの消費量が激しくなる。 追加・変更に比例して大きくなる。削除は若干使用する。 ざっくり以下に比例してコストが増加する。 この機能が有効になっているテーブルの数、およびそれらのテーブル内の個別の値の数。 これらのテーブルで変更されるデータの量 SYSTEM$ESTIMATE_SEARCH_OPTIMIZATION_COSTS 関数によりコストを見積もれる。 -- テーブルに検索最適化を追加する場合の推定コスト select SYSTEM$ESTIMATE_SEARCH_OPTIMIZATION_COSTS(\'TABLE_WITHOUT_SEARCH_OPT\'); +---------------------------------------------------------------------------+ | SYSTEM$ESTIMATE_SEARCH_OPTIMIZATION_COSTS(\'TABLE_WITHOUT_SEARCH_OPT\') | |---------------------------------------------------------------------------| | { | | \"tableName\" : \"TABLE_WITHOUT_SEARCH_OPT\", | | \"searchOptimizationEnabled\" : false, | | \"costPositions\" : [ { | | \"name\" : \"BuildCosts\", | | \"costs\" : { | | \"value\" : 11.279, | | \"unit\" : \"Credits\" | | }, | | \"computationMethod\" : \"Estimated\", | | \"comment\" : \"estimated via sampling\" | | }, { | | \"name\" : \"StorageCosts\", | | \"costs\" : { | | \"value\" : 0.070493, | | \"unit\" : \"TB\" | | }, | | \"computationMethod\" : \"Estimated\", | | \"comment\" : \"estimated via sampling\" | | }, { | | \"name\" : \"MaintenanceCosts\", | | \"costs\" : { | | \"value\" : 30.296, | | \"unit\" : \"Credits\", | | \"perTimeUnit\" : \"MONTH\" | | }, | | \"computationMethod\" : \"Estimated\", | | \"comment\" : \"Estimated from historic change rate over last ~11 days.\" | | } ] | | } | +---------------------------------------------------------------------------+ -- すでに検索最適化が行われているテーブルに対するこの関数の出力 select SYSTEM$ESTIMATE_SEARCH_OPTIMIZATION_COSTS(\'TABLE_WITH_SEARCH_OPT\'); +---------------------------------------------------------------------------+ | SYSTEM$ESTIMATE_SEARCH_OPTIMIZATION_COSTS(\'TABLE_WITH_SEARCH_OPT\') | |---------------------------------------------------------------------------| | { | | \"tableName\" : \"TABLE_WITH_SEARCH_OPT\", | | \"searchOptimizationEnabled\" : true, | | \"costPositions\" : [ { | | \"name\" : \"BuildCosts\", | | \"computationMethod\" : \"NotAvailable\", | | \"comment\" : \"Search optimization is already enabled.\" | | }, { | | \"name\" : \"StorageCosts\", | | \"costs\" : { | | \"value\" : 0.052048, | | \"unit\" : \"TB\" | | }, | | \"computationMethod\" : \"Measured\" | | }, { | | \"name\" : \"Benefit\", | | \"computationMethod\" : \"NotAvailable\", | | \"comment\" : \"Currently not supported.\" | | }, { | | \"name\" : \"MaintenanceCosts\", | | \"costs\" : { | | \"value\" : 30.248, | | \"unit\" : \"Credits\", | | \"perTimeUnit\" : \"MONTH\" | | }, | | \"computationMethod\" : \"EstimatedUpperBound\", | | \"comment\" : \"Estimated from historic change rate over last ~11 days.\" | | } ] | | } | +---------------------------------------------------------------------------+ まとめ 検索最適化サービスについてドキュメントを読んでいくつか試してみた。 ドキュメントにある「ポイントルックアップクエリ」という言葉が機能を最も適切に表していると思う。 高速化したいクエリが明確な時に使えるのかもしれない。

[mathjax] 期待値、分散、歪度、尖度...、確率分布を形成する確率密度関数の特徴を表す値で、 実は、相互に変換できる値なのだという...。読んでいったら若干感動したのでまとめてみる。 40近いオッさんがはじめてテイラー展開のありがたさを味わう瞬間の記録。 モーメント母関数とモーメント モーメント母関数を以下のように定義。 begin{eqnarray} M_x(t) &=& E(e^{tX}) \\ &=& int_{-infty}^{infty} e^{tx} f(x) dx end{eqnarray} 英語で書くとmoment generating function。モーメントを作る関数。 ここで(f(x))というのが確率密度関数。 もともとこの時点で積分が存在しないかもしれない。 確率密度関数によっては、期待値、分散、歪度、尖度を直接求めるのは難しい。 しかし、モーメント母関数の(r)階導関数からモーメント(mu_r)を解析的に求められる性質から、 期待値、分散、歪度、尖度を求めることができる。 さて...、40近いオッさんは思い出す。 指数関数のテイラー展開は、マクローリン級数を使って以下の通り。 begin{eqnarray} e^x = 1+x+x^2/2!+x^3/3!+cdots end{eqnarray} (tX)だと、 begin{eqnarray} e^{tX} = 1+tX+(tX)^2/2! +(tX)^3/3! + cdots end{eqnarray} 両辺の期待値をとる。右辺全体の期待値はそれぞれの項の期待値の和にできるので、 begin{eqnarray} E(e^{tX}) &=& M_x(t)\\ &=& E(1) + E(tX) + E((tX)^2/2!) + E((tX)^3/3!)) + cdots end{eqnarray} (t)に対する定数を出すと begin{eqnarray} M_x(t) &=& E(e^{tX})\\ &=& E(1) + E(X)t + E(X^2/2!)t^2 + E(X^3/3!)t^3 + cdots \\ &=& 1 + mu_1 t + (mu_2/2!)t^2 + (mu_3/3!)t^3 + cdots end{eqnarray} キター。おわかりだろうか...。 (M_x(t))は(t)に関する展開式の係数に各次数のモーメントを含んでいる。 (t)について1回微分すると0次までの項は消える。 2次以降の項の(t)の次数が1減って残る。1次の項だけ(t)が消える。 そのとき(t=0)とすると、階数の係数(M^{(r)}_X(0)=mu_r)だけ残る！ つまり、以下のようなとんでもないことになる。 begin{eqnarray} M_X\'(0) = mu_1 \\ M_X\'\'(0) = mu_2 \\ M_X\'\'\'(0) = mu_3 \\ end{eqnarray} 各次数のモーメントである期待値、分散、歪度、尖度を、 モーメント母関数の(r)階導関数から求められるということになる。 指数分布のモーメント 試しに指数分布でやってみる。 begin{eqnarray} M_x(t) &=& int_{0}^{infty} e^{tx} lambda e^{-lambda x} dx \\ &=& lambda int_{0}^{infty} e^{(t-lambda)x} dx end{eqnarray} 指数関数の積分のところでおっ、と思ったけど、以下となる。 begin{eqnarray} M_x(t) = frac{ lambda }{ lambda -t} end{eqnarray} これ、解析的に微分できるのかな...と思うんだけども高校数学で暗記するやつ。 微分と積分を行ったり来たりするとわかる。 begin{eqnarray} M_x^{(1)}(t) &=& frac{ lambda }{ (lambda -t)^2} \\ M_x^{(2)}(t) &=& frac{ 2 cdot lambda }{(lambda -t)^3} \\ M_x^{(3)}(t) &=& frac{ 2 cdot 3 cdot lambda}{(lambda -t)^4} end{eqnarray} (t=0)とおくと、 begin{eqnarray} mu_1 &=& frac{1}{lambda} \\ mu_2 &=& frac{2}{lambda^2} \\ mu_3 &=& frac{2 cdot 3}{ lambda^3} \\ mu_4 &=& frac{2 cdot 3 cdot 4}{ lambda^4} end{eqnarray} これで、微分の数値計算をしなくても解析的に(mu_1)から(mu_4)が求まった。 そして永遠に微分し続けることで指数分布を形作る指標が決まっていく。 すごいなぁ...。

[mathjax] 線形単回帰で推定する回帰係数の精度を評価する方法を読んだのでまとめてみる。 当然、真の直線はわからないのだけれども、真の直線があると仮定した上で 推定した回帰係数との関係を考えることで、回帰係数の精度について話せるようになる。 回帰係数の導出 データポイントが(n)個ある状況。 ( (x_1,y_1),(x_2,y_2),cdots,(x_n,y_n) ) 回帰係数(hat{beta_0})と(hat{beta_1})を使って線形回帰したい。 begin{eqnarray} hat{y} = hat{beta_0} + hat{beta_1} x end{eqnarray} データポイントと回帰直線の差を残差平方和(RSS,redisual sum of square)で表す。 データポイントは既に与えられているデータなので、(hat{beta_0},hat{beta_1})の関数。 begin{eqnarray} f(hat{beta_0},hat{beta_1}) = (y_1 -hat{beta_0}-hat{beta_1}x_1)^2 + (y_2 - hat{beta_0}-hat{beta_1}x_2)^2 + cdots + (y_n - hat{beta_0}-hat{beta_1}x_n)^2 end{eqnarray} RSSを最小にする(hat{beta_0})と(hat{beta_1})を求めるために、(hat{beta_0})、(hat{beta_1})それぞれで偏微分して(0)として解く。 なんでそれぞれ個別に偏微分して0と置いて良いかは、 RPML読もうとして力尽きたときに理解したので省略。 参考にした本に( hat{beta_0}),(hat{beta_1}),RSSの3次元の図があって、確かにそれで良さそうな予感。 begin{eqnarray} frac{partial}{partial hat{beta_0}} f(hat{beta_0},hat{beta_1}) = 0 \\ frac{partial}{partial hat{beta_1}} f(hat{beta_0},hat{beta_1}) = 0 \\ end{eqnarray} 以下のようになるらしい。(bar{x})、(bar{y})はデータポイントの標本平均。 なので、データポイントがわかれば計算で求まる。 begin{eqnarray} hat{beta_1} &=& frac{sum_{i=1}^n (x_i-bar{x}) (y_i-bar{y}) }{sum_{i=1}^n (x_i-bar{x})^2 }\\ hat{beta_0} &=& bar{y}-hat{beta_1}bar{x} end{eqnarray} 母回帰直線の推定 データポイントが同じであれば(hat{beta_0}),(hat{beta_1})は同じになるけれども、 データポイントを取り直して異なるデータセットにすると、(hat{beta_0}),(hat{beta_1})は微妙に違う値になる。 じゃあ、データセットを大量に用意したとして、(hat{beta_0}),(hat{beta_1})を計算しまくると、 どこかに収束するんじゃなかろうか。 標本が大量にあると標本平均は母平均に収束する。標準偏差はより小さくなる。 つまりデータが大量にあると、母平均からのズレが小さくなっていく。 大数の弱法則、中心極限定理、ルートnの法則。 begin{eqnarray} hat{sigma} &=& frac{sigma}{sqrt{n}} \\ hat{sigma}^2 &=& frac{sigma^2}{n} end{eqnarray} begin{eqnarray} lim_{n rightarrow infty} hat{sigma}^2 = lim_{n rightarrow infty} frac{sigma^2}{n} = 0 end{eqnarray} [clink url=\"https://ikuty.com/2018/07/17/sample_sigma/\"] (hat{beta_0}),(hat{beta_1})は母回帰直線からどれくらいばらついているのか。 (hat{beta_0}),(hat{beta_1})の分散は以下を使うらしい。 両方に出てくる(sigma^2)は、母回帰直線と回帰直線の差となる項の散らばり度合い。 つまり、(Y=beta_0 + beta_1 X + epsilon )としたときの(epsilon)の分散。 begin{eqnarray} sigma_{hat{beta_0}}^2 &=& sigma^2 Bigl[frac{1}{n} + frac{bar{x}^2}{sum_{i=1}^n (x_i-bar{x})^2} Bigr] \\ sigma_{hat{beta_1}}^2 &=& frac{sigma^2}{sum_{i=1}^n (x_i -bar{x})^2} end{eqnarray} (x_i)が散らばれば散らばるほど、(sigma_{hat{beta_1}}^2)は小さくなる。 データポイントの(x)成分が小さい方から大きい方まで含まれれば、傾き(beta_1)を推定しやすくなる。 そして、(bar{x}=0)であるならば、(hat{beta_0})の散らばりは、(hat{mu})の散らばりと等しくなる。 最終的に求めたいのは不明な(sigma^2)だが、(sigma^2)はデータから計算できる。 (sigma)の推定値(RSE,Resual Standard Error)はRSSから推定する。 begin{eqnarray} sqrt{frac{f(hat{beta_0},hat{beta_1})}{(n-2)}} end{eqnarray} (hat{beta_1})の標準偏差がわかったので、95%信頼区間を求めることができる。 線形回帰における(hat{beta_1})の95%信頼区間は、 begin{eqnarray} Bigl[ hat{beta_1} - 1.96 sigma_{hat{beta_1}},hat{beta_1} + 1.96 sigma_{hat{beta_1}} Bigr] end{eqnarray} 同様に(hat{beta_0})の95%信頼区間は、 begin{eqnarray} Bigl[ hat{beta_0} - 1.96 sigma_{hat{beta_0}},hat{beta_0} + 1.96 sigma_{hat{beta_0}} Bigr] end{eqnarray}