<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Katerina Fomkina on Medium]]></title>
        <description><![CDATA[Stories by Katerina Fomkina on Medium]]></description>
        <link>https://medium.com/@katerinafomkina?source=rss-f21d4b5ea3f3------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*guJWWrICbM-ZXn9fb1WXXg@2x.jpeg</url>
            <title>Stories by Katerina Fomkina on Medium</title>
            <link>https://medium.com/@katerinafomkina?source=rss-f21d4b5ea3f3------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 20:14:31 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@katerinafomkina/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Decision Tree Overfitting Issue]]></title>
            <link>https://medium.com/@katerinafomkina/decision-tree-overfitting-issue-dd839214e47d?source=rss-f21d4b5ea3f3------2</link>
            <guid isPermaLink="false">https://medium.com/p/dd839214e47d</guid>
            <category><![CDATA[early-stopping]]></category>
            <category><![CDATA[post-pruning]]></category>
            <category><![CDATA[overfitting-underfitting]]></category>
            <category><![CDATA[decision-tree]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Katerina Fomkina]]></dc:creator>
            <pubDate>Thu, 02 Feb 2023 09:30:40 GMT</pubDate>
            <atom:updated>2023-02-02T09:30:40.725Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*rofKjw3s-5f1cZOc.jpg" /></figure><p>Decision trees are prone to overfitting. It affected how well the model performed. Pruning reduces the size of DT by removing redundant sections. It helps to reduce the complexity and avoid overfitting.</p><blockquote>There are two types of pruning:</blockquote><blockquote>‣ Pre-pruning or early stoping technique;</blockquote><blockquote>‣ Post pruning technique.</blockquote><h3><strong>Pre-pruning</strong></h3><p>The technique uses a criterion to stop the growth of a decision tree at an early stage. Pre-pruning can be done by adjusting the following hyperparameters in the Scikit-learn libraries.</p><p>‣ <strong>max_depth </strong>criterion specifies the maximum depth of a tree.</p><p>‣ <strong>min_samples_leaf </strong>criterion indicates the minimum number of samples required to be at a leaf node.</p><p>‣ <strong>min_samples_split </strong>criterion determines the minimum number of samples required to split an internal node.</p><p>This technique has a big issue called the <strong>Horizon Effect. <em>It is not easy to find the best option for stopping a tree algorithm.</em></strong></p><h3>Post pruning</h3><p>It is a process of deleting the unnecessary nodes from DT in order to get the optimal structure. Two main techniques are <em>bottom-up pruning</em> and <em>top-down pruning.</em></p><h4><strong><em>Bottom-up pruning.</em></strong></h4><p>The method establishes the relevance of each individual node in the tree by starting at the last node and moving upward recursively. The procedure drops the node or replaces it with a leaf. This method&#39;s benefit is that no important sub-trees can be lost. Examples of this technique are: Reduced Error pruning and Cost Complexity pruning.</p><ol><li><strong>Reduced Error Pruning (REP)</strong></li></ol><p>It is one of the simplest strategies, but it is considered too aggressive. REP requires a separate set of examples, not to build the DT but only to check the error. REP is starting at the leaves and replacing a node with its most popular class. Keep the change if it has no effect on prediction accuracy.</p><pre>Algorithm of REP<br><br>if error(parent)&lt;error(child):<br>  prune<br>else:<br>  do not prune</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*aXXyiOrzo1G-vsqw-Ex-tQ.png" /></figure><p>2. <strong>Cost Complexity Pruning (CCP)</strong></p><p>This technique controls the DT size by using a complexity parameter.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/504/0*KscIHtdzFCmX4w0U" /></figure><blockquote>Rule: For any two terminal nodes descended from the same parent, if they yield the same re-substitution error rate as the parent node, prune off these two terminal nodes. The process is applied recursively.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MeBFTBYwtnHl0iTRYhDFaQ.png" /></figure><p>The strategic goal is to find the best tree with the minimum cost-complexity function by choosing the regularization parameter using cross-validation.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/720/1*GgueEcAzllqlAaNKnf-KlA.png" /></figure><h4>Top-down pruning.</h4><p>The method starts at the root of the tree. A relevance check is performed to determine whether or not a node is relevant among all n items. Pessimistic Error pruning (PEP), which achieves excellent results with hidden items, is one of these representatives.</p><p><strong>Pessimistic Error Pruning (PEP)</strong></p><p>The strategic idea is to observe everything, anticipate the worst-case scenario, and avoid it. PEP avoids the need to use a validation set for training. It prunes the nodes unless the estimation errors of the subtree are more than 1 standard error below the estimation for the pruned tree.</p><blockquote>Algorithm:</blockquote><blockquote>1. Start from the root.</blockquote><blockquote>2. Remove the left node. If percent of error increases, mark it as “don’t cut”, otherwise mark it as “cut”.</blockquote><blockquote>3. Remove the right node. If percent of error increases, mark it as “don’t cut”, otherwise mark it as “cut”.</blockquote><blockquote>4. Repeat 2–3 steps until having the smallest possible tree using this approach.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/301/0*x4lIj9hRrBW9jaCB" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/731/1*ZlhDrGzBo5RV1sAgF9WL6Q.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/394/0*wujbwfWq7f_N4RD7" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/916/1*PusNcdTZmFBzwjHR9KtcrA.png" /></figure><p>Overfitting is a crucial problem in DT. To improve the performance of the model, always use post- or pre-pruning techniques, or instead of DT, use Random Forest, because it controls the problem of overfitting.</p><p>Thank you for reading!</p><p>.</p><p>.</p><p>.</p><p>☼☽✨</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dd839214e47d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Decision Trees. Attribute Selection Measure Guide]]></title>
            <link>https://medium.com/@katerinafomkina/decision-trees-attribute-selection-measure-guide-af391681913f?source=rss-f21d4b5ea3f3------2</link>
            <guid isPermaLink="false">https://medium.com/p/af391681913f</guid>
            <category><![CDATA[supervised-learning]]></category>
            <category><![CDATA[decision-tree-regressor]]></category>
            <category><![CDATA[decision-tree-classifier]]></category>
            <category><![CDATA[decision-tree]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Katerina Fomkina]]></dc:creator>
            <pubDate>Mon, 23 Jan 2023 18:57:03 GMT</pubDate>
            <atom:updated>2023-01-23T18:57:03.343Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*nQPp9fMK9fy1YQN2" /><figcaption>Photo by <a href="https://unsplash.com/@fabulu75?utm_source=medium&amp;utm_medium=referral">Fabrice Villard</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>Decision Tree is a non-parametric supervised learning algorithm that can be used for both classification and regression. Internal nodes represent a dataset, branches represent the decision rules, and leaves represent the outcomes in this tree-structured technique.</p><blockquote>Algorithm:</blockquote><blockquote>1. The root is the entire training set.</blockquote><blockquote>2. The values of the root attribute are compared with the dataset. Based on comparison, it follows the branch and jumps to the next node.</blockquote><blockquote>3. For the next node it again compares the attribute value with the other sub-nodes and move further.</blockquote><blockquote>3. Repeat step 3 until it reaches the leaf node, i.e. a pure class.</blockquote><blockquote><strong>Types of DT :</strong></blockquote><blockquote>‣ <strong>Decision Tree Classifier ( categorical target variable )</strong></blockquote><blockquote>‣ <strong>Decision Tree Regressor ( continuous target variable )</strong></blockquote><h4>1. Decision Tree Classifier</h4><p>This type of DT works with a categorical target variable.</p><p>Attribute Selection Measures:</p><p>‣ Entropy</p><p>‣ Information Gain</p><p>‣ Gini Index</p><p>‣ Gain Ratio</p><p><strong>1.1 Entropy</strong></p><p>Entropy measures the impurity of the sample values. If all samples in S belong to one class, then <strong><em>Entropy is zero</em></strong>. This is the best-case scenario; it denotes purity. If half of the samples are classified in one class and the other half are in another class, <strong><em>Entropy is one</em></strong>. This scenario is the worst. <strong><em>The attribute with the smallest entropy should be used as the best feature to split on. </em></strong>It can be stated that Entropy measures the priority of the split.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/262/1*R4BvBVCngPiZA4ivqiHwWA.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/277/1*yp-hr-DwCjfGKNyox1gt7g.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/798/1*pVbxRl6gKSW2kVeohDa_Gg.png" /></figure><p><strong>1.2 Information Gain IG</strong></p><p>Information Gain measures how well a given attribute separates the training examples according to their target classification. It combines all Entropies. <strong><em>The structure with the biggest IG should be chosen for the split.</em></strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/305/1*fX_7eeGwSHsXcIvTDms-jA.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Rff3FYofOKRPIzVHwh9-GQ.png" /></figure><p><strong>1.3 Gini Index</strong></p><p>The Gini Index, also known as Impurity, calculates the likelihood that a randomly selected instance will be incorrectly classified. Gini is computationally efficient. <strong><em>The attribute with the smallest Gini should be used as the best feature to split on.</em></strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/265/1*mfChZ6wSarN3J_JHYBZv9A.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/277/1*IeEEcOdVfKQD6mWDFs5V-w.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/563/1*U-ggrB1Rr8-CjHg3OJDEYQ.png" /></figure><p><strong>1.4 Gain Ratio</strong></p><p>The problem with information gain is that it increases the number of nodes and makes the model more susceptible to overfitting.</p><p>The gain ratio attempts to lessen the bias of information gain on highly branched predictors. It uses normalizing information called intrinsic information. <strong><em>The structure with the biggest GR should be chosen for the split.</em></strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/202/1*sDMquyAW1IQAzbgQgc34Fw.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/194/1*HnqUOpDkq0U2SNmtI33dAA.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/789/1*KlwnxJnqnR7VqP43B0bB4g.png" /></figure><blockquote><strong>In practice the performances of split measurements are quite similar, but Gini Index is more computational efficient.</strong></blockquote><h4>2. Decision Tree Regressor</h4><p>This type of DT works with a continuous target variable.</p><p><strong>2.1 Variance Reduction</strong></p><p>Variance is used for calculating the homogeneity of a node. If a node is entirely homogeneous, then the variance is zero. The lower Variance the better. The best Variance Reduction can decrease the impurity much more than others.</p><blockquote>Algoritm:</blockquote><blockquote>1. Sort X-values in ascending order</blockquote><blockquote>2. Compute the mean of all y and Variance</blockquote><blockquote>3. Take 2 points each time to find their average value, i.e. this value is the splitting point.</blockquote><blockquote>4. Compute mean and variance of each child node.</blockquote><blockquote>5. Compute Variance Reduction for every splitting point, using its child Variance.</blockquote><blockquote>6. Repeat 3–5 steps for every splitting point.</blockquote><blockquote>7. Take the best Variance Reduction.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/550/1*OKRAba7PxKFtLezxZOxy1g.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MMkGo_0QUFrWCdIl55chhQ.png" /><figcaption>Here I computed only first split X[0]≤3.5</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*NjFtg94Rr4zyLmvkx9pybQ.png" /><figcaption>Full Decision Tree</figcaption></figure><p>Criterion in sklearn.tree.<strong>DecisionTreeRegressor</strong></p><p>‣ ‘squared_error’ is equal to Variance Reduction;</p><p>‣ ‘absolute_error’ calculates using MAE;</p><p>‣ ‘friedman_mse’ uses MSE with Friedman’s improvement score for potential splits;</p><p>‣ ‘poisson’ uses reduction in Poisson deviance.</p><p>What measure is to be used only experiments can show.</p><p>P.S. MSE is more efficient to compute.</p><p>.</p><p>.</p><p>.</p><p>☼☽✨</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=af391681913f" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Let me tell you about Logistic Regression]]></title>
            <link>https://medium.com/@katerinafomkina/let-me-tell-you-about-logistic-regression-7497d9fb3858?source=rss-f21d4b5ea3f3------2</link>
            <guid isPermaLink="false">https://medium.com/p/7497d9fb3858</guid>
            <category><![CDATA[gradient-descent]]></category>
            <category><![CDATA[maximum-likelihood]]></category>
            <category><![CDATA[supervised-learning]]></category>
            <category><![CDATA[logistic-regression]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Katerina Fomkina]]></dc:creator>
            <pubDate>Sun, 15 Jan 2023 15:40:34 GMT</pubDate>
            <atom:updated>2023-01-15T15:40:34.643Z</atom:updated>
            <content:encoded><![CDATA[<h3><strong>Let me tell you about</strong> Logistic Regression.</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/442/0*JxzXc2aNabZAu_BT" /></figure><h4>Fundamentals</h4><p>Logistic regression is a classification method that provides probabilities and classifies new data using continuous and discrete datasets.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/365/1*jyQDG-AyB_PJavdW78jSGQ.gif" /></figure><p>The function that helps map predicted values to probabilities is the sigmoid function, which refers to an S-shaped curve. It maps any real value into another in the [0, 1] range.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/133/1*PnkSad1mES6jnES62qPICw.gif" /></figure><h4>The Maximum Likelihood Estimation (MLE)</h4><p>MLE is a method of estimating the parameters of the LogReg model by taking the partial derivative of the log-likelihood function that we use to find the best fitting line.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/251/1*Xvv_dXDppXLR4d95219Kgg.gif" /></figure><p>The goal is to find the value that maximizes the log-likelihood function, i.e., we want to maximize the total probability of the data. The maximization problem does not necessarily have a solution because there may be situations in which the log-probability is an unbounded function of the parameters. In this case, we use the gradient descent algorithm.</p><h4>Gradient Descent Algorithm</h4><p>The gradient descent algorithm is commonly used in LogReg and helps minimize the cost function. The idea behind gradient descent is that if you continuously take small steps in the opposite direction of your gradient, you will eventually make it to a local minima.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/415/1*KjdzsVtQYU2mijXDH4SWIw.gif" /></figure><blockquote><strong><em>GD is the most effective approach to solve a given problem after MLE provides the likelihood function. You must use gradient ascent, or take the log-likelihood function&#39;s opposite and continuously move a bit in the gradient direction, to reach local maxima.</em></strong></blockquote><h4>Key assumptions for Logistic Regression</h4><ol><li>The dependent variable is binary.</li><li>Little or no multicollinearity between independent variables.</li><li>Linear relationship between independent variables and log odds.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/246/1*KAU0Ord58S2fdeVM7FKJdw.gif" /></figure><p>4. Logistic regression prefers large sample size.</p><p>5. There are no extreme outliers in the dataset.</p><p>.</p><p>.</p><p>To be continued…</p><p>☼☽✨</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7497d9fb3858" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[SQL interesting problems from HackerRank. Part I]]></title>
            <link>https://medium.com/@katerinafomkina/sql-interesting-tasks-from-hackerrank-part-i-a588d1d96d61?source=rss-f21d4b5ea3f3------2</link>
            <guid isPermaLink="false">https://medium.com/p/a588d1d96d61</guid>
            <category><![CDATA[hackerrank]]></category>
            <category><![CDATA[sqlalchemy]]></category>
            <category><![CDATA[sql]]></category>
            <category><![CDATA[topcoder]]></category>
            <category><![CDATA[sql-queries]]></category>
            <dc:creator><![CDATA[Katerina Fomkina]]></dc:creator>
            <pubDate>Wed, 07 Dec 2022 08:32:11 GMT</pubDate>
            <atom:updated>2022-12-07T08:35:21.868Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/753/0*EzyOdwua5urxvWSU" /></figure><h4><strong>This problem from</strong> <a href="https://www.hackerrank.com/challenges/full-score/problem"><strong>HackerRank</strong></a></h4><p>Julia just finished conducting a coding contest, and she needs your help assembling the leaderboard! Write a query to print the respective hacker_id and name of hackers who achieved full scores for more than one challenge. Order your output in descending order by the total number of challenges in which the hacker earned a full score. If more than one hacker received full scores in same number of challenges, then sort them by ascending hacker_id.</p><h4><strong>Logic:</strong></h4><blockquote>Use JOINS</blockquote><p>→ First, let’s check the output. It looks like: <em>hacker_id, name</em>.</p><pre>select h.hacker_id, h.name</pre><p>→ Select table <strong>Submissions.</strong> It has four rows (<em>submission_id, hacker_id, challenge_id, score</em>(submission score)).</p><pre><br>from submissions as s</pre><p>→ Join <strong>Hackers</strong> table on <em>hacker_id</em>, because we need names.</p><pre>join hackers as h on s.hacker_id = h.hacker_id</pre><p>→ Join <strong>Challenges</strong> on <em>challenge_id</em>. It gives a difficulty_level.</p><pre>join challenges as ch on ch.challenge_id = s.challenge_id</pre><p>→ Join <strong>Difficulty </strong>on <em>difficulty_level</em>. Now we know the full score of each difficulty level.</p><pre>join difficulty as d on ch.difficulty_level = d.difficulty_level</pre><p>→ Check whether submission score is a full score.</p><pre>where s.score = d.score</pre><p>→ Group by hacker ID and name.</p><pre>group by h.hacker_id, h.name</pre><p>→ Calculate how many full scores each hacker got.</p><pre>having count(*) &gt; 1</pre><p>→ Sort by amount of full scores in descending order and by hacker ID in ascending order.</p><pre>order by count(*) desc, h.hacker_id asc</pre><h4>Solution:</h4><pre>select h.hacker_id, h.name <br>from submissions as s <br>join hackers as h on s.hacker_id = h.hacker_id <br>join challenges as ch on ch.challenge_id = s.challenge_id<br>join difficulty as d on ch.difficulty_level = d.difficulty_level<br>where s.score = d.score <br>group by h.hacker_id, h.name<br>having count(*) &gt; 1<br>order by count(*) desc, h.hacker_id asc;<br><br></pre><p>Happy coding!</p><p>☼☽✨</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a588d1d96d61" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Encoding Categorical features with high cardinality]]></title>
            <link>https://medium.com/@katerinafomkina/encoding-categorical-features-with-high-cardinality-fdb514a7eb87?source=rss-f21d4b5ea3f3------2</link>
            <guid isPermaLink="false">https://medium.com/p/fdb514a7eb87</guid>
            <category><![CDATA[hashing-algorithm]]></category>
            <category><![CDATA[feature-engineering]]></category>
            <category><![CDATA[eda]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[encoder]]></category>
            <dc:creator><![CDATA[Katerina Fomkina]]></dc:creator>
            <pubDate>Thu, 25 Aug 2022 12:50:56 GMT</pubDate>
            <atom:updated>2022-08-25T12:50:56.443Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/600/0*tzELYHq2_PV740cy.jpeg" /></figure><p>Most ML models accept only numerical values as input and do not work with categorical features, thus we need to transform categorical features into numbers to use them in the model.</p><p>The performance of ML algorithms is based on how categorical features are encoded. There are many types of encoders that can help us, but not all of them can handle features with high cardinality.</p><h4>Binning</h4><p>Having too many categories can lead to problems when training and testing the model, i.e. the curse of dimensionality or model have no idea how to handle the unseen category. One way to solve these issues is by engineering new features that have fewer categories, i.e. this can be achieved by combining several categories into one category.</p><p>It’s all about binning. We pick top data points(either categorizing similar values through some analysis or by sorting ) in the feature and place the others in the “Others” category or just drop them due to insignificance. After reduction of dimensionality we can use OHE, if the number of bins is not too big, because this can lead to highly sparse dataset.</p><p>➕ Binning categorical data reduces cardinality and the amount of columns created during encoding thus we have less chance of overfitting</p><p>➖ We can lose information or create wrong bins of data, which can lead to bad consequences.</p><h4>Hash Encoding</h4><p>The idea of the encoder is to convert data into a vector of features using hash function, which takes a string and returns a number between 0 and n-1.</p><p>Specifically, feature hashing maps each category in a feature to an integer within a predetermined range. Even if we have over 1000 distinct categories in a feature and we set 8 as the final feature vector size, the output feature set will still have only 8 features.</p><p>➕ The hash encoder does not maintain a dictionary of observed categories.</p><p>➕ The encoder does not grow in size and accepts new values during data scoring by design.</p><p>➖ Collisions, the encoder can hash different keys to the same integer value. Thus, in this method we have a trade-off between number of categories getting map to the same integer value (% of collisions) and the final feature vector size (n-components).</p><p>➖ Hash encoder is slow compared to other encoders.</p><h4>Target Encoding</h4><p>In this method each category is encoded given the effect it has on the target variable y. The encoder considers that a categorical variable may contain rare categories and, in addition, it takes an empirical Bayes approach to shrink the estimate.</p><p>➕ This method is really easy and powerful.</p><p>➕ Encoder picks up values that can explain the target.</p><p>➖ Using the mean as a predictor for the entire distribution is not as good, because we train models on a portion of the data and the mean of that portion is not necessarily be the mean of the entire population.</p><p>➖ Huge disadvantage — target leakage. The model will learn from a variable that itself contains a target, and this can lead to overfitting. There are various ways to handle this: increase regularization, add random noice to the category in train dataset, use double validation or use <a href="https://www.wikiwand.com/en/Additive_smoothing">additive smoothing</a>.</p><h4>CatBoost</h4><p>This technique using various statistics on combinations of categorical features and combinations of categorical and numerical features. Encoder replaces a categorical feature with average value of target corresponding to that category combined with the target probability over the entire dataset.</p><p>➕ CatBoost avoids the problem of leakage using the principal similar to the time series datas validation, i.e. target probability for the current feature is calculated only from observations before it, and avoids high variance for earlier training examples, using different permutations.</p><p>➕ Encoder prevents overfitting by repeating the process of target encoding multiple times on shuffled versions of the dataset and averaging the results.</p><h4>Categorical Embeddings</h4><p>This technique comes from Deep Learning and NLP, which translates large sparse vectors into a lower dimensional space that preserves semantic relationships.</p><p>An embedding is a matrix in which each column is the vector that corresponds to an item in vocabulary. To get the dense vector for a single vocabulary item, we need to retrieve the column corresponding to that item. The general idea of technique is the distance between the dense vectors will have meanings.</p><p>In theory we can use PCA, word2vec and other embedding techniques to reduce high dimensional space to low dimensional space. Whether or not to use embeddings will depend on the dataset and goals, and the only way to know for sure is to try it.</p><p>How to encode categorical features with high cardinality depends on whether the problem is asking about a regression or a classification model. The answer is also depends on types of variables (ordinal or nominal) and goals. Data Scientists still need to experiment to find the best solution for their particular case.</p><p>☼☽✨</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=fdb514a7eb87" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Interpretation of ML models]]></title>
            <link>https://medium.com/@katerinafomkina/interpretation-of-ml-models-e643b5957726?source=rss-f21d4b5ea3f3------2</link>
            <guid isPermaLink="false">https://medium.com/p/e643b5957726</guid>
            <category><![CDATA[shap]]></category>
            <category><![CDATA[lime]]></category>
            <category><![CDATA[interpretable-ml]]></category>
            <category><![CDATA[partial-dependence-plots]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Katerina Fomkina]]></dc:creator>
            <pubDate>Tue, 16 Aug 2022 13:16:58 GMT</pubDate>
            <atom:updated>2022-08-16T13:16:58.468Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/639/0*_1CmmxuHLgKmpOnq.png" /></figure><p>The interpretability of ML model is important. ML model is a black box and no one can be sure that, despite its good accuracy, the model is working correctly.</p><p>We need to know what is going on in the black box and there are several methods, that can help us understand why certain decisions were made by the model.</p><h4>What is interpretability?</h4><blockquote><strong><em>Interpretability is the degree to which a human can understand the cause of a decision.</em></strong></blockquote><p>The higher the interpretability of ML model, the easier it is for someone to comprehend why certain predictions have been made.</p><p>First, the model must be able to answer the question: “What would the prediction be if input X was different?”</p><p>Second, the scientist must keep the explanation very brief, giving only a few reasons, even if the world is more complex.</p><h4><em>Global Model-Agnostic Methods</em></h4><p>These methods describe the average behavior of ML mode. Global methods are often expressed as expected values based on the distribution of the data.</p><p>Model-agnostic global interpretation techniques:</p><p>▸ <strong>Partial dependence Plot (PDP)</strong></p><p>Shows the marginal effect one or two features have on the predicted outcome of ML model. PDP can show whether the relationship between the target and a feature is linear, monotonic or more complex.</p><p>➕ PDP are easy to implement.</p><p>➕ If features are not correlated with each other, PDP shows how the average prediction in dataset changes when the j-th feature is changed.</p><p>➖ Maximum number of features in a partial dependence is two, because the human cannot imagine more than 3 dimensions.</p><p>➖ Some PDPs do not show the feature disctribution.</p><p>➖ The assumption of independence of the features is the biggest issue of PDP. If features are correlated, PDP cannot be trusted.</p><p>➖ Heterogenous effects might be hidden, because PDP only show the average marginal effects.</p><p>➖ Does not provide a valid functional decomposition, i.e. adding all PDPs of all subsets does not yield the original function.</p><p>▸ <strong>Accumulated Local Effects Plot (ALE)</strong></p><p>Accumulated Local Effects describes how features influence the prediction of ML model on average. ALE plots are faster and unbiased alternative to PDP. ALE plots calculating differences of predictions instead of averages.</p><p>➕ ALE plots are unbiased, i.e. they work when features are correlated.</p><p>➕ ALE plots are faster to compute than PDP.</p><p>➕ The interpretation is clear. ALE plots are centered at zero and the relative effect of changing the feature on the prediction can be easily read.</p><p>➕ Provide the functional decomposition. The entire prediction function can be decomposed into a sum of lower dimensional ALE functions.</p><p>➖ An interpretation of the effect across intervals is not possible if the features are strongly correlated.</p><p>➖ If the number of intervals is too high, the curve becomes shaky.</p><p>➖ The implementation is more complex compared to PDP.</p><p>▸ <strong>Global Surrogate Model</strong></p><p>The purpose of the surrogate model is to approximate the predictions of the underlying model as accurately as possible and to be interpretable at the same time. The performance of the black box model is irrelevant when training surrogate model.</p><pre>Interpretable models:<br>▸ Linear Regression<br>▸ Logistic Regression<br>▸ Decision Trees<br>▸ RuleFit<br>▸ Naive Bayes<br>▸ K-nearest neighbors</pre><p>➕ Surrogate model method is flexible: any interpretable model can be used.</p><p>➕ With the R-squared measure, it is easy to measure how good the surrogate model in approximating the black box predictions.</p><p>➖ Surrogate model draw a conclusion about the black box and not about a data, because it never sees the real outcome.</p><p>➖ It is difficult to determine the best cut-off for R-squared to be sure that the surrogate model is close enough to the black box.</p><p>➖ The surrogate model comes with all its advantages and disadvantages.</p><h4>Local Model-Agnostic Methods</h4><p>Local interpretation methods explain individual predictions of the black box.</p><p>▸ <strong>Local interpretable model-agnostic explanations (LIME)</strong></p><p>It is the implementation of local surrogate models that explains individual predictions. LIME tests what happens to the predictions when it introduces the variations of data into the ML model.</p><p>LIME generates a new dataset consisting of perturbed samples and the corresponding predictions of the black box model. Then on this dataset LIME trains an interpretable model, that is weighted by the proximity of the sampled instances to the instance of interest.</p><p>➕ LIME supports explanations for tabular models, text classifiers, image classifiers.</p><p>➕ LIME generates sparse local explanations.</p><p>➕ LIME makes human-friendly explanation and easy to use.</p><p>➖ Correct definition of the neighborhood is a big issue, when LIME works with tabular data.</p><p>➖ LIME weights the instances according to how close they are to the original instance. The more zeros in the coalition vector, the less weight in LIME.</p><p>➖ Instability of the explanations, i.e. the explanation of two very close points differs greatly.</p><p>➖ LIME does not guarantee that the prediction is fairly distributed among the features.</p><p>▸ <strong>SHapley Additive exPlanations(SHAP)</strong></p><p>Suppose that each feature value of the instance is a player in a game, where the prediction is the payoff. A player can be an individual feature value or a group of feature values. Shapley values — a method from coalition game theory, that fairly distributes the prediction among the features and works for classification and regression problems. In other words, Shapley value is the average marginal contribution of the feature value in all possible coalitions.</p><pre>Shapley values satisfy the properties of:<br>▸ Efficiency<br>▸ Symmetry<br>▸ Dummy<br>▸ Additivity</pre><p>SHAP is a method to explain individual predictions, that based on Shapley values, but has its own KernelSHAP, TreeSHAP, feature importance, summary plot, dependence plot…</p><pre>SHAP’s important properties:<br>▸ Local accuracy<br>▸ Missingness. Missing features get zero attribution<br>▸ Consistency. Shapley values increase as the marginal contribution of the feature value increases.</pre><p>➕ SHAP has a solid theoretical foundation in theory.</p><p>➕ The prediction is fairly distributed among the features.</p><p>➕ SHAP weights the sampled instances according to the weight the coalition would get in the Shapley value estimation.</p><p>➕ SHAP provides global and local interpretations of the model prediction.</p><p>➖ KernelSHAP is slow and ignores feature dependence.</p><p>➖ Shapley values can be misinterpreted.</p><p>➖ SHAP does not generate sparse local explanations.</p><h4>Conclusion</h4><p>The importance of Interpreting ML models cannot be underestimated.</p><p>Which method to use when working with a black box?</p><p>You can use all of them considering their specification, advantages and disadvantages.</p><p>☼☽✨</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e643b5957726" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How about Linear Regression?!]]></title>
            <link>https://medium.com/@katerinafomkina/how-about-linear-regression-4b2c72ed646c?source=rss-f21d4b5ea3f3------2</link>
            <guid isPermaLink="false">https://medium.com/p/4b2c72ed646c</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[machine-intelligence]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[mathematics-education]]></category>
            <category><![CDATA[linear-regression]]></category>
            <dc:creator><![CDATA[Katerina Fomkina]]></dc:creator>
            <pubDate>Fri, 05 Aug 2022 13:28:42 GMT</pubDate>
            <atom:updated>2022-08-05T13:28:42.459Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*5MRMl2TUUA2MRGx1o7YYOg.jpeg" /></figure><h3>Part I. Fundamentals</h3><p>Linear Regression(LR) is ML algorithm based on supervised learning. LR is used to predict the value of dependent variable using given independent variables.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/304/0*fJ75DuW3nAYoM68S" /></figure><p>Task is to find the best coefficients and intercept value to get the best fit line. First, need to check the performance of LR model. To check it need to use Cost Function.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/209/0*yQOsyk_ievkBaa9m" /></figure><p>Cost Function is the calculation of the error between predicted values and actual values. To improve the model need to reduce cost function, i.e. to minimize RMSE.</p><p>How to minimize Cost Function? Answer is Gradient Descent!</p><p>Gradient Descent is an optimization algorithm used to find minimum of Cost Function. Gradient descent will continuously update the parameters of the model untill find the best values which gives the minimum of RMSE.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/362/1*DUkbU7A2Msl3CNSE8R86iw.png" /></figure><h4><strong>Basic terms of LR</strong></h4><p>▸ Residuals: Error_term=actual_value — predicted_value</p><p>▸ Correlation: the strength of linear relationship between two numeric variables</p><p>▸ Variance: the degree of the spread of data, i.e. how far observed values differ from the average of predicted values</p><p>▸ Autocorrelation: the relationship between residuals</p><p>▸ Normal distribution: the probability distribution that is symmetric about the mean</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/396/1*piF1wrU-s0KllmFr_zPduw.png" /></figure><h4>Important assumptions of LR</h4><p>▸ Linear relationship between target and independent variables</p><p>▸ Target variable is continuous</p><p>▸ No or little multicollinearity between independent variables</p><p>▸ Residuals should have a normal distribution</p><p>▸ Residuals should have constant variance</p><p>▸ Residuals should be independently distributed, i.e. no autocorrelation</p><p>.</p><p>.</p><p>To be continued…</p><p>☼☽✨</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4b2c72ed646c" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Math ∩ Programming ≠ ∅]]></title>
            <link>https://medium.com/@katerinafomkina/math-programming-a75c925e8c3f?source=rss-f21d4b5ea3f3------2</link>
            <guid isPermaLink="false">https://medium.com/p/a75c925e8c3f</guid>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[mathematics-education]]></category>
            <category><![CDATA[python-programming]]></category>
            <category><![CDATA[python3]]></category>
            <dc:creator><![CDATA[Katerina Fomkina]]></dc:creator>
            <pubDate>Sat, 23 Jul 2022 13:18:00 GMT</pubDate>
            <atom:updated>2022-07-23T13:18:00.654Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/695/1*khFuXfKYyTOLP2w1rL7srQ.jpeg" /></figure><p>Programming requires building logic and math often is very useful to help find a solution to a problem. For example, we can find a certain pattern using progression or mathematics theorem or some properties of numbers/geometric figures, etc…</p><p>Today i will use math to solve some tasks from leetcode.com</p><blockquote>258. Add Digits</blockquote><blockquote>Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.</blockquote><p>The problem of this task is called a digital root or repeated digital sum.</p><p><strong>The digital root of a natural number in a given radix is the single digit obtained by an iterative process of summing digits on each iteration using the result from the previous iteration to compute a digit sum. The process continues until a single-digit number is reached.</strong></p><p>The mathematical formula of this algorithm in base 10 is:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/347/0*JGuhiOMug7_Jz4c9" /></figure><pre>For example: given number 873 → 8+7+3=18 → 1+8=9</pre><pre>Using formula we can count the digital root of 873: <br>872 % 9=8 → 8+1=9</pre><p>So we can easily and quickly solve the task:</p><pre>def addDigits(num):<br>        if num==0:<br>            return 0<br>        return 1+(num-1)%9</pre><blockquote>292. Nim Game</blockquote><blockquote>You are playing the following Nim Game with your friend:</blockquote><blockquote>Initially, there is a heap of stones on the table.</blockquote><blockquote>You and your friend will alternate taking turns, and <strong>you go first</strong>.</blockquote><blockquote>On each turn, the person whose turn it is will remove 1 to 3 stones from the heap.</blockquote><blockquote>The one who removes the last stone is the winner.</blockquote><blockquote>Given n, the number of stones in the heap, return true<em> if you can win the game assuming both you and your friend play optimally, otherwise return </em>false.</blockquote><p>First, play optimally means that in each step we’ll make the best choice. When we have 1 stone in a heap, we’ll take it and win the game, the same fact is about 2 or 3 stones. When we have 4 stones it doesn’t matter how many stones we take 1, 2 or 3, because the next player takes 3, 2 or 1 stone respectively and wins. Suppose there are 5 stones in a heap. The best tactic is to take 1 stone, the second player loses, because there will be 4 stones left in a heap and we have the situation that i described earlier. This means that we always need to take so many stones, that a number stones left in a heap was divisible by 4. Using this logic we can extend the algorithm to any number of stones in a heap. Before we start coding we can remember about math and use it.</p><pre>For example:</pre><pre>1%4==1<br>2%4==2<br>3%4==3<br>4%4==0</pre><p>Here we see, that if the remainder of a number divided by four is not equal to zero, then we can win. That’s amazing!</p><pre>def canWinNim(n):<br>        if n%4==0:<br>            return False<br>        return True</pre><blockquote>319. Bulb Switcher</blockquote><blockquote>There are n bulbs that are initially off. You first turn on all the bulbs, then you turn off every second bulb.</blockquote><blockquote>On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb.</blockquote><blockquote>Return <em>the number of bulbs that are on after </em><em>n rounds</em>.</blockquote><p>Here we need to find a pattern, so before start coding, we need to draw an example.</p><pre>Example:<br>i=1: o o o o o<br>i=2: o ∅ o ∅ o<br>i=3: o ∅ ∅ ∅ o<br>i=4: o ∅ ∅ o ∅<br>i=5: o ∅ ∅ o ∅</pre><pre>If we continue this process with n=10 and so on, we’ll see, that the number of bulbs on is equal to the integer square root of n.</pre><p>The solution is a one-line code:</p><pre>def bulbSwitch(n):<br>        <br>        return int(pow(n, 0.5))</pre><blockquote>781. Rabbits in Forest</blockquote><blockquote>There is a forest with an unknown number of rabbits. We asked n rabbits <strong>“How many rabbits have the same color as you?”</strong> and collected the answers in an integer array answers where answers[i] is the answer of the ith rabbit.</blockquote><blockquote>Given the array answers, return <em>the minimum number of rabbits that could be in the forest</em>.</blockquote><pre>Let’s take a look at examples:</pre><pre>▸[10,10,10] → answer is 10+1=11 → the three rabbits that answered “10” could be the same color, say white, so the minimum number of rabbits is 11.<br>▸[1,1,1,1] → answer is 4 → the two rabbits can be red and the other two are white, so the minimum number of rabbits is 4<br>▸[1,1,1,1,1] → answer is 6 → the two rabbits are grey, the other two are white and the rest are black.</pre><p>Overall, we can create a condition:</p><pre>If we have a certain item and its number is divisible by (item+1):    <br>    cnt+=number<br>else: <br>    cnt+=(number//(item+1)+1)*(item+1)<br>If the rabbit answered 0, it means that this rabbit is unique:<br>    cnt+=1</pre><p>The solution is:</p><pre>def numRabbits(answers):<br>        <br>        dict_ans={}<br>        <br>        for x in answers:<br>            if x in dict_ans.keys():<br>                dict_ans[x]+=1<br>            else:<br>                dict_ans[x]=1<br>        <br>        cnt=0<br>        for key in dict_ans.keys():<br>            if key!=0:<br>                if dict_ans[key]&lt;=key+1:<br>                    cnt+=key+1<br>                else:<br>                    if dict_ans[key]%(key+1)==0:<br>                        cnt+=dict_ans[key]<br>                    else:<br>                        cnt+=(dict_ans[key]//(key+1)+1)*(key+1)<br>            else:<br>                cnt+=dict_ans[key]<br>        return cnt</pre><blockquote>2344. Minimum Deletions to Make Array Divisible</blockquote><blockquote>You are given two positive integer arrays nums and numsDivide. You can delete any number of elements from nums.</blockquote><blockquote>Return <em>the </em><strong><em>minimum</em></strong><em> number of deletions such that the </em><strong><em>smallest</em></strong><em> element in </em>nums<em> </em><strong><em>divides</em></strong><em> all the elements of </em>numsDivide. If this is not possible, return -1.</blockquote><blockquote>Note that an integer x divides y if y % x == 0.</blockquote><p><strong>GCD is the largest common divisor that divides the numbers without a remainder.</strong></p><pre>Example: Find GCD(8, 12)</pre><pre>The divisors of 8:  1,2,4,8</pre><pre>The divisors of 12: 1,2,3,4,6,12</pre><pre>The numbers that these two lists have in common are the common<em> </em>divisors of 8 and 12, that is: 1,2,4</pre><pre>The greatest divisor from common divisors is 4 --&gt; GCD(8,12)=4</pre><p>The math.gcd() method returns the greatest common divisor of the two integers.</p><p>First, we find the gcd of <em>numsDivide </em>list, then start checking and counting using <em>nums </em>list.</p><pre>import math<br><br>def minOperations(nums, numsDivide):<br>        gd=0<br>        for x in numsDivide:<br>            gd=math.gcd(gd, x)<br>            <br>        nums.sort()<br>        cnt=0<br>        <br>        while cnt&lt;len(nums) and gd % nums[cnt]&gt;0:<br>            cnt+=1<br>        if cnt==len(nums):<br>            return -1<br>        return cnt</pre><p>As we can see above using mathematics is always a good and sometimes the easiest solution.</p><p>That’s all for today, happy coding!</p><p>☼☽✨</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a75c925e8c3f" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Plate collection or a Stack]]></title>
            <link>https://medium.com/@katerinafomkina/plate-collection-or-a-stack-10e3c53b31cd?source=rss-f21d4b5ea3f3------2</link>
            <guid isPermaLink="false">https://medium.com/p/10e3c53b31cd</guid>
            <category><![CDATA[stack]]></category>
            <category><![CDATA[leetcode-medium]]></category>
            <category><![CDATA[leetcode-solution]]></category>
            <category><![CDATA[python-programming]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[Katerina Fomkina]]></dc:creator>
            <pubDate>Wed, 22 Jun 2022 12:09:04 GMT</pubDate>
            <atom:updated>2022-06-23T02:56:28.280Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*IPMo4oXjVZkzVuXk" /><figcaption>Photo by <a href="https://unsplash.com/@brookelark?utm_source=medium&amp;utm_medium=referral">Brooke Lark</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><h4><em>Abstract</em></h4><p>Imagine a pile of plates. We can take a plate from the top or put it on top of the pile. This is a Stack.</p><h4><strong><em>Programming</em></strong></h4><p>Stack is a linear data structure, that stores items in a LIFO manner, i.e. Last-In/First-Out. The process of adding an element to a stack is referred to a “push” operation, while removing the most recently added element from a stack is called a “pop” operation.</p><p>Stack In Python can be implemented either through an array, through a linked list or using the deque class.</p><p><strong>Operations of the Stack</strong></p><pre><em>Two essential operations:</em></pre><pre>▸ <strong>push()</strong> - <em>inserting an element to the stack</em><br>▸ <strong>pop()</strong> - <em>removing the topmost element from the stack</em></pre><pre><em>Operations to check the status of the stack:</em></pre><pre>▸ <strong>peek() </strong>-<strong> </strong><em>get the topmost element without modifying the stack</em><strong><br></strong>▸ <strong>is Empty()</strong> - <em>check if the stack is empty</em></pre><pre><strong>Time Complexity</strong> of all these operations is <strong>O(1)</strong></pre><p><strong>Applications of the Stack</strong></p><pre>▸ <em>Balancing of symbols</em></pre><pre><em>▸ Backtracking</em></pre><pre><em>▸ Expression evaluation and syntax parsing</em></pre><pre><em>▸ Memory management</em></pre><pre><em>▸ Graph Algorithms</em></pre><pre><em>▸ Forward and backward features in web browsers</em></pre><p><strong>Let’s take a look for real problems</strong></p><blockquote>Find a sum of positive integers in a list: [-5, 1, 3, 0, 2].</blockquote><p>The first item of the list is the bottom of a stack and the last - is the top of a stack. Algorithm is as follows: while stack is not empty check whether the top element is positive, and if True, add it to the sum. Remove each checked element(it doesn’t matter if it’s positive or not) from the top of the stack.</p><pre><strong>def find_sum(stack):</strong><br>    <br>    # <em>function to calculate the sum of positive numbers</em><br>    <br>    <strong>sum=0</strong> # <em>initialize sum</em><br>    <br>    # <em>while stack is not empty <br>    # check whether the top element is positive, <br>    # and if True, add it to the sum.<br>    # stack[-1] is the top element of the stack</em><br>    <br>    <strong>while stack:</strong>            <br>        <strong>if stack[-1]&gt;0:</strong>     # <em>check the top element</em><br>            <strong>sum+=stack[-1]</strong>  # <em>if True sum=sum+stack[-1]</em><br>        <strong>stack.pop()</strong>         # <em>pop the top</em><br>    <strong>return sum</strong>              #<em>return sum</em><br>  <br># <em>Driver Code</em>  <br><strong>stack=[-5, 1, 3, 0, 2]<br>print(&quot;<em>The sum of positive elements is:</em> &quot;, find_sum(stack))</strong></pre><p>In this article i will write a solution for some problems from leetcode.com</p><blockquote><strong>735. Asteroid Collision. </strong>We are given an array asteroids of integers representing asteroids in a row. For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed. Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.</blockquote><pre><strong>def asteroidCollision(asteroids):</strong><br>    <em>&quot;&quot;&quot;<br>    :type asteroids: List[int]<br>    :rtype: List[int]<br>    &quot;&quot;&quot;</em></pre><pre>    <em># Create an empty stack for the asteroids.</em> <br>    <br>    <strong>stack=[]</strong></pre><pre><strong>    for x in asteroids:</strong></pre><pre><em>        # if the direction of the asteroid is positive, <br>        # push the asteroid to the stack</em></pre><pre>        <strong>if x&gt;0:                 <br>            stack.append(x)    </strong> <br>       <br>       <strong> else:</strong>   <br>            <br>            <em># while stack is not empty, top of the stack is <br>            # positive and its value less then absolute <br>            # value of the asteroid, pop it from top</em><br>            <br>            <strong>while stack and stack[-1]&gt;0 and stack[-1]&lt;abs(x):<br>                stack.pop()</strong></pre><pre>            <em># if the stack is empty or top of the stack <br>            # is negative push the asteroid to the stack</em><br>            <br>            <strong>if len(stack)==0 or stack[-1]&lt;0:<br>                stack.append(x)</strong></pre><pre>            <em># if the stack is not empty and <br>            # value of the top element is equal to <br>            # absolute value of the asteroid, pop it from top</em></pre><pre>            i<strong>f len(stack)&gt;0 and stack[-1]==abs(x):<br>                stack.pop()<br>    return stack</strong><br>  <br><em># Driver Code </em> <br><strong>asteroids = [5,10,-5]<br>print(&quot;The state of the asteroids after all collisions is: &quot;, asteroidCollision(asteroids))</strong></pre><blockquote><strong>2211. Count Collisions on a Road. </strong>There are n cars on an infinitely long road. The cars are numbered from 0 to n - 1 from left to right and each car is present at a <strong>unique</strong> point.</blockquote><blockquote>You are given a <strong>0-indexed</strong> string directions of length n. directions[i] can be either &#39;L&#39;, &#39;R&#39;, or &#39;S&#39; denoting whether the ith car is moving towards the <strong>left</strong>, towards the <strong>right</strong>, or <strong>staying</strong> at its current point respectively. Each moving car has the <strong>same speed</strong>.</blockquote><blockquote>The number of collisions can be calculated as follows:</blockquote><blockquote>- When two cars moving in <strong>opposite</strong> directions collide with each other, the number of collisions increases by 2.</blockquote><blockquote>- When a moving car collides with a stationary car, the number of collisions increases by 1.</blockquote><blockquote>After a collision, the cars involved can no longer move and will stay at the point where they collided. Other than that, cars cannot change their state or direction of motion.</blockquote><blockquote>Return <em>the </em><strong><em>total number of collisions</em></strong><em> that will happen on the road</em>.</blockquote><pre><strong>def countCollisions(directions):</strong><br>    <em>&quot;&quot;&quot;<br>    :type directions: str<br>    :rtype: int<br>    &quot;&quot;&quot;</em></pre><pre><em>    # initialize an empty stack for collisions<br>    # count_coll is the total number of collisions</em><br>    <strong>count_coll=0<br>    stack=[]</strong><br>    <br>    <strong>for x in directions:</strong><br>        <br>        <em># if stack is empty push a car to stack</em><br>        <strong>if len(stack)==0:<br>            stack.append(x)</strong><br>        <br>        <em># When two cars moving in opposite directions collide <br>        # with each other, the number of collisions increases by 2    <br>        # if top of the stack is &#39;R&#39; and the car has direction &#39;L&#39;<br>        # increase count_call by 2 (first time) and pop from stack <br>        # while stack is not empty and top of the stack is &#39;R&#39;:<br>            # collisions continue and count_coll is  increasing by 1<br>            # because the car with direction &#39;L&#39; has already counted<br>            # before loop<br>            # pop from stack all the time<br>            # if stack became empty or top of the stack is not &#39;R&#39;:<br>            # push &#39;S&#39;, because after a collision, the cars involved <br>            #can no longer move and will stay at the point <br>            # where they collided<br>            # </em><strong><em>---&gt;...---&gt;---&gt;---&gt;&lt;---</em></strong><br>        <strong>elif stack[-1] == &#39;R&#39; and x == &#39;L&#39; :<br>            count_coll+=2<br>            stack.pop()<br>            while stack and stack[-1] == &#39;R&#39; :<br>                count_coll+=1<br>                stack.pop()<br>            stack.append(&#39;S&#39;)   </strong><br>        <br>        <em># When a moving car collides with a stationary car, <br>        # the number of collisions increases by 1<br>        # if top of the stack is &#39;S&#39; and a car has direction &#39;L&#39;:<br>        # increase count_coll by 1 and push &#39;S&#39; to stack<br>        # </em><strong><em>|&lt;---</em></strong><br>        <strong>elif stack[-1] == &#39;S&#39; and x == &#39;L&#39; :<br>            count_coll+=1<br>            stack.append(&#39;S&#39;)</strong><br>        <br>        <em># When a moving car collides with a stationary car, <br>        # the number of collisions increases by 1<br>        # while top of the stack is &#39;R&#39; and a car has direction &#39;S&#39;:<br>        # pop from stack and increase count_coll by 1<br>        # </em><strong><em>---&gt;...---&gt;---&gt;---&gt;|</em></strong><br>        <strong>elif stack[-1] == &#39;R&#39; and x == &#39;S&#39; :<br>            while stack and stack[-1] == &#39;R&#39; :<br>                count_coll+=1<br>                stack.pop()<br>            stack.append(x)</strong><br>       <br>        <em># other cases push to stack<br>        #</em><strong><em>---&gt;---&gt;</em></strong><em><br>        #</em><strong><em>&lt;---&lt;---</em></strong><em><br>        #</em><strong><em>|---&gt;</em></strong><em><br>        #</em><strong><em>&lt;---|<br>        #&lt;------&gt;</em></strong></pre><pre>        <strong>else :<br>            stack.append(x)<br>            <br>    return count_coll</strong><br>    <br><em># Driver Code  </em><br><strong>directions = &quot;RLRSLL&quot;<br>print(&quot;The total number of collisions is: &quot;, countCollisions(directions))</strong></pre><p>Thats all.</p><p>I hope this article was useful for you to see what is stack.</p><p>☼☽✨</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=10e3c53b31cd" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>