Cabbage

C++算法题的一些输出技巧


输出时左对齐与右对齐,补全

C语言

在C语言中我们可以这样来实现左右对齐

printf("%-3d\n",3);
printf("%3d\n",3);

这样得到的结果就是

3
  3

如果像补零的话,就这样写

printf("%-03d
        
阅读全文 »

C++算法题的一些输入技巧


运行C++的终端中如何结束输入

有时候我们运行程序的时候,是以EOF结束程序,可是在终端中,输入空格,TAB和回车符都是无法结束输入的,所以这时我们使用其他方式。

  1. 在Windows中,输入完成后先按Enter键,再按Ctrl+Z键,最后再按Enter键即可结束输入。
  2. 在Linux中,输入完毕后按Ctrl+D键即可结束输入。

输入保留空格和回车

无法使用scanf("%s")输入字符串,因为它遇到空格或TAB就会停下来,所以我们可以使用下面两种方法:

1.getchar(),如果题目是可以边读边处理的,这种是最好的方法。

int c;
while((c = getchar()) != EOF){
    ...
}

2.gets(),如 ...

阅读全文 »

位运算训练 (Uva1590 Uva509题解)


位运算基础

逻辑运算 规则 符号
只有1 and 1 = 1,其他均为0 &
只有0 or 0 = 0,其他均为1 |
也就是取反 ~
异或 相异为1相同为0 ^
同或 相同为1相异为0,c中没有,但可以异或后取反
左移 各二进位全部左移若干位,高位丢弃,低位补0 <<
右移 各二进位全部右移若干位,对无符号数,高位补0,有符号数,有的补符号位(算术右移),有的补0(逻辑右移) >>
...

阅读全文 »

编写高质量代码-改善Python程序的91个建议笔记<编程惯用法>


编写高质量代码-改善Python程序的91个建议笔记<引论>


Python神经网络编程笔记


神经元

想一想便知道,当一个人捏你一下以至于你会痛得叫起来的力度便是神经元的阈值,而我们构建的时候也是把这种现象抽象成一个函数,叫作激活函数

而这里便是我们使用sigmoid函数的原因,它是一个很简单的函数,平滑更接近显示。

​ $$y=\frac{1}{1+e^{-x}}$$

Snipaste_2018-12-03_15-29-41.png

神经网络传递信号

神经网络便是通过一个一个神经元连接,使用权值x输入的和在通过sigmoid函数得到最终的输出值,然后一层一层的传递下去。

$$O = sigmoid(W\cdot I)$$

其中,$O$为输出矩 ...

阅读全文 »

Python进行高效的行计算


太长懒得看版

使用map函数进行行计算,加上np.column_stack 进行合并最快

假如有这么一组数据

df = pd.DataFrame({"one":list("AABBCCDD"),
                   "two":[1,1,2,2,3,3,4,4],
                   "three":[9,9,8,8,7,7,6,6]})
...

阅读全文 »

利用matplotlib进行数据可视化


matplotlib是python中的一个画图库,继承了matlib(从名字上也看得出来)的优点和语法,所以对于熟悉matlib的用户来说是十分友好的。

pylab和pyplot

关于pylab和pyplot,人们做过不少的讨论。这两个模块有哪些不同呢?pylab模块跟matplotlib一起安装,而pyplot则是matplotlib的内部模块。两者的导入方法有所不同,可选择其中一种进行导入。

from pylab import *
#或
import matplotlib.pyplot as plt
import numpy as np
...

阅读全文 »

启发式算法之遗传算法


刚开学便被拉去参加了研究生数模比赛,赛题是一个航班排班的优化问题,所以第一反映便是遗传算法,比赛期间三个问题都使用单目标遗传算法,趁着还比较熟悉,特此记录,以便后续复习。本篇文章使用Python进行实现。

启发式算法

启发式算法是一种技术,这种技术使得在可接受的计算成本内去搜寻最好的解,但不一定能保证所得的可行解和最优解,甚至在多数情况下,无法阐述所得解同最优解的近似程度。

就是说这种算法的全局最优解只是理论上可行,大多数情况下都是一个局部最优解。启发式算法用的比较多的有模拟退火算法(SA)、遗传算法(GA)、列表搜索算法(ST)、进化规划(EP)、进化策略(ES)、蚁群算法(ACA)、人工神经网络(ANN)。这里重点介绍一下遗传算法(GA)。

遗传算法准备

遗传算法(Genetic Algorithm, GA)起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法,借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法,能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应地控制搜索过程以求得最佳解。

具体来说,在写算法之前,有四个很重要的步骤:

  1. 确定编码方式
  2. 如何设计编码
  3. 确定约束条件
  4. 如何实现约束

确定编码方式

对于编码方式来说,影响到交叉算子、变异算子等遗传算子的运算方法,大很大程度上决定了遗传进化的效率。 总的来说,编码方 ...

阅读全文 »

CART算法的实现


3.CART

# -*- coding: utf-8 -*-


from math import log
import operator
import time
import pickle


# 标签集,0为数值型,1为标称型
label_type = {'0':1,'1':1,'2':1,'3':1}

def calc_gini(data_set):
    num_entries=len(data_set)  
    label_counts={}  
    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  
    Gini=1.0  
    for key in label_counts:  
        prob = float(label_counts[key]) / num_entries  
        Gini -= prob*prob  
    return Gini  

def split_data_set(data_set, axis, value):
    """
    按照给定特征划分数据集;去除选择维度中等于选择值的项
    :param data_set: 数据集
    :param axis: 数据集中的位置
    :param value: 特征值
    :return:划分数据集
    """
    ret_data_set = []
    for feat_vec in data_set:
        if feat_vec[axis] == value:
            reduce_feat_vec = feat_vec[:axis]
            reduce_feat_vec.extend(feat_vec[axis+1:])
            ret_data_set.append(reduce_feat_vec)
    return ret_data_set

def split_data_min(data_set, axis, value):
    '''
    将data_set按除开某一特征值划分
    :param data_set: 数据集
    :param axis: 数据集中的位置
    :param value: 特征值
    :return: 除开某一特征值的列表,属性为小于数值型
    '''
    ret_data_set = []
    for feat_vec in data_set:
        try:
            if float(feat_vec[axis]) <= float(value):
                reduced_feat_vec = feat_vec[:axis]
                reduced_feat_vec.extend(feat_vec[axis+1:])
                ret_data_set.append(reduced_feat_vec)
        except:
            ret_data_set.append(feat_vec[:axis+1])
            return ret_data_set
    return ret_data_set

def split_data_max(data_set, axis, value):
    '''
    将data_set按除开某一特征值划分
    :param data_set: 数据集
    :param axis: 数据集中的位置
    :param value: 特征值
    :return: 除开某一特征值的列表,属性为大于数值型
    '''
    ret_data_set = []
    for feat_vec in data_set:
        try:
            if float(feat_vec[axis]) > float(value):
                reduced_feat_vec = feat_vec[:axis]
                reduced_feat_vec.extend(feat_vec[axis+1:])
                ret_data_set.append(reduced_feat_vec)
        except:
            ret_data_set.append(feat_vec[:axis+1])
            return ret_data_set
    return ret_data_set

def choose_best_feature_to_split(data_set, labels):
    '''
    根据信息增益最大,选择最好的数据集划分特征
    :param data_set: 数据集
    :param labels:标签
    :return: 最优分割特征
    '''
    num = len(data_set[0]) - 1   # 数量
    base_entropy = calc_gini(data_set)    #信息熵
    best_info_gain = 0.0  #信息增益
    best_feature = -1    # 最优分割特征
    for i in range(num):
        if label_type[labels[i]]== 1:
            feat_list = [example[i] for example in data_set]
            unique_vals = set(feat_list)
            new_entropy = 0.0
            for value in unique_vals:
                sub_data_set = split_data_set(data_set, i, value)
                prob = len(sub_data_set)/float(len(data_set))
                new_entropy += prob * calc_gini(sub_data_set)
            info_gain = base_entropy - new_entropy
        else:
            info_gain=0.0
            feat_list = [example[i] for example in data_set]
            feat_list.sort()
            for j in range(0,len(feat_list)-1,3000):     # 分箱
                value=(float(feat_list[j])+float(feat_list[j+1]))/2.0
                min_data_set=split_data_min(data_set, i, value)
                max_data_set=split_data_max(data_set, i, value)
                prob = (j+1)/len(feat_list)
                new_entropy = prob * calc_gini(min_data_set)+(1-prob)*calc_gini(max_data_set)
                subinfo_gain = base_entropy - new_entropy
                if subinfo_gain>info_gain:
                    info_gain=subinfo_gain
                    label_type[labels[i]]=str(value)
        if (info_gain > best_info_gain):
            best_info_gain = info_gain
            best_feature = i
    return best_feature

def majority_cnt(class_list):
    """
    数据集已经处理了所有属性,但是类标签依然不是唯一的,采用投票的方法决定该子节点的分类
    :param class_list: 分类类别列表
    :return: 子节点的分类
    """
    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))
    return sorted_class_count[0][0]

def create_tree(data_set, labels):
    """
    递归构建决策树,利用上述的函数
    :param data_set: 数据集
    :param labels: 特征标签
    :return: 决策树
    """
    if len(data_set) == 0:
        return '"no"'
    if len(data_set) == 1:
        return '"no"'
    class_list = [example[-1] for example in data_set]
    if class_list.count(class_list[0]) == len(class_list):
        # 类别完全相同,停止划分
        return class_list[0]
    if len(data_set[0]) == 1:
        # 遍历完所有特征时返回出现次数最多的
        return majority_cnt(class_list)
    best_feat = choose_best_feature_to_split(data_set,labels)
    best_feat_label = labels[best_feat]
    name=labels[best_feat]
    my_tree = {best_feat_label:{}}
    del(labels[best_feat])
    # 得到列表包括节点所有的属性值
    if label_type[name] == 1:
        feat_values = [example[best_feat] for example in data_set]
        unique_vals = set(feat_values)
        for value in unique_vals:
            sub_labels = labels[:]
            my_tree[best_feat_label][value] = create_tree(split_data_set(data_set, best_feat, value), sub_labels)
    else:
        sub_labels = labels[:]
        my_tree[best_feat_label]['low'+str(label_type[name])] = create_tree(split_data_min(data_set, best_feat, label_type[name]),sub_labels)
        sub_labels = labels[:]
        my_tree[best_feat_label]['high'+str(label_type[name])] = create_tree(split_data_max(data_set, best_feat, label_type[name]),sub_labels)
    return my_tree

def classify(input_tree, feat_labels, test_vec):
    """
    决策树
    :param input_tree:决策树
    :param feat_labels:分类标签
    :param test_vec:测试数据
    :return: 决策结果
    """
    global class_label
    first_str = list(input_tree.keys())[0]
    second_dict = input_tree[first_str]
    feat_index = feat_labels.index(first_str)
    for key in second_dict.keys():
        if label_type[first_str] == 1:
            if test_vec[feat_index] == key:
                if type(second_dict[key]).__name__ == 'dict':
                    class_label = classify(second_dict[key], feat_labels, test_vec)
                else:
                    class_label = second_dict[key]
        else:
            if 'low' in key:
                if float(test_vec[feat_index]) <= float(key[3:]):
                    if type(second_dict[key]).__name__ == 'dict':
                        class_label = classify(second_dict[key], feat_labels, test_vec)
                    else:
                        class_label = second_dict[key]
            elif 'high' in key:
                if float(test_vec[feat_index]) > float(key[4:]):
                    if type(second_dict[key]).__name__ == 'dict':
                        class_label = classify(second_dict[key], feat_labels, test_vec)
                    else:
                        class_label = second_dict[key]
    return class_label

def classify_all(input_tree, feat_labels, test_data_set):
    """
    决策树
    :param input_tree:决策树
    :param feat_labels:分类标签
    :param test_data_set:测试数据集
    :return: 决策结果
    """
    class_label_all = []
    for test_vec in test_data_set:
        class_label_all.append(classify(input_tree, feat_labels, test_vec))
    return class_label_all

def format_data(filename):
    '''
    格式化数据
    :return: 数据集和标签
    '''
    t = file(filename, "rb")
    data = []
    data_set = []
    newlabel = []
    for line in t:
        data.append(line.split(','))
    for line in data:
        line[-1] = line[-1].strip()
        data_set.append(line[0:])
    label = data_set.pop(0)
    label = label[:-1]
    newlabel = label
    return data_set, newlabel

def create_data_set(filename):
    """
    从format_data获取train
    """
    data_set = format_data(filename)[0]
    labels = format_data(filename)[1]
    return data_set, labels

def create_test_set(filename):
    """
    从format_data获取test
    """
    test_set = format_data(filename)[0]
    return test_set

def get_true_ans(filename):
    '''
    得到真实数据正确答案
    :return:list
    '''
    t = file(filename, "rb")
    data = []
    ans = []
    for line in t:
        data.append(line.split(','))
    del data[0]
    for line in data:
        line[-1] = line[-1].strip()
        ans.append(line[-1])
    return ans

def main(train, test):
    starttr = time.time()
    data_set, labels = create_data_set(train)
    labels_tmp = labels[:] # 拷贝,create_tree会改变labels
    desicion_tree = create_tree(data_set, labels_tmp)
    endtr = time.time()
    print u'训练时间'+str(endtr - starttr)
    startte = time.time()
    test_set = create_test_set(test)
    me = classify_all(desicion_tree, labels, test_set)
    endte = time.time()
    print u'测试时间'+str(endte - startte)
    ans = get_true_ans(test)
    y = 0
    n = 0 
    for i in range(0,len(me)):
        if me[i] == ans[i]:
            y += 1
        else:
            n += 1
    print u'准确率'+str(float((y))/float(y + n))

if __name__ == '__main__':
    train = './iris/iris.train'
    test = './iris/bezdekIris.data'
    main(train, test)
...

阅读全文 »