勉強したことについてまとめるサイト

勉強したことをまとめるだけのサイト、数学、プログラミング、機械学習とか

Let's Encrypt SSL化(apache) がQiitaで検索した手順通りで進めても一時ファイル作成するコマンドで落ちる

Apacheサーバーをssl

Apacheサーバーをssl化したくてググってたらまぁいっぱい記事が出てきてたから、 あーこれ余裕ー ( ´_ゝ`)フーン とかって思ってたら割と時間溶かしたのでメモ。

スクリーンショット 2021-01-11 13.34.58.png

問題点

certbotの導入は色々な記事に載ってるので、調べれば素晴らしい記事がいっぱい出てくると思います。自分はこちらを参考にさせていただきました。感謝

Let's Encryptで無料SSL化(apache)

記事通り進めたけど。。。Type: unauthorizedエラーが出る。。。

色々な記事で紹介されている通り、こんな感じのコマンドをうつ。 そうすると指定されたドキュメントルート(アプリのメインルート)に一時ファイルが作成されてそのファイルに80番ポートからアクセスできるかを確認してアクセスできたらOKということで認証完了するみたいだけれどもここがなぜかできない。

$ certbot certonly –webroot -w [ドキュメントルート] -d [SSLをかけたいドメイン・URL] –email [メールアドレス]

しかし!Type: unauthorizedが出て先に進めない。

Domain: mydomain.com
Type:   unauthorized
Detail: Invalid response from
http://mydomain.com/.well-known/acme-challenge/rwH-dBrZhXrgii7uiGmccp8GFMOdv1RRRHrBSVfkWuU


To fix these errors, please make sure that your domain name was
entered correctly and the DNS A/AAAA record(s) for that domain
contain(s) the right IP address.

解決方法

@s-katsumataさんの記事に書いてあったもので解消できました。ありがとうございます。mm

certbot(LetsEncrypt)でエラー/Invalid response from

--webrootでなく--apacheオプションを付与して証明書を再取得するだけ。これだけで本当にいけた!

$ certbot certonly --agree-tos --non-interactive -d [ドメイン名] --webroot -w [ドキュメントルートのパス] --email [管理者のメールアドレス]

certbot certonly --agree-tos --non-interactive -d [ドメイン名] --apache -w [ドキュメントルートのパス] --email [管理者のメールアドレス]

に変えたらできました。

LGTM第一号、わーい

個人的にはLGTMってちょっと上から目線なのであまり好きではありませんが、まぁこれしかないので許してください。mm

LGTMをTYFUGQ(Thank You for Your Great Qiita)とかにして欲しい。 なげえかw じゃあ、THXで(Thank you!/Thanks!!)がいいかな

スクリーンショット 2021-01-11 13.43.26.png

"Rossman Store Sales Prediction" : XgBoostで予測モデルを作成

Rossman Store Sales Prediction from kaggle

問題:

Rossmann operates over 3,000 drug stores in 7 European countries. Currently, Rossmann store managers are tasked with predicting their daily sales for up to six weeks in advance. Store sales are influenced by many factors, including promotions, competition, school and state holidays, seasonality, and locality. With thousands of individual managers predicting sales based on their unique circumstances, the accuracy of results can be quite varied.

今回のケースではXgBoostを使用する

XgBoost XGboostは「eXtreme Gradient Boosting」の略で2014年に発表された手法です。

勾配ブースティングと呼ばれるアンサンブル学習と決定木を組み合わせた手法で非常に高い汎化能力を誇ります。

アンサンブル学習とは、弱学習器(それほど性能の高くない手法)を複数用いて総合的に結果を出力する方法で、バギングとブースティングというタイプがあります。

バギングは弱学習器を並列に使うイメージ。決定木とバギングを組み合わせたのがランダムフォレストです。 会社の売り上げを予測する機械学習プロセス。 ロジスティック回帰などの回帰直線を計算して、回帰直線の示す値から未来の月の売り上げなどを予測する。

必要なライブラリをインポート

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inline

import seaborn as sb 

データの読み込み

train = pd.read_csv('train.csv')
test = pd.read_csv('test.csv')
store = pd.read_csv('store.csv')

Data fields Most of the fields are self-explanatory. The following are descriptions for those that aren't.

Id - an Id that represents a (Store, Date) duple within the test set Store - a unique Id for each store Sales - the turnover for any given day (this is what you are predicting) Customers - the number of customers on a given day Open - an indicator for whether the store was open: 0 = closed, 1 = open StateHoliday - indicates a state holiday. Normally all stores, with few exceptions, are closed on state holidays. Note that all schools are closed on public holidays and weekends. a = public holiday, b = Easter holiday, c = Christmas, 0 = None SchoolHoliday - indicates if the (Store, Date) was affected by the closure of public schools StoreType - differentiates between 4 different store models: a, b, c, d Assortment - describes an assortment level: a = basic, b = extra, c = extended CompetitionDistance - distance in meters to the nearest competitor store CompetitionOpenSince[Month/Year] - gives the approximate year and month of the time the nearest competitor was opened Promo - indicates whether a store is running a promo on that day Promo2 - Promo2 is a continuing and consecutive promotion for some stores: 0 = store is not participating, 1 = store is participating Promo2Since[Year/Week] - describes the year and calendar week when the store started participating in Promo2 PromoInterval - describes the consecutive intervals Promo2 is started, naming the months the promotion is started anew. E.g. "Feb,May,Aug,Nov" means each round starts in February, May, August, November of any given year for that store

データの確認

print('Training Data Shape : ',train.shape)
print('Test Data Shape : ',test.shape)
print('Store Data Shape : ',store.shape)
Training Data Shape :  (1017209, 9)
Test Data Shape :  (41088, 8)
Store Data Shape :  (1115, 10)

Pandas head() データフレームの最初のn行を返す

・ここでOpen == 1の箇所は店舗が閉鎖していることを意味するので、ここではオープンされている店舗のみを採用する。そのため下記の処理で、すでに営業していいない店舗を省く作業を行なっている。

train.head()
Store DayOfWeek Date Sales Customers Open Promo StateHoliday SchoolHoliday
0 1 5 2015-07-31 5263 555 1 1 0 1
1 2 5 2015-07-31 6064 625 1 1 0 1
2 3 5 2015-07-31 8314 821 1 1 0 1
3 4 5 2015-07-31 13995 1498 1 1 0 1
4 5 5 2015-07-31 4822 559 1 1 0 1
test.head()
Id Store DayOfWeek Date Open Promo StateHoliday SchoolHoliday
0 1 1 4 2015-09-17 1.0 1 0 0
1 2 3 4 2015-09-17 1.0 1 0 0
2 3 7 4 2015-09-17 1.0 1 0 0
3 4 8 4 2015-09-17 1.0 1 0 0
4 5 9 4 2015-09-17 1.0 1 0 0
store.head()
Store StoreType Assortment CompetitionDistance CompetitionOpenSinceMonth CompetitionOpenSinceYear Promo2 Promo2SinceWeek Promo2SinceYear PromoInterval
0 1 c a 1270.0 9.0 2008.0 0 NaN NaN NaN
1 2 a a 570.0 11.0 2007.0 1 13.0 2010.0 Jan,Apr,Jul,Oct
2 3 a a 14130.0 12.0 2006.0 1 14.0 2011.0 Jan,Apr,Jul,Oct
3 4 c c 620.0 9.0 2009.0 0 NaN NaN NaN
4 5 a a 29910.0 4.0 2015.0 0 NaN NaN NaN

not_openにtrainの中のデータのOpen == "0"というデータを取得してきている。店舗が営業していないということは、売り上げも0になるはずなので、(train['Sales'] != 0)]で店舗の売り上げがない部分を抽出。

ここで確認していることは、営業していないのに売り上げがある店舗と、営業しているのに売り上げがない店舗は不自然なのでそのようなデータが混在していないかを確認している。

not_open = train[(train['Open'] == 0) & (train['Sales'] != 0)]
print("No closed store with sales: " + str(not_open.size == 0))
no_sales = train[(train['Open'] == 1) & (train['Sales'] <= 0)]
print("No open store with no sales: " + str(no_sales.size == 0))
No closed store with sales: True
No open store with no sales: False

trainデータセットの中のSalesデータが0のものは省くため、train.loc[train['Sales'] > 0]として、Salesが0より上のものをtrain変数に再代入している。

train = train.loc[train['Sales'] > 0]

Salesデータが0のデータを省いたデータセットを再代入したtrainデータセットを再度shape表示してどのような配列になっているかを確認する。

行数・列数を取得: df.shape pandas.DataFrameのshape属性で行数と列数をタプル(行数, 列数)で取得できる。

以上より、trainデータの中身は 列数:9列 行数:844338行 のデータセットとなっている。

print('New Training Data Shape : ',train.shape)
New Training Data Shape :  (844338, 9)

データセットにあるDateカラムをソートして、最初と最後のデータを取得してくることでこのデータの取得されている期間を調べることができる。

dates = pd.to_datetime(train['Date']).sort_values()
dates = dates.unique()
start_date = dates[0]
end_date = dates[-1]
print("Start date: ", start_date)
print("End Date: ", end_date)
date_range = pd.date_range(start_date, end_date).values
Start date:  2013-01-01T00:00:00.000000000
End Date:  2015-07-31T00:00:00.000000000

Visualization

  • データの可視化

matplotlib.pyplot.subplots

Matplotlibの使い方④(plt.subplots、plt.title、plt.legend)|Pythonによる可視化入門 #4 このページの説明を見た方がわかりやすいかもしれないが、グラフを同時に複数枚同列に表示する場合に使用する。今回の場合では8つ同時にプロットしているので、その時に使用している。

plt.rcParams['figure.figsize'] = (15.0, 12.0)

f, ax = plt.subplots(7, sharex=True, sharey=True)
for i in range(1, 8):
    data = train[train['DayOfWeek'] == i]
    ax[i - 1].set_title("Day {0}".format(i))
    ax[i - 1].scatter(data['Customers'], data['Sales'], label=i)

plt.legend()
plt.xlabel('Customers')
plt.ylabel('Sales')
plt.tight_layout()
plt.show()

output_11_0.png (59.6 kB)

General Corelation between customer and sales Observed in the above plot

下記の散布図では、 train['Customers']をx軸にとり、 train['Sales']をy軸に取ったグラフを表示している。 ここでは、週の曜日と売上に相関関係があるかどうかを散布図として示している。色が同じものは同じ週の曜日なので、それぞれどこの曜日の売り上げが高くなっているかが見て取れる。

#ploting customer vs sales for each day of week
plt.scatter(train['Customers'], train['Sales'], c=train['DayOfWeek'], alpha=0.6, cmap=plt.cm.get_cmap('YlGn'))

plt.xlabel('Customers')
plt.ylabel('Sales')
plt.show()

output_13_0.png (315.6 kB)

ここでは、School Holiday(学校の休日)が売上に影響を与えているかどうかを調べている。

for i in [0, 1]:
    data = train[train['SchoolHoliday'] == i]
    if (len(data) == 0):
        continue
    plt.scatter(data['Customers'], data['Sales'], label=i)

plt.legend()
plt.xlabel('Customers')
plt.ylabel('Sales')
plt.show()

output_14_0.png (83.8 kB)

データを見るとわかるとおり、SchoolHolidayは[0, 1]のboolean型で、0だと休みじゃなく、1だと休みである。このグラフも休みの日とそうでない日を色分けしてどちらに売上の相関があるのかを確認している。(グラフで見ても重なっている要素が大きいからよくわからないけど。。) これを見ると、休みかどうかではあまり相関関係がないように見れる。 休みの日の学生はショッピングに行く傾向にあるかどうかを見ようとしているグラフの可視化だが、そこまで関連はないようだ。 スクリーンショット 2021-01-02 0.45.34.png (127.6 kB)

次に販促イベントがあるかないかで、売上げの関連性を見ている。グラフを見てもわかる通り、販促イベント(割引セールなど)があるときはオレンジ色のポイントがより上の方に集まっている傾向が見て取れる。

for i in [0, 1]:
    data = train[train['Promo'] == i]
    if (len(data) == 0):
        continue
    plt.scatter(data['Customers'], data['Sales'], label=i)

plt.legend()
plt.xlabel('Customers')
plt.ylabel('Sales')
plt.show()

output_15_0.png (72.0 kB)

次にデータを少し変形してSalesPerCustomer(売上/人)などの要素を足して、よりデータアナライズをしやすくする。

train.head()
Store DayOfWeek Date Sales Customers Open Promo StateHoliday SchoolHoliday
0 1 5 2015-07-31 5263 555 1 1 0 1
1 2 5 2015-07-31 6064 625 1 1 0 1
2 3 5 2015-07-31 8314 821 1 1 0 1
3 4 5 2015-07-31 13995 1498 1 1 0 1
4 5 5 2015-07-31 4822 559 1 1 0 1

train['Sales'] / train['Customers']と計算することで、顧客一人当たりの売上額がいくらくらいかのカラムをtrainデータに含むことができる。 その他にもそれぞれの店舗に平均どれくらいの顧客が来ていて、どれくらいの売上/顧客があるかを計算している。

train['SalesPerCustomer'] = train['Sales'] / train['Customers']

avg_store = train.groupby('Store')[['Sales', 'Customers', 'SalesPerCustomer']].mean()
avg_store.rename(columns=lambda x: 'Avg' + x, inplace=True)
store = pd.merge(avg_store.reset_index(), store, on='Store')
store.head()
Store AvgSales AvgCustomers AvgSalesPerCustomer StoreType Assortment CompetitionDistance CompetitionOpenSinceMonth CompetitionOpenSinceYear Promo2 Promo2SinceWeek Promo2SinceYear PromoInterval
0 1 4759.096031 564.049936 8.393038 c a 1270.0 9.0 2008.0 0 NaN NaN NaN
1 2 4953.900510 583.998724 8.408443 a a 570.0 11.0 2007.0 1 13.0 2010.0 Jan,Apr,Jul,Oct
2 3 6942.568678 750.077022 9.117599 a a 14130.0 12.0 2006.0 1 14.0 2011.0 Jan,Apr,Jul,Oct
3 4 9638.401786 1321.752551 7.249827 c c 620.0 9.0 2009.0 0 NaN NaN NaN
4 5 4676.274711 537.340180 8.611229 a a 29910.0 4.0 2015.0 0 NaN NaN NaN
avg_store.head()
AvgSales AvgCustomers AvgSalesPerCustomer
Store
1 4759.096031 564.049936 8.393038
2 4953.900510 583.998724 8.408443
3 6942.568678 750.077022 9.117599
4 9638.401786 1321.752551 7.249827
5 4676.274711 537.340180 8.611229








array(['c', 'a', 'd', 'b'], dtype=object)

それぞれの店舗タイプに分けて、その店舗タイプと売上にどのくらい相関関係があるかを調べるためのプロット。このデータから見て取れるように、Store Bはあまり街中に個数が存在しないということなので、Bの店舗数はそこまで多くなく、街中ではあまり見かけないタイプの店舗であるということを予想できる。Type Aは、かなり多くの顧客を獲得できているので、街中にたくさんの店舗があるということを予測できる。

for i in store.StoreType.unique():
    data = store[store['StoreType'] == i]
    if (len(data) == 0):
        continue
    plt.scatter(data['AvgCustomers'], data['AvgSales'], label=i)

plt.legend()
plt.xlabel('Average Customers')
plt.ylabel('Average Sales')
plt.show()

output_21_0.png (48.5 kB)

store.Assortment.unique()
array(['a', 'c', 'b'], dtype=object)
for i in store.Assortment.unique():
    data = store[store['Assortment'] == i]
    if (len(data) == 0):
        continue
    plt.scatter(data['AvgCustomers'], data['AvgSales'], label=i)

plt.legend()
plt.xlabel('Average Customers')
plt.ylabel('Average Sales')
plt.show()

output_23_0.png (47.4 kB)

store.Promo2.unique()
array([0, 1], dtype=int64)

販促イベントについても同様に関連性を見る

for i in store.Promo2.unique():
    data = store[store['Promo2'] == i]
    if (len(data) == 0):
        continue
    plt.scatter(data['AvgCustomers'], data['AvgSales'], label=i)

plt.legend()
plt.xlabel('Average Customers')
plt.ylabel('Average Sales')
plt.show()

output_25_0.png (45.4 kB)

Feature Engineering

pandasで欠損値NaNが含まれているか判定、個数をカウント nullとなっているデータが各カラムにどれくらいの数あるかを出力してくれる。

store.isnull().sum()
Store                          0
AvgSales                       0
AvgCustomers                   0
AvgSalesPerCustomer            0
StoreType                      0
Assortment                     0
CompetitionDistance            3
CompetitionOpenSinceMonth    354
CompetitionOpenSinceYear     354
Promo2                         0
Promo2SinceWeek              544
Promo2SinceYear              544
PromoInterval                544
dtype: int64

CompetitionDistanceは-1で置き換えることでnull値を根絶することができる。

CompetitionDistance - distance in meters to the nearest competitor store

上記の説明通り、CompetitionDistanceは近所の競合他社との距離を表している。データを見ると競合が近くに存在する店舗がかなり多くを占めており、近くに競合がある方がより平均売り上げが高くなっている。

# fill NaN values
store["CompetitionDistance"].fillna(-1)


plt.scatter(store['CompetitionDistance'], store['AvgSales'])

plt.xlabel('CompetitionDistance')
plt.ylabel('Average Sales')
plt.show()

output_28_0.png (34.6 kB)

store.head()
Store AvgSales AvgCustomers AvgSalesPerCustomer StoreType Assortment CompetitionDistance CompetitionOpenSinceMonth CompetitionOpenSinceYear Promo2 Promo2SinceWeek Promo2SinceYear PromoInterval
0 1 4759.096031 564.049936 8.393038 c a 1270.0 9.0 2008.0 0 NaN NaN NaN
1 2 4953.900510 583.998724 8.408443 a a 570.0 11.0 2007.0 1 13.0 2010.0 Jan,Apr,Jul,Oct
2 3 6942.568678 750.077022 9.117599 a a 14130.0 12.0 2006.0 1 14.0 2011.0 Jan,Apr,Jul,Oct
3 4 9638.401786 1321.752551 7.249827 c c 620.0 9.0 2009.0 0 NaN NaN NaN
4 5 4676.274711 537.340180 8.611229 a a 29910.0 4.0 2015.0 0 NaN NaN NaN
store['StoreType'] = store['StoreType'].astype('category').cat.codes
store['Assortment'] = store['Assortment'].astype('category').cat.codes
train["StateHoliday"] = train["StateHoliday"].astype('category').cat.codes
store.head()
Store AvgSales AvgCustomers AvgSalesPerCustomer StoreType Assortment CompetitionDistance CompetitionOpenSinceMonth CompetitionOpenSinceYear Promo2 Promo2SinceWeek Promo2SinceYear PromoInterval
0 1 4759.096031 564.049936 8.393038 2 0 1270.0 9.0 2008.0 0 NaN NaN NaN
1 2 4953.900510 583.998724 8.408443 0 0 570.0 11.0 2007.0 1 13.0 2010.0 Jan,Apr,Jul,Oct
2 3 6942.568678 750.077022 9.117599 0 0 14130.0 12.0 2006.0 1 14.0 2011.0 Jan,Apr,Jul,Oct
3 4 9638.401786 1321.752551 7.249827 2 2 620.0 9.0 2009.0 0 NaN NaN NaN
4 5 4676.274711 537.340180 8.611229 0 0 29910.0 4.0 2015.0 0 NaN NaN NaN

これらの表を見比べるとわかるが、それぞれStoreType, Assortment, StateHolidayがa, b, c, dのように文字列でカテゴライズされていたものを数値にして計算に使いやすくしている。 スクリーンショット 2021-01-02 1.36.02.png (194.0 kB)

train.head()
Store DayOfWeek Date Sales Customers Open Promo StateHoliday SchoolHoliday SalesPerCustomer
0 1 5 2015-07-31 5263 555 1 1 1 1 9.482883
1 2 5 2015-07-31 6064 625 1 1 1 1 9.702400
2 3 5 2015-07-31 8314 821 1 1 1 1 10.126675
3 4 5 2015-07-31 13995 1498 1 1 1 1 9.342457
4 5 5 2015-07-31 4822 559 1 1 1 1 8.626118

LEFT JOINしている。

select * from train left join store on train.store_id = store.store_id

みたいなことをしていて、Storeが同じものを一位のデータとしてジョインしている。

merged = pd.merge(train, store, on='Store', how='left')
merged.head()
Store DayOfWeek Date Sales Customers Open Promo StateHoliday SchoolHoliday SalesPerCustomer ... AvgSalesPerCustomer StoreType Assortment CompetitionDistance CompetitionOpenSinceMonth CompetitionOpenSinceYear Promo2 Promo2SinceWeek Promo2SinceYear PromoInterval
0 1 5 2015-07-31 5263 555 1 1 1 1 9.482883 ... 8.393038 2 0 1270.0 9.0 2008.0 0 NaN NaN NaN
1 2 5 2015-07-31 6064 625 1 1 1 1 9.702400 ... 8.408443 0 0 570.0 11.0 2007.0 1 13.0 2010.0 Jan,Apr,Jul,Oct
2 3 5 2015-07-31 8314 821 1 1 1 1 10.126675 ... 9.117599 0 0 14130.0 12.0 2006.0 1 14.0 2011.0 Jan,Apr,Jul,Oct
3 4 5 2015-07-31 13995 1498 1 1 1 1 9.342457 ... 7.249827 2 2 620.0 9.0 2009.0 0 NaN NaN NaN
4 5 5 2015-07-31 4822 559 1 1 1 1 8.626118 ... 8.611229 0 0 29910.0 4.0 2015.0 0 NaN NaN NaN

5 rows × 22 columns

merged.shape
(844338, 22)
merged.isnull().sum()
Store                             0
DayOfWeek                         0
Date                              0
Sales                             0
Customers                         0
Open                              0
Promo                             0
StateHoliday                      0
SchoolHoliday                     0
SalesPerCustomer                  0
AvgSales                          0
AvgCustomers                      0
AvgSalesPerCustomer               0
StoreType                         0
Assortment                        0
CompetitionDistance            2186
CompetitionOpenSinceMonth    268600
CompetitionOpenSinceYear     268600
Promo2                            0
Promo2SinceWeek              423292
Promo2SinceYear              423292
PromoInterval                423292
dtype: int64

null値を0で置き換えている処理

# remove NaNs
merged.fillna(0, inplace=True)

Dateというカラムをdatetimeに変換して再代入している。 文字列になっているとデータとしての処理を加えることができないため、Datetimeとして変換している。

merged['Date'] = pd.to_datetime(merged['Date'])
merged.dtypes
Store                                 int64
DayOfWeek                             int64
Date                         datetime64[ns]
Sales                                 int64
Customers                             int64
Open                                  int64
Promo                                 int64
StateHoliday                           int8
SchoolHoliday                         int64
SalesPerCustomer                    float64
AvgSales                            float64
AvgCustomers                        float64
AvgSalesPerCustomer                 float64
StoreType                              int8
Assortment                             int8
CompetitionDistance                 float64
CompetitionOpenSinceMonth           float64
CompetitionOpenSinceYear            float64
Promo2                                int64
Promo2SinceWeek                     float64
Promo2SinceYear                     float64
PromoInterval                        object
dtype: object

先ほどDatetimeに変換したことを利用して、それぞれ、year, month, day, weekに分けて各カラムを新しく作成したのち、それぞれに入れている。

merged['Year'] = merged.Date.dt.year
merged['Month'] = merged.Date.dt.month
merged['Day'] = merged.Date.dt.day
merged['Week'] = merged.Date.dt.week
merged.head()
Store DayOfWeek Date Sales Customers Open Promo StateHoliday SchoolHoliday SalesPerCustomer ... CompetitionOpenSinceMonth CompetitionOpenSinceYear Promo2 Promo2SinceWeek Promo2SinceYear PromoInterval Year Month Day Week
0 1 5 2015-07-31 5263 555 1 1 1 1 9.482883 ... 9.0 2008.0 0 0.0 0.0 0 2015 7 31 31
1 2 5 2015-07-31 6064 625 1 1 1 1 9.702400 ... 11.0 2007.0 1 13.0 2010.0 Jan,Apr,Jul,Oct 2015 7 31 31
2 3 5 2015-07-31 8314 821 1 1 1 1 10.126675 ... 12.0 2006.0 1 14.0 2011.0 Jan,Apr,Jul,Oct 2015 7 31 31
3 4 5 2015-07-31 13995 1498 1 1 1 1 9.342457 ... 9.0 2009.0 0 0.0 0.0 0 2015 7 31 31
4 5 5 2015-07-31 4822 559 1 1 1 1 8.626118 ... 4.0 2015.0 0 0.0 0.0 0 2015 7 31 31

5 rows × 26 columns

ここでは、近所の競合他社がどれくらいの期間営業しているかを取得して来ている。12ヶ月中どれくらいの期間(年と月)営業していて、それらが0のもの、イコール、営業していなかったものをmergedのデータセットから取得してきている。

locの中では、それぞれの競合他社が営業している時間が0の場合はMonthsCompetitionOpenの値が0になるはずなので(営業していないという認識になるから)ここで、0を入れてデータの整合性を保っている。

# Number of months that competition has existed for
merged['MonthsCompetitionOpen'] = 12 * (merged['Year'] - merged['CompetitionOpenSinceYear']) + (merged['Month'] - merged['CompetitionOpenSinceMonth'])
merged.loc[merged['CompetitionOpenSinceYear'] == 0, 'MonthsCompetitionOpen'] = 0

WeeksPromoOpenにも上記と同様の処理を行う

# Number of weeks that promotion has existed for
merged['WeeksPromoOpen'] = 12 * (merged['Year'] - merged['Promo2SinceYear']) + (merged['Date'].dt.weekofyear - merged['Promo2SinceWeek'])
merged.loc[merged['Promo2SinceYear'] == 0, 'WeeksPromoOpen'] = 0
merged.dtypes
Store                                 int64
DayOfWeek                             int64
Date                         datetime64[ns]
Sales                                 int64
Customers                             int64
Open                                  int64
Promo                                 int64
StateHoliday                           int8
SchoolHoliday                         int64
SalesPerCustomer                    float64
AvgSales                            float64
AvgCustomers                        float64
AvgSalesPerCustomer                 float64
StoreType                              int8
Assortment                             int8
CompetitionDistance                 float64
CompetitionOpenSinceMonth           float64
CompetitionOpenSinceYear            float64
Promo2                                int64
Promo2SinceWeek                     float64
Promo2SinceYear                     float64
PromoInterval                        object
Year                                  int64
Month                                 int64
Day                                   int64
Week                                  int64
MonthsCompetitionOpen               float64
WeeksPromoOpen                      float64
dtype: object

これらのカラムをInt型に変換している。

toInt = [
        'CompetitionOpenSinceMonth',
        'CompetitionOpenSinceYear',
        'Promo2SinceWeek', 
        'Promo2SinceYear', 
        'MonthsCompetitionOpen', 
        'WeeksPromoOpen']

merged[toInt] = merged[toInt].astype(int)

ここでは単純に'Sales', 'Customers', 'SalesPerCustomer'のそれぞれのメディアンの値を計算・取得してmergedデータ配列にマージしている。

med_store = train.groupby('Store')[['Sales', 'Customers', 'SalesPerCustomer']].median()
med_store.rename(columns=lambda x: 'Med' + x, inplace=True)

store = pd.merge(med_store.reset_index(), store, on='Store')
store.head()
Store MedSales MedCustomers MedSalesPerCustomer AvgSales AvgCustomers AvgSalesPerCustomer StoreType Assortment CompetitionDistance CompetitionOpenSinceMonth CompetitionOpenSinceYear Promo2 Promo2SinceWeek Promo2SinceYear PromoInterval
0 1 4647.0 550.0 8.362376 4759.096031 564.049936 8.393038 2 0 1270.0 9.0 2008.0 0 NaN NaN NaN
1 2 4783.0 575.5 8.313092 4953.900510 583.998724 8.408443 0 0 570.0 11.0 2007.0 1 13.0 2010.0 Jan,Apr,Jul,Oct
2 3 6619.0 744.0 9.123440 6942.568678 750.077022 9.117599 0 0 14130.0 12.0 2006.0 1 14.0 2011.0 Jan,Apr,Jul,Oct
3 4 9430.5 1301.5 7.215175 9638.401786 1321.752551 7.249827 2 2 620.0 9.0 2009.0 0 NaN NaN NaN
4 5 4616.0 564.0 8.584677 4676.274711 537.340180 8.611229 0 0 29910.0 4.0 2015.0 0 NaN NaN NaN
merged = pd.merge(med_store.reset_index(), merged, on='Store')
merged.head()
Store MedSales MedCustomers MedSalesPerCustomer DayOfWeek Date Sales Customers Open Promo ... Promo2 Promo2SinceWeek Promo2SinceYear PromoInterval Year Month Day Week MonthsCompetitionOpen WeeksPromoOpen
0 1 4647.0 550.0 8.362376 5 2015-07-31 5263 555 1 1 ... 0 0.0 0.0 0 2015 7 31 31 82.0 0.0
1 1 4647.0 550.0 8.362376 4 2015-07-30 5020 546 1 1 ... 0 0.0 0.0 0 2015 7 30 31 82.0 0.0
2 1 4647.0 550.0 8.362376 3 2015-07-29 4782 523 1 1 ... 0 0.0 0.0 0 2015 7 29 31 82.0 0.0
3 1 4647.0 550.0 8.362376 2 2015-07-28 5011 560 1 1 ... 0 0.0 0.0 0 2015 7 28 31 82.0 0.0
4 1 4647.0 550.0 8.362376 1 2015-07-27 6102 612 1 1 ... 0 0.0 0.0 0 2015 7 27 31 82.0 0.0

5 rows × 31 columns

merged.columns
Index(['Store', 'MedSales', 'MedCustomers', 'MedSalesPerCustomer', 'DayOfWeek',
       'Date', 'Sales', 'Customers', 'Open', 'Promo', 'StateHoliday',
       'SchoolHoliday', 'SalesPerCustomer', 'AvgSales', 'AvgCustomers',
       'AvgSalesPerCustomer', 'StoreType', 'Assortment', 'CompetitionDistance',
       'CompetitionOpenSinceMonth', 'CompetitionOpenSinceYear', 'Promo2',
       'Promo2SinceWeek', 'Promo2SinceYear', 'PromoInterval', 'Year', 'Month',
       'Day', 'Week', 'MonthsCompetitionOpen', 'WeeksPromoOpen'],
      dtype='object')

matplotlib でヒストグラムを描く

ヒストグラムを確認すると、 AvgCustomers,はノーマルディストリビューションに沿っていない。

AvgSalesCustomer、ガウス分布正規分布)に近い。

MedSales, MedCustomersもノーマルディストリビューションに沿っていない。

MedSalesPerCustomerも正規分布に近い

今回Salesという値を予測するわけだが、これを見るとSalesデータもガウス分布に沿っていない。そのため、この Salesの値をガウス分布になるように計算し直す必要がある。ガウス分布に従っている値の方が機械学習で使用しやすいためである。 ・一般的にデータを予測する線形回帰モデルはガウス分布に従っている。

なので、Modelingの箇所で正規分布に従うように正規化処理を行う

merged.hist(figsize=(20,20))
plt.show()

output_47_0.png (97.9 kB)

merged[X].head()
Store Customers CompetitionDistance Promo Promo2 CompetitionOpenSinceMonth CompetitionOpenSinceYear Promo2SinceWeek Promo2SinceYear StateHoliday ... AvgCustomers AvgSalesPerCustomer MedSales MedCustomers MedSalesPerCustomer DayOfWeek Week Day Month Year
0 1 555 1270.0 1 0 9.0 2008.0 0.0 0.0 1 ... 564.049936 8.393038 4647.0 550.0 8.362376 5 31 31 7 2015
1 1 546 1270.0 1 0 9.0 2008.0 0.0 0.0 1 ... 564.049936 8.393038 4647.0 550.0 8.362376 4 31 30 7 2015
2 1 523 1270.0 1 0 9.0 2008.0 0.0 0.0 1 ... 564.049936 8.393038 4647.0 550.0 8.362376 3 31 29 7 2015
3 1 560 1270.0 1 0 9.0 2008.0 0.0 0.0 1 ... 564.049936 8.393038 4647.0 550.0 8.362376 2 31 28 7 2015
4 1 612 1270.0 1 0 9.0 2008.0 0.0 0.0 1 ... 564.049936 8.393038 4647.0 550.0 8.362376 1 31 27 7 2015

5 rows × 23 columns

Model Building and Evaluation

メインパート

# 'Store', 'MedSales', 'MedCustomers', 'MedSalesPerCustomer', 'DayOfWeek',
#        'Date', 'Sales', 'Customers', 'Open', 'Promo', 'StateHoliday',
#        'SchoolHoliday', 'SalesPerCustomer', 'AvgSales', 'AvgCustomers',
#        'AvgSalesPerCustomer', 'StoreType', 'Assortment', 'CompetitionDistance',
#        'CompetitionOpenSinceMonth', 'CompetitionOpenSinceYear', 'Promo2',
#        'Promo2SinceWeek', 'Promo2SinceYear', 'PromoInterval', 'Year', 'Month',
#        'Day', 'Week', 'MonthsCompetitionOpen', 'WeeksPromoOpen'],

データ予測を行うときは、予測に使用するデータと関連性の高いデータがあればあるほど予測の精度が上がるのでデータ前処理してなるべく関連するデータの種類を増やした方が精度を高めるのに役立つ。

from sklearn.model_selection import train_test_split
X = [
    'Store', 
    'Customers',
    'CompetitionDistance', 

    'Promo', 
    'Promo2', 

    'CompetitionOpenSinceMonth',
    'CompetitionOpenSinceYear',
    'Promo2SinceWeek',
    'Promo2SinceYear',

    
    'StateHoliday',
    'StoreType',
    'Assortment',

    'AvgSales',
    'AvgCustomers',
    'AvgSalesPerCustomer',
    
    'MedSales',
    'MedCustomers',
    'MedSalesPerCustomer',

    'DayOfWeek',
    'Week',
    'Day',
    'Month',
    'Year',

]
X_data = merged[X]
Y_data = np.log(merged['Sales'])
X_train, X_test, y_train, y_test = train_test_split(X_data, Y_data, test_size=0.20, random_state=10)
from sklearn.model_selection import cross_val_score
from sklearn.metrics import make_scorer,mean_squared_error



def plot_importance(model):
    k = list(zip(X, model.feature_importances_))
    k.sort(key=lambda tup: tup[1])

    labels, vals = zip(*k)
    
    plt.barh(np.arange(len(X)), vals, align='center')
    plt.yticks(np.arange(len(X)), labels)

XgBoostを使用する。

neg_mean_squared_errorを予測の判定に使用する。平均二乗後さが低ければ低いほど予測の回帰直線が正しくひかれていることを意味する。

import xgboost as xgb
from sklearn.model_selection import GridSearchCV

param ={
            'n_estimators': [100,500, 1000,1500],
            'max_depth':[2,4,6,8]
        }

xgboost_tree = xgb.XGBRegressor(
    eta = 0.1,
    min_child_weight = 2,
    subsample = 0.8,
    colsample_bytree = 0.8,
    tree_method = 'exact',
    reg_alpha = 0.05,
    silent = 0,
    random_state = 1023
)

grid = GridSearchCV(estimator=xgboost_tree,param_grid=param,cv=5,  verbose=1, n_jobs=-1,scoring='neg_mean_squared_error')
   
    

    
grid_result = grid.fit(X_train, y_train)
best_params = grid_result.best_params_

print('Best Params :',best_params)
Fitting 5 folds for each of 16 candidates, totalling 80 fits


[Parallel(n_jobs=-1)]: Using backend LokyBackend with 12 concurrent workers.
[Parallel(n_jobs=-1)]: Done  26 tasks      | elapsed: 26.8min
[Parallel(n_jobs=-1)]: Done  80 out of  80 | elapsed: 186.8min finished
C:\Users\user\Anaconda3\lib\site-packages\xgboost\core.py:587: FutureWarning: Series.base is deprecated and will be removed in a future version
  if getattr(data, 'base', None) is not None and \


[06:06:54] WARNING: C:/Jenkins/workspace/xgboost-win64_release_0.90/src/objective/regression_obj.cu:152: reg:linear is now deprecated in favor of reg:squarederror.
Best Params : {'max_depth': 8, 'n_estimators': 1500}
from math import sqrt

pred = grid_result.predict(X_test)
print('Root Mean squared error {}'.format(sqrt(mean_squared_error(np.exp(y_test), np.exp(pred)))))
Root Mean squared error 351.13062643133986





import sklearn
sorted(sklearn.metrics.SCORERS.keys()) 
['accuracy',
 'adjusted_mutual_info_score',
 'adjusted_rand_score',
 'average_precision',
 'balanced_accuracy',
 'brier_score_loss',
 'completeness_score',
 'explained_variance',
 'f1',
 'f1_macro',
 'f1_micro',
 'f1_samples',
 'f1_weighted',
 'fowlkes_mallows_score',
 'homogeneity_score',
 'jaccard',
 'jaccard_macro',
 'jaccard_micro',
 'jaccard_samples',
 'jaccard_weighted',
 'max_error',
 'mutual_info_score',
 'neg_log_loss',
 'neg_mean_absolute_error',
 'neg_mean_squared_error',
 'neg_mean_squared_log_error',
 'neg_median_absolute_error',
 'normalized_mutual_info_score',
 'precision',
 'precision_macro',
 'precision_micro',
 'precision_samples',
 'precision_weighted',
 'r2',
 'recall',
 'recall_macro',
 'recall_micro',
 'recall_samples',
 'recall_weighted',
 'roc_auc',
 'v_measure_score']

sample_submission.csv (317.6 kB)

Conclusion

  • We were able to reduce the error and get quite good results
  • Whats next ?
    • try other algorithms
      • Cat boost, GBM, nueral network
    • try finer feature engineering

Pythonでcatboostを使ってみる

データ構造とアルゴリズム:ハッシュテーブル(Hash)

スクリーンショット 2020-12-20 14.13.03.png (292.2 kB)

実装

import hashlib

class HashTable(object):
    from typing import Any
    def __init__(self, size=10):
        super().__init__()
        self.size = size
        self.table = [[] for _ in range(self.size)]

    def hash(self, key) -> int:
        # hashlib.md5で文字列をエンコードしてから、文字列なので16進数のint型に直す。
        # それをhashのサイズで割った時のあまりを取得してくる。
        return int(hashlib.md5(key.encode()).hexdigest(), base=16) % self.size

    def add(self, key, value) -> None:
        index = self.hash(key)
        for data in self.table[index]:
            if data[0] == key:
                data[1] = value
                break
        else:
            self.table[index].append([key, value])

    def print(self) -> None:
        for index in range(self.size):
            print(index, end=' ')
            for data in self.table[index]:
                print('-->', end=' ')
                print(data, end=' ')
            print()

    def get(self, key) -> Any:
        index = self.hash(key)
        for data in self.table[index]:
            if data[0] == key:
                return data[1]

    def __setitem__(self, key, value) -> None:
        self.add(key, value)

    def __getitem__(self, key) -> Any:
        return self.get(key)

if __name__ == '__main__':
    hash_table = HashTable()
    hash_table['car'] = 'Tesla'
    hash_table['pc'] = 'Mac'
    hash_table['sns'] = 'YouTube'
    hash_table.print()
    print(hash_table['car'])
    # print(hash_table.table)


====== output ======
0 
1 
2 
3 
4 --> ['pc', 'Mac'] --> ['sns', 'YouTube'] 
5 --> ['car', 'Tesla'] 
6 
7 
8 
9 
Tesla

解説:

参考: ハッシュテーブル(Hash Table)を簡単に理解しよう

追加と呼び出しが早い

ハッシュテーブルも配列系のデータ構造の一種類として、他の二つは配列とリンクリストになる。 ・配列は値を呼び出す時アドレスさえあれば一瞬で終わるが、一つの値を追加・削除すると、他の値も詰めてきて、引っ越さないといけない ・リンクリストは追加が早いが(最後尾に入るから)、呼び出す時入ってるデータを一つづつ確認しないといけない ・ハッシュテーブルは、追加する時ハッシュ関数を回してキーからアドレスを得て、他の値に影響しない上で、呼び出す時キーさえあれば、アドレスもキーからわかってきて、すぐ値を尋ねられる。

解説

それぞれのkey, valueのkeyから一意の数値を計算してそれをそのkey, vlaueのアドレスとする。 そのアドレスの配列の場所にそれらの値を入れる。 今回の場合だと、

int(hashlib.md5(key.encode()).hexdigest(), base=16) % self.size

という計算式で一意の値を出力している。

>>> hashlib.md5('car'.encode()).hexdigest()
'e6d96502596d7e7887b76646c5f615d9'

この部分でcarという文字列をエンコードして一意の文字列として出力する。

その後、以下のようにint形に直す。 文字列は16進数なのでbase=16として文字列を数値にエンコードする。 この際に一つの文字列からは同じ数値しか返ってこない。

>>> int(hashlib.md5('car'.encode()).hexdigest(), base=16)
306851216158335538240511469114392712665
>>> int(hashlib.md5('car'.encode()).hexdigest(), base=16)
306851216158335538240511469114392712665
>>> int(hashlib.md5('car'.encode()).hexdigest(), base=16)
306851216158335538240511469114392712665

最後に上記の数値を配列のサイズで割り算した余剰を出力する。 理由としては、10の要素を持つ配列の場合、その配列のサイズである10で割り算することにより0 ~ 9までの数値しか余剰として出力されないため、そのアドレスを決めるときに配列の数以上になることを防げる。 もし、余剰が11などの配列の数以上になってしまうと、そのサイズの配列ではないためエラーになる。

>>> int(hashlib.md5('pc'.encode()).hexdigest(), base=16) % 10
4

getメソッド

def get(self, key) -> Any:
    index = self.hash(key)
    for data in self.table[index]:
        if data[0] == key:
            return data[1]

単純にfor文でtableをどんどん見ていって、keyが一致する場所のvlaueを出力している。 (計算量とか考えると他にも良い方法があるのかな?)

pythonと同様に実装

 def __setitem__(self, key, value) -> None:
        self.add(key, value)

    def __getitem__(self, key) -> Any:
        return self.get(key)

この部分はそれぞれ、以下のようにすると__setitem__が呼び出され hash_table['sns'] = 'YouTube'

このようにすると、getterである__getitem__が呼び出される。 print(hash_table['car'])

クイズ:足し合わせて同じになるペアを探す

① Input: [11, 2, 5, 9, 10, 3], 12 => Output: (2, 10) or None

  1. Input: [11, 2, 5, 9, 10, 3], 12 => Output: (2, 10) or None
  2. Input: [11, 2, 5, 9, 10, 3] => Output: (11, 9) or None ex) 11 + 9 = 2 + 5 + 10 + 3 のようにアウトプットを出す

set型: Pythonのset型とは、集合を扱うための型です。 もっとも普及しているリスト型のように、set型も同じく複数の値を格納できる型です。 しかし、リスト型との決定的な違いは ・重複した要素がない ・要素に順番がない といった二点が挙げられます。

【Python入門】すぐわかる!set型(集合型)の基本まとめ

from typing import  List, Tuple, Optional

def get_pair(numbers: List[int], target: int) -> Optional[Tuple[int, int]]:
    cache = set()
    # ユニークな数値のみを入れる
    for num in numbers:
        cache.add(num)
        val = target - num
        if val in cache:
            return val, num

if __name__ == '__main__':
    l = [11, 2, 5, 9, 10, 3]
    # l = [11, 2]
    t = 12
    print(get_pair(l, t))
    
===== output =====
(2, 10)

set関数は上記で説明がある通り、重複のない配列。 重複のない配列を作る過程で、ひとつづつ既存の配列からcacheのなかに数値を入れていく過程で、その追加される通知とtargetの数値を引いた値が配列の中にすでにある場合はreuturn vel, numで数値を返して終了。まだない場合は次に進むという感じ。

今回の場合は、

(1)
cache = [11]
val = 12 - 11 = 1
1はないので次に進む

(2)
cache = [11, 2]
val = 12 - 2 = 10
10はないので次に進む

(3)
cache = [11, 2, 5]
val = 12 - 5 = 7
7はcacheにないので次に進む

(4)
cache = [11, 2, 5, 9]
val = 12 - 9 = 3
3はcacheにないので次に進む

(5)
cache = [11, 2, 5, 9, 10]
val = 12 - 10 = 2
2が配列内にあるので終了。
2, 10を返す。

という流れで見つけることができる。

② Input: [11, 2, 5, 9, 10, 3] => Output: (11, 9) or None ex) 11 + 9 = 2 + 5 + 10 + 3

・リストの中で左辺 = 右辺を確立させられるような組み合わせを見つけてくる

まず、全ての要素を足算してそれを2で割ったときに余剰があるようだとこれは確立できないので終了。 2で割ったときに割り切れるようであれば、答えがあるのでこれをhalf_sum = int(sum_numbers / 2)としてhalf_sumに入れてあげる。 残りはhalf_sumをターゲットとして、ひとつ前のクイズでやったようにval = half_sum - numにvalを入れてそれぞれ追加される要素がcacheの中にあるかどうかを見て、割り切れるのであればそれが答えなので出力する。それ以外の残りの配列内の要素で今出力した和のを構築できるので答えが出る。 (残りの要素は出ない)

def get_pair_half_sum(numbers: List[int]) -> Optional[Tuple[int, int]]:
    sum_numbers = sum(numbers)
    # if sum_numbers % 2 != 0:
    #   return
    # half_sum = int(sum_numbers / 2)
    half_sum, remainder = divmod(sum_numbers, 2)
    if remainder != 0:
        return

    cache = set()
    for num in numbers:
        cache.add(num)
        val = half_sum - num
        if val in cache:
            return val, num
            
if __name__ == '__main__':
    l = [11, 2, 5, 9, 10, 3]
    # l = [11, 2]
    t = 12
    print(get_pair(l, t))

    l = [11, 2, 5, 9, 10, 3]
    print(get_pair_half_sum(l))

===== output =====
(11, 9)

クイズ実装

from typing import  List, Tuple, Optional

def get_pair(numbers: List[int], target: int) -> Optional[Tuple[int, int]]:
    cache = set()
    # ユニークな数値のみを入れる
    for num in numbers:
        cache.add(num)
        val = target - num
        if val in cache:
            return val, num

def get_pair_half_sum(numbers: List[int]) -> Optional[Tuple[int, int]]:
    sum_numbers = sum(numbers)
    # if sum_numbers % 2 != 0:
    #   return
    # half_sum = int(sum_numbers / 2)
    half_sum, remainder = divmod(sum_numbers, 2)
    if remainder != 0:
        return

    cache = set()
    for num in numbers:
        cache.add(num)
        val = half_sum - num
        if val in cache:
            return val, num

if __name__ == '__main__':
    l = [11, 2, 5, 9, 10, 3]
    # l = [11, 2]
    t = 12
    print(get_pair(l, t))

    l = [11, 2, 5, 9, 10, 3]
    print(get_pair_half_sum(l))

データ構造とアルゴリズム:Doubly Linked List(双方向リンクリスト )

スクリーンショット 2020-11-28 10.45.33.png (145.5 kB)

単方向連結リストはnextのみを管理していたが、双方向は名前の通り双方向の連結を管理している。


解説

単方向との違いは

class Node(object):
    def __init__(self, data: Any, next_node: Node = None, prev_node: Node = None):
        super().__init__()
        self.data = data
        self.next = next_node
        self.prev = prev_node

と、Nodeクラスのイニシャライズの部分でself.prev = prev_nodeとして、previousデータも一緒に管理できるようにしているところで、これがappendメソッドの中でself.prevにひとつ前のデータを入れることで可能にしている。

こうすることで、インスタンス.nextとすることで次のノードが取得でき、インスタンス.prevとすることで一つ前のノードが管理されているので一つ前ののーどが取得できる。

その次に双方向連結リストのクラスを作っていくのだが、最初の部分はself.headとして単方向連結リストと同様にする。

class DoublyLinkedList(object):

    def __init__(self, head: Node = None) -> None:
        self.head = head



append: リストの最後に追加

その次はappendする処理を書く。 appendは新しくnodeをクラスから作成するときにHEADになるパターンとHEAD以降に作られるパターンがあるので、その部分を考えて作成する必要がある。

new_nodeをNodeクラスから作成して、self.headがNoneの場合は一番最初のノードとなるためnew_node_wo self.headにして終了。

そうでなければcurrent_nodeという変数に一度self.headを入れてwhile文でcurrent_node.nextがfalseになる(nextがないので最後のノード)までcurrent_node = current_node.nextでcurrent_nodeを書き換えて最後のノードをcurrent_nodeに入れるまで回す。

最後のノードがどれかわかったので、current_node.next = new_nodeとして新しく作ったノードを最後のノードのnextに管理させる。また、new_nodeにはnew_node.prev = current_nodeとして最後だったノードを新しく更新された最後のノードの一つ前のノードとして管理させることで双方向に連結できる。

def append(self, data: Any) -> None:
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

        current_node = self.head
        while current_node.next:
            current_node = current_node.next
        current_node.next = new_node 
        new_node.prev = current_node

このようにappendする際には

current_node.next = new_node 
new_node.prev = current_node

最後のこの部分でcurrent_nodeの次に新しいデータ、現在のデータは新しいデータの一つ前になるのでnew_node.prev = current_nodeとすることで前と後ろ両方を管理することができる。

完成形:

def append(self, data: Any ) -> None:
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

        current_node = self.head
        while current_node.next:
            current_node = current_node.next
        current_node.next = new_node
        new_node.prev = current_node



insert: リストの先頭に追加

まだリスト内に何もない状態はappendのhead = noneと同じものを使えるのでそのまま、

def insert(self, data: Any) -> None:
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

とする

リスト内に既に何かある場合は、リストのheadに新しいノードを追加して、それまでheadだったノードを新しく追加したhead(new_node)の次に配置してあげればいいので、

self.head.prev = new_node
new_node.next = self.head
self.head = new_node

というような処理を書く。 1行目のself.head.prev = new_nodeで今までのheadの一つ前に新しいノードを配置(headにnew_nodeをprevとして入れることで管理させる。) 2行目で、new_node.nextに今までのheadのノードを管理させる。 最後にリスト自体のインスタンスheadにnew_nodeを配置する必要があるので、self.head = new_nodeとして完成

完成形:

def insert(self, data: Any) -> None:
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

        self.head.prev = new_node
        new_node.next = self.head
        self.head = new_node

参考: スクリーンショット 2020-12-19 18.10.00.png (97.8 kB)


remove: 削除

完成形:

def remove(self, data: Any) -> Node:
        # 先頭のものを削除する場合
        current_node = self.head
        if current_node and current_node.data == data:
            if current_node.next is None:
                current_node = None
                self.head = None
                return
            else:
                next_node = current_node.next
                next_node.prev = None
                current_node = None
                self.head = next_node
                return

まずは先頭のものを削除する場合を考える。 if current_node and current_node.data == data:で先頭の場合のifを作り、その次のifの部分でcurrent_node.nextがなかった場合はcurrent_node = None, self.head = Noneとしてリストから全てを消す。

その次のelseの部分ではnext_node = current_node.nextとして一旦今あるself.headの次のノードを保存してあげて、next_node.prev = Noneでhead部分を削除。self.head = next_nodeでheadを元のheadの次のノードに書き換えて終了。

# 先頭のものを削除する場合
        current_node = self.head
        if current_node and current_node.data == data:
            if current_node.next is None:
                current_node = None
                self.head = None
                return
            else:
                next_node = current_node.next
                next_node.prev = None
                current_node = None
                self.head = next_node
                return

remove 実行

d = DoublyLinkedList()
d.append(0)
d.append(1)
d.append(2)
d.append(3)
d.print()
print('############# REMOVE')
d.remove(0)
d.print()
========================結果========================
0
1
2
3
############# REMOVE
1
2
3

リストの先頭以外にある項目を削除する場合 スクリーンショット 2020-12-19 20.31.16.png (88.3 kB) - 赤枠の箇所で一番後ろにある要素を削除 - 青枠の箇所で中間にある項目を削除している

赤枠: current_node.next == Noneであれば次はないということなのでこれは最後の項目になる。 current_nodeの一つ前を取得してきて、prev.nextとcurrent_node = Noneとすることで最後の要素な全てNoneになるので削除完了

青枠: 一つ前の項目と一つ後の項目をつなげる必要があるので、next_node, prev_nodeをそれぞれ取得してきて、prev_node.nextを直接next_nodeにつなげることでcurrent_nodeが配列から消える。最後にcurrent_node = Noneとして終わり。

実装

prevで前のデータも取得できている

from __future__ import annotations
from typing import Any, Optional


class Node(object):
    def __init__(self, data: Any, next_node: Node = None, prev_node: Node = None) -> None:
        self.data = data
        self.next = next_node
        self.prev = prev_node


class DoublyLinkedList(object):

    def __init__(self, head: Node = None) -> None:
        self.head = head

    def append(self, data: Any) -> None:
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

        current_node = self.head
        while current_node.next:
            current_node = current_node.next
        current_node.next = new_node
        new_node.prev = current_node

    def insert(self, data: Any) -> None:
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

        self.head.prev = new_node
        new_node.next = self.head
        self.head = new_node

    def print(self) -> None:
        current_node = self.head
        while current_node:
            print(current_node.data)
            current_node = current_node.next

    def remove(self, data: Any) -> Node:
        current_node = self.head
        if current_node and current_node.data == data:
            if current_node.next is None:
                current_node = None
                self.head = None
                return
            else:
                next_node = current_node.next
                next_node.prev = None
                current_node = None
                self.head = next_node
                return

        while current_node and current_node.data != data:
            current_node = current_node.next

        if current_node is None:
            return

        if current_node.next is None:
            prev = current_node.prev
            prev.next = None
            current_node = None
            return
        else:
            next_node = current_node.next
            prev_node = current_node.prev
            prev_node.next = next_node
            next_node.prev = prev_node
            current_node = None
            return



if __name__ == '__main__':
    d = DoublyLinkedList()
    d.append(1)
    d.append(2)
    d.append(3)
    d.insert(0)
    d.print()
    print("######## Remove")
    d.remove(3)
    d.print()

0
1
2
3
######## Remove
0
1
2

1
2
3
2
1

データ構造とアルゴリズム(リンクリスト) 単方向リンク

スクリーンショット 2020-11-28 8.40.21.png (111.0 kB)

単方向リンク

画像のように、データを一列に持っているデータ構造で、リンクの一番後ろにデータをどんどん追加したり、一番最初にデータを追加したりということを行う。

appendでデータ構造の一番後ろに新しくNodeを追加できるようにしている。 insertではデータのHEADに新しいNodeを追加できるようにしている。

append

def append(self, data: Any) -> None:
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        
        # last_node.nextでどんどんノードを後ろにみていき.nextがfalseになったら
        # それ以上ノードがないということなので、そこで新しくデータを追加する
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

new_node = Node(data) - ここで追加したい数字をNodeクラスのインスタンスとしてインスタンス化する - if self.head is None:self.headがなかったらデータ構造の中に何もないということなのでデータをHEADに追加して終了(return) - それ以外の場合はwhile last_node.next:の部分でlast_node(self.head)の次に何もデータがないかどうかをみていき、データがなければnew_node_を.nextで最後に追加してあげるようにする。

insert

# こちらは単純に一番頭に新しいnew_nodeを追加する
    def insert(self, data: Any) -> None:
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node  

これはあまり複雑ではなく、新しくデータが入力されたらNodeインスタンスを作成してそれをnew_nodeという変数に置き換える。self.headをnew_nodeの次に配置して、self.head = new_nodeで一番最初にnew_nodeを入れてあげるとinsertが完了する

remove

def remove(self, data: Any) -> None:
      current_node = self.head
      if current_node and current_node.data == data:
        self.head = current_node.next
        current_node = None
        return
      
      previous_node = None
      while current_node and current_node.data != data:
        previous_node = current_node
        current_node = current_node.next

      if current_node is None:
        return 

      previous_node.next = current_node.next
      current_node = None

これがわりと複雑。。。

current_node = self.head
if current_node and current_node.data == data:
self.head = current_node.next
current_node = None
return

まずこの部分。 self.headをcurrent_nodeとして、current_nodeがなければそのまま終了なのでreturn そして、current_node.data = data => current_node(head)が削除対象データであれば、self.head = current_node.nextでheadを上書きすることでheadが消える。

※この時点で読んでいて気付いたのだが、nextでデータをどのように持つかということは、配列として全ての要素がどこにあるか管理しているわけではなくて、それぞれのデータが自分の次のデータの要素がなんであるかという情報を持っているのでそれで.nextが使えるというわけか 上の理由からself.head = current_node.nextとするとself.headが次のデータで置き換えられるので、それ以降は置き換えられたself.headのデータは見れなくなる。

ということはcurrent_node = current_node.nextでもいいのかな?

先頭にあるものが、削除対象であればそのまま削除する。そして、データがなければ削除するデータそのものがないのでその時点で終了する。

  previous_node = None
  while current_node and current_node.data != data:
    previous_node = current_node
    current_node = current_node.next
    
  if current_node is None:
    return 

  previous_node.next = current_node.next
  current_node = None

次にこの部分。

previous_nodeで一個前のノードを保存していく while current_node and current_node.data != data: current_nodeに値が存在していて、かつ、そのデータがremove対象のデータでなければwhileを続けていく。 (ここでは、current_node.dataをどんどん右側に遡っていき、削除対象のデータにぶつかるまでリニアーサーチみたいな感じで探していく。)

current_node.data != data:の部分が引っ掛かったらwhileループは抜けるので current_nodeには削除対象のデータが入っており、previous_nodeにはcurrent_nodeのひとつ前のデータが入っている状況になる。

そこで、previous_node.next = current_node.nextとしてあげることで、[3, 4, 5] => [3, 4, 5] => [3, 4]のような形で、削除対象のデータがcurrent_node.nextで上書きされるのでデータ構造からデータがremoveされる。

from __future__ import annotations
from typing import Any

class Node(object):
    def __init__(self, data: Any, next_node: Node = None):
        self.data = data
        self.next = next_node # next_nodeにはNode自信を入れる。
    
class LinkedList(object):
    def __init__(self, head=None) -> None:
        self.head = head

    def append(self, data: Any) -> None:
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        
        # last_node.nextでどんどんノードを後ろにみていき.nextがfalseになったらそれ以上ノードがないということなので、そこで新しくデータを追加する
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node
    
    # こちらは単純に一番頭に新しいnew_nodeを追加する
    def insert(self, data: Any) -> None:
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node  
      
    def print(self) -> None:
      current_node = self.head
      while current_node:
        print(current_node.data)
        current_node = current_node.next

    def remove(self, data: Any) -> None:
      current_node = self.head
      if current_node and current_node.data == data:
        self.head = current_node.next
        current_node = None
        return
      
      previous_node = None
      while current_node and current_node.data != data:
        previous_node = current_node
        current_node = current_node.next

      if current_node is None:
        return 

      previous_node.next = current_node.next
      current_node = None


l = LinkedList()
l.append(1)
l.append(2)
l.append(3)
l.insert(0)
l.print()
l.remove(2)
print('#######################')
l.print()
# print(l.head.data)
# print(l.head.next.data)
# print(l.head.next.next.data)
# print(l.head.next.next.next.data)

0
1
2
3
#######################
0
1
3

データ構造とアルゴリズム:Qucikソート

重要度:高い!

スクリーンショット 2020-11-27 0.10.45.png (278.3 kB)

スクリーンショット 2020-11-27 0.11.00.png (325.4 kB)

スクリーンショット 2020-11-27 0.11.16.png (342.5 kB)

スクリーンショット 2020-11-27 0.11.32.png (295.4 kB)

インナー関数

関数の中であるまとまった処理を行う際に関数内に関数を定義することをインナー関数と呼ぶ。 関数内関数

コード

partionの部分で、pivotを配列の一番後ろの数値と決めて、その後左から一つづつpivotと比較して、pivotよりも小さければ一つ後ろの配列と入れ替える。その後右に移動して、pivotと比較して小さかったら入れ替える、大きかったらそのまま。というのを繰り返す。入れ替えを行う配列の要素はif numbers[j] <= pivot:でif文に引っかかった時はi += 1としているのでiの位置がどんどん右側にずれていく。if文に引っかかるたびにiの数値が大きくなり、交換する配列のindex番号が大きくなる。

最後に一番右に到達した後、移動していたiの番号の箇所にpivotの数値を入れる。 そうすることで下記のような状況が作れる。 - pivotの数字を挟んで - 右側はpivotより大きい数値 - 左側はpivotより小さい数値

最後に

_quick_sort(numbers, low, partition_index-1)
_quick_sort(numbers, partition_index+1, high)

の部分で再起呼び出しを行い、partition_index-1は配列の区切りの一つ前partition_index+1の部分で配列の区切りの一つ後を示し、それらの左右の部分で再度大きさを比較する_quick_sortを呼び出して、ソートが完了するまで同じ操作を行う。

from typing import List
import random

def partition(numbers: List[int], low: int, high: int) -> int:
    i = low - 1 
    pivot = numbers[high]
    for j in range(low, high):
        if numbers[j] <= pivot:
            i += 1
            numbers[i], numbers[j] = numbers[j], numbers[i]
    numbers[i+1], numbers[high] = numbers[high], numbers[i+1]
    return i+1

def quick_sort(numbers: List[int]) -> List[int]:
    def _quick_sort(numbers: List[int], low: int, high: int) -> None:
        if low < high:
            partition_index = partition(numbers, low, high)
            _quick_sort(numbers, low, partition_index-1)
            _quick_sort(numbers, partition_index+1, high)

    _quick_sort(numbers, 0, len(numbers)-1)
    return numbers

nums = [random.randint(0, 1000) for i in range(10)]
print(quick_sort(nums))

[37, 93, 174, 191, 218, 702, 813, 854, 951, 975]

データ構造とアルゴリズム:insertion(挿入ソート)

重要度:高い

左から順に入れ替えていくが、一度入れ替えが起こった後その入れ替えた要素をtmp変数に格納し適切な位置に収まるまで左側の数値と比較して小さい値があったらさらに左へ、また次も小さいければさらに左へというように適切な位置まで左に送るソート。

スクリーンショット 2020-11-26 23.30.02.png (154.0 kB)

どんどん左のものと比較して適切な位置に持っていく。 スクリーンショット 2020-11-26 23.31.42.png (156.6 kB) スクリーンショット 2020-11-26 23.32.05.png (158.1 kB)

途中経過を確認。

range(1, len_numbers):と1から始めているので、j = i - 1としてjの初期値を0にしてあげる。その後、whileのなかで j -= 1とすることでpirntで出力しているように左側に一つづつ確認していくような処理を実現している。

from typing import List

import random

def insertion_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    for i in range(1, len_numbers):
        tmp = numbers[i]
        j = i - 1
        while j >= 0:
            print(j, end=' ')
            j -= 1
        print()


nums = [random.randint(0,1000) for i in range(10)]
print(insertion_sort(nums))

スクリーンショット 2020-11-26 23.46.39.png (68.2 kB)

コード

while j >= 0 and numbers[j] > tmp:となっているので、j >= 0か、numbers[j] > tmpのどちらかが満たされていないとwhile文を抜けることになる。一つづつずらしていき、tmpの数値がnumbers[j]より小さくなったら処理が終了する。

numbers[j+1] = numbers[j]では、左に一つづつずらしている時に、tmpの箱に入っている数値の箇所は空白になるが、それを比較して大きい数値はどんどん右に移動させていくので、numbers[j+1] = numbers[j]とするだけで十分で数値の入れ替えは必要ない。

whileを抜けたら、一番左まで到達したか、tmpの値が適切な位置まで到達した(これ以上小さい値は左側にない)_ numbers[j+1] = tmpとしてtmpを配列に入れ戻す。 左側に一番小さい数値を入れていくことになるので、[3, 5, 1, 8 , 9, 4]のようなパターンで4を比較した時に1で止まらない?というのは起こり得ない。

4に到達するまでに、1は一番左の要素になっているため

from typing import List
import random

def insertion_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    for i in range(1, len_numbers):
        tmp = numbers[i]
        j = i - 1
        while j >= 0 and numbers[j] > tmp:
            numbers[j+1] = numbers[j]
            j -= 1
        
        numbers[j+1] = tmp
    
    return numbers

nums = [random.randint(0,1000) for i in range(10)]
print(insertion_sort(nums))

[127, 129, 358, 525, 614, 690, 710, 751, 847, 882]