import json
path = 'ch02/usagov_bitly_data2012-03-16-1331923249.txt'
records = [json.loads(line) for line in open(path)]

records[0]
-----------------------------------
{'a': 'Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/535.11 (KHTML, like Gecko) Chrome/17.0.963.78 Safari/535.11',
 'al': 'en-US,en;q=0.8',
 'c': 'US',
 'cy': 'Danvers',
 'g': 'A6qOVH',
 'gr': 'MA',
 'h': 'wfLQtf',
 'hc': 1331822918,
 'hh': '1.usa.gov',
 'l': 'orofrog',
 'll': [42.576698, -70.954903],
 'nk': 1,
 'r': 'http://www.facebook.com/l/7AQEFzjSi/1.usa.gov/wfLQtf',
 't': 1331923247,
 'tz': 'America/New_York',
 'u': 'http://www.ncbi.nlm.nih.gov/pubmed/22415991'}

time_zones = [rec['tz'] for rec in records if 'tz' in rec]

time_zones[:10]
-----------------------------------
['America/New_York',
 'America/Denver',
 'America/New_York',
 'America/Sao_Paulo',
 'America/New_York',
 'America/New_York',
 'Europe/Warsaw',
 '',
 '',
 '']

def get_counts(sequence):
    counts = {}
    for x in sequence:
        if x in counts:
            counts[x] += 1
        else:
            counts[x] = 1
    return counts

from collections import defaultdict
def get_counts2(sequence):
    counts = defaultdict(int) # values will initialize to 0
    for x in sequence:
        counts[x] += 1
    return counts

def top_counts(count_dict, n=10):
    value_key_pairs = [(count, tz) for tz, count in count_dict.items()]
    value_key_pairs.sort()
    return value_key_pairs[-n:]

top_counts(counts)
--------------------------------------
[(33, 'America/Sao_Paulo'),
 (35, 'Europe/Madrid'),
 (36, 'Pacific/Honolulu'),
 (37, 'Asia/Tokyo'),
 (74, 'Europe/London'),
 (191, 'America/Denver'),
 (382, 'America/Los_Angeles'),
 (400, 'America/Chicago'),
 (521, ''),
 (1251, 'America/New_York')]

from collections import Counter

counts = Counter(time_zones)

counts.most_common(10)
--------------------------------
[('America/New_York', 1251),
 ('', 521),
 ('America/Chicago', 400),
 ('America/Los_Angeles', 382),
 ('America/Denver', 191),
 ('Europe/London', 74),
 ('Asia/Tokyo', 37),
 ('Pacific/Honolulu', 36),
 ('Europe/Madrid', 35),
 ('America/Sao_Paulo', 33)]

from pandas import DataFrame, Series
import pandas as pd
frame = DataFrame(records)
frame

frame['tz'][:10]
-------------------------------
0     America/New_York
1       America/Denver
2     America/New_York
3    America/Sao_Paulo
4     America/New_York
5     America/New_York
6        Europe/Warsaw
7                     
8                     
9                     
Name: tz, dtype: object

tz_counts = frame['tz'].value_counts()
tz_counts[:10]
--------------------------------------------------
America/New_York       1251
                        521
America/Chicago         400
America/Los_Angeles     382
America/Denver          191
Europe/London            74
Asia/Tokyo               37
Pacific/Honolulu         36
Europe/Madrid            35
America/Sao_Paulo        33
Name: tz, dtype: int64

clean_tz = frame['tz'].fillna('Missing')
clean_tz[clean_tz == ''] = 'Unknown'
tz_counts = clean_tz.value_counts()
tz_counts[:10]
----------------------------------------------
America/New_York       1251
Unknown                 521
America/Chicago         400
America/Los_Angeles     382
America/Denver          191
Missing                 120
Europe/London            74
Asia/Tokyo               37
Pacific/Honolulu         36
Europe/Madrid            35
Name: tz, dtype: int64

plt.figure(figsize=(10, 4))
tz_counts[:10].plot(kind='barh', rot=0)

results = Series([x.split()[0] for x in frame.a.dropna()])
results[:5]
---------------------------------------------------
0               Mozilla/5.0
1    GoogleMaps/RochesterNY
2               Mozilla/4.0
3               Mozilla/5.0
4               Mozilla/5.0
dtype: object

results.value_counts()[:8]
-----------------------------------------
Mozilla/5.0                 2594
Mozilla/4.0                  601
GoogleMaps/RochesterNY       121
Opera/9.80                    34
TEST_INTERNET_AGENT           24
GoogleProducer                21
Mozilla/6.0                    5
BlackBerry8520/5.0.0.681       4
dtype: int64

cframe = frame[frame.a.notnull()]

operating_system = np.where(cframe['a'].str.contains('Windows'),
                            'Windows', 'Not Windows')
operating_system[:5]
-----------------------------------------------------------------
array(['Windows', 'Not Windows', 'Windows', 'Not Windows', 'Windows'], 
      dtype='<U11')

by_tz_os = cframe.groupby(['tz', operating_system])

# Use to sort in ascending order
indexer = agg_counts.sum(1).argsort()
indexer[:10]
------------------------------------------------
tz
                                  24
Africa/Cairo                      20
Africa/Casablanca                 21
Africa/Ceuta                      92
Africa/Johannesburg               87
Africa/Lusaka                     53
America/Anchorage                 54
America/Argentina/Buenos_Aires    57
America/Argentina/Cordoba         26
America/Argentina/Mendoza         55
dtype: int64

count_subset = agg_counts.take(indexer)[-10:]
count_subset

count_subset.plot(kind='barh', stacked=True)

normed_subset = count_subset.div(count_subset.sum(1), axis=0)
normed_subset.plot(kind='barh', stacked=True)

import pandas as pd
import os
encoding = 'latin1'
upath = os.path.expanduser('ch02/movielens/users.dat')
rpath = os.path.expanduser('ch02/movielens/ratings.dat')
mpath = os.path.expanduser('ch02/movielens/movies.dat')
unames = ['user_id', 'gender', 'age', 'occupation', 'zip']
rnames = ['user_id', 'movie_id', 'rating', 'timestamp']
mnames = ['movie_id', 'title', 'genres']
users = pd.read_csv(upath, sep='::', header=None, names=unames, encoding=encoding)
ratings = pd.read_csv(rpath, sep='::', header=None, names=rnames, encoding=encoding)
movies = pd.read_csv(mpath, sep='::', header=None, names=mnames, encoding=encoding)

users[:5]

ratings[:5]

movies[:5]

data = pd.merge(pd.merge(ratings, users), movies)
data

mean_ratings = data.pivot_table('rating', index='title',
                                columns='gender', aggfunc='mean')
mean_ratings[:5]

ratings_by_title = data.groupby('title').size()

active_titles = ratings_by_title.index[ratings_by_title >= 250]

mean_ratings = mean_ratings.ix[active_titles]
mean_ratings

top_female_ratings = mean_ratings.sort_values(by='F', ascending=False)
top_female_ratings[:10]

import pandas as pd
names1880 = pd.read_csv('ch02/names/yob1880.txt', names=['name', 'sex', 'births'])
names1880

# 2010 is the last available year right now
years = range(1880, 2011)
pieces = []
columns = ['name', 'sex', 'births']
for year in years:
    path = 'ch02/names/yob%d.txt' % year
    frame = pd.read_csv(path, names=columns)
    frame['year'] = year
    pieces.append(frame)
# Concatenate everything into a single DataFrame
names = pd.concat(pieces, ignore_index=True)

total_births = names.pivot_table('births', index='year',
                                 columns='sex', aggfunc=sum)

total_births.tail()

def add_prop(group):
    # Integer division floors
    births = group.births.astype(float)
    group['prop'] = births / births.sum()
    return group
names = names.groupby(['year', 'sex']).apply(add_prop)

names

np.allclose(names.groupby(['year', 'sex']).prop.sum(), 1)
--------------------------------------------
True

def get_top1000(group):
    return group.sort_values(by='births', ascending=False)[:1000]
grouped = names.groupby(['year', 'sex'])
top1000 = grouped.apply(get_top1000)

top1000.index = np.arange(len(top1000))

boys = top1000[top1000.sex == 'M']
girls = top1000[top1000.sex == 'F']

total_births = top1000.pivot_table('births', index='year', columns='name',
                                   aggfunc=sum)
total_births

subset = total_births[['John', 'Harry', 'Mary', 'Marilyn']]
subset.plot(subplots=True, figsize=(12, 10), grid=False,
            title="Number of births per year")

table = top1000.pivot_table('prop', index='year',
                            columns='sex', aggfunc=sum)
table.plot(title='Sum of table1000.prop by year and sex',
           yticks=np.linspace(0, 1.2, 13), xticks=range(1880, 2020, 10))

df = boys[boys.year == 2010]

prop_cumsum = df.sort_index(by='prop', ascending=False).prop.cumsum()
prop_cumsum[:10]
--------------------------------------------------
260877    0.011523
260878    0.020934
260879    0.029959
260880    0.038930
260881    0.047817
260882    0.056579
260883    0.065155
260884    0.073414
260885    0.081528
260886    0.089621
Name: prop, dtype: float64

prop_cumsum.values.searchsorted(0.5)
---------------------------------------------------
116

df = boys[boys.year == 1900]
in1900 = df.sort_index(by='prop', ascending=False).prop.cumsum()
in1900.values.searchsorted(0.5) + 1
---------------------------------------------------
25

def get_quantile_count(group, q=0.5):
    group = group.sort_values(by='prop', ascending=False)
    return group.prop.cumsum().values.searchsorted(q) + 1
diversity = top1000.groupby(['year', 'sex']).apply(get_quantile_count)
diversity = diversity.unstack('sex')
diversity.head()

diversity.plot(title="Number of popular names in top 50%")

# extract last letter from name column
get_last_letter = lambda x: x[-1]
last_letters = names.name.map(get_last_letter)
last_letters.name = 'last_letter'
table = names.pivot_table('births', index=last_letters,
                          columns=['sex', 'year'], aggfunc=sum)

subtable = table.reindex(columns=[1910, 1960, 2010], level='year')
subtable.head()

subtable.sum()
-------------------------------------
sex  year
F    1910     396416.0
     1960    2022062.0
     2010    1759010.0
M    1910     194198.0
     1960    2132588.0
     2010    1898382.0
dtype: float64

letter_prop = subtable / subtable.sum().astype(float)

import matplotlib.pyplot as plt
fig, axes = plt.subplots(2, 1, figsize=(10, 8))
letter_prop['M'].plot(kind='bar', rot=0, ax=axes[0], title='Male')
letter_prop['F'].plot(kind='bar', rot=0, ax=axes[1], title='Female',
                      legend=False)

letter_prop = table / table.sum().astype(float)
dny_ts = letter_prop.ix[['d', 'n', 'y'], 'M'].T

dny_ts.plot()

all_names = top1000.name.unique()
mask = np.array(['lesl' in x.lower() for x in all_names])
lesley_like = all_names[mask]
lesley_like
----------------------------------------------
array(['Leslie', 'Lesley', 'Leslee', 'Lesli', 'Lesly'], dtype=object)

filtered = top1000[top1000.name.isin(lesley_like)]
filtered.groupby('name').births.sum()
----------------------------------------------
name
Leslee      1082
Lesley     35022
Lesli        929
Leslie    370429
Lesly      10067
Name: births, dtype: int64

table = filtered.pivot_table('births', index='year',
                             columns='sex', aggfunc='sum')
table = table.div(table.sum(1), axis=0)
table.tail()

table.plot(style={'M': 'k-', 'F': 'k--'})

"""	<A spider to crawl the house information.>
    Copyright (C) <2017>  Li W.H., Duan X
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.
    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>. 
"""
class HouseSpider(scrapy.Spider):
    name = "house"
    head = "http://esf.sh.fang.com"
    allowed_domains = ["sh.fang.com"]
    start_urls = [
        "http://esf.sh.fang.com/housing/"
    ]
    # 各区对应的编号（由于丧心病狂的url）
    area_map = {25: 'pudong', 18: 'minhang', 19: 'xuhui', 30: 'baoshan',
                28: 'putuo', 20: 'changning', 26: 'yangpu', 586: 'songjiang',
                29: 'jiading', 23: 'hongkou', 27: 'zhabei', 21: 'jingan',
                24: 'huangpu', 22: 'luwan', 31: 'qingpu', 32: 'fengxian',
                35: 'jinshan', 996: 'chongming'}
    estate_to_area_map = {}
    seperator = '=\n'
    def __init__(self):
        for key, value in self.area_map.items():
            self.estate_to_area_map[key] = []
        # print(self.estate_to_area_map)
    def parse(self, response):
        # 解析出上海市各区的地址
        area_lis = response.xpath('//*[@id="houselist_B03_02"]/div[1]')
        for a in area_lis.xpath('./a'):
            # areas = items.AreaItem()
            # areas['name'] = a.xpath('text()').extract()[0]
            yield Request(self.head + a.xpath('@href').extract()[0],
                          callback=self.parse_area)
            # print(a.xpath('text()').extract()[0])
    def parse_area(self, response):
        # 确定response来源于哪一个区
        area_index = str(response).split('/')[-2].split('_')[0]
        if area_index == '':
            return
        else:
            # 解析出各区中小区的详情页面地址
            detail_str = 'xiangqing'
            estate_list = response.xpath('/html/body/div[4]/div[5]/div[4]')
            for a in estate_list.xpath('.//a[@class="plotTit"]'):
                estate_url = a.xpath('@href').extract()[0]
                if estate_url.find('esf') != -1:
                    estate_url = estate_url.replace('esf', detail_str)
                else:
                    estate_url = estate_url + detail_str
                if estate_url.find('http') != -1:
                    # print(estate_url)
                    self.estate_to_area_map[int(area_index)].append(estate_url)
            # print(len(self.estate_to_area_map[int(area_index)]))
            next_page = response.xpath('//*[@id="PageControl1_hlk_next"]')
            if len(next_page) != 0:
                yield Request(self.head +
                              next_page.xpath('@href').extract()[0],
                              callback=self.parse_area)
            else:
                # print(len(self.estate_to_area_map[int(area_index)]))
                for url in self.estate_to_area_map[int(area_index)]:
                    request = Request(url, callback=self.parse_house,
                                      dont_filter=True)
                    request.meta['index'] = int(area_index)
                    yield request
    def parse_house(self, response):
        flag = 0
        area_index = response.meta['index']
        area_name = self.area_map[area_index]
        filename = area_name + '.txt'
        # print(response.xpath('/html'))
        # 详情页面存在两种，因此分情况讨论
        house_name = response.xpath(
            '/html/body/div[4]/div[2]/div[2]/h1/a/text()')
        if len(house_name) == 0:
            # house_name = response.xpath(
            #     '/html/body/div[1]/div[3]/div[2]/h1/a/text()')
            # flag = 1
            return
        house_name = house_name.extract()[0]
        # 清洁小区名
        house_name = re.sub(r'小区网', '', house_name)
        result_str = '【小区名称】' + house_name + '\n'
        if flag == 0:
            avg_price_xpath = response.xpath(
                '/html/body/div[4]/div[4]/div[1]/div[1]/dl[1]/dd/span/text()')
            avg_price = avg_price_xpath.extract()[0]
            result_str = result_str + '【平均价格】' + avg_price + '\n'
            detail_block_list = response.xpath(
                '/html/body/div[4]/div[4]/div[1]')
            for headline in detail_block_list.xpath('.//h3'):
                head_str = headline.xpath('./text()').extract()[0]
                if head_str == '基本信息':
                    result_str = result_str + \
                        '【' + \
                        head_str + '】\n'
                    for item in headline.xpath(
                            '../../div[@class="inforwrap clearfix"]/dl/dd'):
                        if len(item.xpath('./strong/text()')) != 0:
                            if len(item.xpath('./text()')) != 0:
                                result_str = result_str + \
                                    item.xpath(
                                        './strong/text()').extract()[0]
                                result_str = result_str + \
                                    item.xpath('./text()').extract()[0] + '\n'
                    # print(result_str)
                # elif head_str == '交通状况':
                #     result_str = result_str + \
                #         '【' + \
                #         head_str + '】\n'
                #     tempstr = headline.xpath(
                #         '../../div[@class="inforwrap clearfix"]/dl/dt/text()').extract()[0]
                #     result_str = result_str + tempstr + '\n'
                #     # print(result_str)
                # elif head_str == '周边信息':
                #     result_str = result_str + \
                #         '【' + \
                #         head_str + '】\n'
                #     for item in headline.xpath(
                #             '../../div[@class="inforwrap clearfix"]/dl/dt'):
                #         result_str = result_str + \
                #             item.xpath('./text()').extract()[0] + '\n'
                #     # print(result_str)
                elif head_str == '就近楼群':
                    result_str = result_str + \
                        '【' + \
                        head_str + '】\n'
                    for item in headline.xpath(
                            '../../div[@class="inforwrap clearfix"]/dl/dd'):
                        result_str = result_str + \
                            item.xpath('./a/text()').extract()[0] + '\n'
            result_str = result_str + self.seperator
            # print(result_str)
            with open(filename, 'a', errors='ignore') as f:
                f.write(result_str)

""" <A formatter>
    Copyright (C) <2017>  Li W.H., Duan X
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.
    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
"""
def GetDataFileList(path='.'):
    """ Get the houses file list.
    Arguments:
        path: Dir path.
    Returns:
        file_list: the list of data file that find houses data.
    """
    file_list = [x for x in os.listdir(path) if os.path.isfile(
        x) and os.path.splitext(x)[1] == '.txt']
    return file_list
def Parse(file_list):
    """ Parse the txt file that find houses data.
    Extract some import infomation such as house name,
    avarage price, address and so on.
    Arguments:
        file_list: the list of data file that find houses data.
    Returns:
        houses_dict_list: the list that each item find the detail
                          dict of each house.
    """
    HOUSE_NAME = '小区名称'
    HOUSE_NAME_SPLITOR = '】'
    HOUSE_ADDRESS = '小区地址'
    HOUSE_ADDRESS_SPLITOR = '：'
    HOUSE_AVG_PRICE = '平均价格'
    HOUSE_AVG_PRICE_SPLITOR = '】'
    AREA_OF_HOUSE_BELONGS_TO = '所属区域'
    AREA_OF_HOUSE_BELONGS_TO_SPLITOR_1 = '：'
    AREA_OF_HOUSE_BELONGS_TO_SPLITOR_2 = ' '
    PROPERTY_CATEGORY = '物业类别'
    PROPERTY_CATEGORY_SPLITOR = '：'
    GREEN_RATE = '绿 化 率'
    GREEN_RATE_SPLITOR = '：'
    VOLUME_RATE = '容 积 率'
    VOLUME_RATE_SPLITOR = '：'
    PROPERTY_COSTS = '物 业 费'
    PROPERTY_COSTS_SPLITOR = '：'
    NO_INFO_NOW = '暂无信息'
    DETAIL_LIST = [HOUSE_NAME, HOUSE_AVG_PRICE, HOUSE_ADDRESS, AREA_OF_HOUSE_BELONGS_TO,
                   PROPERTY_CATEGORY, GREEN_RATE, VOLUME_RATE, PROPERTY_COSTS]
    houses_dict_list = []
    for file_name in file_list:
        raw_houses_string = ''
        # read all lines as a string
        with open(file_name, 'r', errors='ignore') as f:
            for line in f.readlines():
                raw_houses_string += line
        # split the string to the houses raw info list
        raw_houses_list = raw_houses_string.split('=\n')
        raw_houses_details_list = []
        for raw_house in raw_houses_list:
            # format house raw info to lines
            raw_houses_details = raw_house.split('\n')[:-1]
            if len(raw_houses_details) == 0:
                continue
            # combine the all formated house raw info to a list
            raw_houses_details_list.append(raw_houses_details)
        for raw_house_details in raw_houses_details_list:
            house_details_dict = {}
            for raw_detail in raw_house_details:
                # search house name
                if re.search(HOUSE_NAME, raw_detail):
                    house_details_dict[HOUSE_NAME] = raw_detail.split(
                        HOUSE_NAME_SPLITOR)[-1]
                # search house avarage price
                elif re.search(HOUSE_AVG_PRICE, raw_detail):
                    # print(raw_detail)
                    house_details_dict[HOUSE_AVG_PRICE] = raw_detail.split(
                        HOUSE_AVG_PRICE_SPLITOR)[-1]
                # search house address
                elif re.search(HOUSE_ADDRESS, raw_detail):
                    house_details_dict[HOUSE_ADDRESS] = raw_detail.split(
                        HOUSE_ADDRESS_SPLITOR)[-1]
                # search the area of house belongs to
                elif re.search(AREA_OF_HOUSE_BELONGS_TO, raw_detail):
                    temp_detail_value = raw_detail.split(
                        AREA_OF_HOUSE_BELONGS_TO_SPLITOR_1)[-1]
                    detail_value = temp_detail_value.split(
                        AREA_OF_HOUSE_BELONGS_TO_SPLITOR_2)[0]
                    house_details_dict[AREA_OF_HOUSE_BELONGS_TO] = detail_value
                # search the property category of house
                elif re.search(PROPERTY_CATEGORY, raw_detail):
                    house_details_dict[PROPERTY_CATEGORY] = raw_detail.split(
                        PROPERTY_CATEGORY_SPLITOR)[-1]
                # search the green rate
                elif re.search(GREEN_RATE, raw_detail):
                    house_details_dict[GREEN_RATE] = raw_detail.split(
                        GREEN_RATE_SPLITOR)[-1]
                # search the volume rate
                elif re.search(VOLUME_RATE, raw_detail):
                    house_details_dict[VOLUME_RATE] = raw_detail.split(
                        VOLUME_RATE_SPLITOR)[-1]
                # search the property costs
                elif re.search(PROPERTY_COSTS, raw_detail):
                    house_details_dict[PROPERTY_COSTS] = raw_detail.split(
                        PROPERTY_COSTS_SPLITOR)[-1]
            # Judge if all details are contained.
            # If not, set to null.
            house_details_dict_keys = house_details_dict.keys()
            for detail_name in DETAIL_LIST:
                if detail_name not in house_details_dict_keys:
                    house_details_dict[detail_name] = NO_INFO_NOW
            houses_dict_list.append(house_details_dict)
    return houses_dict_list

""" <A toolto transfer position.>
    Copyright (C) <2017>  Li W.H., Duan X
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.
    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
"""
def Geocode(address):
    """ A tool that call the God-Map api.
    Arguments:
        address: the address to transfer.
    Returns:
        location: the transfered location.
    """
    CITY_NAME = '上海'
    parameters = {'address': address,
                  'key': 'your key',
                  'city': CITY_NAME}
    base = 'http://restapi.amap.com/v3/geocode/geo'
    try:
        response = requests.get(base, parameters)
    except Exception as e:
        print('error!', e)
    finally:
        pass
    answer = response.json()
    return answer
def GETGodMapLocation(houses):
    """ Get the location that corresponds to the house name.
    Use the God-Map api to get the corresponding location.
    Arguments:
        houses_dict_list: the houses info.
    Returns:
        houses_dict_list_contains_loc: the houses info that
                                           contains the location info.
    """
    HOUSE_NAME = '小区名称'
    HOUSE_LOCATION = '经纬度'
    NO_INFO_NOW = '暂无信息'
    houses_dict_list = houses.copy()
    error_count = 0
    count = 0
    size = len(houses)
    for house_dict in houses_dict_list:
        # Count
        count = count + 1
        # Loading needs
        if count % 1000 == 0:
            print(count, '/', size)
        address = house_dict[HOUSE_NAME]
        answer = Geocode(address)
        # print(answer)
        # If find
        if len(answer['geocodes']) != 0:
            # print(address + "的经纬度：", answer['geocodes'][0]['location'])
            house_dict[HOUSE_LOCATION] = answer['geocodes'][0]['location']
        else:
            # remaking the invalid address
            # print('address remaking...')
            if re.search(r'别墅', address):
                re.sub(r'别墅', '', address)
            else:
                address = address + '小区'
            # print('retransfering...')
            # transfer again
            answer = Geocode(address)
            if len(answer['geocodes']) != 0:
                # print(address + "的经纬度：", answer['geocodes'][0]['location'])
                house_dict[HOUSE_LOCATION] = answer['geocodes'][0]['location']
            else:
                # print(address)
                error_count += 1
                house_dict[HOUSE_LOCATION] = NO_INFO_NOW
    print('error counts: ', error_count)
    return houses_dict_list

""" <A tool to save the excel file.>
    Copyright (C) <2017>  Li W.H., Duan X
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.
    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
"""
        
def Save2ExcelFile(houses):
    """ Save the python based list file to excel file.
    Arguments:
        houses: the houses list.
    """
    houses_dict_list = houses.copy()
    house_list = []
    # format the source data to fit the xlwt package
    keys = houses[0].keys()
    for key in keys:
        house = []
        house.append(key)
        for house_dict in houses_dict_list:
            house.append(house_dict[key])
        house_list.append(house)
    # return house_list
    xls = ExcelWrite.Workbook()
    sheet = xls.add_sheet('小区信息')
    for i in range(len(house_list)):
        for j in range(len(house_list[0])):
            sheet.write(j, i, house_list[i][j])
    xls.save('houses.xls')

#!/usr/bin/env python3
#-*- coding:utf-8 -*-
'''
利用高德地图api实现地址和经纬度的转换
'''
import requests
def geocode(address):
        parameters = {'address': address, 'key': 'e798a5bfb344a09977b79552ae415974'}
        base = 'http://restapi.amap.com/v3/geocode/geo'
        response = requests.get(base, parameters)
        answer = response.json()
        print(address + "的经纬度：", answer['geocodes'][0]['location'])
if __name__=='__main__':
        #address = input("请输入地址:")
        address = '北京市海淀区'
        geocode(address)

import xlrd
def readXlsx(self, filename='CenterBottom2013.xlsx', sheetname='Sheet1'):
        rawData = []
        if (os.path.isfile(self.fn_rawDat)):
            with open(self.fn_rawDat, 'rb') as f:
                self.rawDat = np.load(f)
        else:
            workBook = xlrd.open_workbook(filename)
            bookSheet = workBook.sheet_by_name(sheetname)
            # 从第二行开始读取，因为第一行有标签
            for row in range(1, bookSheet.nrows):
                rowData = []
                for col in range(bookSheet.ncols):
                    cel = bookSheet.cell(row, col)
                    try:
                        val = cel.value
                    except:
                        pass
                    if type(val) == float:
                        val = float(val)
                    else:
                        val = str(val)
                    rowData.append(val)
                rawData.append(rowData)
            self.rawDat = np.array(rawData)
            with open(self.fn_rawDat, 'wb') as f:
                np.save(f, self.rawDat)
        return self.rawDat

from numpy import *

def createDataset():
    group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels

def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances**0.5
    sortedDistIndices = distances.argsort()
    classCount = {}
    for i in range(k):
        voteIlabel = labels[sortedDistIndices[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    # the return of sorted() is a list and its item is a tuple
    sortedClassCount = sorted(classCount.items(),
                             key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0] # returns the predict class label

import numpy as np
from kdTreeNode import *
def createDataSet():
    """ Create the test dataset.
    Returns:
        A numpy array that contains the test data.
    """
    dataSet = np.array([[2, 3], [5, 4], [9, 6],
                        [4, 7], [8, 1], [7, 2]])
    return dataSet
def split(dataSet):
    """ Split the given dataset.
    Returns:
        LeftDataSet: A kdTreeNode object.
        RightDataSet: A kdTreeNode object.
        NodeData: A tuple.
    """
    # Ensure the dimension to split
    dimenIndex = np.var(dataSet, axis=0).argmax()
    partitionDataSet = dataSet[:, dimenIndex]
    # print(partitionDataSet)
    # Ensure the position to split
    partitionDataSetArgSort = partitionDataSet.argsort()
    # print(partitionDataSetArgSort)
    lenOfPartitionDataSetArgSort = len(partitionDataSetArgSort)
    if lenOfPartitionDataSetArgSort % 2 == 0:
        posIndex = lenOfPartitionDataSetArgSort // 2
        splitIndex = partitionDataSetArgSort[posIndex]
    else:
        posIndex = (lenOfPartitionDataSetArgSort - 1) // 2
        splitIndex = partitionDataSetArgSort[posIndex]
    # print(splitIndex)
    # Split
    nodeData = dataSet[splitIndex]
    leftIndeies = partitionDataSetArgSort[:posIndex]
    rightIndeies = partitionDataSetArgSort[posIndex + 1:]
    leftDataSet = dataSet[leftIndeies]
    rightDataSet = dataSet[rightIndeies]
    return nodeData, dimenIndex, leftDataSet, rightDataSet
def createKDTree(dataSet):
    """ Create the KD tree.
    Returns:
        A kdTreeNode object.
    """
    if len(dataSet) == 0:
        return
    nodeData, dimenIndex, leftDataSet, rightDataSet = split(dataSet)
    # print(nodeData, dimenIndex, leftDataSet, rightDataSet)
    node = kdTreeNode(nodeData, dimenIndex)
    node.setLeft(createKDTree(leftDataSet))
    node.setRight(createKDTree(rightDataSet))
    return node
def midTravel(node):
    if node is None:
        return
    midTravel(node.getLeft())
    print(node.getData())
    midTravel(node.getRight())
if __name__ == "__main__":
    dataSet = createDataSet()
    node = createKDTree(dataSet)
    midTravel(node)

class kdTreeNode(object):
    """ Class of k-d tree nodes
    """
    def __init__(self, data=None, split=None, left=None, right=None):
        self.__data = data
        self.__split = split
        self.__left = left
        self.__right = right
    def getData(self):
        return self.__data
    def setData(self, data):
        self.__data = data
    def getSplit(self):
        return self.__split
    def setSplit(self, split):
        self.__split = split
    def getLeft(self):
        return self.__left
    def setLeft(self, left):
        self.__left = left
    def getRight(self):
        return self.__right
    def setRight(self, right):
        self.__right = right

import numpy as np
def cal_dist(node, target):
    """ Calculate the distance between the node
    and the target.
    Arguments:
        node: The kd-tree's one node.
        target: Search target.
    Returns:
        dist: The distance between the two nodes.
    """
    node_data = np.array(node)
    target_data = np.array(target)
    square_dist_vector = (node_data - target_data) ** 2
    square_dist = np.sum(square_dist_vector)
    dist = square_dist ** 0.5
    return dist
def search(root_node, target):
    """ Search the nearest node of the target node
    in the kd-tree that root node is the root_node
    Arguments:
        root_node: The kd-tree's root node.
        target: Search target.
    Returns:
        nearest: The nearest node of the target node in the kd-tree.
        min_dist: The nearest distance.
    """
    if root_node is None:
        min_dist = float('inf')
        return min_dist
    # Two-fork search
    kd_point = root_node    # Save the root node
    nearest = kd_point.getData()    # Initial the nearest node
    search_path = []    # Initial the search stack
    while kd_point:
        search_path.append(kd_point)
        split_index = kd_point.getSplit()   # Ensure the split path
        if target[split_index] <= kd_point.getData()[split_index]:
            kd_point = kd_point.getLeft()
        else:
            kd_point = kd_point.getRight()
    nearest = search_path.pop().getData()
    min_dist = cal_dist(nearest, target)
    # Retrospect search
    while search_path:
        back_point = search_path.pop()
        # Ensure the back-split path
        back_split_index = back_point.getSplit()
        # Judge if needs to enter the subspace
        if cal_dist(target[back_split_index],
                back_point.getData()[back_split_index]) < min_dist:
            # If the target is in the left subspace, then enter the right
            if target[back_split_index] <= back_point.getData()[back_split_index]:
                kd_point = back_point.getRight()
            # Otherwise enter the left
            else:
                kd_point = back_point.getLeft()
            # Add the node to the search path
            if kd_point is not None:
                search_path.append(kd_point)
                if cal_dist(nearest, target) > cal_dist(kd_point.getData(), target):
                    # Update the nearest node
                    nearest = kd_point.getData()
                    # Update the maximum distance
                    min_dist = cal_dist(kd_point.getData(), target)
    return nearest, min_dist

createbranch()
检测数据集中的每个子项是否属于同一分类:
	If so return 类标签;
	Else
		寻找划分数据集的最好特征
		划分数据集
		创建分支节点
			for 每个划分的子集
				调用函数createBranch并增加返回结果到分支节点中
		return 分支节点

from math import log
def CalcShannonEnt(data_set):
    """ Calculate the Shannon Entropy.
    Arguments:
        data_set: The object dataset.
    Returns:
        shannon_ent: The Shannon entropy of the object data set.
    """
    # Initiation
    num_entries = len(data_set)
    label_counts = {}
    # Statistics the frequency of each class in the dataset
    for feat_vec in data_set:
        current_label = feat_vec[-1]
        if current_label not in label_counts.keys():
            label_counts[current_label] = 0
        label_counts[current_label] += 1
    # Calculates the Shannon entropy
    shannon_ent = 0.0
    for key in label_counts:
        prob = float(label_counts[key]) / num_entries
        shannon_ent -= prob * log(prob, 2)
    return shannon_ent

def CreateDataSet():
    """ A naive data generation method.
    Returns:
        data_set: The data set excepts label info.
        labels: The data set only contains label info.
    """
    data_set = [[1, 1, 'yes'],
                [1, 1, 'yes'],
                [1, 0, 'no'],
                [0, 1, 'no'],
                [0, 1, 'no']]
    labels = ['no surfacing', 'flippers']
    return data_set, labels

In [22]: import trees
In [23]: my_dat, labels = trees.CreateDataSet()
In [24]: my_dat
Out[24]: [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
In [25]: trees.CalcShannonEnt(my_dat)
Out[25]: 0.9709505944546686

def CalcGiniImpurity(data_set):
    """ Calculate the Gini impurity.
    Arguments:
        data_set: The object dataset.
    Returns:
        gini_impurity: The Gini impurity of the object data set.
    """
    # Initiation
    num_entries = len(data_set)
    label_counts = {}
    # Statistics the frequency of each class in the dataset
    for feat_vec in data_set:
        current_label = feat_vec[-1]
        if current_label not in label_counts.keys():
            label_counts[current_label] = 0
        label_counts[current_label] += 1
    # Calculates the Gini impurity
    gini_impurity = 0.0
    for key in label_counts:
        prob = float(label_counts[key]) / num_entries
        gini_impurity += pow(prob, 2)
    gini_impurity = 1 - gini_impurity
    return gini_impurity

In [4]: import trees
In [5]: my_dat, labels = trees.CreateDataSet()
In [6]: my_dat
Out[6]: [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
In [7]: trees.CalcGiniImpurity(my_dat)
Out[7]: 0.48

def CalcMisClassifyImpurity(data_set):
    """ Calculate the misclassification impurity.
    Arguments:
        data_set: The object dataset.
    Returns:
        mis_classify_impurity: The misclassification impurity of the object data set.
    """
    # Initiation
    num_entries = len(data_set)
    label_counts = {}
    # Statistics the frequency of each class in the dataset
    for feat_vec in data_set:
        current_label = feat_vec[-1]
        if current_label not in label_counts.keys():
            label_counts[current_label] = 0
        label_counts[current_label] += 1
    # Calculates the misclassification impurity
    mis_classify_impurity = 0.0
    max_prob = max(label_counts.values()) / num_entries
    mis_classify_impurity = 1 - max_prob
    return mis_classify_impurity

In [25]: reload(trees)
Out[25]: <module 'trees' from 'C:\\Users\\Ewan\\Documents\\GitHub\\hexo\\public\\2017\\02\\15\\Decision-tree\\trees.py'>
In [26]: my_dat, labels = trees.CreateDataSet()
In [27]: my_dat
Out[27]: [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
In [28]: trees.CalcMisClassifyImpurity(my_dat)
Out[28]: 0.4

def SplitDataSet(data_set, axis, value):
    """ Split the data set according to the given axis and correspond value.
    Arguments:
        data_set: Object data set.
        axis: The split-feature index.
        value: The value of the split-feature.
    Returns:
        ret_data_set: The splited data set.
    """
    
    ret_data_set = []
    for feat_vec in data_set:
        if feat_vec[axis] == value:
            reduced_feat_vec = feat_vec[:axis]
            reduced_feat_vec.extend(feat_vec[axis + 1:])
            ret_data_set.append(reduced_feat_vec)
    return ret_data_set
def ChooseBestFeatureToSplit(data_set):
    """ Choose the best feature to split.
    Arguments:
        data_set: Object data set.
    Returns:
        best_feature: The index of the feature to split.
    """
    
    # Initiation
    # Because the range() method excepts the lastest number
    num_features = len(data_set[0]) - 1
    base_entropy = CalcShannonEnt(data_set)
    best_info_gain = 0.0
    best_feature = -1
    for i in range(num_features):
        # Choose the i-th feature of all data
        feat_list = [example[i] for example in data_set]
        # Abandon the repeat feature value(s)
        unique_vals = set(feat_list)
        new_entropy = 0.0
        # Calculates the Shannon entropy of the splited data set
        for value in unique_vals:
            sub_data_set = SplitDataSet(data_set, i, value)
            prob = len(sub_data_set) / len(data_set)
            new_entropy += prob * CalcShannonEnt(sub_data_set)
        # base_entropy is equal or greatter than new_entropy
        info_gain = base_entropy - new_entropy
        if info_gain > best_info_gain:
            best_info_gain = info_gain
            best_feature = i
    return best_feature

def majority_cnt(class_list):
    """ Decided the final class.
    When the splited data is not belongs to the same class
    while all feature is handled, the final class is decided by
    the majority class.
    Arguments:
        class_list: The class list of the splited data set.
    Returns:
        sorted_class_count[0][0]: The majority class.
    """
    
    class_count = {}
    for vote in class_list:
        if vote not in class_count.keys():
            class_count[vote] = 0
        class_count[vote] += 1
    sorted_class_count = sorted(
        class_count.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sorted_class_count[0][0]

def CreateTree(data_set, labels):
    """ Create decision tree.
    Arguments:
        data_set: The object data set.
        labels: The feature labels in the data_set.
    Returns:
        my_tree: A dict that represents the decision tree.
    """
    class_list = [example[-1] for example in data_set]
    # If the classes are fully same
    if class_list.count(class_list[0]) == len(class_list):
        return class_list[0]
    # If all feature is handled
    if len(data_set[0]) == 1:
        return majority_cnt(class_list)
    # Get the best split-feature and the correspond label
    best_feat = ChooseBestFeatureToSplit(data_set)
    best_feat_label = labels[best_feat]
    # Build a recurrence dict
    my_tree = {best_feat_label: {}}
    # Get the next step labels parameter
    del(labels[best_feat])
    # Next step start
    feat_values = [example[best_feat] for example in data_set]
    unique_vals = set(feat_values)
    for value in unique_vals:
        sub_labels = labels[:]
        # Recurrence calls
        my_tree[best_feat_label][value] = CreateTree(
            SplitDataSet(data_set, best_feat, value), sub_labels)
    return my_tree

In [27]: reload(trees)
Out[27]: <module 'trees' from 'C:\\Users\\Ewan\\Documents\\GitHub\\hexo\\public\\2017\\02\\15\\Decision-tree\\trees.py'>
In [28]: my_dat, labels = trees.CreateDataSet()
In [29]: my_tree = trees.CreateTree(my_dat, labels)
In [30]: my_tree
Out[30]: {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

In [63]: reload(trees)
Out[63]: <module 'trees' from 'C:\\Users\\Ewan\\Documents\\GitHub\\hexo\\public\\2017\\02\\15\\Decision-tree\\trees.py'>
In [64]: my_dat, labels = trees.CreateDataSet()
In [65]: labels
Out[65]: ['no surfacing', 'flippers']
In [66]: my_tree = trees.CreateTree(my_dat, labels)
In [67]: labels
Out[67]: ['no surfacing', 'flippers']
In [68]: my_tree
Out[68]: {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
In [69]: trees.Classify(my_tree, labels, [1, 0])
Out[69]: 'no'
In [70]: trees.Classify(my_tree, labels, [1, 1])
Out[70]: 'yes'

def ChooseBestFeatureToSplit(data_set, flag='ID3'):
    """ Choose the best feature to split.
    Arguments:
        data_set: Object data set.
        flag: Decide if use the infomation gain rate or not.
    Returns:
        best_feature: The index of the feature to split.
    """
    # Initiation
    # Because the range() method excepts the lastest number
    num_features = len(data_set[0]) - 1
    base_entropy = CalcShannon(data_set)
    method = 'ID3'
    best_feature = -1
    best_info_gain = 0.0
    best_info_gain_rate = 0.0
    for i in range(num_features):
        new_entropy = 0.0
        # Choose the i-th feature of all data
        feat_list = [example[i] for example in data_set]
        # Abandon the repeat feature value(s)
        unique_vals = set(feat_list)
        if len(unique_vals) > 3:
            method = 'C4.5'
        if method == 'ID3':
            # Calculates the Shannon entropy of the splited data set
            for value in unique_vals:
                sub_data_set = SplitDataSet(data_set, i, value)
                prob = len(sub_data_set) / len(data_set)
                new_entropy += prob * CalcShannon(sub_data_set)
        else:
            data_set = np.array(data_set)
            sorted_feat = np.argsort(feat_list)
            for index in range(len(sorted_feat) - 1):
                pre_sorted_feat, post_sorted_feat = np.split(
                    sorted_feat, [index + 1, ])
                pre_data_set = data_set[pre_sorted_feat]
                post_data_set = data_set[post_sorted_feat]
                pre_coff = len(pre_sorted_feat) / len(sorted_feat)
                post_coff = len(post_sorted_feat) / len(sorted_feat)
                # Calucate the split info
                iv = pre_coff * CalcShannon(pre_data_set) + \
                    post_coff * CalcShannon(post_data_set)
                if iv > new_entropy:
                    new_entropy = iv
        # base_entropy is equal or greatter than new_entropy
        info_gain = base_entropy - new_entropy
        if flag == 'C4.5':
            info_gain_rate = info_gain / new_entropy
            # print('index', i, 'info_gain_rate', info_gain_rate)
            if info_gain_rate > best_info_gain_rate:
                best_info_gain_rate = info_gain_rate
                best_feature = i
        if flag == 'ID3':
            if info_gain > best_info_gain:
                best_info_gain = info_gain
                best_feature = i
    return best_feature

def CreateDataSet(method='ID3'):
    """ A naive data generation method.
    Arguments:
        method: The algorithm class
    Returns:
        data_set: The data set excepts label info.
        labels: The data set only contains label info.
    """
    # Arguments check
    if method not in ('ID3', 'C4.5'):
        raise ValueError('invalid value: %s' % method)
    if method == 'ID3':
        data_set = [[1, 1, 'yes'],
                    [1, 1, 'yes'],
                    [1, 0, 'no'],
                    [0, 1, 'no'],
                    [0, 1, 'no']]
        labels = ['no surfacing', 'flippers']
    else:
        data_set = [[85, 85, 'no'],
                    [80, 90, 'yes'],
                    [83, 78, 'no'],
                    [70, 96, 'no'],
                    [68, 80, 'no'],
                    [65, 70, 'yes'],
                    [64, 65, 'yes'],
                    [72, 95, 'no'],
                    [69, 70, 'no'],
                    [75, 80, 'no'],
                    [75, 70, 'yes'],
                    [72, 90, 'yes'],
                    [81, 75, 'no'],
                    [71, 80, 'yes']]
        labels = ['temperature', 'humidity']
    return data_set, labels

from math import log
import operator
import numpy as np
def CalcShannon(data_set):
    """ Calculate the Shan0n Entropy.
    Arguments:
        data_set: The object dataset.
    Returns:
        shan0n_ent: The Shan0n entropy of the object data set.
    """
    # Initiation
    num_entries = len(data_set)
    label_counts = {}
    # Statistics the frequency of each class in the dataset
    for feat_vec in data_set:
        current_label = feat_vec[-1]
        if current_label not in label_counts.keys():
            label_counts[current_label] = 0
        label_counts[current_label] += 1
    # print(label_counts)
    # Calculates the Shan0n entropy
    shan0n_ent = 0.0
    for key in label_counts:
        prob = float(label_counts[key]) / num_entries
        shan0n_ent -= prob * log(prob, 2)
    return shan0n_ent
def CalcGiniImpurity(data_set):
    """ Calculate the Gini impurity.
    Arguments:
        data_set: The object dataset.
    Returns:
        gini_impurity: The Gini impurity of the object data set.
    """
    # Initiation
    num_entries = len(data_set)
    label_counts = {}
    # Statistics the frequency of each class in the dataset
    for feat_vec in data_set:
        current_label = feat_vec[-1]
        if current_label not in label_counts.keys():
            label_counts[current_label] = 0
        label_counts[current_label] += 1
    # Calculates the Gini impurity
    gini_impurity = 0.0
    for key in label_counts:
        prob = float(label_counts[key]) / num_entries
        gini_impurity += pow(prob, 2)
    gini_impurity = 1 - gini_impurity
    return gini_impurity
def CalcMisClassifyImpurity(data_set):
    """ Calculate the misclassification impurity.
    Arguments:
        data_set: The object dataset.
    Returns:
        mis_classify_impurity:
            The misclassification impurity of the object data set.
    """
    # Initiation
    num_entries = len(data_set)
    label_counts = {}
    # Statistics the frequency of each class in the dataset
    for feat_vec in data_set:
        current_label = feat_vec[-1]
        if current_label not in label_counts.keys():
            label_counts[current_label] = 0
        label_counts[current_label] += 1
    # Calculates the misclassification impurity
    mis_classify_impurity = 0.0
    max_prob = max(label_counts.values()) / num_entries
    mis_classify_impurity = 1 - max_prob
    return mis_classify_impurity
def CreateDataSet(method='ID3'):
    """ A naive data generation method.
    Arguments:
        method: The algorithm class
    Returns:
        data_set: The data set excepts label info.
        labels: The data set only contains label info.
    """
    # Arguments check
    if method not in ('ID3', 'C4.5'):
        raise ValueError('invalid value: %s' % method)
    if method == 'ID3':
        data_set = [[1, 1, 1],
                    [1, 1, 1],
                    [1, 0, 0],
                    [0, 1, 0],
                    [0, 1, 0]]
        labels = ['0 surfacing', 'flippers']
    else:
        data_set = [[1, 85, 85, 0, 0],
                    [1, 80, 90, 1, 0],
                    [2, 83, 78, 0, 1],
                    [3, 70, 96, 0, 1],
                    [3, 68, 80, 0, 1],
                    [3, 65, 70, 1, 0],
                    [2, 64, 65, 1, 1],
                    [1, 72, 95, 0, 0],
                    [1, 69, 70, 0, 1],
                    [3, 75, 80, 0, 1],
                    [1, 75, 70, 1, 1],
                    [2, 72, 90, 1, 1],
                    [2, 81, 75, 0, 1],
                    [3, 71, 80, 1, 0]]
        labels = ['outlook', 'temperature', 'humidity', 'windy']
    return data_set, labels
def SplitDataSet(data_set, axis, value):
    """ Split the data set according to the given axis and correspond value.
    Arguments:
        data_set: Object data set.
        axis: The split-feature index.
        value: The value of the split-feature.
    Returns:
        ret_data_set: The splited data set.
    """
    ret_data_set = []
    for feat_vec in data_set:
        if feat_vec[axis] == value:
            reduced_feat_vec = feat_vec[:axis]
            reduced_feat_vec.extend(feat_vec[axis + 1:])
            ret_data_set.append(reduced_feat_vec)
    return ret_data_set
def ChooseBestFeatureToSplit(data_set, flag='ID3'):
    """ Choose the best feature to split.
    Arguments:
        data_set: Object data set.
        flag: Decide if use the infomation gain rate or not.
    Returns:
        best_feature: The index of the feature to split.
    """
    # Initiation
    # Because the range() method excepts the lastest number
    num_features = len(data_set[0]) - 1
    base_entropy = CalcShannon(data_set)
    method = 'ID3'
    best_feature = -1
    best_info_gain = 0.0
    best_info_gain_rate = 0.0
    for i in range(num_features):
        new_entropy = 0.0
        # Choose the i-th feature of all data
        feat_list = [example[i] for example in data_set]
        # Abandon the repeat feature value(s)
        unique_vals = set(feat_list)
        if len(unique_vals) > 3:
            method = 'C4.5'
        if method == 'ID3':
            # Calculates the Shannon entropy of the splited data set
            for value in unique_vals:
                sub_data_set = SplitDataSet(data_set, i, value)
                prob = len(sub_data_set) / len(data_set)
                new_entropy += prob * CalcShannon(sub_data_set)
        else:
            data_set = np.array(data_set)
            sorted_feat = np.argsort(feat_list)
            for index in range(len(sorted_feat) - 1):
                pre_sorted_feat, post_sorted_feat = np.split(
                    sorted_feat, [index + 1, ])
                pre_data_set = data_set[pre_sorted_feat]
                post_data_set = data_set[post_sorted_feat]
                pre_coff = len(pre_sorted_feat) / len(sorted_feat)
                post_coff = len(post_sorted_feat) / len(sorted_feat)
                # Calucate the split info
                iv = pre_coff * CalcShannon(pre_data_set) + \
                    post_coff * CalcShannon(post_data_set)
                if iv > new_entropy:
                    new_entropy = iv
        # base_entropy is equal or greatter than new_entropy
        info_gain = base_entropy - new_entropy
        if flag == 'C4.5':
            info_gain_rate = info_gain / new_entropy
            # print('index', i, 'info_gain_rate', info_gain_rate)
            if info_gain_rate > best_info_gain_rate:
                best_info_gain_rate = info_gain_rate
                best_feature = i
        if flag == 'ID3':
            if info_gain > best_info_gain:
                best_info_gain = info_gain
                best_feature = i
    return best_feature
def majority_cnt(class_list):
    """ Decided the final class.
    When the splited data is 0t belongs to the same class
    while all feature is handled, the final class is decided by
    the majority class.
    Arguments:
        class_list: The class list of the splited data set.
    Returns:
        sorted_class_count[0][0]: The majority class.
    """
    class_count = {}
    for vote in class_list:
        if vote not in class_count.keys():
            class_count[vote] = 0
        class_count[vote] += 1
    sorted_class_count = sorted(
        class_count.
        items(), key=operator.itemgetter(1), reverse=True)
    return sorted_class_count[0][0]
def CreateTree(data_set, feat_labels, method='ID3'):
    """ Create decision tree.
    Arguments:
        data_set: The object data set.
        labels: The feature labels in the data_set.
        method: The algorithm class.
    Returns:
        my_tree: A dict that represents the decision tree.
    """
    # Arguments check
    if method not in ('ID3', 'C4.5'):
        raise ValueError('invalid value: %s' % method)
    labels = feat_labels.copy()
    class_list = [example[-1] for example in data_set]
    # print(class_list)
    # If the classes are fully same
    print('class_list', class_list)
    if class_list.count(class_list[0]) == len(class_list):
        return class_list[0]
    # If all feature is handled
    if len(data_set[0]) == 1:
        return majority_cnt(class_list)
    if method == 'ID3':
        # Get the best split-feature and the correspond label
        best_feat = ChooseBestFeatureToSplit(data_set)
        best_feat_label = labels[best_feat]
        # print(best_feat_label)
        # Build a recurrence dict
        my_tree = {best_feat_label: {}}
        # Next step start
        feat_values = [example[best_feat] for example in data_set]
        # Get the next step labels parameter
        del(labels[best_feat])
        unique_vals = set(feat_values)
        for value in unique_vals:
            sub_labels = labels[:]
            # Recurrence calls
            my_tree[best_feat_label][value] = CreateTree(
                SplitDataSet(data_set, best_feat, value), sub_labels)
        return my_tree
    else:
        flag = 'ID3'
        # Get the best split-feature and the correspond label
        best_feat = ChooseBestFeatureToSplit(data_set, 'C4.5')
        best_feat_label = labels[best_feat]
        print(best_feat_label)
        # Build a recurrence dict
        my_tree = {best_feat_label: {}}
        # Next step start
        feat_values = [example[best_feat] for example in data_set]
        del(labels[best_feat])
        unique_vals = set(feat_values)
        if len(unique_vals) > 3:
            flag = 'C4.5'
        if flag == 'ID3':
            for value in unique_vals:
                sub_labels = labels[:]
                # Recurrence calls
                my_tree[best_feat_label][value] = CreateTree(
                    SplitDataSet(data_set, best_feat, value),
                    sub_labels, 'C4.5')
            return my_tree
        else:
            data_set = np.array(data_set)
            best_iv = 0.0
            best_split_value = -1
            sorted_feat = np.argsort(feat_values)
            for i in range(len(sorted_feat) - 1):
                pre_sorted_feat, post_sorted_feat = np.split(
                    sorted_feat, [i + 1, ])
                pre_data_set = data_set[pre_sorted_feat]
                post_data_set = data_set[post_sorted_feat]
                pre_coff = len(pre_sorted_feat) / len(sorted_feat)
                post_coff = len(post_sorted_feat) / len(sorted_feat)
                # Calucate the split info
                iv = pre_coff * CalcShannon(pre_data_set) + \
                    post_coff * CalcShannon(post_data_set)
                if iv > best_iv:
                    best_iv = iv
                    best_split_value = feat_values[sorted_feat[i]]
            print(best_feat, best_split_value)
            # print(best_split_value)
            left_data_set = data_set[
                data_set[:, best_feat] <= best_split_value]
            left_data_set = np.delete(left_data_set, best_feat, axis=1)
            # if len(left_data_set) == 1:
            #     return left_data_set[0][-1]
            right_data_set = data_set[
                data_set[:, best_feat] > best_split_value]
            right_data_set = np.delete(right_data_set, best_feat, axis=1)
            # if len(right_data_set) == 1:
            #     return right_data_set[0][-1]
            sub_labels = labels[:]
            my_tree[best_feat_label][
                '<=' + str(best_split_value)] = CreateTree(
                    left_data_set.tolist(), sub_labels, 'C4.5')
            my_tree[best_feat_label][
                '>' + str(best_split_value)] = CreateTree(
                    right_data_set.tolist(), sub_labels, 'C4.5')
            # print('continious tree', my_tree)
            return my_tree
def Classify(input_tree, feat_labels, test_vec):
    """ Classify that uses the given decision tree.
    Arguments:
        input_tree: The Given decision tree.
        feat_labels: The labels of correspond feature.
        test_vec: The test data.
    Returns:
        class_label: The class label that corresponds to the test data.
    """
    # Get the start feature label to split
    first_str = list(input_tree.keys())[0]
    # Get the sub-tree that corresponds to the start feature to split
    second_dict = input_tree[first_str]
    # Get the feature index that the label is the start feature label
    feat_index = feat_labels.index(first_str)
    # Start recurrence search
    for key in second_dict.keys():
        if test_vec[feat_index] == key:
            if type(second_dict[key]).__name__ == 'dict':
                # Recurrence calls
                class_label = Classify(second_dict[key], feat_labels, test_vec)
            else:
                class_label = second_dict[key]
    return class_label

In [108]: reload(trees)
Out[108]: <module 'trees' from 'C:\\Users\\Ewan\\Documents\\GitHub\\hexo\\public\\2017\\02\\15\\Decision-tree\\trees.py'>
In [109]: my_dat, labels = trees.CreateDataSet('C4.5')
In [110]: my_tree_c = trees.CreateTree(my_dat, labels, 'C4.5')
class_list [0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0]
outlook
class_list [0, 0, 0, 1, 1]
humidity
1 90
class_list [0, 0, 1, 1]
temperature
0 69
class_list [1]
class_list [0, 0, 1]
windy
class_list [0]
class_list [0, 1]
class_list [0]
class_list [1, 1, 1, 1]
class_list [1, 1, 0, 1, 0]
windy
class_list [1, 1, 1]
class_list [0, 0]
In [111]: my_tree_c
Out[111]:
{'outlook': {1: {'humidity': {'<=90': {'temperature': {'<=69': 1,
      '>69': {'windy': {0: 0, 1: 0}}}},
    '>90': 0}},
  2: 1,
  3: {'windy': {0: 1, 1: 0}}}}