[TIL][心得] K-MC2: Approximate K-Means++ in Sublinear Time

前提

每週五是我們公司的資料科學家讀書會時間,常常這類時間我可能都會在外面跟客戶開會無法參加. 但是這個禮拜總算把時間空出來參加,還好聽得懂內容跟為何要這麼做,所以相當的開心.

本週分享的是 Clustering 中的 K-Means , K-Means++ 與 也就是有名的文章 K-MC2: Approximate K-Means++ in Sublinear Time

其中 K-MC2 : K-Means++ with Markov chain Monte Carlo.

簡單筆記

  • Fast and Provably Good Seeding for means
    • K-mean
      • 計算 k-gram 之間距離
      • 如果以三角形來說 tri-gram
      • 透過”三角不等式”
        • 第三邊不小於 1 - 2
        • 第三邊不能大於 1+ 2
      • 透過這樣來限縮第三邊的範圍可以加速 k-means 運算
    • K-mean++
      • 解決 k-mean 容易因為初始值導致 clustering 效果不佳
      • 透過修正取點的方式(比較遠的比較容易被取到) 透過機率性的方式
      • 取點只做第一次,後面還是使用 k-mean 來計算
    • MCMC Samling (K-MC2)
      • 在做 clustering 中心點取樣的時候
      • 透過取樣後 clustering 中心點,然後來分群
      • 透過 Markov Chain
      • [優點]
        • 以往做 K-mean 挑點,需要 k * m
        • 透過這個方式可以不在需要把每個點都走過挑選

思考脈絡與筆記

  • K-Means
    • 優點:
      • 分群效能快,取樣隨便取.
    • 缺點:
      • 精準度不足,當一開始的取樣點不好的時候.需要不斷重新取樣來重新計算.
  • K-Means++
    • 優點(解決 K-Means 問題):
      • 分群精准度好
    • 缺點:
      • 取樣的時間複雜度變高.試著每次取樣比較遠的點.
  • K-MC2
    • 優點(解決 K-Means++ 問題):
      • 分群精準度好之外,也減少了取樣的複雜度.
    • 缺點:
      • 需要Markov Chain length 超過一定比例的 m
      • 你的精準度,就會達到 K-Means++

圖表

  K-Means K-Means++ K-MC2
取樣效率
精準度 當初取點錯誤,精準度就差 解決取點精準度問題,但是構成取點效率差 當 MCMC 長度 m 夠大的時候,精準度就跟 K-Means++ 一樣精準
取樣方式 隨機選 透過全部距離計算,高機率選取到比較遠的點 透過 MCMC 的方式,來解決 Sample 點是否要繼續來計算距離.某些機率下,不在繼續計算距離而直接移到下一個節點來計算距離.

代碼 github.com/obachem/kmc2 :

安裝

pip install numpy
pip install kmc2

不過… macOS 會報錯

kmc2.c:232:10: fatal error: 'numpy/arrayobject.h' file not found
    #include "numpy/arrayobject.h"
             ^
    1 error generated.
    error: command 'clang' failed with exit status 1
    

解決方式

解法

export CFLAGS="-I /usr/local/lib/python2.7/site-packages/numpy/core/include $CFLAGS"

範例

import kmc2
import numpy
X = numpy.random.random((3, 3))
seeding = kmc2.kmc2(X, 5)  # Run k-MC2 with k=5

參考資料:

[TIL] Kubernetes Anywhere, 1.5 and Beyond 影片導讀

前提

2016/12 底由 CoreOS 主辦的 TECTONIC 2016 Summit 裡面有將 Kubernetes 1.5 做了一整個清楚的說明. Kubernetes 1.5 (與未來) 針對了大家一直以來的痛點做了很多的改進,並且用很生動的範例來解釋如何使用.相當推薦的好影片,以下快速整理一下:

簡化安裝流程: (KubeAdm, KubeFed)

KubeAdm: 一直以來安裝 Kubernetes 一直都不是簡單的事情 (與 Docker Swarm 與 DCOS 比較起來) .當然 Google 找出了解決方式,就是 KubeAdm ( 跟 Docker Swarm 一樣的使用方式)

個人有使用過 KubeAdm ,真的使用起來就像 Docker Swarm Mode 一樣簡單.就是 init 之後,其他就透過 join 來加入就好.

KubeFed: 就是 Kubernets 解決多個集群的問題.

支援更複雜的排程: (Taint, Toleration, Forgiveness 目前都還沒完成)

  • Taint/Toleration (issue 25320) : 透過 Taint 標記每個節點的特性 (比如說機器具有 GPU),然後 Toleration 可以挑選具有 GPU 的機器 (反之,沒有透過 Toleration 的 Pod 無法分配到 Taint 上面. 相同的也可以設定使用者特定的 Pod 在特定幾台專屬用該使用者機器上. 細節在這裡

  • Forgiveness(issue 1574): 可以透過對於 pod 的 health check 判別是否 pod 已經出問題,如果出問題會移到另外的節點重啟.

  • Disruption Budget: 可以透過他來做 stateful server 的關閉與升級. 細節在這裡

  • Network Policy Object: 可以設定哪些 pod 可以跟哪些 pod 溝通,甚至可以規定到單向. 細節在這裡

如何更輕鬆地不少複雜的軟體服務?: (比如說成套的服務套件,或是有優先順序?)

HELM: The Kubernetes Package Manager : 就把它當成 Kubernetes apt-get,可以快速幫你安裝軟體.

投影片

在這裡

[TIL] Cassandra Backup Survey

Preface

Our cassandra instance sometime got crash mess amount of data. To backup those data to another storage is task need to do.

CQLSH

First backup canssandra schema

Export entire schema of your cassandra.

cqlsh -e "DESC SCHEMA" > user_schema.cql

Or you can specific your keyspace here.

cqlsh -e "DESC SCHEMA" > user_schema.cql

Export and Import cassandra data

Export

COPY <tablename> [ ( column [, ...] ) ]
     FROM ( '<filename>' | STDIN )
     [ WITH <option>='value' [AND ...] ];

For example

cqlsh> COPY log.parts FROM STDIN;

Another example to transform output format

cqlsh> COPY log.chatlogs (ts, content, other) TO './chatlog.dat'
   ... WITH DELIMITER = '|' AND QUOTE = '''' AND ESCAPE = '''' AND NULL = '<null>';

Import

cqlsh> COPY emp (empid,deptid,last_name,first_name) FROM 'temp.csv';

Troubleshooting

  1. Cannot dump all DB because partition.
Error for (-5813055698912042437, -5769658640073958582): Failed to connect to all replicas ['10.123.456.789'] for (-5813055698912042437, -5769658640073958582), errors: ['NoHostAvailable - (\'Unable to connect to any servers\', {\'10.123.456.789\': error(None, "Tried connecting to [(\'10.123.456.789\', 9042)]. Last error: timed out")})'] (will try again later attempt 1 of 5)

Ans:

Because your cassandra has three partition, and it is in GCE. We only export one port for cqlsh remote connect. So, you could not get any data from your other two partition.

Try install cqlsh in GCE machine with pip install cqlsh.

  1. pip install cqlsh has some problem with copy.
'module' object has no attribute 'parse_options'

**Ans: **

We could not use cqlsh from pip, suggestion use cassanra’s cqlsh. Refer jira

sudo docker run -it cassandra /usr/bin/cqlsh

Refer:

程式設計週記[2017/01/06]: 新年新希望: 健康與毅力

這是什麼?

程式週記主要內容如下:

Gihub project 介紹:

  • 主要會貼一些github,但是會盡量寫上一些有用的評語(或是我容易想到的關鍵詞)幫助以後查詢

網路文章心得:

  • 會寫些心得,強迫自己閱讀.

“程式週記”並且定期週期性更新.

大部分內容在我的twitter都會有,這邊只是將一些簡單的心得與感想註解一下.

本週摘要

本週工作上有個里程碑,很開心夥伴們能夠準時的交付出產品.雖然我們也踩了不少雷,不過我們完成了!!

目前一邊在看 udacity 的 Introduction Machine Learning 一邊也跟著公司同事們學習相關論文.相當充實!!



Go

Contributing to the Go project

2016 的舊文章,不過很實用.

由於 Go 專案都是放在 Gerrit 想要貢獻給 #golang 專案,卻又不知道該如何開始? 這篇文章提供一整個流程的介紹,幫助你可以提交你的第一個 PR 給 Golang, 來看看這篇文章吧

有人幫忙精選了在 2016 的九篇最受歡迎的 Golang 相關文章,其中前五篇是:

Grumpy: Go running Python!

Google open source 為了解決很多 legacy 的 python code ,開發了一個工具可以讓你將 Python 轉換成 Go ,或是在 python 裡面跑 go 的套件.

一些重點整理:

  1. Grumpy (脾氣暴躁 XD) 把 令人討厭的 GIL (Global interpreter lock) 拿掉了.換成 Go 的 GC 來管理.可以讓跑 python 的時候 multiple thread 更快. Grumpy 也不是第一個把 GIL 拿掉的 Python runtime, IronPython/Jython 都這樣幹過

  2. 目前 Grumpy 支援度不夠,所以大家使用前看一下 issue list (光是 import “/”, “.” 就有些問題 refer issue 11)

  3. Grumpy 不知道 CPython 的部分,所以 numPy 跟 opencv 都不能用. (其實還不少不能用的,畢竟還 alpha)

  4. 也是可以跑 Interactive shell “make run” 就可以了…

  5. 目前僅支援 python 2.7 (畢竟還有四年可以活 XD)

最後,為了呼應拿掉 GIL , Russ Cox 也發了篇十年前的 C 與顏文章.來解釋 lock 有多痛苦 XDDD

想清楚了解 Python GIL 是什麼,可以看看這篇 slide



Python



Android/JAVA/NODE.JS/Scala

Migration From Spark 1.x to Spark 2.x

如何將你手邊 Spark 1.x 的代碼移植到 Spark 2.x 裡面.有些 package 位置有換得的部分要注意一下.



Docker



Kubernetes

Setting up OpenAI’s Kubernetes EC2 autoscaler in the cluster installed by kops

同事寫的相關安裝文件,整理的不錯.



iOS/Swift



其他程式語言

Rust: Reword ‘stupid’ and ‘crazy’ in docs.

如何在文件中把一些比較激進的文字修改成比較溫和的文字 XDD



論文收集



網站文章

【长城】原来是一部细思极恐的IT大片

雲端架構師如何來看”長城”這部賀歲大片. HA 的怪是哪招? XDD



Machine Learning

berkeley 2017 春季的 Deep Reinforcement Learning 課程

Breaking things is easy

Nicolas Papernot 和 Ian Goodfellow 探討機器學習模型的資安問題,本文列出了三招,摘要如下:

  1. 對資料集下毒:在已上線的模型中,餵幾個最能增加模型預測錯誤的資料點。例如莫里雅提教授送福爾摩斯穿一雙新鞋子,讓警方認為那雙鞋子就是福爾摩斯穿的,接著莫再穿著另一雙一樣的鞋子去犯案,來入罪福爾摩斯。
  2. 惡意輸入讓模型預測錯誤:例如一隻熊貓加上一些人眼無法察覺的雜訊,可讓機器預測為長臂猿。要使用這種攻擊需要知道模型參數
  3. 隱私問題:壞人的目標是想辦法取得一部分帶有使用者隱私的訓練資料,或是觀察模型的預測來擷取隱私。例如觀察智慧型手機鍵盤輸入的預測,可以約略知道使用者常打什麼關鍵字。

(以上文字轉錄自 智程梁)

Learning from Simulated and Unsupervised Images through Adversarial Training

Apple 發表的第一篇跟 Machine Learning 相關的論文,內容圍繞著 GAN 與影像處理.

Matching networks for one shot learning

Morning Paper 是每天會幫你讀一篇論文,然後寫下導讀跟心得. 今天談如何透過極少的object 來做分類



有聲書/影片心得





程式設計週記[2016/12/29]: 年底到了,先來點今年完成了哪些吧

這是什麼?

程式週記主要內容如下:

Gihub project 介紹:

  • 主要會貼一些github,但是會盡量寫上一些有用的評語(或是我容易想到的關鍵詞)幫助以後查詢

網路文章心得:

  • 會寫些心得,強迫自己閱讀.

“程式週記”並且定期週期性更新.

大部分內容在我的twitter都會有,這邊只是將一些簡單的心得與感想註解一下.

本週摘要

年底到了,先盤點一下,今年達成的目標:

  • COSCUP 講者
  • Modern Web 講者
  • GOOGLE DevFest Taipei 講者
  • Organize GolangTW meetup
  • 完成 Project 52
  • 修完 2 堂 Moocs

除了完成的部分,也該盤點一下把自己的 Coursera, EDX, Udacity 上面還沒修完的課程.得要把他們都修完才對:

  • Coursera: Cloud Computing Part 1. 學習 Gossip 的好課程,一定要好好把他修完.
  • Coursera: Machine Learning. Andrew Ng 的經典課程,上了幾個禮拜就停住,一樣得好好學學.
  • Udacity: Machine Learning入門. 算很基礎的課程,搭配 SKLearn .應該會比 Andrew Ng 的課程還早修完.



Go

Enigma emulator in Go

Enigma 就是二次世界大戰德國用來加解密的機器,德國透過 Enigma 來加解密相關軍事訊息來傳送給友軍.

這個模擬器試著要透過 Golang 模擬 Enigma 的功能,很有趣.

geohot/lolrecaptcha: We try to break the recaptcha for the Merry Christmas for all!

喬治·霍茲 (geohot) 是美國的知名駭客,目前在 Google 的 Zero Project 團隊中專門發現所謂的 Zero-Day Bug.

之前比較知名的事件就是他是第一個破解 iOS 跟 PS3 的人,並且也開源了 comma.ai

在聖誕節前夕,他忽然想來學 Golang,於是就把 recaptcha (Google 開發的是否是機器人的判斷器) 破解了.

快來看看他怎麼破解的..

Testing distributed systems in Go

Golang 是最容易拿來撰寫分散式系統的語言(之一),這篇文章拿了 etcd (CoreOS 開發的分散式 K/V 資料庫) 為範例來講解如何測試.

裡面提到不少測試的新法,比如說:

  • 砍掉任意節點
  • 砍掉任意 Leader 節點
  • 砍掉超過多數的節點
  • 砍掉全部節點…

也有提供該如何砍掉 node 的 sample code .

這篇文章相當適合想寫分散式系統的人好好閱讀,也希望大家會喜歡.

GopherVids

這邊有搜集了所有的 Golang 的相關演講的影片,你可以透過講者與時間來做簡單的搜尋與分類.

來看看吧,一定能找到你想要看的演講影片



Python



Android/JAVA/NODE.JS/Scala



Docker



Kubernetes



iOS/Swift



其他程式語言



論文收集



網站文章

The 12 Most Retweeted Programming Quotes

12 個最常被轉 tweet 的經典程式設計師語錄. Programming Wisdom 是一個 twitter 上面相當知名的程式設計師語錄.這篇文章精選了 12 個最多人歡迎的 tweeet 並且解釋了其中的內容.



Machine Learning

Deep Learning: An MIT Press book

這是一本相當知名的 Deep Learning 書籍,作者就是 Ian Goodfellow (深度學習的大師,也就是生成式對抗網絡 GAN: Generative Adversarial Networks 的作者之一).

這本書在 Amazon 有販賣紙本,當然也可以在這個地方直接線上閱讀. 作者也有提供投影片可以觀看.

如果有興趣,也可以跟 chihcheng.liang 一起來讀這本

自上而下的学习路线: 软件工程师的机器学习

軟體工程師想要自學 Machine Learning 所記錄的所有心路歷程與相關資源.很適合想要自學的人來看看.

近200篇機器學習&深度學習資料分享

兩百篇精選的 Machine Learning 相關資源(也附上相關的中文翻譯) . 很多文章都相當的經典,很推薦好好讀讀.



有聲書/影片心得





程式設計週記[2016/12/23]: 把握時間,珍惜你愛的

這是什麼?

程式週記主要內容如下:

Gihub project 介紹:

  • 主要會貼一些github,但是會盡量寫上一些有用的評語(或是我容易想到的關鍵詞)幫助以後查詢

網路文章心得:

  • 會寫些心得,強迫自己閱讀.

“程式週記”並且定期週期性更新.

大部分內容在我的twitter都會有,這邊只是將一些簡單的心得與感想註解一下.

本週摘要

最近家人得了癌症,就深刻地了解到健康的重要.

“時間”,“愛”與“死亡“緊緊的將我們串連在一起 這句話其實是最近已經上映的電影 “最美的安排 (ollateral Beauty)“裡面的一句話.

我們真的要好好的珍惜我們擁有的時間與愛才能幫助我們正確地面對死亡.

不論你信仰是哪一種神,最公平的就是每個人一天就是 24 個小時,不會因為你是身份,種族與性別有何不同. 如何把握每一天,好好運用這上篇天給予我們的禮物就格外重要.



Go

Who needs generics? Use … instead!

介紹 generics 基本定義,如何在 go 用其他方式取代。

大家都知道 Golang 不支援 generics 如果程式就是需要怎麼辦? 這邊介紹一些心法。

minaandrawos/machat : An open source chat server implemented in Go

透過 Golang 完成的一個聊天室伺服器,還有 client 端

jpoz/gomeme: Command line double caption meme generator. Written in Go (Golang)

將 GIF 加上一段有趣的上標跟下標,做成 MEME GIF.

The 12 Factors of Go

12FA (12 factor app) 是 heroku 提出建制 modern app 的方法論。 這篇作者試著用 Go 與 Docker 來實作並且寫了一本書

piladb: Lightweight RESTful database engine based on stack data structures

piladb (pila: 就是西班牙文的 stack): PilaDB 是一個輕量化的 RESTful DB ,並且提供 stack structure 的架構,也就是說你可以透過 Push/Pop 來存取資料.



Python



Android/JAVA/NODE.JS/Scala

PMML model export - RDD-based API

Exploring Spark MLlib: Part 4 – Exporting the model for use outside of Spark

如何把 model 輸出,載入再加上預測.

Apache Spark 2.0 Preview: Machine Learning Model Persistence

2.0 machine learning 輸出與輸入的方式…



Docker



Kubernetes

深度学习框架TensorFlow在Kubernetes上的实践

這一篇文章稍微簡單的介紹 Tensorflow 與 Deep Learning ,並起稍微簡介了 Tensorflow 的工作流程.

既然 Tensorflow 已經支援了 cluster mode ,那為何還需要 Kubernetes 呢? 主要原因如下:

  • Storage
  • Failure Recovery
  • Task Monitoring
  • Resource Management
  • Tensorflow Cluster mode will not terminal after job finised (tentative)

算是初步入門文章

Why Red Hat makes more money on Docker than Docker does

“Redhat 透過 Docker 賺的錢,比 Docker 自己都還要多”

這篇章從商業的角度上來探討為何 Docker 很難賺到錢,相反的身為系統服務商 Redhat 卻透過 OpenShift 賺進大筆的鈔票 ($2 billion in annual revenue ).

本文中認為 OpenShift 其實在內容上跟 Docker Datacenter 的服務並沒有太大差異,而 Redhat 憑著是良好的 Docker Container 的運作熟悉度 ( BTW: Redhat 是第二大的 Docker opensource 的貢獻者) 搭配著 Kubernetes 在底層的服務就賺進了大筆的器業服務與諮詢費.

常跟幾個商業夥伴在笑說, Redhat 的服務費是很貴,那是因為當以要找他的時候,就是你需要服務( 解 Bug ) 的時候.所以就像是軟體服(ㄌ ㄜ )務(ㄙ ㄨ ㄛ \/ ) 費一樣.



iOS/Swift



其他程式語言

How to include graphviz graphs in github README

如何在 Github Readme 裡面使用 graphviz 系列的向量與流程圖語言.



論文收集



網站文章



Machine Learning

Splunk+蜜罐+防火墙=简易WAF

透過 Splunk (相當快速的資料分析工具) 來收集所有的 syslog 來分析所有的網路流量,如果看到有異常的狀況,就會報警出來.

並且架設一個蜜罐 ( 一個無防禦的漏洞,但是不會實際損害到主機的端口 ) 來收集所有可能是惡意攻擊的連線,交給 Splunk 來分析.

透過 Splunk 跟 蜜罐能達到什麼? 就可以建置一個類似於 WAF 全文為「Web Application Firewall」,可以直接翻譯成「網路應用程式防火牆」或「網站應用程式防火牆」,這邊有詳細的介紹

如何成为一名人工智能产品经理?

這篇文章主要介紹做一個 AI(ML) 的 PM 與一般軟體(或是服務)的差別在哪裡,如何做好一個?

也會一並建議如何自我進修的部分.

引用 Andrew Ng 的一段話:

「对我而言,无论何时,当我觉得我不知道下一步应该如何做的时候,
我将会尝试大量的学习和阅读,和某些领域的专家谈话。我不知道我们
的大脑是如何工作的,但它非常的神奇:当你读了足够多的书,或者和
足够多的专家谈话之后,换句话说,当你的大脑有了足够多的输入信
息,新的想法就会随之产生。」

OpenAI: Infrastructure for Deep Learning

OpenAI (一個提供平台給大家做 AI 練習的公司) 公佈了他們的基礎架構,一個基於 Kubernets 所部署出來的分散式的 Tensorflow .

這篇文章除了介紹 Tensorflow 之外,也介紹了一個透過 Deep Learning 完成的範例. 其中系統架構是透過 Kubernetes 加上分散式的 Tensorflow cluster ,並且透過 Kubernetes-ec2-autoscaler 來做到機器的 Auto-Scaler .



有聲書/影片心得