Ritarma

blog


  • Home

  • About

  • Tags

  • Categories

  • Archives

特枕选择和建模

Posted on 2020-09-22 | Visitors: ℃
Words count in article: 4.6k

数据预处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 确定哪些包是安装好的

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
import datetime
from tqdm import tqdm
from sklearn.preprocessing import LabelEncoder
from sklearn.feature_selection import SelectKBest
from sklearn.feature_selection import chi2
from sklearn.preprocessing import MinMaxScaler
import xgboost as xgb
import lightgbm as lgb
from catboost import CatBoostRegressor
import warnings
from sklearn.model_selection import StratifiedKFold, KFold
from sklearn.metrics import accuracy_score, f1_score, roc_auc_score, log_loss
warnings.filterwarnings('ignore')
1
2
data_train =pd.read_csv('./train.csv')
data_test_a = pd.read_csv('./testA.csv')
1
2
data_train.info()
is_default = data_train['isDefault']
<class 'pandas.core.frame.DataFrame'>
RangeIndex: 800000 entries, 0 to 799999
Data columns (total 47 columns):
 #   Column              Non-Null Count   Dtype  
---  ------              --------------   -----  
 0   id                  800000 non-null  int64  
 1   loanAmnt            800000 non-null  float64
 2   term                800000 non-null  int64  
 3   interestRate        800000 non-null  float64
 4   installment         800000 non-null  float64
 5   grade               800000 non-null  object 
 6   subGrade            800000 non-null  object 
 7   employmentTitle     799999 non-null  float64
 8   employmentLength    753201 non-null  object 
 9   homeOwnership       800000 non-null  int64  
 10  annualIncome        800000 non-null  float64
 11  verificationStatus  800000 non-null  int64  
 12  issueDate           800000 non-null  object 
 13  isDefault           800000 non-null  int64  
 14  purpose             800000 non-null  int64  
 15  postCode            799999 non-null  float64
 16  regionCode          800000 non-null  int64  
 17  dti                 799761 non-null  float64
 18  delinquency_2years  800000 non-null  float64
 19  ficoRangeLow        800000 non-null  float64
 20  ficoRangeHigh       800000 non-null  float64
 21  openAcc             800000 non-null  float64
 22  pubRec              800000 non-null  float64
 23  pubRecBankruptcies  799595 non-null  float64
 24  revolBal            800000 non-null  float64
 25  revolUtil           799469 non-null  float64
 26  totalAcc            800000 non-null  float64
 27  initialListStatus   800000 non-null  int64  
 28  applicationType     800000 non-null  int64  
 29  earliesCreditLine   800000 non-null  object 
 30  title               799999 non-null  float64
 31  policyCode          800000 non-null  float64
 32  n0                  759730 non-null  float64
 33  n1                  759730 non-null  float64
 34  n2                  759730 non-null  float64
 35  n2.1                759730 non-null  float64
 36  n4                  766761 non-null  float64
 37  n5                  759730 non-null  float64
 38  n6                  759730 non-null  float64
 39  n7                  759730 non-null  float64
 40  n8                  759729 non-null  float64
 41  n9                  759730 non-null  float64
 42  n10                 766761 non-null  float64
 43  n11                 730248 non-null  float64
 44  n12                 759730 non-null  float64
 45  n13                 759730 non-null  float64
 46  n14                 759730 non-null  float64
dtypes: float64(33), int64(9), object(5)
memory usage: 286.9+ MB

缺失值填充

由于EDA中对缺失的数据发现还有很多,尝试多种缺失填充然后比较结果选择结果最优的一种

1
2
3
4
5
6
# 找到数值型的特征
numerical_fea = list(data_train.select_dtypes(exclude=['object']).columns)
# 找到非结构化的特征
category_fea = list(filter(lambda x: x not in numerical_fea, list(data_train.columns)))
# 移除‘isDefault’特征
numerical_fea.remove('isDefault')
1
print(len(numerical_fea))
41

有三种缺失值填充的方式

  • 缺失值替换为指定的值(’0’)
  • 用上面的值替换缺失值
  • 纵向用下面的值来替换,且最多只填充两个连续的
1
2
# 显示缺失值的情况
data_train.isnull().sum()
id                        0
loanAmnt                  0
term                      0
interestRate              0
installment               0
grade                     0
subGrade                  0
employmentTitle           1
employmentLength      46799
homeOwnership             0
annualIncome              0
verificationStatus        0
issueDate                 0
isDefault                 0
purpose                   0
postCode                  1
regionCode                0
dti                     239
delinquency_2years        0
ficoRangeLow              0
ficoRangeHigh             0
openAcc                   0
pubRec                    0
pubRecBankruptcies      405
revolBal                  0
revolUtil               531
totalAcc                  0
initialListStatus         0
applicationType           0
earliesCreditLine         0
title                     1
policyCode                0
n0                    40270
n1                    40270
n2                    40270
n2.1                  40270
n4                    33239
n5                    40270
n6                    40270
n7                    40270
n8                    40271
n9                    40270
n10                   33239
n11                   69752
n12                   40270
n13                   40270
n14                   40270
dtype: int64
1
2
3
4
5
6
7
8
9
10
fill_type = 0
if fill_type == 1:
# 缺失值替换为指定的值
data_train = data_train.fillna(0)
elif fill_type == 2:
# 用上面的值替换缺失值
data_train = data_train.fillna(axis=0,method='ffill')
elif fill_type == 3:
# 纵向用下面的值来替换,且最多只填充两个连续的
data_train = data_train.fillna(axis=0,method='bfill',limit=2)
1
2
3
4
5
6
#按照平均数填充数值型特征
data_train[numerical_fea] = data_train[numerical_fea].fillna(data_train[numerical_fea].median())
data_test_a[numerical_fea] = data_test_a[numerical_fea].fillna(data_train[numerical_fea].median())
#按照众数填充类别型特征
data_train[category_fea] = data_train[category_fea].fillna(data_train[category_fea].mode())
data_test_a[category_fea] = data_test_a[category_fea].fillna(data_train[category_fea].mode())
1
2
3
4
5
6
7
8
# 处理没有结构化的数据 'issueDate' 
data_train.isnull().sum()
# 由于有些数据类型比如时间需要特别处理:['issueDate'] ['earliesCreditLine']
for data in [data_train, data_test_a]:
data['issueDate'] = pd.to_datetime(data['issueDate'],format='%Y-%m-%d')
startdate = datetime.datetime.strptime('2007-06-01', '%Y-%m-%d')
#构造时间特征
data['issueDateDT'] = data['issueDate'].apply(lambda x: x-startdate).dt.days
1
2
3
4
5
6
7
8
9
10
11
data_train['employmentLength'].value_counts(dropna=False).sort_index()
# employmentLength 这一列特征中主要存储的是带信息的字符串稍微处理下变成int类型
def employmentLength_to_int(s):
if pd.isnull(s):
return s
else:
return np.int8(s.split()[0])
for data in [data_train, data_test_a]:
data['employmentLength'].replace(to_replace='10+ years', value='10 years', inplace=True)
data['employmentLength'].replace('< 1 year', '0 years', inplace=True)
data['employmentLength'] = data['employmentLength'].apply(employmentLength_to_int)
1
2
data['employmentLength'].value_counts(dropna=False).sort_index()
# 可以看出数据的分布主要还是集中在10年以上
0.0     15989
1.0     13182
2.0     18207
3.0     16011
4.0     11833
5.0     12543
6.0      9328
7.0      8823
8.0      8976
9.0      7594
10.0    65772
NaN     11742
Name: employmentLength, dtype: int64

‘employmentLength’这个特征表示借款人最早报告的信用额度开立的月份 存储的时候是按照str存储的

1
data_train['earliesCreditLine'].sample(5)
631614    May-2002
657973    Mar-1995
518715    Jan-2003
16630     Apr-1993
308502    Jun-2009
Name: earliesCreditLine, dtype: object
1
2
3
# 对于这个类型的特征由于时间跨度大所以只需要年份就行了
for data in [data_train, data_test_a]:
data['earliesCreditLine'] = data['earliesCreditLine'].apply(lambda s: int(s[-4:]))

处理一些类别特征
用nunique() 可以找到不重复的类别有几种
grade 类型数: 7
subGrade 类型数: 35
employmentTitle 类型数: 79282
homeOwnership 类型数: 6
verificationStatus 类型数: 3
purpose 类型数: 14
postCode 类型数: 889
regionCode 类型数: 51
applicationType 类型数: 2
initialListStatus 类型数: 2
title 类型数: 12058
policyCode 类型数: 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
semantic_dict = {
id:'为贷款清单分配的唯一信用证标识',
'loanAmnt':'贷款金额',
'term' :'贷款期限(year)',
'interestRate':'贷款利率',
'installment' :'分期付款金额',
'grade' :'贷款等级',
'subGrade' :'贷款等级之子级',
'employmentTitle' :'就业职称',
'employmentLength' :'就业年限(年)',
'homeOwnership' :'借款人在登记时提供的房屋所有权状况',
'annualIncome' :'年收入',
'verificationStatus' :'验证状态',
'issueDate' :'贷款发放的月份',
'purpose' :'借款人在贷款申请时的贷款用途类别',
'postCode' :'借款人在贷款申请中提供的邮政编码的前3位数字',
'regionCode' :'地区编码',
'dti' :'债务收入比',
'delinquency_2years' :'借款人过去2年信用档案中逾期30天以上的违约事件数',
'ficoRangeLow':'借款人在贷款发放时的fico所属的下限范围',
'ficoRangeHigh':'借款人在贷款发放时的fico所属的上限范围',
'openAcc':'借款人信用档案中未结信用额度的数量',
'pubRec':'贬损公共记录的数量',
'pubRecBankruptcies':'公开记录清除的数量',
'revolBal':'信贷周转余额合计',
'revolUtil':'循环额度利用率,或借款人使用的相对于所有可用循环信贷的信贷金额',
'totalAcc':'借款人信用档案中当前的信用额度总数',
'initialListStatus':'贷款的初始列表状态',
'applicationType':'表明贷款是个人申请还是与两个共同借款人的联合申请',
'earliesCreditLine':'借款人最早报告的信用额度开立的月份',
'title':'借款人提供的贷款名称',
'policyCode':'公开可用的策略_代码=1新产品不公开可用的策略_代码=2n系列匿名特征 匿名特征n0-n14,为一些贷款人行为计数特征的处理',}
1
2
3
4
5
# 把grad映射一下
for data in [data_train, data_test_a]:
data['grade'] = data['grade'].map({'A':1,'B':2,'C':3,'D':4,'E':5,'F':6,'G':7})
for data in [data_train, data_test_a]:
data = pd.get_dummies(data, columns=['subGrade', 'homeOwnership', 'verificationStatus', 'purpose', 'regionCode'], drop_first=True)

异常值处理

  • 首先,如果这一异常值并不代表一种规律性的,而是极其偶然的现象,或者说你并不想研究这种偶然的现象,这时可以将其删除。
  • 其次,如果异常值存在且代表了一种真实存在的现象,那就不能随便删除。在现有的欺诈场景中很多时候欺诈数据本身相对于正常数据说就是异常的,我们要把这些异常点纳入,重新拟合模型,研究其规律。能用监督的用监督模型,不能用的还可以考虑用异常检测的算法来做。
  • 注意test的数据不能删。
    让我们来分析一下数值型数据的异常值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 使用3sigma分析来找异常值,此时的data是[200000, 148], 增加的列编程了
def find_outliers_by_3segama(data,fea):
data_std = np.std(data[fea])
data_mean = np.mean(data[fea])
outliers_cut_off = data_std * 3
lower_rule = data_mean - outliers_cut_off
upper_rule = data_mean + outliers_cut_off
data[fea+'_outliers'] = data[fea].apply(lambda x:str('异常值') if x > upper_rule or x < lower_rule else '正常值')
return data

data_train = data_train.copy()
for fea in numerical_fea:
data_train = find_outliers_by_3segama(data_train,fea)
print(data_train[fea+'_outliers'].value_counts())
print(data_train.groupby(fea+'_outliers')['isDefault'].sum())
print('*'*10)
# data_train[80w, 89]
正常值    800000
Name: id_outliers, dtype: int64
id_outliers
正常值    159610
Name: isDefault, dtype: int64
**********
正常值    800000
Name: loanAmnt_outliers, dtype: int64
loanAmnt_outliers
正常值    159610
Name: isDefault, dtype: int64
**********
正常值    800000
Name: term_outliers, dtype: int64
term_outliers
正常值    159610
Name: isDefault, dtype: int64
**********
正常值    794259
异常值      5741
Name: interestRate_outliers, dtype: int64
interestRate_outliers
异常值      2916
正常值    156694
Name: isDefault, dtype: int64
**********
正常值    792046
异常值      7954
Name: installment_outliers, dtype: int64
installment_outliers
异常值      2152
正常值    157458
Name: isDefault, dtype: int64
**********
正常值    800000
Name: employmentTitle_outliers, dtype: int64
employmentTitle_outliers
正常值    159610
Name: isDefault, dtype: int64
**********
正常值    799701
异常值       299
Name: homeOwnership_outliers, dtype: int64
homeOwnership_outliers
异常值        62
正常值    159548
Name: isDefault, dtype: int64
**********
正常值    793973
异常值      6027
Name: annualIncome_outliers, dtype: int64
annualIncome_outliers
异常值       756
正常值    158854
Name: isDefault, dtype: int64
**********
正常值    800000
Name: verificationStatus_outliers, dtype: int64
verificationStatus_outliers
正常值    159610
Name: isDefault, dtype: int64
**********
正常值    783003
异常值     16997
Name: purpose_outliers, dtype: int64
purpose_outliers
异常值      3635
正常值    155975
Name: isDefault, dtype: int64
**********
正常值    798931
异常值      1069
Name: postCode_outliers, dtype: int64
postCode_outliers
异常值       221
正常值    159389
Name: isDefault, dtype: int64
**********
正常值    799994
异常值         6
Name: regionCode_outliers, dtype: int64
regionCode_outliers
异常值         1
正常值    159609
Name: isDefault, dtype: int64
**********
正常值    798440
异常值      1560
Name: dti_outliers, dtype: int64
dti_outliers
异常值       466
正常值    159144
Name: isDefault, dtype: int64
**********
正常值    778245
异常值     21755
Name: delinquency_2years_outliers, dtype: int64
delinquency_2years_outliers
异常值      5089
正常值    154521
Name: isDefault, dtype: int64
**********
正常值    788261
异常值     11739
Name: ficoRangeLow_outliers, dtype: int64
ficoRangeLow_outliers
异常值       778
正常值    158832
Name: isDefault, dtype: int64
**********
正常值    788261
异常值     11739
Name: ficoRangeHigh_outliers, dtype: int64
ficoRangeHigh_outliers
异常值       778
正常值    158832
Name: isDefault, dtype: int64
**********
正常值    790889
异常值      9111
Name: openAcc_outliers, dtype: int64
openAcc_outliers
异常值      2195
正常值    157415
Name: isDefault, dtype: int64
**********
正常值    792471
异常值      7529
Name: pubRec_outliers, dtype: int64
pubRec_outliers
异常值      1701
正常值    157909
Name: isDefault, dtype: int64
**********
正常值    794120
异常值      5880
Name: pubRecBankruptcies_outliers, dtype: int64
pubRecBankruptcies_outliers
异常值      1423
正常值    158187
Name: isDefault, dtype: int64
**********
正常值    790001
异常值      9999
Name: revolBal_outliers, dtype: int64
revolBal_outliers
异常值      1359
正常值    158251
Name: isDefault, dtype: int64
**********
正常值    799948
异常值        52
Name: revolUtil_outliers, dtype: int64
revolUtil_outliers
异常值        23
正常值    159587
Name: isDefault, dtype: int64
**********
正常值    791663
异常值      8337
Name: totalAcc_outliers, dtype: int64
totalAcc_outliers
异常值      1668
正常值    157942
Name: isDefault, dtype: int64
**********
正常值    800000
Name: initialListStatus_outliers, dtype: int64
initialListStatus_outliers
正常值    159610
Name: isDefault, dtype: int64
**********
正常值    784586
异常值     15414
Name: applicationType_outliers, dtype: int64
applicationType_outliers
异常值      3875
正常值    155735
Name: isDefault, dtype: int64
**********
正常值    775134
异常值     24866
Name: title_outliers, dtype: int64
title_outliers
异常值      3900
正常值    155710
Name: isDefault, dtype: int64
**********
正常值    800000
Name: policyCode_outliers, dtype: int64
policyCode_outliers
正常值    159610
Name: isDefault, dtype: int64
**********
正常值    782773
异常值     17227
Name: n0_outliers, dtype: int64
n0_outliers
异常值      3485
正常值    156125
Name: isDefault, dtype: int64
**********
正常值    790500
异常值      9500
Name: n1_outliers, dtype: int64
n1_outliers
异常值      2491
正常值    157119
Name: isDefault, dtype: int64
**********
正常值    789067
异常值     10933
Name: n2_outliers, dtype: int64
n2_outliers
异常值      3205
正常值    156405
Name: isDefault, dtype: int64
**********
正常值    789067
异常值     10933
Name: n2.1_outliers, dtype: int64
n2.1_outliers
异常值      3205
正常值    156405
Name: isDefault, dtype: int64
**********
正常值    788660
异常值     11340
Name: n4_outliers, dtype: int64
n4_outliers
异常值      2476
正常值    157134
Name: isDefault, dtype: int64
**********
正常值    790355
异常值      9645
Name: n5_outliers, dtype: int64
n5_outliers
异常值      1858
正常值    157752
Name: isDefault, dtype: int64
**********
正常值    786006
异常值     13994
Name: n6_outliers, dtype: int64
n6_outliers
异常值      3182
正常值    156428
Name: isDefault, dtype: int64
**********
正常值    788430
异常值     11570
Name: n7_outliers, dtype: int64
n7_outliers
异常值      2746
正常值    156864
Name: isDefault, dtype: int64
**********
正常值    789625
异常值     10375
Name: n8_outliers, dtype: int64
n8_outliers
异常值      2131
正常值    157479
Name: isDefault, dtype: int64
**********
正常值    786384
异常值     13616
Name: n9_outliers, dtype: int64
n9_outliers
异常值      3953
正常值    155657
Name: isDefault, dtype: int64
**********
正常值    788979
异常值     11021
Name: n10_outliers, dtype: int64
n10_outliers
异常值      2639
正常值    156971
Name: isDefault, dtype: int64
**********
正常值    799434
异常值       566
Name: n11_outliers, dtype: int64
n11_outliers
异常值       112
正常值    159498
Name: isDefault, dtype: int64
**********
正常值    797585
异常值      2415
Name: n12_outliers, dtype: int64
n12_outliers
异常值       545
正常值    159065
Name: isDefault, dtype: int64
**********
正常值    788907
异常值     11093
Name: n13_outliers, dtype: int64
n13_outliers
异常值      2482
正常值    157128
Name: isDefault, dtype: int64
**********
正常值    788884
异常值     11116
Name: n14_outliers, dtype: int64
n14_outliers
异常值      3364
正常值    156246
Name: isDefault, dtype: int64
**********
1
2
3
4
#删除异常值对应的行
for fea in numerical_fea:
data_train = data_train[data_train[fea+'_outliers']=='正常值']
data_train = data_train.reset_index(drop=True)

数据分桶

将一些连续数据比如999,99,8这种连续数据离散化来处理

1
2
3
4
5
6
# 通过除法映射到间隔均匀的分箱中,每个分箱的取值范围都是loanAmnt/1000
data['loanAmnt_bin1'] = np.floor_divide(data['loanAmnt'], 1000)
## 通过对数函数映射到指数宽度分箱
data['loanAmnt_bin2'] = np.floor(np.log10(data['loanAmnt']))
## 分位数分箱
data['loanAmnt_bin3'] = pd.qcut(data['loanAmnt'], 10, labels=False)

特征编码

labelEncode 直接放入树模型中

1
2
3
4
5
6
7
8
#label-encode:subGrade,postCode,title
# 高维类别特征需要进行转换
for col in tqdm(['employmentTitle', 'postCode', 'title','subGrade']):
le = LabelEncoder()
le.fit(list(data_train[col].astype(str).values) + list(data_test_a[col].astype(str).values))
data_train[col] = le.transform(list(data_train[col].astype(str).values))
data_test_a[col] = le.transform(list(data_test_a[col].astype(str).values))
print('Label Encoding 完成')
100%|██████████| 4/4 [00:03<00:00,  1.13it/s]


Label Encoding 完成

逻辑回归等模型要单独增加的特征工程

  • 对特征做归一化,去除相关性高的特征
  • 归一化目的是让训练过程更好更快的收敛,避免特征大吃小的问题
  • 去除相关性是增加模型的可解释性,加快预测过程。

特征选择

特征选择技术可以精简掉无用的特征,以降低最终模型的复杂性,它的最终目的是得到一个简约模型,
在不降低预测准确率或对预测准确率影响不大的情况下提高计算速度。特征选择不是为了减少训练时间
(实际上,一些技术会增加总体训练时间),而是为了减少模型评分时间。

  • Filter
    • 方差选择法
    • 相关系数法(pearson 相关系数)
    • 卡方检验
    • 互信息法
  • 2 Wrapper (RFE)
    • 递归特征消除法
  • 3 Embedded
    • 基于惩罚项的特征选择法
    • 基于树模型的特征选择
1
2
"纵向用缺失值上面的值替换缺失值"
data_train = data_train.fillna(axis=0,method='ffill')
1
2
3
4
5
6
x_train = data_train
#计算协方差
data_corr = x_train.corrwith(data_train.isDefault) #计算相关性
result = pd.DataFrame(columns=['features', 'corr'])
result['features'] = data_corr.index
result['corr'] = data_corr.values
1
2
3
4
5
6
7
# 当然也可以直接看图
data_numeric = data_train[numerical_fea]
correlation = data_numeric.corr()

f , ax = plt.subplots(figsize = (7, 7))
plt.title('Correlation of Numeric Features with Price',y=1,size=16)
sns.heatmap(correlation,square = True, vmax=0.8)
<matplotlib.axes._subplots.AxesSubplot at 0x16522246898>

png

1
2
3
4
features = [f for f in data_train.columns if f not in ['id','issueDate','isDefault'] and '_outliers' not in f]
x_train = data_train[features]
x_test = data_test_a[features]
y_train = data_train['isDefault']
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
def cv_model(clf, train_x, train_y, test_x, clf_name):
folds = 5
seed = 2020
kf = KFold(n_splits=folds, shuffle=True, random_state=seed)

train = np.zeros(train_x.shape[0])
test = np.zeros(test_x.shape[0])

cv_scores = []

for i, (train_index, valid_index) in enumerate(kf.split(train_x, train_y)):
print('************************************ {} ************************************'.format(str(i+1)))
trn_x, trn_y, val_x, val_y = train_x.iloc[train_index], train_y[train_index], train_x.iloc[valid_index], train_y[valid_index]

if clf_name == "lgb":
train_matrix = clf.Dataset(trn_x, label=trn_y)
valid_matrix = clf.Dataset(val_x, label=val_y)

params = {
'boosting_type': 'gbdt',
'objective': 'binary',
'metric': 'auc',
'min_child_weight': 5,
'num_leaves': 2 ** 5,
'lambda_l2': 10,
'feature_fraction': 0.8,
'bagging_fraction': 0.8,
'bagging_freq': 4,
'learning_rate': 0.1,
'seed': 2020,
'nthread': 28,
'n_jobs':24,
'silent': True,
'verbose': -1,
}

model = clf.train(params, train_matrix, 50000, valid_sets=[train_matrix, valid_matrix], verbose_eval=200,early_stopping_rounds=200)
val_pred = model.predict(val_x, num_iteration=model.best_iteration)
test_pred = model.predict(test_x, num_iteration=model.best_iteration)

# print(list(sorted(zip(features, model.feature_importance("gain")), key=lambda x: x[1], reverse=True))[:20])

if clf_name == "xgb":
train_matrix = clf.DMatrix(trn_x , label=trn_y)
valid_matrix = clf.DMatrix(val_x , label=val_y)

params = {'booster': 'gbtree',
'objective': 'binary:logistic',
'eval_metric': 'auc',
'gamma': 1,
'min_child_weight': 1.5,
'max_depth': 5,
'lambda': 10,
'subsample': 0.7,
'colsample_bytree': 0.7,
'colsample_bylevel': 0.7,
'eta': 0.04,
'tree_method': 'exact',
'seed': 2020,
'nthread': 36,
"silent": True,
}

watchlist = [(train_matrix, 'train'),(valid_matrix, 'eval')]

model = clf.train(params, train_matrix, num_boost_round=50000, evals=watchlist, verbose_eval=200, early_stopping_rounds=200)
val_pred = model.predict(valid_matrix, ntree_limit=model.best_ntree_limit)
test_pred = model.predict(test_x , ntree_limit=model.best_ntree_limit)

if clf_name == "cat":
params = {'learning_rate': 0.05, 'depth': 5, 'l2_leaf_reg': 10, 'bootstrap_type': 'Bernoulli',
'od_type': 'Iter', 'od_wait': 50, 'random_seed': 11, 'allow_writing_files': False}

model = clf(iterations=20000, **params)
model.fit(trn_x, trn_y, eval_set=(val_x, val_y),
cat_features=[], use_best_model=True, verbose=500)

val_pred = model.predict(val_x)
test_pred = model.predict(test_x)

train[valid_index] = val_pred
test = test_pred / kf.n_splits
cv_scores.append(roc_auc_score(val_y, val_pred))

print(cv_scores)

print("%s_scotrainre_list:" % clf_name, cv_scores)
print("%s_score_mean:" % clf_name, np.mean(cv_scores))
print("%s_score_std:" % clf_name, np.std(cv_scores))
return train, test
1
2
3
4
5
6
7
8
9
10
11
12
def lgb_model(x_train, y_train, x_test):
lgb_train, lgb_test = cv_model(lgb, x_train, y_train, x_test, "lgb")
return lgb_train, lgb_test

def xgb_model(x_train, y_train, x_test):
xgb_train, xgb_test = cv_model(xgb, x_train, y_train, x_test, "xgb")
return xgb_train, xgb_test

def cat_model(x_train, y_train, x_test):
cat_train, cat_test = cv_model(CatBoostRegressor, x_train, y_train, x_test, "cat")

lgb_train, lgb_test = lgb_model(x_train, y_train, x_test)
************************************ 1 ************************************
[LightGBM] [Warning] num_threads is set with nthread=28, will be overridden by n_jobs=24. Current value: num_threads=24
[LightGBM] [Warning] Unknown parameter: silent
Training until validation scores don't improve for 200 rounds
[200]    training's auc: 0.748799    valid_1's auc: 0.730081
[400]    training's auc: 0.764154    valid_1's auc: 0.730891
[600]    training's auc: 0.777375    valid_1's auc: 0.730927
Early stopping, best iteration is:
[439]    training's auc: 0.766861    valid_1's auc: 0.731
[0.7310002011064074]
************************************ 2 ************************************
[LightGBM] [Warning] num_threads is set with nthread=28, will be overridden by n_jobs=24. Current value: num_threads=24
[LightGBM] [Warning] Unknown parameter: silent
Training until validation scores don't improve for 200 rounds
[200]    training's auc: 0.748535    valid_1's auc: 0.731631
[400]    training's auc: 0.764256    valid_1's auc: 0.732332
Early stopping, best iteration is:
[345]    training's auc: 0.76031    valid_1's auc: 0.732483
[0.7310002011064074, 0.7324829219213177]
************************************ 3 ************************************
[LightGBM] [Warning] num_threads is set with nthread=28, will be overridden by n_jobs=24. Current value: num_threads=24
[LightGBM] [Warning] Unknown parameter: silent
Training until validation scores don't improve for 200 rounds
[200]    training's auc: 0.747855    valid_1's auc: 0.73267
[400]    training's auc: 0.763207    valid_1's auc: 0.733776
[600]    training's auc: 0.776409    valid_1's auc: 0.734096
[800]    training's auc: 0.788911    valid_1's auc: 0.733663
Early stopping, best iteration is:
[628]    training's auc: 0.778126    valid_1's auc: 0.734146
[0.7310002011064074, 0.7324829219213177, 0.7341455481432986]
************************************ 4 ************************************
[LightGBM] [Warning] num_threads is set with nthread=28, will be overridden by n_jobs=24. Current value: num_threads=24
[LightGBM] [Warning] Unknown parameter: silent
Training until validation scores don't improve for 200 rounds
[200]    training's auc: 0.749233    valid_1's auc: 0.727753
[400]    training's auc: 0.764767    valid_1's auc: 0.728777
[600]    training's auc: 0.777702    valid_1's auc: 0.728611
Early stopping, best iteration is:
[420]    training's auc: 0.766087    valid_1's auc: 0.728853
[0.7310002011064074, 0.7324829219213177, 0.7341455481432986, 0.7288532795103251]
************************************ 5 ************************************
[LightGBM] [Warning] num_threads is set with nthread=28, will be overridden by n_jobs=24. Current value: num_threads=24
[LightGBM] [Warning] Unknown parameter: silent
Training until validation scores don't improve for 200 rounds
[200]    training's auc: 0.748281    valid_1's auc: 0.733124
[400]    training's auc: 0.763463    valid_1's auc: 0.733781
[600]    training's auc: 0.776921    valid_1's auc: 0.733684
Early stopping, best iteration is:
[536]    training's auc: 0.772805    valid_1's auc: 0.733891
[0.7310002011064074, 0.7324829219213177, 0.7341455481432986, 0.7288532795103251, 0.7338908945947943]
lgb_scotrainre_list: [0.7310002011064074, 0.7324829219213177, 0.7341455481432986, 0.7288532795103251, 0.7338908945947943]
lgb_score_mean: 0.7320745690552286
lgb_score_std: 0.0019639611876869616
1
2
testA_result = pd.read_csv('./testA.csv')
roc_auc_score(testA_result['isDefault'].values, lgb_test)
---------------------------------------------------------------------------

KeyError                                  Traceback (most recent call last)

~\anaconda3\envs\tf13\lib\site-packages\pandas\core\indexes\base.py in get_loc(self, key, method, tolerance)
   2888             try:
-> 2889                 return self._engine.get_loc(casted_key)
   2890             except KeyError as err:


pandas\_libs\index.pyx in pandas._libs.index.IndexEngine.get_loc()


pandas\_libs\index.pyx in pandas._libs.index.IndexEngine.get_loc()


pandas\_libs\hashtable_class_helper.pxi in pandas._libs.hashtable.PyObjectHashTable.get_item()


pandas\_libs\hashtable_class_helper.pxi in pandas._libs.hashtable.PyObjectHashTable.get_item()


KeyError: 'isDefault'

​
The above exception was the direct cause of the following exception:

KeyError                                  Traceback (most recent call last)

<ipython-input-69-262e8275a2db> in <module>
      1 testA_result = pd.read_csv('./testA.csv')
----> 2 roc_auc_score(testA_result['isDefault'].values, lgb_test)
      3 


~\anaconda3\envs\tf13\lib\site-packages\pandas\core\frame.py in __getitem__(self, key)
   2897             if self.columns.nlevels > 1:
   2898                 return self._getitem_multilevel(key)
-> 2899             indexer = self.columns.get_loc(key)
   2900             if is_integer(indexer):
   2901                 indexer = [indexer]


~\anaconda3\envs\tf13\lib\site-packages\pandas\core\indexes\base.py in get_loc(self, key, method, tolerance)
   2889                 return self._engine.get_loc(casted_key)
   2890             except KeyError as err:
-> 2891                 raise KeyError(key) from err
   2892 
   2893         if tolerance is not None:


KeyError: 'isDefault'

金融风控比赛项目任务一赛题理解

Posted on 2020-09-15 | Visitors: ℃
Words count in article: 893

DW金融风控比赛项目任务一赛题理解

天池的入门赛:https://tianchi.aliyun.com/competition/entrance/531830/introduction

该数据来自某信贷平台的贷款记录,总数据量超过120w,包含47列变量信息,其中15列为匿名变量。为了保证比赛的公平性,将会从中抽取80万条作为训练集,20万条作为测试集A,20万条作为测试集B

数据内容

Field Description
id 为贷款清单分配的唯一信用证标识
loanAmnt 贷款金额
term 贷款期限(year)
interestRate 贷款利率
installment 分期付款金额
grade 贷款等级
subGrade 贷款等级之子级
employmentTitle 就业职称
employmentLength 就业年限(年)
homeOwnership 借款人在登记时提供的房屋所有权状况
annualIncome 年收入
verificationStatus 验证状态
issueDate 贷款发放的月份
purpose 借款人在贷款申请时的贷款用途类别
postCode 借款人在贷款申请中提供的邮政编码的前3位数字
regionCode 地区编码
dti 债务收入比
delinquency_2years 借款人过去2年信用档案中逾期30天以上的违约事件数
ficoRangeLow 借款人在贷款发放时的fico所属的下限范围
ficoRangeHigh 借款人在贷款发放时的fico所属的上限范围
openAcc 借款人信用档案中未结信用额度的数量
pubRec 贬损公共记录的数量
pubRecBankruptcies 公开记录清除的数量
revolBal 信贷周转余额合计
revolUtil 循环额度利用率,或借款人使用的相对于所有可用循环信贷的信贷金额
totalAcc 借款人信用档案中当前的信用额度总数
initialListStatus 贷款的初始列表状态
applicationType 表明贷款是个人申请还是与两个共同借款人的联合申请
earliesCreditLine 借款人最早报告的信用额度开立的月份
title 借款人提供的贷款名称
policyCode 公开可用的策略_代码=1新产品不公开可用的策略_代码=2
n系列匿名特征 匿名特征n0-n14,为一些贷款人行为计数特征的处理

提交结果为每个测试样本是1的概率,也就是y为1的概率。评价方法为AUC评估模型效果

评级标准:

AUC(Area Under Curve)

AUC(Area Under Curve)被定义为 ROC曲线 下与坐标轴围成的面积,显然这个面积的数值不会大于1。又由于ROC曲线一般都处于y=x这条直线的上方,所以AUC的取值范围在0.5和1之间。AUC越接近1.0,检测方法真实性越高;等于0.5时,则真实性最低,无应用价值。

ROC曲线

ROC空间将假正例率(FPR)定义为 X 轴,真正例率(TPR)定义为 Y 轴。

TPR:在所有实际为正例的样本中,被正确地判断为正例之比率。

FPR:在所有实际为负例的样本中,被错误地判断为正例之比率。

召回率又称为查全率,正确预测为正样本(TP)占正样本(TP+FN)的百分比

准确率就是判断为准确的所有样本中,到底多少个是真的对的

ROC曲线和PR曲线的区别在与x,y轴不同,ROC的y轴是TPR 就是召回率,但是x轴是FPR表示错误判断占所有负样本的比例

image-20200915225404914

查找 2

Posted on 2020-08-27 | Visitors: ℃
Words count in article: 1.3k

查找2

1. 两数之和

简单题

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

1
2
3
4
给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

暴力法O(N^2)

1
2
3
4
5
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i+1 , len(nums), 1):
if nums[j] == target - nums[i]:
return [i , j]

使用哈希表

1
2
3
4
5
6
7
def twoSum(self, nums: List[int], target: int) -> List[int]:
hash_tab = {}
for i in range(len(nums)):
if target - nums[i] in hash_tab.keys():
return [i, hash_tab[target - nums[i]]]
else:
hash_tab[nums[i]] = i

如果返回的不是键值,而是对应的结果,可以用

排序+双指针

首先可以先排序,此时的数组是从小到大的,使用两个指针,分别从前后两个方向上去找

单步:

  1. 前指针的数值求补数,直到后指针找到
  2. 找到以后,前指针向后,后指针向前
  3. 如果发现数值已经大于该数字,结束后指针查找,重新开始前指针后移

15. 三数之和

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。

此题虽然合上述的问题相似,但是没有利用哈希表来做了,因为哈希表利用了哈希的程序便利性,使用排序加双指针会更好

  1. 首先求的和是0,当从小到大排序完成后,第一个数字必须是小于0的,如果大于0说明已经结束了
  2. 此时双指针一个从上一个循环的值开始(pre),一个从数组尾端开始(end)
  3. 两个while 同时逼近,target = -nums[i] - nums[pre]首先先动后面的,如果小于taget,跳出,前指针后移,如果大于,后指针前移查找直到相等,或者前后指针相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
target = 0
for i in range(len(nums)):
if nums[i] > 0: break
if i != 0 and nums[i] == nums[i-1]:
continue
pre = i + 1
end = len(nums) - 1

while pre < end:
sum = nums[end] + nums[pre]
if -nums[i] > sum:
pre += 1
elif -nums[i] < sum:
end -= 1
elif -nums[i] == sum:
res.append([nums[i], nums[pre], nums[end]])
pre += 1
end -= 1
while pre < end and nums[pre] == nums[pre - 1]:
pre += 1
while pre < end and nums[end] == nums[end + 1]:
end -= 1
return res

16. 最接近的三数之和

1
2
3
输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案

  1. 先排序,第一个是最小的i,
  2. 然后往后查找,如果三个数字和等于target就返回,如果大于,说明可以end调小一点, 如果小于说明可以pre调大一点
  3. 每一次运算完检测差的绝对值是否变小了,如果变小了就记录当前的总和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
temp = nums[0] + nums[1] + nums[2]
res = abs(nums[0] + nums[1] + nums[2] - target)
for i in range(len(nums) - 2):
if i != 0 and nums[i] == nums[i - 1]:
continue
pre = i + 1
end = len(nums) - 1
while pre < end:
t_sum = nums[pre] + nums[i] + nums[end]
if t_sum == target:
return target
else:
if abs(target - t_sum) < res:
res = abs(target - t_sum)
temp = t_sum
if t_sum < target:
pre += 1
else:
end -= 1

return temp

92 ms, 在所有 Python3 提交中击败了94.96%的用户

18. 四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。

1
2
3
4
5
6
7
8
给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。

满足要求的四元组集合为:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

和三数字之和很类似,应该是在之前的上面增加一个循环

由于输出的是数字组合,用排序和双指针实现,首先是排序,确定第一个最小的值,然后确定第二小的值,剩下两个双指针走

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
res = []
nums.sort()
for i in range(len(nums) - 3):
if i != 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, len(nums)-2, 1):

if j > i+1 and nums[j] == nums[j-1]:
continue
pre = j + 1
end = len(nums) - 1

while pre < end:
sum = nums[end] + nums[pre] + nums[i] + nums[j]
if target > sum:
pre += 1
elif target < sum:
end -= 1
elif target == sum:
res.append([nums[i], nums[j], nums[pre], nums[end]])
pre += 1
end -= 1
while pre < end and nums[pre] == nums[pre - 1]:
pre += 1
while pre < end and nums[end] == nums[end + 1]:
end -= 1
return res

由于是N^3的复杂度,速度还是很慢的,可以提前考虑一些极端情况优化下

查找 1

Posted on 2020-08-25 | Visitors: ℃
Words count in article: 1.5k

查找

349. 两个数组的交集

利用set的不重复性,

1
2
3
4
def intersection(self, nums1: List[int], nums2: List[int])
set1 = set(nums1)
set2 = set(nums2)
return [i for i in set1 if i in set2]

62 ms

也可以直接使用set的求交符号,但是底层实现类似

1
2
def intersection(self, nums1: List[int], nums2: List[int]) 
return set(nums1)&set(nums2)

84 ms

350. 两个数组的交集 II

增加了次数的要求,此时就需要一个计数表,使用Counter简单实现

1
2
3
4
5
6
7
8
9
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
res = []
from collections import Counter
cnt1 = Counter(nums1)
for i in nums2:
if cnt1[i] > 0:
res.append(i)
cnt1[i] -= 1
return res

时间 88 ms 有点慢, 复杂度是O(M+N)的

为什么很慢在提示给出了,nums1很小,nums2很大,所以可以稍微加一句if len(nums1) < len(nums2): nums2, nums1 = nums1, nums2 让conter执行较长的,循环较小的,速度比较稳定在60 ms

202. 快乐数

1
2
3
4
5
6
7
输入:19
输出:true
解释:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

定义: 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果 可以变为 1,那么这个数就是快乐数。

题目的建模过程是简单的,分开然后求平方和,不为1就继续,需要判断的是,在发生始终变不到1的情况下,如何及时跳出。而且每一各数字对应的下一个数字都是绝对的,是一个链表一样的情况。

仔细思考可以发现,一个数字的平凡和结果最后是不可能溢出的,那么这个while循环的结果只有两种,变成了1,或者变成了之前的数字,导致有环

用一个set来记录之前出现过的数字,一直迭代下去,如果是出现了重复的数字就是环,返回False就行,这样代码就很简单了

1
2
3
4
5
6
7
8
9
10
11
12
13
def isHappy(self, n: int) -> bool:
num_table = set()
while n >= 1 and n not in num_table:
sum = 0
num_table.add(n)
while n > 0:
n, mod = divmod(n, 10)
sum += mod ** 2
if sum == 1:
return True
else:
n = sum
return False

290. 单词规律

1
2
输入: pattern = "abba", str = "dog cat cat dog"
输出: true

遵循 指完全匹配,例如, pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律

很明显的映射关系,只要一个个匹配就行,对pattern中的每个a,b,c 都存放在一个dict,a对应的是dog

pattern str_list
a dog
b cat
c apple
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def wordPattern(self, pattern: str, str: str) -> bool:
str_list = str.split(' ')
if len(pattern) != len(str_list):
return False
hash_table = {}
for i in range(len(pattern)):
if pattern[i] not in hash_table.keys():
if str_list[i] in hash_table.values():
return False
else:
hash_table[pattern[i]] = str_list[i]
elif hash_table[pattern[i]] != str_list[i]:
return False
return True

算法时间 40 ms 复杂度是O(N)级别

451. 根据字符出现频率排序

这个就是典型的排序加哈希表题,哈希表存储每个字符的出现次数

1
2
3
4
5
6
7
8
9
输入:
"cccaaa"

输出:
"cccaaa"

解释:
'c'和'a'都出现三次。此外,"aaaccc"也是有效的答案。
注意"cacaca"是不正确的,因为相同的字母必须放在一起。

采用Counter 来计数,喜欢自己写的也可以用dict实现,效率没有太大区别

1
2
3
4
5
6
7
8
9
10
def frequencySort(self, s: str) -> str:
from collections import Counter
s1 = Counter(s)

s2 = sorted(s1.items(),key=lambda item:item[1],reverse=True)

res = ''
for key,value in s2:
res += key*value
return res

执行时间 40 ms

242. 有效的字母异位词

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词

1
2
输入: s = "anagram", t = "nagaram"
输出: true

满足字符串的长度,字母出现的次数一致即可,那还是用两个Counter来实现应该最为简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def isAnagram(self, s: str, t: str) -> bool:
if s is None or t is None:
return False
if len(s) != len(t):
return False

from collections import Counter
cnt1 = Counter(s)
cnt2 = Counter(t)
char_tab = cnt2.keys()
for char in cnt1.keys():
if char not in char_tab:
return False
elif cnt2[char] != cnt1[char]:
return False
return True

时间:44 ms, 在所有 Python3 提交中击败了96.13%的用户

205. 同构字符串

如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换,同时保留字符的顺序。两个字符不能映射到同一个字符上,但字符可以映射自己本身

这个题和上面的单词规律是一样,都检查映射关系是否正确:

一个非常python 的写法是

map(s.index, s) == map(t.index, t)

由于返回的是map的对象,没有实现 == 运算符重载

1
2
def isIsomorphic(self, s: str, t: str) -> bool:
return list(map(s.index,s)) == list(map(t.index,t))

540. 有序数组中的单一元素

一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数

1
2
输入: [1,1,2,3,3,4,4,8,8]
输出: 2

如果全都是两个的,那么肯定num[奇数] == nums[偶数],由于只有一个,导致后面发生变化,每一次取一个mid,来缩短查询距离,如果mid是偶数,那么和1异或的话,那么得到的是mid+1,如果mid是奇数,得到的是mid-1。如果相等的话,那么唯一的元素还在这之后,往后找就可以了

1
2
3
4
5
6
7
8
9
def singleNonDuplicate(self, nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] == nums[mid ^ 1]:
lo = mid + 1
else:
hi = mid
return nums[lo]

动态规划

Posted on 2020-08-22 | Visitors: ℃
Words count in article: 2.6k

动态规划

动态规划:结合了分治思想和回溯思想的一种动态解决子问题的方法,本质是一个问题由多个子问题组合

WHY:相对于朴素解法,由于可以利用子问题的结果来简化下一子问题的计算,计算复杂度的提升巨大,同时采用了类似回溯的方法来剪枝

HOW:使用DP 需要有一个状态转移的概念,不一定要非常格式化的按照DP的状态转移方程来思考,但是得有状态转移的一个列表

300. 最长上升子序列

本题相对最长连续子序列减少了连续的条件,由于有多种组合导致回溯的情况问题的时间复杂度预计应该是在O(NlogN), 是典型的数组问题,使用指针的思维实现

如果存在一个最优子序列,那么包含该seq的所有seq(不超过原序列)的最优解都是这个seq的长度

### 单步

思考一个单步过程,对每一个数字,都查找以后的是否有比这个数字大的,如果有说明存在以这个数字开头的上升序列,更新子序列最大的数字,但是这个最大数字并非是最优的,可能存在一个比这个最大数字小,但是比上一个的数字大的,例如【2,5,4,3,。。】此时子序列的最大数字应该是3而不是5

遍历完可以找到一个子序列,计算长度就可以了。这个算法的计算复杂度是N^2

可以简单的写一个伪代码,了解题目意思;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def lengthOfLIS(self, nums) -> int:
max_len = 0
if not nums:
return max_len
for i in range(len(nums)):
tmp_max_num = nums[i]
tmp_max_num2 = nums[i]
res = []
res.append(tmp_max_num)
for j in range(i+1, len(nums), 1):
if nums[j] > tmp_max_num:
tmp_max_num2 = tmp_max_num
tmp_max_num = nums[j]
res.append(nums[j])
elif nums[j] > tmp_max_num2:
res.remove(tmp_max_num)
res.append(nums[j])
tmp_max_num = nums[j]
max_len = max(max_len, len(res))
return max_len

这个算法N2 的复杂度,时间是1044ms

思考一个更优化的的动态规划算法单步执行,对于数字的分治方法,都是将一个长的数组转化为多个小数组(子序列),并将子问题的答案存在一个dp[]中,然后对这个dp数组处理得到result

再优化一下,由于原数组很长,但是维护的res数组很短,而且反复申请空间消耗的时间很长,干脆每一次遍历的时候都找一下有序数组res里面有没有比这个数字更大的数字,如果没有就说明这个是子序列的最大值,有就替换一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def lengthOfLIS(self, nums) -> int:
if not nums or not len(nums):
return 0
records = []
records.append(nums[0])
for i in range(1, len(nums)):
if nums[i]>records[-1]:
records.append(nums[i])
else:
j = len(records)-1
while j>=0:
if records[j]>=nums[i]:
j-=1
else:
break
records[j+1]=nums[i]
return len(records)

时间50ms

674. 最长连续递增序列

这个问题相对上一个更加简单,遍历就完事了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
max_len = 0
if nums is None : return max_len
if len(nums) > 1 :
max_len += 1
elif len(nums) == 0:
return 0
else:
return 1
max_all = 0
for i in range(1, len(nums)):
if nums[i] > nums[i-1]:
max_len += 1
else:
max_len = 1
max_all = max(max_all, max_len)
return max_all

用上动态规划,就是把每一回找到的连续数组的长度用一个dp【】来保存,此时对于每一个子序列都求一个最大长度,求解每一个,但是这个小问题有点浪费内存

5. 最长回文子串

DP经典问题,题目还是子序列的求最优化的问题,一般都有多项式级别的暴力解,子序列不同的序列头和序列尾可以生成n(n-1)/2个子序列,只要对每个子序列判断一次是否回文即可

分析一个序列判断回文的单步:

1, 分析是否头尾相同

2, 然后while 逐步分析两段是否相同

3,直到两个指针指向同一个或者只相差1个位置结束

暴力算法的复杂度是N^3,考虑使用动态规划来简化

可以定义一个dp[i][j]为一个从位置i到位置j的一个子序列是否是回文。

这个看起来是很简单的过程,但是问题其实可以思考到每一个子序列存在相关性,字串不是回文,那么父亲序列绝对不是回文,但是一个子序列若是回文,那它的下一位父亲序列s[i-1]到[j+1]还要判断多出来的s[i-1] == [j+1]就知道是不是回文了,这就是一个递推的一个状态过程

不断的找序列然后找到j-i 最大的那个存在回文的序列即是最长的回文子串

分析一个单步过程:

对于每一个子串i, j=i+n, (n)表示长度为n, n必须满足小于总长len-i-1

  1. 如果n==0 表示只有字串一位肯定是满足的,n==1, 判断是否s[i]==s[j]相等就是aa这种情况,也是满足的
  2. 如果都不满足说明,长度超过1了,那么需要判断它的字串的状态dp[i+1][j-1]和s[i]==s[j] 两者同时成立才可以。
  3. 如果上一条的情况都成立,说明新父亲串是一个回文,此时判断长度是否大于当前最大的回文串是否要更新就行

最后返回最长串的回文字符串

运行时间:4644ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def longestPalindrome(self, s: str) -> str:
len_s = len(s)
res = ''
max_len = 0
dp = [[False] * len_s for _ in range(len_s)]
for i in range(len_s-1, -1, -1):
for n in range(len_s - i):
j = i+n
if n == 0:
dp[i][j] = True
elif n == 1:
dp[i][j] = True if s[i] == s[j] else False
else:
dp[i][j] = (dp[i+1][j-1] and s[i] == s[j])
if dp[i][j] and n+1 > max_len:
max_len = n+1
res = s[i:j+1]
return res

速度很慢,主要字符串的长度太长,可以采用Manacher 优化到o(N) 有空自再思考

516. 最长回文子序列

相比于上题,减少了连续的条件,此时生成的回文可以不用连续,子序列的数量没有增加,但是要判断的内容变化了, 之前是一次两步长的判断,现在是一次左右可以多步

使用DP的方法,矩阵的数量可以不用改变,但是状态转换的递归条件发生了变化

之前是只判断子序列是否为回文,由于序列的最大回文存在,数量肯定是在最长的序列

​ 此时DP矩阵中存储的是数值, 表示此时子序列(问题)的最大回文长度

状态转移过程:如果满足s[i]==s[j](‘abba’) 此时的序列相对于dp[i+1][j-1]对应的序列(‘bb’)多两个长度,

​ 如果不满足条件(‘abbc’)此时的序列就是比较子序列dp[i][j-1](‘abb’)和dp[i+1][j](‘bbc’)两个谁更大,如果都一样,说明增加的没有区别,不一样说明长度增加了,需要注意要从右下角开始往上遍历,因为每次都需要利用的子序列位于矩阵的左下脚dp[i + 1][j - 1],左边dp[i][j - 1],下边dp[i+1][j]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
len_s = len(s)
dp = [[0] * len_s for _ in range(len_s)]
for i in range(len_s):
dp[i][i] = 1
for i in range(len_s, -1, -1):
for j in range(i + 1, len_s):
# print(s[i:j+1])
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
return dp[0][-1]

运行时间1512 ms

72. 编辑距离

DP中较难的题,编辑距离又叫levenshtein长度,在字符串匹配库,搜索引擎elastic search内都有应用,复杂度最低应该O(mn),表示至少每个字符都对比一下,一般使用C实现库再调用

存在三种方法编辑,编辑距离为1的情况是len*(2+26), 能编辑的字符串数量是指数增长的,暴力法就不太可能实现了

一个初步的思考是编辑距离为2的序列中间过程应该是由距离为1的再来了一次距离为1的过程,这应该要用递归来做

思考word1 和word2 可能有子问题

1
2
3
4
ho -> ro	ho -> ros 	ho -> rose
hor -> ros hor -> rose
hors -> rose
horse -> rose

但是这个开头都是固定的,但是很明显开头和结尾都不是固定的,像or-> ro这样的子问题也可能出现

可以设置dp[i][j]表示字符长度为i的字符串和长度为j的字符串的最短编辑距离,那对于一个单步过程,如果dp[i][i]是0时,说明第i个前面都是一样的

  1. 判断s1[i+1]和s2[j+1]是否相等,如果相等说明两个指针各进一步不影响结果
  2. 如果不等就需要判断这一次的状态改变是如何导致dp[i+1][j+1]变化
  3. 判断插入操作,当我们在word1中插入一个和word2一样的字符,那么word2就被匹配了,所以可以直接表示为dp[i][j-1]+1 对于删除操作,直接表示为dp[i-1][j]+1 对于替换操作,直接表示为dp[i-1][j-1]+1 所以下一个状态就是min(三者)

最后输出结果就是dp[m][n]的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def minDistance(self, word1, word2):
m=len(word1)
n=len(word2)
dp=[[0 for _ in range(n+1)] for _ in range(m+1)]
#空字符串的初始化
for i in range(n+1):
dp[0][i]=i
for j in range(m+1):
dp[j][0]=j
# 每一次一个指针走一步
for i in range(1,m+1):
for j in range(1,n+1):
if word1[i-1]==word2[j-1]:
dp[i][j]=dp[i-1][j-1]
else:
#不同情况递归求下一个状态,分治思想
dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
return dp[-1][-1]

运行时间200 ms

分治算法

Posted on 2020-08-17 | Visitors: ℃
Words count in article: 1.2k

分治算法:

what: 是一个将母问题分为相同子问题来简化计算的算法

How: 基本有三步,

  1. 将问题转化为相同的小问题
  2. 递归解相同的小问题
  3. 将上述小问题的结果综合并返回

Why:

​ 主要是重复利用堆栈,效率上的提升主要是针对计算数量级逐级快速递增的,解决的问题主要是计算量大

POW(X,n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def myPow(self, x: float, n: int) -> float:
# 数据预处理
res = 1.0
if n ==0:
return res
if n < 0:
x = 1 /x
n = -n
# 问题划分
if n%2 == 0:
res = self.myPow(x*x, n/2)
return res
else:
res1 = self.myPow(x, n-1)
# 集合所有的结果
res = res1*x
return res

注意:

​ 从解决问题的角度,算法只用

​

1
2
3
4
5
6
7
8
9
10
11
12
13
def myPow(self, x: float, n: int) -> float:
# 数据预处理
res = 1.0
if n ==0:
return res
if n < 0:
x = 1 /x
n = -n
# 问题划分
res1 = self.myPow(x, n-1)
# 集合所有的结果
res = res1*x
return res

但是会导致一个问题

​ 递归的栈爆了,采取稍微减少点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def myPow(self, x: float, n: int) -> float:
# 数据预处理
res = 1.0
if n ==0:
return res
if n == 1:
return x
if n == -1:
return 1.0/x
if n < 0:
x = 1 /x
n = -n
# 问题划分
if n%2 == 0:
res = self.myPow(x*x, n//2)
return res
else:
res1 = self.myPow(x*x, (n-1)//2)
# 集合所有的结果
res = res1*x
return res

53. 最大子序和

分治思路:

一个序列中的最大子序列和可以分为三个部分, 左半部分的子序列和,右半部分的子序列和,从中间开始的最大子序和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# 结束条件
if len(nums) == 1:
return nums[0]
if nums is None or len(nums) == 0:
return None
# 划分子问题
max_sum_l = self.maxSubArray(nums[:len(nums)//2])
max_sum_r = self.maxSubArray(nums[len(nums)//2:])
# 从中间开始
m_left = nums[len(nums)//2 - 1]
m_right = nums[len(nums)//2]
temp = 0
for i in range(len(nums)//2 - 1, -1, -1):
temp += nums[i]
m_left = max(m_left, temp)
temp = 0
for i in range(len(nums)//2, len(nums)):
temp += nums[i]
m_right = max(m_right, temp)
return max(max_sum_l, max_sum_r, m_right+m_left)

这个算法不是很好,计算的复杂度还是O(n)的,因为每一次的决策是否加入后面的序列可以根据上一次的计算结果,采用动态规划也可以, 提前算好每一次前几个序列和和,还可以减少空间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
dp = [0] * len(nums)
# 存储每一步的最优结果
dp[0] = nums[0]
max_num = nums[0]
for i in range(1, len(nums)):
# 对于每一次更新加入i个数字后的序列的最佳子序列和
dp[i] = max(dp[i-1]+nums[i], nums[i])
if dp[i] > max_num:
max_num = dp[i]
return max_num

169. 多数元素

​ 对于这种求出现次数的问题,python中collection模块中的Count 很好用, 但是本文没有使用该方法,一个简单的思路是用一个dict来统计出现的次数,然后便利这个字典求出最大次数的即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def majorityElement(self, nums: List[int]) -> int:
table = {}
for i in nums:
if i in table.keys():
table[i] += 1
else:
table[i] = 1
max_freq = 0

for key in table.keys():
if table[key] > max_freq:
max_freq = table[key]
temp = key
return temp

但是这个不是我们的目标,我们的目标是学会利用分治的思想

传统的分治思想对于数组来说,基本上就是从空间上划数组的范围达到分解问题再组合,这个题目其实利用了一个假设,就是如果一个数字出现的次数最多,要么在左边数量最多,要么在右边数量最多

按照这个假设就可以做题了,首先分为两个部分,然后再来求两边的哪一个最大,如果分到只剩下这一个就返回这个数值

1
2
3
4
5
6
7
8
9
10
11
12
def majorityElement(self, nums) -> int:
if nums is None:
return None
if len(nums) == 1:
return nums[0]
left = self.majorityElement(nums[: len(nums) // 2])
right = self.majorityElement(nums[len(nums) // 2:])
if right == left:
return right
else:
# N+N
return right if nums.count(right) > nums.count(left) else left

使用分治的算法其实相比哈希的方法更慢,因为最后都有个查询次数的遍历,反而计算量更大

最佳的办法还是使用Conter 方法最快,然后使用most_commen 函数找最常见的,然后返回

1
2
3
4
from collections import Counter
def majorityElement(self, nums) -> int:
c = Counter(nums)
return c.most_common(1)[0][0]

还有利用条件n/2 的,先排序再取中间值,虽然速度很快,但是计算复杂度是nlog(n)的,速度快只是运气好主频高而已

从零开始爬取疫情并云端数据可视化

Posted on 2020-03-03 | Visitors: ℃
Words count in article: 1.3k

从零开始爬取疫情并云端数据可视化

实验OS环境:Win10 /ubuntu 16.04

安装python

首先需要安装Python, windows版本在Python网站下载 msi安装版 (py3.71)

  • Win64版本下载网址
    avatar
    自动添加环境变量勾选下方“Add Python 3.7 to PATH”
    avatar
    手动设置环境变量:在系统环境变量中添加安装路径 (省略号表示安装路径的前缀)
    ….\Python37\Scripts\;….\Python37\

  • Linux版本教程

step1:测试安装

输入python 回车出现下述shell场景表示安装成功, 输入exit()退出

asd

安装Streamlit

streamlit 是第一个专门针对机器学习和数据科学团队的应用开发框架,它是开发自定义机器学习工具的最快的方法,可以调用tornado与其他可视化包的网站框架。官网地址

本文使用streamlit的地图可视化官方教程Github

step2: 测试安装成果

  • cmd 输入 pip install streamlit, 安装完成后输入streamlit hello 测试是否安装成功,浏览器中进入 http://localhost:8501 出现下述场景表示安装完成, cmd中按住ctrl+c可以退出

    34o3PU.png

  • cmd 输入 pip install json, 完成安装json解析库

    avatar

在丁香园网上爬取数据

step3:创建web_get.py文件

​ 需要导入的依赖库有

1
2
3
4
5
6
import streamlit as st
import pydeck as pdk
import pandas as pd
from urllib import request
import json
import re

step4:使用爬虫爬取丁香园数据

  • 首先在浏览器进入丁香园网址 按下F12查看网页信息,找到数据项藏在<strip id = "window.getAreaStat"></strip>中

34otM9.png

  • 写一个正则表达式,将中间的数据提取出来
    want = re.compile(r' window.getAreaStat.*?</script>', re.S)

  • 对html进行匹配得到数据,并转化为string格式

    result = want.findall(str(html.decode("utf-8")))

  • 此时的结果是字符串格式的

  • 需要对数据处理,将不必要的符号和其他的无意义单词去除

  • 将字符串转化为json格式:

    json.loads(result)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

def get_data_from_web():
user_agent = "ritarma/1.0 (X11; Ubuntu; Linux x86_64; rv:72.0) Gecko/20100101 Firefox/72.0"
headers = {"User-Agent": user_agent}
req = request.Request(
"https://3g.dxy.cn/newh5/view/pneumonia?scene=2&clicktime=1579596108&enterid=1579596108&from=groupmessage"
"&isappinstalled=0",
headers=headers)
resp = request.urlopen(req)
# 打开页面
try:
html = resp.read()
except http.client.IncompleteRead as e:
html = e.partial

want = re.compile(r' window.getAreaStat.*?</script>', re.S)
result = want.findall(str(html.decode("utf-8")))
result = str(result).replace(" ", "")
# 处理结果
result_p = result
# print('处理结果:',result)
result_p = result_p.replace(']}catch(e){}</script>', " ")
result_p = result_p.replace('}', "}\n")
result_p = result_p.replace('window.getAreaStat=[', " ")
result_p = result_p.replace("[' ", "")
result_p = result_p.replace(" ']", "")
json_output = json.loads('[' + result_p + ']')
return json_output
`

地图可视化

step5:转化数据格式,

​ 分析json格式的输出,里面的格式是字典类型的映射,获得省份的数据使用data['provinceName']获得各个城市的确诊人数data['provinceName']['cities']['confirmedCount'], 此时只有当前省份和城市的数据,要在地图上是可视化需要得到各个城市的地理坐标(经纬度信息)

​ 在pyecharts中查询地理坐标需要导入中国城市的地图包,本文使用一个带有全国地理信息的json文件作为原始信息,并对该文件解析,得到各个城市的地理位置信息。该json文件来源于网络,需要对一些不规则的结构略作处理,并对地名找不到的异常处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def get_lat_by_name(name: str, pos_dic):
pos_data = str(pos_dic[name]).split(',')
lat = float(pos_data[0])
lon = float(pos_data[1])
return lat, lon

def get_pos_by_json(url='geo_info/geoinfo-all.json'):
"""
get all cities position form json file
:return: dictionary of [cityName, (lat, lon)]
"""
with open(url, 'r', encoding='UTF-8') as f:
all_city_pos = json.loads(f.read())
pos_dic = {}
for province in all_city_pos:
# pos_dic.update({province['name'].replace('市', ''): province['center']})
pos_dic.update({province['name']: province['center']})
if province['name'] != '重庆市':
for city in province['districts']:
pos_dic.update({city['name'].replace('市', ''): city['center']})
else:
for city in province['districts']:
for districts in city['districts']:
pos_dic.update({districts['name']: districts['center']})
return pos_dic

转化为需要的格式[cityName, counts, latitude, longitude]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def get_cities_data(json_output, pos_dic):
"""
get all cities data form json and position dictionary
:return: list of [lat, lon, cityName, counts]
"""
city_list = []
for province in json_output:
if province['provinceName'] == '台湾':
lat, lon = get_lat_by_name(province['provinceName'], pos_dic)
city_list.append([lat, lon, province['provinceName'], province['confirmedCount']])
for city in province['cities']:
try:
lat, lon = get_lat_by_name(city['cityName'], pos_dic)
city_list.append([lat, lon, city['cityName'], city['confirmedCount']])
except KeyError:
try:
lat, lon = get_lat_by_name(city['cityName' + '区'], pos_dic)
city_list.append([lat, lon, city['cityName'], city['confirmedCount']])
except KeyError:
pass

return city_list

​ 最后将数据转化Pandas包的DataFrame 格式

data = get_cities_data(get_data_from_web(), get_pos_by_json())

data = pd.DataFrame(data, columns=['lat', 'lon', 'cityName', 'counts'])

step6: 可视化

streamlit 使用的数据可视化包是Uber团队开发的开源地图deck.gl 在安装streamlit的同时已经附带安装了deckgl的python封装库pydeck。

​ 此时直接将数据输入pydeck的接口中不能完全显示,需要先定义一个摄像机观察位置

​ view_point= [32.33, 113.32]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# initial view state :
view_state = pdk.ViewState(latitude=view_point[0], longitude=view_point[1], zoom=4, pitch=40, bearing=-27.36)

column_layer = pdk.Layer(
"ColumnLayer",
data=city_data,
get_position=["lat", "lon"],
radius=15000,
diskResolution=24,
elevation_scale=90,
elevation_range=[0, 10000],
getElevation='counts',
getFillColor='[48, 128, counts*3, 225]',
getLineColor=[0, 0, 0],
pickable=True,
)

st.write(pdk.Deck(
map_style="mapbox://styles/mapbox/dark-v10",
initial_view_state=view_state,
layers=[column_layer],
))

在当前的python文件路径下使用cmd输入

streamlit run you_file_name.py

step7: 浏览器打开网址loacalhost:8501

avatar

1
cmd下输入 ctrl+c 可以退出

Untitled

Posted on 2019-08-16 | Visitors: ℃
Words count in article: 48

交叉熵与基于交叉熵的损失函数

交叉熵

概念:首先解释解信息熵:信息熵是用来消除不确定性所需信息的度量,W()CA

Java的HashMap

Posted on 2019-05-14 | Visitors: ℃
Words count in article: 157

HashMap

主要参数: capacity,loadFactor

1
2
3
4
5
6
7
java.lang.Object
↳ java.util.AbstractMap<K, V>
↳ java.util.HashMap<K, V>

public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable { }

继承了抽象类AbstractMap,实现了Map、Cloneable、java.io.Serializable接口。

img

threshold的值=”容量*加载因子”

当HashMap中的容量到threshold,重建Hash表,将容量加倍

table主要存储容器,每个单元Entry都是带hash(int)和next的对

为什么使用hash: 为了效率

使用hash会有什么不好的后果 空间换时间,产生哈希冲突

HashMap中如何解决这问题:散列表—>Entry的next

Untitled

Posted on 2019-05-12 | Visitors: ℃
Words count in article: 345

Text Classification Read notes

解决文本分类的问题
流程:

​ 特征提取 ->> (特征降维) >> 分类→评估

1557644929766

基于机器学习和深度学习都有一个难以避免的特点,就是模型本身的鲁棒性相对不够,但是处理的问题都十分复杂,对文本的预处理十分重要:

特征提取与清洗

文本数据的清洗:

 1. 分词:Tokenization
 2. 去除意义不大的词语{啊,一,后,前}
 3. 大小写问题解决
 4. 口语化和简称
 5. 降噪{不必要的标点}
 6. 语法错误
 7. 词语的时态
 8. 还原词形

词语的语法分析

1. N-Gram

加权词语

1. 词袋模型(不计算顺序与上下文,将所有的 词扔进一个袋子中,附送的都是出现次数,基于单热编码)
 2. 词向量模型(神经忘录得到高位向量,具有上下文信息,但是并不能包含长连续全部的语义)

此处注意的事:并不是词向量(word2Vec)就是最好的,在贝叶斯邮件分类,文本分类中,词袋模型的下效率高,仅仅有文章的内容信息,鲁棒性更好

特征降维

  1. PCA 主成分分析法应用非常广
  2. ICA 独立成分分析,在线性的模型中应用多
  3. LDA ,NMF
12

Ritarma Arthur

The place for Rita show his learning notes and personal insights

13 posts
6 tags
RSS
GitHub E-Mail
© 2020 Ritarma Arthur | Site words total count: 15.1k
Powered by Hexo
|
Theme — NexT.Muse v5.1.4
博客全站共15.1k字