Recommender Systems 推薦系統與深度學習

Posted on 2017-06-16 by 蕭博元

Recommender Systems 推薦系統

#coding:utf-8
from __future__ import division
from collections import Counter
print "---有興趣的有哪些---"
users_interests = [
    ["Hadoop", "Big Data", "HBase", "Java", "Spark", "Storm", "Cassandra"],
    ["NoSQL", "MongoDB", "Cassandra", "HBase", "Postgres"],
    ["Python", "scikit-learn", "scipy", "numpy", "statsmodels", "pandas"],
    ["R", "Python", "statistics", "regression", "probability"],
    ["machine learning", "regression", "decision trees", "libsvm"],
    ["Python", "R", "Java", "C++", "Haskell", "programming languages"],
    ["statistics", "probability", "mathematics", "theory"],
    ["machine learning", "scikit-learn", "Mahout", "neural networks"],
    ["neural networks", "deep learning", "Big Data", "artificial intelligence"],
    ["Hadoop", "Java", "MapReduce", "Big Data"],
    ["statistics", "R", "statsmodels"],
    ["C++", "deep learning", "artificial intelligence", "probability"],
    ["pandas", "R", "Python"],
    ["databases", "HBase", "Postgres", "MySQL", "MongoDB"],
    ["libsvm", "regression", "support vector machines"]
]

popular_interests = Counter(interest
                            for user_interests in users_interests
                            for interest in user_interests).most_common()

print "Popular Interests"
print popular_interests

#coding:utf-8

from __future__ import division

from collections import Counter

print "---有興趣的有哪些---"

users_interests = [

["Hadoop", "Big Data", "HBase", "Java", "Spark", "Storm", "Cassandra"],

["NoSQL", "MongoDB", "Cassandra", "HBase", "Postgres"],

["Python", "scikit-learn", "scipy", "numpy", "statsmodels", "pandas"],

["R", "Python", "statistics", "regression", "probability"],

["machine learning", "regression", "decision trees", "libsvm"],

["Python", "R", "Java", "C++", "Haskell", "programming languages"],

["statistics", "probability", "mathematics", "theory"],

["machine learning", "scikit-learn", "Mahout", "neural networks"],

["neural networks", "deep learning", "Big Data", "artificial intelligence"],

["Hadoop", "Java", "MapReduce", "Big Data"],

["statistics", "R", "statsmodels"],

["C++", "deep learning", "artificial intelligence", "probability"],

["pandas", "R", "Python"],

["databases", "HBase", "Postgres", "MySQL", "MongoDB"],

["libsvm", "regression", "support vector machines"]

]

popular_interests = Counter(interest

for user_interests in users_interests

for interest in user_interests).most_common()

print "Popular Interests"

print popular_interests

print "---用大眾資料推薦你適合甚麼---"
def most_popular_new_interests(user_interests, max_results=5):
    suggestions = [(interest, frequency)
                   for interest, frequency in popular_interests
                   if interest not in user_interests]
    return suggestions[:max_results]

print "Most Popular New Interests"
print "already like:", ["NoSQL", "MongoDB", "Cassandra", "HBase", "Postgres"]
print most_popular_new_interests(["NoSQL", "MongoDB", "Cassandra", "HBase", "Postgres"])
print "Me like Python Java Hbase"
print most_popular_new_interests(["Python","Java","Hbase"])

print "---用大眾資料推薦你適合甚麼---"

def most_popular_new_interests(user_interests, max_results=5):

suggestions = [(interest, frequency)

for interest, frequency in popular_interests

if interest not in user_interests]

return suggestions[:max_results]

print "Most Popular New Interests"

print "already like:", ["NoSQL", "MongoDB", "Cassandra", "HBase", "Postgres"]

print most_popular_new_interests(["NoSQL", "MongoDB", "Cassandra", "HBase", "Postgres"])

print "Me like Python Java Hbase"

print most_popular_new_interests(["Python","Java","Hbase"])

用相似的人與你喜歡進行分析，算出哪個跟你最相似

print "---與誰最相似---"
from linear_algebra import dot
import math

unique_interests = sorted(list({ interest
                                 for user_interests in users_interests
                                 for interest in user_interests }))

def make_user_interest_vector(user_interests):
    """given a list of interests, produce a vector whose i-th element is 1
    if unique_interests[i] is in the list, 0 otherwise"""
    return [1 if interest in user_interests else 0
            for interest in unique_interests]

# 兩兩做比對，算出哪個跟你最相近
def cosine_similarity(v, w):
    return dot(v, w) / math.sqrt(dot(v, v) * dot(w, w))

user_interest_matrix = map(make_user_interest_vector, users_interests)
user_similarities = [[cosine_similarity(interest_vector_i, interest_vector_j)
                      for interest_vector_j in user_interest_matrix]
                     for interest_vector_i in user_interest_matrix]

def most_similar_users_to(user_id):
    pairs = [(other_user_id, similarity)                      # find other
             for other_user_id, similarity in                 # users with
                enumerate(user_similarities[user_id])         # nonzero
             if user_id != other_user_id and similarity &gt; 0]  # similarity
    return sorted(pairs,                                      # sort them
                  key=lambda (_, similarity): similarity,     # most similar
                  reverse=True)                               # first

print "User based similarity"
print "most similar to 11",most_similar_users_to(11)

print "---與誰最相似---"

from linear_algebra import dot

import math

unique_interests = sorted(list({ interest

for user_interests in users_interests

for interest in user_interests }))

def make_user_interest_vector(user_interests):

"""given a list of interests, produce a vector whose i-th element is 1

if unique_interests[i] is in the list, 0 otherwise"""

return [1 if interest in user_interests else 0

for interest in unique_interests]

# 兩兩做比對，算出哪個跟你最相近

def cosine_similarity(v, w):

return dot(v, w) / math.sqrt(dot(v, v) * dot(w, w))

user_interest_matrix = map(make_user_interest_vector, users_interests)

user_similarities = [[cosine_similarity(interest_vector_i, interest_vector_j)

for interest_vector_j in user_interest_matrix]

for interest_vector_i in user_interest_matrix]

def most_similar_users_to(user_id):

pairs = [(other_user_id, similarity) # find other

for other_user_id, similarity in # users with

enumerate(user_similarities[user_id]) # nonzero

if user_id != other_user_id and similarity > 0] # similarity

return sorted(pairs, # sort them

key=lambda (_, similarity): similarity, # most similar

reverse=True) # first

print "User based similarity"

print "most similar to 11",most_similar_users_to(11)

print "---以誰為基準進行推薦---"
from collections import defaultdict

def user_based_suggestions(user_id, include_current_interests=False):
    # sum up the similarities
    suggestions = defaultdict(float)
    for other_user_id, similarity in most_similar_users_to(user_id):
        for interest in users_interests[other_user_id]:
            suggestions[interest] += similarity
    # convert them to a sorted list
    suggestions = sorted(suggestions.items(),
                         key=lambda (_, weight): weight,
                         reverse=True)
    # and (maybe) exclude already-interests
    if include_current_interests:
        return suggestions
    else:
        return [(suggestion, weight)
                for suggestion, weight in suggestions
                if suggestion not in users_interests[user_id]]

print "Suggestions for 10"
print user_based_suggestions(10)

print "---以誰為基準進行推薦---"

from collections import defaultdict

def user_based_suggestions(user_id, include_current_interests=False):

# sum up the similarities

suggestions = defaultdict(float)

for other_user_id, similarity in most_similar_users_to(user_id):

for interest in users_interests[other_user_id]:

suggestions[interest] += similarity

# convert them to a sorted list

suggestions = sorted(suggestions.items(),

key=lambda (_, weight): weight,

reverse=True)

# and (maybe) exclude already-interests

if include_current_interests:

return suggestions

else:

return [(suggestion, weight)

for suggestion, weight in suggestions

if suggestion not in users_interests[user_id]]

print "Suggestions for 10"

print user_based_suggestions(10)

print "---以項目為基準進行興趣分析---"
interest_user_matrix = [[user_interest_vector[j]
                         for user_interest_vector in user_interest_matrix]
                        for j, _ in enumerate(unique_interests)]

interest_similarities = [[cosine_similarity(user_vector_i, user_vector_j)
                          for user_vector_j in interest_user_matrix]
                         for user_vector_i in interest_user_matrix]

def most_similar_interests_to(interest_id):
    similarities = interest_similarities[interest_id]
    pairs = [(unique_interests[other_interest_id], similarity)
             for other_interest_id, similarity in enumerate(similarities)
             if interest_id != other_interest_id and similarity &gt; 0]
    return sorted(pairs,
                  key=lambda (_, similarity): similarity,
                  reverse=True)

print "Item based similarity"
print "most similar to 'Big Data'"
print most_similar_interests_to(0)

print "---以項目為基準進行興趣分析---"

interest_user_matrix = [[user_interest_vector[j]

for user_interest_vector in user_interest_matrix]

for j, _ in enumerate(unique_interests)]

interest_similarities = [[cosine_similarity(user_vector_i, user_vector_j)

for user_vector_j in interest_user_matrix]

for user_vector_i in interest_user_matrix]

def most_similar_interests_to(interest_id):

similarities = interest_similarities[interest_id]

pairs = [(unique_interests[other_interest_id], similarity)

for other_interest_id, similarity in enumerate(similarities)

if interest_id != other_interest_id and similarity > 0]

return sorted(pairs,

key=lambda (_, similarity): similarity,

reverse=True)

print "Item based similarity"

print "most similar to 'Big Data'"

print most_similar_interests_to(0)

print "---以項目為基準進行推薦分析---"
def item_based_suggestions(user_id, include_current_interests=False):
    suggestions = defaultdict(float)
    user_interest_vector = user_interest_matrix[user_id]
    for interest_id, is_interested in enumerate(user_interest_vector):
        if is_interested == 1:
            similar_interests = most_similar_interests_to(interest_id)
            for interest, similarity in similar_interests:
                suggestions[interest] += similarity
    suggestions = sorted(suggestions.items(),
                         key=lambda (_, similarity): similarity,
                         reverse=True)
    if include_current_interests:
        return suggestions
    else:
        return [(suggestion, weight)
                for suggestion, weight in suggestions
                if suggestion not in users_interests[user_id]]

print "suggestions for user 0"
print item_based_suggestions(0)

print "---以項目為基準進行推薦分析---"

def item_based_suggestions(user_id, include_current_interests=False):

suggestions = defaultdict(float)

user_interest_vector = user_interest_matrix[user_id]

for interest_id, is_interested in enumerate(user_interest_vector):

if is_interested == 1:

similar_interests = most_similar_interests_to(interest_id)

for interest, similarity in similar_interests:

suggestions[interest] += similarity

suggestions = sorted(suggestions.items(),

key=lambda (_, similarity): similarity,

reverse=True)

if include_current_interests:

return suggestions

else:

return [(suggestion, weight)

for suggestion, weight in suggestions

if suggestion not in users_interests[user_id]]

print "suggestions for user 0"

print item_based_suggestions(0)

深度學習

以類神經為基礎

DNN DEEP Neual network

深度不固定

高速公路網路

ReLU f(x)=max(0,x)取0與x最大值，

Sigmoid 不管值是什麼都變成0-1 or -1 – 1

Maxout 只取大的點

CNN Convolutional neural network 捲基

減少像素圖片的權重訓練

RNN

把類神經計算前一個時間與後一個時間

深度學習套件

CAFFE 快,python

THEANO 結合GPU,python…TENSORFLOW 多GPU,分布式計算

LASAGNE 簡化THEANO

KERAS 注重CNN,單GPU

MXNET 多GPU

SKLEARN-THEANO 把CNN當作特徵器

NOLEARN

DIGITS web介面

PYLEARN2 較少改版

DEEPLEARNING4J 用JAVA開發

ENSEMBLE 集成學習

建立好幾個模型，做分析預測，看哪個模型訓練結果最高當作輸出

Bagging, boosting, randomforest

MORVAN

Github

Pip install Keras 先裝好Keras

先跑一次regressor-example，之後會產生一個

再去修改裡面的json

把tensorflow改成theano

classifer結果

備註：2017/06/08 計算方法分析與設計課堂筆記

分群(clutering) & NLP 自然語言處理

Posted on 2017-06-16 by 蕭博元

Github

分群(clutering)

#coding:utf-8
import math, random
from linear_algebra import squared_distance, vector_mean, distance
# KMean class
class KMeans:
    """performs k-means clustering"""
    def __init__(self, k):
        self.k = k  # number of clusters
        self.means = None  # means of clusters

    def classify(self, input):
        """return the index of the cluster closest to the input"""
        return min(range(self.k),
                   key=lambda i: squared_distance(input, self.means[i]))

    def train(self, inputs):
        self.means = random.sample(inputs, self.k)
        assignments = None
        while True:
            # Find new assignments
            new_assignments = map(self.classify, inputs)
            # If no assignments have changed, we're done.
            if assignments == new_assignments:
                return
            # Otherwise keep the new assignments,
            assignments = new_assignments
            for i in range(self.k):
                i_points = [p for p, a in zip(inputs, assignments) if a == i]
                # avoid divide-by-zero if i_points is empty
                if i_points:
                    self.means[i] = vector_mean(i_points)

#coding:utf-8

import math, random

from linear_algebra import squared_distance, vector_mean, distance

# KMean class

class KMeans:

"""performs k-means clustering"""

def __init__(self, k):

self.k = k # number of clusters

self.means = None # means of clusters

def classify(self, input):

"""return the index of the cluster closest to the input"""

return min(range(self.k),

key=lambda i: squared_distance(input, self.means[i]))

def train(self, inputs):

self.means = random.sample(inputs, self.k)

assignments = None

while True:

# Find new assignments

new_assignments = map(self.classify, inputs)

# If no assignments have changed, we're done.

if assignments == new_assignments:

return

# Otherwise keep the new assignments,

assignments = new_assignments

for i in range(self.k):

i_points = [p for p, a in zip(inputs, assignments) if a == i]

# avoid divide-by-zero if i_points is empty

if i_points:

self.means[i] = vector_mean(i_points)

input 資料

inputs = [[-14,-5],[13,13],[20,23],[-19,-11],[-9,-16],[21,27],[-49,15],[26,13],[-46,5],[-34,-1],[11,15],[-49,0],[-22,-16],[19,28],[-12,-8],[-13,-19],[-41,8],[-11,-6],[-25,-9],[-18,-3]]

以…為中心點分群

print "---分成3群---"
random.seed(0) # so you get the same results as me
clusterer = KMeans(3)
clusterer.train(inputs)
print "3-means:"
print clusterer.means

print "---分成3群---"

random.seed(0) # so you get the same results as me

clusterer = KMeans(3)

clusterer.train(inputs)

print "3-means:"

print clusterer.means

以…為中心點分群

print "---分成2群---"
random.seed(0)
clusterer = KMeans(2)
clusterer.train(inputs)
print "2-means:"
print clusterer.means

print "---分成2群---"

random.seed(0)

clusterer = KMeans(2)

clusterer.train(inputs)

print "2-means:"

print clusterer.means

分群誤差

def squared_clustering_errors(inputs, k):
    """finds the total squared error from k-means clustering the inputs"""
    clusterer = KMeans(k)
    clusterer.train(inputs)
    means = clusterer.means
    assignments = map(clusterer.classify, inputs)
    return sum(squared_distance(input, means[cluster])
               for input, cluster in zip(inputs, assignments))

def squared_clustering_errors(inputs, k):

"""finds the total squared error from k-means clustering the inputs"""

clusterer = KMeans(k)

clusterer.train(inputs)

means = clusterer.means

assignments = map(clusterer.classify, inputs)

return sum(squared_distance(input, means[cluster])

for input, cluster in zip(inputs, assignments))

# 跑分群，從1群到20群，看他的差異值

print "---跑不同的分群誤差---"
for k in range(1, len(inputs) + 1):
    print k, squared_clustering_errors(inputs, k)

print "---跑不同的分群誤差---"

for k in range(1, len(inputs) + 1):

print k, squared_clustering_errors(inputs, k)

分群差異圖

def plot_squared_clustering_errors(plt):
    ks = range(1, len(inputs) + 1)
    errors = [squared_clustering_errors(inputs, k) for k in ks]
    plt.plot(ks, errors)
    plt.xticks(ks)
    plt.xlabel("k")
    plt.ylabel("total squared error")
    plt.show()

print "---分群差異畫圖---"
import matplotlib.pyplot as plt
plot_squared_clustering_errors(plt)

def plot_squared_clustering_errors(plt):

ks = range(1, len(inputs) + 1)

errors = [squared_clustering_errors(inputs, k) for k in ks]

plt.plot(ks, errors)

plt.xticks(ks)

plt.xlabel("k")

plt.ylabel("total squared error")

plt.show()

print "---分群差異畫圖---"

import matplotlib.pyplot as plt

plot_squared_clustering_errors(plt)

print “—圖片顏色分群—“

import matplotlib.image as mpimg
def recolor_image(input_file, k=5):
    img = mpimg.imread(input_file)
    pixels = [pixel for row in img for pixel in row]
    clusterer = KMeans(k)
    clusterer.train(pixels) # this might take a while

    def recolor(pixel):
        cluster = clusterer.classify(pixel) # index of the closest cluster
        return clusterer.means[cluster]     # mean of the closest cluster

    new_img = [[recolor(pixel) for pixel in row]
               for row in img]
    plt.imshow(new_img)
    plt.axis('off')
    plt.show()

# 5色分群
recolor_image(r"flower.png")
# 3色分群
recolor_image(r"flower.png",3)

import matplotlib.image as mpimg

def recolor_image(input_file, k=5):

img = mpimg.imread(input_file)

pixels = [pixel for row in img for pixel in row]

clusterer = KMeans(k)

clusterer.train(pixels) # this might take a while

def recolor(pixel):

cluster = clusterer.classify(pixel) # index of the closest cluster

return clusterer.means[cluster] # mean of the closest cluster

new_img = [[recolor(pixel) for pixel in row]

for row in img]

plt.imshow(new_img)

plt.axis('off')

plt.show()

# 5色分群

recolor_image(r"flower.png")

# 3色分群

recolor_image(r"flower.png",3)

原始圖檔

5色分群

3色分群

NLP

自然語言處理

print "---NLP自然語言處理---"
import matplotlib.pyplot as plt
def plot_resumes(plt):
    data = [ ("big data", 100, 15), ("Hadoop", 95, 25), ("Python", 75, 50),
         ("R", 50, 40), ("machine learning", 80, 20), ("statistics", 20, 60),
         ("data science", 60, 70), ("analytics", 90, 3),
         ("team player", 85, 85), ("dynamic", 2, 90), ("synergies", 70, 0),
         ("actionable insights", 40, 30), ("think out of the box", 45, 10),
         ("self-starter", 30, 50), ("customer focus", 65, 15),
         ("thought leadership", 35, 35)]

    def text_size(total):
        """equals 8 if total is 0, 28 if total is 200"""
        return 8 + total / 200 * 20

    for word, job_popularity, resume_popularity in data:
        plt.text(job_popularity, resume_popularity, word,
                 ha='center', va='center',
                 size=text_size(job_popularity + resume_popularity))
    plt.xlabel("Popularity on Job Postings")
    plt.ylabel("Popularity on Resumes")
    plt.axis([0, 100, 0, 100])
    plt.show()

plot_resumes(plt)

print "---NLP自然語言處理---"

import matplotlib.pyplot as plt

def plot_resumes(plt):

data = [ ("big data", 100, 15), ("Hadoop", 95, 25), ("Python", 75, 50),

("R", 50, 40), ("machine learning", 80, 20), ("statistics", 20, 60),

("data science", 60, 70), ("analytics", 90, 3),

("team player", 85, 85), ("dynamic", 2, 90), ("synergies", 70, 0),

("actionable insights", 40, 30), ("think out of the box", 45, 10),

("self-starter", 30, 50), ("customer focus", 65, 15),

("thought leadership", 35, 35)]

def text_size(total):

"""equals 8 if total is 0, 28 if total is 200"""

return 8 + total / 200 * 20

for word, job_popularity, resume_popularity in data:

plt.text(job_popularity, resume_popularity, word,

ha='center', va='center',

size=text_size(job_popularity + resume_popularity))

plt.xlabel("Popularity on Job Postings")

plt.ylabel("Popularity on Resumes")

plt.axis([0, 100, 0, 100])

plt.show()

plot_resumes(plt)

NLP 組成文章

EX: We have a dog. We get a cat.

可分解成

We > have

We > get

Have > a

Get > a

A > dog

A > cat

因此可組成

We get a dog.

這樣的句子組成

由前後文找出單字後面的字是什麼

再依據後面的單字組成句子

print "---爬網抓文章，用前一個字比對---"
import requests,re
from bs4 import BeautifulSoup
from collections import defaultdict

def fix_unicode(text):
    return text.replace(u"\u2019", "'")

def get_document():
    url = "<a href="http://radar.oreilly.com/2010/06/what-is-data-science.html">http://radar.oreilly.com/2010/06/what-is-data-science.html</a>"
    html = requests.get(url).text
    soup = BeautifulSoup(html, 'html5lib')
    content = soup.find("div", "article-body")        # find article-body div
    regex = r"[\w']+|[\.]"                            # matches a word or a period
    document = []
    for paragraph in content("p"):
        words = re.findall(regex, fix_unicode(paragraph.text))
        document.extend(words)
    return document

def generate_using_bigrams(transitions):
    current = "."   # this means the next word will start a sentence
    result = []
    while True:
        next_word_candidates = transitions[current]    # bigrams (current, _)
        current = random.choice(next_word_candidates)  # choose one at random
        result.append(current)                         # append it to results
        if current == ".": return " ".join(result)     # if "." we're done

document = get_document()
bigrams = zip(document, document[1:])
transitions = defaultdict(list)

for prev, current in bigrams:
    transitions[prev].append(current)

random.seed(0)
print "bigram sentences"
for i in range(10):
    print i, generate_using_bigrams(transitions)

print "---爬網抓文章，用前一個字比對---"

import requests,re

from bs4 import BeautifulSoup

from collections import defaultdict

def fix_unicode(text):

return text.replace(u"\u2019", "'")

def get_document():

url = "<a href="http://radar.oreilly.com/2010/06/what-is-data-science.html">http://radar.oreilly.com/2010/06/what-is-data-science.html</a>"

html = requests.get(url).text

soup = BeautifulSoup(html, 'html5lib')

content = soup.find("div", "article-body") # find article-body div

regex = r"[\w']+|[\.]" # matches a word or a period

document = []

for paragraph in content("p"):

words = re.findall(regex, fix_unicode(paragraph.text))

document.extend(words)

return document

def generate_using_bigrams(transitions):

current = "." # this means the next word will start a sentence

result = []

while True:

next_word_candidates = transitions[current] # bigrams (current, _)

current = random.choice(next_word_candidates) # choose one at random

result.append(current) # append it to results

if current == ".": return " ".join(result) # if "." we're done

document = get_document()

bigrams = zip(document, document[1:])

transitions = defaultdict(list)

for prev, current in bigrams:

transitions[prev].append(current)

random.seed(0)

print "bigram sentences"

for i in range(10):

print i, generate_using_bigrams(transitions)

用文章前面兩個字與後面一個字去組成文章

print "---用前兩個字與後一個字做比對---"
def generate_using_trigrams(starts, trigram_transitions):
    current = random.choice(starts)   # choose a random starting word
    prev = "."                        # and precede it with a '.'
    result = [current]
    while True:
        next_word_candidates = trigram_transitions[(prev, current)]
        next = random.choice(next_word_candidates)
        prev, current = current, next
        result.append(current)
        if current == ".":
            return " ".join(result)

trigrams = zip(document, document[1:], document[2:])
trigram_transitions = defaultdict(list)
starts = []

for prev, current, next in trigrams:
    if prev == ".":              # if the previous "word" was a period
        starts.append(current)   # then this is a start word
    trigram_transitions[(prev, current)].append(next)
print "trigram sentences"

for i in range(10):
    print i, generate_using_trigrams(starts, trigram_transitions)

print "---用前兩個字與後一個字做比對---"

def generate_using_trigrams(starts, trigram_transitions):

current = random.choice(starts) # choose a random starting word

prev = "." # and precede it with a '.'

result = [current]

while True:

next_word_candidates = trigram_transitions[(prev, current)]

next = random.choice(next_word_candidates)

prev, current = current, next

result.append(current)

if current == ".":

return " ".join(result)

trigrams = zip(document, document[1:], document[2:])

trigram_transitions = defaultdict(list)

starts = []

for prev, current, next in trigrams:

if prev == ".": # if the previous "word" was a period

starts.append(current) # then this is a start word

trigram_transitions[(prev, current)].append(next)

print "trigram sentences"

for i in range(10):

print i, generate_using_trigrams(starts, trigram_transitions)

加上像是名詞、動詞、形容詞，根據詞性再去組成句子

print "---加入文法增加文章可讀性---"
def is_terminal(token):
    return token[0] != "_"

def expand(grammar, tokens):
    for i, token in enumerate(tokens):
        # ignore terminals
        if is_terminal(token): continue
        # choose a replacement at random
        replacement = random.choice(grammar[token])
        if is_terminal(replacement):
            tokens[i] = replacement
        else:
            tokens = tokens[:i] + replacement.split() + tokens[(i+1):]
        return expand(grammar, tokens)

    # if we get here we had all terminals and are done
    return tokens

def random_y_given_x(x):
    """equally likely to be x + 1, x + 2, ... , x + 6"""
    return x + roll_a_die()

def random_x_given_y(y):
    if y &lt;= 7:
        # if the total is 7 or less, the first die is equally likely to be
        # 1, 2, ..., (total - 1)
        return random.randrange(1, y)
    else:
        # if the total is 7 or more, the first die is equally likely to be
        # (total - 6), (total - 5), ..., 6
        return random.randrange(y - 6, 7)

def gibbs_sample(num_iters=100):
    x, y = 1, 2 # doesn't really matter
    for _ in range(num_iters):
        x = random_x_given_y(y)
        y = random_y_given_x(x)
    return x, y

def roll_a_die():
    return random.choice([1,2,3,4,5,6])

def direct_sample():
    d1 = roll_a_die()
    d2 = roll_a_die()
    return d1, d1 + d2

def generate_sentence(grammar):
    return expand(grammar, ["_S"])

def compare_distributions(num_samples=1000):
    counts = defaultdict(lambda: [0, 0])
    for _ in range(num_samples):
        counts[gibbs_sample()][0] += 1
        counts[direct_sample()][1] += 1
    return counts

print "---加入文法增加文章可讀性---"

def is_terminal(token):

return token[0] != "_"

def expand(grammar, tokens):

for i, token in enumerate(tokens):

# ignore terminals

if is_terminal(token): continue

# choose a replacement at random

replacement = random.choice(grammar[token])

if is_terminal(replacement):

tokens[i] = replacement

else:

tokens = tokens[:i] + replacement.split() + tokens[(i+1):]

return expand(grammar, tokens)

# if we get here we had all terminals and are done

return tokens

def random_y_given_x(x):

"""equally likely to be x + 1, x + 2, ... , x + 6"""

return x + roll_a_die()

def random_x_given_y(y):

if y <= 7:

# if the total is 7 or less, the first die is equally likely to be

# 1, 2, ..., (total - 1)

return random.randrange(1, y)

else:

# if the total is 7 or more, the first die is equally likely to be

# (total - 6), (total - 5), ..., 6

return random.randrange(y - 6, 7)

def gibbs_sample(num_iters=100):

x, y = 1, 2 # doesn't really matter

for _ in range(num_iters):

x = random_x_given_y(y)

y = random_y_given_x(x)

return x, y

def roll_a_die():

return random.choice([1,2,3,4,5,6])

def direct_sample():

d1 = roll_a_die()

d2 = roll_a_die()

return d1, d1 + d2

def generate_sentence(grammar):

return expand(grammar, ["_S"])

def compare_distributions(num_samples=1000):

counts = defaultdict(lambda: [0, 0])

for _ in range(num_samples):

counts[gibbs_sample()][0] += 1

counts[direct_sample()][1] += 1

return counts

文法規則

grammar = {

“_S” : [“_NP _VP”],

“_NP” : [“_N”,

“_A _NP _P _A _N”],

“_VP” : [“_V”,

“_V _NP”],

“_N” : [“data science”, “Python”, “regression”],

“_A” : [“big”, “linear”, “logistic”],

“_P” : [“about”, “near”],

“_V” : [“learns”, “trains”, “tests”, “is”]

}

print "grammar sentences"
for i in range(10):
    print i, " ".join(generate_sentence(grammar))

print "grammar sentences"

for i in range(10):

print i, " ".join(generate_sentence(grammar))

print "gibbs sampling"
comparison = compare_distributions()
for roll, (gibbs, direct) in comparison.iteritems():
    print roll, gibbs, direct

print "gibbs sampling"

comparison = compare_distributions()

for roll, (gibbs, direct) in comparison.iteritems():

print roll, gibbs, direct

備註：2017/06/01 計算方法分析與設計課堂筆記

Decision Tree & 隨機森林 & Neural Networks

Posted on 2017-05-30 by 蕭博元

Github

Kaggle:資料分析競賽

Decision Tree

決策樹只能使用目標是離散型的，不能試數字型態。

Entropy數值越高代表越純

範例 : https://zh.wikipedia.org/wiki/%E5%86%B3%E7%AD%96%E6%A0%91

x=wind

y=no wind

用熵去計算

Entropy = x * log(x,2)

Entropy = y * log(y,2)

選高的推斷哪種原因下去拆

篩選熵當作從哪層往下做

#coding:utf-8
from __future__ import division
from collections import Counter, defaultdict
import math

def entropy(class_probabilities):
    """given a list of class probabilities, compute the entropy"""
    return sum(-p * math.log(p, 2) for p in class_probabilities if p)

def class_probabilities(labels):
    total_count = len(labels)
    return [count / total_count
            for count in Counter(labels).values()]

def data_entropy(labeled_data):
    labels = [label for _, label in labeled_data]
    probabilities = class_probabilities(labels)
    return entropy(probabilities)

def partition_entropy(subsets):
    """find the entropy from this partition of data into subsets"""
    total_count = sum(len(subset) for subset in subsets)
    return sum(data_entropy(subset) * len(subset) / total_count
               for subset in subsets)

def group_by(items, key_fn)
    """returns a defaultdict(list), where each input item
    is in the list whose key is key_fn(item)"""
    groups = defaultdict(list)
    for item in items:
        key = key_fn(item)
        groups[key].append(item)
    return groups

def partition_by(inputs, attribute):
    """returns a dict of inputs partitioned by the attribute
    each input is a pair (attribute_dict, label)"""
    return group_by(inputs, lambda x: x[0][attribute])

def partition_entropy_by(inputs,attribute):
    """computes the entropy corresponding to the given partition"""
    partitions = partition_by(inputs, attribute)
    return partition_entropy(partitions.values())

inputs = [
        ({'level':'Senior','lang':'Java','tweets':'no','phd':'no'},   False),
        ({'level':'Senior','lang':'Java','tweets':'no','phd':'yes'},  False),
        ({'level':'Mid','lang':'Python','tweets':'no','phd':'no'},     True),
        ({'level':'Junior','lang':'Python','tweets':'no','phd':'no'},  True),
        ({'level':'Junior','lang':'R','tweets':'yes','phd':'no'},      True),
        ({'level':'Junior','lang':'R','tweets':'yes','phd':'yes'},    False),
        ({'level':'Mid','lang':'R','tweets':'yes','phd':'yes'},        True),
        ({'level':'Senior','lang':'Python','tweets':'no','phd':'no'}, False),
        ({'level':'Senior','lang':'R','tweets':'yes','phd':'no'},      True),
        ({'level':'Junior','lang':'Python','tweets':'yes','phd':'no'}, True),
        ({'level':'Senior','lang':'Python','tweets':'yes','phd':'yes'},True),
        ({'level':'Mid','lang':'Python','tweets':'no','phd':'yes'},    True),
        ({'level':'Mid','lang':'Java','tweets':'yes','phd':'no'},      True),
        ({'level':'Junior','lang':'Python','tweets':'no','phd':'yes'},False)
    ]

for key in ['level','lang','tweets','phd']:
    print key, partition_entropy_by(inputs, key)

#coding:utf-8

from __future__ import division

from collections import Counter, defaultdict

import math

def entropy(class_probabilities):

"""given a list of class probabilities, compute the entropy"""

return sum(-p * math.log(p, 2) for p in class_probabilities if p)

def class_probabilities(labels):

total_count = len(labels)

return [count / total_count

for count in Counter(labels).values()]

def data_entropy(labeled_data):

labels = [label for _, label in labeled_data]

probabilities = class_probabilities(labels)

return entropy(probabilities)

def partition_entropy(subsets):

"""find the entropy from this partition of data into subsets"""

total_count = sum(len(subset) for subset in subsets)

return sum(data_entropy(subset) * len(subset) / total_count

for subset in subsets)

def group_by(items, key_fn)

"""returns a defaultdict(list), where each input item

is in the list whose key is key_fn(item)"""

groups = defaultdict(list)

for item in items:

key = key_fn(item)

groups[key].append(item)

return groups

def partition_by(inputs, attribute):

"""returns a dict of inputs partitioned by the attribute

each input is a pair (attribute_dict, label)"""

return group_by(inputs, lambda x: x[0][attribute])

def partition_entropy_by(inputs,attribute):

"""computes the entropy corresponding to the given partition"""

partitions = partition_by(inputs, attribute)

return partition_entropy(partitions.values())

inputs = [

({'level':'Senior','lang':'Java','tweets':'no','phd':'no'}, False),

({'level':'Senior','lang':'Java','tweets':'no','phd':'yes'}, False),

({'level':'Mid','lang':'Python','tweets':'no','phd':'no'}, True),

({'level':'Junior','lang':'Python','tweets':'no','phd':'no'}, True),

({'level':'Junior','lang':'R','tweets':'yes','phd':'no'}, True),

({'level':'Junior','lang':'R','tweets':'yes','phd':'yes'}, False),

({'level':'Mid','lang':'R','tweets':'yes','phd':'yes'}, True),

({'level':'Senior','lang':'Python','tweets':'no','phd':'no'}, False),

({'level':'Senior','lang':'R','tweets':'yes','phd':'no'}, True),

({'level':'Junior','lang':'Python','tweets':'yes','phd':'no'}, True),

({'level':'Senior','lang':'Python','tweets':'yes','phd':'yes'},True),

({'level':'Mid','lang':'Python','tweets':'no','phd':'yes'}, True),

({'level':'Mid','lang':'Java','tweets':'yes','phd':'no'}, True),

({'level':'Junior','lang':'Python','tweets':'no','phd':'yes'},False)

]

for key in ['level','lang','tweets','phd']:

print key, partition_entropy_by(inputs, key)

比較哪level與tweets哪種比較好?

print '---level=senior---'
senior_inputs = [(input, label) for input, label in inputs if input["level"] == "Senior"]
for key in ['lang', 'tweets', 'phd']:
    print key, partition_entropy_by(senior_inputs, key)

print '---level=Junior---'
senior_inputs = [(input, label) for input, label in inputs if input["level"] == "Junior"]
for key in ['lang', 'tweets', 'phd']:
    print key, partition_entropy_by(senior_inputs, key)

print '---tweets=yes---'
senior_inputs = [(input, label) for input, label in inputs if input["tweets"] == "yes"]
for key in ['lang', 'tweets', 'phd']:
    print key, partition_entropy_by(senior_inputs, key)

print '---tweets=no---'
senior_inputs = [(input, label) for input, label in inputs if input["tweets"] == "no"]
for key in ['lang', 'tweets', 'phd']:
    print key, partition_entropy_by(senior_inputs, key)

print '---phd=yes---'
senior_inputs = [(input, label) for input, label in inputs if input["phd"] == "yes"]
for key in ['lang', 'tweets', 'phd']:
    print key, partition_entropy_by(senior_inputs, key)

print '---phd=no---'
senior_inputs = [(input, label) for input, label in inputs if input["phd"] == "no"]
for key in ['lang', 'tweets', 'phd']:
    print key, partition_entropy_by(senior_inputs, key)

print '---level=senior---'

senior_inputs = [(input, label) for input, label in inputs if input["level"] == "Senior"]

for key in ['lang', 'tweets', 'phd']: