<?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 Riley Huang on Medium]]></title>
        <description><![CDATA[Stories by Riley Huang on Medium]]></description>
        <link>https://medium.com/@yunhanh?source=rss-b3c4a67e76b6------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*ib2ZO447y-YaI02mfYtsiA@2x.jpeg</url>
            <title>Stories by Riley Huang on Medium</title>
            <link>https://medium.com/@yunhanh?source=rss-b3c4a67e76b6------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Mon, 16 Nov 2026 20:52:11 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@yunhanh/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[Analysis of Boston Crime Incident Open Data Using Pandas]]></title>
            <link>https://medium.com/data-science/analysis-of-boston-crime-incident-open-data-using-pandas-5ff2fd6e3254?source=rss-b3c4a67e76b6------2</link>
            <guid isPermaLink="false">https://medium.com/p/5ff2fd6e3254</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[pandas]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[data-analysis]]></category>
            <dc:creator><![CDATA[Riley Huang]]></dc:creator>
            <pubDate>Sat, 20 Jul 2019 04:00:44 GMT</pubDate>
            <atom:updated>2021-06-11T14:50:29.363Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*oVzQ3kMf-jgzyXUPAbO4nA.jpeg" /><figcaption><a href="https://pixabay.com/photos/panda-china-bamboo-zoo-bear-3857754/">Pixabay.com</a></figcaption></figure><p>While I was learning Data Analysis using <a href="https://pandas.pydata.org/pandas-docs/stable/user_guide/index.html">Pandas</a> in Python, I was interested in analyzing the open data about the city I am currently living in.</p><p>Open data provides people myriad opportunities to use and analyze the data as they wish without restrictions. By looking at a city’s Crime Incident open data, you can learn about if this city or a specific neighborhood is safe. Hence, I used the open data of Boston Crime Incident Reports to analyze and visualize them by using Pandas. Hopefully, you can have a better understanding of obtaining, analyzing and visualizing open data after reading my experience.</p><h3>Obtaining Data</h3><ul><li>Firstly, I went to <a href="https://data.boston.gov/"><em>Analyze Boston</em></a><em>: </em>a Boston open data website. Search “crime” and go to <a href="https://data.boston.gov/dataset/crime-incident-reports-august-2015-to-date-source-new-system">Crime Incident Reports</a></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/703/1*ThzuBRD6ycPSiLoshHStfA.png" /></figure><ul><li>To get the data, I copied the link for downloading the data in csv format:</li></ul><pre>url = “<a href="https://data.boston.gov/dataset/6220d948-eae2-4e4b-8723-2dc8e67722a3/resource/12cb3883-56f5-47de-afa5-3b1cf61b257b/download/tmppj4rb047.csv">https://data.boston.gov/dataset/6220d948-eae2-4e4b-8723-2dc8e67722a3/resource/12cb3883-56f5-47de-afa5-3b1cf61b257b/download/tmppj4rb047.csv</a>”</pre><ul><li>Use wget command to download the data.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/716/1*du9p1ib0bexMFhfIdM9Rrg.png" /></figure><ul><li>Import pandas</li></ul><p>import pandas as pd</p><ul><li>Use read_csv in pandas to read data and save them into a data frame</li></ul><p>df = pd.read_csv(&#39;tmppj4rb047.csv&#39;)</p><ul><li>Check if data is successfully obtained.</li></ul><p>df.head()</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/909/1*Ds6_bbzLbPRivTA6Wbu38w.png" /></figure><h3>Data Analysis</h3><h4>1. Types of Crimes</h4><p>After obtaining the data, I want to know how many types of crimes are there in Boston.</p><ul><li>Use value_counts in Pandas.</li></ul><p>value_counts helps count the number of appearances of different types of crimes and sort them in orders.</p><pre>df.OFFENSE_CODE_GROUP.value_counts().iloc[:10]</pre><p>To make it easy to show, I only asked to return the first ten results.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/564/1*cMuQe-A6i5NU4Uz7T9XIbQ.png" /><figcaption>Top 10 Crime Incidents in Boston</figcaption></figure><p>Here, we can see the crime incident that has happened the most frequently in Boston is “Motor Vehicle Accident Response,” and “Larceny” has also been taking place very frequently.</p><p>Then, I plotted the result for better visualization.</p><pre>df.OFFENSE_CODE_GROUP.value_counts().iloc[:10].sort_values().plot(kind= “barh”)</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/851/1*pT18BXm60-YbG9Ft__DGVg.png" /></figure><h4>2. Analyzing a Specific Crime</h4><p>I want to specifically analyze larceny in Boston. Hence I put the part of the data frame that contains larceny into another data frame and called it “larceny.”</p><pre>larceny = df[df.OFFENSE_CODE_GROUP.str.contains(“Larceny”)]<br>larceny.head()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/910/1*lfyeiZjI1-GVaFa4jwQcmg.png" /></figure><ul><li>Check the size of the data “Larceny”</li></ul><pre>larceny.shape() </pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/339/1*TyzVlIyu0aFp3Cxnlz_qkA.png" /></figure><p>There are 17961 records of Larceny incidents, and each record has 17 columns.</p><h4>3. Analyzing Places</h4><p>I want to know the data of crime incidents in different locations of Boston and, more specifically, what places in Boston are more dangerous.</p><p>I used groupby function in Pandas to group the types of criminal locations, and used size function to check the number of entries.</p><pre>larceny.groupby(“STREET”).size().sort_values(ascending = False)</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/755/1*PkfzsaQgPTzwwtpLgV3UwA.png" /><figcaption>First few entires of the result</figcaption></figure><p>Looking at the result, we can see the locations in Boston where larceny is more likely to happen are Washington St, Boylston St, and Newbury St.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/923/1*C6mN-0c0_By1hHOs63cC1w.png" /></figure><h4>4. Analyzing Time</h4><p>I also want to know about the trend of larceny incidents that has been taking place in Boston.</p><pre>larceny.groupby(“MONTH”).size().plot(kind = “bar”)</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/615/1*aK_dnPKJgPbIu-8KGSRRqg.png" /></figure><p>Based on the bar graph that I computed, larceny happened the most during May, June, and December, whereas September, October, and August appear to be safer.</p><p>Let’s also look at how the number of larceny incidents changes within a day.</p><pre>larceny.groupby(“HOUR”).size().plot(kind= “bar”) </pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/614/1*4TbiWr4tMaI1sObKpgo4bg.png" /></figure><p>Here, we can tell the safest time of the day when larceny is the least possible to happen in Boston is 5 am. However, people need to be more careful from 4 to 6 pm.</p><p>Now, I want to have an overall look at the data about larceny incidents in Boston in each month and 24 hours. Let’s specifically look at the data in 2018 since 2019 has not ended yet and the data is incomplete.</p><p>If we group MONTH and HOUR using groupby in Pandas, we get the following results.</p><pre>larceny[larceny.YEAR == 2019].groupby([‘MONTH’, ‘HOUR’]).size()</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/716/1*28GujO0tpp08Tq8GYwv0aw.png" /></figure><p>However, this is not helpful for us to read the data easily. To make it better, I used unstack, and this will turn the result in a more readable form.</p><pre>larceny[larceny.YEAR==2018].groupby([‘MONTH’,’HOUR’]).size().unstack(0)</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/751/1*mNZy9i6g5VcETbFgLrWs1w.png" /></figure><p>Now, I want to visualize the result.</p><p>Since I am visualizing 12 months of data into 12 pieces of graphs, I want to use the facet plot. In Pandas, there is a parameter in plot called subplots. Initialize it to be True. I can also adjust the length and width of the graph by using figsize.</p><pre>larceny[larceny.YEAR==2018].groupby([‘MONTH’,’HOUR’]).size().unstack(0).plot(subplots=True, kind = “bar”, figsize = (5, 30)</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/378/1*lLGmFvqvHIpk-e5UJDXsiw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/332/1*ZqYaJJyb825fqOTShrBdhg.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/340/1*OuE55jiScE8fX8suGSVUog.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/323/1*4aeJ6ZpT3nIHFWkuV-c7zQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/315/1*DICjA9d4IIY5xo-InDGYfA.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/334/1*8ktfiTZS1nSZl8bUKAIc-A.png" /></figure><p>Now, we have a complete visualization of the larceny incidents happened in Boston in 2018.</p><h3>Summary</h3><p>By using Pandas, I analyzed and visualized the open data of Boston Crime Incident Reports. Turns out Pandas is indeed a very powerful Python package in terms of extracting, grouping, sorting, analyzing, and plotting the data. If you are interested in data analysis, using Pandas to analyze some real datasets is a good way to start.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5ff2fd6e3254" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/analysis-of-boston-crime-incident-open-data-using-pandas-5ff2fd6e3254">Analysis of Boston Crime Incident Open Data Using Pandas</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Introduction to Gensim: Calculating Text Similarity]]></title>
            <link>https://medium.com/better-programming/introduction-to-gensim-calculating-text-similarity-9e8b55de342d?source=rss-b3c4a67e76b6------2</link>
            <guid isPermaLink="false">https://medium.com/p/9e8b55de342d</guid>
            <category><![CDATA[gensim]]></category>
            <category><![CDATA[machine-learning]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[Riley Huang]]></dc:creator>
            <pubDate>Wed, 10 Jul 2019 03:02:07 GMT</pubDate>
            <atom:updated>2019-07-12T15:12:04.475Z</atom:updated>
            <content:encoded><![CDATA[<h3>Calculating Text Similarity With Gensim</h3><h4>Easily comparing different texts with the Genism tool</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*vWOBONiJMU7FFLY6AwVLCA.jpeg" /><figcaption>Photo from <a href="https://www.maxpixel.net/Education-Dictionary-Book-Literature-Page-3294946">Maxpixel</a></figcaption></figure><p>Two years ago, I built my first Python project: a tool that generates similarity scores between multiple articles. Back then, I merely used Python dictionaries to store different attributes of a text file — such as word frequencies, stem words frequencies, sentence lengths, punctuations, and etc. — and compare them in a relatively efficient way.</p><p>Thanks to this Python project, I was assigned to do a similar project alone during my summer internship. I was told to build a tool that compares a large number of films and television products with their different attributes. The tool was supposed to generate a set of dictionaries with the same or the most similar products in pairs with different similarity scores.</p><p>I started doing the project by using the same approach I took last time, but it didn’t go well. Then, I was introduced to <a href="https://radimrehurek.com/gensim/intro.html"><strong>Gensim</strong></a>.</p><p>The content on Gensim’s official website and its tutorial are a little too vague, so I wanted to talk a bit about what is Gensim. More importantly, I want to talk about my experience of learning and using Gensim.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*GYEB8J6c5aaMiUgceMp6HQ.jpeg" /></figure><h3>What is Gensim?</h3><p>According to Gnism’s official website:</p><blockquote>Gensim is a <strong>free</strong> Python library designed to automatically extract semantic topics from documents, as efficiently (computer-wise) and painlessly (human-wise) as possible. Gensim is designed to process raw, unstructured digital texts (“<em>plain text</em>”).</blockquote><h3>Main Concept</h3><p><strong>Corpus</strong></p><p>The corpus is used to train a machine learning model in Gensim, and the models use the corpus to initialize parameters for the model.</p><p><strong>Vector Space Model (VSM)</strong></p><p>Every document is represented by an array of features, and you can think of the feature as a question-answer pair. An example of a feature could be the following: <strong>How many times does the word “happy” appear in the text document? Three.</strong></p><p>The question is represented by its id (integer), and hence the representation of the text document becomes a series of pairs, such as (2, 4.0), (3, 6.0), (4, 5.0). This series can be thought of as a <strong>vector.</strong></p><p>If the vectors in the two documents are similar, the documents must be similar too.</p><p><strong>Sparse Vector</strong></p><p>Documents in Gensim are represented by sparse vectors. Gensim omits all vectors with value 0.0, and each vector is a pair of (feature_id, feature_value).</p><p><strong>Model</strong></p><p>A Model can be thought of as a transformation from one vector space to another. By training the corpus, the parameters of this transformation are learned.</p><h3>Use Gensim to Determine Text Similarity</h3><p>Here’s a simple example of code implementation that generates text similarity:</p><p>(Here, jieba is a text segmentation Python module for cutting the words into segmentations for easier analysis of text similarity in the future.)</p><pre>from gensim import corpora, models, similarities<br>import jieba</pre><pre>texts = [&#39;I love reading Japanese novels. My favorite Japanese writer is Tanizaki Junichiro.&#39;, &#39;Natsume Soseki is a well-known Japanese novelist and his Kokoro is a masterpiece.&#39;, &#39;American modern poetry is good. &#39;]</pre><pre>keyword = &#39;Japan has some great novelists. Who is your favorite Japanese writer?&#39;</pre><pre>texts = [jieba.lcut(text) for text in texts]</pre><pre>dictionary = corpora.Dictionary(texts)</pre><pre>feature_cnt = len(dictionary.token2id)</pre><pre>corpus = [dictionary.doc2bow(text) for text in texts]</pre><pre>tfidf = models.TfidfModel(corpus) </pre><pre>kw_vector = dictionary.doc2bow(jieba.lcut(keyword))</pre><pre>index = similarities.SparseMatrixSimilarity(tfidf[corpus], num_features = feature_cnt)</pre><pre>sim = index[tfidf[kw_vector]]</pre><pre>for i in range(len(sim)):<br>    print(&#39;keyword is similar to text%d: %.2f&#39; % (i + 1, sim[i]))</pre><p>Print Results:</p><pre>keyword is similar to text1: 0.50<br>keyword is similar to text2: 0.02<br>keyword is similar to text3: 0.00</pre><h3>Code Explanation</h3><h4>Step 1: Word segmentation using Jieba</h4><p>First, let’s look at how jieba works. We want to segment a quote from Tanizaki Junichiro’s novel <a href="https://en.wikipedia.org/wiki/Naomi_(novel)"><strong><em>Naomi</em></strong></a><em>:</em></p><pre>import jieba </pre><pre>text = ‘I wanted to boast to everyone. This woman is mine. Take a look at my treasure. ‘ </pre><pre>words = jieba.lcut(text)</pre><pre>print(words)<br></pre><p>Print result:</p><pre>[‘I’, ‘wanted’, ‘to’, ‘boast’, ‘to’, ‘everyone’, ‘.’, ‘This’, ‘woman’, ‘is’, ‘mine’, ‘.’, ‘Take’, ‘a’, ‘look’, ‘at’, ‘my’, ‘treasure’, ‘.’]</pre><h4>Step 2: Obtain the number of features based on dictionary</h4><p>corpora.Dictionary builds a dictionary.</p><p>len(dictionary.token2id) represents the number of words in the dictionary.</p><p><strong>Example</strong>:</p><pre>from gensim import corpora<br>import jieba</pre><pre><br>text1 = ‘痴人の愛’</pre><pre>text2 = ‘よく世間では「女が男を欺す」と云います。’</pre><pre>texts = [text1, text2]</pre><pre># Generate a word list for the text set</pre><pre>texts = [jieba.lcut(text) for text in texts]</pre><pre>print(‘Text set:’, texts)<br></pre><pre>#Build a dictionary based on a text set</pre><pre>dictionary = corpora.Dictionary(texts)</pre><pre>print(‘dictionary:’, dictionary)<br></pre><pre># Extract dictionary features</pre><pre>feature_cnt = len(dictionary.token2id)</pre><pre>print(‘Dictionary feature number: %d’ % feature_cnt)</pre><p><strong>Print result:</strong></p><pre>Text set: [[&#39;痴人&#39;, &#39;の&#39;, &#39;愛&#39;], [&#39;よ&#39;, &#39;く&#39;, &#39;世間&#39;, &#39;で&#39;, &#39;は&#39;, &#39;「&#39;, &#39;女&#39;, &#39;が&#39;, &#39;男&#39;, &#39;を&#39;, &#39;欺&#39;, &#39;す&#39;, &#39;」&#39;, &#39;と&#39;, &#39;云&#39;, &#39;い&#39;, &#39;ま&#39;, &#39;す&#39;, &#39;。&#39;]]</pre><pre>dictionary: Dictionary(21 unique tokens: [&#39;の&#39;, &#39;愛&#39;, &#39;痴人&#39;, &#39;。&#39;, &#39;「&#39;]...)</pre><pre>Dictionary feature number: 21</pre><h4>Step 3: Obtain corpus based on dictionary</h4><p><strong>Example:</strong></p><pre>from gensim import corpora<br>import jieba</pre><pre>text1 = &#39;I love Tokyo&#39;</pre><pre>text2 = &#39;Tokyo, Tokyo, Tokyo&#39;</pre><pre>texts = [text1, text2]</pre><pre>texts = [jieba.lcut(text) for text in texts]</pre><pre>dictionary = corpora.Dictionary(texts)</pre><pre>corpus = [dictionary.doc2bow(text) for text in texts]</pre><pre>print(&#39;Dictionary (dictionary):&#39;, dictionary.token2id)</pre><pre>print(&#39;Corpus: &#39;, corpus)</pre><p><strong>Print result:</strong></p><pre>Dictionary (dictionary): {&#39; &#39;: 0, &#39;Come&#39;: 1, &#39;Tokyo&#39;: 2, &#39;cuisine&#39;: 3, &#39;for&#39;: 4, &#39;to&#39;: 5, &#39;,&#39;: 6}</pre><pre>Corpus: [[(0, 5), (1, 1), (2, 2), (3, 1), (4, 1), (5, 1)], [(0, 2), (2, 3), (6, 2)]]</pre><p>Here, thedoc2bow function generates <a href="https://stackoverflow.com/questions/31522893/sparse-vector-vs-dense-vector">Sparse Vector</a>.</p><h4>Step 4: Use TF-IDF Model to process corpus, obtaining index</h4><p>Here’s some more information about what <a href="https://en.wikipedia.org/wiki/Tf%E2%80%93idf">TF-IDF</a> does.</p><p>tfidf = models.TfidfModel(corpus)</p><p>index = similarities.SparseMatrixSimilarity(tfidf[corpus], num_features = feature_cnt)</p><h4>Step 5: Convert search words into Sparse Vectors</h4><p><strong>Example:</strong></p><pre>from gensim import corpora<br>import jieba</pre><pre>text1 = ‘Tanizaki Junichiro writes good stories’ </pre><pre>text2 = ‘Naomi is a story written by Tanizaki’</pre><pre>texts = [text1, text2]</pre><pre>texts = [jieba.lcut(text) for text in texts]</pre><pre>dictionary = corpora.Dictionary(texts)</pre><pre># Use [Dictionary] to convert [search word] to [sparse vector]<br>keyword = ‘good stories’</pre><pre>kw_vector = dictionary.doc2bow(jieba.lcut(keyword))</pre><pre>print(kw_vector)</pre><p><strong>Print result:</strong></p><pre>[(0, 1), (3, 1), (4, 1)]</pre><h4>Step 5: Put everything together: similarity calculation</h4><pre>texts = [jieba.lcut(text) for text in texts]</pre><pre>dictionary = corpora.Dictionary(texts)</pre><pre>feature_cnt = len(dictionary.token2id)</pre><pre>corpus = [dictionary.doc2bow(text) for text in texts]</pre><pre>tfidf = models.TfidfModel(corpus)</pre><pre>kw_vector = dictionary.doc2bow(jieba.lcut(keyword))</pre><pre>index = similarities.SparseMatrixSimilarity(tfidf[corpus], num_features = feature_cnt)</pre><pre>sim = index[tfidf[kw_vector]]</pre><pre>for i in range(len(sim)):<br>    print(&#39;keyword is similar to text%d: %.2f&#39; % (i + 1, sim[i]))</pre><h3>Use of Gensim in the Film Comparison Project</h3><p>After learning the basic uses of Gensim, I incorporated Gensim in my project to compare film and television.</p><p>First of all, the very first inputs are two Excel sheets containing films and televisions’ attributes. The headings of the form look like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/664/1*vkfY2cUGdm24HFnJNXSfrw.png" /></figure><p>The name and the summary are the hardest assets to compare because they are in sentence/paragraph form. Hence, Gensim and jieba are used here.</p><p>After using <a href="https://pandas.pydata.org/pandas-docs/stable/reference/api/pandas.read_excel.html">pandas</a> to extract all the data from the two Excel sheets and saving them in data frames, we can store the name and the summary separately in dictionaries. This helps indicate the ID of the assets and their corresponding attributes.</p><pre>df = pd.read_excel (&quot;YOUR LOCAL FILE ADDRESS&quot;, sheetname = &#39;Sheet1&#39;)<br>df2 = pd.read_excel(&quot;YOUR LOCAL FILE ADDRESS&quot;, sheetname = &quot;Sheet1&quot;)</pre><pre># This is the first excel file<br>ccms_title = {}<br>for i in range(len(df[‘assets_id’])):<br> name = df[‘assets_name’][i]<br> iD = str(df[‘assets_id’][i])<br> ccms_title[iD] = name</pre><pre># This is the second excel file<br>douban_title = {}<br>for i in range(len(df2[‘assets_id’])):<br> name = df2[‘assets_name’][i]<br> iD = str(df2[‘assets_id’][i])<br> douban_title[iD] = name</pre><pre>ccms_summary = {}<br>for i in range(len(df[&#39;assets_id&#39;])):<br>    name = df[&#39;assets_name&#39;][i]<br>    iD = str(df[&#39;summary&#39;][i])<br>    ccms_summary[iD] = name</pre><pre>douban_summary = {}<br>for i in range(len(df2[&#39;assets_id&#39;])):<br>    name = df2[&#39;assets_name&#39;][i]<br>    iD = str(df2[&#39;summary&#39;][i])<br>    douban_summary[iD] = name</pre><p>Create a function that uses Gensim to calculate the similarity score between titles and summary.</p><pre>def gensimCalculation(d1, d2):<br>  new_dict = {}</pre><pre>  for x in d1:<br>    text1 = d1[x]<br>    texts = [jieba.lcut(d2[y]) for y in d2] <br>    dictionary = corpora.Dictionary(texts)<br>    feature_cnt = len(dictionary.token2id)<br>    corpus = [dictionary.doc2bow(text) for text in texts]<br>    tfidf = models.TfidfModel(corpus)<br>    new_vec = dictionary.doc2bow(jieba.lcut(text1))<br>    index = similarities.SparseMatrixSimilarity(tfidf[corpus],     num_features = feature_cnt)<br>    sim = index[tfidf[new_vec]]<br>    new_dict[x] = max(sim) </pre><pre> print(new_dict)<br> return</pre><pre>print(gensimCalculation(ccms_summary, douban_summary)) </pre><p>The function compares the summary of a single asset in excel1 with every other summary in excel2, and it finds the most similar summary. The output is a dictionary with the ID of the assets and the most similar asset ID with its most similar summary.</p><p>Other similarity calculations, such as comparing titles, can be efficiently generated in this way too.</p><h3>Summary</h3><p>When approaching Gensim, I learned to focus more on the input and the output in each step. With the help of jieba, the word segmentation module in Python, text similarity is easily calculated.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9e8b55de342d" width="1" height="1" alt=""><hr><p><a href="https://medium.com/better-programming/introduction-to-gensim-calculating-text-similarity-9e8b55de342d">Introduction to Gensim: Calculating Text Similarity</a> was originally published in <a href="https://betterprogramming.pub/">Better Programming</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Make Your Python Web Scraper Smarter]]></title>
            <link>https://levelup.gitconnected.com/make-your-python-web-scraper-smarter-6233f2d10c3f?source=rss-b3c4a67e76b6------2</link>
            <guid isPermaLink="false">https://medium.com/p/6233f2d10c3f</guid>
            <category><![CDATA[beautifulsoup]]></category>
            <category><![CDATA[web-scraping]]></category>
            <category><![CDATA[technology]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[Riley Huang]]></dc:creator>
            <pubDate>Thu, 20 Jun 2019 04:51:25 GMT</pubDate>
            <atom:updated>2019-07-16T20:25:40.818Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*c-oO0pMZ2HoAHoxDP-m6JQ.jpeg" /></figure><p>I recently started learning about web scraping with Python. So far, one thing which I think is quite interesting is how to make your web scraper “smarter” by adding more features to it. For example, I wanted to make it able to turn the page and continue doing its job once it finishes scraping all the desired data at its current page.</p><h3><strong>Example Project</strong></h3><p>I wanted to know the relationships between every single Chinese celebrity. To obtain the information, I needed to extract data from<a href="http://www.1905.com/mdb/relation/list/s0t1p1.html"> http://www.1905.com/mdb/relation/list/s0t1p1.html</a>”, which is a website consisting of all the Chinese celebrity relations.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/601/1*uQsGfB3VKcjlTS-h8GN74w.png" /><figcaption>Celebrity relations</figcaption></figure><p>Notice “s0t1p1 “ at the end of the URL: it indicates the category number, relationship type (marriage, family-member, couples, etc), and page number. Hence s0t1p1 indicates category1, relationship type1 (marriage), and page1.</p><p>Here, I use<a href="https://www.crummy.com/software/BeautifulSoup/bs4/doc/"> <strong>Beautiful Soup</strong></a> in Python to read my HTML file and extract data from it. This<a href="https://medium.com/@yunhanh/quick-web-scraping-with-python-beautiful-soup-4dde18468f1f"> <em>article</em></a> of mine explains what Beautiful Soup is and how we can use it to easily scrape data from the web.</p><p>After importing the necessary modules and packages, let’s get started.</p><h3><strong>Create Beautiful Soup Object</strong></h3><p>After reading the HTML by using urllib, we need to create a Beautiful Soup object. Pass the html to the BeautifulSoup() function, and the Beautiful Soup package will parse the html (it takes the html text and parses it into Python objects.)</p><pre>html = urlopen(url)<br>soup = BeautifulSoup(html, “html.parser”)</pre><p>Or, you can do it another way, and this method can avoid errors when you directly do html = urlopen(url)</p><pre>url_i = &quot;YOUR_URL&quot;</pre><pre>referer = url_i</pre><pre>user_agent = “YOUR_USER_AGENT”</pre><pre>headers = {‘User-Agent’: user_agent, ‘Referer’: referer, ‘Connection’: ‘keep-alive’}</pre><pre>try:</pre><pre>  req = urllib.request.Request(url = url_i, headers = headers)</pre><pre>  response = urlopen(req)</pre><pre>  html = response.read()</pre><pre># throw exceptions</pre><pre>except error.HTTPError as e:</pre><pre>  print(e.reason)</pre><pre>soup = BeautifulSoup(html, “html.parser”)</pre><h3><strong>Extracting Data</strong></h3><p>After obtaining the Beautiful Soup object, we can use it to extract the data that we want. In this example project, we use the same method as I mentioned in my previous<a href="https://medium.com/@yunhanh/quick-web-scraping-with-python-beautiful-soup-4dde18468f1f"> post</a>, which is to scrape data based on their tag and class. Beside the celebrity names and their relations, I also want their corresponding ID, which is the href.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/724/1*6nVSSj3Yjxe3WFJmGIdc7A.png" /><figcaption>A single relation between celebrity “文章” and “马伊琍”</figcaption></figure><p>By constructing a nested loop, your web scraper automatically scrapes all the desired data.</p><pre>def relations(soup):<br>  k = soup.find_all(‘div’, class_=’gx_List mt10&#39;)<br>  for x in k:<br>    allP = x.find_all(‘ul’)<br>    for person in allP:<br>      result = “”<br>      for el in person.find_all(‘li’):<br>        iD = “”<br>        for a in el.find_all(‘a’, href = True):<br>          p = el.get_text(“|”, strip = True)<br>          iD += a[‘href’]<br>          iD += “|”<br>        res = p + iD <br>        res += “\n” <br>        result += res<br>      return result</pre><p>The function above will generate the data on the first page, which looks something like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/729/1*S4G8n5zzcEfvvNPi5n2VzQ.png" /></figure><h3><strong>Page Turning</strong></h3><p>Now let’s talk about page turning.<strong> </strong>A lot of times, data is distributed everywhere on a specific website, especially when it has multiple pages consisting of the same type of data that you want to extract at once. Hence, a page turner is necessary when developing your web scraper.</p><p>To make it run multiple times, we need to build another function that will keep track of the current page, page number, and whether the scraper reaches the end of the page list. In this example website, we are not able to find out the total number of pages exist, so we can’t use a specific number to set the limit of our loop.</p><h4>1. A Counter</h4><p>Let’s first initialize a counter, i, to be zero. It keeps track of the current page and increments by 1 in every iteration.</p><pre># NOT A COMPLETE CODE FOR THE WHILE LOOP </pre><pre>i = 0</pre><pre>While SOME CONDITION :<br>  <br>  i +=1</pre><pre>  url_i = “http://www.1905.com/mdb/relation/list/&quot; + “s0t1p” + str(i) + “.html”</pre><pre>  referer = url_i</pre><pre>  user_agent = “YOUR USER AGENT”</pre><pre>  headers = {‘User-Agent’: user_agent, ‘Referer’: referer, ‘Connection’: ‘keep-alive’}</pre><pre>  try:</pre><pre>    req = urllib.request.Request(url = url_i, headers = headers)</pre><pre>    response = urlopen(req)</pre><pre>    html = response.read()</pre><pre># throw exceptions<br>  except error.HTTPError as e:<br>    print(e.reason)</pre><pre>  soup = BeautifulSoup(html, “html.parser”)</pre><h4>2. The Page</h4><p>Next step is to find out the element on the website that indicates the page. Right click on your website, choose “inspect” and go to “element”.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/587/1*_SGz5TErxUpBXsq2Mc0RdA.png" /></figure><p>(The text “下一页“ means “next page” in Chinese.)</p><p>Now observe this part of the html text closely. To find the information of the page, we need to extract this entire div tag</p><pre>page = soup.find_all (id = “new_page”)</pre><p>To check if the scraper reaches the end of the page list, we need to check if this line of the html text exist when it is at that page:</p><pre>&lt;a href=”/mdb/relation/list/s0t1p2.html”&gt;下一页&lt;/a&gt;&lt;/div&gt;</pre><p>Hence we can build a loop like this:</p><pre>for p in page:<br>  allp = p.find_all(‘a’, href = True)<br>  for x in allp:<br>    if x.get_text() == “下一页”:<br>      print(“More pages ahead, keep going!”)<br>      if x[‘href’] == “/mdb/relation/list/s1t0p” + str(i+1)+ “.html”:<br>        break<br>      else:</pre><pre>       # MORE CODE HERE<br>     <br>f.write(relations(soup))<br>print(relations(soup))</pre><h4>3. End the While loop</h4><p>Now let’s think about how to end the while loop and make sure the web scraper has scraped every single page. We haven’t set the while condition, so we can use the counter to do the restriction.</p><pre>while <strong>i &gt;= 0</strong>:</pre><pre>(content of the while loop)</pre><pre>…</pre><pre>else:</pre><pre><strong>i = -1</strong> <br></pre><p>Here, i is no longer greater or equal to 0, which will make the while loop break.</p><h4>4. Put everything together</h4><p>Let’s put everything together in a function and let Python write the result into a text file called “celebrity.txt”</p><p>The complete code for page turning function:</p><pre>def pageturning():<br>  f = open(“celebrity.txt”, “w+”)<br>  i = 0<br>  <br>  while i&gt;=0 :<br>    i += 1<br>    url_i = “<a href="http://www.1905.com/mdb/relation/list/">http://www.1905.com/mdb/relation/list/</a>&quot; + “s1t0p” + str(i) + “.html”<br>    referer = url_i<br>    user_agent = ‘YOUR_USER_AGENT’<br>    headers = {‘User-Agent’: user_agent, ‘Referer’: referer, ‘Connection’: ‘keep-alive’}<br>    <br>    try:<br>      req = urllib.request.Request(url = url_i, headers = headers)<br>      response = urlopen(req)<br>      html = response.read()<br>    except error.HTTPError as e:<br>      break<br>    <br>    soup = BeautifulSoup(html, “lxml”)<br>    <br>    page = soup.find_all(id = “new_page”)</pre><pre>    for p in page:<br>      allp = p.find_all(‘a’, href = True)<br>      <br>      for x in allp:<br>        if x.get_text() == “下一页”:<br>          print(“More pages ahead, keep going!”)<br>          # inner loop ends</pre><pre>      if x[‘href’] == “/mdb/relation/list/s1t0p” + str(i+1)+ “.html”:<br>        break</pre><pre>      else:<br>        i = -1<br>    f.write(relations(soup))<br>    print(relations(soup)) <br> print(“You have reached the end”)<br> <br> return</pre><p>Here’s what the result will look like: the modified version of our web scraper automatically turns the page once it reaches the end of the page, and generates 1387 lines of results in total.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*GP3LmhFeXCiNpBdKebwjtw.gif" /><figcaption>Result text file “celebrity.txt”</figcaption></figure><h3><strong>Summary</strong></h3><p>Hopefully this article can help you establish some idea of developing a better Python web scraper. There are definitely many other ways to implement a page-turning function. If you are certain about the total number of pages that you want to scrape, you can simply put the limit as your loop condition. However, when different websites have different page numbers, this way of implementation applies to more general cases. As long as you know how to keep track of the page number and be able to set a restriction while your web scraper is collecting data, you are all good.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6233f2d10c3f" width="1" height="1" alt=""><hr><p><a href="https://levelup.gitconnected.com/make-your-python-web-scraper-smarter-6233f2d10c3f">Make Your Python Web Scraper Smarter</a> was originally published in <a href="https://levelup.gitconnected.com/">Level Up Coding</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Quick Web Scraping with Python & Beautiful Soup]]></title>
            <link>https://levelup.gitconnected.com/quick-web-scraping-with-python-beautiful-soup-4dde18468f1f?source=rss-b3c4a67e76b6------2</link>
            <guid isPermaLink="false">https://medium.com/p/4dde18468f1f</guid>
            <category><![CDATA[web-crawling]]></category>
            <category><![CDATA[beautifulsoup]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[web-scraping]]></category>
            <dc:creator><![CDATA[Riley Huang]]></dc:creator>
            <pubDate>Sat, 15 Jun 2019 06:00:14 GMT</pubDate>
            <atom:updated>2019-06-18T07:18:32.914Z</atom:updated>
            <content:encoded><![CDATA[<h3>Quick Web Scraping with Python and Beautiful Soup</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/780/1*-ZQxCcXWY0nhQms2vZYDKQ.jpeg" /></figure><p>Web scraping allows you to download the HTML of a website and extract the data that you need. Using Python with Beautiful Soup is an excellent way to scrape the web.</p><h3>Beautiful Soup</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/490/1*NZz995dKNIjXnRqDroCqWg.png" /></figure><p>One of the many packages you could use while doing data scraping is Beautiful Soup. Beautiful Soup is a python package for parsing HTML and XML documents and extracting data. To perform web scraping, we also need urllib to connect the webpage.</p><h3>Environment Set Up</h3><p>First, install the following python packages.</p><pre>pip install requests</pre><pre>pip install beautifulsoup4</pre><p>Then, we can start importing all the necessary packages.</p><pre>import requests</pre><pre>from urllib import request, response, error, parse</pre><pre>from urllib.request import urlopen</pre><pre>from bs4 import BeautifulSoup</pre><h3><strong>Beautiful Soup Object</strong></h3><p>There are three objects under BeautifulSoup:</p><ul><li>BeautifulSoup</li><li>Tag</li><li>NavigableString</li></ul><h4><strong>Creating a BeautifulSoup object is the first step of any project using Beautiful Soup</strong></h4><p>There are two ways to create your BeautifulSoup object.</p><ul><li>Use string</li></ul><pre>soup_string = BeautifulSoup(“&lt;p&gt;Hello!&lt;/p&gt;”)</pre><ul><li>Use urlopen to create a BeautifulSoup object. This is the most common way of creating a BeautifulSoup object.</li></ul><pre>url = “<em>PUT_YOUR_URL_HERE</em>”</pre><pre>html = urlopen(url)</pre><pre>soup = BeautifulSoup(html, &quot;lxml&quot;) <br># here, the &quot;lxml&quot; is the html parser</pre><h3>Obtaining data by using BeautifulSoup</h3><p>Let’s use BeautifulSoup to do a simple data extraction. Say I want to have a quick glance of the Boston University facts and statistics on their <a href="http://www.bu.edu/president/boston-university-facts-stats/">website</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/360/1*JVZTQ0OR4vYJDnlzMli1lw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/360/1*fGuVvRiwtHw0_YqXXol4qg.png" /></figure><p>First, we want to obtain the title of this website.</p><pre>url = “<a href="http://www.bu.edu/president/boston-university-facts-stats/">http://www.bu.edu/president/boston-university-facts-stats/</a>”</pre><pre>html = urlopen(url)</pre><pre>soup = BeautifulSoup(html, “lxml”)</pre><pre>title = soup.title </pre><pre>titleText = title.get_text()</pre><pre>print(titleText)</pre><p>This will print out the text of the title:</p><pre>BU Facts &amp; Stats | Office of the President</pre><p>If you don’t do the final step titleText = title.get_text(), your web scraper will give you the following result instead of a clean text.</p><pre>&lt;title&gt;BU Facts &amp;amp; Stats | Office of the President&lt;/title&gt;</pre><p>There are many ways that BeautifulSoup allows you to find specific elements. Here are some of the common ones:</p><pre>find(), find_all(), find_parent(), find_parents(), find_next_sibling(), find_next_siblings(), find_previous_sibling(), find_previous_siblings(), find_next(), find_all_next()</pre><p>BeautifulSoup is powerful enough to do any data extraction you can think of. Here are some other simple data extractions you can do with it:</p><ul><li>soup.p.attrs[&#39;name&#39;] #obtain the &#39;name&#39; attribute in &lt;p&gt; tag</li><li>soup.select(&#39;ul&#39;)[&#39;id&#39;] # obtain &#39;id&#39; attribute in &#39;ul&#39;</li><li>soup.find_all(re.complie(&quot;^b&quot;)) # finds all the tags whose names start with &quot;b&quot;, for example &lt;body&gt; tag</li><li>soup.find_all(&quot;a&quot;, string = &quot;Name&quot;) # finds all the &lt;a&gt; tags whose .string is &quot;Name&quot;</li></ul><p>In this example we only need find() and find_all() to find specific data.</p><p>find_all() allows you to obtain <strong>all</strong> the elements based on the restrictions you put inside the parenthesis.</p><p>find() allows you to extract the very <strong>first</strong> element that satisfies your restriction.</p><h4>Step 1: Identifying ranges of tags you are scraping</h4><p>Right-click anywhere on the webpage and go to “inspect” and select the element that we want to inspect. There is a &lt;section class = &quot;facts-categories&quot;&gt; that consists of multiple div tags.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/496/1*kyD7POYFc5CxEIkXeSSjSA.png" /><figcaption>The section that we want</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/373/1*ayfJ-y_mZGm4brx88M-VQQ.png" /><figcaption>One of many &lt;div&gt; tags under &lt;section class =”facts-categories”&gt;</figcaption></figure><p>Each div tags has corresponding data that we want to obtain, and what we need to do is to use BeautifulSoup to go to the section, and then find all the data content in each &lt;div class = &quot;facts-wrapper&quot;&gt;. We can use find_all() to do that.</p><pre>section = soup.find_all(‘section’, class_=’facts-categories’)</pre><p>By doing this, we are now in the range of the section whose CSS class is facts-categories. Next, we want to loop over our web scraper to every single div tags under this section, which contains two parts: a sub-category, in &lt;h5&gt;&lt;/h5&gt; tag, and the corresponding data under this sub-category, which can be found in &lt;li class = &quot;list-item&quot;&gt;.</p><p>For example, here we have the first sub-category: “Community”, it contains data about Student Body, Living Alumni, Total Employees…etc.</p><h4>Step 2: Nesting all the loops</h4><p>We want to construct a nested loop for the web scraper to iterate every single list that contains our desired data.</p><pre>section = soup.find_all(‘section’, class_=’facts-categories’)</pre><pre>for elem in section:<br>    wrappers = elem.find_all(‘div’)<br>    for x in wrappers: <br>        title = x.find(‘h5’).get_text()<br>        print(title)<br>        detail = x.find_all(‘ul’)<br>        for row in detail:<br>            for l in row.find_all(‘li’):<br>                text = l.find(‘p’).get_text() <br>                value = l.find(‘span’, class_ = ‘value’).get_text()<br>                print (text + value)<br>            print(&quot;----------&quot;)</pre><p>Awesome, now we can put the code into a function and run it. Part of the result we get will look like this:</p><pre>BU Facts &amp; Stats | Office of the President<br>Community<br>Student Body34,262<br>Living Alumni377,900+<br>Total Employees10,182<br>Faculty4,021<br>Non-Degree Students2,232<br>Graduate &amp; Professional Students15,238<br>Undergraduate Students16,792<br>----------<br>Campus<br>Classrooms544<br>Buildings310+<br>Laboratories2,326<br>Libraries21<br>Campus Area (acres)134<br>----------<br>Academics<br>Study Abroad Programs90+<br>Average Class Size27<br>Faculty4,021<br>Student/Faculty Ratio10:1<br>Schools and Colleges17<br>Programs of Study300+<br>----------<br>Grant &amp; Contract Awards<br>Research Awards$486.8M<br>BMC Clinical Research Grants$116M</pre><pre>......</pre><h4>Summary</h4><p>Python and BeautifulSoup package make web scraping much easier.</p><p>Hopefully this simple web scraping example gives you an introduction of BeautifulSoup and some idea of building a basic web scraper.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4dde18468f1f" width="1" height="1" alt=""><hr><p><a href="https://levelup.gitconnected.com/quick-web-scraping-with-python-beautiful-soup-4dde18468f1f">Quick Web Scraping with Python &amp; Beautiful Soup</a> was originally published in <a href="https://levelup.gitconnected.com/">Level Up Coding</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Gale Shapley Algorithm and Stable Matching]]></title>
            <link>https://medium.com/@yunhanh/gale-shapley-algorithm-and-stable-matching-dbf1bf748541?source=rss-b3c4a67e76b6------2</link>
            <guid isPermaLink="false">https://medium.com/p/dbf1bf748541</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[algorithmic-design]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[technology]]></category>
            <dc:creator><![CDATA[Riley Huang]]></dc:creator>
            <pubDate>Fri, 14 Jun 2019 02:59:50 GMT</pubDate>
            <atom:updated>2019-06-25T03:20:29.305Z</atom:updated>
            <content:encoded><![CDATA[<h3>Gale Shapley and Stable Matching Problem</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2HYA5jKq4LuJfUaGfgESGw.jpeg" /></figure><p>Let us assume a case that is impossible to happen in real life: a man, let’s<strong> </strong>call him m1, proposes to a woman, let’s call her w1, by one following the order of his preference list. If a woman is not “taken,” meaning she has not gotten paired<strong> </strong>up<strong> </strong>with<strong> </strong>a<strong> </strong>partner<strong> </strong>or she prefers m1 over her current partner m2, she will accept him and her new partner will be updated to m1. If she is already paired up with m3, another man, and she prefers m3 over m1, she rejects.</p><p>Now, think about the following question:</p><blockquote>Can a man or a woman end up better off by lying about his or her preferences?</blockquote><p>Suppose each participant has a preference list. A woman w supposedly prefers man m to m’, but both m and m’ are quite low on her list. If she lies about her preferences, meaning switching the order of m and m’ by falsely claiming the opposite order, will w end up being with m1, the man she truly prefers over m and m’?</p><p>This question explores the issue of truthfulness in the Stable Matching Problem and the Gale-Shapley algorithm used in this problem.</p><h3><strong>Stable Matching</strong></h3><p>Let’s first look at the definition of Stable Matching.</p><p><strong>A stable match is a perfect match with no unstable pair.</strong></p><ul><li>What is an <strong>Unstable Pair</strong>?</li></ul><blockquote><em>Given a set of preferences among men and women. Man m and woman w form an unstable pair if both:</em></blockquote><blockquote><em>- m prefers w to his matched woman</em></blockquote><blockquote><em>- w prefers m to her matched man</em></blockquote><p>For example:</p><p>man m1’s list:</p><p>w1, w2</p><p>m1 is engaged with w2</p><p>woman w1’s list:</p><p>m1, m2</p><p>w1 is engaged with m2</p><p>Here, m1-w1 is an unstable pair</p><ul><li>What is a <strong>Perfect Match</strong>?</li></ul><blockquote><em>A perfect match MA is a set of ordered pairs m-w with m &lt;- M and w &lt;- W such that:</em></blockquote><blockquote><em>- Each man m &lt;- M appears in at most one pair of MA</em></blockquote><blockquote><em>- Each woman w &lt;- W appears in at most one pair of MA</em></blockquote><blockquote><em>A matching MA is perfect is |MA| = |M| = |W| = n</em></blockquote><p><strong>The goal of a stable matching problem is to find a stable match (if one exists), given the preference lists of n men and n women.</strong></p><h3><strong>Gale-Shapley and Man-Optimality</strong></h3><p>To find a stable match, an intuitive method called the<strong> </strong>“Gale-Shapley deferred acceptance algorithm” is used.</p><p>The algorithm is basically the same as the process of pairing up men and women in the case I just asked you to imagine. To put it into a more general case, it is the following:</p><p><em>1. First, initialize M to empty matching</em></p><p><em>2. A WHILE loop. While some man m is unmatched and hasn’t proposed to every single woman on his list</em></p><p><em>In this loop, get w, the first woman on m’s list to whom m has not proposed yet</em></p><p><em>IF w is unmatched, add m-w to matching M</em></p><p><em>ELSE IF w prefers m to current partner m’, replace m’-w with m-w in matching M</em></p><p><em>ELSE, w rejects m</em></p><p><em>3. Finish the loop, return stable matching M</em></p><p>It is known that Gale-Shapley matching is <strong>man-optimal</strong>. To see further proof of this claim, feel free to read <a href="https://www.cs.umd.edu/class/spring2017/cmsc451/GS.pdf">this</a>.</p><p>Now that we understand the process of the<strong> </strong>Gale-Shapley algorithm and its way of finding a stable match, let’s get back to our original question: <strong>can a man or a woman end up better off by lying about his or her preferences?</strong></p><p>This is a rather difficult question to prove if you want to give a proof that for any set of preference lists, lying about the preference of partners can improve a man or a woman’s final match in the Gale-Shapley algorithm. Hence, here I choose to come up with an example of a set of preference lists for men and women and there exists a switch that can improve a woman’s partner in the end.</p><p>Preference list of men:</p><p>D: A &gt; B &gt; C</p><p>E: B &gt; A &gt; C</p><p>F: A &gt; B &gt; C</p><p>Preference list of women:</p><p><strong>A: E &gt; D &gt; F</strong></p><p>B: D &gt; E &gt; F</p><p>C: D &gt; E &gt; F</p><p>If woman A lies, updated preference list of women:</p><p><strong>A: E &gt; F &gt; D</strong> (she lies about preferring F over D but she actually does not)</p><p>B: D &gt; E &gt; F</p><p>C: D &gt; E &gt; F</p><p>If we run the Gale-Shapley on the first two preference lists above, we obtain the final match to be D-A, E-B, F-C, noticing that A is paired with her second preference.</p><p>If we run the Gale-Shapley on the updated preference list of women if A lies, we obtain the match to be D-B, E-A, F-C, noticing that A ends up with her first preference.</p><p>Voila! We now proved that lying about one’s preference list makes it possible for men or women to<strong> </strong>end up better off<strong>; </strong>that<strong> </strong>is<strong>,</strong> with their more desired partner.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dbf1bf748541" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>