Analisis Rantai Markov di R

Apa itu Rantai Markov?

Rantai Markov adalah sistem matematis yang mengalami transisi dari satu keadaan ke keadaan lain sesuai dengan seperangkat aturan probabilistik tertentu. Rantai Markov merupakan proses stokastik, tetapi berbeda karena harus tidak memiliki "memori". Artinya, probabilitas keadaan berikutnya dari suatu sistem hanya bergantung pada keadaan saat ini, bukan pada keadaan sebelumnya. Ini disebut sifat Markov (terlihat di bawah):

Untuk memiliki model rantai Markov yang fungsional, penting untuk mendefinisikan matriks transisi P_^t. Matriks transisi memuat informasi tentang probabilitas transisi antar berbagai keadaan dalam sistem. Agar valid, setiap baris pada matriks transisi harus berupa vektor probabilitas, dan jumlah seluruh elemennya harus 1.

Matriks Transisi memiliki sifat bahwa hasil kali matriks-matriks berurutan dapat menggambarkan probabilitas transisi sepanjang selang waktu. Karena itu, kita dapat memodelkan seberapa besar kemungkinan berada pada keadaan tertentu setelah k langkah dengan menghitung hal berikut:

Tutorial ini juga akan membahas rantai Markov menyerap (absorbing). Rantai ini terjadi ketika ada setidaknya satu keadaan yang, setelah dicapai, probabilitas untuk tetap di dalamnya adalah 1 (Anda tidak dapat meninggalkannya).

Apa itu Rantai Markov Menyerap?

Rantai Markov menyerap adalah rantai Markov di mana tidak mungkin keluar dari beberapa keadaan setelah memasukinya. Namun, ini hanya salah satu prasyarat agar sebuah rantai Markov termasuk rantai menyerap. Agar menjadi rantai Markov menyerap, semua keadaan transien lainnya harus dapat mencapai keadaan menyerap dengan probabilitas 1.

Rantai Markov menyerap memiliki sifat-sifat khusus yang membedakannya dari rantai Markov homogen waktu biasa. Salah satu sifat tersebut adalah cara matriks transisinya dapat ditulis. Dengan rantai yang memiliki t keadaan transien dan r keadaan menyerap, matriks transisi P dapat ditulis dalam bentuk kanonik sebagai berikut:

Dengan Q adalah matriks t x t, R adalah matriks t x r, 0 adalah matriks nol r x t, dan I_^r adalah matriks identitas r x r. Secara khusus, dekomposisi matriks transisi menjadi matriks fundamental memungkinkan perhitungan tertentu seperti jumlah langkah ekspektasian hingga terserap dari setiap keadaan. Matriks fundamental N dihitung sebagai berikut:

Dengan I_^t adalah matriks identitas t x t

Jumlah langkah ekspektasian didasarkan pada konsep linearitas ekspektasi, dan dihitung sebagai berikut:

Di mana 1 adalah vektor kolom dengan panjang sama seperti jumlah keadaan transien dengan semua entri bernilai 1

Selain itu, kita dapat menghitung probabilitas untuk terserap oleh suatu keadaan menyerap tertentu saat memulai dari keadaan transien mana pun. Probabilitas ini dihitung sebagai berikut:

Analisis Kecepatan Penjualan

Rantai Markov banyak digunakan di berbagai bidang seperti keuangan, teori permainan, dan genetika. Namun, dasar tutorial ini adalah bagaimana menggunakannya untuk memodelkan lamanya proses penjualan perusahaan karena ini bisa merupakan proses Markov. Hal ini memang divalidasi dengan menguji apakah urutan yang merinci langkah-langkah yang dilalui suatu kesepakatan sebelum berhasil ditutup memenuhi sifat Markov.

Analisis ini mengasumsikan bahwa probabilitas suatu kesepakatan bergerak maju dalam proses penjualan kami bersifat konstan dari bulan ke bulan untuk industri tertentu guna menggunakan rantai Markov homogen waktu. Artinya, rantai Markov di mana probabilitas transisi antar keadaan tetap konstan seiring waktu (jumlah langkah k meningkat).

Probabilitas yang dihitung adalah sebagai berikut:

• Probabilitas sebuah kesepakatan bergerak dari tahap perwakilan penjualan kami ke tahap eksekutif akun vs. tetap di sana untuk bulan tertentu.
• Probabilitas sebuah kesepakatan bergerak dari tahap eksekutif akun kami ke kesepakatan yang berhasil ditutup vs. tetap di dalamnya untuk bulan tertentu.
• Probabilitas tetap berada dalam kesepakatan yang berhasil ditutup, yaitu 1. Dengan demikian, membuat status "closed" menjadi keadaan menyerap.

Analisis ini dilakukan menggunakan bahasa pemrograman R. R memiliki paket praktis bernama Markov Chain yang dapat menangani beragam tipe rantai Markov.

Untuk memulai, hal pertama yang kami lakukan adalah memeriksa apakah urutan penjualan kami mengikuti sifat Markov. Untuk itu, paket Markov Chain memiliki fungsi praktis bernama verifyMarkovProperty() yang menguji apakah suatu urutan kejadian mengikuti sifat Markov dengan melakukan uji Chi-square pada serangkaian tabel kontingensi yang diturunkan dari urutan kejadian tersebut. Nilai p yang besar mengindikasikan bahwa hipotesis nol bahwa suatu urutan mengikuti sifat Markov tidak boleh ditolak. Contoh urutan penjualan yang menunjukkan posisi sebuah kesepakatan setiap bulan dari pertemuan pertama hingga saat ditutup disediakan di bawah ini:

library(markovchain)
library(dplyr)
# SDR Funnel is our sales representative stages, AE Funnel is our account executive stages, and CW is a successfully closed deal
seq <- c('SDR Funnel','SDR Funnel','AE Funnel','AE Funnel','AE Funnel','AE Funnel','AE Funnel','AE Funnel','CW')
verifyMarkovProperty(seq)

## Testing markovianity property on given data sequence
## Chi - square statistic is: 0.5733333  degrees of freedom are: 27  and corresponding p-value is: 1

Karena nilai p yang ditunjukkan di atas 0,05, kami tidak menolak hipotesis nol bahwa urutan tersebut mengikuti sifat Markov.

Setelah itu terverifikasi, kami memplot struktur rantai Markov beserta probabilitas transisi yang diturunkan dari data kami. Kode ini membuat objek rantai Markov dengan mendefinisikan matriks transisi serta nama-nama keadaannya. Kode ini juga menampilkan rantai Markov dan probabilitas transisinya.

source('TransProb.R')
source('MatDataBase.R')
source('GatherTransMat.R')
transElec <- GatherTransMat('Manufacturing','Between 100M and 500M', 'Between 500 and 1k')

print(transElec)

markov2 <- new('markovchain',
              transitionMatrix = transElec, # These are the transition probabilities of a random industry
              states = c('SDR','AE','CW'))

layout <- matrix(c(0,0,0,1,1,0), ncol = 2, byrow = TRUE)
plot(markov2, node.size = 10, layout = layout)

##           [,1]      [,2]      [,3]
## [1,] 0.5573215 0.4426785 0.0000000
## [2,] 0.0000000 0.8678118 0.1321882
## [3,] 0.0000000 0.0000000 1.0000000

Karena kita memiliki rantai Markov menyerap, kita menghitung waktu ekspektasian hingga terserap. Entri pertama dari vektor akan menghasilkan jumlah langkah ekspektasian hingga penutupan dari corong SDR, sementara entri kedua akan menghasilkan jumlah ekspektasian jika kita mulai dari corong AE.

# Extract Q from the transition matrix
Q <- transElec[1:2,1:2]
# Generate It
It <- diag(2)
#Calculate fundamental matrix
N <- solve(It-Q)
#Generate column vector of 1s
one <- t(t(c(1,1)))

# Calculate the expected steps by matrix multiplication
expected <- N%*%one
print(expected)

##          [,1]
## [1,] 9.823945
## [2,] 7.564969

Namun, kita juga dapat memvisualisasikan bagaimana probabilitas berubah seiring bertambahnya jumlah langkah untuk membandingkan jumlah langkah ekspektasian. Karena itu, kami juga memeriksa probabilitas sebuah kesepakatan berada di salah satu dari tiga tahap selama 24 langkah.

library(ggplot2)

initState <- c(1,0,0) # The initial state will be SDR Funnel (mimicking setting an initial discovery appointment)

# Initiate probability vectors
SDRProb <- c()
AEProb <- c()
CW <- c()

# Calculate probabilities for 24 steps.
for(k in 1:24){
  nsteps <- initState*markov2^k
  SDRProb[k] <- nsteps[1,1]
  AEProb[k] <- nsteps[1,2]
  CW[k] <- nsteps[1,3]
}

# Make dataframes and merge them
SDRProb <- as.data.frame(SDRProb)
SDRProb$Group <- 'SDR'
SDRProb$Iter <- 1:24
names(SDRProb)[1] <- 'Value'

AEProb <- as.data.frame(AEProb)
AEProb$Group <- 'AE'
AEProb$Iter <- 1:24
names(AEProb)[1] <- 'Value'

CW <- as.data.frame(CW)
CW$Group <- 'CW'
CW$Iter <- 1:24
names(CW)[1] <- 'Value'

steps <- rbind(SDRProb,AEProb,CW)

# Plot the probabilities using ggplot
ggplot(steps, aes(x = Iter, y = Value, col = Group))+
  geom_line() +
  xlab('Chain Step') +
  ylab('Probability') +
  ggtitle('24 Step Chain Probability Prediction')+
  theme(plot.title = element_text(hjust = 0.5))

Jika kita menggabungkan kedua hasil tersebut, tampak jelas bahwa keadaan CW menjadi keadaan paling mungkin setelah 6–9 langkah. Mengingat bahwa probabilitas transisi adalah probabilitas transisi bulanan, Anda dapat berargumen bahwa kecepatan penjualan khas dari penetapan janji awal hingga berhasil menutup kesepakatan untuk industri tersebut dapat berada di antara 6 dan 9 bulan. Itu proses penjualan yang cukup panjang.

Kesimpulan

Tujuan analisis ini adalah menunjukkan bagaimana prinsip dasar rantai Markov dan rantai Markov menyerap dapat digunakan untuk menjawab pertanyaan yang relevan bagi bisnis. Dalam kasus ini, hasil rantai Markov cukup akurat meskipun ada asumsi homogen waktu karena analisis empiris lebih lanjut mengungkapkan bahwa kecepatan penjualan rata-rata untuk industri yang digunakan dalam analisis ini adalah 208 hari, yang hampir 7 bulan. Semoga contoh ini mendorong Anda untuk mengeksplorasi rantai Markov lebih lanjut dan menerapkannya pada pertanyaan bisnis Anda.

Jika Anda tertarik mempelajari lebih lanjut tentang R, ikuti kursus Intermediate R dari DataCamp.

Lihat juga Rantai Markov di Python: Tutorial Pemula.