TweetsT-DP-BMM-FP.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "D:\\anacoda\\lib\\site-packages\\gensim\\utils.py:1197: UserWarning: detected Windows; aliasing chunkize to chunkize_serial\n",
      "  warnings.warn(\"detected Windows; aliasing chunkize to chunkize_serial\")\n"
     ]
    }
   ],
   "source": [
    "from sklearn.datasets import fetch_20newsgroups\n",
    "from nltk.stem.wordnet import WordNetLemmatizer\n",
    "from nltk.tokenize import RegexpTokenizer\n",
    "from nltk.corpus import stopwords\n",
    "from collections import defaultdict\n",
    "import gensim\n",
    "from InitKmeans import InitKmeans\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "from sklearn.mixture import GaussianMixture\n",
    "     \n",
    "def pre_processData(newsgroups_train):\n",
    "    tokenizer = RegexpTokenizer(r'\\w+')\n",
    "    for i in range(len(newsgroups_train)):\n",
    "        newsgroups_train[i] = newsgroups_train[i].lower()\n",
    "        #newsgroups_train[i] = tokenizer.tokenize(newsgroups_train[i])\n",
    "    #newsgroups_train = [[token for token in doc if not token.isdigit()] for doc in newsgroups_train]\n",
    "    newsgroups_train = [doc.split(' ') for doc in newsgroups_train]\n",
    "    return newsgroups_train\n",
    "from sklearn.datasets import fetch_20newsgroups\n",
    "from nltk.stem.wordnet import WordNetLemmatizer\n",
    "from nltk.tokenize import RegexpTokenizer\n",
    "from nltk.corpus import stopwords\n",
    "from collections import defaultdict\n",
    "import gensim\n",
    "from InitKmeans import InitKmeans\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "from sklearn.mixture import GaussianMixture\n",
    "import sys  \n",
    "import json\n",
    "if __name__ == \"__main__\":\n",
    "    newsgroups_train = list()\n",
    "    news_labels = {}\n",
    "    docID_username = {}\n",
    "    \n",
    "    i = 0\n",
    "    file_path=\"D:/part_news3_biterm.txt\"\n",
    "    with open(file_path) as fp:\n",
    "        lines = fp.read().split(\"\\n\")\n",
    "        for line in lines:\n",
    "            if line:\n",
    "                text = json.loads(line)[\"bitermText\"].strip()\n",
    "                label = json.loads(line)[\"clusterNo\"]\n",
    "                newsgroups_train.append(text)\n",
    "                news_labels[i] = label\n",
    "                i+=1\n",
    "    fp.close()\n",
    "    \n",
    "    corpus = pre_processData(newsgroups_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "doc_biterm = {}\n",
    "for docID in range(len(corpus)):\n",
    "    words = corpus[docID]\n",
    "    duplicate_biterm = []\n",
    "    doc_biterm[docID] = {}\n",
    "    for biterm in words:\n",
    "        hash_biterm = set(biterm.split(','))\n",
    "        if hash_biterm not in duplicate_biterm:\n",
    "            duplicate_biterm.append(hash_biterm)\n",
    "            doc_biterm[docID][biterm] = 1\n",
    "        else:\n",
    "            if biterm in doc_biterm[docID].keys():\n",
    "                doc_biterm[docID][biterm] += 1\n",
    "            else:\n",
    "                doc_biterm[docID][biterm] = 1\n",
    "doc_words = {}\n",
    "i_biterm = 0\n",
    "for docID in range(len(corpus)):\n",
    "    doc_words[docID] = {}\n",
    "    words = corpus[docID]\n",
    "    for biterm in words:\n",
    "        for word in biterm.split(','):\n",
    "            if word not in doc_words[docID].keys():\n",
    "                doc_words[docID][word] = 0\n",
    "            doc_words[docID][word] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "start  0  end  1895 topics:  74 truth:  32  NMI:  0.8441538426522822\n",
      "start  0  end  3790 topics:  106 truth:  62  NMI:  0.8312210474530084\n",
      "start  1896  end  5685 topics:  90 truth:  48  NMI:  0.8134929015078751\n",
      "start  3791  end  7580 topics:  87 truth:  38  NMI:  0.8254108499197133\n",
      "start  5686  end  9475 topics:  94 truth:  44  NMI:  0.8316848199157013\n",
      "start  7581  end  11370 topics:  84 truth:  33  NMI:  0.8465183329341434\n",
      "start  9476  end  13265 topics:  55 truth:  23  NMI:  0.8861585753363685\n",
      "start  11371  end  15160 topics:  61 truth:  35  NMI:  0.8907185578531914\n",
      "start  13266  end  17055 topics:  71 truth:  37  NMI:  0.8914560693223879\n",
      "start  15161  end  18950 topics:  57 truth:  31  NMI:  0.8855585610744889\n",
      "start  17056  end  20845 topics:  55 truth:  28  NMI:  0.9122174573737886\n",
      "start  18951  end  22740 topics:  52 truth:  22  NMI:  0.9094036828236365\n",
      "start  20846  end  24635 topics:  50 truth:  21  NMI:  0.8864085759101779\n",
      "start  22741  end  26530 topics:  68 truth:  30  NMI:  0.8599767131213099\n",
      "start  24636  end  28425 topics:  76 truth:  36  NMI:  0.7995858837720357\n",
      "start  26531  end  30322 topics:  75 truth:  25  NMI:  0.7883701825543133\n"
     ]
    }
   ],
   "source": [
    "total_batch = 16\n",
    "NMI_batch = {}\n",
    "start = 0\n",
    "end = 0\n",
    "topic_batch = {}\n",
    "for batch_i in range(1,17):\n",
    "    if batch_i == 16:\n",
    "        end = int(len(corpus))\n",
    "    else:\n",
    "        end = int(len(corpus) / total_batch) * batch_i\n",
    "    \n",
    "    docID_assign_z = {}\n",
    "    m_z = {}\n",
    "    n_z = {}\n",
    "    n_w = {}\n",
    "    n_b = {}\n",
    "    Topics = []\n",
    "    V = set()\n",
    "    D = set()\n",
    "    alpha = 0.003\n",
    "    beta = 0.02\n",
    "    NMI_batch[batch_i] = 0\n",
    "    topic_batch[batch_i] = 0\n",
    "    \n",
    "    total_iter = 10\n",
    "    for iter in range(total_iter):\n",
    "        for docID in range(start,end):\n",
    "            words = corpus[docID]\n",
    "            D.discard(docID)\n",
    "            if docID in docID_assign_z.keys():\n",
    "                before_k = docID_assign_z[docID]\n",
    "                m_z[before_k].discard(docID)\n",
    "                for biterm in words:\n",
    "                    for word in biterm.split(','):\n",
    "                        n_z[before_k][word] -= 1\n",
    "                        n_w[before_k] -=1\n",
    "            else:\n",
    "                before_k = -1\n",
    "            if len(D) == 0 and len(V) == 0:\n",
    "                choose_k = 0\n",
    "                D.add(docID)\n",
    "                docID_assign_z[docID] = choose_k\n",
    "                if choose_k not in m_z.keys():\n",
    "                    m_z[choose_k] = set()\n",
    "                m_z[choose_k].add(docID)\n",
    "                for biterm in words:\n",
    "                    for word in biterm.split(','):\n",
    "                        if choose_k not in n_w.keys():\n",
    "                            n_w[choose_k] = 0\n",
    "                        if choose_k not in n_z.keys():\n",
    "                            n_z[choose_k] = {}\n",
    "                        if word not in n_z[choose_k].keys():\n",
    "                            n_z[choose_k][word] = 0\n",
    "                        n_z[choose_k][word] += 1\n",
    "                        n_w[choose_k] += 1\n",
    "                        V.add(word)\n",
    "                if choose_k not in Topics:\n",
    "                    Topics.append(choose_k)\n",
    "            else:\n",
    "                log_pro = []\n",
    "                for k in Topics:\n",
    "                    pro_k = len(m_z[k])\n",
    "                    if pro_k != 0:\n",
    "                        i = 0\n",
    "                        for biterm in words:\n",
    "                            each_word = biterm.strip().split(',')\n",
    "                            for word in each_word:\n",
    "                                if word not in n_z[k].keys():\n",
    "                                    n_z[k][word] = 0\n",
    "                            for j in range(doc_biterm[docID][biterm]):\n",
    "                                pro_k *= (n_z[k][each_word[0]] + n_z[k][each_word[-1]] + beta + j) / ( n_w[k] + len(V)*beta + i) \n",
    "                                i += 1\n",
    "\n",
    "                    if pro_k == 0:\n",
    "                        pro_k = sys.float_info.min\n",
    "                    log_pro.append(pro_k)\n",
    "\n",
    "                pro_new_k = alpha*(len(D))\n",
    "                i = 0\n",
    "                for biterm in words:\n",
    "                    for j in range(doc_biterm[docID][biterm]):\n",
    "                        pro_new_k *= ( beta + j) / ( len(V)*beta + i) \n",
    "                        i += 1\n",
    "\n",
    "                if pro_new_k == 0:\n",
    "                    pro_new_k = sys.float_info.min        \n",
    "                log_pro.append(pro_new_k)\n",
    "\n",
    "                sum_pro=sum(log_pro)\n",
    "\n",
    "                normalized_posterior = [i/sum_pro for i in log_pro]    \n",
    "                select_k = None\n",
    "                if iter == (total_iter - 1):\n",
    "                    select_k = normalized_posterior.index(max(normalized_posterior))\n",
    "\n",
    "                else:\n",
    "                    select_k = np.random.choice( (len(Topics)+1) , 1, p=normalized_posterior)[0]  \n",
    "\n",
    "                if select_k == len(Topics):\n",
    "                    choose_k = np.max(Topics) + 1\n",
    "                else:\n",
    "                    choose_k = Topics[select_k]\n",
    "\n",
    "                D.add(docID)\n",
    "                docID_assign_z[docID] = choose_k\n",
    "                if choose_k not in m_z.keys():\n",
    "                    m_z[choose_k] = set()\n",
    "                m_z[choose_k].add(docID)\n",
    "                for biterm in words:\n",
    "                    for word in biterm.split(','):\n",
    "                        if choose_k not in n_w.keys():\n",
    "                            n_w[choose_k] = 0\n",
    "                        if choose_k not in n_z.keys():\n",
    "                            n_z[choose_k] = {}\n",
    "                        if word not in n_z[choose_k].keys():\n",
    "                            n_z[choose_k][word] = 0\n",
    "                        n_z[choose_k][word] += 1\n",
    "                        n_w[choose_k] += 1\n",
    "                        V.add(word)\n",
    "                if choose_k not in Topics:\n",
    "                    Topics.append(choose_k)\n",
    "\n",
    "            count_k = []\n",
    "            for k in Topics:\n",
    "                if k in m_z.keys() and len(m_z[k]) == 0:\n",
    "                    m_z.pop(k, None)\n",
    "                    n_z.pop(k, None)\n",
    "                    n_w.pop(k, None)\n",
    "                    count_k.append(k)\n",
    "            for k in count_k:\n",
    "                Topics.remove(k)   \n",
    "        if iter == 9:\n",
    "            from sklearn.metrics.cluster import normalized_mutual_info_score\n",
    "            nmi_sample = []\n",
    "            nmi_result = []\n",
    "            for key, value in news_labels.items():\n",
    "                if key < end and key >= start:\n",
    "                    nmi_sample.append(value)\n",
    "                    nmi_result.append(docID_assign_z[key])\n",
    "            NMI_batch[batch_i] = normalized_mutual_info_score(np.array(nmi_sample), np.array(nmi_result))\n",
    "            topic_batch[batch_i] = len(Topics)\n",
    "            print(\"start \",start, \" end \",end, \"topics: \",len(Topics),\"truth: \",len(np.unique(nmi_sample)), \" NMI: \",normalized_mutual_info_score(np.array(nmi_sample), np.array(nmi_result)))\n",
    "    if batch_i != 1:\n",
    "        start = int(len(corpus) / total_batch) * (batch_i -1) + 1\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "start  0  end  1895 topics:  91 truth:  32  NMI:  0.8541620657728693\n",
      "start  0  end  3790 topics:  133 truth:  62  NMI:  0.825823225627117\n",
      "start  1896  end  5685 topics:  114 truth:  48  NMI:  0.8033470558632811\n",
      "start  3791  end  7580 topics:  106 truth:  38  NMI:  0.8289650313973387\n",
      "start  5686  end  9475 topics:  119 truth:  44  NMI:  0.8322720147139834\n",
      "start  7581  end  11370 topics:  100 truth:  33  NMI:  0.8503644239682501\n",
      "start  9476  end  13265 topics:  64 truth:  23  NMI:  0.8652697963710134\n",
      "start  11371  end  15160 topics:  81 truth:  35  NMI:  0.9006097384737322\n",
      "start  13266  end  17055 topics:  87 truth:  37  NMI:  0.8804840098696127\n",
      "start  15161  end  18950 topics:  64 truth:  31  NMI:  0.8783485256081192\n",
      "start  17056  end  20845 topics:  79 truth:  28  NMI:  0.8925488587618355\n",
      "start  18951  end  22740 topics:  74 truth:  22  NMI:  0.8935566664477498\n",
      "start  20846  end  24635 topics:  65 truth:  21  NMI:  0.8783042535008054\n",
      "start  22741  end  26530 topics:  76 truth:  30  NMI:  0.8529155013334383\n",
      "start  24636  end  28425 topics:  100 truth:  36  NMI:  0.7888824121272956\n",
      "start  26531  end  30322 topics:  92 truth:  25  NMI:  0.7680583941160468\n"
     ]
    }
   ],
   "source": [
    "total_batch = 16\n",
    "NMI_batch = {}\n",
    "start = 0\n",
    "end = 0\n",
    "topic_batch = {}\n",
    "for batch_i in range(1,17):\n",
    "    if batch_i == 16:\n",
    "        end = int(len(corpus))\n",
    "    else:\n",
    "        end = int(len(corpus) / total_batch) * batch_i\n",
    "    \n",
    "    docID_assign_z = {}\n",
    "    m_z = {}\n",
    "    n_z = {}\n",
    "    n_w = {}\n",
    "    n_b = {}\n",
    "    Topics = []\n",
    "    V = set()\n",
    "    D = set()\n",
    "    alpha = 0.3\n",
    "    beta = 0.02\n",
    "    NMI_batch[batch_i] = 0\n",
    "    topic_batch[batch_i] = 0\n",
    "    \n",
    "    total_iter = 10\n",
    "    for iter in range(total_iter):\n",
    "        for docID in range(start,end):\n",
    "            words = corpus[docID]\n",
    "            D.discard(docID)\n",
    "            if docID in docID_assign_z.keys():\n",
    "                before_k = docID_assign_z[docID]\n",
    "                m_z[before_k].discard(docID)\n",
    "                for biterm in words:\n",
    "                    for word in biterm.split(','):\n",
    "                        n_z[before_k][word] -= 1\n",
    "                        n_w[before_k] -=1\n",
    "            else:\n",
    "                before_k = -1\n",
    "            if len(D) == 0 and len(V) == 0:\n",
    "                choose_k = 0\n",
    "                D.add(docID)\n",
    "                docID_assign_z[docID] = choose_k\n",
    "                if choose_k not in m_z.keys():\n",
    "                    m_z[choose_k] = set()\n",
    "                m_z[choose_k].add(docID)\n",
    "                for biterm in words:\n",
    "                    for word in biterm.split(','):\n",
    "                        if choose_k not in n_w.keys():\n",
    "                            n_w[choose_k] = 0\n",
    "                        if choose_k not in n_z.keys():\n",
    "                            n_z[choose_k] = {}\n",
    "                        if word not in n_z[choose_k].keys():\n",
    "                            n_z[choose_k][word] = 0\n",
    "                        n_z[choose_k][word] += 1\n",
    "                        n_w[choose_k] += 1\n",
    "                        V.add(word)\n",
    "                if choose_k not in Topics:\n",
    "                    Topics.append(choose_k)\n",
    "            else:\n",
    "                log_pro = []\n",
    "                for k in Topics:\n",
    "                    pro_k = len(m_z[k])\n",
    "                    if pro_k != 0:\n",
    "                        i = 0\n",
    "                        for biterm in words:\n",
    "                            each_word = biterm.strip().split(',')\n",
    "                            for word in each_word:\n",
    "                                if word not in n_z[k].keys():\n",
    "                                    n_z[k][word] = 0\n",
    "                            for j in range(doc_biterm[docID][biterm]):\n",
    "                                pro_k *= (n_z[k][each_word[0]] + n_z[k][each_word[-1]] + beta + j) / ( n_w[k] + len(V)*beta + i) \n",
    "                                i += 1\n",
    "\n",
    "                    if pro_k == 0:\n",
    "                        pro_k = sys.float_info.min\n",
    "                    log_pro.append(pro_k)\n",
    "\n",
    "                pro_new_k = alpha*(len(D))\n",
    "                i = 0\n",
    "                for biterm in words:\n",
    "                    for j in range(doc_biterm[docID][biterm]):\n",
    "                        pro_new_k *= ( beta + j) / ( len(V)*beta + i) \n",
    "                        i += 1\n",
    "\n",
    "                if pro_new_k == 0:\n",
    "                    pro_new_k = sys.float_info.min        \n",
    "                log_pro.append(pro_new_k)\n",
    "\n",
    "                sum_pro=sum(log_pro)\n",
    "\n",
    "                normalized_posterior = [i/sum_pro for i in log_pro]    \n",
    "                select_k = None\n",
    "                if iter == (total_iter - 1):\n",
    "                    select_k = normalized_posterior.index(max(normalized_posterior))\n",
    "\n",
    "                else:\n",
    "                    select_k = np.random.choice( (len(Topics)+1) , 1, p=normalized_posterior)[0]  \n",
    "\n",
    "                if select_k == len(Topics):\n",
    "                    choose_k = np.max(Topics) + 1\n",
    "                else:\n",
    "                    choose_k = Topics[select_k]\n",
    "\n",
    "                D.add(docID)\n",
    "                docID_assign_z[docID] = choose_k\n",
    "                if choose_k not in m_z.keys():\n",
    "                    m_z[choose_k] = set()\n",
    "                m_z[choose_k].add(docID)\n",
    "                for biterm in words:\n",
    "                    for word in biterm.split(','):\n",
    "                        if choose_k not in n_w.keys():\n",
    "                            n_w[choose_k] = 0\n",
    "                        if choose_k not in n_z.keys():\n",
    "                            n_z[choose_k] = {}\n",
    "                        if word not in n_z[choose_k].keys():\n",
    "                            n_z[choose_k][word] = 0\n",
    "                        n_z[choose_k][word] += 1\n",
    "                        n_w[choose_k] += 1\n",
    "                        V.add(word)\n",
    "                if choose_k not in Topics:\n",
    "                    Topics.append(choose_k)\n",
    "\n",
    "            count_k = []\n",
    "            for k in Topics:\n",
    "                if k in m_z.keys() and len(m_z[k]) == 0:\n",
    "                    m_z.pop(k, None)\n",
    "                    n_z.pop(k, None)\n",
    "                    n_w.pop(k, None)\n",
    "                    count_k.append(k)\n",
    "            for k in count_k:\n",
    "                Topics.remove(k)   \n",
    "        if iter == 9:\n",
    "            from sklearn.metrics.cluster import normalized_mutual_info_score\n",
    "            nmi_sample = []\n",
    "            nmi_result = []\n",
    "            for key, value in news_labels.items():\n",
    "                if key < end and key >= start:\n",
    "                    nmi_sample.append(value)\n",
    "                    nmi_result.append(docID_assign_z[key])\n",
    "            NMI_batch[batch_i] = normalized_mutual_info_score(np.array(nmi_sample), np.array(nmi_result))\n",
    "            topic_batch[batch_i] = len(Topics)\n",
    "            print(\"start \",start, \" end \",end, \"topics: \",len(Topics),\"truth: \",len(np.unique(nmi_sample)), \" NMI: \",normalized_mutual_info_score(np.array(nmi_sample), np.array(nmi_result)))\n",
    "    if batch_i != 1:\n",
    "        start = int(len(corpus) / total_batch) * (batch_i -1) + 1\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]\n",
      "\n",
      "[0.8541620657728693, 0.825823225627117, 0.8033470558632811, 0.8289650313973387, 0.8322720147139834, 0.8503644239682501, 0.8652697963710134, 0.9006097384737322, 0.8804840098696127, 0.8783485256081192, 0.8925488587618355, 0.8935566664477498, 0.8783042535008054, 0.8529155013334383, 0.7888824121272956, 0.7680583941160468]\n",
      "\n",
      "0.8496194983720305\n"
     ]
    }
   ],
   "source": [
    "common_keys = []\n",
    "\n",
    "item_NMI = []\n",
    "for key,value in sorted(NMI_batch.items(), key=lambda x: x[0]):\n",
    "    common_keys.append(key)\n",
    "    item_NMI.append(value)\n",
    "print(common_keys)\n",
    "\n",
    "print()\n",
    "\n",
    "print(item_NMI)\n",
    "print()\n",
    "\n",
    "print(np.mean(item_NMI))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "start  0  end  1895 topics:  93 truth:  32  NMI:  0.8493299044970227\n",
      "[124.47662545532339]\n",
      "start  0  end  3790 topics:  135 truth:  62  NMI:  0.8358267224037599\n",
      "[124.47662545532339, 322.9079524862167]\n",
      "start  1896  end  5685 topics:  111 truth:  48  NMI:  0.8176920153201213\n",
      "[124.47662545532339, 322.9079524862167, 259.24636514990857]\n",
      "start  3791  end  7580 topics:  104 truth:  38  NMI:  0.8268768354116884\n",
      "[124.47662545532339, 322.9079524862167, 259.24636514990857, 243.3053607597542]\n",
      "start  5686  end  9475 topics:  124 truth:  44  NMI:  0.8341988252151786\n",
      "[124.47662545532339, 322.9079524862167, 259.24636514990857, 243.3053607597542, 277.14703576694296]\n",
      "start  7581  end  11370 topics:  105 truth:  33  NMI:  0.840153174618594\n",
      "[124.47662545532339, 322.9079524862167, 259.24636514990857, 243.3053607597542, 277.14703576694296, 238.6720100092275]\n",
      "start  9476  end  13265 topics:  69 truth:  23  NMI:  0.8664766012830064\n",
      "[124.47662545532339, 322.9079524862167, 259.24636514990857, 243.3053607597542, 277.14703576694296, 238.6720100092275, 185.51932361996774]\n",
      "start  11371  end  15160 topics:  81 truth:  35  NMI:  0.9002085161456742\n",
      "[124.47662545532339, 322.9079524862167, 259.24636514990857, 243.3053607597542, 277.14703576694296, 238.6720100092275, 185.51932361996774, 217.8748891644525]\n",
      "start  13266  end  17055 topics:  83 truth:  37  NMI:  0.8859663700924478\n",
      "[124.47662545532339, 322.9079524862167, 259.24636514990857, 243.3053607597542, 277.14703576694296, 238.6720100092275, 185.51932361996774, 217.8748891644525, 326.1817724012501]\n",
      "start  15161  end  18950 topics:  67 truth:  31  NMI:  0.86634466369112\n",
      "[124.47662545532339, 322.9079524862167, 259.24636514990857, 243.3053607597542, 277.14703576694296, 238.6720100092275, 185.51932361996774, 217.8748891644525, 326.1817724012501, 279.013968509033]\n",
      "start  17056  end  20845 topics:  73 truth:  28  NMI:  0.9077727279047639\n",
      "[124.47662545532339, 322.9079524862167, 259.24636514990857, 243.3053607597542, 277.14703576694296, 238.6720100092275, 185.51932361996774, 217.8748891644525, 326.1817724012501, 279.013968509033, 233.55943805062816]\n",
      "start  18951  end  22740 topics:  66 truth:  22  NMI:  0.8930466891854689\n",
      "[124.47662545532339, 322.9079524862167, 259.24636514990857, 243.3053607597542, 277.14703576694296, 238.6720100092275, 185.51932361996774, 217.8748891644525, 326.1817724012501, 279.013968509033, 233.55943805062816, 220.87854437132683]\n",
      "start  20846  end  24635 topics:  56 truth:  21  NMI:  0.8597292178889554\n",
      "[124.47662545532339, 322.9079524862167, 259.24636514990857, 243.3053607597542, 277.14703576694296, 238.6720100092275, 185.51932361996774, 217.8748891644525, 326.1817724012501, 279.013968509033, 233.55943805062816, 220.87854437132683, 194.89093992450398]\n",
      "start  22741  end  26530 topics:  75 truth:  30  NMI:  0.8638505012009249\n",
      "[124.47662545532339, 322.9079524862167, 259.24636514990857, 243.3053607597542, 277.14703576694296, 238.6720100092275, 185.51932361996774, 217.8748891644525, 326.1817724012501, 279.013968509033, 233.55943805062816, 220.87854437132683, 194.89093992450398, 270.11886558483775]\n",
      "start  24636  end  28425 topics:  92 truth:  36  NMI:  0.7997994348441185\n",
      "[124.47662545532339, 322.9079524862167, 259.24636514990857, 243.3053607597542, 277.14703576694296, 238.6720100092275, 185.51932361996774, 217.8748891644525, 326.1817724012501, 279.013968509033, 233.55943805062816, 220.87854437132683, 194.89093992450398, 270.11886558483775, 321.921819136217]\n",
      "start  26531  end  30322 topics:  93 truth:  25  NMI:  0.7516159205447744\n",
      "[124.47662545532339, 322.9079524862167, 259.24636514990857, 243.3053607597542, 277.14703576694296, 238.6720100092275, 185.51932361996774, 217.8748891644525, 326.1817724012501, 279.013968509033, 233.55943805062816, 220.87854437132683, 194.89093992450398, 270.11886558483775, 321.921819136217, 273.0754724351127]\n"
     ]
    }
   ],
   "source": [
    "import timeit\n",
    "total_batch = 16\n",
    "NMI_batch = {}\n",
    "start = 0\n",
    "end = 0\n",
    "topic_batch = {}\n",
    "time_iteration_list = []\n",
    "for batch_i in range(1,17):\n",
    "    if batch_i == 16:\n",
    "        end = int(len(corpus))\n",
    "    else:\n",
    "        end = int(len(corpus) / total_batch) * batch_i\n",
    "    \n",
    "    docID_assign_z = {}\n",
    "    m_z = {}\n",
    "    n_z = {}\n",
    "    n_w = {}\n",
    "    n_b = {}\n",
    "    Topics = []\n",
    "    V = set()\n",
    "    D = set()\n",
    "    alpha = 0.3\n",
    "    beta = 0.02\n",
    "    NMI_batch[batch_i] = 0\n",
    "    topic_batch[batch_i] = 0\n",
    "    \n",
    "    time_start = timeit.default_timer()\n",
    "    total_iter = 10\n",
    "    for iter in range(total_iter):\n",
    "        for docID in range(start,end):\n",
    "            words = corpus[docID]\n",
    "            D.discard(docID)\n",
    "            if docID in docID_assign_z.keys():\n",
    "                before_k = docID_assign_z[docID]\n",
    "                m_z[before_k].discard(docID)\n",
    "                for biterm in words:\n",
    "                    for word in biterm.split(','):\n",
    "                        n_z[before_k][word] -= 1\n",
    "                        n_w[before_k] -=1\n",
    "            else:\n",
    "                before_k = -1\n",
    "            if len(D) == 0 and len(V) == 0:\n",
    "                choose_k = 0\n",
    "                D.add(docID)\n",
    "                docID_assign_z[docID] = choose_k\n",
    "                if choose_k not in m_z.keys():\n",
    "                    m_z[choose_k] = set()\n",
    "                m_z[choose_k].add(docID)\n",
    "                for biterm in words:\n",
    "                    for word in biterm.split(','):\n",
    "                        if choose_k not in n_w.keys():\n",
    "                            n_w[choose_k] = 0\n",
    "                        if choose_k not in n_z.keys():\n",
    "                            n_z[choose_k] = {}\n",
    "                        if word not in n_z[choose_k].keys():\n",
    "                            n_z[choose_k][word] = 0\n",
    "                        n_z[choose_k][word] += 1\n",
    "                        n_w[choose_k] += 1\n",
    "                        V.add(word)\n",
    "                if choose_k not in Topics:\n",
    "                    Topics.append(choose_k)\n",
    "            else:\n",
    "                log_pro = []\n",
    "                for k in Topics:\n",
    "                    pro_k = len(m_z[k])\n",
    "                    if pro_k != 0:\n",
    "                        i = 0\n",
    "                        for biterm in words:\n",
    "                            each_word = biterm.strip().split(',')\n",
    "                            for word in each_word:\n",
    "                                if word not in n_z[k].keys():\n",
    "                                    n_z[k][word] = 0\n",
    "                            for j in range(doc_biterm[docID][biterm]):\n",
    "                                pro_k *= (n_z[k][each_word[0]] + n_z[k][each_word[-1]] + beta + j) / ( n_w[k] + len(V)*beta + i) \n",
    "                                i += 1\n",
    "\n",
    "                    if pro_k == 0:\n",
    "                        pro_k = sys.float_info.min\n",
    "                    log_pro.append(pro_k)\n",
    "\n",
    "                pro_new_k = alpha*(len(D))\n",
    "                i = 0\n",
    "                for biterm in words:\n",
    "                    for j in range(doc_biterm[docID][biterm]):\n",
    "                        pro_new_k *= ( beta + j) / ( len(V)*beta + i) \n",
    "                        i += 1\n",
    "\n",
    "                if pro_new_k == 0:\n",
    "                    pro_new_k = sys.float_info.min        \n",
    "                log_pro.append(pro_new_k)\n",
    "\n",
    "                sum_pro=sum(log_pro)\n",
    "\n",
    "                normalized_posterior = [i/sum_pro for i in log_pro]    \n",
    "                select_k = None\n",
    "                if iter == (total_iter - 1):\n",
    "                    select_k = normalized_posterior.index(max(normalized_posterior))\n",
    "\n",
    "                else:\n",
    "                    select_k = np.random.choice( (len(Topics)+1) , 1, p=normalized_posterior)[0]  \n",
    "\n",
    "                if select_k == len(Topics):\n",
    "                    choose_k = np.max(Topics) + 1\n",
    "                else:\n",
    "                    choose_k = Topics[select_k]\n",
    "\n",
    "                D.add(docID)\n",
    "                docID_assign_z[docID] = choose_k\n",
    "                if choose_k not in m_z.keys():\n",
    "                    m_z[choose_k] = set()\n",
    "                m_z[choose_k].add(docID)\n",
    "                for biterm in words:\n",
    "                    for word in biterm.split(','):\n",
    "                        if choose_k not in n_w.keys():\n",
    "                            n_w[choose_k] = 0\n",
    "                        if choose_k not in n_z.keys():\n",
    "                            n_z[choose_k] = {}\n",
    "                        if word not in n_z[choose_k].keys():\n",
    "                            n_z[choose_k][word] = 0\n",
    "                        n_z[choose_k][word] += 1\n",
    "                        n_w[choose_k] += 1\n",
    "                        V.add(word)\n",
    "                if choose_k not in Topics:\n",
    "                    Topics.append(choose_k)\n",
    "\n",
    "            count_k = []\n",
    "            for k in Topics:\n",
    "                if k in m_z.keys() and len(m_z[k]) == 0:\n",
    "                    m_z.pop(k, None)\n",
    "                    n_z.pop(k, None)\n",
    "                    n_w.pop(k, None)\n",
    "                    count_k.append(k)\n",
    "            for k in count_k:\n",
    "                Topics.remove(k)   \n",
    "        if iter == 9:\n",
    "            from sklearn.metrics.cluster import normalized_mutual_info_score\n",
    "            nmi_sample = []\n",
    "            nmi_result = []\n",
    "            for key, value in news_labels.items():\n",
    "                if key < end and key >= start:\n",
    "                    nmi_sample.append(value)\n",
    "                    nmi_result.append(docID_assign_z[key])\n",
    "            NMI_batch[batch_i] = normalized_mutual_info_score(np.array(nmi_sample), np.array(nmi_result))\n",
    "            topic_batch[batch_i] = len(Topics)\n",
    "            print(\"start \",start, \" end \",end, \"topics: \",len(Topics),\"truth: \",len(np.unique(nmi_sample)), \" NMI: \",normalized_mutual_info_score(np.array(nmi_sample), np.array(nmi_result)))\n",
    "    if batch_i != 1:\n",
    "        start = int(len(corpus) / total_batch) * (batch_i -1) + 1\n",
    "    time_stop = timeit.default_timer()\n",
    "    time_iteration_list.append(time_stop-time_start)\n",
    "    print(time_iteration_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dict_keys([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16])\n",
      "dict_values([93, 135, 111, 104, 124, 105, 69, 81, 83, 67, 73, 66, 56, 75, 92, 93])\n"
     ]
    }
   ],
   "source": [
    "print(topic_batch.keys())\n",
    "print(topic_batch.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "0.8461431116282747"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]\n",
      "\n",
      "[0.8490775422178058, 0.8360113596016167, 0.8017326375272005, 0.8269963983134461, 0.8259949715651002, 0.8469034211974069, 0.8689500165610579, 0.8880185467940986, 0.8879679257956725, 0.8556842818338339, 0.8924981532543471, 0.8898471837668972, 0.8751979807882151, 0.8591115412272363, 0.7716295524551399, 0.7626682731533194]\n",
      "\n",
      "0.8461431116282747\n"
     ]
    }
   ],
   "source": [
    "common_keys = []\n",
    "\n",
    "item_NMI = []\n",
    "for key,value in sorted(NMI_batch.items(), key=lambda x: x[0]):\n",
    "    common_keys.append(key)\n",
    "    item_NMI.append(value)\n",
    "print(common_keys)\n",
    "\n",
    "print()\n",
    "\n",
    "print(item_NMI)\n",
    "print()\n",
    "\n",
    "print(np.mean(item_NMI))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]\n",
      "\n",
      "[0.8498076980818865, 0.7774663436307994, 0.777480416315458, 0.799597977152846, 0.8123893850338224, 0.7853681035349211, 0.8601579571732086, 0.8769340148293916, 0.8248206313398326, 0.8543233453659018, 0.8462780378479873, 0.827834189858882, 0.8621949972642189, 0.7796067956372406, 0.7501453688617773, 0.6809083067114148]\n",
      "\n",
      "0.8103320980399742\n"
     ]
    }
   ],
   "source": [
    "common_keys = []\n",
    "\n",
    "item_NMI = []\n",
    "for key,value in sorted(NMI_batch.items(), key=lambda x: x[0]):\n",
    "    common_keys.append(key)\n",
    "    item_NMI.append(value)\n",
    "print(common_keys)\n",
    "\n",
    "print()\n",
    "\n",
    "print(item_NMI)\n",
    "print()\n",
    "\n",
    "print(np.mean(item_NMI))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1: 0.8441538426522822, 2: 0.8312210474530084, 3: 0.8134929015078751, 4: 0.8254108499197133, 5: 0.8316848199157013, 6: 0.8465183329341434, 7: 0.8861585753363685, 8: 0.8907185578531914, 9: 0.8914560693223879, 10: 0.8855585610744889, 11: 0.9122174573737886, 12: 0.9094036828236365, 13: 0.8864085759101779, 14: 0.8599767131213099, 15: 0.7995858837720357, 16: 0.7883701825543133}\n",
      "0.02\n",
      "dict_keys([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16])\n",
      "dict_values([0.8441538426522822, 0.8312210474530084, 0.8134929015078751, 0.8254108499197133, 0.8316848199157013, 0.8465183329341434, 0.8861585753363685, 0.8907185578531914, 0.8914560693223879, 0.8855585610744889, 0.9122174573737886, 0.9094036828236365, 0.8864085759101779, 0.8599767131213099, 0.7995858837720357, 0.7883701825543133])\n"
     ]
    }
   ],
   "source": [
    "print(NMI_batch)\n",
    "print(beta)\n",
    "print(NMI_batch.keys())\n",
    "print(NMI_batch.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "start  0  end  500 topics:  44 truth:  32  NMI:  0.880181128846321\n",
      "start  500  end  1000 topics:  37 truth:  29  NMI:  0.8781310441089455\n",
      "start  1000  end  1500 topics:  36 truth:  27  NMI:  0.8903626031124846\n",
      "start  1500  end  2000 topics:  49 truth:  53  NMI:  0.8802891820550155\n",
      "start  2000  end  2500 topics:  41 truth:  29  NMI:  0.8065787161554409\n",
      "start  2500  end  3000 topics:  39 truth:  30  NMI:  0.8244414545681393\n",
      "start  3000  end  3500 topics:  40 truth:  30  NMI:  0.8427443074941608\n",
      "start  3500  end  4000 topics:  45 truth:  45  NMI:  0.8249955372910738\n",
      "start  4000  end  4500 topics:  40 truth:  18  NMI:  0.8249857718905035\n",
      "start  4500  end  5000 topics:  30 truth:  17  NMI:  0.8373118759546907\n",
      "start  5000  end  5500 topics:  33 truth:  18  NMI:  0.8274495385773019\n",
      "start  5500  end  6000 topics:  44 truth:  37  NMI:  0.8243009403391134\n",
      "start  6000  end  6500 topics:  35 truth:  21  NMI:  0.8392714729131685\n",
      "start  6500  end  7000 topics:  33 truth:  21  NMI:  0.8556819033068159\n",
      "start  7000  end  7500 topics:  39 truth:  21  NMI:  0.8614101236288397\n",
      "start  7500  end  8000 topics:  50 truth:  39  NMI:  0.8850371548645493\n",
      "start  8000  end  8500 topics:  37 truth:  24  NMI:  0.8403906752788657\n",
      "start  8500  end  9000 topics:  49 truth:  24  NMI:  0.8220668353085563\n",
      "start  9000  end  9500 topics:  42 truth:  32  NMI:  0.8744072197265904\n",
      "start  9500  end  10000 topics:  18 truth:  10  NMI:  0.8774912503219744\n",
      "start  10000  end  10500 topics:  21 truth:  10  NMI:  0.8300296696402276\n",
      "start  10500  end  11000 topics:  25 truth:  10  NMI:  0.8334140813293694\n",
      "start  11000  end  11500 topics:  38 truth:  23  NMI:  0.8977474954163979\n",
      "start  11500  end  12000 topics:  24 truth:  14  NMI:  0.9061124878029874\n",
      "start  12000  end  12500 topics:  26 truth:  14  NMI:  0.9262559650343551\n",
      "start  12500  end  13000 topics:  23 truth:  14  NMI:  0.9229661598166313\n",
      "start  13000  end  13500 topics:  42 truth:  33  NMI:  0.9083133309514114\n",
      "start  13500  end  14000 topics:  29 truth:  22  NMI:  0.9053395054295947\n",
      "start  14000  end  14500 topics:  30 truth:  21  NMI:  0.8928315213516842\n",
      "start  14500  end  15000 topics:  30 truth:  22  NMI:  0.9196137968443262\n",
      "start  15000  end  15500 topics:  32 truth:  34  NMI:  0.8876037759344444\n",
      "start  15500  end  16000 topics:  23 truth:  16  NMI:  0.9022462055522564\n",
      "start  16000  end  16500 topics:  24 truth:  16  NMI:  0.8818799347608985\n",
      "start  16500  end  17000 topics:  21 truth:  15  NMI:  0.8917594478084228\n",
      "start  17000  end  17500 topics:  30 truth:  26  NMI:  0.9015455645845137\n",
      "start  17500  end  18000 topics:  20 truth:  16  NMI:  0.9325381132984558\n",
      "start  18000  end  18500 topics:  24 truth:  16  NMI:  0.9295841377350417\n",
      "start  18500  end  19000 topics:  28 truth:  26  NMI:  0.9328653390711169\n",
      "start  19000  end  19500 topics:  21 truth:  13  NMI:  0.9077193070162694\n",
      "start  19500  end  20000 topics:  20 truth:  13  NMI:  0.9306916480786396\n",
      "start  20000  end  20500 topics:  21 truth:  13  NMI:  0.9397634573184117\n",
      "start  20500  end  21000 topics:  33 truth:  22  NMI:  0.9258933591238503\n",
      "start  21000  end  21500 topics:  19 truth:  10  NMI:  0.8864484439763445\n",
      "start  21500  end  22000 topics:  21 truth:  10  NMI:  0.8721592079629906\n",
      "start  22000  end  22500 topics:  22 truth:  10  NMI:  0.8788951163418408\n",
      "start  22500  end  23000 topics:  30 truth:  20  NMI:  0.9159286572290315\n",
      "start  23000  end  23500 topics:  20 truth:  12  NMI:  0.89285605171759\n",
      "start  23500  end  24000 topics:  21 truth:  12  NMI:  0.8863104939466819\n",
      "start  24000  end  24500 topics:  23 truth:  11  NMI:  0.8635172203456739\n",
      "start  24500  end  25000 topics:  35 truth:  26  NMI:  0.8872433906897604\n",
      "start  25000  end  25500 topics:  31 truth:  17  NMI:  0.8047278473360366\n",
      "start  25500  end  26000 topics:  31 truth:  18  NMI:  0.8466606456306535\n",
      "start  26000  end  26500 topics:  31 truth:  19  NMI:  0.7956908761013551\n",
      "start  26500  end  27000 topics:  39 truth:  26  NMI:  0.7908289354019211\n",
      "start  27000  end  27500 topics:  38 truth:  18  NMI:  0.7918652318451828\n",
      "start  27500  end  28000 topics:  35 truth:  18  NMI:  0.8237996947481364\n",
      "start  28000  end  28500 topics:  40 truth:  20  NMI:  0.8265739236481314\n",
      "start  28500  end  29000 topics:  30 truth:  8  NMI:  0.6511147538598351\n",
      "start  29000  end  29500 topics:  30 truth:  8  NMI:  0.6538073465596914\n",
      "start  29500  end  30000 topics:  21 truth:  7  NMI:  0.6748867666141182\n",
      "start  30000  end  30322 topics:  19 truth:  7  NMI:  0.7026920684190141\n",
      "dict_keys([0, 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])\n",
      "dict_values([0.880181128846321, 0.8781310441089455, 0.8903626031124846, 0.8802891820550155, 0.8065787161554409, 0.8244414545681393, 0.8427443074941608, 0.8249955372910738, 0.8249857718905035, 0.8373118759546907, 0.8274495385773019, 0.8243009403391134, 0.8392714729131685, 0.8556819033068159, 0.8614101236288397, 0.8850371548645493, 0.8403906752788657, 0.8220668353085563, 0.8744072197265904, 0.8774912503219744, 0.8300296696402276, 0.8334140813293694, 0.8977474954163979, 0.9061124878029874, 0.9262559650343551, 0.9229661598166313, 0.9083133309514114, 0.9053395054295947, 0.8928315213516842, 0.9196137968443262, 0.8876037759344444, 0.9022462055522564, 0.8818799347608985, 0.8917594478084228, 0.9015455645845137, 0.9325381132984558, 0.9295841377350417, 0.9328653390711169, 0.9077193070162694, 0.9306916480786396, 0.9397634573184117, 0.9258933591238503, 0.8864484439763445, 0.8721592079629906, 0.8788951163418408, 0.9159286572290315, 0.89285605171759, 0.8863104939466819, 0.8635172203456739, 0.8872433906897604, 0.8047278473360366, 0.8466606456306535, 0.7956908761013551, 0.7908289354019211, 0.7918652318451828, 0.8237996947481364, 0.8265739236481314, 0.6511147538598351, 0.6538073465596914, 0.6748867666141182, 0.7026920684190141])\n"
     ]
    }
   ],
   "source": [
    "nmi_batch = {}\n",
    "topic_batch = {}\n",
    "start = 0\n",
    "end = 0\n",
    "total_batch = None\n",
    "if len(corpus) % 500 == 0:\n",
    "    total_batch = int(len(corpus) / 500)\n",
    "else:\n",
    "    total_batch = int(len(corpus) / 500) +1\n",
    "\n",
    "for batch in range(total_batch):\n",
    "    docID_assign_z = {}\n",
    "    m_z = {}\n",
    "    n_z = {}\n",
    "    n_w = {}\n",
    "    n_b = {}\n",
    "    Topics = []\n",
    "    V = set()\n",
    "    D = set()\n",
    "    alpha = 0.3\n",
    "    beta = 0.2\n",
    "    end = 500 * (batch + 1)\n",
    "    if end > len(corpus):\n",
    "        end = len(corpus)\n",
    "    nmi_batch[batch] = 0\n",
    "    topic_batch[batch] = 0\n",
    "    \n",
    "    total_iter = 10\n",
    "    for iter in range(total_iter):\n",
    "        for docID in range(start,end):\n",
    "            words = corpus[docID]\n",
    "            D.discard(docID)\n",
    "            if docID in docID_assign_z.keys():\n",
    "                before_k = docID_assign_z[docID]\n",
    "                m_z[before_k].discard(docID)\n",
    "                for biterm in words:\n",
    "                    for word in biterm.split(','):\n",
    "                        n_z[before_k][word] -= 1\n",
    "                        n_w[before_k] -=1\n",
    "            else:\n",
    "                before_k = -1\n",
    "            if len(D) == 0 and len(V) == 0:\n",
    "                choose_k = 0\n",
    "                D.add(docID)\n",
    "                docID_assign_z[docID] = choose_k\n",
    "                if choose_k not in m_z.keys():\n",
    "                    m_z[choose_k] = set()\n",
    "                m_z[choose_k].add(docID)\n",
    "                for biterm in words:\n",
    "                    for word in biterm.split(','):\n",
    "                        if choose_k not in n_w.keys():\n",
    "                            n_w[choose_k] = 0\n",
    "                        if choose_k not in n_z.keys():\n",
    "                            n_z[choose_k] = {}\n",
    "                        if word not in n_z[choose_k].keys():\n",
    "                            n_z[choose_k][word] = 0\n",
    "                        n_z[choose_k][word] += 1\n",
    "                        n_w[choose_k] += 1\n",
    "                        V.add(word)\n",
    "                if choose_k not in Topics:\n",
    "                    Topics.append(choose_k)\n",
    "            else:\n",
    "                log_pro = []\n",
    "                for k in Topics:\n",
    "                    pro_k = len(m_z[k])\n",
    "                    if pro_k != 0:\n",
    "                        i = 0\n",
    "                        for biterm in words:\n",
    "                            each_word = biterm.strip().split(',')\n",
    "                            for word in each_word:\n",
    "                                if word not in n_z[k].keys():\n",
    "                                    n_z[k][word] = 0\n",
    "                            for j in range(doc_biterm[docID][biterm]):\n",
    "                                pro_k *= (n_z[k][each_word[0]] + n_z[k][each_word[-1]] + beta + j) / ( n_w[k] + len(V)*beta + i) \n",
    "                                i += 1\n",
    "\n",
    "                    if pro_k == 0:\n",
    "                        pro_k = sys.float_info.min\n",
    "                    log_pro.append(pro_k)\n",
    "\n",
    "                pro_new_k = alpha*(len(D))\n",
    "                i = 0\n",
    "                for biterm in words:\n",
    "                    for j in range(doc_biterm[docID][biterm]):\n",
    "                        pro_new_k *= ( beta + j) / ( len(V)*beta + i) \n",
    "                        i += 1\n",
    "\n",
    "                if pro_new_k == 0:\n",
    "                    pro_new_k = sys.float_info.min        \n",
    "                log_pro.append(pro_new_k)\n",
    "\n",
    "                sum_pro=sum(log_pro)\n",
    "\n",
    "                normalized_posterior = [i/sum_pro for i in log_pro]    \n",
    "                select_k = None\n",
    "                if iter == (total_iter - 1):\n",
    "                    select_k = normalized_posterior.index(max(normalized_posterior))\n",
    "\n",
    "                else:\n",
    "                    select_k = np.random.choice( (len(Topics)+1) , 1, p=normalized_posterior)[0]  \n",
    "\n",
    "                if select_k == len(Topics):\n",
    "                    choose_k = np.max(Topics) + 1\n",
    "                else:\n",
    "                    choose_k = Topics[select_k]\n",
    "\n",
    "                D.add(docID)\n",
    "                docID_assign_z[docID] = choose_k\n",
    "                if choose_k not in m_z.keys():\n",
    "                    m_z[choose_k] = set()\n",
    "                m_z[choose_k].add(docID)\n",
    "                for biterm in words:\n",
    "                    for word in biterm.split(','):\n",
    "                        if choose_k not in n_w.keys():\n",
    "                            n_w[choose_k] = 0\n",
    "                        if choose_k not in n_z.keys():\n",
    "                            n_z[choose_k] = {}\n",
    "                        if word not in n_z[choose_k].keys():\n",
    "                            n_z[choose_k][word] = 0\n",
    "                        n_z[choose_k][word] += 1\n",
    "                        n_w[choose_k] += 1\n",
    "                        V.add(word)\n",
    "                if choose_k not in Topics:\n",
    "                    Topics.append(choose_k)\n",
    "\n",
    "            count_k = []\n",
    "            for k in Topics:\n",
    "                if k in m_z.keys() and len(m_z[k]) == 0:\n",
    "                    m_z.pop(k, None)\n",
    "                    n_z.pop(k, None)\n",
    "                    n_w.pop(k, None)\n",
    "                    count_k.append(k)\n",
    "            for k in count_k:\n",
    "                Topics.remove(k)   \n",
    "        if iter == 9:\n",
    "            from sklearn.metrics.cluster import normalized_mutual_info_score\n",
    "            nmi_sample = []\n",
    "            nmi_result = []\n",
    "            for key, value in news_labels.items():\n",
    "                if key < end and key >= start:\n",
    "                    nmi_sample.append(value)\n",
    "                    nmi_result.append(docID_assign_z[key])\n",
    "            nmi_batch[batch] = normalized_mutual_info_score(np.array(nmi_sample), np.array(nmi_result))\n",
    "            topic_batch[batch] = len(Topics)\n",
    "            print(\"start \",start, \" end \",end, \"topics: \",len(Topics),\"truth: \",len(np.unique(nmi_sample)), \" NMI: \",normalized_mutual_info_score(np.array(nmi_sample), np.array(nmi_result)))\n",
    "    start = end \n",
    " \n",
    "print(nmi_batch.keys())\n",
    "print(nmi_batch.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "start  0  end  1895 topics:  50 truth:  32  NMI:  0.8809833190237517\n",
      "start  0  end  3790 topics:  68 truth:  62  NMI:  0.8439591343395921\n",
      "start  1896  end  5685 topics:  50 truth:  48  NMI:  0.8411933507485957\n",
      "start  3791  end  7580 topics:  46 truth:  38  NMI:  0.8662774155065565\n",
      "start  5686  end  9475 topics:  65 truth:  44  NMI:  0.861500698458091\n",
      "start  7581  end  11370 topics:  61 truth:  33  NMI:  0.8637970647294302\n",
      "start  9476  end  13265 topics:  47 truth:  23  NMI:  0.9275081042154694\n",
      "start  11371  end  15160 topics:  43 truth:  35  NMI:  0.9296569611245717\n",
      "start  13266  end  17055 topics:  40 truth:  37  NMI:  0.9310156872776246\n",
      "start  15161  end  18950 topics:  31 truth:  31  NMI:  0.9147819104407958\n",
      "start  17056  end  20845 topics:  45 truth:  28  NMI:  0.9205557215382661\n",
      "start  18951  end  22740 topics:  41 truth:  22  NMI:  0.9556500802946675\n",
      "start  20846  end  24635 topics:  28 truth:  21  NMI:  0.9269834155693576\n",
      "start  22741  end  26530 topics:  40 truth:  30  NMI:  0.9162053955295711\n",
      "start  24636  end  28425 topics:  54 truth:  36  NMI:  0.8181493364763252\n",
      "start  26531  end  30322 topics:  44 truth:  25  NMI:  0.7977881339967929\n"
     ]
    }
   ],
   "source": [
    "total_batch = 16\n",
    "NMI_batch = {}\n",
    "start = 0\n",
    "end = 0\n",
    "topic_batch = {}\n",
    "for batch_i in range(1,17):\n",
    "    if batch_i == 16:\n",
    "        end = int(len(corpus))\n",
    "    else:\n",
    "        end = int(len(corpus) / total_batch) * batch_i\n",
    "    \n",
    "    docID_assign_z = {}\n",
    "    m_z = {}\n",
    "    n_z = {}\n",
    "    n_w = {}\n",
    "    n_b = {}\n",
    "    Topics = []\n",
    "    V = set()\n",
    "    D = set()\n",
    "    alpha = 0.3\n",
    "    beta = 0.3\n",
    "    NMI_batch[batch_i] = 0\n",
    "    topic_batch[batch_i] = 0\n",
    "    \n",
    "    total_iter = 10\n",
    "    for iter in range(total_iter):\n",
    "        for docID in range(start,end):\n",
    "            words = corpus[docID]\n",
    "            D.discard(docID)\n",
    "            if docID in docID_assign_z.keys():\n",
    "                before_k = docID_assign_z[docID]\n",
    "                m_z[before_k].discard(docID)\n",
    "                for biterm in words:\n",
    "                    for word in biterm.split(','):\n",
    "                        n_z[before_k][word] -= 1\n",
    "                        n_w[before_k] -=1\n",
    "            else:\n",
    "                before_k = -1\n",
    "            if len(D) == 0 and len(V) == 0:\n",
    "                choose_k = 0\n",
    "                D.add(docID)\n",
    "                docID_assign_z[docID] = choose_k\n",
    "                if choose_k not in m_z.keys():\n",
    "                    m_z[choose_k] = set()\n",
    "                m_z[choose_k].add(docID)\n",
    "                for biterm in words:\n",
    "                    for word in biterm.split(','):\n",
    "                        if choose_k not in n_w.keys():\n",
    "                            n_w[choose_k] = 0\n",
    "                        if choose_k not in n_z.keys():\n",
    "                            n_z[choose_k] = {}\n",
    "                        if word not in n_z[choose_k].keys():\n",
    "                            n_z[choose_k][word] = 0\n",
    "                        n_z[choose_k][word] += 1\n",
    "                        n_w[choose_k] += 1\n",
    "                        V.add(word)\n",
    "                if choose_k not in Topics:\n",
    "                    Topics.append(choose_k)\n",
    "            else:\n",
    "                log_pro = []\n",
    "                for k in Topics:\n",
    "                    pro_k = len(m_z[k])\n",
    "                    if pro_k != 0:\n",
    "                        i = 0\n",
    "                        for biterm in words:\n",
    "                            each_word = biterm.strip().split(',')\n",
    "                            for word in each_word:\n",
    "                                if word not in n_z[k].keys():\n",
    "                                    n_z[k][word] = 0\n",
    "                            for j in range(doc_biterm[docID][biterm]):\n",
    "                                pro_k *= (n_z[k][each_word[0]] + n_z[k][each_word[-1]] + beta + j) / ( n_w[k] + len(V)*beta + i) \n",
    "                                i += 1\n",
    "\n",
    "                    if pro_k == 0:\n",
    "                        pro_k = sys.float_info.min\n",
    "                    log_pro.append(pro_k)\n",
    "\n",
    "                pro_new_k = alpha*(len(D))\n",
    "                i = 0\n",
    "                for biterm in words:\n",
    "                    for j in range(doc_biterm[docID][biterm]):\n",
    "                        pro_new_k *= ( beta + j) / ( len(V)*beta + i) \n",
    "                        i += 1\n",
    "\n",
    "                if pro_new_k == 0:\n",
    "                    pro_new_k = sys.float_info.min        \n",
    "                log_pro.append(pro_new_k)\n",
    "\n",
    "                sum_pro=sum(log_pro)\n",
    "\n",
    "                normalized_posterior = [i/sum_pro for i in log_pro]    \n",
    "                select_k = None\n",
    "                if iter == (total_iter - 1):\n",
    "                    select_k = normalized_posterior.index(max(normalized_posterior))\n",
    "\n",
    "                else:\n",
    "                    select_k = np.random.choice( (len(Topics)+1) , 1, p=normalized_posterior)[0]  \n",
    "\n",
    "                if select_k == len(Topics):\n",
    "                    choose_k = np.max(Topics) + 1\n",
    "                else:\n",
    "                    choose_k = Topics[select_k]\n",
    "\n",
    "                D.add(docID)\n",
    "                docID_assign_z[docID] = choose_k\n",
    "                if choose_k not in m_z.keys():\n",
    "                    m_z[choose_k] = set()\n",
    "                m_z[choose_k].add(docID)\n",
    "                for biterm in words:\n",
    "                    for word in biterm.split(','):\n",
    "                        if choose_k not in n_w.keys():\n",
    "                            n_w[choose_k] = 0\n",
    "                        if choose_k not in n_z.keys():\n",
    "                            n_z[choose_k] = {}\n",
    "                        if word not in n_z[choose_k].keys():\n",
    "                            n_z[choose_k][word] = 0\n",
    "                        n_z[choose_k][word] += 1\n",
    "                        n_w[choose_k] += 1\n",
    "                        V.add(word)\n",
    "                if choose_k not in Topics:\n",
    "                    Topics.append(choose_k)\n",
    "\n",
    "            count_k = []\n",
    "            for k in Topics:\n",
    "                if k in m_z.keys() and len(m_z[k]) == 0:\n",
    "                    m_z.pop(k, None)\n",
    "                    n_z.pop(k, None)\n",
    "                    n_w.pop(k, None)\n",
    "                    count_k.append(k)\n",
    "            for k in count_k:\n",
    "                Topics.remove(k)   \n",
    "        if iter == 9:\n",
    "            from sklearn.metrics.cluster import normalized_mutual_info_score\n",
    "            nmi_sample = []\n",
    "            nmi_result = []\n",
    "            for key, value in news_labels.items():\n",
    "                if key < end and key >= start:\n",
    "                    nmi_sample.append(value)\n",
    "                    nmi_result.append(docID_assign_z[key])\n",
    "            NMI_batch[batch_i] = normalized_mutual_info_score(np.array(nmi_sample), np.array(nmi_result))\n",
    "            topic_batch[batch_i] = len(Topics)\n",
    "            print(\"start \",start, \" end \",end, \"topics: \",len(Topics),\"truth: \",len(np.unique(nmi_sample)), \" NMI: \",normalized_mutual_info_score(np.array(nmi_sample), np.array(nmi_result)))\n",
    "    if batch_i != 1:\n",
    "        start = int(len(corpus) / total_batch) * (batch_i -1) + 1\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]\n",
      "\n",
      "[0.8809833190237517, 0.8439591343395921, 0.8411933507485957, 0.8662774155065565, 0.861500698458091, 0.8637970647294302, 0.9275081042154694, 0.9296569611245717, 0.9310156872776246, 0.9147819104407958, 0.9205557215382661, 0.9556500802946675, 0.9269834155693576, 0.9162053955295711, 0.8181493364763252, 0.7977881339967929]\n",
      "0.8872503580793412\n"
     ]
    }
   ],
   "source": [
    "common_keys = []\n",
    "\n",
    "item_NMI = []\n",
    "for key,value in sorted(NMI_batch.items(), key=lambda x: x[0]):\n",
    "    common_keys.append(key)\n",
    "    item_NMI.append(value)\n",
    "print(common_keys)\n",
    "\n",
    "print()\n",
    "\n",
    "print(item_NMI)\n",
    "print(np.mean(item_NMI))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]\n",
      "\n",
      "[0.8776164167985246, 0.8364336026215384, 0.8427075406409203, 0.8633197450712946, 0.8445904054720953, 0.8744979689512565, 0.9231958326975366, 0.9177916950253654, 0.9323616880042681, 0.9277386915588987, 0.9378230070071573, 0.9469150565186208, 0.9204913463472311, 0.9038963198811201, 0.8096090638413559, 0.7857563666730738]\n",
      "0.8840465466943912\n"
     ]
    }
   ],
   "source": [
    "common_keys = []\n",
    "\n",
    "item_NMI = []\n",
    "for key,value in sorted(NMI_batch.items(), key=lambda x: x[0]):\n",
    "    common_keys.append(key)\n",
    "    item_NMI.append(value)\n",
    "print(common_keys)\n",
    "\n",
    "print()\n",
    "\n",
    "print(item_NMI)\n",
    "print(np.mean(item_NMI))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "alpha  0.1  NMI:  0.8453845540783476\n",
      "alpha  0.1  Topics:  81\n",
      "alpha  0.2  NMI:  0.8486100535419043\n",
      "alpha  0.2  Topics:  87\n",
      "alpha  0.3  NMI:  0.84942774143682\n",
      "alpha  0.3  Topics:  89\n",
      "alpha  0.4  NMI:  0.8474128102136836\n",
      "alpha  0.4  Topics:  91\n",
      "alpha  0.5  NMI:  0.8460112095273967\n",
      "alpha  0.5  Topics:  95\n",
      "alpha  0.6  NMI:  0.8447677521639362\n",
      "alpha  0.6  Topics:  94\n",
      "alpha  0.7  NMI:  0.8489684822857698\n",
      "alpha  0.7  Topics:  97\n",
      "alpha  0.8  NMI:  0.8485642574705066\n",
      "alpha  0.8  Topics:  98\n",
      "alpha  0.9  NMI:  0.8441177310998838\n",
      "alpha  0.9  Topics:  99\n",
      "alpha  1.0  NMI:  0.8439768970506967\n",
      "alpha  1.0  Topics:  101\n"
     ]
    }
   ],
   "source": [
    "alpha_NMI = {}\n",
    "alpha_topics = {}\n",
    "for alpha in np.arange(0.1,1.1,0.1):\n",
    "    alpha = np.around(alpha,decimals=1)\n",
    "    \n",
    "    total_batch = 16\n",
    "    NMI_batch = {}\n",
    "    start = 0\n",
    "    end = 0\n",
    "    topic_batch = {}\n",
    "    time_iteration_list = []\n",
    "    for batch_i in range(1,17):\n",
    "        if batch_i == 16:\n",
    "            end = int(len(corpus))\n",
    "        else:\n",
    "            end = int(len(corpus) / total_batch) * batch_i\n",
    "\n",
    "        docID_assign_z = {}\n",
    "        m_z = {}\n",
    "        n_z = {}\n",
    "        n_w = {}\n",
    "        n_b = {}\n",
    "        Topics = []\n",
    "        V = set()\n",
    "        D = set()\n",
    "        #alpha = 0.6\n",
    "        beta = 0.02\n",
    "        NMI_batch[batch_i] = 0\n",
    "        topic_batch[batch_i] = 0\n",
    "\n",
    "        time_start = timeit.default_timer()\n",
    "        total_iter = 10\n",
    "        for iter in range(total_iter):\n",
    "            for docID in range(start,end):\n",
    "                words = corpus[docID]\n",
    "                D.discard(docID)\n",
    "                if docID in docID_assign_z.keys():\n",
    "                    before_k = docID_assign_z[docID]\n",
    "                    m_z[before_k].discard(docID)\n",
    "                    for biterm in words:\n",
    "                        for word in biterm.split(','):\n",
    "                            n_z[before_k][word] -= 1\n",
    "                            n_w[before_k] -=1\n",
    "                else:\n",
    "                    before_k = -1\n",
    "                if len(D) == 0 and len(V) == 0:\n",
    "                    choose_k = 0\n",
    "                    D.add(docID)\n",
    "                    docID_assign_z[docID] = choose_k\n",
    "                    if choose_k not in m_z.keys():\n",
    "                        m_z[choose_k] = set()\n",
    "                    m_z[choose_k].add(docID)\n",
    "                    for biterm in words:\n",
    "                        for word in biterm.split(','):\n",
    "                            if choose_k not in n_w.keys():\n",
    "                                n_w[choose_k] = 0\n",
    "                            if choose_k not in n_z.keys():\n",
    "                                n_z[choose_k] = {}\n",
    "                            if word not in n_z[choose_k].keys():\n",
    "                                n_z[choose_k][word] = 0\n",
    "                            n_z[choose_k][word] += 1\n",
    "                            n_w[choose_k] += 1\n",
    "                            V.add(word)\n",
    "                    if choose_k not in Topics:\n",
    "                        Topics.append(choose_k)\n",
    "                else:\n",
    "                    log_pro = []\n",
    "                    for k in Topics:\n",
    "                        pro_k = len(m_z[k])\n",
    "                        if pro_k != 0:\n",
    "                            i = 0\n",
    "                            for biterm in words:\n",
    "                                each_word = biterm.strip().split(',')\n",
    "                                for word in each_word:\n",
    "                                    if word not in n_z[k].keys():\n",
    "                                        n_z[k][word] = 0\n",
    "                                for j in range(doc_biterm[docID][biterm]):\n",
    "                                    pro_k *= (n_z[k][each_word[0]] + n_z[k][each_word[-1]] + beta + j) / ( n_w[k] + len(V)*beta + i) \n",
    "                                    i += 1\n",
    "\n",
    "                        if pro_k == 0:\n",
    "                            pro_k = sys.float_info.min\n",
    "                        log_pro.append(pro_k)\n",
    "\n",
    "                    pro_new_k = alpha*(len(D))\n",
    "                    i = 0\n",
    "                    for biterm in words:\n",
    "                        for j in range(doc_biterm[docID][biterm]):\n",
    "                            pro_new_k *= ( beta + j) / ( len(V)*beta + i) \n",
    "                            i += 1\n",
    "\n",
    "                    if pro_new_k == 0:\n",
    "                        pro_new_k = sys.float_info.min        \n",
    "                    log_pro.append(pro_new_k)\n",
    "\n",
    "                    sum_pro=sum(log_pro)\n",
    "\n",
    "                    normalized_posterior = [i/sum_pro for i in log_pro]    \n",
    "                    select_k = None\n",
    "                    if iter == (total_iter - 1):\n",
    "                        select_k = normalized_posterior.index(max(normalized_posterior))\n",
    "\n",
    "                    else:\n",
    "                        select_k = np.random.choice( (len(Topics)+1) , 1, p=normalized_posterior)[0]  \n",
    "\n",
    "                    if select_k == len(Topics):\n",
    "                        choose_k = np.max(Topics) + 1\n",
    "                    else:\n",
    "                        choose_k = Topics[select_k]\n",
    "\n",
    "                    D.add(docID)\n",
    "                    docID_assign_z[docID] = choose_k\n",
    "                    if choose_k not in m_z.keys():\n",
    "                        m_z[choose_k] = set()\n",
    "                    m_z[choose_k].add(docID)\n",
    "                    for biterm in words:\n",
    "                        for word in biterm.split(','):\n",
    "                            if choose_k not in n_w.keys():\n",
    "                                n_w[choose_k] = 0\n",
    "                            if choose_k not in n_z.keys():\n",
    "                                n_z[choose_k] = {}\n",
    "                            if word not in n_z[choose_k].keys():\n",
    "                                n_z[choose_k][word] = 0\n",
    "                            n_z[choose_k][word] += 1\n",
    "                            n_w[choose_k] += 1\n",
    "                            V.add(word)\n",
    "                    if choose_k not in Topics:\n",
    "                        Topics.append(choose_k)\n",
    "\n",
    "                count_k = []\n",
    "                for k in Topics:\n",
    "                    if k in m_z.keys() and len(m_z[k]) == 0:\n",
    "                        m_z.pop(k, None)\n",
    "                        n_z.pop(k, None)\n",
    "                        n_w.pop(k, None)\n",
    "                        count_k.append(k)\n",
    "                for k in count_k:\n",
    "                    Topics.remove(k)   \n",
    "            if iter == 9:\n",
    "                from sklearn.metrics.cluster import normalized_mutual_info_score\n",
    "                nmi_sample = []\n",
    "                nmi_result = []\n",
    "                for key, value in news_labels.items():\n",
    "                    if key < end and key >= start:\n",
    "                        nmi_sample.append(value)\n",
    "                        nmi_result.append(docID_assign_z[key])\n",
    "                NMI_batch[batch_i] = normalized_mutual_info_score(np.array(nmi_sample), np.array(nmi_result))\n",
    "                topic_batch[batch_i] = len(Topics)\n",
    "                #print(\"start \",start, \" end \",end, \"topics: \",len(Topics),\"truth: \",len(np.unique(nmi_sample)), \" NMI: \",normalized_mutual_info_score(np.array(nmi_sample), np.array(nmi_result)))\n",
    "        if batch_i != 1:\n",
    "            start = int(len(corpus) / total_batch) * (batch_i -1) + 1\n",
    "    \n",
    "    alpha_NMI[alpha] = np.mean(list(NMI_batch.values()))\n",
    "    alpha_topics[alpha] = int(np.mean(list(topic_batch.values())))\n",
    "    print(\"alpha \",alpha, \" NMI: \", alpha_NMI[alpha])\n",
    "    print(\"alpha \",alpha, \" Topics: \", alpha_topics[alpha])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dict_values([0.8453845540783476, 0.8486100535419043, 0.84942774143682, 0.8474128102136836, 0.8460112095273967, 0.8447677521639362, 0.8489684822857698, 0.8485642574705066, 0.8441177310998838, 0.8439768970506967])\n",
      "dict_values([81, 87, 89, 91, 95, 94, 97, 98, 99, 101])\n"
     ]
    }
   ],
   "source": [
    "print(alpha_NMI.values())\n",
    "print(alpha_topics.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}